Source-linked AI summary
Expander Decomposition and Pruning: Faster, Stronger, and Simpler
Thatchaphol Saranurak, Di Wang
TL;DR
Efficient expander decomposition seeks clusters with conductance at least a target threshold while keeping the number of cut edges low, but recursive approaches can become slow when sparse cuts are unbalanced. The paper uses local fixing on a nearly-expanding larger side to obtain an expander decomposition whose clusters have conductance at least φ/6.
Problem
For a fixed conductance requirement, expander decomposition seeks low error and fast running time, while recursive approximate-cut methods can have Ω(n) depth and take Ω(n^2) time.
Source: §1 · p. 3, §1.1 · p. 3Method
The algorithm recursively seeks balanced sparse cuts and locally fixes a very unbalanced cut's larger side when it has a weak expansion guarantee.
Source: §2 · p. 5Results
The recursion leaves form clusters with conductance at least φ/6, measured with respect to volume in the original graph.
Source: §2 · p. 7Takeaways & Limitations
The approach relies on fairly basic, simple techniques that the authors say are likely to have practical significance.
Source: §1.2 · p. 4The local-fixing step requires a nearly-expander guarantee for the larger side of a very unbalanced cut.
Source: §2 · p. 5
Abstract
from arXiv · showhide
We study the problem of graph clustering where the goal is to partition a graph into clusters, i.e. disjoint subsets of vertices, such that each cluster is well connected internally while sparsely connected to the rest of the graph. In particular, we use a natural bicriteria notion motivated by Kannan, Vempala, and Vetta which we refer to as {\em expander decomposition}. Expander decomposition has become one of the building blocks in the design of fast graph algorithms, most notably in the nearly linear time Laplacian solver by Spielman and Teng, and it also has wide applications in practice. We design algorithm for the parametrized version of expander decomposition, where given a graph $G$ of $m$ edges and a parameter $\phi$, our algorithm finds a partition of the vertices into clusters such that each cluster induces a subgraph of conductance at least $\phi$ (i.e. a $\phi$ expander), and only a $\widetilde{O}(\phi)$ fraction of the edges in $G$ have endpoints across different clusters. Our algorithm runs in $\widetilde{O}(m/\phi)$ time, and is the first nearly linear time algorithm when $\phi$ is at least $1/\log^{O(1)} m$, which is the case in most practical settings and theoretical applications. Previous results either take $\Omega(m^{1+o(1)})$ time, or attain nearly linear time but with a weaker expansion guarantee where each output cluster is guaranteed to be contained inside some unknown $\phi$ expander. Our result achieve both nearly linear running time and the strong expander guarantee for clusters. Moreover, a main technique we develop for our result can be applied to obtain a much better \emph{expander pruning} algorithm, which is the key tool for maintaining an expander decomposition on dynamic graphs. Finally, we note that our algorithm is developed from first principles based on relatively simple and basic techniques, thus making it very likely to be practical.
1 Introduction
Expander decomposition formalizes clustering as a trade-off between internally well-connected clusters and few cross-cluster edges, with applications in graph algorithms and practice. This paper combines a strong induced-expansion guarantee with near-linear running time in the practical parameter regime, and applies its technique to expander pruning.
1 Introduction
- Expander decomposition partitions vertices into clusters with high induced conductance and few edges between clusters, a bicriteria notion used in graph algorithms and practical clustering.An ideal decomposition has conductance at least φ in every cluster and O(φm log n) crossing edges.Source: §1 · p. 2
1.1 Previous Work
- The algorithm addresses a key recursion obstacle: approximate sparsest cuts can be unbalanced, while certifying that no better-balanced sparse cut exists is difficult and prior certificates do not establish that the larger side is an expander.Direct recursion can reach depth Ω(n), taking Ω(n^2) time.Source: §1.1 · p. 3
- Prior approaches leave a gap between speed and guarantee: Spielman and Teng avoid recursing on the larger side but guarantee only containment in an unknown expander, while later work obtains actual expanders in superlinear time.The latter approach takes O(m^(1+O(log log n/√log n)))-type time.Source: §1.1 · pp. 3–4
1.2 Our contribution.
- O(m log^4 m/φ) time yields clusters with conductance at least φ and O(φm log^3 m) cross-cluster edge error; the algorithm also guarantees expansion with original degrees.The guarantee holds with high probability and is the first nearly linear-time result when φ is at least 1/log^O(1) m; its error has the right dependence on φ up to polylogarithmic factors.Source: §1.2 · p. 4
- The same technique improves expander pruning: for up to k ≤ φm/10 online edge deletions, a deterministic algorithm maintains a pruned set with amortized update time O(log m/φ^2) over short sequences.The trimming technique reuses local-flow information across rounds; the authors also describe an extension to weighted graphs.Source: §1.2 · pp. 4–5
2 Overview
The algorithm combines cut-matching with a trimming step to handle unbalanced sparse cuts, certifying the larger side as an expander and recursing only on the smaller side. This yields clusters with a strong expansion guarantee and bounds the edges left between clusters.
2 Overview
- For an unbalanced sparse cut, trimming locally fixes the larger side so it becomes a certified expander, allowing recursion only on the smaller side.The overall recursion has O(polylog n) depth; balanced cuts instead lead to recursion on both sides.Source: §2 · p. 5
- Trimming finds A′ with conductance at least φ/6, retaining volume at least vol(A) − 4|E(A, A)|/φ and leaving at most 2|E(A, A)| edges across the cut.It requires A to be a nearly φ expander and |E(A, A)| ≤ φvol(A)/10; the text notes that approximate balanced sparse-cut methods can provide the needed weak expansion guarantee.Source: §2 · p. 5
- The trimming flow subroutine updates solutions across rounds when the graph and demands change only a little, bounding work by total change rather than round count.This dynamic adaptation of a local flow algorithm is also identified as the key insight behind applications to dynamic graphs.Source: §2 · p. 6
- For a graph G with m edges and parameter φ, the cut-matching step takes O((m log m)/φ) time and has three cases, including the two cut outcomes described here.One cut has conductance O(φ log^2 m) and both sides have volume Ω(m/log^2 m); another has conductance at most c0φ log^2 m, vol(A) ≤ m/(10c0 log^2 m), and A is a nearly φ-expander.Source: §2 · p. 6
- Each final cluster has conductance at least φ/6, and at most O(mφ log^3 m) edges remain between clusters.The recursion has O(log^3 m) levels; the supplied passage gives a per-level running time but its total-time bound is truncated.Source: §2 · p. 7
3 The Trimming Step
This section develops a flow-based method for trimming a nearly expander to extract an induced expander, analyzing exact max flow and an adapted dynamic Unit-Flow approach. The dynamic trimming step bounds removed volume and total running time while leaving a set of conductance at least φ/6 with at most 2|E(A, R)| edges to the outside.
3.1 Preliminaries
- For induced subgraphs, self-loops preserve each node’s original degree, while the flow notation tracks source mass, edge capacities, and sink capacity.A node’s sink is saturated when its received mass reaches its capacity.Source: §3.1 · p. 8
3.2 Finding an Expander inside a Nearly Expander
- If A is a nearly φ expander but G{A} is not a φ/6 expander, the constructed flow problem has no feasible routing.It places 2/φ units of source mass on each boundary edge, gives each node sink capacity deg(v), and assigns each induced edge capacity 2/φ.Source: §3.2 · p. 8
3.3 Slow Trimming
- With exact max flow, trimming finishes in at most 2 rounds and returns a certified φ/6-expander A′ with vol(A′) ≥ vol(A) − 2|E(A,V−A)|/φ and |E(A′,V−A′)| ≤ |E(A,V−A)|.Exact max flow is too slow for the intended efficiency; this analysis supplies the guarantees apart from running time.Source: §3.3 · pp. 10–11
3.4 Efficient Trimming
- Approximate flow may require many trimming rounds, making recomputation from scratch too slow; the method treats successive problems dynamically and reuses prior routing as the graph shrinks.Each round removes a cut, while sources either persist or are removed and new sources arise at the newly exposed cut edges.Source: §3.4 · p. 11
3.4.1 Reusing Flow Information
- The method adapts Unit-Flow, a push-relabel algorithm whose flow and cut invariants support simple routing reuse and amortized analysis.The paper notes that reusing routing naturally involves a directed residual network, which is not straightforward for approximate max-flow methods designed for undirected graphs.Source: §3.4.1 · p. 12
3.4.2 Dynamic Adaptation of Unit-Flow
- Unit-Flow can warm-start from any G-valid state, retaining its pre-flow and node labels, and returns a G-valid solution and a level cut.The method uses these properties to carry state between trimming rounds rather than restarting the flow computation.Source: §3.4.2 · pp. 12–13
- After removing a level cut, the next round restricts the prior flow and labels to the remaining graph and adds source mass on newly exposed cut edges.When prior routing points from a retained node into the removed cut, that routing is truncated so Unit-Flow can reroute the mass within the remaining graph.Source: §3.4.2 · pp. 13–14
- Mass at a retained node increases only when a removed cut edge carried less than 2/φ units toward it, and the increase is at most 4/φ per edge.Mass on nodes removed with the cut is discarded.Source: §3.4.2 · p. 14
- Restricting the flow to the remaining vertices can reduce their mass, so the algorithm adds 2/φ units per cut edge to keep their mass non-decreasing.The flow-valid state is maintained across rounds as vertices are removed.Source: §3.4.2 · p. 14
- The total mass created across rounds is at most 4|E(A, R)|/φ, bounding the volume of the union of removed level cuts.Each round adds at most half the cut volume in mass and destroys at least the cut volume; initial mass is 2|E(A, R)|/φ.Source: §3.4.2 · p. 15
- Unit-Flow takes O(|E(A, R)| log m/φ^2) total time over all trimming rounds.This follows from the bound O(|∆total(·)|h) on total time.Source: §3.4.2 · p. 15
- The retained set A′ has conductance at least φ/6 and at most 2|E(A, R)| edges crossing to V′ − A.The proof also gives vol(A′) ≥ vol(A) − 4|E(A, R)|/φ.Source: §3.4.2 · p. 15
4 Discussion
The discussion extends decomposition and pruning guarantees to weighted graphs and describes applications of the methods in dynamic graph algorithms and graph decomposition. It also identifies open directions, including reducing trimming time and strengthening pruning update guarantees.
4.1 Weighted Graphs
- The weighted decomposition runs in O(m log^5 m/φ) time, produces clusters of conductance at least φ, and has total inter-cluster cut weight O(φW log^3 m).The weighted pruning algorithm handles online deletions of total weight at most φW/10, with total update time O(m log m/φ).Source: §4.1 · pp. 15–16
- The weighted pruning update-time guarantee cannot hold amortized over short update sequences because deleting one very high-weight edge can drastically change conductance.The caveat concerns short sequences, not the stated long-sequence weighted guarantee.Source: §4.1 · p. 16
4.2 Applications
- The stronger guarantee that each cluster induces an expander simplifies spectral sparsification and the analysis of several other algorithms.The cited applications include spectral sketches, Laplacian solvers, and approximate max flow.Source: §4.2 · p. 16
- A 2φ expander decomposition yields a cut of conductance O(φ log^3 m) whose smaller-side volume approximates that of any cut with conductance at most φ, up to a constant factor.The cut is found in eO(m/φ) time.Source: §4.2 · p. 16
- The new expander decomposition improves short-cycle decomposition to time m^(1+O(1/√log n)) with the stated cycle-length and leftover-edge bounds.The resulting bounds are O(n^(1+O(log log n/√log n)), n^(O(log log n/√log n))).Source: §4.2 · p. 17
- The dynamic minimum spanning forest algorithm has worst-case update time O(n^(O(√(log log n/log n)))) in expectation and with high probability.The paper attributes the improved bound to faster expander decomposition and pruning.Source: §4.2 · p. 17
- A fully dynamic low-diameter decomposition achieves amortized update time eO(1/β^2) and amortized inter-cluster edge increase eO(1/β), even against a non-oblivious adversary.Its decomposition is (β, eO(1/β)).Source: §4.2 · p. 17
4.3 Open problems
- Open directions include removing the trimming step’s 1/φ running-time dependency and making pruning’s amortized update time worst-case.The authors also mention reducing inter-cluster edges by a logarithmic factor.Source: §4.3 · p. 18
A Details of Unit-Flow
The appendix adapts a Push-Relabel-based Unit-Flow algorithm for repeated use on dynamically updated graphs. It defines the flow and label invariants, then describes how the algorithm handles excess mass and terminates.
Unit-Flow
- A pre-flow may exceed sink capacity; absorbed mass is min(f(v), T(v)), and excess is the remainder.With no excess at any node, the pre-flow is a feasible flow; the implicit setup uses T(v)=deg(v) and edge capacity 2/φ.Source: A Details of Unit-Flow · p. 22
- Push-Relabel maintains labels so every residual arc from u to v satisfies l(u) ≤ l(v)+1, and pushes excess along eligible arcs.When no eligible arc is available, the algorithm raises the active node’s label.Source: A Details of Unit-Flow · p. 22
- Unit-Flow adapts Push-Relabel by stopping pushes at a label bound h and limiting moved excess at each node to its degree.Initial excess placed by the source function is exempt from the degree bound.Source: A Details of Unit-Flow · pp. 22–23
- The active-vertex queue is ordered by non-decreasing labels, with per-label linked lists supporting queue updates in O(1) time.This ordering ensures a push target has no existing excess.Source: A Details of Unit-Flow · p. 23
- Unit-Flow maintains a valid pre-flow and labels; at termination, nodes below level h have no excess and therefore obey sink capacity.The stated validity invariants include saturation of arcs when endpoint labels differ by more than one.Source: A Details of Unit-Flow · pp. 23–24
A.1 Proof of Lemma 3.4
The proof uses terminal labels to form nested level sets and searches for a level cut with a suitable boundary. A region-growing contradiction establishes that such a level exists.
A.1 Proof of Lemma 3.4
- When the top level is empty, no vertex has positive excess, giving case (1) of the lemma.Source: §A.1 · p. 24
- The proof forms level cuts S_i from vertices whose terminal labels are at least i, then classifies crossing edges by their label and flow properties.Edges spanning a label difference greater than one are saturated in the downhill direction.Source: §A.1 · p. 24
- If the boundary-edge condition failed at every level, region growth would force vol(S_1) to exceed 2m, contradicting vol(S_1) ≤ 3m/2.The argument starts from level h, where the top-level set has volume at least one.Source: §A.1 · p. 24
A.2 Warm-up proof of Lemma 3.7
The warm-up bounds one Unit-Flow call by charging its work to mass. Pushes and relabels each incur O(h) total charge per unit of mass.
A.2 Warm-up proof of Lemma 3.7
- A single Unit-Flow call runs in O(|∆(·)|h) time.The bound allows initial mass at a vertex to exceed twice its degree.Source: §A.2 · p. 24
- The analysis charges each iteration to a push or relabel, then charges that operation’s work to the mass.Each unit of mass receives O(h) total charge.Source: §A.2 · p. 25
- The potential Λ decreases by ψ when ψ units are pushed and increases only on relabels, enabling push work to be charged to mass.Initial excess and absorbed mass each receive O(h) total charge across relabel-related increases.Source: §A.2 · p. 25
A.3 Proof of Lemma 3.7
The proof bounds the round-based trimming step by charging its work to pushes, relabels, and added mass. The resulting running time depends on the total mass created across rounds.
A.3 Proof of Lemma 3.7
- The proof charges operations to pushes and relabels, then charges pushes to increases in the potential function.This follows the earlier proof strategy, adapted to mass added between rounds.Source: §A.3 · p. 25
- Each unit of mass added between rounds increases Λ by at most O(h), and is charged only once for that increase.The increase is bounded by the node's label, which is at most O(h).Source: §A.3 · p. 25
- O(|∆total(·)|h) is the total running time, with O(|∆total(·)|) additional time for sweep cuts.The total volume of removed cuts is bounded by |∆total(·)|.Source: §A.3 · p. 25
A.4 Proof of Theorem 1.3: expander pruning
The expander-pruning algorithm extends trimming to edge deletions by updating a flow problem on the original graph and removing vertices from the maintained set. Its guarantees relate the deleted edges to the resulting expander and running time.
A.4 Proof of Theorem 1.3: expander pruning
- If G′{A} is not a φ/6 expander, the specified flow problem on G{A} is infeasible.The proof compares source mass inside a low-conductance cut with the flow capacity that can absorb or leave that cut.Source: §A.4 · p. 26
- After deletions D, the maintained induced subgraph G′{A′} is a φ/6 expander, and the algorithm outputs P = V − A′.It updates the source function for deleted edges while running Unit-Flow on G{A}.Source: §A.4 · p. 27
- For each deleted edge, the algorithm adds 4/φ units of source mass at each endpoint before running Unit-Flow.The sink capacity at each node is its degree, and each edge has capacity 2/φ.Source: §A.4 · p. 27
- O(|D| log n/φ^2) bounds the total running time of expander pruning.The bound is expressed as O(|∆total(·)|h) in the lemma.Source: §A.4 · p. 27
B The Cut-Matching Step
The cut-matching step works on a subdivision graph and iteratively removes low-conductance sets while updating an implicit multicommodity flow. The analysis gives a nearly φ-expander guarantee for the remaining set or a balanced cut, in O(m log m/φ) time.
B The Cut-Matching Step
- The algorithm uses the subdivision graph GE, which inserts a split node on every edge of G.For the specified subsets, volume, cut-size, and conductance in GE agree with those in G up to a constant factor of 2.Source: B The Cut-Matching Step · pp. 27–28
- The algorithm implicitly updates F while maintaining that it is routable with congestion ct, where c = 1/(φT).The flow matrix is initialized as the identity and updated across rounds.Source: B The Cut-Matching Step · pp. 27–28
- The algorithm stops when the removed set R exceeds the volume threshold or after T = Θ(log^2 m) rounds.Each returned low-conductance set S is moved from A into R.Source: B The Cut-Matching Step · pp. 27–28
- The remaining A is a φ nearly expander when ψ(t) ≤ 1/16m^2, and the condition holds after T rounds with high probability.The proof uses bounded congestion and the small volume of R to establish expansion.Source: B The Cut-Matching Step · pp. 28–29
- O(m log m/φ) is the total running time of the cut-matching step.The theorem's cases include a balanced cut with conductance O(φ log^2 m), or a remaining nearly φ-expander under the stated volume bound.Source: B The Cut-Matching Step · p. 29
B.1 Implicitly Updating Multi-commodity Flows
The update step uses projected flow vectors to choose source and target sets, routes a flow between them, and converts that flow into a matching. Averaging matched flow vectors updates the implicit multicommodity flow while controlling its congestion and potential.
B.1 Implicitly Updating Multi-commodity Flows
- Each round finds source and target sets, routes mass between them, and uses the resulting matching to update F.The procedure is a variant of one cut-matching-framework round.Source: §B.1 · p. 29
- The source and target sets are selected by projecting flow vectors onto a random direction and separating their projected values.The separation value η lies between the projections for the two sets.Source: §B.1 · pp. 29–30
- The flow matrix F is not explicitly maintained, but all projected values can be computed in O(m log^2 m).For an m-dimensional vector r, the projections can be computed in O(mt) time.Source: §B.1 · pp. 29–30
- The routing step uses unit sources in Al, unit-capacity sinks in Ar, and edge capacities U = 1/(φ log^2 m).The flow problem can be solved using push-relabel or blocking-flow algorithms with labels bounded by h = 1/(φ log m).Source: §B.1 · p. 30
- For each matched pair, the update replaces a flow vector with the average of the two matched vectors.The update is Ft+1(xe) = Ft(xe)/2 + Ft(xh)/2, and the resulting flow remains routable with congestion c(t + 1).Source: §B.1 · p. 30
- The potential decreases by a (1−Ω(1/ log m)) factor per round with high probability.Before removing S, the potential is also reduced by at least 1, according to Lemma B.9.Source: §B.1 · p. 30