論文の概要: Tackling Provably Hard Representative Selection via Graph Neural
Networks
- arxiv url: http://arxiv.org/abs/2205.10403v2
- Date: Wed, 19 Jul 2023 14:23:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-20 18:33:59.618301
- Title: Tackling Provably Hard Representative Selection via Graph Neural
Networks
- Title（参考訳）: グラフニューラルネットワークによるおそらくハードな代表選択の処理
- Authors: Mehran Kazemi, Anton Tsitsulin, Hossein Esfandiari, MohammadHossein
Bateni, Deepak Ramachandran, Bryan Perozzi, Vahab Mirrokni
- Abstract要約: 代表選択(Representive Selection, RS)は、データセットの代表であるデータセットから、例の小さなサブセットを見つける問題である。
本稿では,グラフのRSについて検討し,選択した代表に対して学習したモデルの精度を最適化する代表ノードの探索に焦点をあてる。
グラフニューラルネットワークに基づく表現学習に基づくRSモデルであるRS-GNNを開発した。
- 参考スコア（独自算出の注目度）: 22.87686689456669
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Representative Selection (RS) is the problem of finding a small subset of
exemplars from a dataset that is representative of the dataset. In this paper,
we study RS for attributed graphs, and focus on finding representative nodes
that optimize the accuracy of a model trained on the selected representatives.
Theoretically, we establish a new hardness result forRS (in the absence of a
graph structure) by proving that a particular, highly practical variant of it
(RS for Learning) is hard to approximate in polynomial time within any
reasonable factor, which implies a significant potential gap between the
optimum solution of widely-used surrogate functions and the actual accuracy of
the model. We then study the setting where a (homophilous) graph structure is
available, or can be constructed, between the data points.We show that with an
appropriate modeling approach, the presence of such a structure can turn a hard
RS (for learning) problem into one that can be effectively solved. To this end,
we develop RS-GNN, a representation learning-based RS model based on Graph
Neural Networks. Empirically, we demonstrate the effectiveness of RS-GNN on
problems with predefined graph structures as well as problems with graphs
induced from node feature similarities, by showing that RS-GNN achieves
significant improvements over established baselines on a suite of eight
benchmarks.
- Abstract（参考訳）: 代表選択(Representive Selection, RS)は、データセットの代表であるデータセットから、例の小さなサブセットを見つける問題である。
本稿では,帰属グラフのrsを調査し,選択した代表者に対してトレーニングされたモデルの精度を最適化する代表ノードの探索に焦点をあてる。
理論的には、(グラフ構造が存在しない場合)新しい硬さ結果のforrsを確立させるには、任意の妥当な係数内で多項式時間で近似することが困難であり、これは広く使われているサーロゲート関数の最適解とモデルの実際の精度との間に有意なギャップがあることを意味する。
次に,データポイント間のグラフ構造が利用可能である,あるいは構築可能な設定について検討し,適切なモデリング手法により,そのような構造が存在することにより,ハードRS(学習用)問題を効果的に解けるものにすることができることを示す。
そこで我々は,グラフニューラルネットワークに基づく表現学習型rsモデルrs-gnnを開発した。
実験的に, RS-GNNは, 8つのベンチマークで確立されたベースラインよりも大幅に改善されていることを示すことにより, 事前に定義されたグラフ構造とノード特徴の類似性に起因するグラフ問題に対するRS-GNNの有効性を実証した。
関連論文リスト
- Revisiting Graph Neural Networks on Graph-level Tasks: Comprehensive Experiments, Analysis, and Improvements [54.006506479865344]
グラフレベルグラフニューラルネットワーク(GNN)のための統一評価フレームワークを提案する。
このフレームワークは、さまざまなデータセットにわたるGNNを評価するための標準化された設定を提供する。
また,表現性の向上と一般化機能を備えた新しいGNNモデルを提案する。
論文 参考訳（メタデータ） (2025-01-01T08:48:53Z) - Graph Structure Refinement with Energy-based Contrastive Learning [56.957793274727514]
グラフの構造と表現を学習するための生成訓練と識別訓練のジョイントに基づく教師なし手法を提案する。
本稿では,ECL-GSR(Energy-based Contrastive Learning)によるグラフ構造再構成(GSR)フレームワークを提案する。
ECL-GSRは、主要なベースラインに対するサンプルやメモリの少ない高速なトレーニングを実現し、下流タスクの単純さと効率性を強調している。
論文 参考訳（メタデータ） (2024-12-20T04:05:09Z) - Graph Reasoning Networks [9.18586425686959]
Graph Reasoning Networks (GRNs) は、グラフ表現と学習したグラフ表現の長所と、微分可能満足度解法に基づく推論モジュールを組み合わせるための新しいアプローチである。
実世界のデータセットの結果は、GNNに匹敵するパフォーマンスを示している。
合成データセットの実験は、新しく提案された手法の可能性を示している。
論文 参考訳（メタデータ） (2024-07-08T10:53:49Z) - A GAN Approach for Node Embedding in Heterogeneous Graphs Using Subgraph Sampling [33.50085646298074]
本稿では,グラフニューラルネットワーク (GNN) とGAN (Generative Adrial Network) を組み合わせた新しいフレームワークを提案する。
このフレームワークには高度なエッジ生成と選択モジュールが含まれており、合成ノードとエッジを同時に生成することができる。
論文 参考訳（メタデータ） (2023-12-11T16:52:20Z) - A Comprehensive Study on Large-Scale Graph Training: Benchmarking and
Rethinking [124.21408098724551]
グラフニューラルネットワーク(GNN)の大規模グラフトレーニングは、非常に難しい問題である
本稿では,既存の問題に対処するため,EnGCNという新たなアンサンブルトレーニング手法を提案する。
提案手法は,大規模データセット上でのSOTA(State-of-the-art)の性能向上を実現している。
論文 参考訳（メタデータ） (2022-10-14T03:43:05Z) - Relation Embedding based Graph Neural Networks for Handling
Heterogeneous Graph [58.99478502486377]
我々は、同種GNNが不均一グラフを扱うのに十分な能力を持つように、シンプルで効率的なフレームワークを提案する。
具体的には、エッジ型関係と自己ループ接続の重要性を埋め込むために、関係1つのパラメータのみを使用する関係埋め込みベースのグラフニューラルネットワーク(RE-GNN)を提案する。
論文 参考訳（メタデータ） (2022-09-23T05:24:18Z) - Graph-Time Convolutional Neural Networks: Architecture and Theoretical
Analysis [12.995632804090198]
グラフ時間畳み込みニューラルネットワーク(GTCNN)を学習支援の原則アーキテクチャとして導入する。
このアプローチはどんな種類のプロダクトグラフでも機能し、パラメトリックグラフを導入して、プロダクトの時間的結合も学べます。
GTCNNが最先端のソリューションと好意的に比較できることを示す。
論文 参考訳（メタデータ） (2022-06-30T10:20:52Z) - Scalable Graph Neural Networks for Heterogeneous Graphs [12.44278942365518]
グラフニューラルネットワーク(GNN)は、グラフ構造化データを学習するためのパラメトリックモデルの一般的なクラスである。
最近の研究は、GNNが主に機能をスムースにするためにグラフを使用しており、ベンチマークタスクで競合する結果を示していると主張している。
本研究では、これらの結果が異種グラフに拡張可能かどうかを問うとともに、異なるエンティティ間の複数のタイプの関係を符号化する。
論文 参考訳（メタデータ） (2020-11-19T06:03:35Z) - Stochastic Graph Recurrent Neural Network [6.656993023468793]
本稿では,ノード属性とトポロジの進化を同時に捉えるために潜時変数を適用した新しいニューラルアーキテクチャであるSGRNNを提案する。
具体的には、決定論的状態は、相互干渉を抑制する反復過程において状態から分離される。
実世界のデータセットを用いた実験により,提案モデルの有効性が示された。
論文 参考訳（メタデータ） (2020-09-01T16:14:30Z) - Binarized Graph Neural Network [65.20589262811677]
我々は二項化グラフニューラルネットワークを開発し、二項化ネットワークパラメータを用いてノードのバイナリ表現を学習する。
提案手法は既存のGNNベースの埋め込み手法にシームレスに統合できる。
実験により、提案された二項化グラフニューラルネットワーク、すなわちBGNは、時間と空間の両方の観点から、桁違いに効率的であることが示されている。
論文 参考訳（メタデータ） (2020-04-19T09:43:14Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。