A graph with a tenth of the edges

A sparsifier is a graph with fewer edges that behaves like the original. Which behaviour is preserved is the entire content of the definition, and the version that has a theorem behind it preserves the quadratic form:

(1 − ε) · xᵀL x   ≤   xᵀL' x   ≤   (1 + ε) · xᵀL x      for every x

Every x. Not every x in a subspace, not with high probability for a given x — every vector at once, which means every cut, every eigenvalue, and the answer to every linear system.

The construction #

Keep each edge with probability proportional to its effective resistance times its weight, sample q times with replacement, and give each kept edge a weight of w/(q·p) where p was its probability.

The reweighting is what makes it work. An edge kept once carries w/(q·p); kept twice, twice that. So the expected Laplacian of the sample is exactly the Laplacian of the original — the estimator is unbiased, edge by edge, and that is the only part of the construction that is a theorem rather than a measurement.

The probabilities come out normalised for free, and by Foster’s identity: Σ w·R(e) over the edges is exactly n − 1 for any connected graph, so dividing by n − 1 gives a distribution without a normalising pass. The assertion in this library checks that sum to 10⁻⁸n before sampling anything, which is Foster’s theorem being used as a precondition rather than as a curiosity.

What survives #

On a fifty-vertex complete graph, sampling at five different counts:

samples   edges kept   eigenvalue ratios   degree ratios   diameter after
  200        187        0.289 – 2.018      0.37 – 1.75          3
  400        344        0.432 – 1.674      0.56 – 1.50          3
  800        599        0.611 – 1.589      0.72 – 1.53          2
 1600        887        0.654 – 1.377      0.72 – 1.31          2
 3200       1123        0.721 – 1.222      0.76 – 1.16          2

At 400 samples the graph has 28% of its edges and every one of its forty-nine non-zero eigenvalues is within a factor of 1.7 of the original. That is the theorem working: no vector, of the 2⁵⁰ cuts or the continuum of directions, sees a distortion larger than the band.

The band closes like the square root of the sample count, which is the ordinary rate for an average of independent draws and is the only asymptotic in the construction. Sixteen times the samples buys four times the accuracy: 2.02 down to 1.22 at the top of the band.

What does not #

The degree column is the one to read next.

At 400 samples the degrees run from 0.56 to 1.50 of their original values. Half the vertices in a graph whose spectrum is preserved to within 1.7 have a degree wrong by more than a third, and the worst is wrong by half.

That is not a defect of the sampler; it is what the theorem does not claim. A degree is xᵀLx for x = eᵢ — a single indicator vector — and the guarantee is a relative one, so a quantity that is small relative to the norm is preserved only relatively to itself, with a variance that comes from one vertex’s worth of draws rather than the whole graph’s. Fewer draws, wider band.

The diameter is starker. A complete graph has diameter one: every pair is adjacent. The sample has diameter three at 400 samples and two at 800. No shortest path survives. Every pair of vertices that was one hop apart is now up to three, and a routing algorithm run on the sparsifier would return answers that are wrong by a factor rather than by a percentage.

The band is not the same as the error #

One reading of the eigenvalue column needs correcting before it becomes a habit, and it is the reading that treats the band as an accuracy.

The guarantee is a relative distortion of a quadratic form, applied uniformly. So a solve using the sparsified Laplacian as a preconditioner converges at a rate governed by the band’s width — a band of 0.43 to 1.67 is a condition number of 3.9 for the preconditioned system, which is excellent — and the answer it converges to is the answer to the original system, exactly, because the preconditioner does not change the problem.

That is the use in which the band is an accuracy of nothing and a cost of something.

The other use is to solve with the sparsifier directly, treating it as a substitute for the graph. The answer is then wrong by the band: a solve with L’ rather than L returns a vector differing from the true one by a relative amount of order ε, and at 400 samples that is tens of per cent. Which is usually not what anybody wanted.

So the same object is either a free speedup or a large approximation error depending on which side of the solve it is put on, and the distinction is not visible in the object. The preconditioning essays make the general form of this argument: an approximate inverse used as a preconditioner is exact in the answer and approximate in the cost, and used as a solver is the reverse.

Why the two are so easy to confuse #

The trap is that the sparsifier is the graph, in the sense that it is a set of vertices and weighted edges, and every graph algorithm will run on it and return something.

Run a spectral partitioner on it and the answer is right, because a partition is a quadratic form. Run a solver on it as a preconditioner and it works, because a solve is a quadratic form. Run a shortest-path algorithm on it and the answer is wrong, and nothing warns, because the input was a perfectly well-formed graph.

The general form of that is a shape this site keeps meeting: an approximation preserves the quantity it was built to preserve, and an object that is an approximation for one purpose is not labelled as such. The half of a problem a sketch may touch makes the same argument about randomised sketching — a sketch is a valid input to any routine and is a valid approximation for only some of them — and a rank that is a number of digits makes it about a hierarchical format.

When it fails outright #

There is a failure worse than a wide band, and the sampler is not immune to it.

At 200 samples on an eighty-vertex two-block graph, the sample came back disconnected — one vertex with no edges at all. Its eigenvalue ratios then include a zero where the original had a positive eigenvalue, which is not a factor of ε; it is a quadratic form that vanishes on a vector where the original’s does not, and the guarantee has failed completely rather than by a margin.

Undersampling is the whole cause, and there is a bound saying how many samples are enough — of order n log n divided by ε² — with constants nobody uses because they are pessimistic by orders. So in practice the sample count is chosen by measurement, and the measurement to make is not the eigenvalue band but whether the sample is connected, which costs one breadth-first search and catches the catastrophic case before the numerical one.

