論文の概要: Enhanced Expressivity in Graph Neural Networks with Lanczos-Based Linear Constraints

• arxiv url: http://arxiv.org/abs/2408.12334v1
• Date: Thu, 22 Aug 2024 12:22:00 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-23 14:03:43.040018
• Title: Enhanced Expressivity in Graph Neural Networks with Lanczos-Based Linear Constraints
• Title（参考訳）: Lanczosをベースとした線形制約を持つグラフニューラルネットワークにおける表現性の向上
• Authors: Niloofar Azizi, Nils Kriege, Horst Bischof,
• Abstract要約: グラフニューラルネットワーク(GNN)はグラフ構造化データの処理に優れるが、リンク予測タスクでは性能が劣ることが多い。 グラフラプラシア行列の固有基底に誘導された部分グラフを埋め込むことによりGNNの表現性を高める新しい手法を提案する。 提案手法は,PubMedとOGBL-Vesselのデータセットから,5%と10%のデータしか必要とせず,20倍と10倍の高速化を実現する。
• 参考スコア（独自算出の注目度）: 7.605749412696919
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Graph Neural Networks (GNNs) excel in handling graph-structured data but often underperform in link prediction tasks compared to classical methods, mainly due to the limitations of the commonly used Message Passing GNNs (MPNNs). Notably, their ability to distinguish non-isomorphic graphs is limited by the 1-dimensional Weisfeiler-Lehman test. Our study presents a novel method to enhance the expressivity of GNNs by embedding induced subgraphs into the graph Laplacian matrix's eigenbasis. We introduce a Learnable Lanczos algorithm with Linear Constraints (LLwLC), proposing two novel subgraph extraction strategies: encoding vertex-deleted subgraphs and applying Neumann eigenvalue constraints. For the former, we conjecture that LLwLC establishes a universal approximator, offering efficient time complexity. The latter focuses on link representations enabling differentiation between $k$-regular graphs and node automorphism, a vital aspect for link prediction tasks. Our approach results in an extremely lightweight architecture, reducing the need for extensive training datasets. Empirically, our method improves performance in challenging link prediction tasks across benchmark datasets, establishing its practical utility and supporting our theoretical findings. Notably, LLwLC achieves 20x and 10x speedup by only requiring 5% and 10% data from the PubMed and OGBL-Vessel datasets while comparing to the state-of-the-art.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)はグラフ構造化データの処理に優れるが、一般的に使用されるメッセージパッシングGNN(MPNN)の制限により、従来の手法と比較してリンク予測タスクでは性能が劣ることが多い。 特に、非同型グラフを区別する能力は、1次元ワイスフェイラー・リーマン検定によって制限される。 本研究では,GNNの表現性をグラフラプラシア行列の固有基底に埋め込むことにより向上させる新しい手法を提案する。 本稿では,Learnerable LanczosアルゴリズムとLearner Constraints(LLwLC)を導入し,頂点削除部分グラフの符号化とノイマン固有値制約の適用という2つの新しい部分グラフ抽出手法を提案する。 前者にとって、LLwLCは、効率的な時間複雑性を提供する普遍近似器を確立していると推測する。 後者は、$k$-regular graphsとノード自己同型の間の区別を可能にするリンク表現に焦点を当てている。 当社のアプローチは極めて軽量なアーキテクチャを実現し、広範なトレーニングデータセットの必要性を低減します。 実験により,提案手法は,ベンチマークデータセット間のリンク予測タスクの性能向上を実現し,その実用性を確立し,理論的結果をサポートする。 特に、LLwLCは、最先端と比較して、PubMedとOGBL-Vesselのデータセットから5%と10%のデータしか必要とせず、20倍と10倍のスピードアップを実現している。

関連論文リスト

• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる 本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。 我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
  論文  参考訳（メタデータ） (2024-05-27T17:52:12Z)
• Learning to Reweight for Graph Neural Network [63.978102332612906]
  グラフニューラルネットワーク(GNN)は、グラフタスクに対して有望な結果を示す。 既存のGNNの一般化能力は、テストとトレーニンググラフデータの間に分散シフトが存在する場合に低下する。 本稿では,分布外一般化能力を大幅に向上させる非線形グラフデコリレーション法を提案する。
  論文  参考訳（メタデータ） (2023-12-19T12:25:10Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  不均一グラフニューラルネットワーク(HGNN)は、異種グラフを深層学習するための強力なツールである。 最近のプリ計算ベースのHGNNは、一時間メッセージパッシングを使用して不均一グラフを正規形テンソルに変換する。 我々はRandom Projection Heterogeneous Graph Neural Network (RpHGNN) というハイブリッド計算前HGNNを提案する。
  論文  参考訳（メタデータ） (2023-10-23T01:25:44Z)
• DualHGNN: A Dual Hypergraph Neural Network for Semi-Supervised Node Classification based on Multi-View Learning and Density Awareness [3.698434507617248]
  グラフに基づく半教師付きノード分類は、研究価値と重要性の高い多くのアプリケーションにおいて最先端のアプローチであることが示されている。 本稿では、ハイパーグラフ構造学習とハイパーグラフ表現学習を同時に統合した新しいデュアル接続モデルであるデュアルハイパーグラフニューラルネットワーク(DualHGNN)を提案する。
  論文  参考訳（メタデータ） (2023-06-07T07:40:04Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
  グラフニューラルネットワーク(GNN)は、構造データのモデリングにおいて強力な能力を示している。 GMPTと呼ばれる新しいグラフマッチングベースのGNN事前学習フレームワークを提案する。 提案手法は,完全自己指導型プレトレーニングと粗粒型プレトレーニングに適用できる。
  論文  参考訳（メタデータ） (2022-03-03T09:53:53Z)
• Scalable Graph Neural Networks for Heterogeneous Graphs [12.44278942365518]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データを学習するためのパラメトリックモデルの一般的なクラスである。 最近の研究は、GNNが主に機能をスムースにするためにグラフを使用しており、ベンチマークタスクで競合する結果を示していると主張している。 本研究では、これらの結果が異種グラフに拡張可能かどうかを問うとともに、異なるエンティティ間の複数のタイプの関係を符号化する。
  論文  参考訳（メタデータ） (2020-11-19T06:03:35Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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