論文の概要: Tackling Provably Hard Representative Selection via Graph Neural
Networks
- arxiv url: http://arxiv.org/abs/2205.10403v1
- Date: Fri, 20 May 2022 18:44:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-24 19:51:23.511617
- Title: Tackling Provably Hard Representative Selection via Graph Neural
Networks
- Title（参考訳）: グラフニューラルネットワークによるおそらくハードな代表選択の処理
- Authors: Seyed Mehran Kazemi, Anton Tsitsulin, Hossein Esfandiari,
MohammadHossein Bateni, Deepak Ramachandran, Bryan Perozzi, Vahab Mirrokni
- Abstract要約: グラフニューラルネットワークに基づく表現学習に基づくRSモデルであるRS-GNNを開発した。
RS-GNNは、サロゲート関数を最適化する確立されたベースラインよりも大幅に改善されていることを示す。
- 参考スコア（独自算出の注目度）: 25.6874928494925
- 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 an unlabeled dataset, and has numerous applications in
summarization, active learning, data compression and many other domains. In
this paper, we focus on finding representatives that optimize the accuracy of a
model trained on the selected representatives. We study RS for data represented
as attributed graphs. 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 that
optimize surrogate functions. Theoretically, we establish a new hardness result
for RS by proving that RS is hard to approximate in polynomial time within any
reasonable factor, which implies a significant gap between the optimum solution
of widely-used surrogate functions and the actual accuracy of the model, and
provides justification for the superiority of representation learning-based
approaches such as RS-GNN over surrogate functions.
- Abstract（参考訳）: 代表選択(rs)は、ラベルのないデータセットから例題の小さなサブセットを見つける問題であり、要約、アクティブラーニング、データ圧縮、その他多くの領域で多くの応用がある。
本稿では,選択した代表者に対して学習したモデルの精度を最適化する代表者を見つけることに焦点を当てる。
属性グラフとして表されるデータのRSについて検討する。
グラフニューラルネットワークに基づく表現学習型rsモデルrs-gnnを開発した。
実験により,rs-gnn がサーロゲート関数を最適化する確立されたベースラインよりも大幅に改善できることを示し,既定のグラフ構造問題やノード特徴類似性に起因するグラフ問題に対する rs-gnn の有効性を実証した。
理論的には、RSが任意の妥当な係数内で多項式時間内で近似することが困難であることを証明することによって、RSの新たな硬度結果を確立する。これは、広く使われている代用関数の最適解とモデルの実際の精度との間に大きなギャップを生じさせ、代用関数に対するRS-GNNのような表現学習に基づくアプローチの優位性に対する正当化を与える。
関連論文リスト
- 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) - Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
グラフ構造化データに対する半教師付き学習(SSL)は、多くのネットワークサイエンスアプリケーションに現れる。
グラフ上の学習を効率的に管理するために,近年,グラフニューラルネットワーク(GNN)の変種が開発されている。
実際に成功したにも拘わらず、既存の手法のほとんどは、不確実な結節属性を持つグラフを扱うことができない。
ノイズ測定によって得られたデータに関連する分布の不確実性によっても問題が発生する。
分散ロバストな学習フレームワークを開発し,摂動に対する定量的ロバスト性を示すモデルを訓練する。
論文 参考訳（メタデータ） (2021-10-20T14:23:54Z) - Scalable Graph Neural Networks for Heterogeneous Graphs [12.44278942365518]
グラフニューラルネットワーク(GNN)は、グラフ構造化データを学習するためのパラメトリックモデルの一般的なクラスである。
最近の研究は、GNNが主に機能をスムースにするためにグラフを使用しており、ベンチマークタスクで競合する結果を示していると主張している。
本研究では、これらの結果が異種グラフに拡張可能かどうかを問うとともに、異なるエンティティ間の複数のタイプの関係を符号化する。
論文 参考訳（メタデータ） (2020-11-19T06:03:35Z) - Discriminability of Single-Layer Graph Neural Networks [172.5042368548269]
グラフニューラルネットワーク(GNN)は、幅広い問題について有望な性能を示した。
本稿では, 識別可能性の特性に着目し, 安定グラフフィルタバンクへのポイントワイド非線形性の適用により, 高固有値コンテンツに対する識別能力が向上する条件を確立する。
論文 参考訳（メタデータ） (2020-10-17T18:52:34Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。