PaperlayerView exact revision on arXiv

Source-linked AI summary

Ultra-Scalable Spectral Clustering and Ensemble Clustering

Dong Huang, Chang-Dong Wang, Jian-Sheng Wu, Jian-Huang Lai, Chee-Keong Kwoh

arXiv:1903.01057v2cs.LGstat.ML

TL;DR

Large-scale spectral clustering is constrained by high computational and memory costs, especially under limited resources. The paper proposes U-SPEC and U-SENC using representative-based sparse graphs, transfer cuts, and ensemble integration; experiments report improved robustness and scalability over state-of-the-art methods.

  • Problem

    Conventional spectral clustering has huge time and space complexity, restricting its application to large-scale problems.

  • Method

    U-SPEC constructs a sparse affinity sub-matrix through hybrid representative selection and approximate K-nearest representatives, while U-SENC integrates multiple U-SPEC clusterers in an ensemble framework.

  • Results

    Experiments on ten large-scale datasets showed superiority over the state-of-the-art in clustering robustness and scalability.

  • Takeaways & Limitations

    The proposed algorithms support scalable and robust spectral or ensemble clustering for large-scale datasets.

  • Takeaways & Limitations

    On SF-2M, LSC-K cannot handle ≥1400 representatives and Nyström cannot handle ≥1200 because of memory bottlenecks.

Abstract

from arXiv · show

This paper focuses on scalability and robustness of spectral clustering for extremely large-scale datasets with limited resources. Two novel algorithms are proposed, namely, ultra-scalable spectral clustering (U-SPEC) and ultra-scalable ensemble clustering (U-SENC). In U-SPEC, a hybrid representative selection strategy and a fast approximation method for K-nearest representatives are proposed for the construction of a sparse affinity sub-matrix. By interpreting the sparse sub-matrix as a bipartite graph, the transfer cut is then utilized to efficiently partition the graph and obtain the clustering result. In U-SENC, multiple U-SPEC clusterers are further integrated into an ensemble clustering framework to enhance the robustness of U-SPEC while maintaining high efficiency. Based on the ensemble generation via multiple U-SEPC's, a new bipartite graph is constructed between objects and base clusters and then efficiently partitioned to achieve the consensus clustering result. It is noteworthy that both U-SPEC and U-SENC have nearly linear time and space complexity, and are capable of robustly and efficiently partitioning ten-million-level nonlinearly-separable datasets on a PC with 64GB memory. Experiments on various large-scale datasets have demonstrated the scalability and robustness of our algorithms. The MATLAB code and experimental data are available at https://www.researchgate.net/publication/330760669.

1 INTRODUCTION

Conventional spectral clustering is limited by quadratic-to-cubic computational and memory costs, motivating U-SPEC and U-SENC for scalable, robust clustering on large datasets.

  • O(N^2d) time and O(N^2) memory are required to construct conventional spectral clustering’s affinity matrix, followed by O(N^3) eigen-decomposition time.
  • 7450.58 GB of memory is required for a one-million-object affinity matrix stored with double-precision entries.
  • U-SPEC combines hybrid representative selection, approximate K-nearest representatives, sparse affinity construction, and transfer-cut partitioning.
  • U-SENC integrates multiple U-SPEC clusterers into an ensemble framework to enhance robustness while maintaining scalability.
  • Experiments on ten large-scale datasets showed U-SPEC and U-SENC were superior to state-of-the-art methods in clustering robustness and scalability.

2 RELATED WORK

Prior work addresses spectral-clustering cost through sparsification and sub-matrix approximations, while ensemble methods improve robustness but often remain inefficient for very large datasets.

  • Large-scale spectral clustering: Spectral clustering handles nonlinearly separable data but its O(N^3) time and O(N^2) space complexity restrict large-scale use.
  • Large-scale spectral clustering: Nyström and related sub-matrix methods avoid full affinity computation, but FastESC remains constrained by an O(Np) complexity bottleneck.
  • Large-scale spectral clustering: EulerSC achieves O(Ndkt) time but is limited to the positive Euler kernel and is not feasible for general similarity metrics.
  • Ensemble clustering: Ensemble clustering combines multiple base clusterings through co-occurrence, graph-partitioning, or median-partition approaches.
  • Ensemble clustering: Most existing ensemble methods are unsuitable for very large-scale applications because of efficiency bottlenecks.

3 PROPOSED FRAMEWORK

The proposed U-SPEC and U-SENC algorithms are described in Sections 3.1 and 3.2, respectively.

  • U-SPEC is described in Section 3.1.
  • U-SENC is described in Section 3.2.
  • The framework presents the two proposed algorithms in separate subsections.

3.1 Ultra-Scalable Spectral Clustering (U-SPEC)

