論文の概要: Scalable network reconstruction in subquadratic time
- arxiv url: http://arxiv.org/abs/2401.01404v3
- Date: Mon, 12 Feb 2024 13:01:54 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-13 21:08:50.813528
- Title: Scalable network reconstruction in subquadratic time
- Title（参考訳）: subquadratic timeにおけるスケーラブルネットワーク再構成
- Authors: Tiago P. Peixoto
- Abstract要約: 本稿では,幅広い再構成問題に適用可能な汎用アルゴリズムを提案する。
我々のアルゴリズムは、高い確率で最適なエッジ候補を生成する第2の隣人探索に依存している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Network reconstruction consists in determining the unobserved pairwise
couplings between $N$ nodes given only observational data on the resulting
behavior that is conditioned on those couplings -- typically a time-series or
independent samples from a graphical model. A major obstacle to the scalability
of algorithms proposed for this problem is a seemingly unavoidable quadratic
complexity of $O(N^2)$, corresponding to the requirement of each possible
pairwise coupling being contemplated at least once, despite the fact that most
networks of interest are sparse, with a number of non-zero couplings that is
only $O(N)$. Here we present a general algorithm applicable to a broad range of
reconstruction problems that achieves its result in subquadratic time, with a
data-dependent complexity loosely upper bounded by $O(N^{3/2}\log N)$, but with
a more typical log-linear complexity of $O(N\log^2N)$. Our algorithm relies on
a stochastic second neighbor search that produces the best edge candidates with
high probability, thus bypassing an exhaustive quadratic search. In practice,
our algorithm achieves a performance that is many orders of magnitude faster
than the quadratic baseline, allows for easy parallelization, and thus enables
the reconstruction of networks with hundreds of thousands and even millions of
nodes and edges.
- Abstract（参考訳）: ネットワーク再構成は、それらの結合(典型的には、グラフィカルモデルからの時系列または独立したサンプル)に条件づけられた結果の振る舞いに関する観測データのみを与えられた$N$ノード間の、観測されていないペアワイズ結合を決定することである。
この問題のために提案されたアルゴリズムのスケーラビリティに対する大きな障害は、一見避けられない二次的複雑性である$o(n^2)$であり、関心のあるネットワークのほとんどがスパースであり、いくつかの非ゼロ結合が$o(n)$であるという事実にもかかわらず、各ペアワイズ結合が少なくとも1回は検討されている要件に対応している。
本稿では,o(n^{3/2}\log n)$という大まかな上限値を持つデータ依存的複雑性を持つが,より典型的な対数線形複雑性であるo(n\log^2n)$を持つ,サブクアドラル時間でその結果を達成する,幅広いレコンストラクション問題に適用可能な一般アルゴリズムを提案する。
我々のアルゴリズムは, 確率的に第2の隣接探索に依拠し, 最良辺候補を高い確率で生成し, 余剰二次探索をバイパスする。
実際、我々のアルゴリズムは、2次ベースラインよりも桁違いに高速な性能を実現し、容易に並列化が可能となり、数十万のノードとエッジでネットワークを再構築することができる。
関連論文リスト
- Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。
次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
論文 参考訳（メタデータ） (2024-04-18T17:57:53Z) - A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical
Initialization [107.07093621337084]
正規化カット(N-Cut)は、スペクトルクラスタリングの有名なモデルである。
1)正規化ラプラシア行列の連続スペクトル埋め込みを計算する; 2)$K$-meansまたはスペクトル回転による離散化。
有名な座標降下法に基づく新しいN-Cut解法を提案する。
論文 参考訳（メタデータ） (2023-11-26T07:11:58Z) - Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still
Impractical, Quantum Distributed Algorithms [0.0]
確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。
従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。
Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
論文 参考訳（メタデータ） (2023-04-06T02:18:52Z) - Time and Query Complexity Tradeoffs for the Dihedral Coset Problem [0.19731444261635428]
Z_N$のディヘドラルコセット問題(DCP)は量子コンピューティングやポスト量子暗号において広く研究されている。
Ettinger-Hoyerアルゴリズムは$O(log(N))$クエリでDCPを解くことが知られている。
本稿では,Ettinger-Hoyerアルゴリズムよりも線形クエリ方式を改良した最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-29T05:30:54Z) - Spatial search by continuous-time quantum walks on renormalized Internet
networks [0.0]
実世界の複雑なネットワーク上での連続的な量子ウォークを用いた空間探索について検討する。
実世界の複素ネットワーク上での量子空間探索アルゴリズムの挙動を初めて推測する。
論文 参考訳（メタデータ） (2022-05-04T15:46:14Z) - Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and
Costs [45.87981728307819]
異種空間に居住する関連するデータセットを比較して整列する能力は、機械学習においてますます重要な役割を担っている。
グロモフ・ワッサーシュタイン (Gromov-Wasserstein, GW) 形式主義はこの問題に対処するのに役立つ。
論文 参考訳（メタデータ） (2021-06-02T12:50:56Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。