PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved large-scale graph learning through ridge spectral sparsification

Daniele Calandriello, Ioannis Koutis, Alessandro Lazaric, Michal Valko

arXiv:2604.20078v1cs.LGstat.ML

TL;DR

Large-scale graph learning is difficult when Laplacian computation and distributed storage impose substantial costs. The paper develops a distributed sparsification approach using effective-resistance sampling, with spectral guarantees and a small communication-round bound. It also introduces ridge effective resistance for smaller sparsifiers suited to Laplacian-regularized learning tasks.

  • Problem

    Graph-learning objectives based on Laplacians become difficult to compute and store at scale, and distributing graph data and computation can incur large communication costs.

    Source: §1 · pp. 1–2

  • Method

    The approach combines distributed merge-and-sparsify operations with sampling by regularized, or γ-effective, resistance to construct graph sparsifiers.

    Source: §3.1 · p. 4, §3.2 · p. 5

  • Results

    With a balanced merge tree, DiSRe yields (ε, γ)-sparsifiers with at most 3qdeff(γ) edges and O(log(n)) communication rounds, under the stated condition on m/k.

    Source: §3.2 · p. 5

  • Takeaways & Limitations

    Ridge effective resistance gives sparsifiers better adapted to Laplacian-regularized learning tasks that are smaller than standard spectral sparsifiers without compromising downstream performance.

    Source: §1 · p. 2

    When the original graph already has m ≤ e O(deff(γ)) edges, DiSRe is unnecessary because the sparsifier would not reduce its size.

    Source: §3.2 · p. 4

Abstract

from arXiv · show

Graph-based techniques and spectral graph theory have enriched the field of machine learning with a variety of critical advances. A central object in the analysis is the graph Laplacian L, which encodes the structure of the graph. We consider the problem of learning over this Laplacian in a distributed streaming setting, where new edges of the graph are observed in real time by a network of workers. In this setting, it is hard to learn quickly or approximately while keeping a distributed representation of L. To address this challenge, we present a novel algorithm, GSQUEAK, which efficiently sparsifies the Laplacian by maintaining a small subset of effective resistances. We show that our algorithm produces sparsifiers with strong spectral approximation guarantees, all while processing edges in a single pass and in a distributed fashion.

1. Introduction

Graph-based learning often requires costly optimization over a graph Laplacian, while large graphs make storage, computation, and distributed processing difficult. The introduction motivates combining graph sparsification with distributed computation to support faster Laplacian learning.

  • Exact graph-learning optimization can require O(n^3) time and O(n^2) space, making it infeasible even for mildly large or dense graphs.Source: §1 · p. 1
  • Simple iterative methods may require O(κ) iterations, and κ can grow linearly with n, while preconditioned solvers reduce iteration counts but remain difficult to distribute.Source: §1 · p. 1
  • Effective-resistance sampling can reduce a graph to O(n polylog(n)) edges, but computing effective resistances itself requires the Laplacian pseudoinverse.Source: §1 · p. 2
  • Distributing large graphs can reduce runtime and expand memory capacity, but communication costs and non-local memory access complicate efficient distributed implementations.Source: §1 · pp. 1–2
  • The proposed approach combines distributed computation and sequential sparsification, with O(n log^3(n)) time, O(n log^2(n)) work, O(n log(n)) memory, and O(log(n)) communication rounds.The resulting sparsifier supports near-linear-time downstream learning; ridge effective resistance is proposed for smaller sparsifiers suited to Laplacian-regularized tasks without compromising downstream performance.Source: §1 · p. 2

2. Background

The background defines graph and Laplacian notation, then frames graph-learning tasks through smoothness and Laplacian-based objectives. It also explains why exact computations become impractical as graphs grow.

2. Background

  • The paper uses lowercase letters for scalars, bold lowercase for vectors, and uppercase bold for matrices.Source: §2 · p. 2

2.1. Graphs and graph Laplacian

  • A graph is undirected and weighted, its edge weights encode node similarity, and its Laplacian is positive semidefinite; the analysis assumes the graph is connected.For a connected graph, the Laplacian has one zero eigenvalue and kernel equal to the all-ones vector.Source: §2.1 · p. 2

2.2. Learning on graphs

  • Graph learning assumes smooth labels have small edge-weighted variation; LAPSMO reconstructs noisy labels, while SSL predicts unrevealed labels from partial observations.Source: §2.2 · pp. 2–3
  • Spectral clustering relaxes the ratio-cut problem to obtain cluster assignments, which can then be recovered using thresholding or k-means.Source: §2.2 · p. 3
  • Exact Laplacian eigendecomposition or linear-system computation can be impractical: storing the Laplacian takes O(m) space, while computing and storing its pseudoinverse can take O(n^3) time and O(n^2) space.Source: §2.2 · p. 3

