論文の概要: Learning-Augmented Streaming Algorithms for Correlation Clustering
- arxiv url: http://arxiv.org/abs/2510.10705v1
- Date: Sun, 12 Oct 2025 17:04:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-14 18:06:30.077306
- Title: Learning-Augmented Streaming Algorithms for Correlation Clustering
- Title（参考訳）: 相関クラスタリングのための学習強化ストリーミングアルゴリズム
- Authors: Yinhao Dong, Shan Jiang, Shi Li, Pan Peng,
- Abstract要約: 相関クラスタリングのためのストリーミングアルゴリズムについて検討する。
完全グラフと一般グラフの両方に関する問題に対して,初めて学習強化されたストリーミングアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 6.0943362338120055
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study streaming algorithms for Correlation Clustering. Given a graph as an arbitrary-order stream of edges, with each edge labeled as positive or negative, the goal is to partition the vertices into disjoint clusters, such that the number of disagreements is minimized. In this paper, we give the first learning-augmented streaming algorithms for the problem on both complete and general graphs, improving the best-known space-approximation tradeoffs. Based on the works of Cambus et al. (SODA'24) and Ahn et al. (ICML'15), our algorithms use the predictions of pairwise distances between vertices provided by a predictor. For complete graphs, our algorithm achieves a better-than-$3$ approximation under good prediction quality, while using $\tilde{O}(n)$ total space. For general graphs, our algorithm achieves an $O(\log |E^-|)$ approximation under good prediction quality using $\tilde{O}(n)$ total space, improving the best-known non-learning algorithm in terms of space efficiency. Experimental results on synthetic and real-world datasets demonstrate the superiority of our proposed algorithms over their non-learning counterparts.
- Abstract（参考訳）: 相関クラスタリングのためのストリーミングアルゴリズムについて検討する。
エッジの任意の順序列としてグラフが与えられると、各エッジを正または負のラベルでラベル付けし、頂点を不整合クラスタに分割し、不整合の数を最小限に抑える。
本稿では,完全グラフと一般グラフの両問題に対する学習強化された最初のストリーミングアルゴリズムについて述べる。
Cambus et al (SODA'24) と Ahn et al (ICML'15) の業績に基づき、我々のアルゴリズムは予測器によって提供される頂点間のペア距離の予測を使用する。
完全グラフに対して、我々のアルゴリズムは、$\tilde{O}(n)$ total space を用いて予測精度の良い3$近似を達成する。
一般グラフに対して、このアルゴリズムは、$\tilde{O}(n)$トータル空間を用いて予測精度の高い$O(\log |E^-|)$近似を達成し、空間効率の観点から最もよく知られた非学習アルゴリズムを改善する。
合成および実世界のデータセットに対する実験結果は、提案アルゴリズムが非学習データセットよりも優れていることを示す。
関連論文リスト
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Efficient Graph Matching for Correlated Stochastic Block Models [7.320365821066744]
2つのバランスの取れたコミュニティを持つ相関ブロックモデルの学習問題について検討する。
我々の主な成果は、この設定におけるグラフマッチングのための最初の効率的なアルゴリズムである。
我々はこれを情報理論的に可能であれば、正確なグラフマッチングのための効率的なアルゴリズムに拡張する。
論文 参考訳（メタデータ） (2024-12-03T18:36:45Z) - Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。
まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。
補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
論文 参考訳（メタデータ） (2024-04-24T18:39:18Z) - A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。
我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
論文 参考訳（メタデータ） (2024-03-21T11:57:16Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Sublinear Time and Space Algorithms for Correlation Clustering via
Sparse-Dense Decompositions [9.29659220237395]
本稿では,相関クラスタリングの解法を提案する。
我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。
提案手法の主な要素はスパース線グラフ分解への新規な接続である。
論文 参考訳（メタデータ） (2021-09-29T16:25:02Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time [1.5644420658691407]
エッジ重み付きグラフ上での階層的凝集クラスタリング(HAC)アルゴリズムについて検討する。
階層的な集合グラフクラスタリングのためのアルゴリズムフレームワークを定義する。
提案手法は,ポイントデータセットのクラスタリングを20.7～76.5倍の速度で高速化できることを示す。
論文 参考訳（メタデータ） (2021-06-10T09:29:05Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。