Source-linked AI summary
Multi-graph Fusion for Multi-view Spectral Clustering
Zhao Kang, Guoxin Shi, Shudong Huang, Wenyu Chen, Xiaorong Pu, Joey Tianyi Zhou, Zenglin Xu
TL;DR
Existing multi-view spectral clustering methods leave graph fusion and explicit cluster-structure learning insufficiently addressed, while graph learning and spectral clustering are often not jointly optimized. The paper proposes simultaneous graph fusion and spectral clustering, and experiments on four widely used data sets confirm the proposed method’s superiority.
Problem
Existing methods inadequately address effective graph fusion and explicit cluster-structure learning, with separate graph learning and spectral clustering procedures that are not jointly optimized.
Method
The proposed multi-view spectral clustering model simultaneously fuses graphs into a consensus graph and performs spectral clustering, preserving explicit cluster structure.
Results
Experiments on four widely used data sets confirm the superiority of the proposed method, with the consensus graph and graph structure improving clustering quality.
Takeaways & Limitations
The fusion graph approximates each individual view’s original graph while maintaining an explicit cluster structure.
Takeaways & Limitations
Failing to account for flexible local manifold structures across views can lead to suboptimal clustering.
Abstract
from arXiv · showhide
A panoply of multi-view clustering algorithms has been developed to deal with prevalent multi-view data. Among them, spectral clustering-based methods have drawn much attention and demonstrated promising results recently. Despite progress, there are still two fundamental questions that stay unanswered to date. First, how to fuse different views into one graph. More often than not, the similarities between samples may be manifested differently by different views. Many existing algorithms either simply take the average of multiple views or just learn a common graph. These simple approaches fail to consider the flexible local manifold structures of all views. Hence, the rich heterogeneous information is not fully exploited. Second, how to learn the explicit cluster structure. Most existing methods don't pay attention to the quality of the graphs and perform graph learning and spectral clustering separately. Those unreliable graphs might lead to suboptimal clustering results. To fill these gaps, in this paper, we propose a novel multi-view spectral clustering model which performs graph fusion and spectral clustering simultaneously. The fusion graph approximates the original graph of each individual view but maintains an explicit cluster structure. Experiments on four widely used data sets confirm the superiority of the proposed method.
1. Introduction
Multi-view spectral clustering must address both how to fuse view-specific graphs and how to preserve explicit cluster structure during graph learning. GFSC jointly learns, fuses, and clusters graphs, while its fusion graph approximates individual-view graphs and maintains cluster structure.
- Motivation: Multi-view data provides complementary information, but simply concatenating features may not outperform clustering each view separately.
- Motivation: Spectral clustering is sensitive to graph perturbations, so inaccurate affinity graphs can produce inferior clustering accuracy.
- Limitations: Graph construction and spectral clustering are often performed separately, so the learned graph may not be ideal for the subsequent clustering task.
- Limitations: Existing approaches may average view graphs or learn a common graph, which fails to capture discriminative properties and flexible local structures across views.
- Proposed approach: GFSC performs graph fusion and spectral clustering simultaneously; its fusion graph approximates each view's graph while retaining an explicit cluster structure.
- Results: Experiments on four widely used data sets confirm the proposed method's superiority compared with state-of-the-art methods.
2. Multi-view Spectral Clustering Revisited
Multi-view spectral clustering represents each view with a graph and seeks a shared cluster indicator, but common fusion strategies do not fully exploit heterogeneous information.
- Each view provides a data matrix and nonnegative adjacency graph, whose Laplacian is formed as Lv = Dv − Zv.
- The standard formulation assumes one cluster indicator matrix F is shared across all views, with every graph contributing equally to F.
- Averaging graphs or enforcing a common F can fail because views capture different structures and complementary information.
- Linear graph combinations also assume relationships are linearly related and are sensitive to the weights assigned to each graph.
- The paper proposes integrating the graphs while incorporating an explicit cluster structure into the consensus graph.
3. Proposed Multi-graph Fusion for Multi-view Spectral Clustering
The proposed GFSC model learns view-specific graphs, a weighted consensus graph, and cluster structure jointly rather than treating graph fusion and spectral clustering separately.
- Graph Fusion: GFSC aggregates view-specific graphs into a consensus graph S while distinguishing the contributions of different views.
- Graph Fusion: The fusion assumes each view graph is a perturbation of S and assigns larger weights to graphs closer to the consensus.
- Graph Fusion: Dynamic graph weighting reduces the adverse effect of noisy views during fusion.
- Structured Graph Learning: The structured learning term encourages S to have k connected components, linking graph structure directly to spectral clustering.
- Structured Graph Learning: A single objective jointly performs graph learning, graph fusion, and spectral clustering through a regularized consensus graph.
- Properties: The framework learns graphs automatically, uses clustering to guide graph construction, and iteratively improves the clustering result.
4. Optimization of Problem (9)
GFSC optimizes its coupled variables with alternating updates for view graphs, the consensus graph, cluster indicators, and view weights.
- The coupled variables are solved using an alternating iterative strategy.
- With F and S fixed, each view graph Zv is updated independently.
- With F and the view graphs fixed, the consensus graph S is updated using distances between rows of F.
- With Zv and S fixed, F is obtained from the k eigenvectors of L associated with the k smallest eigenvalues.
- The algorithm stops after 200 iterations or when the relative change of S falls below 10^-3.
- Updating Zv and F each costs about O(n^3), while skinny SVD and sampling-based methods are suggested for acceleration but not used experimentally.
REPEAT
The supplied passage lists the alternating GFSC update steps and identifies the data-set information table.
- Algorithm 1 updates each view graph, the consensus graph S, the cluster indicator F, and the view weights wv until convergence.
- Table 1 reports information about the data sets, including the number of features.
5. Experiments
Experiments evaluate GFSC on four multi-view datasets using clustering metrics and comparisons with single-view, multi-view, and graph-learning baselines. The results support view differentiation, graph fusion, and explicit graph-structure learning.
- Datasets: Four datasets—BBC, Reuters2, Digits, and Caltech20—are used for evaluation, covering text and image data.BBC and Reuters are text datasets; Digits and Caltech20 are image datasets.
- Evaluation metrics: Performance is evaluated using accuracy, normalized mutual information, and purity.The study compares clustering quality using these three metrics.
- Results: Different views produce different spectral-clustering results, confirming heterogeneous view information and motivating view differentiation.The experiments state that views should be differentiated when building a multi-view learning model.
- Results: Naively averaging view graphs can deteriorate performance, whereas GFSC often outperforms individual-view spectral clustering and SC(Ave).The paper attributes GFSC’s stronger performance to learning a more accurate graph with graph fusion and weighting.
- Results: GFSC consistently outperforms GF, demonstrating the importance of considering graph structure during clustering.GF performs spectral clustering separately after obtaining the fused graph, while GFSC incorporates graph structure in the model.
- Baseline comparisons: GFSC beats k-means-based methods, AMGL, Co-train, Co-reg, and most state-of-the-art multi-view subspace clustering methods on Acc, NMI, and Purity.The comparisons include KM, MVKKM, RMKMC, MSPL, AMGL, Co-train, Co-reg, DiMSC, MVSC, and IMVSC.
6. Conclusion
The conclusion presents GFSC as a unified multi-view spectral clustering framework that fuses graphs, weights their contributions, and models consensus-graph structure jointly. Alternating optimization and benchmark experiments support the effectiveness of these strategies.
- 6. Conclusion: GFSC fuses multiple graphs into a consensus graph instead of relying on averaged graphs for spectral clustering.The proposed strategy is designed to integrate the graphs into a consensus representation.
- 6. Conclusion: A parameter-free weighting scheme distinguishes the contributions of different graphs, while the consensus graph retains an explicit cluster structure.These design choices address graph fusion and cluster-structure modeling within the proposed method.
- 6. Conclusion: Graph learning, fusion, and spectral clustering are integrated into one framework and mutually boosted through alternating iterative optimization.Experiments on benchmark datasets verify the effectiveness of the proposed approach.
- 6. Conclusion: The results show that both the consensus graph and graph structure help improve clustering quality.The conclusion attributes the observed improvement to both components.