Large-scale spectral clustering using diffusion coordinates on landmark-based bipartite graphs

Khiem Pham, Guangliang ChenNAACL 2018

TL;DR

This paper introduces a novel, scalable spectral clustering algorithm called Landmark-based Bipartite Diffusion Maps (LBDM). LBDM leverages a bipartite graph constructed between the data and a small set of landmarks, combined with diffusion maps, to efficiently capture global data geometry for clustering, outperforming existing methods in terms of both accuracy and speed on benchmark datasets.

What Problem Does This Paper Address?

Spectral clustering is a powerful technique for uncovering complex data structures, but its computational cost, particularly the need to compute and factorize a large similarity matrix, makes it impractical for large datasets. While many scalable methods exist, they often struggle with normalized spectral clustering or are sensitive to approximations. This paper aims to bridge this gap by developing a computationally efficient yet accurate spectral clustering method that can handle large-scale data by intelligently using a small set of landmarks.

Methods

The core of LBDM lies in constructing a bipartite graph between the original data points ($X$) and a selected set of landmarks ($Y$). This graph is weighted using an affinity matrix ($A$) derived from a similarity function between $X$ and $Y$. The key innovation is the application of diffusion maps to this bipartite graph. By simulating a random walk on this graph and computing "diffusion coordinates" at various time steps ($\alpha$), the algorithm captures the global geometry of the data at different scales. These diffusion coordinates, derived efficiently from the affinity matrix $A$, are then used as a low-dimensional embedding for clustering, typically with k-means. The method offers flexibility by allowing different strategies for using these coordinates depending on whether the diffusion time step ($\alpha$) is even or odd, and whether to cluster the data directly or via the landmarks.

Datasets

The paper evaluates LBDM on six standard benchmark datasets:

  • usps: handwritten digits (9,298 samples, 256 features, 10 classes)
  • pendigits: handwritten digits (10,992 samples, 16 features, 10 classes)
  • letter: character recognition (20,000 samples, 16 features, 26 classes)
  • protein: protein localization (24,387 samples, 357 features, 3 classes)
  • shuttle: sensor data (58,000 samples, 9 features, 7 classes)
  • mnist: handwritten digits (70,000 samples, 784 features, 10 classes)

These datasets were merged from training and testing parts for an unsupervised clustering setting.

Key Insights and Ideas

  • Landmarks as Proxies for Global Geometry: The paper demonstrates that a small set of carefully chosen landmarks, when used in conjunction with a bipartite graph and diffusion maps, can effectively capture the global structure of a large dataset, bypassing the need for the full similarity matrix.
  • Diffusion Coordinates on Bipartite Graphs: The core idea of using diffusion maps on a bipartite graph is novel. It allows for a principled way to generate informative embeddings that reflect connectivity at various scales, even when the underlying data structure is complex.
  • Flexibility with Diffusion Time ($\alpha$): The algorithm's behavior changes with the diffusion time step ($\alpha$). Even $\alpha$ leads to independent clustering of data and landmarks, while odd $\alpha$ necessitates co-clustering. This flexibility allows tailoring the approach to different data characteristics.
  • Scalability through Matrix Operations: By deriving diffusion coordinates directly from the $n \times m$ affinity matrix ($A$) and its SVD, the method avoids the $n \times n$ similarity matrix, achieving significant computational gains.

Key Results

  • Accuracy: LBDM, particularly the LBDM(2,Y) variant (direct clustering with even $\alpha$), achieved the highest accuracy on three out of six datasets (usps, protein, mnist) and showed very stable performance across all datasets. It generally outperformed other scalable methods like KASP, LSC, and cSPEC.
  • Speed: LBDM(2,Y) and KASP were among the fastest methods. LBDM(2,Y) achieved competitive accuracy with significantly lower runtime compared to methods like plain Ncut.
  • Parameter Sensitivity: The method showed good robustness to parameter choices. Increasing the number of landmarks ($m$) generally improved accuracy, while increasing the number of nearest landmarks ($s$) had a less pronounced effect. The diffusion time ($\alpha$) also showed potential to further improve accuracy, demonstrating the power of diffusion maps.
  • Text Data Performance: When adapted to document clustering (treating terms as landmarks), LBDM significantly improved clustering accuracy on text datasets (TDT2, Reuters21578) compared to Dhillon's original co-clustering method, especially for small diffusion times.

Limitations and Future Work

  • Landmark Selection: While the paper mentions methods like uniform sampling or k-means for landmark selection, the optimal strategy for landmark selection is not deeply explored.
  • Parameter Tuning: Although the paper studies parameter sensitivity, finding optimal values for $m$, $s$, and $\alpha$ might still require experimentation for specific applications.
  • Future Work: The authors suggest that their work extends Dhillon's (2001) co-clustering by allowing $\alpha=0$ (which corresponds to Dhillon's embedding). They also note that for even $\alpha$, the diffusion coordinates for $X$ and $Y$ can be used separately, implying potential for further specialized applications. The paper also hints at the possibility of using other values of $p$ (embedding dimension) beyond $k-1$.

Summary updated

BibTeX
@inproceedings{pham2018large,
  author = {Khiem Pham and Guangliang Chen},
  title = {{Large-scale spectral clustering using diffusion coordinates on landmark-based bipartite graphs}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2018},
}
Figure