3. Distributed Spectral Sparsification

The section develops regularization-aware spectral sparsifiers and a distributed merge-and-resparsify algorithm for constructing them. It gives conditions and guarantees for the sparsifier size, computation, and communication.

3.1. (ε, γ)-spectral sparsifiers

  • The (ε, γ)-sparsifier permits an additive error of order εγ, enabling smaller graphs for regularized learning tasks whose solutions tolerate small additive errors.The motivation is that regularization partially ignores small Laplacian eigenvalues, so reconstructing the full spectrum can be wasteful.Source: §3.1 · p. 3
  • Sampling edges by γ-effective resistance yields an (ε, γ)-sparsifier with O(d_eff(γ)q) edges when q ≥ 4 log(4n/δ)/ε^2, with probability at least 1 − δ.For graphs with rapidly decaying spectra, d_eff(γ) can be much smaller than n − 1 because γ reduces the contribution of small eigenvalues.Source: §3.1 · p. 4

3.2. The algorithm

  • When the original graph already has m ≤e O(d_eff(γ)) edges, DiSRe is unnecessary because the sparsifier would not reduce its size.Source: §3.2 · p. 4
  • DiSRe partitions the graph, then repeatedly merges and resparsifies pairs of subgraphs; balanced parallel merges form a full binary tree.The resparsification aims to produce a valid sparsifier of the union, as if that union had been sparsified directly.Source: §3.2 · pp. 4–5
  • With a balanced merge tree and m/k ≤ 3q d_eff(γ), DiSRe produces (ε, γ)-sparsifiers with at most 3q d_eff(γ) edges using O(log(n)) communication rounds.The theorem gives time complexity O(d_eff(γ) log^3(n)) and total work O(m log^3(n)).Source: §3.2 · p. 5
  • DiSRe’s sequential Merge-Resparsify avoids cumulative error from treating each resparsification as independent, which would otherwise require error accumulation or multiple data passes.The method estimates γ-effective resistances with fast solvers to invert the regularized sparsifier Laplacian.Source: §3.2 · pp. 5–6

4. Downstream Guarantees

This section relates replacing the full graph Laplacian with a sparsified one to downstream learning guarantees. It analyzes semi-supervised learning and Laplacian smoothing, then extends approximation guarantees to clustering and other Laplacian-based algorithms.

4. Downstream Guarantees

  • The section obtains downstream guarantees by replacing LG with LH and using a nearly-linear-time solver to compute approximate solutions.It considers ε-sparsifiers for SSL and (ε, γ)-sparsifiers for regularized LAPSMO.Source: §4 · p. 6, §4.1 · p. 6

4.1. Generalization bounds for SSL

  • For semi-supervised learning, the sparsification error term vanishes as O(ε^2/ℓ^2(1−ε)^4) as labeled samples grow, while ε trades off the bound against space complexity.The theorem assumes a fixed connected graph, bounded labels, and centered labels on the sampled nodes.Source: §4.1 · pp. 6–7

4.2. Generalization bounds for LAPSMO

  • For LAPSMO, γ > 0 adds a bound term proportional to λγ∥bf∥2, which is constant when γ = 1/λ and ∥f⋆∥2 is small.The section reports near-linear overall runtime, with potentially sub-linear runtime for favorable spectra and sufficient regularization.Source: §4.2 · p. 7

4.3. Bounds for other problems

  • For other Laplacian-based problems, a clustering that separates the sparsifier also separates the original graph, and regularized tasks can receive strong generalization guarantees.The stated examples include LTR, Laplacian-regularized least squares, and Laplacian SVM.Source: §4.3 · p. 7

5. Experiments

The experiments test whether (ε, γ)-sparsifiers reduce computational costs without sacrificing task accuracy. On the Amazon co-purchase graph, DiSRe’s accuracy is close to the exact solution for both smoothing and semi-supervised learning, and exceeds k-neighbors’ reported accuracy.

5. Experiments

  • The experiments use an unweighted Amazon co-purchase graph with 334,863 nodes and 98,465,352 edges, and evaluate a hand-designed smooth target signal.The signal is based on an approximation of the graph’s smallest eigenvector.Source: §5 · p. 7
  • The study averages performance and standard deviation over 10 runs with different sparsifiers, reporting selected noise levels and the best regularization for each method.The smoothing results shown in the text cover σ = 0.001 and 0.01; the SSL results cover ℓ = 346 and 672 revealed labels.Source: §5 · p. 8, §5.1 · p. 8, §5.2 · p. 8