That is the same asymmetry the randomised field describes: the guarantee changes kind, from a bound that holds to a bound that holds with a probability, and the low-probability event is not a slightly worse answer but a different one.

Why resistance is the right probability #

Uniform sampling fails on graphs where sparsification is most wanted, and the refusal in this field is exactly that case.

A barbell is two cliques joined by one edge. Keeping edges uniformly at random with probability a quarter keeps about a quarter of the clique edges, which is plenty — the cliques are massively redundant — and keeps the bridge with probability a quarter. Three times in four the sample is disconnected, and a graph in two pieces does not approximate a connected one in any sense at all.

Resistance sampling keeps the bridge with probability one. Its effective resistance is 1, the largest in the graph by a factor of about k², so it takes a proportionate share of the samples and the construction cannot lose it.

That is the informal reading of what effective resistance measures: how much of the graph’s connectivity an edge is personally responsible for. An edge in a clique has dozens of parallel routes and low resistance; a bridge has none and resistance 1. Sampling in proportion to it is sampling in proportion to irreplaceability, and the spectral form of the quantity says why: a high-resistance edge is one the low eigenvalue modes depend on.

What it costs to build #

The awkward part of the construction is that computing the sampling probabilities requires all the effective resistances, and computing those requires solving with the Laplacian — which is the thing the sparsifier was going to make cheaper.

Three ways round it, in increasing order of practicality.

Solve exactly anyway. For a graph small enough this is what the figures here do, and it makes the measurement clean at the cost of making the construction pointless.

Estimate the resistances. They can be approximated by a Johnson–Lindenstrauss projection — project the incidence matrix onto O(log n) random directions and read the resistances as squared distances — which needs only O(log n) approximate solves rather than n exact ones. That is the route that makes the whole thing practical, and it is a randomised approximation inside a randomised approximation.

Or use something cheaper as a proxy. Sampling by weight, or by an edge’s position in a spanning tree, gives weaker guarantees and is sometimes enough.

The recursion in the second route is worth noticing: to sparsify a graph cheaply, one needs to solve with it cheaply, which is what sparsification is for. The published algorithms break the circle by building a chain of progressively sparser graphs, each used to precondition the solve that builds the next.

Sampling with replacement, and the edges kept twice #

A detail of the construction is worth pulling out because it is where the count of edges and the count of samples part company.

The sampling is with replacement, so 400 samples do not produce 400 edges. They produced 344 in the table above, because fifty-odd of the draws duplicated an edge already kept, and a duplicate adds its weight rather than appearing twice.

That gap widens as the sample count rises relative to the number of edges: 3,200 samples on a graph with 1,225 edges keep 1,123 of them, so at that point 65 per cent of the draws are duplicates and the sparsifier is nearly the original graph with slightly wrong weights.

Two consequences. First, the sample count is the right knob and the edge count is the wrong one: asking for “half the edges” does not determine the accuracy, because how many distinct edges a given number of draws produces depends on the resistance distribution. Second, the construction degrades gracefully into the identity — oversampling gives back something close to the original graph with a narrow band, which is a sensible limit for a randomised method to have and is not automatic.

The weights of the kept edges are also not the original weights. An edge kept once in 400 draws with probability p carries w/(400p), which is w only if it was drawn exactly its expected number of times. So a sparsifier of an unweighted graph is a weighted graph, always, and any downstream code that assumes unit weights is reading a third thing that was not preserved.

What to check when using one #

Three things, and the order matters because they fail in this order.

Connectivity. One breadth-first search, which is also the exact route to a component count. A disconnected sample is not an ε-approximation of anything and is the failure mode of undersampling.

The spectral band. For a graph small enough to diagonalise, the ratio of each eigenvalue to the original’s is the direct measurement of ε and takes no argument about constants. For a larger one, the extreme eigenvalues of L’⁺L by a few iterations of a Lanczos process bound the band from both sides.

And the list of things not preserved. Degrees, distances, triangle counts, edge counts, anything local. A sparsifier is an approximation in one norm and in no other, and a pipeline that hands it to a routine reading a degree has substituted a different graph.

The last of those is the one that costs afternoons, because it produces answers rather than errors — which is this site’s most-repeated observation, and is why the essay measures the degrees and the diameter beside the spectrum rather than only the thing that works.

What this field gets from the randomised one #

The construction is a randomised method and it inherits the whole of that field’s vocabulary, which is worth stating because the inheritance is exact rather than analogical.

The guarantee changes kind. Everything else in the graph field is deterministic: a conductance is below a bound or it is not. A sparsifier’s band holds with a probability, and the failure event — undersampling to disconnection — is not a slightly worse answer.

The seed is part of the answer. Two sparsifiers of one graph, from two seeds, are different graphs with different degrees and different diameters, and both satisfy the theorem. Reporting one without its seed makes the result irreproducible in exactly the way the seed essays describe.

And the band should be drawn rather than stated. A single run’s eigenvalue ratios are one draw from a distribution, so quoting “ε = 0.5” from one run is quoting a sample. The figures here draw the whole spectrum’s ratios, which is one run seen completely rather than summarised, and the honest version over seeds would be a band of bands.

What the graph field adds in return is a sampling probability that is not uniform and not heuristic. Most randomised methods on this site sample uniformly or with Gaussian weights, because nothing better is available; here the right probability is a computable property of each edge, it is what makes the guarantee hold for every vector at once, and the identity that normalises it is a hundred-year-old theorem about electrical networks.

At other settings #