Source-linked AI summary
Spectrally approximating large graphs with smaller graphs
Andreas Loukas, Pierre Vandergheynst
TL;DR
The paper asks how coarsening affects the spectrum of a general graph, a question with limited theoretical guidance. It analyzes coarsening through restricted spectral similarity and establishes conditions for approximating principal Laplacian eigenvalues and eigenspaces. The results also support good-quality spectral-clustering assignments from lifted eigenvectors without refinement.
Problem
How coarsening affects the spectrum of a general graph remained open beyond certain interlacing results, limiting rigorous guidance on how much coarsening spectral methods can tolerate.
Source: §1 · p. 1Method
Results
Principal Laplacian eigenvalues and eigenspaces are close when RSS constants are sufficiently small, and lifted eigenvectors can yield good-quality clustering assignments without refinement.
Source: §1 · p. 2Takeaways & Limitations
For spectral clustering, the theorem identifies lifted coarse eigenvectors as candidates for final assignments when the graph has nearly constant degree and a large K-clusterability gap.
Source: §5 · p. 12The analysis does not currently apply to multi-level coarsening, so the maximum attainable dimensionality-reduction ratio is below 1/2.
Source: §6 · p. 13
Abstract
from arXiv · showhide
How does coarsening affect the spectrum of a general graph? We provide conditions such that the principal eigenvalues and eigenspaces of a coarsened and original graph Laplacian matrices are close. The achieved approximation is shown to depend on standard graph-theoretic properties, such as the degree and eigenvalue distributions, as well as on the ratio between the coarsened and actual graph sizes. Our results carry implications for learning methods that utilize coarsening. For the particular case of spectral clustering, they imply that coarse eigenvectors can be used to derive good quality assignments even without refinement---this phenomenon was previously observed, but lacked formal justification.
1 Introduction
The paper addresses the open question of how coarsening affects the spectrum of a general graph and develops conditions for approximating principal Laplacian eigenvalues and eigenspaces. It links those conditions to graph properties and dimensionality reduction, with implications for spectral clustering.
1 Introduction
- Coarsening reduces the size and cost of graph problems before solutions are lifted and refined in the original graph domain.Prior uses include graph partitioning, visualization, and multiscale representations.Source: §1 · p. 1
- Graph convolutional networks also use coarsening like pooling to reduce layer output size, prevent overfitting, and encourage hierarchical representations.The paper places its analysis against prior theoretical work focused mainly on multigrid solvers and related Laplacian problems.Source: §1 · p. 1
- The effect of coarsening on a general graph’s spectrum remained open beyond certain interlacing results, leaving no rigorous way to determine how much coarsening spectral methods could tolerate.The gap also limited understanding of information loss in coarsening-based learning methods.Source: §1 · pp. 1–2
- The paper studies one-shot coarsening through restricted spectral similarity (RSS), whose constants depend on degree distribution and can be controlled by the coarse-to-original graph-size ratio.The authors show RSS holds for coarsenings formed by contracting edges in a randomized matching.Source: §1 · p. 2
- Principal eigenvalues and eigenspaces are close when RSS constants are sufficiently small, and lifted eigenvectors can yield good-quality spectral-clustering assignments without refinement.The paper formally justifies a phenomenon previously observed experimentally.Source: §1 · p. 2
2 Graph coarsening
The paper represents coarsening as a dimension-reducing map from original vertices to coarse vertices, with lifting back to the original space. Restricted spectral similarity captures how closely the coarsened and original Laplacians act on a selected set of vectors.
2.1 How to coarsen a graph?
- Coarsening maps the original vertex set surjectively to a smaller set, and the coarsened Laplacian is built from the edges crossing between mapped vertices.The associated matrix downsamples graph-supported vectors; this section focuses on block-diagonal coarsening with constant, unit-norm weights.Source: §2.1 · pp. 2–3
- Lifting uses C⊤ to map a coarse vector back to the original dimension, while C⊤C yields a locality-preserving approximation of an original vector.The coarsening frame is the induced subgraph on vertices that are mapped together; edge contraction corresponds to that frame forming a matching.Source: §2.1 · p. 3
2.2 Restricted spectral similarity
- RSS restricts spectral approximation to an appropriate vector subset because the lifted coarsened Laplacian and original Laplacian have different ranks.The property is defined over the first K eigenvectors; when an RSS constant is zero, the corresponding downsampled eigenvector is an eigenvector of the coarsened Laplacian with the same eigenvalue.Source: §2.2 · pp. 4–5
- When the RSS constants are sufficiently small, the coarsened spectrum approximates the original spectrum up to lifting, including the principal eigenvalues and eigenspaces.The paper uses individual RSS constants to obtain tighter bounds than a single uniform constant.Source: §2.2 · p. 5
3 A randomized edge contraction algorithm
The paper introduces randomized edge contraction (REC) to produce coarsenings with bounded RSS constants. Its results connect those constants to graph structure and degree variation, with smaller constants observed for low-index eigenvectors and regular graphs.
3 A randomized edge contraction algorithm
- REC maintains candidate edges for a matching, selects edges according to a potential-based probability, and removes neighboring candidates after each selection.A null-edge probability keeps the sampling measure valid without updating the total potential at each iteration.Source: §3 · p. 5
3.1 Analysis of REC
- The analysis reports that RSS error depends on the reduction ratio and is smaller for low-index eigenvectors, which are described as smooth and less affected by local averaging.The theorem’s bounds are reported to depend on extremal properties of the potential function and graph structure.Source: §3.1 · pp. 6–7
3.2 The heavy-edge potential function
- With the heavy-edge potential, the analysis identifies small degree variation as a favorable setting for efficient coarsening.The paper notes that such degree patterns occur in some machine-learning graphs, including k-nearest-neighbor constructions.Source: §3.2 · p. 8
- For the heavy-edge potential, RSS constants decrease with eigenvalue index and degree variance across the tested graphs, with the regular graph showing much smaller constants than the heavy-tailed yeast network.The examples include two k-nearest-neighbor graphs, the yeast-protein network, and a d-regular graph.Source: §3.2 · p. 8
3.3 Regular graphs
- For regular graphs, the paper gives a corollary bounding the probability that the RSS relation fails and specifies that REC iterations suffice in expectation to achieve a target reduction.The supplied corollary states these results under equal edge weights and a condition on λk.Source: §3.3 · p. 8
4 The spectrum of the coarsened Laplacian
The section connects restricted spectral similarity (RSS) to bounds on coarsened Laplacian eigenvalues and eigenspaces. The usefulness of eigenspace bounds depends on eigenvalue gaps, and the stochastic-block-model example shows alignment improving at the community subspace size.
4.2 From the RSS property to spectrum preservation
- The section links RSS constants to spectral-distance bounds, extending the relationship from eigenvalues to eigenspaces.The section states that the spectrum distance is directly a function of the RSS constant.Source: §4 · p. 8, §4.2 · pp. 9–10
4.1 Basic facts about the spectrum
- For the combinatorial Laplacian, the coarsened eigenvalues relate directly to the original; Theorem 4.1 addresses Lc = CLC⊤, unlike the cited normalized-Laplacian result.Source: §4.1 · p. 9
4.2 From the RSS property to spectrum preservation
- A significant eigengap at the subspace boundary makes the first bound applicable; the alternative avoids a minimum-eigengap condition but depends on gaps to λk+1.The first bound vanishes when n = N.Source: §4.2 · p. 10
- In the stochastic block model, eigenspaces are poorly aligned below K but align well at K; a smaller eigenvalue gap makes this change less pronounced.The reported trend matches the bounds' prediction.Source: §4.2 · pp. 10–11
5 Implications for spectral clustering
The section analyzes clustering assignments obtained from lifted eigenvectors after a single coarsening level. It reports good assignment quality without refinement under near-constant degree and a large λK+1−λK gap, and illustrates error and refinement on MNIST digits.
5 Implications for spectral clustering
- The analysis gives solution-quality guarantees for a single coarsening level, measuring lifted assignments by their k-means cost on the original eigenvectors.Source: §5 · pp. 11–12
- For 1,000 MNIST images depicting digits 0–4, Figure 4b plots relative k-means error against reduction ratio for lifted eigenvectors with and without refinement.The experiment used a 12-nearest-neighbor graph and ten randomly selected image sets.Source: Figure 4 · p. 12, §5 · p. 13
- With almost-constant degree and a large λK+1−λK gap, lifted coarse eigenvectors yield good-quality clustering assignments without refinement.The theorem compares assignment quality in absolute k-means error.Source: §5 · p. 12
- Most remaining error occurred at coarsened cluster-boundary vertices, and a few local-smoothing iterations removed most errors.The illustrated power-iteration refinement adds O(tM(K −1)) overhead.Source: §5 · p. 13
6 Discussion
Coarsening can perturb individual eigenvectors while preserving well-separated principal eigenspaces relatively well. The results also support a manifold-approximation interpretation, but the analysis has pessimistic concentration estimates and does not currently cover multi-level coarsening.
6 Discussion
- Coarsening locally perturbs individual eigenvectors, but carefully constructed coarsenings can leave well-separated principal eigenspaces relatively untouched.For manifold learning, this is interpreted as agreement between coarse and original discretizations in the global geometry captured by eigenvectors.Source: §6 · p. 13
- The concentration estimates in Theorem 3.1 are overly pessimistic, and the results do not currently apply to multi-level coarsening.Consequently, the maximum attainable dimensionality reduction ratio is below 1/2.Source: §6 · p. 13
A.1 Proof of Theorem 4.1
The proof compares the min-max formulations for the original and coarsened Laplacians. Restricting the optimization to vectors satisfying x = Πx makes the coarsened problem more constrained and yields an eigenvalue inequality.
A.1 Proof of Theorem 4.1
- The proof sets Lc = CLC⊤ and xc = Cx when rewriting the coarsened min-max expression.It also uses that Π is a projection matrix.Source: §A.1 · p. 13
- The coarsened min-max problem adds the constraint x = Πx to an otherwise identical optimization, so its solution is strictly larger.This gives eλk ≥ λk.Source: §A.1 · pp. 13–14
A.2 Proof of Theorem 3.1
The proof bounds the random quadratic-form deviation by controlling its expectation and using the edge-contraction probabilities. The resulting probability bound depends on graph properties and sampling probabilities, with a stated condition ensuring nonnegative terms.
A.2 Proof of Theorem 3.1
- The bound depends on ϑk(T, φ), which is a function of sampling probabilities, λk, and the graph’s degree distribution.The RSS constant also depends on the probability that each edge is contracted.Source: §A.2 · p. 15
- The proof notes that the relevant expression is a sum of non-negative terms, then uses Markov’s inequality to obtain the desired probability bound.Source: §A.2 · p. 15
- Lemma A.2 concerns the probability that each edge eij in E is found in EF at REC termination; its proof tracks whether eij remains in candidate set C and its selection after T iterations.Source: §A.2 · pp. 15–16
A.3 Proof of Theorem 4.2
The proof constructs a trial subspace from lifted coarse eigenvectors and an additional projected vector, then applies a variational argument to bound the relevant eigenvalue. The construction is subject to dimension and nullspace conditions.
A.3 Proof of Theorem 4.2
- The variational argument uses that the column space of Z has dimension k and does not intersect the nullspace of Π.The argument considers k ≤ K.Source: §A.3 · p. 17
- The proof builds a trial matrix Z from lifted first eigenvectors of Lc and an additional vector z, then represents vectors in its span as Yk−1a + bz.The coefficients are normalized so ∥a∥2 + b2∥z∥2 = 1.Source: §A.3 · p. 17
- Because z lies outside the span of the first k−1 lifted coarse eigenvectors, the variational upper bound is at least eλk−1.The proof identifies the cases a(k−1) = 1 and b = 1.Source: §A.3 · p. 17
A.4 Proof of Theorem 4.3
The proof of Theorem 4.3 derives sinΘ bounds for the original and lifted coarsened eigenvectors, taking the tighter of two bounds. The proof of Corollary 5.1 adapts a spectral-clustering argument and analyzes its terms together under stated graph and coarsening assumptions.
A.4 Proof of Theorem 4.3
- The proof bounds the subspace angle using squared inner products and summed RSS inequalities.Source: §A.4 · p. 18
- It derives two sinΘ bounds and takes their minimum as the final bound.The first uses λ2 ≤ eλ2; the second comes from an alternative manipulation.Source: §A.4 · p. 18
A.5 Proof of Corollary 5.1
- The corollary proof follows a spectral-clustering argument of Boutsidis and Martin et al. [26], comparing eigenvectors up to a unitary alignment.Yu et al. [40] are cited for the existence of a suitable unitary matrix.Source: §A.5 · pp. 18–19
- Rather than union-bounding two events, the proof analyzes all terms simultaneously.Source: §A.5 · p. 19
- With a heavy-edge potential, sufficiently large N, and bounded degree, the bound simplifies with c1 = 4ϱmax = O(1).Source: §A.5 · p. 19