그래프 신경망 (GNN) 설명을 위한 관련 워크 탐색 (Relevant Walk Search)

그래프 신경망 (Graph Neural Networks, GNNs)은 그래프 분석을 위한 중요한 머신러닝 (machine learning) 도구가 되었으며, 이들의 설명 가능성 (explainability)은 안전성, 공정성 및 강건성 (robustness)을 위해 매우 중요합니다. GNN을 위한 계층별 관련성 전파 (Layer-wise relevance propagation for GNNs, GNN-LRP)는 네트워크 내의 중요한 정보 흐름을 드러내기 위해 extit{워크 (walks)}의 관련성을 평가하며, 저차원(즉, 노드/에지 수준) 설명보다 우수함이 입증된 고차원 설명을 제공합니다. 그러나 GNN-LRP를 통해 관련 워크를 식별하는 것은 네트워크 깊이에 따라 { extit{지수적 (exponential)}} 계산 복잡도를 요구하며, 본 논문에서는 이를 해결하고자 합니다. 구체적으로, 우리는 상위 $K$개의 관련 워크를 찾기 위한 { extit{다항 시간 (polynomial-time)}} 알고리즘을 제안하며, 이는 계산량을 획기적으로 줄여 대규모 문제에 대한 GNN-LRP의 적용 가능성을 높여줍니다. 우리가 제안하는 알고리즘은 확률적 그래픽 모델 (probabilistic graphical models)에서 최대 가능도 구성 (maximum likelihood configurations)을 찾는 일반적인 도구인 { extit{max-product}} 알고리즘을 기반으로 하며, 뉴런 (neuron) 수준에서는 가장 관련 있는 워크를 정확하게, 노드 (node) 수준에서는 근사적으로 찾아낼 수 있습니다. 우리의 실험은 대규모 환경에서의 알고리즘 성능과 역학 (epidemiology), 분자 (molecular), 자연어 (natural language) 벤치마크 등 다양한 응용 분야에서의 유용성을 입증합니다. 코드는
ef{https://github.com/xiong-ping/rel_walk_gnnlrp}{github.com/xiong-ping/rel_walk_gnnlrp}에서 제공합니다.