Beyond Cut Balance: Spectral Sparsification of the Nonlinear Directed Laplacian

1 Introduction

• Because arc contributions depend on the ordering of real potentials, preserving the nonlinear energy imposes constraints beyond those tested by binary cut indicators.The energy extends the outgoing-cut function from binary vectors to arbitrary potentials, and a sparsifier must approximate it across all potential orderings.Source: §1 · p. 3

1.1 Our results

• For fixed error, simple Eulerian digraphs have worst-case spectral sparsifier size ẽΘ(min{m, n^3/2}), despite admitting nearly linear cut sparsifiers.Eulerian digraphs are perfectly cut-balanced; the cut–spectral separation also occurs on strongly connected examples.Source: §1 · p. 3, §1.1 · p. 4
• Every tournament has a nearly linear-size spectral sparsifier without regularity, strong connectivity, or cut-balance assumptions.The transitive tournament has unbounded cut balance, yet the tournament guarantee applies to it.Source: §1.1 · p. 4

Quadratic costs of nonnegative flows.

• Spectral approximation preserves the optimal quadratic cost for routing every demand feasible in the original graph using nonnegative arc flows.Feasibility transfers to the sparsifier, but the result does not claim that the optimum flows themselves are close.Source: Quadratic costs of nonnegative flows · p. 5

1.2 Technical overview

• The technical overview contrasts multivalued-potential lower bounds for Eulerian graphs with cycle-based sampling, then uses directed paths to sparsify tournaments.The tournament approach addresses why the cycle-based sampling guarantee alone gives no useful bound even for the transitive tournament.Source: §1.2 · p. 5, §1.2.2 · p. 7

1.2.1 Eulerian digraphs: matching lower and upper bounds

• In the Eulerian lower-bound construction, multivalued potentials preserve selected unit drops while spreading return drops across many arcs, forcing a constant fraction of arcs to remain.For the matching upper bound, short directed-cycle decomposition and row sampling yield support ẽO(min{m, n^3/2}) for constant error.Source: §1.2.1 · pp. 6–7

1.2.2 Tournaments: nearly linear sparsification

• In tournaments, directed paths constrain arc energies jointly, and distance-based sampling in the transitive case limits an arc’s energy share to O(1/D) at endpoint distance Θ(D).Grouping arcs by endpoint distance and sampling with probability min{1, ρ/D} gives expected sample size O(nρ log(2n)).Source: §1.2.2 · pp. 8–9
• For transitive tournaments, endpoint-distance sampling yields eO(n/ε^3) arcs by bounding uniform error through Gaussian width and O(log n) levels of potential energy.The bound balances local comparison errors at R ≍ ρ^1/3, giving EA ≤ eO(ρ^-1/3).Source: §1.2.2 · pp. 9–11
• Every n-vertex tournament T has a (1 ± ε)-spectral sparsifier with eO(n/ε^3) arcs, using routing and an undirected correction approximated by effective-resistance sampling.Each approximation uses a sufficiently small constant times ε/log(2n) as its error parameter; routing orders vertices by nondecreasing outdegree.Source: §1.2.2 · pp. 11–12

1.3 Relation to previous work

• Prior work gave cut sparsifiers with size depending on cut balance, but the Eulerian lower bound rules out a nearly linear spectral guarantee even for simple, unweighted digraphs with cut balance one.The authors note that this lower bound does not characterize sparsifier size for weighted or generally β-balanced digraphs.Source: §1.3 · p. 12

1.4 Organization

• The paper proceeds from energy, flow duality, and sampling criteria to Eulerian bounds, then proves transitive-tournament sparsification and extends it to arbitrary tournaments.The Gaussian-matrix estimates appear in the appendix.Source: §1.4 · p. 13

2.1 The energy of the nonlinear directed Laplacian and its sparsifiers

• The sparsification model represents relative error through normalized arc-energy vectors for the nonlinear directed energy.The section also defines the minimum support size of a spectral sparsifier.Source: §2.1 · pp. 13–14