5.1. Laplacian smoothing with Gaussian noise

  • ε-sparsifiers match the exact method’s accuracy in Laplacian smoothing, while DiSRe still outperforms k-neighbors when γ is large and the graph is much smaller.Increasing γ increases compression but degrades accuracy; increasing q for γ = 0 enlarges the sparsifier and slightly improves performance.Source: §5.1 · p. 8
  • For smoothing, DiSRe preprocessing plus solving takes roughly 12 minutes, matching the exact baseline, and memory stays below 10GB versus over 30GB for the exact method.DiSRe takes 12 minutes for preprocessing on four machines; solving takes 1–2 minutes for both DiSRe and k-neighbors.Source: §5.1 · p. 8

5.2. SSL with harmonic function solution

  • DiSRe closely approximates the exact solution on the semi-supervised learning task despite substantial graph compression, and its error is significantly lower than k-neighbors’.The experiment uses an ε-sparsifier with γ = 0; running times are reported as comparable to those for smoothing.Source: §5.2 · p. 8

A. Proofs for the statements in Sec. 4

The appendix supplies proof arguments for the downstream guarantees, including a stability-based analysis for Stable-HFS and a bound on the difference between LAPSMO solutions computed on the full and sparsified graphs.

A. Proofs for the statements in Sec. 4

  • The Stable-HFS theorem assumes a fixed connected graph, bounded labels, centered sampled labels, and a random labeled-node subset, and gives a high-probability guarantee for solutions on H and G.The probability accounts for both sparsifier generation and selection of labeled points.Source: A. Proofs for the statements in Sec. 4 · p. 11
  • The Stable-HFS proof combines a stability bound with a comparison of empirical errors, using centered labels to express the solution in closed form.Its stability argument uses the smallest nonzero eigenvalue of the sparsified Laplacian and the spectral guarantee relating it to the original graph.Source: A. Proofs for the statements in Sec. 4 · pp. 11–12
  • For LAPSMO, the proof bounds the distance between solutions on G and H using the (ε, γ)-sparsifier condition and the regularization parameter λ.The theorem applies to an arbitrary graph and identifies λ as LAPSMO’s regularization.Source: A. Proofs for the statements in Sec. 4 · pp. 11, 13

B. Proof of Thm. 1

Theorem 1 bounds the error and size of every intermediate sparsifier with high probability, and gives near-linear parallel complexity for balanced merge trees under a condition on the number of machines. The proof analyzes a merge tree node by node, bounding approximation error and memory use separately.

Theorem 1

  • With q = 26ρ log(3n/δ)/ε^2, every intermediate H{h,ℓ} is an (ε, γ)-sparsifier with at most 3q d_eff(γ) edges, with probability 1 − δ.Theorem 1 applies to an arbitrary graph and arbitrary merge tree.Source: B. Proof of Thm. 1 · p. 14
  • For a balanced merge tree with m/k ≤ 3q d_eff(γ), parallel merges take O(d_eff(γ) log^3(n)) time, O(m log^3(n)) total work, and O(log(n)) communication rounds.The condition ensures sufficiently sparse leaf subgraphs.Source: B. Proof of Thm. 1 · p. 14

Proof approach

  • The analysis adapts Kelner and Levin’s sparsification proof using martingale inequalities to handle dependencies across resparsifications, and modifies SQUEAK’s analysis for graph Laplacians.The authors say this addresses a flaw in the original analysis that treated dependent variables as independent.Source: B. Proof of Thm. 1 · p. 14

Merge trees

  • The proof partitions the graph into k subgraphs, initializes one sparsifier per subgraph, and represents successive pairwise merges as a full binary tree.The initial sparsifiers contain the input edges with unit weights and q copies; subgraphs can be chosen small enough for in-memory processing.Source: B. Proof of Thm. 1 · p. 14

Bounding failure

  • At each tree layer, block-diagonal projection matrices let the proof reduce simultaneous sparsifier accuracy to bounding the error at individual nodes.The probability analysis separately accounts for approximation failure and a node exceeding its memory bound, then uses a union bound across events.Source: B. Proof of Thm. 1 · pp. 15–16
  • The error and space guarantees rely on resistance estimates that are respectively bounded below by a fraction of the true γ-effective resistances and above by them.The lower bound supports sufficient sampling for accuracy; the upper bound prevents oversampling relative to exact γ-effective-resistance sampling.Source: B. Proof of Thm. 1 · p. 16

B.1. Bounding the projection error ∥P{h,ℓ} −eP{h,ℓ}∥

For a fixed merge-tree node, the proof studies the random approximate projection matrix built from its fixed graph and random sparsifier. It tracks edge-copy sampling along the unique path from leaves to that node.

