論文の概要: TinyGraph: Joint Feature and Node Condensation for Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2407.08064v1
- Date: Wed, 10 Jul 2024 21:54:12 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-12 21:19:34.333618
- Title: TinyGraph: Joint Feature and Node Condensation for Graph Neural Networks
- Title(参考訳): TinyGraph: グラフニューラルネットワークのジョイント機能とノード凝縮
- Authors: Yezi Liu, Yanning Shen,
- Abstract要約: 大規模グラフ上でのグラフニューラルネットワーク(GNN)のトレーニングは、高い計算コストのために困難である。
既存のグラフ凝縮の研究は、グラフ内のノード数を減少させることによってのみこの問題に取り組む。
グラフで特徴とノードを同時に結集する新しいフレームワークであるTinyGraphを提案する。
- 参考スコア(独自算出の注目度): 14.8325651280105
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Training graph neural networks (GNNs) on large-scale graphs can be challenging due to the high computational expense caused by the massive number of nodes and high-dimensional nodal features. Existing graph condensation studies tackle this problem only by reducing the number of nodes in the graph. However, the resulting condensed graph data can still be cumbersome. Specifically, although the nodes of the Citeseer dataset are reduced to 0.9% (30 nodes) in training, the number of features is 3,703, severely exceeding the training sample magnitude. Faced with this challenge, we study the problem of joint condensation for both features and nodes in large-scale graphs. This task is challenging mainly due to 1) the intertwined nature of the node features and the graph structure calls for the feature condensation solver to be structure-aware; and 2) the difficulty of keeping useful information in the condensed graph. To address these challenges, we propose a novel framework TinyGraph, to condense features and nodes simultaneously in graphs. Specifically, we cast the problem as matching the gradients of GNN weights trained on the condensed graph and the gradients obtained from training over the original graph, where the feature condensation is achieved by a trainable function. The condensed graph obtained by minimizing the matching loss along the training trajectory can henceforth retain critical information in the original graph. Extensive experiments were carried out to demonstrate the effectiveness of the proposed TinyGraph. For example, a GNN trained with TinyGraph retains 98.5% and 97.5% of the original test accuracy on the Cora and Citeseer datasets, respectively, while significantly reducing the number of nodes by 97.4% and 98.2%, and the number of features by 90.0% on both datasets.
- Abstract(参考訳): 大規模グラフ上でのグラフニューラルネットワーク(GNN)のトレーニングは、大量のノードと高次元のノイズ特徴に起因する計算コストが高いため、難しい場合がある。
既存のグラフ凝縮の研究は、グラフ内のノード数を減少させることによってのみこの問題に取り組む。
しかし、結果として得られる凝縮グラフデータはいまだに困難である。
具体的には、Citeseerデータセットのノードはトレーニング時に0.9%(30ノード)に削減されるが、特徴の数は3,703で、トレーニングサンプルの規模を大きく上回っている。
この課題に直面して,大規模グラフにおける特徴とノードの合同凝縮の問題について検討する。
この仕事は、主に原因で難しい。
1) ノードの特徴とグラフ構造が相互に絡み合う性質は,特徴凝縮解器に構造を認識させるよう要求する。
2) 凝縮グラフに有用な情報を保持することの難しさ。
これらの課題に対処するため,我々は新しいフレームワークTinyGraphを提案し,機能とノードを同時にグラフに格納する。
具体的には、縮合グラフ上で訓練されたGNN重みの勾配と、トレーニング可能な関数によって特徴凝縮が達成される原グラフ上でのトレーニングから得られた勾配とを一致させた。
トレーニング軌跡に沿った整合損失を最小化して得られる凝縮グラフは、したがって、元のグラフに重要な情報を保持することができる。
提案したTinyGraphの有効性を示す大規模な実験を行った。
例えば、TinyGraphでトレーニングされたGNNは、CoraとCiteseerのデータセットでそれぞれ元のテスト精度の98.5%と97.5%を保持し、ノード数を97.4%、98.2%、両方のデータセットで90.0%削減している。
関連論文リスト
- Graph-Skeleton: ~1% Nodes are Sufficient to Represent Billion-Scale
Graph [11.661431088477329]
本稿では,背景ノードを適切に取得する新しいGraph-Skeleton1モデルを提案する。
特に、0.24億のノードを持つMAG240Mデータセットでは、生成したスケルトングラフは、元のグラフの1.8%のノードしか含んでおらず、非常に同等のパフォーマンスを実現しています。
論文 参考訳(メタデータ) (2024-02-14T20:33:11Z) - Random Geometric Graph Alignment with Graph Neural Networks [8.08963638000146]
グラフニューラルネットワークは、2つのグラフの頂点間の未知の1対1マッピングを復元可能であることを示す。
また、ノイズレベルの条件が対数的要因に厳密であることも証明した。
ノイズレベルが少なくとも一定である場合、この直接マッチングは完全なリカバリが得られず、グラフニューラルネットワークは、グラフの大きさのパワーと同じくらいの速さで成長するノイズレベルを許容できることを示した。
論文 参考訳(メタデータ) (2024-02-12T00:18:25Z) - Graph Condensation for Inductive Node Representation Learning [59.76374128436873]
マッピング対応グラフ凝縮法(MCond)を提案する。
MCondは、帰納的表現学習のための合成グラフに新しいノードを統合する。
Redditデータセットでは、最大121.5倍の推論スピードアップと55.9倍のストレージ要求の削減を実現している。
論文 参考訳(メタデータ) (2023-07-29T12:11:14Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳(メタデータ) (2023-06-14T09:21:15Z) - Structure-free Graph Condensation: From Large-scale Graphs to Condensed
Graph-free Data [91.27527985415007]
既存のグラフ凝縮法は、凝縮グラフ内のノードと構造の合同最適化に依存している。
我々は、大規模グラフを小さなグラフノード集合に蒸留する、SFGCと呼ばれる新しい構造自由グラフ凝縮パラダイムを提唱する。
論文 参考訳(メタデータ) (2023-06-05T07:53:52Z) - Gradient scarcity with Bilevel Optimization for Graph Learning [0.0]
勾配不足は、ノードのサブセットの損失を最小限にすることでグラフを学習する際に発生する。
我々は、この現象の正確な数学的特徴を与え、双レベル最適化にも現れることを証明した。
この問題を緩和するために,グラフ・ツー・グラフモデル(G2G)を用いた潜時グラフ学習,グラフに先行構造を課すグラフ正規化,あるいは直径を縮小した元のグラフよりも大きなグラフを最適化することを提案する。
論文 参考訳(メタデータ) (2023-03-24T12:37:43Z) - Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
本稿では、観測されたグラフと潜伏グラフのグラフ畳み込み関係を提案し、グラフ学習タスクをネットワーク逆(デコンボリューション)問題として定式化する。
固有分解に基づくスペクトル法の代わりに、近似勾配反復をアンロール・トランケートして、グラフデコンボリューションネットワーク(GDN)と呼ばれるパラメータ化ニューラルネットワークアーキテクチャに到達させる。
GDNは、教師付き方式でグラフの分布を学習し、損失関数を適応させることでリンク予測やエッジウェイト回帰タスクを実行し、本質的に帰納的である。
論文 参考訳(メタデータ) (2022-05-19T14:08:15Z) - Graph Condensation for Graph Neural Networks [34.4899280207043]
グラフニューラルネットワーク(GNN)におけるグラフ凝縮の問題点について検討する。
我々は、この大きなオリジナルグラフを、小さく、合成され、高度にインフォームティブなグラフに凝縮することを目指している。
私たちはオリジナルのテスト精度をRedditで95.3%、Flickrで99.8%、Citeseerで99.0%と近似することができる。
論文 参考訳(メタデータ) (2021-10-14T17:42:14Z) - Increase and Conquer: Training Graph Neural Networks on Growing Graphs [116.03137405192356]
本稿では,このグラフからBernoulliをサンプリングしたグラフ上でGNNをトレーニングすることで,WNN(Graphon Neural Network)を学習する問題を考察する。
これらの結果から着想を得た大規模グラフ上でGNNを学習するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-06-07T15:05:59Z) - Line Graph Neural Networks for Link Prediction [71.00689542259052]
実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。
このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。
本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。
特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
論文 参考訳(メタデータ) (2020-10-20T05:54:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。