論文の概要: Local Fragments, Global Gains: Subgraph Counting using Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2305.19659v4
- Date: Wed, 05 Nov 2025 19:46:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-07 20:17:53.034892
- Title: Local Fragments, Global Gains: Subgraph Counting using Graph Neural Networks
- Title（参考訳）: ローカルフラグメントとグローバルゲイン:グラフニューラルネットワークを用いたサブグラフカウント
- Authors: Shubhajit Roy, Shrutimoy Das, Binita Maity, Anant Kumar, Anirban Dasgupta,
- Abstract要約: グラフ構造データの構造パターンを解析するための基本課題はグラフカウントである。
Wesfeiler-Leman (WL) アルゴリズムのローカライズされたバージョンを提案し、このタスクの表現性と計算効率を改善する。
- 参考スコア（独自算出の注目度）: 3.993513380816159
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Subgraph counting is a fundamental task for analyzing structural patterns in graph-structured data, with important applications in domains such as computational biology and social network analysis, where recurring motifs reveal functional and organizational properties. In this paper, we propose localized versions of the Weisfeiler-Leman (WL) algorithms to improve both expressivity and computational efficiency for this task. We introduce Local $k$-WL, which we prove to be more expressive than $k$-WL and at most as expressive as $(k+1)$-WL, and provide a characterization of patterns whose subgraph and induced subgraph counts are invariant under Local $k$-WL equivalence. To enhance scalability, we present two variants -- Layer $k$-WL and Recursive $k$-WL -- that achieve greater time and space efficiency compared to applying $k$-WL on the entire graph. Additionally, we propose a novel fragmentation technique that decomposes complex subgraphs into simpler subpatterns, enabling the exact count of all induced subgraphs of size at most $4$ using only $1$-WL, with extensions possible for larger patterns when $k>1$. Building on these ideas, we develop a three-stage differentiable learning framework that combines subpattern counts to compute counts of more complex motifs, bridging combinatorial algorithm design with machine learning approaches. We also compare the expressive power of Local $k$-WL with existing GNN hierarchies and demonstrate that, under bounded time complexity, our methods are more expressive than prior approaches.
- Abstract（参考訳）: グラフ構造データの構造パターンを解析するための基本課題はグラフカウントであり、計算生物学やソーシャルネットワーク分析といった分野において重要な応用があり、繰り返し発生するモチーフが機能的・組織的特性を示す。
本稿では,Weisfeiler-Leman(WL)アルゴリズムの局所化バージョンを提案する。
我々は、$k$-WLよりも表現力が高く、少なくとも$(k+1)$-WLほど表現力が高いことを証明したLocal $k$-WLを導入し、サブグラフと誘導されたサブグラフ数がLocal $k$-WL同値の下で不変であるパターンの特性を提供する。
スケーラビリティを向上させるために、グラフ全体に$k$-WLを適用するよりも、時間と空間の効率を高める2つのバリエーション、Layer $k$-WL と Recursive $k$-WL を提示する。
さらに、複雑な部分グラフを単純なサブパターンに分解し、$k>1$の場合に拡張可能な1ドル-WLの値で、最大4ドル以上の全てのインジェクションされたサブグラフを正確にカウントできる新しいフラグメンテーション手法を提案する。
これらのアイデアに基づいて,より複雑なモチーフの数を計算するために,サブパターン数を組み合わせた3段階の微分可能な学習フレームワークを開発し,組合せアルゴリズム設計と機械学習アプローチをブリッジする。
また、ローカル$k$-WLの表現力と既存のGNN階層を比較し、境界時間複雑性の下では、従来の手法よりも表現力が高いことを示す。
関連論文リスト
- Improving the Expressiveness of $K$-hop Message-Passing GNNs by Injecting Contextualized Substructure Information [17.56609419806051]
K$ホップメッセージパスGNNの表現力を高めるために,テキストサブストラクチャ符号化関数を提案する。
提案手法は,従来の$K$-hopグラフニューラルネットワークや1-WLサブグラフGNNよりも強力である。
論文 参考訳（メタデータ） (2024-06-27T15:10:56Z) - Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning [17.646846505225735]
グラフ同型テストの新しい階層構造と対応するGNNフレームワークである$r$-$ell$MPNNを導入し、最大長さ$r + 2$までサイクルをカウントできる。
特に、$r$-$ell$WL がサクタスグラフの準同型を数えることができることを示す。
提案した$r$-$ell$MPNNの複数の合成データセットに対する表現力とカウント力を実証的に検証し,様々な実世界のデータセットに対する最先端の予測性能を示す。
論文 参考訳（メタデータ） (2024-03-20T16:58:28Z) - Weisfeiler and Leman Go Measurement Modeling: Probing the Validity of the WL Test [58.1543112860658]
グラフ機械学習実践者の表現力概念化と$k$-WLとの相違を明らかにする。
ベンチマークに基づく表現力の拡張的定義と測定について論じる。
論文 参考訳（メタデータ） (2023-07-11T20:06:12Z) - Extending the Design Space of Graph Neural Networks by Rethinking
Folklore Weisfeiler-Lehman [66.23316415757456]
近年、グラフニューラルネットワーク(GNN)の最も人気のあるフレームワークとして、メッセージパッシングニューラルネットワーク(MPNN)が登場している。
しかし、その表現力は1次元のWeisfeiler-Lehman (1-WL) テストによって制限される。
我々は、任意の同変集合をすべてのノードの代わりに隣人と考える拡張、$(k,t)$-FWLを提案する。
N$2-GNN は ZINC-Subset (0.059) で記録破りの結果を達成し、以前の SOTA の成績を 10.6% 上回った。
論文 参考訳（メタデータ） (2023-06-05T21:35:32Z) - From Relational Pooling to Subgraph GNNs: A Universal Framework for More
Expressive Graph Neural Networks [8.121462458089141]
メッセージパッシングニューラルネットワークの表現力を向上させるために、ノードにラベルを割り当てる方法を示す。
実験により,本手法は普遍的に互換性があり,任意のベースGNNモデルの表現性を向上させることができることを示した。
私たちの$k,l$-GNNは、多くの合成および実世界のデータセットで優れたパフォーマンスを実現しています。
論文 参考訳（メタデータ） (2023-05-08T18:00:50Z) - A Practical, Progressively-Expressive GNN [27.267362661067285]
近年,メッセージパッシングニューラルネットワーク(MPNN)がグラフニューラルネットワーク(GNN)の主流となっている。
MPNNは、グラフ同型テストのフレームワークにおいてグラフを区別する1次元のWeisfeiler-Leman (1-WL)テストと同じくらい強力である。
我々は,k-tuples ノードから =c 連結成分上で定義された=k ノードの集合へ移動することで,k-WL から k-WL への複雑性を大幅に低減した (k, c)(=)-SETWL 階層を提案する。
論文 参考訳（メタデータ） (2022-10-18T01:27:21Z) - Two-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link
Prediction [61.01337335214126]
グラフニューラルネットワーク(GNN)のリンク予測
リンク予測のためのほとんどの既存のGNNは、1次元Weisfeiler-Lehman (1-WL) テストに基づいている。
テキスト2次元Weisfeiler-Lehman (2-WL) テストに基づいて,ノード対(リンク)表現を直接取得可能な,まったく異なるアプローチを提案する。
論文 参考訳（メタデータ） (2022-06-20T04:50:38Z) - Representation Power of Graph Neural Networks: Improved Expressivity via
Algebraic Analysis [124.97061497512804]
標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。
また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
論文 参考訳（メタデータ） (2022-05-19T18:40:25Z) - Twin Weisfeiler-Lehman: High Expressive GNNs for Graph Classification [48.087302573188396]
本稿では,ノードラベルとノードIDを同時に渡す新しいグラフ同型テスト手法Twin-WLを提案する。
2つのツイン-GNNは、従来のメッセージパッシングGNNよりも表現力が高いことが証明された。
論文 参考訳（メタデータ） (2022-03-22T12:58:03Z) - Walk Message Passing Neural Networks and Second-Order Graph Neural
Networks [4.355567556995855]
我々は,新しいタイプのMPNNである$ell$-walk MPNNを紹介した。
2ドル(約2万円)のMPNNが表現力で2-WLと一致していることを示す。
特に、W[$ell$]を表現力で一致させるために、各層で$ell-1$行列乗法を許す。
論文 参考訳（メタデータ） (2020-06-16T20:24:01Z) - Improving Graph Neural Network Expressivity via Subgraph Isomorphism
Counting [63.04999833264299]
グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。
Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。
グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
論文 参考訳（メタデータ） (2020-06-16T15:30:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。