論文の概要: Community detection using fast low-cardinality semidefinite programming

• arxiv url: http://arxiv.org/abs/2012.02676v1
• Date: Fri, 4 Dec 2020 15:46:30 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-22 20:32:20.916791
• Title: Community detection using fast low-cardinality semidefinite programming
• Title（参考訳）: 高速低次半有限プログラムを用いたコミュニティ検出
• Authors: Po-Wei Wang, J. Zico Kolter
• Abstract要約: 局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。 提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
• 参考スコア（独自算出の注目度）: 94.4878715085334
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Modularity maximization has been a fundamental tool for understanding the community structure of a network, but the underlying optimization problem is nonconvex and NP-hard to solve. State-of-the-art algorithms like the Louvain or Leiden methods focus on different heuristics to help escape local optima, but they still depend on a greedy step that moves node assignment locally and is prone to getting trapped. In this paper, we propose a new class of low-cardinality algorithm that generalizes the local update to maximize a semidefinite relaxation derived from max-k-cut. This proposed algorithm is scalable, empirically achieves the global semidefinite optimality for small cases, and outperforms the state-of-the-art algorithms in real-world datasets with little additional time cost. From the algorithmic perspective, it also opens a new avenue for scaling-up semidefinite programming when the solutions are sparse instead of low-rank.
• Abstract（参考訳）: モジュラリティの最大化はネットワークのコミュニティ構造を理解するための基本的なツールであるが、基盤となる最適化問題は非凸であり、np困難である。 louvainやleidenといった最先端のアルゴリズムは、局所的なオプティマから逃れるために異なるヒューリスティックに焦点を合わせているが、それでもノードの割り当てをローカルに移動させ、罠にかかりやすいという欲張りなステップに依存している。 本稿では,max-k-cutによる半定値緩和を最大化するために,局所更新を一般化した新しい低カージナリティアルゴリズムを提案する。 提案アルゴリズムは拡張性があり、小規模なケースに対して大域半定最適性を実証的に達成し、実際のデータセットにおける最先端のアルゴリズムよりも、時間的コストがほとんどない。 アルゴリズムの観点からは、ソリューションが低ランクではなくスパースである場合に、半定義型プログラミングをスケールアップするための新しい道を開く。

関連論文リスト

• Characterization of Locality in Spin States and Forced Moves for Optimizations [0.36868085124383626]
  最適化問題において、エネルギーランドスケープにおける局所最小値の存在は、世界最小値を求めるために問題となる。 そこで我々は,局所最小値から効率よく抜け出すアルゴリズムを開発したが,正確なサンプリングは得られなかった。 提案アルゴリズムはリジェクションフリーなアルゴリズムに基づいているため,計算コストは低い。
  論文  参考訳（メタデータ） (2023-12-05T07:21:00Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization [43.31016937305845]
  インターネット・オブ・シング、ネットワークセンシング、自律システム、有限サム最適化のための分散アルゴリズムのためのフェデレーション学習。 非有限サム最適化のためのDecentralized STochastic Recursive MethodDESTRESSを開発した。 詳細な理論的および数値的な比較は、DESTRESSが事前の分散アルゴリズムにより改善されていることを示している。
  論文  参考訳（メタデータ） (2021-10-04T03:17:41Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data [59.50904660420082]
  フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。 クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
  論文  参考訳（メタデータ） (2020-05-22T23:07:42Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)

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

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