2.2 Quadratic costs of nonnegative flows

• Preserving directed energy within a multiplicative factor preserves the optimum quadratic cost of routing every feasible demand with nonnegative flows.The dual formula also characterizes infeasible demands by infinite optimum cost.Source: §2.2 · pp. 14–15

2.3 Expected Gaussian width after random restriction

• After independently sampling arcs, the expected Gaussian width is measured on the coordinates where two independent samples disagree.A sampling comparison bounds this quantity using the Gaussian supremum on the restricted coordinates.Source: §2.3 · pp. 15–16

2.4 Independent sampling from an expected Gaussian-width bound

• An upper bound on expected Gaussian width yields an independent-sampling spectral sparsifier with support proportional to the total inclusion probability.Theorem 2.3 supplies this general sampling criterion.Source: §2.4 · p. 16

3 The n3/2 Threshold for Simple Eulerian Digraphs

• For constant error, the worst-case support for simple Eulerian digraphs is eΘ(min{m, n^3/2}).The upper and lower bounds determine the worst-case size for every m.Source: §3 · p. 17, §3.2 · p. 19

3.1 Upper bound by removing short directed cycles

• Removing short directed cycles leaves a sparse residual; row sampling the removed arcs gives the upper bound after choosing M = Θ(n^3/2/ε).The cycle-removal step preserves the Eulerian property, and short cycles bound the complexity used in sampling.Source: §3.1 · pp. 17–18

3.2 Lower bound via cyclic blow-ups

• With k = 8b + 2, cyclic blow-ups force every vertex to retain at least 3b/4 arcs, yielding an Ω(n^3/2) support lower bound.The construction has n = (8b + 2)b ≤ 10b^2 vertices.Source: §3.2 · pp. 18–20

4 Sampling Transitive Tournaments by Endpoint Distance

• Every n-vertex transitive tournament has a spectral sparsifier with eO(min{n^2, n/ε^3}) arcs.The construction uses endpoint-distance ranges and a general sampling criterion.Source: §4 · p. 20
• The construction chooses inclusion probabilities across endpoint-distance ranges and applies the general sampling criterion to obtain the sparsifier.The proof bounds Gaussian width for one range before setting probabilities across all ranges.Source: §4 · p. 20
• The range bound is developed by decomposing squared differences into bilinear terms, assigning arcs to consecutive intervals, and bounding the resulting forms.The proof uses energy constraints, deterministic averaging, elimination of endpoint vectors, and moment bounds.Source: §4 · p. 20

4.1 A Gaussian-width bound for one endpoint-distance range

• Arcs with endpoint distance in [D, 2D) are sampled independently with probability p = ρ/D.The parameter ρ lies in [1, D] and controls expected sample size.Source: §4.1 · pp. 20–21
• The expected Gaussian supremum for a distance range is bounded by a polylogarithmic factor times ρ^-1/3.This estimate determines the inclusion probability for the range.Source: §4.1 · pp. 20–21
• The disagreement indicators restrict the Gaussian-width calculation to sampled coordinates, and each of the two Bernoulli samples retains at most nρ arcs in expectation.The range contains at most nD arcs and uses p = ρ/D.Source: §4.1 · p. 21

4.2 Combining the distance ranges to obtain a sparsifier

• For any 0 < η ≤ 1/2, distance-based inclusion probabilities achieve total inclusion probability eO(min{n^2, n/η^3}) while targeting expected Gaussian width at most η.Taking η to be a sufficiently small multiple of ε then gives a sparsifier by Theorem 2.3.Source: §4.2 · p. 21
• eO(min{n^2, n/ε^3}) arcs suffice for a (1 ± ε)-spectral sparsifier of the transitive tournament when 0 < ε ≤ 1/2.The bound is stated for the transitive tournament TTn.Source: §4.2 · p. 22
• The proof applies Theorem 2.3 after setting η = min{csamp, 1}ε, giving a sparsifier whose arc count is O(∑e πe).Here csamp is the constant in Theorem 2.3.Source: §4.2 · p. 22

