그래프 신경망 (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}에서 제공합니다.