論文の概要: Improved Reconstruction of Random Geometric Graphs
- arxiv url: http://arxiv.org/abs/2107.14323v1
- Date: Thu, 29 Jul 2021 20:37:28 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-15 12:46:35.090879
- Title: Improved Reconstruction of Random Geometric Graphs
- Title（参考訳）: ランダム幾何グラフの再構築
- Authors: Varsha Dani and Josep D\'iaz and Thomas P. Hayes and Cristopher Moore
- Abstract要約: ランダムな幾何グラフの古典的モデルを考えると、$n$の点が一様に領域$n$の正方形に散らばっている。
グラフ距離と近距離推定のハイブリッドを用いてユークリッド距離を推定する。
本手法は, グラフ距離と近辺点数に基づく短距離推定のハイブリッドを用いてユークリッド距離を推定する。
- 参考スコア（独自算出の注目度）: 3.930410971186142
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Embedding graphs in a geographical or latent space, i.e., inferring locations
for vertices in Euclidean space or on a smooth submanifold, is a common task in
network analysis, statistical inference, and graph visualization. We consider
the classic model of random geometric graphs where $n$ points are scattered
uniformly in a square of area $n$, and two points have an edge between them if
and only if their Euclidean distance is less than $r$. The reconstruction
problem then consists of inferring the vertex positions, up to symmetry, given
only the adjacency matrix of the resulting graph. We give an algorithm that, if
$r=n^\alpha$ for $\alpha > 0$, with high probability reconstructs the vertex
positions with a maximum error of $O(n^\beta)$ where $\beta=1/2-(4/3)\alpha$,
until $\alpha \ge 3/8$ where $\beta=0$ and the error becomes $O(\sqrt{\log
n})$. This improves over earlier results, which were unable to reconstruct with
error less than $r$. Our method estimates Euclidean distances using a hybrid of
graph distances and short-range estimates based on the number of common
neighbors. We sketch proofs that our results also apply on the surface of a
sphere, and (with somewhat different exponents) in any fixed dimension.
- Abstract（参考訳）: 地理空間や潜在空間、すなわちユークリッド空間や滑らかな部分多様体上の頂点の位置を推定するグラフの埋め込みは、ネットワーク分析、統計推論、グラフ視覚化において一般的なタスクである。
ランダムな幾何グラフの古典的モデルを考えると、$n$の点が一様に領域$n$の正方形に散らばっており、2つの点がそのユークリッド距離が$r$より小さい場合に限る。
再構成問題は、結果のグラフの隣接行列のみを与えられた頂点位置を対称性まで推測することからなる。
r=n^\alpha$ for $\alpha > 0$とすると、高い確率で頂点位置を最大誤差$O(n^\beta)$, $\beta=1/2-(4/3)\alpha$, $\alpha \ge 3/8$, $\beta=0$, そして誤差が$O(\sqrt{\log n})$に再構成するアルゴリズムを与える。
これは以前の結果よりも改善され、$r$未満のエラーで再構築できなかった。
本手法は, グラフ距離と近辺点数に基づく短距離推定のハイブリッドを用いてユークリッド距離を推定する。
我々は、この結果が球面にも当てはまること、そして(幾分異なる指数を持つ)任意の固定次元におけることの証明をスケッチする。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits [24.592554830963966]
グラフが任意の開始ノードから任意のターゲットノードへの移動に成功すれば、グラフはナビゲート可能である。
アプリケーションにとって重要な問題は、スペーサーグラフを構築することができるかどうかである。
任意の次元において、任意の距離関数に対して、平均次数$O(sqrtn log n )$の任意の$n$点に対してナビゲート可能なグラフを構築するための単純かつ効率的な方法を与える。
論文 参考訳（メタデータ） (2024-05-29T01:07:26Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - A note on estimating the dimension from a random geometric graph [2.3020018305241337]
グラフの隣接行列にアクセスする際に、基礎空間の次元$d$を推定する問題について検討する。
また、密度の条件がなければ、$d$の一貫した推定子は$n r_nd to infty$と$r_n = o(1)$が存在することを示す。
論文 参考訳（メタデータ） (2023-11-21T23:46:44Z) - 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) - Planted Bipartite Graph Detection [13.95780443241133]
ランダムグラフに隠れた二部グラフを検出するタスクについて検討する。
ヌル仮説の下では、このグラフは、エッジ密度$q$の$n$上のアードホスラーイランダムグラフの実現である。
k_mathsfR times k_mathsfL$ bipartite subgraph with edge density $p>q$。
論文 参考訳（メタデータ） (2023-02-07T18:18:17Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。
近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文 参考訳（メタデータ） (2022-02-22T04:14:45Z) - Fast Computation of Generalized Eigenvectors for Manifold Graph
Embedding [38.902986549367434]
我々は、高速実行に既存の高速極端固有ベクトル計算アルゴリズムを利用する。
我々の埋め込みは文献の中では最速であり、多様体グラフのクラスタリング性能は最高のものとなっている。
論文 参考訳（メタデータ） (2021-12-15T03:45:39Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。