論文の概要: Connectivity-Guided Sparsification of 2-FWL GNNs: Preserving Full Expressivity with Improved Efficiency

• arxiv url: http://arxiv.org/abs/2511.12838v1
• Date: Sun, 16 Nov 2025 23:46:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-18 14:36:24.57277
• Title: Connectivity-Guided Sparsification of 2-FWL GNNs: Preserving Full Expressivity with Improved Efficiency
• Title（参考訳）: 2-FWL GNNの接続性誘導型スカラー化:効率向上による完全表現性保存
• Authors: Rongqin Chen, Fan Mo, Pak Lon Ip, Shenghui Zhang, Dan Wu, Ye Li, Leong Hou U,
• Abstract要約: 接続性を考慮したスペーシフィケーションフレームワークである textbfCo-Sparsify を提案する。 私たちのキーとなる洞察は、3ノードの相互作用は、エンファンビコネクテッドなコンポーネントの中でのみ、表現的に必要であるということです。 Co-Sparsify は 2-FWL テストと同じくらい表現力があることを示す。
• 参考スコア（独自算出の注目度）: 15.330129666665927
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Higher-order Graph Neural Networks (HOGNNs) based on the 2-FWL test achieve superior expressivity by modeling 2- and 3-node interactions, but at $\mathcal{O}(n^3)$ computational cost. However, this computational burden is typically mitigated by existing efficiency methods at the cost of reduced expressivity. We propose \textbf{Co-Sparsify}, a connectivity-aware sparsification framework that eliminates \emph{provably redundant} computations while preserving full 2-FWL expressive power. Our key insight is that 3-node interactions are expressively necessary only within \emph{biconnected components} -- maximal subgraphs where every pair of nodes lies on a cycle. Outside these components, structural relationships can be fully captured via 2-node message passing or global readout, rendering higher-order modeling unnecessary. Co-Sparsify restricts 2-node message passing to connected components and 3-node interactions to biconnected ones, removing computation without approximation or sampling. We prove that Co-Sparsified GNNs are as expressive as the 2-FWL test. Empirically, on PPGN, Co-Sparsify matches or exceeds accuracy on synthetic substructure counting tasks and achieves state-of-the-art performance on real-world benchmarks (ZINC, QM9). This study demonstrates that high expressivity and scalability are not mutually exclusive: principled, topology-guided sparsification enables powerful, efficient GNNs with theoretical guarantees.
• Abstract（参考訳）: 2-FWLテストに基づく高次グラフニューラルネットワーク(HOGNN)は、2-および3-ノード相互作用をモデル化することで優れた表現性を実現するが、$\mathcal{O}(n^3)$計算コストはかかる。 しかし、この計算負担は、圧縮率の低下を犠牲にして、既存の効率方法によって軽減されるのが一般的である。 完全2-FWL表現力を保ちながら, \emph{provably redundant} 計算を不要にする接続対応スペーシングフレームワークである \textbf{Co-Sparsify} を提案する。 私たちのキーとなる洞察は、3つのノード間の相互作用は、すべてのノードがサイクル上にある最大部分グラフである \emph{bi connected components} の中でのみ、表現的に必要であるということです。 これらのコンポーネント以外では、構造的関係は2ノードのメッセージパッシングやグローバルな読み込みを通じて完全にキャプチャできるため、高次のモデリングは不要である。 Co-Sparsifyは、接続されたコンポーネントへの2ノードのメッセージパッシングと3ノードのインタラクションを2つに制限し、近似やサンプリングなしに計算を削除する。 共分散GNNは2-FWLテストと同じくらい表現力があることを示す。 実証的には、PPGNでは、Co-Sparsifyは合成サブストラクチャカウントタスクに適合または精度を上回り、実世界のベンチマーク(ZINC, QM9)で最先端のパフォーマンスを達成する。 本研究は,高表現性とスケーラビリティが相互排他的ではないことを示す。

関連論文リスト

• Universally Invariant Learning in Equivariant GNNs [47.74131538835446]
  等変グラフニューラルネットワーク(GNN)は、様々なアプリケーションで大きな成功を収めている。 完全同変GNNを構築するための理論的基盤となる枠組みを提案する。 以上の結果から,少数の層で優れた完全性と優れた性能を示すことができた。
  論文  参考訳（メタデータ） (2025-10-15T05:50:16Z)
