論文の概要: 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の有効性を実証した。
関連論文リスト
- Interpretable Fine-Tuning for Graph Neural Network Surrogate Models [0.0]
本研究は,グラフニューラルネットワーク(GNN)の解釈可能な微調整戦略を導入する。
最終結果は、予測タスクに本質的に関連付けられている部分グラフに対応する物理空間内の領域を分離する強化された微調整モデルである。
正規化手順により、微調整されたGNNを使用して、予測予測エラーの大多数に対応するグラフノードを推論時に特定することもできる。
論文 参考訳(メタデータ) (2023-11-13T18:37:07Z) - 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) - Crime Prediction with Graph Neural Networks and Multivariate Normal
Distributions [18.640610803366876]
グラフ畳み込みネットワーク(GCN)のフレキシブルな構造を利用して,高分解能領域における疎結合問題に取り組む。
グラフ畳み込みGated Recurrent Units (Graph-ConvGRU) を用いてモデルを構築し,空間的・時間的・カテゴリー的関係を学習する。
モデルが生成性だけでなく,正確性も示しています。
論文 参考訳(メタデータ) (2021-11-29T17:37:01Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。