論文の概要: Exploring Edge Probability Graph Models Beyond Edge Independency: Concepts, Analyses, and Algorithms
- arxiv url: http://arxiv.org/abs/2405.16726v1
- Date: Sun, 26 May 2024 23:48:30 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-28 19:35:41.713768
- Title: Exploring Edge Probability Graph Models Beyond Edge Independency: Concepts, Analyses, and Algorithms
- Title（参考訳）: エッジ依存性を超えたエッジ確率グラフモデル:概念、分析、アルゴリズム
- Authors: Fanchen Bu, Ruochen Yang, Paul Bogdan, Kijung Shin,
- Abstract要約: ランダムグラフモデル(RGM)は、グラフ統計を計算し制御できるように、抽出可能でなければならない。
エッジ独立性では、RGMは入力グラフを「複製」しない限り、理論的には高いサブグラフ密度を生成できない。
本稿では,バインディングを用いたグラフ生成アルゴリズムを提案し,高いクラスタリングによる現実的なグラフを生成する。
- 参考スコア（独自算出の注目度）: 26.550266795403022
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Desirable random graph models (RGMs) should (i) be tractable so that we can compute and control graph statistics, and (ii) generate realistic structures such as high clustering (i.e., high subgraph densities). A popular category of RGMs (e.g., Erdos-Renyi and stochastic Kronecker) outputs edge probabilities, and we need to realize (i.e., sample from) the edge probabilities to generate graphs. Typically, each edge (in)existence is assumed to be determined independently. However, with edge independency, RGMs theoretically cannot produce high subgraph densities unless they "replicate" input graphs. In this work, we explore realization beyond edge independence that can produce more realistic structures while ensuring high tractability. Specifically, we propose edge-dependent realization schemes called binding and derive closed-form tractability results on subgraph (e.g., triangle) densities in graphs generated with binding. We propose algorithms for graph generation with binding and parameter fitting of binding. We empirically validate that binding exhibits high tractability and generates realistic graphs with high clustering, significantly improving upon existing RGMs assuming edge independency.
- Abstract（参考訳）: 好ましくない乱数グラフモデル(RGM)
(i)グラフ統計を計算・制御できるようにトラクタブルで、
(II)ハイクラスタリング(ハイサブグラフ密度)のような現実的な構造を生成する。
RGM (例: Erdos-Renyi and stochastic Kronecker) の一般的なカテゴリは、エッジ確率を出力し、グラフを生成するためのエッジ確率(すなわち、サンプル)を実現する必要がある。
通常、それぞれのエッジ(存在)は独立に決定される。
しかし、エッジ独立性では、RGMは入力グラフを「複製」しない限り、理論的には高いサブグラフ密度を生成できない。
本研究では,高いトラクタビリティを確保しつつ,より現実的な構造を創出できるエッジ独立以外の実現について検討する。
具体的には、結合によって生成されたグラフにおける部分グラフ(例えば三角形)密度に対して、結合と閉形式トラクタビリティ結果の導出というエッジ依存的な実現スキームを提案する。
本稿では,バインディングとパラメータフィッティングを用いたグラフ生成アルゴリズムを提案する。
我々は、結合が高いトラクタビリティを示し、高いクラスタリングを持つリアルグラフを生成することを実証的に検証し、エッジ依存性を仮定する既存のRGMを大幅に改善する。
関連論文リスト
- Gradient-Based Spectral Embeddings of Random Dot Product Graphs [7.612218105739107]
本稿では,RDPG (Random Dot Product Graph) の組込み問題の解法について述べる。
そこで我々は, 結果の多様体に対して, 実現可能な新しい最適化手法を開発した。
当社のオープンソースアルゴリズムの実装はスケーラブルで、エッジデータに欠ける堅牢さと異なり、ストリーミンググラフからゆっくりと、潜伏した位置を追跡することができます。
論文 参考訳（メタデータ） (2023-07-25T21:09:55Z) - HiGen: Hierarchical Graph Generative Networks [2.3931689873603603]
ほとんどの実世界のグラフは階層構造を示しており、しばしば既存のグラフ生成法で見過ごされる。
本稿では,グラフの階層的な性質を捉え,グラフのサブ構造を粗い方法で連続的に生成するグラフ生成ネットワークを提案する。
このモジュラーアプローチは、大規模で複雑なグラフに対してスケーラブルなグラフ生成を可能にする。
論文 参考訳（メタデータ） (2023-05-30T18:04:12Z) - Graph Generation with Diffusion Mixture [57.78958552860948]
グラフの生成は、非ユークリッド構造の複雑な性質を理解する必要がある実世界のタスクにとって大きな課題である。
本稿では,拡散過程の最終グラフ構造を明示的に学習することにより,グラフのトポロジーをモデル化する生成フレームワークを提案する。
論文 参考訳（メタデータ） (2023-02-07T17:07:46Z) - Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF)
我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。
我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
論文 参考訳（メタデータ） (2022-05-28T15:37:03Z) - A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
本稿では,AGE という逆グラフ埋め込みのための頑健なフレームワークを提案する。
AGEは、暗黙の分布から強化された負のサンプルとして偽の隣接ノードを生成する。
本フレームワークでは,3種類のグラフデータを扱う3つのモデルを提案する。
論文 参考訳（メタデータ） (2021-05-22T07:05:48Z) - Learning non-Gaussian graphical models via Hessian scores and triangular
transport [6.308539010172309]
連続分布と非ガウス分布のマルコフ構造を学習するアルゴリズムを提案する。
このアルゴリズムは三角トランスポートマップによって誘導される決定論的結合を用いて密度を推定し、グラフのスパース性を明らかにするために地図内のスパース構造を反復的に活用する。
論文 参考訳（メタデータ） (2021-01-08T16:42:42Z) - Factorizable Graph Convolutional Networks [90.59836684458905]
本稿では,グラフに符号化された相互に絡み合った関係を明示的に解消する新しいグラフ畳み込みネットワーク(GCN)を提案する。
FactorGCNは単純なグラフを入力として取り、それをいくつかの分解グラフに分解する。
提案したFacterGCNは,合成および実世界のデータセットに対して質的かつ定量的に評価する。
論文 参考訳（メタデータ） (2020-10-12T03:01:40Z) - Unsupervised Graph Embedding via Adaptive Graph Learning [85.28555417981063]
グラフオートエンコーダ(GAE)は、グラフ埋め込みのための表現学習において強力なツールである。
本稿では,2つの新しい教師なしグラフ埋め込み法,適応グラフ学習(BAGE)による教師なしグラフ埋め込み,変分適応グラフ学習(VBAGE)による教師なしグラフ埋め込みを提案する。
いくつかのデータセットに関する実験的研究により、我々の手法がノードクラスタリング、ノード分類、グラフ可視化タスクにおいて、ベースラインよりも優れていることが実証された。
論文 参考訳（メタデータ） (2020-03-10T02:33:14Z) - Residual Correlation in Graph Neural Network Regression [39.54530450932135]
我々は条件付き独立仮定が予測力を著しく制限していることを示します。
この問題を解釈可能かつ効率的なフレームワークで解決する。
我々のフレームワークは、競合するベースラインよりもかなり高い精度を実現している。
論文 参考訳（メタデータ） (2020-02-19T16:32:54Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。