ラプラシアンの先へ：グラフニューラルネットワークのための二重確率行列

arXiv cs.LG / 2026/4/17

📰 ニュースDeveloper Stack & InfrastructureIdeas & Deep AnalysisModels & Research

共有:

要点

本論文は、GNNの構造メッセージパッシングにおける従来のラプラシアン／隣接行列の代わりに、修正ラプラシアンの逆行列から導く二重確率グラフ行列（DSM）を用いることで、連続的な多ホップ近接性と厳密な局所中心性を自然に符号化することを提案しています。
厳密な行列反転はO(n^3)で計算不可能なため、Neumann級数の打ち切りによる近似でDSMをスケーラブルに推定し、その基盤としてDsmNetを構築します。
打ち切りにより確率質量が漏れる問題に対して、Residual Mass Compensation（DsmNet-compensate）を導入し、解析的に打ち切り末尾の質量を自己ループへ再注入することで、行確率性（row-stochasticity）を厳密に回復します。
理論および実験の双方で、O(K|E|)の効率的な計算、ディリクレエネルギー減衰の境界によるオーバースムージング抑制、同質的ベンチマークでの有効性が示され、さらに異質的トポロジーにおけるDSMの限界も分析されています。
最後にDSMを、グラフニューラルネットワークに留まらない連続的構造エンコーディングとして、グラフTransformerへの適用可能性と、グラフ種別ごとの理論的境界とともに位置づけています。

Abstract

グラフニューラルネットワーク（GNN）は従来、構造的なメッセージパッシングに標準のラプラシアン行列または隣接行列に依存してきました。本研究では、従来のラプラシアンを、修正ラプラシアンの逆数から導出した双重確率グラフ行列（Doubly Stochastic graph Matrix; DSM）に置き換えることで、連続的な多ホップ近接性と厳密な局所中心性を自然に符号化します。厳密な行列反転に伴う手に負えない計算量

O(n^3)

を克服するために、まず切り詰めたネーマン級数を用いてDSMをスケーラブルに近似し、これを提案手法DsmNetの基盤とします。さらに、代数的な切り詰めは本質的に確率質量の漏れを引き起こすため、DsmNet-compensateを導入します。この変種には、切り詰められたテール質量を解析的に自己ループへ再注入する、数学的に厳密な残差質量補償（Residual Mass Compensation）機構が備わっており、行確率性（row-stochasticity）を厳密に回復し、構造的支配性を確実に取り戻します。広範な理論的および実証的分析により、切り離した（デカップルした）アーキテクチャが

O(K|E|)

時間で効率的に動作し、ディリクレ・エネルギーの減衰を抑えることで過スムージングを効果的に緩和することを示します。同相性（homophilic）のベンチマークで頑健な実験的裏付けも得られました。最後に、異質性（heterophilic）のトポロジーにおけるDSMの理論的な境界を確立し、グラフ・トランスフォーマに対する連続的な構造符号化としての汎用性も実証します。