U-SPEC combines hybrid representative selection, approximate K-nearest representative search, and bipartite-graph partitioning to scale spectral clustering. Its sparse affinity construction and transfer-cut stages reduce computation while retaining a representative set that better reflects data distribution than random selection.

  • U-SPEC overview: U-SPEC uses hybrid selection, coarse-to-fine nearest-representative approximation, sparse affinity construction, and bipartite graph partitioning.The method balances random and k-means selection, then uses transfer cut on the resulting graph.
  • Hybrid Representative Selection: Hybrid selection randomly samples p′ candidates, with p < p′ ≪ N, then applies k-means to obtain p representative centers.The paper suggests p′ may be several times larger than p, such as p′ = 10p.
  • Hybrid Representative Selection: The hybrid strategy reduces k-means selection complexity from O(Npdt) to O(p2dt) while better reflecting data distribution than random selection.It also requires much less computational cost than applying k-means to the entire dataset.
  • Approximation of K-Nearest Representatives: Sub-matrix construction is a key scalability bottleneck because an N × p affinity matrix requires O(Npd) time and O(Np) memory.For ten million objects and one thousand representatives, storing the sub-matrix alone requires 74.51GB.
  • Approximation of K-Nearest Representatives: The K-nearest representative approximation searches a representative region, its nearest representative, and that representative’s K′-neighbor neighborhood.Representatives are first grouped into rep-clusters, then searched coarse-to-fine rather than comparing every object with every representative.
  • Bipartite Graph Partitioning: The sparse affinity sub-matrix is interpreted as a bipartite graph between objects and representatives, which transfer cut partitions to obtain clustering eigenvectors.The eigen-decomposition cost is O(NK(K + k) + p3), and the overall U-SPEC complexity is dominated by O(Np^1/2d).

3.2 Ultra-Scalable Ensemble Clustering (U-SENC)

U-SENC integrates multiple U-SPEC clusterers to improve clustering robustness while retaining high efficiency, then obtains consensus clusters through an object–cluster bipartite graph.

  • Ensemble Generation via Multiple U-SPEC’s: U-SENC generates diverse base clusterings by independently selecting representatives and randomly varying the number of clusters across multiple U-SPEC clusterers.Each U-SPEC instance builds its sparse affinity sub-matrix through fast K-nearest-representative approximation before transfer-cut partitioning and k-means discretization.
  • Consensus Function with Bipartite Graph: The ensemble represents each object–cluster membership as an edge in a bipartite graph whose nodes are objects and all base-clustering clusters.The total number of ensemble clusters is kc = Pm i=1 ki, and each object belongs to exactly m clusters.
  • Consensus Function with Bipartite Graph: The cross-affinity matrix for the ensemble has exactly m non-zero entries per object row and can be stored using O(Nm) memory.Its construction also takes O(Nm) time.
  • Consensus Function with Bipartite Graph: U-SENC computes consensus eigenvectors through a smaller cluster graph, reconstructs the bipartite-graph eigenvectors, and applies k-means discretization.The consensus eigenvector reconstruction takes O(Nm(m + k)) time, followed by O(Nk^2t) k-means discretization.
  • Computational Complexity: With m, k, K ≪ p ≪ N, U-SENC’s dominant overall time complexity is O(Nmp^(1/2)d), while its two stages use O(Np^(1/2)) and O(Nm) memory.The ensemble-generation time is O(Nm(p^(1/2)d + K^2 + Kk + Kd + k^2t)), and the consensus time includes O(N(m^2 + mk + k^2t) + kc^3).

4 EXPERIMENTS

The experiments compare U-SPEC and U-SENC with established spectral and ensemble clustering methods across ten large-scale datasets using repeated NMI, CA, and time measurements.

  • Experimental Design: Experiments compare the proposed algorithms with classical k-means, seven spectral clustering methods, and seven ensemble clustering methods.The comparisons cover both spectral and ensemble clustering settings.
  • Experimental Setup: All experiments run in Matlab 2016b on a PC with an Intel i5-6600 CPU and 64GB of RAM.
  • Datasets: Ten datasets comprise five real and five synthetic datasets, ranging from ten thousand to twenty million objects.The real datasets include PenDigits, USPS, Letters, MNIST, and Covertype; the synthetic datasets range from TB-1M to Flower-20M.
  • Evaluation: Clustering quality is evaluated with normalized mutual information (NMI) and clustering accuracy (CA), while average time costs are also reported.Each method is run 20 times, and larger NMI and CA values indicate better clustering results.

4.2 Baseline Methods and Experimental Settings

