論文の概要: Exploring Edge Probability Graph Models Beyond Edge Independency: Concepts, Analyses, and Algorithms

• arxiv url: http://arxiv.org/abs/2405.16726v2
• Date: Tue, 22 Oct 2024 07:05:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-23 14:24:40.072845
• 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の一般的なクラス(例えば、ErdHos-R'enyi や Kronecker など)はエッジ確率を出力する。 エッジ独立性では、理論上RGMは高いサブグラフ密度と高い出力変動を同時に生成することはできない。
• 参考スコア（独自算出の注目度）: 26.550266795403022
• License:
• Abstract: Desirable random graph models (RGMs) should (i) generate realistic structures such as high clustering (i.e., high subgraph densities), (ii) generate variable (i.e., not overly similar) graphs, and (iii) remain tractable to compute and control graph statistics. A common class of RGMs (e.g., Erd\H{o}s-R'{e}nyi and stochastic Kronecker) outputs edge probabilities, and we need to realize (i.e., sample from) the edge probabilities to generate graphs. Typically, each edge's existence is assumed to be determined independently for simplicity and tractability. However, with edge independency, RGMs theoretically cannot produce high subgraph densities and high output variability simultaneously. In this work, we explore realization beyond edge independence that can produce more realistic structures while maintaining high traceability and variability. Theoretically, we propose an edge-dependent realization framework called binding that provably preserves output variability, and derive closed-form tractability results on subgraph (e.g., triangle) densities in generated graphs. Practically, we propose algorithms for graph generation with binding and parameter fitting of binding. Our empirical results demonstrate that binding exhibits high tractability and generates realistic graphs with high clustering, significantly improving upon existing RGMs assuming edge independency.
• Abstract（参考訳）: 好ましくない乱数グラフモデル(RGM) 一 高クラスタリング(高サブグラフ密度)のような現実的な構造を生成すること。 (ii)変数(すなわち、過剰に類似しない)グラフを生成し、 (iii)グラフ統計の計算と制御は引き続き容易である。 RGMの共通類(例: Erd\H{o}s-R'{e}nyi と確率的クロネッカー)はエッジ確率を出力し、グラフを生成するためにエッジ確率(すなわち、サンプル)を実現する必要がある。 通常、それぞれのエッジの存在は、単純さとトラクタビリティのために独立に決定される。 しかし、エッジ独立性では、理論上、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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。