論文の概要: Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach
- arxiv url: http://arxiv.org/abs/2505.18043v1
- Date: Fri, 23 May 2025 15:46:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-26 18:08:34.204441
- Title: Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach
- Title（参考訳）: エッジカラーハイパーグラフの重畳とロバストクラスタリングのためのアルゴリズムの改良:LPベースの組合せアプローチ
- Authors: Changyeol Lee, Yongho Shin, Hyung-Chan An,
- Abstract要約: エッジカラークラスタリング(ECC)は、カテゴリデータを扱う上で有用なアプローチである。
これらの制限に対処するため、ECCの3つのバージョンが研究されている。
本稿では,LPの強みとアルゴリズムの計算効率を組み合わせたアルゴリズムフレームワークを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Clustering is a fundamental task in both machine learning and data mining. Among various methods, edge-colored clustering (ECC) has emerged as a useful approach for handling categorical data. Given a hypergraph with (hyper)edges labeled by colors, ECC aims to assign vertex colors to minimize the number of edges where the vertex color differs from the edge's color. However, traditional ECC has inherent limitations, as it enforces a nonoverlapping and exhaustive clustering. To tackle these limitations, three versions of ECC have been studied: Local ECC and Global ECC, which allow overlapping clusters, and Robust ECC, which accounts for vertex outliers. For these problems, both linear programming (LP) rounding algorithms and greedy combinatorial algorithms have been proposed. While these LP-rounding algorithms provide high-quality solutions, they demand substantial computation time; the greedy algorithms, on the other hand, run very fast but often compromise solution quality. In this paper, we present an algorithmic framework that combines the strengths of LP with the computational efficiency of combinatorial algorithms. Both experimental and theoretical analyses show that our algorithms efficiently produce high-quality solutions for all three problems: Local, Global, and Robust ECC. We complement our algorithmic contributions with complexity-theoretic inapproximability results and integrality gap bounds, which suggest that significant theoretical improvements are unlikely. Our results also answer two open questions previously raised in the literature.
- Abstract（参考訳）: クラスタリングは、機械学習とデータマイニングの両方において、基本的なタスクである。
エッジカラークラスタリング(ECC)は分類データを扱う上で有用な手法である。
色でラベル付けされた(ハイパー)エッジのハイパーグラフが与えられた場合、ECCは頂点色を割り当て、頂点色がエッジの色と異なるエッジの数を最小限にすることを目的としている。
しかし、従来のECCには本質的に制限がある。
これらの制限に対処するために、ローカルECCとグローバルECCの3つのバージョンが研究されている。
これらの問題に対して、線形プログラミング(LP)ラウンドリングアルゴリズムとグリーディ組合せアルゴリズムの両方が提案されている。
これらのLPラウンドのアルゴリズムは高品質なソリューションを提供するが、相当な計算時間を必要とする。
本稿では,LPの強みと組合せアルゴリズムの計算効率を組み合わせたアルゴリズムフレームワークを提案する。
実験と理論的解析の両方で、我々のアルゴリズムは、ローカル、グローバル、ロバストECCの3つの問題に対して効率よく高品質な解を生成する。
我々は,複雑性理論的不近似結果と積分性ギャップ境界を補完し,有意な理論的改善はあり得ないことを示唆する。
文献で以前に提起された2つのオープンな質問にも回答した。
関連論文リスト
- An island-parallel ensemble metaheuristic algorithm for large graph coloring problems [0.4915744683251149]
大規模GCPインスタンスを解決するために,島並列アンサンブルメタヒューリスティックアルゴリズム(PEM-Color)を提案する。
私たちの知る限りでは、これはメタヒューリスティックスを組み合わせて、アンサンブルアプローチを使用してGCPに適用する最初の研究です。
論文 参考訳（メタデータ） (2025-04-21T13:15:23Z) - Tree-Guided $L_1$-Convex Clustering [1.0589208420411012]
本研究では,新しい凸クラスタリングアルゴリズムであるTree-Guided- Clusteringを開発した。
最適化プロセスの高速化に重みのツリーを利用する,効率的なクラスタ融合アルゴリズムを開発した。
注目すべきは、私たちのTGCCアルゴリズムは、ラップトップ標準で$mathbbR2秒で完全なデングラムを構築することができることです。
論文 参考訳（メタデータ） (2025-03-31T12:39:48Z) - A Greedy Strategy for Graph Cut [95.2841574410968]
GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。
これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。
GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
論文 参考訳（メタデータ） (2024-12-28T05:49:42Z) - Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search [61.08720171136229]
本稿では,3つの革新的手法のハイブリッド化に基づく問題に対する新しいアルゴリズムSMARTを提案する。
これらの2つの手法は動的プログラミングに基づいており、評価のために選択された連立関係とアルゴリズムの性能の強力な関係を示す。
我々の手法は、問題にアプローチする新しい方法と、その分野に新しいレベルの精度をもたらす。
論文 参考訳（メタデータ） (2024-07-22T23:24:03Z) - Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。
従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。
本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-15T04:57:37Z) - Randomized Greedy Algorithms and Composable Coreset for k-Center
Clustering with Outliers [11.546734084378683]
外れ値の存在は計算の複雑さを著しく増大させる。
我々のアイデアは、通常の$k$-centerクラスタリング問題を解決するために開発されたgreedy法にインスパイアされている。
論文 参考訳（メタデータ） (2023-01-07T09:26:01Z) - An algorithm for clustering with confidence-based must-link and cannot-link constraints [0.0]
我々はPCCCアルゴリズム(Pairwise-Confidence-Constraints-Clustering)を導入する。
PCCCアルゴリズムは、オブジェクトのペアに提供された情報を考慮しながら、反復的にオブジェクトをクラスタに割り当てる。
既存のアルゴリズムとは異なり、我々のアルゴリズムは最大6万のオブジェクト、100のクラスタ、数百万のnot-link制約を持つ大規模インスタンスにスケールする。
論文 参考訳（メタデータ） (2022-12-29T19:21:33Z) - A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programming [14.35928967799696]
本稿では,分散化ネットワーク上での双方向プログラミング問題の解法として,ペナルティ関数に基づく分散化アルゴリズムを提案する。
提案アルゴリズムの重要な特徴は,ペナルティ関数の過度勾配の推定である。
我々の理論的枠組みは、様々な凸条件下での原問題の最適解に漸近的でない収束を保証する。
論文 参考訳（メタデータ） (2022-11-08T08:39:30Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳（メタデータ） (2021-06-09T09:18:18Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。