論文の概要: One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering
- arxiv url: http://arxiv.org/abs/2305.07386v1
- Date: Fri, 12 May 2023 11:27:20 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-15 13:19:26.571780
- Title: One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering
- Title（参考訳）: 一段階二部グラフカット:正規化された定式化とスケーラブルな部分空間クラスタリングへの応用
- Authors: Si-Guo Fang, Dong Huang, Chang-Dong Wang, Jian-Huang Lai
- Abstract要約: 両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。
本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。
このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
- 参考スコア（独自算出の注目度）: 56.81492360414741
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The bipartite graph structure has shown its promising ability in facilitating
the subspace clustering and spectral clustering algorithms for large-scale
datasets. To avoid the post-processing via k-means during the bipartite graph
partitioning, the constrained Laplacian rank (CLR) is often utilized for
constraining the number of connected components (i.e., clusters) in the
bipartite graph, which, however, neglects the distribution (or normalization)
of these connected components and may lead to imbalanced or even ill clusters.
Despite the significant success of normalized cut (Ncut) in general graphs, it
remains surprisingly an open problem how to enforce a one-step normalized cut
for bipartite graphs, especially with linear-time complexity. In this paper, we
first characterize a novel one-step bipartite graph cut (OBCut) criterion with
normalized constraints, and theoretically prove its equivalence to a trace
maximization problem. Then we extend this cut criterion to a scalable subspace
clustering approach, where adaptive anchor learning, bipartite graph learning,
and one-step normalized bipartite graph partitioning are simultaneously modeled
in a unified objective function, and an alternating optimization algorithm is
further designed to solve it in linear time. Experiments on a variety of
general and large-scale datasets demonstrate the effectiveness and scalability
of our approach.
- Abstract（参考訳）: 2部グラフ構造は,大規模データセットのサブスペースクラスタリングとスペクトルクラスタリングアルゴリズムの容易化に有望な能力を示している。
二部グラフ分割中のk-平均による後処理を避けるために、制限されたラプラシア階数(CLR)は二部グラフ内の連結成分(すなわちクラスタ)の数を制限するためにしばしば使用されるが、これらの連結成分の分布(あるいは正規化)を無視し、不均衡や不規則なクラスターにつながる可能性がある。
一般グラフにおける正規化カット(Ncut)の顕著な成功にもかかわらず、特に線形時間複雑性のある二部グラフに対して一段階正規化カットを強制する方法は驚くほどオープンな問題である。
本稿では,まず,正規化制約のある新しい一段階二分グラフカット(obcut)基準を特徴付け,その等価性をトレース最大化問題に理論的に証明する。
次に、このカット基準をスケーラブルな部分空間クラスタリングアプローチに拡張し、適応型アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を統一目的関数で同時にモデル化し、線形時間で解くために交互最適化アルゴリズムを更に設計する。
様々な一般および大規模データセットの実験は、我々のアプローチの有効性とスケーラビリティを実証している。
関連論文リスト
- HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
HeNClerは、Heterophilous Node Clusteringの新しいアプローチである。
HeNClerは異種グラフコンテキストにおけるノードクラスタリングタスクの性能を大幅に向上させることを示す。
論文 参考訳（メタデータ） (2024-05-27T11:04:05Z) - Interpretable Multi-View Clustering Based on Anchor Graph Tensor Factorization [64.00146569922028]
アンカーグラフの分解に基づくマルチビュークラスタリング法では,分解行列に対する適切なクラスタ解釈性が欠如している。
複数のビューからアンカーグラフを合成するアンカーグラフテンソルを分解するために、非負のテンソル因子分解を用いることにより、この制限に対処する。
論文 参考訳（メタデータ） (2024-04-01T03:23:55Z) - An SDP-based Branch-and-Cut Algorithm for Biclustering [0.0]
本稿では,二クラスタリング問題に対する分枝切断アルゴリズムを提案する。
提案アルゴリズムは汎用的な解法よりも20倍大きな解法を解くことができることを示す。
論文 参考訳（メタデータ） (2024-03-17T21:43:19Z) - Deep Contrastive Graph Learning with Clustering-Oriented Guidance [61.103996105756394]
グラフ畳み込みネットワーク(GCN)は、グラフベースのクラスタリングを改善する上で大きな可能性を秘めている。
モデルはGCNを適用するために初期グラフを事前に推定する。
一般的なデータクラスタリングには,Deep Contrastive Graph Learning (DCGL)モデルが提案されている。
論文 参考訳（メタデータ） (2024-02-25T07:03:37Z) - MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity
and Degree Descent Criterion [0.6906005491572401]
スペクトルクラスタリングは、優れたパフォーマンス、簡単な実装、強力な適応性のために人気があり、魅力的です。
我々は,MeanCutを目的関数として提案し,非破壊グラフ分割の次数降下順で厳密に最適化する。
本アルゴリズムの有効性は,実世界のベンチマークによる検証と顔認識の適用によって実証される。
論文 参考訳（メタデータ） (2023-12-07T06:19:39Z) - Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。
ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
論文 参考訳（メタデータ） (2023-08-12T02:47:57Z) - Efficient Multi-view Clustering via Unified and Discrete Bipartite Graph
Learning [15.617206773324952]
本稿では,統一および離散二部グラフ学習(UDBGL)による効率的なマルチビュークラスタリング手法を提案する。
複数のビューからビュー固有の二部グラフを学習するために、アンカーベースのサブスペース学習が組み込まれている。
ラプラシア階数制約は、融合二部グラフが離散クラスタ構造を持つことを保証するために課される。
論文 参考訳（メタデータ） (2022-09-09T08:51:01Z) - Generalized Spectral Clustering for Directed and Undirected Graphs [4.286327408435937]
本稿では、有向グラフと無向グラフの両方に対処できる一般化スペクトルクラスタリングフレームワークを提案する。
我々のアプローチは、グラフ関数の一般化されたディリクレエネルギーとして導入する新しい函数のスペクトル緩和に基づいている。
また、グラフ上の自然ランダムウォークの反復パワーから構築された正規化尺度の実用的なパラメトリゼーションを提案する。
論文 参考訳（メタデータ） (2022-03-07T09:18:42Z) - Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
マルチビュークラスタリングのための効率的かつ効率的なグラフ学習モデルを提案する。
本手法はテンソルシャッテンp-ノルムの最小化により異なるビューのグラフ間のビュー類似性を利用する。
提案アルゴリズムは時間経済であり,安定した結果を得るとともに,データサイズによく対応している。
論文 参考訳（メタデータ） (2021-08-15T13:14:28Z) - Multilayer Clustered Graph Learning [66.94201299553336]
我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。
実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。
クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
論文 参考訳（メタデータ） (2020-10-29T09:58:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。