Source-linked AI summary
Effective and Efficient Graph Learning for Multi-view Clustering
Quanxue Gao, Wei Xia, Xinbo Gao, Xiangdong Zhang, Qin Li, Dacheng Tao
TL;DR
Existing graph-based multi-view clustering methods can be costly, poorly scalable, and require post-processing for clustering. This paper uses anchor-based bipartite graphs, tensor Schatten p-norm minimization, adaptive weighting, and connectivity constraints, outperforming state-of-the-art competitors in efficiency.
Problem
Existing methods incur costly graph construction and eigendecomposition, scale poorly, require post-processing, and inadequately capture graph structure or target rank.
Method
The method learns an adaptive, connectivity-constrained consensus graph from anchor-based bipartite graphs using tensor Schatten p-norm minimization.
Results
The method outperforms state-of-the-art competitors in efficiency and is suitable for large-scale multi-view clustering.
Takeaways & Limitations
Its K-connected components directly provide clustering results without post-processing, while the reduced complexity supports large-scale data.
Takeaways & Limitations
The paper is motivated by existing methods whose graph construction and Laplacian eigendecomposition are costly and whose learned graphs may lack K-connected components.
Abstract
from arXiv · showhide
Despite the impressive clustering performance and efficiency in characterizing both the relationship between data and cluster structure, existing graph-based multi-view clustering methods still have the following drawbacks. They suffer from the expensive time burden due to both the construction of graphs and eigen-decomposition of Laplacian matrix, and fail to explore the cluster structure of large-scale data. Moreover, they require a post-processing to get the final clustering, resulting in suboptimal performance. Furthermore, rank of the learned view-consensus graph cannot approximate the target rank. In this paper, drawing the inspiration from the bipartite graph, we propose an effective and efficient graph learning model for multi-view clustering. Specifically, our method exploits the view-similar between graphs of different views by the minimization of tensor Schatten p-norm, which well characterizes both the spatial structure and complementary information embedded in graphs of different views. We learn view-consensus graph with adaptively weighted strategy and connectivity constraint such that the connected components indicates clusters directly. Our proposed algorithm is time-economical and obtains the stable results and scales well with the data size. Extensive experimental results indicate that our method is superior to state-of-the-art methods.
1 INTRODUCTION
The paper proposes a scalable graph-learning model for multi-view clustering that uses bipartite graphs and tensor Schatten p-norm minimization to capture cross-view structure. Its adaptive, connectivity-constrained consensus graph directly yields clusters while reducing computational complexity for large-scale data.
- Motivation: Existing graph-based methods face burdens from graph construction and Laplacian eigen-decomposition, depend on predefined graphs, and often require post-processing.These limitations motivate learning the graph adaptively while avoiding full-scale graph construction and separate clustering procedures.
- Proposed model: The method constructs an n × m bipartite graph, with m ≪ n anchors, to avoid constructing the full n × n graph.This design targets scalable multi-view clustering by reducing the graph size before learning cross-view structure.
- Proposed model: Tensor Schatten p-norm minimization exploits view similarity and helps the learned view-consensus graph approximate the target rank.The method is intended to capture complementary and high-order information across graphs from different views.
- Proposed model: The learned view-similar graph has K-connected components, adaptively accounts for view importance, and directly provides clustering results without post-processing.Connected components indicate clusters, eliminating a separate step such as k-means.
- Efficiency: The algorithm reduces main computational complexity from O(n3 + V n2d) to O(m2n + V nmd) compared with ETLMSC.This reduction makes the method time-economical and suitable for large-scale multi-view data clustering.
2 METHODOLOGY
The methodology replaces expensive global-graph construction and post-processing with anchor-based bipartite graph learning, connectivity constraints, and tensor Schatten p-norm regularization. An ALM-based alternating optimization efficiently learns view-specific graphs, errors, auxiliary variables, and adaptive view weights.
- Limitations: Existing graph-based learning constructs n×n graphs and performs Laplacian eigen-decomposition, requiring O(V n2d) and O(n3) complexity while lacking K-connected components for direct clustering.These costs hinder large-scale data and necessitate post-processing, which can produce suboptimal graphs and clustering results.
- Bipartite graph learning: The proposed model constructs n×m bipartite graphs between data points and m ≪n anchors, reducing graph-construction complexity from O(V n2d) to O(V nmd).The anchor-based representation replaces the n×n global graph while retaining relationships useful for clustering.
- Connectivity constraint: A rank-related connectivity constraint is approximated through eigenvalue minimization so the learned graph has K connected components indicating clusters directly.The method uses the relationship between the zero-eigenvalue multiplicity and connected components, with the constraint rank(eLF(v)) = n + m −K.
- Multi-view consensus: To capture differences and complementary information across views while approximating the target rank, the method replaces the first regularization term with a tensor Schatten p-norm.The tensor Schatten p-norm is defined for 0 < p ≤1 using singular values across tensor slices.
- Optimization algorithm: An augmented-Lagrangian formulation alternates updates for P, C(v), E(v), J, and ξ(v), using efficient singular-vector computation with complexity O(V nm + m2n).The procedure is summarized in Algorithm 1 and outputs a graph C with K-connected components.
10 end
The method constructs view-specific graphs and then optimizes the model iteratively. It directly obtains K clusters from the connectivity of C = PV, with complexity dominated by anchor-based operations because m ≪ n.
- Clustering output: The final clustering directly achieves K clusters from the connectivity of C = PV.The procedure then returns the clustering results.
- Method stages: The method has two stages: constructing graphs {B(v)}V and optimizing by iteratively solving Eq. (8).The graph-construction stage takes O(V nmd + V nm log(m)) time.
- Optimization complexity: Iterative optimization updates C(v), J, E(v), and P with complexities O(V nmK + V nm log(m)), O(V nm log(V n) + V 2mn), O(V nm), and O(V nm + m2n), respectively.Here, K and t denote the number of clusters and iterations, while m ≪ n.
3 EXPERIMENTS
Experiments across six datasets and seven clustering metrics show that the proposed method consistently outperforms competing approaches, including on large-scale data. Ablation analyses further show that performance depends on p and anchor proportion, while the learned graph recovers the target connected components directly.
- Overall comparison: The proposed method and ETLMSC outperform most competing methods by exploiting complementary and high-order information across views.The paper attributes the advantage to modeling information embedded in graphs from different views.
- Overall comparison: On MSRC-v5, the proposed method improves over SFMC by 18.5% in ACC, 26.8% in NMI, 18.5% in Purity, 33.3% in PER, 20.8% in REC, 27.6% in F-score, and 32.6% in ARI.These comparisons span all seven reported metrics.
- Large-scale datasets: On large-scale datasets, several competitors encounter out-of-memory errors, whereas the proposed method consistently and significantly outperforms the partial competitor set.The experiments use 37 anchors on Reuters and 400 anchors on NUS-WID.
- Effect of the number of anchors: Performance fluctuates with anchor proportion, peaking at 0.7 on MSRC-v5 and 0.3 on Handwritten4; experiments therefore use a uniform proportion of 0.5.The metric curves are not monotonically increasing, so using more anchors is not always beneficial.
- Graph Visualization: On MSRC-v5, the learned view-consensus graph has exactly 7 connected components despite unclear components in the five input graphs.This supports direct characterization of the dataset’s cluster structure.
4 CONCLUSION
The paper proposes an effective and efficient graph-learning method for multi-view clustering. It uses a tensor Schatten p-norm to capture spatial and complementary information while computing an n × m graph with m ≪ n instead of an n × n graph.
- 4 CONCLUSION: The method learns a multi-view graph by minimizing a proposed tensor Schatten p-norm.The norm characterizes spatial structure and complementary information across different views.
- 4 CONCLUSION: The tensor Schatten p-norm captures spatial structure and complementary information embedded in different views.
- 4 CONCLUSION: The method is time-economical because it computes an n × m graph with m ≪ n rather than an n × n graph.Here, n and m denote the numbers of data points and anchors, respectively.