Randomized Spectral Clustering for Large-Scale Multi-Layer Networks

Wenqing Su, Xiao Guo, Xiangyu Chang, Ying YangStat. Comput 2025 · DOI

TL;DR

This paper introduces an efficient randomized spectral clustering algorithm (RSC) for analyzing large, complex multi-layer networks. By combining random sampling and random projection, RSC significantly reduces computational cost and memory requirements, making it feasible to analyze networks with millions of nodes, while maintaining competitive clustering accuracy.

What Problem Does This Paper Address?

Modern data is increasingly represented as multi-layer networks, where multiple types of relationships exist between the same set of entities. These networks are growing rapidly in size (millions of nodes and edges), posing a significant computational challenge for traditional analysis methods, particularly community detection. Existing spectral clustering methods, while effective, become computationally prohibitive for large-scale networks due to the high dimensionality and dense matrices involved in eigen-decomposition. This paper aims to bridge this gap by developing a randomized algorithm that is both computationally efficient and accurate for large multi-layer networks.

Methods

The core of the proposed method, Randomized Spectral Clustering (RSC), builds upon existing spectral clustering techniques for multi-layer networks, specifically the approach of using the sum of squared adjacency matrices. RSC introduces two key randomization strategies:

  • Random Sampling: To reduce the computational burden of squaring adjacency matrices, each layer's adjacency matrix ($A_l$) is sparsified by randomly sampling its elements. This creates a sparser matrix ($\tilde{A}_l$) that retains essential information while being more manageable.
  • Random Projection: To accelerate the eigen-decomposition of the aggregated (sum of squared) matrices, random projection is employed. This technique, specifically using randomized block Krylov subspace methods, allows for an approximation of the eigenspace without computing the full dense matrix, drastically reducing computational complexity.

The algorithm also incorporates a bias-correction step to account for potential statistical biases introduced by the squaring and sampling operations. Finally, k-means clustering is applied to the computed eigenvectors to identify the communities.

Datasets

The paper evaluates the proposed algorithm on seven real-world multi-layer networks, ranging in size from thousands to millions of nodes. These datasets include:

  • European email network
  • Yeast landscape network
  • Home genetic network
  • MoscowAthletics 2013 social network
  • Cannes2013 social network
  • YouTube social network
  • Stack overflow network

The paper also uses simulated data generated from multi-layer Stochastic Block Models (SBMs) and Stochastic Co-Block Models (ScBMs) to theoretically analyze the algorithm's performance and misclassification error rates under controlled conditions.

Key Insights and Ideas

  • Randomization as a Scalability Solution: The paper demonstrates that randomization techniques, specifically random sampling and projection, are not just theoretical curiosities but practical tools for achieving significant computational speedups in spectral clustering for large networks.
  • Bridging Theory and Practice: The theoretical analysis shows that, under certain conditions, the randomization introduced by RSC does not substantially deteriorate the misclassification error rate compared to non-randomized methods. This is a crucial finding, as it validates the trade-off between computational efficiency and accuracy.
  • Handling Heterogeneity: The use of squared adjacency matrices, as in the baseline method, is shown to be effective in handling heterogeneity across network layers (e.g., some layers being assortative and others disassortative). The randomized approach inherits this benefit.
  • Practical Implementation: The development of an R package (MLRclust) makes the proposed algorithm readily accessible to the research community, facilitating its adoption and further exploration.

Key Results

  • Computational Efficiency: RSC significantly outperforms the standard spectral clustering (SC) algorithm in terms of computational time and memory usage. For networks with millions of nodes, SC becomes infeasible due to memory overflow, while RSC can process them rapidly (e.g., in under a minute). RSC is shown to be up to 30 times faster than SC for networks with thousands of nodes.
  • Clustering Accuracy: The misclassification rates of RSC are shown to be very close to those of SC, especially as network size and density increase. The performance of RSC generally improves with higher sampling rates and power parameters.
  • Theoretical Guarantees: The paper provides theoretical bounds on the misclassification error rate of RSC under multi-layer SBMs, showing that the randomization does not significantly degrade performance under specific sparsity regimes.

Limitations and Future Work

  • Information Loss: The authors acknowledge that random sampling might lead to some information loss, which could result in slightly worse bounds compared to non-randomized methods in certain regimes.
  • Generalization to Other Methods: The paper suggests that generalizing the methodology and theory to other community detection methods, such as tensor-based approaches for multi-layer networks, would be an interesting future direction.
  • Co-clustering Extension: The paper details an extension of the RSC algorithm to spectral co-clustering for directed multi-layer networks, indicating ongoing research in this area.

Summary updated

BibTeX
@article{su2025randomized,
  author = {Wenqing Su and Xiao Guo and Xiangyu Chang and Ying Yang},
  title = {{Randomized Spectral Clustering for Large-Scale Multi-Layer Networks}},
  journal = {Stat. Comput.},
  year = {2025},
  doi = {10.1007/s11222-025-10723-6},
}
Figure