4.3 Decomposing squared differences and grouping arcs into vertex intervals

• The proof separates each distance range into bilinear contributions indexed by value-tree nodes and consecutive vertex intervals.A value interval indexes terms in squared differences; a vertex interval groups arc endpoints with Θ(D) intervening vertices.Source: §4.3 · pp. 22–23

4.3.1 A binary tree on the attained values

• The balanced binary tree on attained values gives an exact decomposition of each squared difference into contributions from value gaps and internal nodes.The tree has height O(log(2m)), where m is the number of consecutive gaps between distinct attained values.Source: §4.3.1 · p. 23
• Summing clipped energies over the value tree gives a logarithmic energy bound, also for pairwise disjoint vertex sets.The lemmas state bounds for a single set and more generally for a family of pairwise disjoint subsets.Source: §4.3.1 · p. 23

4.3.2 Consecutive vertex intervals for ED

• Each arc in a dyadic distance range is assigned to a consecutive vertex interval containing its endpoints, with intervals arranged into a constant number of disjoint families.This organization lets clipped energies be summed using the value-tree bound.Source: §4.3.2 · p. 24
• For 32 ≤ D < n, the construction partitions vertices into blocks of size between D/32 and D/8 and groups arcs by their endpoint blocks.The resulting intervals have Θ(D)-sized endpoint and middle portions, and their arc sets partition ED.Source: §4.3.2 · p. 24

4.4 Reducing the Gaussian-width bound to endpoint bilinear forms

• The Gaussian-width estimate is reduced to local bilinear contributions on endpoint blocks, normalized by clipped energy on their containing intervals.The resulting uniform endpoint supremum does not depend on the potential or its value tree.Source: §4.4 · p. 24

4.4.1 Energy constraints on the endpoint vectors

• Within-block arcs and paths through intervening vertices impose quadratic constraints on the endpoint vectors.The path constraint accounts for the Θ(D) intervening vertices.Source: §4.4.1 · p. 25
• Lemma 4.6 bounds endpoint-vector energy using the within-block and intervening-path constraints when both supports are nonempty.The bound holds for a universal constant c > 0.Source: §4.4.1 · p. 25
• The threshold constraint bounds the norm of the endpoint vector with smaller support, while ordered differences and threshold control are used for the other vector.The support-size norm bound is stated for nonnegative vectors with at most s nonzero coordinates.Source: §4.4.1 · p. 25

4.4.2 A uniform bound for the endpoint bilinear forms

• The random endpoint matrix defines a supremum over both nonnegative vectors and their support sets after the matrix is realized.Theorem 4.8 bounds the expected maximum of this supremum over intervals under its stated D and ρ conditions.Source: §4.4.2 · p. 26

4.4.3 Summing the clipped contributions

• Homogeneity bounds each tree-node contribution by the endpoint supremum times clipped energy, and the squared-difference decomposition sums those contributions.Summing clipped energies within the constant number of disjoint interval families extends the bound across the distance range.Source: §4.4.3 · pp. 26–27
• The value tree may depend on the potential, but the maximum endpoint supremum does not, allowing the bound to hold uniformly over potentials.The proof takes the supremum over positive-energy potentials before taking expectation.Source: §4.4.3 · p. 27

4.5 Bounding the endpoint bilinear forms

• With R subblocks, comparison errors contribute the first term of the bound and the constant number of unpaired subblocks contribute the second.Balancing these terms gives R ≍ ρ^1/3 and a ρ^-1/3 bound.Source: §4.5 · p. 27

4.5.1 A deterministic averaging inequality

• Averaging across a middle subblock bounds the endpoint deviations, while coefficient-total imbalance and unpaired positive terms remain to be controlled.The last three subblocks are left unpaired because the two-subblock shift leaves terms without partners and the final block may be larger.Source: §4.5.1 · pp. 27–28
• The averaging inequality controls a bilinear form using forward decreases of a nonnegative vector under a one-sided energy constraint, without requiring a total-variation bound.The endpoint-vector application reverses the vertex order for one vector.Source: §4.5.1 · pp. 27–28

