Infinite Lewis Weights in Spectral Graph Theory

02/12/2023
by   Amit Suliman, et al.
0

We study the spectral implications of re-weighting a graph by the ℓ_∞-Lewis weights of its edges. Our main motivation is the ER-Minimization problem (Saberi et al., SIAM'08): Given an undirected graph G, the goal is to find positive normalized edge-weights w∈ℝ_+^m which minimize the sum of pairwise effective-resistances of G_w (Kirchhoff's index). By contrast, ℓ_∞-Lewis weights minimize the maximum effective-resistance of edges, but are much cheaper to approximate, especially for Laplacians. With this algorithmic motivation, we study the ER-approximation ratio obtained by Lewis weights. Our first main result is that ℓ_∞-Lewis weights provide a constant (≈ 3.12) approximation for ER-minimization on trees. The proof introduces a new technique, a local polarization process for effective-resistances (ℓ_2-congestion) on trees, which is of independent interest in electrical network analysis. For general graphs, we prove an upper bound α(G) on the approximation ratio obtained by Lewis weights, which is always ≤min{diam(G), κ(L_w_∞)}, where κ is the condition number of the weighted Laplacian. All our approximation algorithms run in input-sparsity time Õ(m), a major improvement over Saberi et al.'s O(m^3.5) SDP for exact ER-minimization. Finally, we demonstrate the favorable effects of ℓ_∞-LW reweighting on the spectral-gap of graphs and on their spectral-thinness (Anari and Gharan, 2015). En-route to our results, we prove a weighted analogue of Mohar's classical bound on λ_2(G), and provide a new characterization of leverage-scores of a matrix, as the gradient (w.r.t weights) of the volume of the enclosing ellipsoid.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset

Sign in with Google

×

Use your Google Account to sign in to DeepAI

×

Consider DeepAI Pro