論文の概要: Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using
Graph-based Machine Learning
- arxiv url: http://arxiv.org/abs/2201.01825v1
- Date: Wed, 5 Jan 2022 21:11:23 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-07 22:50:08.831647
- Title: Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using
Graph-based Machine Learning
- Title（参考訳）: グラフベース機械学習を用いて高密度乱数グラフに植木したDenseサブグラフを検索する
- Authors: Itay Levinas and Yoram Louzoun
- Abstract要約: 本稿では,グラフニューラルネットワークに基づくアルゴリズムであるPYGONについて述べる。
我々はPYGONが$Thetaleft(sqrtnright)$を復元できることを示し、$n$は背景グラフのサイズである。
また、同じアルゴリズムで、$Thetaleft(sqrtnright)$の複数の植字されたサブグラフを、有向および無向の両方で復元できることを示す。
- 参考スコア（独自算出の注目度）: 1.52292571922932
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Multiple methods of finding the vertices belonging to a planted dense
subgraph in a random dense $G(n, p)$ graph have been proposed, with an emphasis
on planted cliques. Such methods can identify the planted subgraph in
polynomial time, but are all limited to several subgraph structures. Here, we
present PYGON, a graph neural network-based algorithm, which is insensitive to
the structure of the planted subgraph. This is the first algorithm that uses
advanced learning tools for recovering dense subgraphs. We show that PYGON can
recover cliques of sizes $\Theta\left(\sqrt{n}\right)$, where $n$ is the size
of the background graph, comparable with the state of the art. We also show
that the same algorithm can recover multiple other planted subgraphs of size
$\Theta\left(\sqrt{n}\right)$, in both directed and undirected graphs. We
suggest a conjecture that no polynomial time PAC-learning algorithm can detect
planted dense subgraphs with size smaller than $O\left(\sqrt{n}\right)$, even
if in principle one could find dense subgraphs of logarithmic size.
- Abstract（参考訳）: ランダムな高密度な$G(n, p)$グラフにおいて、植込みされた高密度部分グラフに属する頂点を見つけるための複数の方法が提案され、植込みされた斜めに重点を置いている。
そのような方法は、植込まれた部分グラフを多項式時間で識別できるが、全ていくつかの部分グラフ構造に限定される。
本稿では,グラフニューラルネットワークに基づくアルゴリズムであるPYGONについて述べる。
これは、高度な学習ツールを使って高密度サブグラフを復元する最初のアルゴリズムである。
PYGONは、背景グラフのサイズである$\Theta\left(\sqrt{n}\right)$を復元できることを示す。
また,同じアルゴリズムが,有向グラフと無向グラフの両方において,複数の植込み部分グラフに対して$\theta\left(\sqrt{n}\right)$を回収できることも示す。
我々は、多項式時間PAC学習アルゴリズムが$O\left(\sqrt{n}\right)$より小さい植込み高密度部分グラフを検出できないという予想を、原理上は対数サイズの高密度部分グラフを見つけることができたとしても提案する。
関連論文リスト
- Jaccard-constrained dense subgraph discovery [2.4511852052357628]
大きい対のジャカード類似係数を持つ高密度部分グラフを探索する。
我々は,我々のアルゴリズムが効率的であることを実験的に示し,合成データセットに基底真理を見つけ,実世界のデータセットから解釈可能な結果を提供する。
論文 参考訳（メタデータ） (2023-08-30T10:33:02Z) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An
Index-based Approach [9.13755431537592]
本稿では,相関クラスタリング問題を$O(mtimesleft(2+ alpha (G) right)+n)$から$O(m+n)$に近似する複雑性を,完全符号グラフに対して$varepsilon$とする。
提案手法は,元のアルゴリズムと同じ出力を与え,そのアルゴリズムをフルダイナミックな設定で実装できるようにする。
論文 参考訳（メタデータ） (2023-01-01T10:57:36Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Random Subgraph Detection Using Queries [29.192695995340653]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。
このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
論文 参考訳（メタデータ） (2021-10-02T07:41:17Z) - The Generalized Mean Densest Subgraph Problem [30.33731479053404]
1つのパラメータ$p$でパラメータ化された、高密度なサブグラフ対象の新しいファミリーを導入する。
我々の目的は、標準の高密度部分グラフ問題と特別な場合の最大$k$-coreの両方をキャプチャする。
我々の研究の大きな貢献は、理論と実践の両方において、密接な部分グラフに対する様々な種類の剥離アルゴリズムの性能を分析することである。
論文 参考訳（メタデータ） (2021-06-02T02:58:35Z) - Efficient Graph Deep Learning in TensorFlow with tf_geometric [53.237754811019464]
グラフ深層学習のための効率的でフレンドリなライブラリであるtf_geometricを導入する。
tf_geometricは、人気のあるGNNの実装と同様に、グラフニューラルネットワーク(GNN)を構築するためのカーネルライブラリを提供する。
カーネルライブラリは、グラフデータ構造、グラフマップ-リデュースフレームワーク、グラフミニバッチ戦略など、効率的なGNNを構築するためのインフラストラクチャで構成されている。
論文 参考訳（メタデータ） (2021-01-27T17:16:36Z) - A step towards neural genome assembly [0.0]
我々はMPNNモデルを最大集約器で訓練し、グラフ単純化のためのいくつかのアルゴリズムを実行する。
アルゴリズムがうまく学習され、トレーニングで使用されるグラフの最大20倍の大きさのグラフにスケールできることを示す。
論文 参考訳（メタデータ） (2020-11-10T10:12:19Z) - Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
既存のディープニューラルネットワーク手法では、隣接行列を構築することで、$Omega(n2)$複雑さを必要とする。
我々は,この空間を利用して完全隣接行列を生成する新しい自己回帰モデルBiGGを開発した。
トレーニング中、この自己回帰モデルは$O(log n)$同期ステージで並列化できる。
論文 参考訳（メタデータ） (2020-06-28T04:37:57Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。