論文の概要: Correlation Clustering with Random Partial Information
- arxiv url: http://arxiv.org/abs/2608.16315v1
- Date: Mon, 17 Aug 2026 09:22:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-18 19:59:03.616594
- Title: Correlation Clustering with Random Partial Information
- Title（参考訳）: ランダム部分情報を用いた相関クラスタリング
- Abstract要約: 相関クラスタリングは基本的な教師なし学習問題である。
完全符号グラフをランダムにサブサンプリングして得られる自然グラフのクラスを$G$で研究する。
一般グラフに対して達成可能な境界よりもかなり良い近似を保証する。
- 参考スコア（独自算出の注目度）: 4.706621352211144
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor approximations, yet on general (non-complete) graphs, the best guarantees blow up to $O(\log n)$ and $O(\sqrt{n})$. This gap between the two regimes motivates the following question: are there classes of incomplete graphs that circumvent the lower bounds on general graphs and admit approximation guarantees approaching those attainable on complete graphs? We study a natural class of graphs obtained by randomly subsampling a complete signed graph $G$, where each edge is independently deleted with probability $q$. For such graph instances both for the min-max and the min-disagreement objectives, we prove approximation guarantees (depending on $q$) that are substantially better than the bounds achievable for general graphs. We supplement our theoretical results with experiments that also suggest that the approximation ratios of our algorithm are close to those of the complete graph and better than the worst-case bounds for general (non-complete) graphs.
- Abstract（参考訳）: 相関クラスタリングは基本的な教師なし学習問題である。
完全グラフ上では、min-disagreement と min-max の目的の両方が定数要素近似を許容するが、一般(非完全)グラフでは、最良の保証は$O(\log n)$と$O(\sqrt{n})$に爆発する。
一般グラフ上の下界を回避し、完備グラフ上で達成可能なものへの近似保証を許容する不完全グラフのクラスは存在するか?
完全符号付きグラフをランダムにサブサンプリングして得られるグラフの自然なクラスについて研究し、各エッジは確率$q$で独立に削除される。
そのようなグラフインスタンスを min-max と min-disagreement の目的の両方に対して、一般グラフに対して達成可能な境界よりもかなり良い近似保証($q$ に依存する)を証明する。
また,アルゴリズムの近似比が全グラフの近似比に近く,一般(非完全)グラフの最悪のケース境界よりも優れていることを示す実験で理論結果を補足する。
関連論文リスト
- Simultaneous variances of Pauli strings, weighted independence numbers, and a new kind of perfection of graphs [13.60873698530933]
可換性構造を符号化するグラフ、すなわちフラストレーショングラフによって、グラフ理論と量子情報の間の自然なインターフェースを提供する。
このクラスを$hbar$-perfectと呼び、完全グラフと$hbar-perfectグラフのクラスを拡張します。
絡み合い検出のための効率的なスキーム,シャドウトモグラフィーの複雑さへの接続,厳密な不確実性関係,地中エネルギーの低い計算のための構成を見いだす。
論文 参考訳（メタデータ） (2025-11-17T16:05:28Z) - On Approximate MMS Allocations on Restricted Graph Classes [0.31457219084519]
本研究では,接続制約のある不特定商品群を公平に分割する問題について検討する。
完備グラフ、サイクル、固定された$d$に対する$d$-claw-freeグラフのようなグラフのクラスが実際に存在することは知られている。
このようなアロケーションは、ブロックグラフ、cacti、完全多部グラフ、分割グラフなど、よく研究されているクラスに存在していることを示す。
論文 参考訳（メタデータ） (2025-08-08T14:17:44Z) - Efficient Graph Matching for Correlated Stochastic Block Models [7.320365821066744]
2つのバランスの取れたコミュニティを持つ相関ブロックモデルの学習問題について検討する。
我々の主な成果は、この設定におけるグラフマッチングのための最初の効率的なアルゴリズムである。
我々はこれを情報理論的に可能であれば、正確なグラフマッチングのための効率的なアルゴリズムに拡張する。
論文 参考訳（メタデータ） (2024-12-03T18:36:45Z) - MGNet: Learning Correspondences via Multiple Graphs [78.0117352211091]
学習対応は、不均一な対応分布と低い不整合率で設定された初期対応から正しい対応を見つけることを目的としている。
最近の進歩は、通常、グラフニューラルネットワーク(GNN)を使用して単一のタイプのグラフを構築したり、グローバルなグラフに局所グラフをスタックしてタスクを完了させる。
本稿では,複数の補完グラフを効果的に組み合わせるためのMGNetを提案する。
論文 参考訳（メタデータ） (2024-01-10T07:58:44Z) - Improved High-Probability Regret for Adversarial Bandits with
Time-Varying Feedback Graphs [62.52390282012508]
我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。
提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。
また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-04T04:36:15Z) - Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF)
我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。
我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
論文 参考訳（メタデータ） (2022-05-28T15:37:03Z) - The Performance of the MLE in the Bradley-Terry-Luce Model in
$\ell_{\infty}$-Loss and under General Graph Topologies [76.61051540383494]
我々はBradley-Terry-Luceモデルの$ell_infty$推定誤差に関する新しい一般上限を導出する。
導出された境界は良好に機能し、場合によっては既知の結果よりもシャープであることを示す。
論文 参考訳（メタデータ） (2021-10-20T23:46:35Z) - Settling the Sharp Reconstruction Thresholds of Random Graph Matching [19.54246087326288]
2つのエッジ関連ランダムグラフ間の隠れた対応を復元する問題について検討する。
p=n-o(1)$のグラフに対して、鋭いしきい値が存在することが証明される。
sparse ErdHos-R'enyi graphs with $p=n-Theta(1)$ に対して、オール・オー・ナッシング現象はもはや成り立たないことを示す。
論文 参考訳（メタデータ） (2021-01-29T21:49:50Z) - Random Graph Matching with Improved Noise Robustness [2.294014185517203]
本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。
我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。
これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
論文 参考訳（メタデータ） (2021-01-28T02:39:27Z) - Multilevel Graph Matching Networks for Deep Graph Similarity Learning [79.3213351477689]
グラフ構造オブジェクト間のグラフ類似性を計算するためのマルチレベルグラフマッチングネットワーク(MGMN)フレームワークを提案する。
標準ベンチマークデータセットの欠如を補うため、グラフグラフ分類とグラフグラフ回帰タスクの両方のためのデータセットセットを作成し、収集した。
総合的な実験により、MGMNはグラフグラフ分類とグラフグラフ回帰タスクの両方において、最先端のベースラインモデルより一貫して優れていることが示された。
論文 参考訳（メタデータ） (2020-07-08T19:48:19Z) - Graph Pooling with Node Proximity for Hierarchical Representation
Learning [80.62181998314547]
本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。
その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
論文 参考訳（メタデータ） (2020-06-19T13:09:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。