• Constructive Lyapunov Functions via Topology-Preserving Neural Networks [0.0]
  ONNは収束率、エッジ効率、計算複雑性の順序-最適性能を達成する。 3Mノードのセマンティックネットワークにおける実証的な検証は、ベースライン法よりも99.75%改善されている。 ORTSFをトランスに組み込むことで、14.7%のパープレキシティ低減と2.3の高速化を実現している。
  論文  参考訳（メタデータ） (2025-10-10T17:46:52Z)
• DUPLEX: Dual GAT for Complex Embedding of Directed Graphs [17.84142263305169]
  現在の有向グラフ埋め込み法は、非有向技術に基づいて構築されるが、しばしば有向エッジ情報を不適切にキャプチャする。 有向グラフの複雑な埋め込みのための帰納的フレームワークであるDUPlexを提案する。 DUPlexは、特に疎結合なノードにおいて、最先端モデルよりも優れている。
  論文  参考訳（メタデータ） (2024-06-08T07:48:16Z)
• EntailE: Introducing Textual Entailment in Commonsense Knowledge Graph Completion [54.12709176438264]
  Commonsense knowledge graph(CSKG)は、名前付きエンティティ、短いフレーズ、イベントをノードとして表現するために自由形式のテキストを使用する。 現在の手法では意味的類似性を利用してグラフ密度を増大させるが、ノードとその関係のセマンティックな妥当性は未探索である。 そこで本研究では,CSKGノード間の暗黙的な包絡関係を見つけるために,テキストエンテーメントを導入し,同じ概念クラス内のサブグラフ接続ノードを効果的に密度化することを提案する。
  論文  参考訳（メタデータ） (2024-02-15T02:27:23Z)
• Efficient Link Prediction via GNN Layers Induced by Negative Sampling [86.87385758192566]
  リンク予測のためのグラフニューラルネットワーク(GNN)は、緩やかに2つの広いカテゴリに分けられる。 本稿では,新しいGNNアーキテクチャを提案する。このアーキテクチャでは,Emphforwardパスは,Emphboth陽性(典型的)と負陰性(アプローチに共通)のエッジに明示的に依存する。 これは、埋め込み自体を、正と負のサンプルの分離を好むフォワードパス特異的エネルギー関数の最小化子として再キャストすることで達成される。
  論文  参考訳（メタデータ） (2023-10-14T07:02:54Z)
• Binary Graph Convolutional Network with Capacity Exploration [58.99478502486377]
  ネットワークパラメータと入力ノード属性の両方を二項化するバイナリグラフ畳み込みネットワーク(Bi-GCN)を提案する。 我々のBi-GCNは、ネットワークパラメータと入力データの両方で平均31倍のメモリ消費を削減でき、推論速度を平均51倍に加速できる。
  論文  参考訳（メタデータ） (2022-10-24T12:05:17Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• The Curious Case of Convex Neural Networks [12.56278477726461]
  完全連結層と畳み込み層の両方に凸性制約を適用可能であることを示す。 a) IOC-NN(Input Output Convex Neural Networks)の自己正規化とオーバーフィッティング(オーバーフィッティング)の問題の低減; (b) 厳しい制約にもかかわらず、ベースマルチレイヤのパーセプトロンを上回り、ベースコンボリューションアーキテクチャと比較して同様のパフォーマンスを実現する。
  論文  参考訳（メタデータ） (2020-06-09T08:16:38Z)
• Bilinear Graph Neural Network with Neighbor Interactions [106.80781016591577]
  グラフニューラルネットワーク(GNN)は,グラフデータ上で表現を学習し,予測を行う強力なモデルである。 本稿では,グラフ畳み込み演算子を提案し,隣接するノードの表現の対の相互作用で重み付け和を増大させる。 このフレームワークをBGNN(Bilinear Graph Neural Network)と呼び、隣ノード間の双方向相互作用によるGNN表現能力を向上させる。
  論文  参考訳（メタデータ） (2020-02-10T06:43:38Z)

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

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