PaperlayerView exact revision on arXiv

Source-linked AI summary

Compressive Spectral Clustering

Nicolas Tremblay, Gilles Puy, Remi Gribonval, Pierre Vandergheynst

arXiv:1602.02018v2cs.DScs.LGstat.ML

TL;DR

Spectral clustering is computationally demanding at large N or k, including its eigenvector and k-means stages. This paper uses graph-filtered random signals and sampled nodes to approximate it, reporting efficient and accurate performance on synthetic and real-world data, with a reconstruction guarantee under stated conditions.

  • Problem

    Spectral clustering becomes computationally intensive for large N and/or k, including the eigendecomposition and k-means stages.

    Source: §1 · p. 1

  • Method

    The method filters random signals to form features, clusters a random subset of nodes, and interpolates cluster indicators to the full graph.

    Source: §3.1 · p. 3, §3.2.2 · p. 4

  • Results

    The experiments report that compressive spectral clustering is efficient and accurate on synthetic and real-world datasets and faster than SC for large N and/or k.

    Source: §4.4 · p. 7, §6 · p. 9

  • Takeaways & Limitations

    The authors conclude that compressive spectral clustering could be preferred to SC for large N and/or k.

    Source: §6 · p. 9

    When the estimated λk exceeds λk+1, feature vectors incorporate eigenvectors outside span(Uk), and the impact is application-dependent.

    Source: §5.2 · pp. 7–8

Abstract

from arXiv · show

Spectral clustering has become a popular technique due to its high performance in many contexts. It comprises three main steps: create a similarity graph between N objects to cluster, compute the first k eigenvectors of its Laplacian matrix to define a feature vector for each object, and run k-means on these features to separate objects into k classes. Each of these three steps becomes computationally intensive for large N and/or k. We propose to speed up the last two steps based on recent results in the emerging field of graph signal processing: graph filtering of random signals, and random sampling of bandlimited graph signals. We prove that our method, with a gain in computation time that can reach several orders of magnitude, is in fact an approximation of spectral clustering, for which we are able to control the error. We test the performance of our method on artificial and real-world network data.

1. Introduction

Spectral clustering builds a similarity graph, derives node features from Laplacian eigenvectors, and clusters them with k-means, but these steps become costly at large scale. Compressive spectral clustering addresses the eigendecomposition and k-means bottlenecks with graph filtering and sampling, while prior subsampling approaches lacked a proof of approximation to standard spectral clustering.

1. Introduction

  • Similarity-graph construction, Laplacian eigendecomposition, and k-means are the three computational bottlenecks for large N and/or k.SC partitions data points into k weakly interconnected clusters using Laplacian eigenvectors as features for k-means.Source: §1 · p. 1

1.1. Related work

  • Earlier approaches either accelerated eigenvector computation while retaining k-means on all N feature vectors, or subsampled nodes and interpolated results without proving approximation to SC.Other approaches reduced graph size by aggregation and used kernel k-means to control interpolation errors.Source: §1.1 · pp. 1–2

1.2. Contribution: compressive clustering

  • Compressive spectral clustering assumes the Laplacian is given and replaces eigenvector computation with graph-filtered random signals as clustering features.The paper analyzes how non-ideal, computationally efficient filters affect feature quality.Source: §1.2 · p. 2
  • Sampling O(k log(k)) nodes and clustering random feature vectors of size O(log(k)) supports label inference for all N nodes, reducing k-means complexity from O(Nk^2) to O(k^2 log^2(k)).The method interpolates the sampled cluster indicators back to the full graph.Source: §1.2 · p. 2

2. Background

The background defines graph signals and Laplacian-based graph filtering, then presents normalized-Laplacian spectral clustering as the reference procedure.

2.1. Graph signal processing

  • An undirected weighted graph has nodes, edges, and a symmetric nonnegative adjacency matrix; its normalized Laplacian has an orthonormal eigenbasis used as graph Fourier modes.The modes correspond to eigenvalues whose square roots are treated as graph frequencies.Source: §2.1 · p. 2
  • Graph filtering applies h(L) to a node signal, and polynomial approximation enables filtering through successive Laplacian-vector multiplications rather than diagonalizing L.For a graph with #E edges, filtering has complexity O(p#E) for polynomial order p.Source: §2.1 · p. 2

