Abstract
Graph-based multi-view clustering has received considerable attention due to its ability to explore neighborhood relationships among data points from multiple views. Although these methods have achieved impressive performance, most merely exploit first-order proximity, leading to inadequate information exploration and a degraded capacity for multi-view representation. We propose High-order Graph Fusion for Multi-view Clustering (HCDMC), which constructs high-order graphs from first-order and second-order proximity via a novel implicit weight learning paradigm. By incorporating diversity regularization and a connectivity constraint, HCDMC obtains clustering labels directly without post-processing. Extensive experiments on six datasets demonstrate its superior performance compared to state-of-the-art algorithms.
Introduction
Multi-view clustering (MVC) aims to group data points described by multiple feature sets—for example, a video represented by visual frames, audio tracks, and subtitles. While graph-based MVC is popular for capturing complex data structures, existing methods often suffer from a "short-sighted" perspective by only considering first-order proximity (direct neighbors). This makes them sensitive to noise and prevents them from capturing global structures. Furthermore, many methods require unstable post-processing steps like k-means to generate final clusters.
Methodology
The proposed HCDMC algorithm addresses these challenges through three primary innovations:
- High-Order Graph Construction: For each view, the algorithm builds a first-order proximity graph and a second-order graph (representing shared neighbors). These are fused into a "high-order" graph, allowing the model to recognize that points sharing many neighbors likely belong together, even if not directly connected.
- Implicit Weight Learning: Instead of manual tuning, HCDMC automatically assigns weights to first-order and second-order information based on reconstruction loss, enhancing robustness to noise across different views.
- Diversity Regularization (HSIC): Using the Hilbert-Schmidt Independence Criterion (HSIC), the model ensures that different views contribute unique, complementary information.
- Direct Clustering via Laplacian Rank: By imposing a rank constraint on the Laplacian matrix of the consensus graph, the algorithm ensures exactly $k$ connected components, outputting cluster labels directly.
Experimental Evaluation
HCDMC was evaluated on six diverse real-world datasets: Yale (faces), WebKB (webpages), MSRC-v1 (scenes), LGG & BRCA (biomedical/cancer data), and HW2sources (handwritten digits).
Key Results
- Superior Accuracy: HCDMC achieved the highest Accuracy (ACC), Normalized Mutual Information (NMI), and Purity across nearly all datasets. On WebKB, it reached an ACC of 0.7635, outperforming the next best state-of-the-art method.
- Structural Clarity: The method produces cleaner "block-diagonal" structures in similarity matrices, indicating distinct, low-noise clusters compared to competing algorithms.
- Efficient Convergence: The iterative optimization process typically converges within 20 iterations, ensuring computational predictability.
Conclusion and Future Work
HCDMC provides a robust framework for multi-view clustering by leveraging high-order relationships and direct label output. While it demonstrates state-of-the-art performance, its $O(mn^3)$ complexity poses challenges for massive datasets. Future research will focus on incorporating "anchor graph" techniques to achieve linear complexity, facilitating large-scale industrial applications.
Summary updated