The evaluation uses named spectral and ensemble baselines under shared parameter settings, repeated runs, and the true class count as the tested cluster number.

  • Baseline Methods: Spectral baselines include SC, ESCG, Nyström, LSC-K, LSC-R, FastESC, and EulerSC.LSC-K and LSC-R differ by k-means-based versus random landmark selection.
  • Baseline Methods: Ensemble baselines include EAC, WCT, KCC, PTGP, ECC, SEC, and LWGP.
  • Experimental Settings: SC and ESCG receive an N × N affinity matrix constructed with the same Gaussian kernel and K-nearest neighbors.
  • Experimental Settings: The common settings use p = 1000 representatives, K = 5 nearest representatives, and m = 20 base clusterings.The number of clusters in each baseline base clustering is randomly selected in [20, 60].
  • Experimental Settings: The true number of classes in each dataset is used as the number of clusters for all test methods.

4.3 Comparison with Spectral Clustering Methods

U-SPEC and U-SENC remain feasible on the largest benchmark datasets and generally achieve the strongest spectral-clustering scores, with U-SENC ranking ahead of U-SPEC on most datasets.

  • Scalability and Clustering Quality: Only U-SPEC, U-SENC, and EulerSC process all ten benchmark datasets; U-SENC and U-SPEC achieve the best and second-best scores on most datasets.SC and ESCG fail beyond MNIST, while Nyström, LSC-K, LSC-R, and FastESC handle at most two million objects.
  • Scalability and Clustering Quality: U-SENC ranks first on nine of ten datasets and achieves an average rank of 1.10 for both NMI and CA.U-SPEC achieves average ranks of 2.40 for NMI and 2.00 for CA.
  • Computational Cost: U-SPEC is more efficient on most datasets, whereas U-SENC requires more time but scales well to ten-million-level datasets through memory efficiency.
  • Computational Cost: On SF-2M, LSC-K cannot handle ≥1400 representatives and Nyström cannot handle ≥1200 representatives because of memory bottlenecks.

4.4 Comparison with Ensemble Clustering Methods

U-SENC is compared with state-of-the-art ensemble clustering methods on ten large-scale datasets, achieving the strongest reported clustering scores and favorable efficiency, especially beyond million-scale data.

  • U-SENC achieves the highest NMI and CA scores on all ten datasets.
  • 74.57 average NMI(%) and 81.68 average CA(%) are reported for U-SENC across the ten datasets.
  • U-SENC shows an efficiency advantage over other ensemble clustering methods, especially on datasets exceeding millions of objects.

4.5 Parameters Analysis

Parameter analyses examine representative count, nearest-representative count, and ensemble size across benchmark datasets, with U-SENC generally delivering strong accuracy and efficiency.

  • Number of Representatives p: Larger p generally improves performance but increases time cost; U-SENC consistently outperforms other methods in NMI and CA across four datasets.
  • Number of Representatives p: U-SPEC is overall the fastest method across the benchmark datasets for varying p.
  • Number of Representatives p: LSC-K and Nyström cannot handle p ≥ 1,400 representatives on SF-2M, a two-million-object dataset.
  • Number of Nearest Representatives K: U-SENC and U-SPEC are overall the best two methods on three of four datasets with varying K, while U-SENC and LSC-K lead on MNIST.
  • Ensemble Size m: U-SENC outperforms or significantly outperforms other ensemble methods in NMI and CA across varying ensemble size m while requiring lower computational cost.

4.6 Influence of Representative Selection Strategies

The representative-selection analysis compares hybrid, random, and k-means strategies for U-SPEC and U-SENC, finding that hybrid selection balances efficiency and clustering robustness.

  • Random selection is more efficient than k-means selection but may reduce clustering quality because of inherent instability.
  • K-means selection generally improves clustering quality over random selection but incurs much greater computational cost.
  • Hybrid selection has efficiency comparable to random selection, significantly better efficiency than k-means, and competitive clustering quality.
  • Approximate K-nearest representatives achieve comparable NMI and CA to exact representatives while reducing computational cost.
  • The approximation reduces time complexity from O(Npd) to O(Np 1 2 d), with larger efficiency gains on high-dimensional datasets such as MNIST.
  • On a 64GB-memory machine, approximation scales to ten-million-level datasets, whereas conventional nearest-representative computation can hardly exceed five million objects.

5 CONCLUSION

The conclusion presents U-SPEC and U-SENC as large-scale clustering algorithms built around hybrid selection, approximate nearest representatives, bipartite graphs, and transfer cut.

  • U-SPEC and U-SENC are proposed as ultra-scalable spectral and ensemble clustering algorithms, respectively.
  • The conclusion evaluates approximate and exact K-nearest representatives for both U-SPEC and U-SENC.
  • U-SPEC combines hybrid representative selection and approximate K-nearest representatives to construct a bipartite graph for clustering with transfer cut.
Loading 1903.01057v2…