2.2. Spectral clustering

  • The reference spectral-clustering procedure computes the first k normalized-Laplacian eigenvectors, normalizes their rows into node features, and runs Euclidean k-means to obtain k classes.The input graph is represented by its pairwise-similarity adjacency matrix before computing the Laplacian.Source: §2.2 · pp. 2–3

3. Principles of CSC

Compressive spectral clustering (CSC) approximates spectral clustering by using random graph-filtered features, clustering a sampled subset of nodes, and interpolating cluster labels to the full graph. Its sampling and recovery theory relies on cluster indicators being approximately bandlimited and gives sufficient sample counts under stated conditions.

3. Principles of CSC

  • CSC avoids partial Laplacian diagonalization by estimating spectral-clustering distances with filtered random signals, then clusters sampled feature vectors and interpolates labels to the full graph.The framework extends distance estimation to account for normalization and polynomial filter approximation; the stated downsampling scheme uses d = O(log k) features and n = O(k log k) samples.Source: §3 · p. 3, §3.1 · p. 3

3.1. Ideal filtering of random signals

  • With ideal low-pass filtering, coherence-normalized random signals provide node features whose pairwise distances estimate the spectral-clustering distance with high probability for sufficiently large d.The treatment says a later extension covers finite-order polynomial approximations and d = O(log k) features with downsampling.Source: §3.1 · p. 3

3.2.1. THE LOW-DIMENSIONAL MODEL

  • For general graphs, CSC assumes cluster indicator vectors lie close to span(U_k), making them approximately k-bandlimited.The paper says experiments will confirm that this model is sufficient to recover the cluster indicators.Source: §3.2.1 · p. 4

3.2. Downsampling and interpolation

  • The method samples n feature vectors, runs k-means on those nodes, and reconstructs the full cluster indicators from the sampled labels.The reconstruction is faithful when indicators lie near span(U_k) and the sampling matrix has the restricted isometry property; it is robust to observation noise and model error, with performance depending on the filter ratio g(λ_k)/g(λ_{k+1}).Source: §3.2.2 · p. 4

3.2.3. HOW MANY FEATURES TO SAMPLE?

  • The theorem’s sufficient condition on n ensures M satisfies the restricted isometry property (6); sampling O(ν_k^2 log k) features is sufficient to recover the cluster indicator vectors.Source: §3.2.3 · p. 5

4. CSC in practice

CSC combines polynomial graph filtering, random feature sampling, and indicator-vector interpolation to reduce the cost of spectral clustering. Its guarantees and practical accuracy depend on filter approximation, cutoff estimation, and the chosen distance resolution.

4.1. The CSC algorithm

  • CSC filters random Gaussian signals, retains n node features, clusters the reduced set, interpolates cluster indicators, and normalizes them for hard assignments.The interpolated indicators can also represent fuzzy cluster membership before normalization.Source: §4.1 · p. 5

4.2. Non-ideal filtering of random signals

  • Theorem 4.1 controls reduced-feature distance estimates around resolution D_r,min: smaller distances stay below (1 + δ)D_r,min, while larger ones are estimated within relative error δ.The theorem accounts for both non-ideal polynomial filtering and clustering on the reduced feature set.Source: §4.2 · pp. 5–6
  • Lowering D_r,min requires smaller filter errors e1 and/or e2, which raises polynomial order and filtering time.Non-ideal filtering creates an irreducible feature-vector error, so distances near zero need not be approximated exactly.Source: §4.2 · p. 6

4.3. Polynomial approximation and estimation of λk

  • Jackson-Chebychev polynomials damp Gibbs oscillations near λk; p = 50 yielded good experimental results.The recommended order is the smallest p meeting the error condition for the chosen resolution and coherence values.Source: §4.3 · p. 6
  • CSC estimates λk without computing the first k eigenvectors, using random-signal low-pass filtering and dichotomous search over the cutoff.For each trial cutoff, it filters 2 log N random signals to estimate the number of enclosed eigenvalues.Source: §4.3 · p. 7

