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

• arxiv url: http://arxiv.org/abs/2306.08489v2
• Date: Mon, 5 Feb 2024 11:06:07 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-07 06:03:47.555789
• Title: Analysis and Approximate Inference of Large Random Kronecker Graphs
• Title（参考訳）: 大規模ランダムクロネッカーグラフの解析と近似推定
• Authors: Zhenyu Liao, Yuanqian Xia, Chengmei Niu, Yong Xiao
• Abstract要約: 大規模なランダムクロネッカーグラフの隣接性は分解可能であることを示す。 本稿では,鍵グラフパラメータを推論するデノワーズ・アンド・ソルブの手法を提案する。
• 参考スコア（独自算出の注目度）: 4.417282202068703
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Random graph models are playing an increasingly important role in various fields ranging from social networks, telecommunication systems, to physiologic and biological networks. Within this landscape, the random Kronecker graph model, emerges as a prominent framework for scrutinizing intricate real-world networks. In this paper, we investigate large random Kronecker graphs, i.e., the number of graph vertices $N$ is large. Built upon recent advances in random matrix theory (RMT) and high-dimensional statistics, we prove that the adjacency of a large random Kronecker graph can be decomposed, in a spectral norm sense, into two parts: a small-rank (of rank $O(\log N)$) signal matrix that is linear in the graph parameters and a zero-mean random noise matrix. Based on this result, we propose a ``denoise-and-solve'' approach to infer the key graph parameters, with significantly reduced computational complexity. Experiments on both graph inference and classification are presented to evaluate the our proposed method. In both tasks, the proposed approach yields comparable or advantageous performance, than widely-used graph inference (e.g., KronFit) and graph neural net baselines, at a time cost that scales linearly as the graph size $N$.
• Abstract（参考訳）: ランダムグラフモデルは、ソーシャルネットワーク、通信システム、生理学的および生物学的ネットワークなど、様々な分野でますます重要な役割を担っている。 この風景の中で、ランダムクロネッカーグラフモデルは、複雑な現実世界のネットワークを精査するための顕著なフレームワークとして現れる。 本稿では,Kroneckerグラフの大規模乱数,すなわちグラフ頂点数が$N$であることを示す。 ランダム行列理論(RMT)と高次元統計学の最近の進歩に基づいて、大きなランダムクロネッカーグラフの隣接性はスペクトルノルムの意味で分解可能であることを証明した: グラフパラメータとゼロ平均ランダムノイズ行列において線形な小さなランク(ランク$O(\log N)$)信号行列である。 この結果に基づき,計算量を大幅に削減したキーグラフパラメータを推算する ``denoise-and-solve''' 手法を提案する。 提案手法を評価するために,グラフ推定と分類の両方の実験を行った。 どちらのタスクにおいても、提案されたアプローチは、グラフサイズ$n$として線形にスケールする時間コストで、広く使われているグラフ推論(例えば、kronfit)やグラフニューラルネットワークベースラインと同等あるいは有利なパフォーマンスをもたらす。

関連論文リスト

• 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)

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

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