Node-specific process

  • Fixing a merge-tree node makes its graph G{h,ℓ} deterministic, while randomness in its approximate projection comes from sampled edges and their weights.The node-specific process can therefore be analyzed sequentially rather than over the entire merge tree.Source: §B.1 · p. 16

Edge-copy process

  • With edge-disjoint leaf graphs, each edge follows a unique path of length h, so its sampling probabilities and copy counts are tracked at each step.If an edge is not involved in a merge at a layer, its probability and copy count are propagated unchanged.Source: §B.1 · p. 16

Projection matrices

  • The exact projection is formed from columns of (L_G{h,ℓ} + γI)^−1/2 B_G{h,ℓ}, whose squared column norms are the edges’ γ-effective resistances.These quantities are defined relative to the graph associated with the fixed node.Source: §B.1 · p. 17

B.2. Bounding Yh

The proof bounds the projection error by representing it as a matrix process and stopping that process after its first threshold violation. A lower bound on frozen sampling probabilities supports a martingale concentration argument.

Process construction

  • The projection error is recast as a random matrix process Y_h that uses the algorithm’s edge weights and copy multiplicities.The construction connects the process to the algorithm through the same probabilities and multiplicities.Source: §B.2 · p. 17

Freezing the process

  • After the first step with error norm at least ε, the auxiliary process is frozen, so any intermediate threshold violation persists to its final value.Until that point, the frozen and original processes agree.Source: §B.2 · p. 17

Probability lower bound

  • Each frozen copy probability satisfies p_s,e,j ≥ r_h,e/α, where α = (1 + 3ε)/(1 − ε).The lemma relates the lower bound to the γ-effective resistance r_h,e at the node.Source: §B.2 · p. 18

Concentration bound

  • The frozen process is shown to be a martingale with bounded differences, enabling a matrix Freedman inequality to bound its norm.The proof also bounds the probability of a large predictable quadratic variation before applying the inequality.Source: §B.2 · pp. 19–20
  • With q = 39α log(2n/δ)/ε^2, the proof combines the concentration bounds for a fixed node and uses k ≤ n to complete this part of the failure analysis.The supplied proof states these steps but does not provide the resulting bound in the passage.Source: §B.2 · p. 20

B.3. Proof of Lem. 2 (bound on predictable quadratic variation)

To bound predictable quadratic variation, the proof replaces dependent edge-copy variables with independent variables that stochastically dominate them. This enables a concentration bound for the sum of positive semidefinite matrix terms.

Independent domination

  • Dependence among edge-copy chains makes a direct high-probability bound on W_h difficult, so the proof replaces them with independent dominating variables.The proof notes that low retention probability also makes a retained-copy ratio small, but dependence obstructs using that intuition directly.Source: §B.3 · p. 22
  • The auxiliary variables w_s,e,j are defined from conditional distributions involving p_s,e,j, p_h,e, and α, and are independent of other such variables given the prior history.At the initial step, the variables are independent without conditioning.Source: §B.3 · p. 22

Stochastic dominance

  • Peeling the process backward establishes stochastic dominance by the initial independent variables, allowing the bound to use their independence across edge copies.The proof applies this dominance to the maximum over steps and then to the matrix sum.Source: §B.3 · pp. 24–26

Concentration

  • Although Yh is not necessarily PSD, Wh is a sum of PSD matrices; using L = α²/q², the proof computes E[Xk], then selects h = 2 and σ² = 6α/q before applying Prop. 5.Source: §B.3 · pp. 25, 27

B.4. Space complexity bound

The space-complexity proof bounds approximate effective resistances under event A, then uses domination and layer-by-layer arguments to establish its conclusion.

B.4. Space complexity bound

  • Under event A, the approximate γ-effective resistances are accurate, and the proof considers an (ε, 2γ)-sparsifier of the graph.Source: §B.4 · p. 27
  • The proof handles dependent Bernoulli variables by finding a dominating stochastic variable; the comparison variable lacks a recursive definition and depends only on ε at the preceding step.Source: §B.4 · p. 28
  • The layer argument proceeds backward from iteration s to s − 1 and is applied repeatedly from h down to 2.Source: §B.4 · p. 28
  • At the first layer, independent Bernoulli variables are bounded using a Hoeffding-like bound with Markov's inequality.Source: §B.4 · p. 29
  • The proof chooses θ to minimize the preceding expression before concluding the bound.Source: §B.4 · p. 29

C. Further details on experiments

The experiment details report the computing setup, solver and DiSRe implementation, and selected parameter configurations; supplementary spreadsheets contain additional results.

C. Further details on experiments

Related papers

Loading 2604.20078v1…