論文の概要: Relevant Walk Search for Explaining Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2605.23673v1
• Date: Fri, 22 May 2026 14:21:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-25 17:29:20.388942
• Title: Relevant Walk Search for Explaining Graph Neural Networks
• Title（参考訳）: グラフニューラルネットワークの解説のための関連ウォークサーチ
• Authors: Ping Xiong, Thomas Schnake, Michael Gastegger, Grégoire Montavon, Klaus-Robert Müller, Shinichi Nakajima,
• Abstract要約: グラフネットワーク(GNN)は、機械学習分析において重要な機械学習ツールとなっている。 GNN(GNN-LRP)の階層的関連性伝搬は、ネットワーク内の重要な情報フローを明らかにするために、エンフウォークの関連性を評価する。 我々は,GNN-LRPの大規模問題への適用性を大幅に低減する,最高時間$K$関連ウォークを求めるエムタイムアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 23.612178520096162
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Neural Networks (GNNs) have become important machine learning tools for graph analysis, and its explainability is crucial for safety, fairness, and robustness. Layer-wise relevance propagation for GNNs (GNN-LRP) evaluates the relevance of \emph{walks} to reveal important information flows in the network, and provides higher-order explanations, which have been shown to be superior to the lower-order, i.e., node-/edge-level, explanations. However, identifying relevant walks by GNN-LRP requires {\em exponential} computational complexity with respect to the network depth, which we will remedy in this paper. Specifically, we propose {\em polynomial-time} algorithms for finding top-$K$ relevant walks, which drastically reduces the computation and thus increases the applicability of GNN-LRP to large-scale problems. Our proposed algorithms are based on the \emph{max-product} algorithm -- a common tool for finding the maximum likelihood configurations in probabilistic graphical models -- and can find the most relevant walks exactly at the neuron level and approximately at the node level. Our experiments demonstrate the performance of our algorithms at scale and their utility across application domains, i.e., on epidemiology, molecular, and natural language benchmarks. We provide our codes under \href{https://github.com/xiong-ping/rel_walk_gnnlrp}{github.com/xiong-ping/rel\_walk\_gnnlrp}.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、グラフ解析において重要な機械学習ツールとなり、その説明可能性は安全性、公正性、堅牢性に不可欠である。 GNN(GNN-LRP)の階層的関連性伝播は、ネットワーク内の重要な情報フローを明らかにするために、emph{walks} の関連性を評価し、ノード/エッジレベルの説明よりも優れていることが示されている高階の説明を提供する。 しかしながら、GNN-LRPによる関連ウォークの特定には、ネットワーク深度に関する計算複雑性が要求される。 具体的には,計算量を大幅に削減し,大規模問題へのGNN-LRPの適用性を高めることを目的として,トップ$Kの関連ウォークを求めるアルゴリズムを提案する。 提案アルゴリズムは,確率的グラフィカルモデルにおける最大可能性構成を求める一般的なツールであるemph{max-product}アルゴリズムに基づいており,ニューロンレベルで,ほぼノードレベルで,最も関連性の高いウォークを見つけることができる。 我々の実験は、我々のアルゴリズムの大規模性能と応用分野、すなわち疫学、分子、自然言語のベンチマークにおける有用性を実証した。 We provide our codes under \href{https://github.com/xiong-ping/rel_walk_gnnlrp}{github.com/xiong-ping/rel\_walk\_gnnlrp}。

関連論文リスト

• Efficient Higher-order Subgraph Attribution via Message Passing [23.932427893302826]
  GNN-LRPのような高階の解釈スキームは、異なる機能がどのように相互作用するかを明らかにする強力なツールとして登場した。 線形時間でGNN-LRPでサブグラフを属性化できる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-05-21T12:16:19Z)
• On the Complexity of Optimal Graph Rewiring for Oversmoothing and Oversquashing in Graph Neural Networks [2.8427946758947304]
  グラフニューラルネットワーク(GNN)は、ディープアーキテクチャへのスケールアップにおいて、2つの根本的な課題に直面している。 オーバースムーシングとオーバースキャッシングは、基礎となるグラフ構造と密接に結びついている。 本稿では,そのようなグラフ構造最適化の計算複雑性について理論的に考察する。
  論文  参考訳（メタデータ） (2026-03-27T07:50:42Z)
• DeltaGNN: Graph Neural Network with Information Flow Control [5.563171090433323]
  グラフニューラルネットワーク(GNN)は、メッセージパッシングプロセスの近傍集約を通じてグラフ構造化データを処理するように設計されている。 メッセージパッシングにより、GNNは短距離空間的相互作用を理解できるだけでなく、過度なスムーシングや過度なスカッシングに悩まされる。 本稿では,線形計算オーバーヘッドを伴うオーバー・スムーシングとオーバー・スキャッシングに対処するための,emph情報フロー制御機構を提案する。 さまざまなサイズ、トポロジ、密度、ホモフィリック比のグラフを含む10の実世界のデータセットを対象に、我々のモデルをベンチマークし、優れたパフォーマンスを示す。
  論文  参考訳（メタデータ） (2025-01-10T14:34:20Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。 実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
  論文  参考訳（メタデータ） (2023-10-05T02:58:29Z)
• Layer-wise training for self-supervised learning on graphs [0.0]
  大規模グラフ上でのグラフニューラルネットワーク(GNN)のエンドツーエンドトレーニングは、いくつかのメモリと計算上の課題を示す。 本稿では,GNN層を自己教師型で学習するアルゴリズムであるレイヤワイズ正規化グラフInfomaxを提案する。
  論文  参考訳（メタデータ） (2023-09-04T10:23:39Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  我々は,GNN予測に対する忠実な説明を提供するためにDGREEを提案する。 GNNの情報生成と集約機構を分解することにより、DECREEは入力グラフの特定のコンポーネントのコントリビューションを最終的な予測に追跡することができる。 また,従来の手法で見過ごされるグラフノード間の複雑な相互作用を明らかにするために,サブグラフレベルの解釈アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-05-22T10:29:52Z)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  グラフニューラルネットワーク(GNN)の大規模グラフトレーニングは、非常に難しい問題である 本稿では,既存の問題に対処するため,EnGCNという新たなアンサンブルトレーニング手法を提案する。 提案手法は,大規模データセット上でのSOTA(State-of-the-art)の性能向上を実現している。
  論文  参考訳（メタデータ） (2022-10-14T03:43:05Z)
• Decoupling the Depth and Scope of Graph Neural Networks [21.273445344654597]
  最先端のグラフニューラルネットワーク(GNN)は、グラフとモデルサイズに関して、スケーラビリティに制限がある。 本稿では,GNNの深度と範囲を分離する設計原理を提案する。 我々の設計は、計算量やハードウェアコストの大幅な削減により、大幅な精度向上を実現している。
  論文  参考訳（メタデータ） (2022-01-19T20:52:42Z)
• Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
  GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。 高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。 このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
  論文  参考訳（メタデータ） (2020-07-03T09:30:07Z)
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification [70.50751397870972]
  FastGATは、スペクトルスペーシフィケーションを用いて、注目に基づくGNNを軽量にし、入力グラフの最適プルーニングを生成する手法である。 我々は,ノード分類タスクのための大規模実世界のグラフデータセット上でFastGATを実験的に評価した。
  論文  参考訳（メタデータ） (2020-06-15T22:07:54Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。