4.4. Complexity considerations

  • For sparse graphs, CSC’s complexity simplifies to O(k^2 log^2 k + pN(log N + k)); SC additionally pays for eigenvector computation.The analysis omits iteration counts, which are difficult to predict theoretically.Source: §4.4 · p. 7

5. Experiments

Across the SBM and Amazon experiments, CSC achieves recovery close to SC and the power method while gaining runtime as k increases. In SBM tests, its estimate of λk can exceed λk+1 at larger ϵ.

5. Experiments

  • The experiments use SBM graphs and a large real-world network; the SBM varies community connection probabilities, with larger ϵ making detection harder.The experiment description identifies the Amazon co-purchasing network as the real-world graph.Source: §5 · p. 7, §5.1 · p. 7, §5.2 · p. 8

5.2. Performance results

  • CSC recovery saturates at the default settings for n, d, p, and γ; heterogeneous-community SBM experiments show similar results.Recovery is measured by Adjusted Rand similarity, with higher values indicating better reconstruction.Source: §5.2 · p. 7
  • In SBM tests, λk is overestimated, and the estimate exceeds λk+1 for ϵ above roughly 0.06.The effect of the resulting additional eigenvector information is application-dependent and can be insignificant in some cases.Source: §5.2 · pp. 7–8
  • On SBM graphs, CSC’s recovery is only a few percent below SC and the power method, and it becomes up to an order of magnitude faster as k increases to 200.At k = 20, SC and the power method are faster; the SBM setting also favors SC because eigs converges quickly.Source: Figure 1 · p. 8, §5.2 · p. 8
  • On the Amazon network, CSC is much faster than SC for the same modularity, especially as k increases.The comparison uses modularity because the network has no clear ground truth; SC’s k-means used two replicates for a fair comparison.Source: Figure 1 · p. 8, §5.2 · p. 8

6. Conclusion

The conclusion presents filtering O(log k) random signals and sampling O(k log k) nodes as a route to approximate spectral clustering. It reports that CSC is efficient and accurate on synthetic and real-world data even without the suggested community-core refinement.

  • Filtering O(log k) random signals constructs feature vectors whose interdistances approximate those of standard spectral clustering.Source: §6 · p. 8
  • Sampling O(k log k) nodes supports inference of labels for all N nodes when reduced-set k-means is correct under Eq. (3).The conclusion characterizes the interpolated result as a good approximation of spectral clustering.Source: §6 · pp. 8–9
  • Repeated runs could identify stable community cores for interpolation, but CSC is reported efficient and accurate without this refinement on synthetic and real-world data.The suggested refinement keeps nodes that are always classified together across runs using different random signals.Source: §6 · p. 9

A. Proof of Theorem 3.2

The proof transforms standard spectral-clustering feature differences into a form suitable for a Johnson–Lindenstrauss bound. It then establishes pairwise distance preservation under a dimension condition.

  • The proof uses Y_k = V_kU_k as the feature representation.Source: A. Proof of Theorem 3.2 · p. 9
  • It rewrites feature differences in a form to apply the Johnson–Lindenstrauss lemma to R^T U_k(f_i−f_j).The passage identifies f_i as standard spectral-clustering feature vectors.Source: A. Proof of Theorem 3.2 · p. 9
  • When d exceeds the stated threshold, pairwise distances are preserved within factors 1−ϵ and 1+ϵ with probability at least 1−N^−β.The proof uses orthonormality of U_k to equate the transformed and standard feature distances.Source: A. Proof of Theorem 3.2 · p. 9

B. Proof of Theorem 4.1

The proof bounds errors in estimated distances and uses probability bounds to control all sampled-node pairs. It then handles two cases separately to establish the theorem's parts under Eq. (7).

C. Experiments on the SBM with heterogeneous community sizes

The heterogeneous-community SBM experiments vary ϵ and several CSC parameters. The reported results are similar to those for the homogeneous case.

Loading 1602.02018v2…