Abstract
Multi-view clustering (MVC) is a critical task in data mining, yet existing methods often struggle with noise sensitivity, the neglect of structural topology, and cubic computational complexity. This paper presents Scalable Multi-view Clustering with Graph Filtering (SMC), a unified framework designed to address these challenges. By treating data features as signals on a graph and applying a low-pass graph filter via first-order Taylor expansion, SMC effectively removes high-frequency noise in linear time. Furthermore, a novel importance-based anchor sampling strategy ensures that the structural skeleton of the graph is preserved. Experimental results across multiple benchmarks demonstrate that SMC achieves state-of-the-art accuracy while providing up to a 1000x speedup over deep learning-based competitors.
Introduction
In modern data analysis, objects are frequently characterized by multiple "views." For instance, a web page might be described by its text content, its hyperlink structure, and the anchor text used by other pages. Multi-view clustering seeks to leverage these diverse perspectives to uncover underlying patterns that a single view might miss.
Despite the potential of MVC, three primary hurdles have limited its application to large-scale, real-world datasets:
- Noise Sensitivity: Raw features are often corrupted by noise, which can obscure the true cluster structure.
- Topological Neglect: Many algorithms treat views as independent feature vectors, ignoring the rich relational (graph) information between samples.
- Computational Scalability: High-performance methods, such as spectral or subspace clustering, typically scale at $O(n^3)$, making them computationally prohibitive for datasets with millions of samples.
SMC addresses these issues by combining graph signal processing with anchor-based subspace learning to create a framework that is both robust and efficient.
Methodology
The SMC framework is built upon three core technical pillars designed to optimize both the quality of the data representation and the speed of the clustering process.
1. Graph Filtering as Feature Smoothing
SMC treats the features of each view as signals residing on a graph. To mitigate the impact of noise, the authors apply a low-pass graph filter. This filter suppresses "high-frequency" components—the sharp, erratic differences between neighboring nodes—resulting in a smoother, more "clustering-friendly" feature space.
To maintain efficiency, the authors avoid the $O(n^3)$ matrix inversion typically required for graph filtering. Instead, they utilize a first-order Taylor series expansion to approximate the filter. This allows the model to capture structural information and aggregate features from neighboring nodes in linear time ($O(n)$).
2. Importance-Based Anchor Sampling
To further reduce complexity, SMC employs anchor-based subspace clustering. Rather than constructing a full $n \times n$ similarity matrix, the model learns a mapping to a much smaller set of $m$ "anchors" ($m \ll n$).
While traditional methods often use K-means to select these anchors, SMC introduces an importance-based sampling strategy for graph data. This strategy assigns higher selection probabilities to nodes with higher degrees (more connections). By prioritizing these structural hubs, the anchors more accurately represent the "skeleton" of the graph compared to uniform or centroid-based sampling.
3. Linear-Time Subspace Learning
By combining the smoothed features and the representative anchors, SMC learns an $n \times m$ transition matrix. This matrix captures the relationships between all samples and the selected anchors. The final clustering is performed on this reduced representation, ensuring the entire pipeline remains linear with respect to the number of samples.
Experimental Evaluation
The authors evaluated SMC against a variety of state-of-the-art methods on two distinct types of benchmarks: multi-view feature datasets (e.g., Handwritten, Caltech) and attributed graph datasets (e.g., ACM, DBLP, IMDB).
Performance and Accuracy
SMC consistently outperformed existing methods in clustering accuracy. On the Handwritten digits dataset, SMC achieved an accuracy (ACC) of 96.20%, surpassing the previous state-of-the-art, SMVSC (94.30%). The results suggest that the graph filtering step acts as a powerful pre-conditioner, increasing the spatial separation between different clusters.
Efficiency and Scalability
The most significant advantage of SMC is its computational speed. On the DBLP dataset, SMC completed the clustering task in just 4.92 seconds. In contrast, O2MAC, a prominent deep learning-based competitor, required 4,725.36 seconds. This represents a 1000x speedup, demonstrating that SMC can achieve high-quality results without the need for expensive iterative training or backpropagation.
Discussion and Insights
- The Power of Smoothing: A key insight from the study is that graph filtering does more than just reduce noise; it effectively aggregates information from $k$-th order neighbors. This allows a mathematically "shallow" model to capture long-distance relationships that are usually the domain of deep Graph Neural Networks (GNNs).
- Iteration-Free Design: Unlike deep learning approaches that are sensitive to initialization and require many epochs to converge, SMC relies on closed-form solutions and direct sampling. This makes the framework exceptionally stable and easy to deploy.
Conclusion and Future Work
SMC provides a scalable and robust solution for multi-view clustering by bridging the gap between graph signal processing and subspace learning. While highly effective, the authors note that the performance is sensitive to the filter order $k$ and the parameter $\mu$, which prevents "over-smoothing." Future research may explore automated parameter tuning and the extension of this linear-time framework to dynamic, evolving graphs where node relationships change over time.
Summary updated