Directed graph sparsifiers reveal limits of balance for spectral approximation
Beyond Cut Balance: Spectral Sparsification of the Nonlinear Directed Laplacian
Data Structures and Algorithms
Summary
The paper studies ways to simplify complex directed networks while keeping key properties intact. The authors find that having a balanced flow of connections in both directions of every split part of the network does not always allow for a very efficient simplification that preserves detailed energy-related information. Surprisingly, they show that some highly unbalanced networks called tournaments can be simplified effectively despite lacking this balance. Their work also links this simplification to preserving important flow optimization costs in the network, meaning the simplifier keeps more information than just simple cut measures.
Directed graphCut balanceSpectral sparsificationNonlinear LaplacianEulerian digraphTournament graphSubgraph reweightingConvex dualityFlow optimizationCut sparsifier
Authors
Yuichi Yoshida
Abstract
Digraphs with constant cut balance admit nearly linear directed cut sparsifiers. This condition requires the total arc weights in the two directions of every cut to be within a constant factor of each other. We ask whether this condition also permits nearly linear spectral sparsification with respect to the energy of the nonlinear directed Laplacian. For a weighted digraph $G=(V,E,w)$, let \[ Q_G^+(x)=\sum_{(u,v)\in E}w_{uv}(x_u-x_v)_+^2, \qquad (t)_+:=\max\{t,0\}. \] This energy agrees with the outgoing-cut function on binary vectors. A spectral sparsifier is a nonnegatively reweighted subgraph that preserves $Q_G^+(x)$ within a factor of $1\pm\varepsilon$ simultaneously for all $x\in\mathbb R^V$. We show that cut balance alone does not yield nearly linear spectral sparsifiers: for constant error, the worst-case support size for simple unweighted Eulerian digraphs is $\widetildeΘ(n^{3/2})$, although Eulerian digraphs are perfectly cut-balanced and admit nearly linear directed cut sparsifiers. In contrast, we prove that every $n$-vertex tournament has a spectral sparsifier with $\widetilde O(n/\varepsilon^3)$ arcs, without any assumption on its cut balance. This includes the transitive tournament, whose cut balance is unbounded. Thus perfect balance does not guarantee nearly linear spectral sparsification, while unbounded imbalance does not preclude it. Finally, we use convex duality to show that preserving $Q_G^+$ also preserves, for every feasible demand vector, the optimum quadratic cost of a nonnegative flow. Hence the guarantee contains information beyond directed cut values.