論文の概要: Analysis and Approximate Inference of Large and Dense Random Kronecker Graphs

• arxiv url: http://arxiv.org/abs/2306.08489v1
• Date: Wed, 14 Jun 2023 13:09:38 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-16 18:56:25.474360
• Title: Analysis and Approximate Inference of Large and Dense Random Kronecker Graphs
• Title（参考訳）: 大規模・高密度ランダムクロネッカーグラフの解析と近似推定
• Authors: Zhenyu Liao, Yuanqian Xia, Chengmei Niu, Yong Xiao
• Abstract要約: 本稿では,citeleskovec2010kroneckerで提案されたランダムクロネッカーグラフモデルの詳細な解析を行う。 濃密な状況下では、ランダムクロネッカーグラフの隣接行列は信号プラスノイズモデルにほぼ従うことが示される。 本稿では,計算複雑性の低減と(漸近的な)性能保証により,グラフパラメータを近似的に推定するメタアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 5.230929570574604
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Random graph models are playing an increasingly important role in science and industry, and finds their applications in a variety of fields ranging from social and traffic networks, to recommendation systems and molecular genetics. In this paper, we perform an in-depth analysis of the random Kronecker graph model proposed in \cite{leskovec2010kronecker}, when the number of graph vertices $N$ is large. Built upon recent advances in random matrix theory, we show, in the dense regime, that the random Kronecker graph adjacency matrix follows approximately a signal-plus-noise model, with a small-rank (of order at most $\log N$) signal matrix that is linear in the graph parameters and a random noise matrix having a quarter-circle-form singular value distribution. This observation allows us to propose a ``denoise-and-solve'' meta algorithm to approximately infer the graph parameters, with reduced computational complexity and (asymptotic) performance guarantee. Numerical experiments of graph inference and graph classification on both synthetic and realistic graphs are provided to support the advantageous performance of the proposed approach.
• Abstract（参考訳）: ランダムグラフモデルは科学や産業においてますます重要な役割を担っており、社会や交通ネットワーク、レコメンデーションシステムや分子遺伝学など幅広い分野に応用されている。 本稿では,グラフ頂点数が$N$である場合のランダムクロネッカーグラフモデルの詳細な解析を行う。 乱数行列理論の最近の進歩を基にして、密分布において、ランダムクロネッカーグラフの隣接行列は、グラフパラメータに線形な最小ランク(最大$\log n$)信号行列と4/4円の特異値分布を持つランダムノイズ行列を持つ信号プラスノイズモデル(英語版)(signal-plus-noise model)に従うことを示した。 この観測により,計算複雑性の低減と(漸近的な)性能保証により,グラフパラメータを近似的に推定する<denoise-and-solve'メタアルゴリズムを提案することができる。 合成グラフと現実グラフの両方におけるグラフ推定とグラフ分類の数値実験を行い,提案手法の利点を実証した。

関連論文リスト

• Generalization of Geometric Graph Neural Networks [84.01980526069075]
  幾何グラフニューラルネットワーク(GNN)の一般化能力について検討する。 我々は,このGNNの最適経験リスクと最適統計リスクとの一般化ギャップを証明した。 最も重要な観察は、前の結果のようにグラフのサイズに制限されるのではなく、1つの大きなグラフで一般化能力を実現することができることである。
  論文  参考訳（メタデータ） (2024-09-08T18:55:57Z)
• Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
  本研究では,社会科学や生物科学においてユビキタスな小世界ネットワークのランダムグラフモデルについて検討する。 植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $tau$、エッジワイド信号対雑音比$lambda$で特徴づける。
  論文  参考訳（メタデータ） (2024-02-01T03:39:01Z)
• Graph Neural Networks with a Distribution of Parametrized Graphs [27.40566674759208]
  複数のグラフをパラメータ化して生成するために潜在変数を導入する。 予測最大化フレームワークにおいて,ネットワークパラメータの最大推定値を得る。
  論文  参考訳（メタデータ） (2023-10-25T06:38:24Z)
• General Graph Random Features [42.75616308187867]
  重み付き隣接行列の任意の関数の偏りのない推定のためのランダムウォークに基づく新しいアルゴリズムを提案する。 提案アルゴリズムは, ノード数に関して, グラフカーネル評価の厳密な3次スケーリングを克服し, 準四次時間的複雑性を享受する。
  論文  参考訳（メタデータ） (2023-10-07T15:47:31Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Effects of Graph Convolutions in Deep Networks [8.937905773981702]
  多層ネットワークにおけるグラフ畳み込みの効果に関する厳密な理論的理解を示す。 単一のグラフ畳み込みは、多層ネットワークがデータを分類できる手段間の距離のレギュレーションを拡大することを示す。 ネットワーク層間の異なる組み合わせに配置されたグラフ畳み込みの性能に関する理論的および実証的な知見を提供する。
  論文  参考訳（メタデータ） (2022-04-20T08:24:43Z)
• Neighborhood Random Walk Graph Sampling for Regularized Bayesian Graph Convolutional Neural Networks [0.6236890292833384]
  本稿では,近隣ランダムウォークサンプリング(BGCN-NRWS)を用いたベイジアングラフ畳み込みネットワーク(Bayesian Graph Convolutional Network)を提案する。 BGCN-NRWSは、グラフ構造を利用したマルコフ・チェイン・モンテカルロ(MCMC)に基づくグラフサンプリングアルゴリズムを使用し、変分推論層を用いてオーバーフィッティングを低減し、半教師付きノード分類における最先端と比較して一貫して競合する分類結果を得る。
  論文  参考訳（メタデータ） (2021-12-14T20:58:27Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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