論文の概要: Efficient Learning on Large Graphs using a Densifying Regularity Lemma

• arxiv url: http://arxiv.org/abs/2504.18273v1
• Date: Fri, 25 Apr 2025 11:34:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-02 19:15:53.756157
• Title: Efficient Learning on Large Graphs using a Densifying Regularity Lemma
• Title（参考訳）: 正規化補題を用いた大規模グラフの効率的な学習
• Authors: Jonathan Kouchly, Ben Finkelshtein, Michael Bronstein, Ron Levie,
• Abstract要約: 交差する二部体成分の組み合わせに基づいて、大きな有向グラフの低ランク分解を導入する。 グラフ,スパース,あるいは密度を高密度IBGで効率的に近似する方法を示す。
• 参考スコア（独自算出の注目度）: 7.2134828716289645
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning on large graphs presents significant challenges, with traditional Message Passing Neural Networks suffering from computational and memory costs scaling linearly with the number of edges. We introduce the Intersecting Block Graph (IBG), a low-rank factorization of large directed graphs based on combinations of intersecting bipartite components, each consisting of a pair of communities, for source and target nodes. By giving less weight to non-edges, we show how to efficiently approximate any graph, sparse or dense, by a dense IBG. Specifically, we prove a constructive version of the weak regularity lemma, showing that for any chosen accuracy, every graph, regardless of its size or sparsity, can be approximated by a dense IBG whose rank depends only on the accuracy. This dependence of the rank solely on the accuracy, and not on the sparsity level, is in contrast to previous forms of the weak regularity lemma. We present a graph neural network architecture operating on the IBG representation of the graph and demonstrating competitive performance on node classification, spatio-temporal graph analysis, and knowledge graph completion, while having memory and computational complexity linear in the number of nodes rather than edges.
• Abstract（参考訳）: 従来のメッセージパッシングニューラルネットワークは、エッジの数に応じて線形にスケールする計算とメモリコストに悩まされている。 我々は,大方向グラフの低ランク因子化であるIntersecting Block Graph (IBG)を紹介した。 非辺により少ない重みを与えることにより、高密度のIBGによりグラフ、スパース、あるいは密度を効率的に近似する方法を示す。 具体的には、弱正則性補題の構成バージョンを証明し、任意の選択された精度に対して、その大きさや間隔に関わらず、すべてのグラフは、その精度にのみ依存する高密度なIBGによって近似できることを示す。 ランクのこの依存は精度にのみ依存し、空間レベルには依存しないが、以前の弱い正則性補題の形式とは対照的である。 本稿では,グラフのIBG表現で動作するグラフニューラルネットワークアーキテクチャを提案し,ノード分類,時空間グラフ解析,知識グラフ補完において,エッジではなくノード数でメモリと計算の複雑さが線形でありながら競合性能を示す。

関連論文リスト

• Learning on Large Graphs using Intersecting Communities [13.053266613831447]
  MPNNは、各ノードの隣人からのメッセージを集約することで、入力グラフ内の各ノードの表現を反復的に更新する。 MPNNは、あまりスパースではないため、すぐに大きなグラフの禁止になるかもしれない。 本稿では,入力グラフを交差するコミュニティグラフ (ICG) として近似することを提案する。
  論文  参考訳（メタデータ） (2024-05-31T09:26:26Z)
• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる 本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。 我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
  論文  参考訳（メタデータ） (2024-05-27T17:52:12Z)
• Hypergraph-enhanced Dual Semi-supervised Graph Classification [14.339207883093204]
  半教師付きグラフ分類のためのハイパーグラフ拡張DuALフレームワークHEALを提案する。 ノード間の高次関係をよりよく探求するために,複雑なノード依存を適応的に学習するハイパーグラフ構造を設計する。 学習したハイパーグラフに基づいて,ハイパーエッジ間の相互作用を捉える線グラフを導入する。
  論文  参考訳（メタデータ） (2024-05-08T02:44:13Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  局所グラフコントラスト学習(Local-GCL)という,シンプルだが効果的なコントラストモデルを導入する。 その単純さにもかかわらず、Local-GCLは、様々なスケールと特性を持つグラフ上の自己教師付きノード表現学習タスクにおいて、非常に競争力のある性能を達成する。
  論文  参考訳（メタデータ） (2022-12-08T23:36:00Z)
• GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings [51.82434518719011]
  GNNAutoScale(GAS)は、任意のメッセージパスGNNを大規模グラフにスケールするためのフレームワークである。 ガスは、前回のトレーニングの繰り返しから過去の埋め込みを利用して計算グラフのサブツリー全体を掘り起こします。 ガスは大規模グラフ上で最先端のパフォーマンスに達する。
  論文  参考訳（メタデータ） (2021-06-10T09:26:56Z)
• Co-embedding of Nodes and Edges with Graph Neural Networks [13.020745622327894]
  グラフ埋め込みは、高次元および非ユークリッド特徴空間でデータ構造を変換しエンコードする方法である。 CensNetは一般的なグラフ埋め込みフレームワークで、ノードとエッジの両方を潜在機能空間に埋め込む。 提案手法は,4つのグラフ学習課題における最先端のパフォーマンスを達成または一致させる。
  論文  参考訳（メタデータ） (2020-10-25T22:39:31Z)
• Multilevel Graph Matching Networks for Deep Graph Similarity Learning [79.3213351477689]
  グラフ構造オブジェクト間のグラフ類似性を計算するためのマルチレベルグラフマッチングネットワーク(MGMN)フレームワークを提案する。 標準ベンチマークデータセットの欠如を補うため、グラフグラフ分類とグラフグラフ回帰タスクの両方のためのデータセットセットを作成し、収集した。 総合的な実験により、MGMNはグラフグラフ分類とグラフグラフ回帰タスクの両方において、最先端のベースラインモデルより一貫して優れていることが示された。
  論文  参考訳（メタデータ） (2020-07-08T19:48:19Z)
• Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings [53.58077686470096]
  グラフ構造とグラフ埋め込みを協調的かつ反復的に学習するための、エンドツーエンドのグラフ学習フレームワーク、すなわち、IDGL(Iterative Deep Graph Learning)を提案する。 実験の結果,提案したIDGLモデルは,最先端のベースラインを一貫して上回る,あるいは一致させることができることがわかった。
  論文  参考訳（メタデータ） (2020-06-21T19:49:15Z)
• CoSimGNN: Towards Large-scale Graph Similarity Computation [5.17905821006887]
  グラフニューラルネットワーク(GNN)はこのタスクにデータ駆動型ソリューションを提供する。 既存のGNNベースの手法は、それぞれ2つのグラフを埋め込んだり、グラフ全体のクロスグラフインタラクションをデプロイしたりするが、まだ競合する結果が得られない。 このフレームワークは,まず適応的なプーリング操作で大きなグラフを埋め込んで粗くし,最後に類似点を求めるために粗いグラフにきめ細かな相互作用を展開させる。
  論文  参考訳（メタデータ） (2020-05-14T16:33:13Z)

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

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