4.5.2 Eliminating the endpoint vectors and support sizes

• The deterministic inequality turns endpoint-vector constraints into a bound involving only the matrix, eliminating dependence on the vectors and their support size.The remaining quantities are the matrix norm, coefficient-total differences, and boundary sums.Source: §4.5.2 · p. 29

4.5.3 Moment bounds and the choice of the number of subblocks

• The proof fills missing matrix entries with independent mean-zero copies so all entries share a law, enabling comparisons across equal-sized subblocks.Conditional Jensen bounds the original supremum's moment by that of the completed matrix.Source: §4.5.3 · p. 30
• The random-matrix estimates bound the matrix norm, coefficient-total differences, and unpaired-subblock terms before their contributions are balanced.For unequal endpoint supports, transposing the matrix and reversing coordinate orders exchanges the energy constraints while preserving the entry law.Source: §4.5.3 · pp. 31–32
• ∥AW∥Lq ≤ C√q ρ^-1/3 follows by choosing R = ⌈ρ^1/3⌉ and balancing R/ρ against 1/R.The bound is substituted into the estimate for E maxW∈WD AW to establish Theorem 4.8.Source: §4.5.3 · p. 32

5 From Transitive Tournaments to Arbitrary Tournaments

• Every n-vertex tournament has a spectral sparsifier with eO(min{n^2, n/ε^3}) arcs.The construction uses common sampling indicators for the signed and undirected terms of each pair.Source: §5 · p. 32, §5.5 · p. 37

5.2 An energy identity using pairs whose orientations disagree

• The original tournament’s energy decomposes into a fixed-sign sum of transitive-tournament arc energies and an undirected correction for disagreeing orientations.The correction is bounded by the original directed energy.Source: §5 · p. 32, §5.2 · pp. 34–35

5.1 Energy domination after ordering by outdegree

• Ordering vertices by outdegree yields a transitive tournament whose directed energy is at most an O(log n) factor larger, via routing arcs along short paths.The proof bounds routing congestion using reciprocal-degree estimates.Source: §5.1 · pp. 32–33

5.3 Sampling the sum with fixed signs

• The signed sum can be sampled with probabilities shared by arcs at the same endpoint distance, controlling normalized error over potentials.The sampling bound applies to arbitrary fixed signs.Source: §5.3 · p. 35

5.4 Probability monotonicity and undirected sampling

• For the undirected correction, effective-resistance sampling is combined with probability monotonicity, which permits increasing inclusion probabilities while retaining the sampling guarantee.The independent spectral-sampling result applies when probabilities meet the stated lower bounds.Source: §5.4 · pp. 36–37

5.5 Proof of the tournament theorem

• The proof uses common Bernoulli indicators for each pair’s signed and undirected contributions, yielding a nonnegatively weighted sampled subgraph.The two approximations are combined with energy comparisons to obtain the tournament sparsifier.Source: §5.5 · pp. 37–38

• The appendix proves moment estimates for both the maximum retained-entry count and a Bernoulli-restricted Gaussian matrix’s operator norm.The count estimate uses stochastic domination and Bernstein’s inequality; the norm estimate uses a trace expansion over closed walks and pairings.Source: A Probabilistic Estimates for… · p. 41
• The maximum-count bound follows by applying a tail estimate across the indexed counts and integrating the resulting tail bound.The proof uses stochastic domination, Bernstein’s inequality, and a bound on the maximum.Source: A Probabilistic Estimates for… · p. 41
• The operator-norm estimate expands a trace into closed walks, counts compatible walks through pairings, and then bounds the resulting moment.The argument uses independence and Gaussian scalar moments, followed by a 2q-th root bound.Source: A Probabilistic Estimates for… · p. 41