論文の概要: On the Power of Edge Independent Graph Models
- arxiv url: http://arxiv.org/abs/2111.00048v1
- Date: Fri, 29 Oct 2021 19:12:14 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-02 17:12:05.836205
- Title: On the Power of Edge Independent Graph Models
- Title（参考訳）: エッジ独立グラフモデルの力について
- Authors: Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos, and
Charalampos E. Tsourakakis
- Abstract要約: 本研究では,エッジ独立乱数グラフモデルの限界について検討する。
有界重なり条件の下では、エッジ独立モデルは本質的に、高い三角形やその他の部分グラフ密度を持つグラフを生成する能力に制限されていることを示す。
- 参考スコア（独自算出の注目度）: 22.085932117823738
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Why do many modern neural-network-based graph generative models fail to
reproduce typical real-world network characteristics, such as high triangle
density? In this work we study the limitations of edge independent random graph
models, in which each edge is added to the graph independently with some
probability. Such models include both the classic Erd\"{o}s-R\'{e}nyi and
stochastic block models, as well as modern generative models such as NetGAN,
variational graph autoencoders, and CELL. We prove that subject to a bounded
overlap condition, which ensures that the model does not simply memorize a
single graph, edge independent models are inherently limited in their ability
to generate graphs with high triangle and other subgraph densities. Notably,
such high densities are known to appear in real-world social networks and other
graphs. We complement our negative results with a simple generative model that
balances overlap and accuracy, performing comparably to more complex models in
reconstructing many graph statistics.
- Abstract（参考訳）: 現代のニューラルネットワークベースのグラフ生成モデルは、なぜ高三角密度のような典型的な実世界のネットワーク特性を再現できないのか?
本研究では,各辺を確率的に独立にグラフに追加する,エッジ独立なランダムグラフモデルの限界について検討する。
そのようなモデルには、古典的な erd\"{o}s-r\'{e}nyi と確率ブロックモデルの両方と、netgan、変分グラフオートエンコーダ、セルといった現代的な生成モデルの両方が含まれる。
モデルが単に1つのグラフを記憶しないことを保証する有界重なり条件の下では、エッジ独立モデルは本質的に高い三角形やその他の部分グラフ密度を持つグラフを生成する能力に制限される。
特に、そのような高い密度は、現実世界のソーシャルネットワークや他のグラフに現れることが知られている。
我々は、重なり合いと精度のバランスをとる単純な生成モデルで負の結果を補完し、多くのグラフ統計を再構成する際に、より複雑なモデルに相容れない性能を発揮する。
関連論文リスト
- Advancing Graph Generation through Beta Diffusion [49.49740940068255]
Graph Beta Diffusion (GBD)は、グラフデータの多様な性質を扱うために特別に設計された生成モデルである。
本稿では, 臨界グラフトポロジを安定化させることにより, 生成グラフの現実性を高める変調手法を提案する。
論文 参考訳（メタデータ） (2024-06-13T17:42:57Z) - Almost Surely Asymptotically Constant Graph Neural Networks [7.339728196535312]
出力は定数関数に収束し、これらの分類器が一様に表現できる上限となることを示す。
この強い収束現象は、芸術モデルを含む非常に幅広い種類のGNNに適用される。
我々はこれらの知見を実証的に検証し、収束現象がランダムグラフだけでなく、実世界のグラフにも現れることを観察した。
論文 参考訳（メタデータ） (2024-03-06T17:40:26Z) - On the Role of Edge Dependency in Graph Generative Models [28.203109773986167]
本稿では,グラフ生成モデルのための新しい評価フレームワークを提案する。
我々は、精度とエッジの多様性の両方を保証するために、モデル生成グラフの重複の重要性に焦点をあてる。
我々の単純な解釈可能なモデルが、一般的な生成モデルと競合するベースラインを提供することを示す。
論文 参考訳（メタデータ） (2023-12-06T18:54:27Z) - GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
本稿では,高次元分布をモデル化し,グラフスケルトンと整合した複雑な関係特徴構造を持つデータの新しい例を生成することの問題点を考察する。
提案するモデルは,タスクを2つのフェーズに分割することで,各データポイントのグラフ構造に制約されたデータ特徴を生成する問題に対処する。
第一に、与えられたグラフのノードに関連する機能の分布をモデル化し、第二に、ノードのフィーチャに条件付きでエッジ機能を補完する。
論文 参考訳（メタデータ） (2022-12-01T11:49:07Z) - Model Inversion Attacks against Graph Neural Networks [65.35955643325038]
グラフニューラルネットワーク(GNN)に対するモデル反転攻撃について検討する。
本稿では,プライベートトレーニンググラフデータを推測するためにGraphMIを提案する。
実験の結果,このような防御効果は十分ではないことが示され,プライバシー攻撃に対するより高度な防御が求められている。
論文 参考訳（メタデータ） (2022-09-16T09:13:43Z) - Node Copying: A Random Graph Model for Effective Graph Sampling [35.957719744856696]
本稿では,グラフ上の分布を構成するノードコピーモデルを提案する。
コピーモデルの有用性を3つのタスクで示す。
提案モデルを用いて,グラフトポロジに対する敵攻撃の効果を緩和する。
論文 参考訳（メタデータ） (2022-08-04T04:04:49Z) - Score-based Generative Modeling of Graphs via the System of Stochastic
Differential Equations [57.15855198512551]
本稿では,連続時間フレームワークを用いたグラフのスコアベース生成モデルを提案する。
本手法は, トレーニング分布に近い分子を生成できるが, 化学価数則に違反しないことを示す。
論文 参考訳（メタデータ） (2022-02-05T08:21:04Z) - An Interpretable Graph Generative Model with Heterophily [38.59200985962146]
ヘテロフィリーを捉えるのに十分な表現性を持つ最初のエッジ非依存グラフ生成モデルを提案する。
我々の実験は、様々な重要なアプリケーションタスクに対して、我々のモデルの有効性を実証する。
論文 参考訳（メタデータ） (2021-11-04T17:34:39Z) - A Deep Latent Space Model for Graph Representation Learning [10.914558012458425]
本稿では,従来の潜時変動に基づく生成モデルをディープラーニングフレームワークに組み込むために,有向グラフのための深潜時空間モデル(DLSM)を提案する。
提案モデルは,階層的変動型オートエンコーダアーキテクチャによって階層的に接続されるグラフ畳み込みネットワーク(GCN)エンコーダとデコーダから構成される。
実世界のデータセットにおける実験により,提案モデルがリンク予測とコミュニティ検出の両タスクにおける最先端のパフォーマンスを達成することを示す。
論文 参考訳（メタデータ） (2021-06-22T12:41:19Z) - Auto-decoding Graphs [91.3755431537592]
生成モデルは、潜在コードからグラフを合成することを学ぶ自動デコーダである。
グラフは、おそらく接続パターンを特定するためにトレーニングされた自己アテンションモジュールを使用して合成される。
論文 参考訳（メタデータ） (2020-06-04T14:23:01Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。