論文の概要: Graph Condensation via Eigenbasis Matching
- arxiv url: http://arxiv.org/abs/2310.09202v1
- Date: Fri, 13 Oct 2023 15:48:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-16 12:08:30.640953
- Title: Graph Condensation via Eigenbasis Matching
- Title(参考訳): 固有ベイシスマッチングによるグラフ凝縮
- Authors: Yang Liu, Deyu Bo, Chuan Shi
- Abstract要約: グラフ凝縮は、実際の大きなグラフをはるかに小さな合成グラフで置き換えることを目的としている。
既存のGCメソッドは、一般化が貧弱なため、同じ合成グラフ上で訓練された異なるGNNは明らかに性能差がある。
本稿では、2つの重要なステップを持つGCEMと呼ばれるスペクトルフリーグラフ凝縮に対する固有基底マッチングを提案する。
- 参考スコア(独自算出の注目度): 48.99164820872498
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The increasing amount of graph data places requirements on the efficiency and
scalability of graph neural networks (GNNs), despite their effectiveness in
various graph-related applications. Recently, the emerging graph condensation
(GC) sheds light on reducing the computational cost of GNNs from a data
perspective. It aims to replace the real large graph with a significantly
smaller synthetic graph so that GNNs trained on both graphs exhibit comparable
performance. However, our empirical investigation reveals that existing GC
methods suffer from poor generalization, i.e., different GNNs trained on the
same synthetic graph have obvious performance gaps. What factors hinder the
generalization of GC and how can we mitigate it? To answer this question, we
commence with a detailed analysis and observe that GNNs will inject spectrum
bias into the synthetic graph, resulting in a distribution shift. To tackle
this issue, we propose eigenbasis matching for spectrum-free graph
condensation, named GCEM, which has two key steps: First, GCEM matches the
eigenbasis of the real and synthetic graphs, rather than the graph structure,
which eliminates the spectrum bias of GNNs. Subsequently, GCEM leverages the
spectrum of the real graph and the synthetic eigenbasis to construct the
synthetic graph, thereby preserving the essential structural information. We
theoretically demonstrate that the synthetic graph generated by GCEM maintains
the spectral similarity, i.e., total variation, of the real graph. Extensive
experiments conducted on five graph datasets verify that GCEM not only achieves
state-of-the-art performance over baselines but also significantly narrows the
performance gaps between different GNNs.
- Abstract(参考訳): グラフデータの増加は、様々なグラフ関連アプリケーションでの有効性にもかかわらず、グラフニューラルネットワーク(gnns)の効率とスケーラビリティに要求を課す。
近年,新しいグラフ凝縮法 (GC) は,データの観点からGNNの計算コストの低減に重点を置いている。
これは、実際の大きなグラフをはるかに小さな合成グラフに置き換えることを目的としており、両方のグラフでトレーニングされたGNNは同等のパフォーマンスを示す。
しかし,本研究では,既存のGC手法が一般化に乏しいこと,すなわち,同一合成グラフ上で訓練された異なるGNNが明らかに性能ギャップを有することを明らかにする。
gcの一般化を妨げる要因は何であり、どのように緩和できるのか?
この問いに答えるために、我々は詳細な分析を開始し、GNNが合成グラフにスペクトルバイアスを注入し、分布シフトをもたらすことを観察する。
この問題に対処するために、GCEM は、GNN のスペクトルバイアスを排除したグラフ構造ではなく、実グラフと合成グラフの固有ベイズにマッチする、GCEM と呼ばれる2つの重要なステップを持つスペクトルフリーグラフ凝縮に対する固有ベイズマッチングを提案する。
その後、GCEMは実グラフと合成固有基底のスペクトルを利用して合成グラフを構築し、本質的な構造情報を保存する。
我々は、GCEMによって生成された合成グラフが実グラフのスペクトル類似性、すなわち全変量を維持することを理論的に証明する。
5つのグラフデータセットで実施された大規模な実験により、GCEMはベースライン上での最先端のパフォーマンスを達成するだけでなく、異なるGNN間のパフォーマンスギャップを大幅に狭める。
関連論文リスト
- Scalable Implicit Graphon Learning [25.015678499211404]
本稿では、暗黙的ニューラルネットワーク(INR)とグラフニューラルネットワーク(GNN)を組み合わせて、観測されたグラフからグラフを推定するスケーラブルな手法を提案する。
合成グラフと実世界のグラフでSIGLを評価し,既存の手法より優れ,大規模グラフに効果的にスケール可能であることを示した。
論文 参考訳(メタデータ) (2024-10-22T22:44:24Z) - Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる
本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。
我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
論文 参考訳(メタデータ) (2024-05-27T17:52:12Z) - A Spectral Analysis of Graph Neural Networks on Dense and Sparse Graphs [13.954735096637298]
そこで我々は,グラフスペクトルの空間分布がグラフスペクトルに与える影響を解析し,グラフニューラルネットワーク(GNN)の高密度グラフとスパースグラフのノード分類における性能について検討した。
GNNはスパースグラフのスペクトル法よりも優れており、これらの結果を合成グラフと実グラフの両方で数値例で示すことができる。
論文 参考訳(メタデータ) (2022-11-06T22:38:13Z) - MentorGNN: Deriving Curriculum for Pre-Training GNNs [61.97574489259085]
本稿では,グラフ間のGNNの事前学習プロセスの監視を目的とした,MentorGNNというエンドツーエンドモデルを提案する。
我々は、事前学習したGNNの一般化誤差に自然かつ解釈可能な上限を導出することにより、関係データ(グラフ)に対するドメイン適応の問題に新たな光を当てた。
論文 参考訳(メタデータ) (2022-08-21T15:12:08Z) - Evaluating Explainability for Graph Neural Networks [21.339111121529815]
本稿では,様々なベンチマークデータセットを生成することができる合成グラフデータ生成器ShapeGGenを紹介する。
ShapeGGenといくつかの実世界のグラフデータセットを、オープンソースのグラフ説明可能性ライブラリであるGraphXAIに含めています。
論文 参考訳(メタデータ) (2022-08-19T13:43:52Z) - Graph Generative Model for Benchmarking Graph Neural Networks [73.11514658000547]
本稿では,プライバシ制御により実世界のグラフの分布を学習し,再現する新しいグラフ生成モデルを提案する。
我々のモデルは、GNNモデルのベンチマークに効果的に使用できる大規模な実世界のグラフの、プライバシ制御された合成代用をうまく生成することができる。
論文 参考訳(メタデータ) (2022-07-10T06:42:02Z) - Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
本稿では,元のグラフを表す小さなグラフの作成に焦点をあてる。
我々は、元のグラフを受容体の分布とみなし、受容体が同様の分布を持つ小さなグラフを合成することを目的としている。
論文 参考訳(メタデータ) (2022-06-28T02:10:05Z) - Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
本稿では、観測されたグラフと潜伏グラフのグラフ畳み込み関係を提案し、グラフ学習タスクをネットワーク逆(デコンボリューション)問題として定式化する。
固有分解に基づくスペクトル法の代わりに、近似勾配反復をアンロール・トランケートして、グラフデコンボリューションネットワーク(GDN)と呼ばれるパラメータ化ニューラルネットワークアーキテクチャに到達させる。
GDNは、教師付き方式でグラフの分布を学習し、損失関数を適応させることでリンク予測やエッジウェイト回帰タスクを実行し、本質的に帰納的である。
論文 参考訳(メタデータ) (2022-05-19T14:08:15Z) - Adaptive Kernel Graph Neural Network [21.863238974404474]
グラフニューラルネットワーク(GNN)は,グラフ構造化データの表現学習において大きな成功を収めている。
本稿では,AKGNN(Adaptive Kernel Graph Neural Network)という新しいフレームワークを提案する。
AKGNNは、最初の試みで最適なグラフカーネルに統一的に適応することを学ぶ。
評価されたベンチマークデータセットで実験を行い、提案したAKGNNの優れた性能を示す有望な結果を得た。
論文 参考訳(メタデータ) (2021-12-08T20:23:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。