One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering
- URL: http://arxiv.org/abs/2305.07386v1
- Date: Fri, 12 May 2023 11:27:20 GMT
- Title: One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering
- Authors: Si-Guo Fang, Dong Huang, Chang-Dong Wang, Jian-Huang Lai
- Abstract summary: We show 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 criterion with normalized constraints, and theoretically prove its equivalence to a trace problem.
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.
- Score: 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.
Related papers
- HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
HeNCler is a novel approach for Heterophilous Node Clustering.
We show that HeNCler significantly enhances performance in node clustering tasks within heterophilous graph contexts.
arXiv Detail & Related papers (2024-05-27T11:04:05Z) - Interpretable Multi-View Clustering Based on Anchor Graph Tensor Factorization [64.00146569922028]
Multi-view clustering methods based on anchor graph factorization lack adequate cluster interpretability for the decomposed matrix.
We address this limitation by using non-negative tensor factorization to decompose an anchor graph tensor that combines anchor graphs from multiple views.
arXiv Detail & Related papers (2024-04-01T03:23:55Z) - An SDP-based Branch-and-Cut Algorithm for Biclustering [0.0]
We present a tailored branch-and-cut algorithm for biclustering problems.
We show that the proposed algorithm can solve instances 20 times larger than those handled by general-purpose solvers.
arXiv Detail & Related papers (2024-03-17T21:43:19Z) - Deep Contrastive Graph Learning with Clustering-Oriented Guidance [61.103996105756394]
Graph Convolutional Network (GCN) has exhibited remarkable potential in improving graph-based clustering.
Models estimate an initial graph beforehand to apply GCN.
Deep Contrastive Graph Learning (DCGL) model is proposed for general data clustering.
arXiv Detail & Related papers (2024-02-25T07:03:37Z) - MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity
and Degree Descent Criterion [0.6906005491572401]
spectral clustering is popular and attractive due to the remarkable performance, easy implementation, and strong adaptability.
We propose MeanCut as the objective function and greedily optimize it in degree descending order for a nondestructive graph partition.
The validity of our algorithm is demonstrated by testifying on real-world benchmarks and application of face recognition.
arXiv Detail & Related papers (2023-12-07T06:19:39Z) - Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
We present a probabilistic model based on non-negative matrix factorization which unifies clustering and simplification.
By relaxing the hard clustering to a soft clustering, our algorithm relaxes potentially hard clustering problems to a tractable ones.
arXiv Detail & Related papers (2023-08-12T02:47:57Z) - Efficient Multi-view Clustering via Unified and Discrete Bipartite Graph
Learning [15.617206773324952]
This paper presents an efficient multi-view clustering approach via unified and discrete bipartite graph learning (UDBGL)
An anchor-based subspace learning is incorporated to learn the view-specific bipartite graphs from multiple views.
The Laplacian rank constraint is imposed to ensure that the fused bipartite graph has discrete cluster structures.
arXiv Detail & Related papers (2022-09-09T08:51:01Z) - Generalized Spectral Clustering for Directed and Undirected Graphs [4.286327408435937]
We present a generalized spectral clustering framework that can address both directed and undirected graphs.
Our approach is based on the spectral relaxation of a new functional that we introduce as the generalized Dirichlet energy of a graph function.
We also propose a practical parametrization of the regularizing measure constructed from the iterated powers of the natural random walk on the graph.
arXiv Detail & Related papers (2022-03-07T09:18:42Z) - Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
We propose an effective and efficient graph learning model for multi-view clustering.
Our method exploits the view-similar between graphs of different views by the minimization of tensor Schatten p-norm.
Our proposed algorithm is time-economical and obtains the stable results and scales well with the data size.
arXiv Detail & Related papers (2021-08-15T13:14:28Z) - Multilayer Clustered Graph Learning [66.94201299553336]
We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph.
Experiments show that our method leads to a clustered clusters w.r.t.
We learn a clustering algorithm for solving clustering problems.
arXiv Detail & Related papers (2020-10-29T09:58:02Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.