Towards Optimal Effective Resistance Estimation
Authors: Rajat Vadiraj Dwaraknath
Ishani Karmarkar
Aaron Sidford
Venue: NeurIPS 2023 poster (2023)
Keywords: effective resistances
spectral sketch
fine-grained complexity
triangle detection
numerical linear algebra
TL;DR: We provide improved algorithms and conditional lower bounds for the problem of estimating effective resistances between nodes in an undirected graph, and apply the techniques to more general problems involving general positive semidefinite matrices.

Abstract: We provide new algorithms and conditional hardness for the problem of estimating effective resistances in $n$-node $m$-edge undirected, expander graphs. We provide an $\widetilde{O}(m\epsilon^{-1})$-time algorithm that produces with high probability, an $\widetilde{O}(n\epsilon^{-1})$-bit sketch from which the effective resistance between any pair of nodes can be estimated, to $(1 \pm \epsilon)$-multiplicative accuracy, in $\widetilde{O}(1)$-time. Consequently, we obtain an $\widetilde{O}(m\epsilon^{-1})$-time algorithm for estimating the effective resistance of all edges in such graphs, improving (for sparse graphs) on the previous fastest runtimes of $\widetilde{O}(m\epsilon^{-3/2})$ [Chu et. al. 2018] and $\widetilde{O}(n^2\epsilon^{-1})$ [Jambulapati, Sidford, 2018] for general graphs and $\widetilde{O}(m + n\epsilon^{-2})$ for expanders [Li, Sachdeva 2022]. 
We complement this result by showing a conditional lower bound that a broad set of algorithms for computing such estimates of the effective resistances between all pairs of nodes require $\widetilde{\Omega}(n^2 \epsilon^{-1/2})$-time, improving upon the previous best such lower bound of $\widetilde{\Omega}(n^2 \epsilon^{-1/13})$ [Musco et. al. 2017]. Further, we leverage the tools underlying these results to obtain improved algorithms and conditional hardness for more general problems of sketching the pseudoinverse of positive semidefinite matrices and estimating functions of their eigenvalues.

Towards Optimal Effective Resistance Estimation
Rajat Vadiraj Dwaraknath Stanford University rajatvd@stanford. edu
Ishani Karmarkar Stanford University ord. edu
Aaron Sidford Stanford University
sidford@stanf ord. edu
Abstract
We provide new algorithms and conditional hardness for the problem of estimating effective resistances in n-node m-edge undirected, expander graphs. We provide an O(me-1)-tine algorithm that produces with high probability, an ))- bit sketch from which the effective resistance between any pair of nodes can be estimated, to (1 i c)-multiplicatiive accuracy, in -1m)- Consequently, we obtain an O(mc-1)-timee algorithm for estimating the effective resistance of all edges in such graphs, improving (for sparse graphs) the previous fastest runtimes of Óme 3/2) [Chu al. 2018] and Ö(n2c-1) [Jambulapati, Sidford 2018] for general graphs and Õ(m + nc=?) 2) for expanders [Li, Sachdeva 2022]. We complement this result by showing conditional lower bound that broad set algorithmss for computing such estimates the effective resistances between all pairs of nodes require 0(n2e-11 -tmmmm, improving upon the previous best such lower bound of U(n= -/113) [Musco et. al. 2017]. Further, we leverage the tools underlying these results to obtain improved algorithms and conditional hardness for more general problems of sketching the pseudoinverse of positive semidefinite matrices and estimating functions their eigenvalues.
1 Introduction
In weighted, undirected graph G the effective resistance between a pair of vertices and b, denoted ra(a, b). defined as the energy of unit of electric current sent from b in the natural resistor network induced by G. Effective resistances arise for broad set of graph processing tasks and have multiple equivalent definitions. For example, Ta (a, is proportional the expected roundtrip commute time between a and 1 in the natural random walk induced on the graph and when {a, b} is an edge the graph, it is proportional the probability that the edge in random spanning tree.
Effective resistances also form a particular class of metrics on the vertices [1,2] 2] and are a key measure of proximity between vertex pairs. Correspondingly, effective resistances can arise in a variety of data analysis tasks. For example, effective resistances have been used in social network analysis for measuring edge centrality social networks [3] well as for measuring chemical distances [4].
Effective resistances have a broad range of algorithmic implications. Sampling edges of a graph using effective resistance is known to efficiently produce cut and spectral sparsifiers (sparse graphs which approximately preserve cuts, random walk properties, and more) [5-7]. Effective resistance- based graph sparsifiers have also been applied develop fast graph attention neural networks [8], to design graph convolutional neural networks for action recognition [9], to sample from Gaussian graphical models [10], and beyond [11, 12). Effective resistances have also been used in algorithms for maximum flow problems, [13-16, 16-18), sampling random spanning trees [19-21], and graph partitioning [22,23] 23). More recently, effective resistances have also been used analyze the problem of oversquashing in GNNs and in designing algorithms to alleviate oversquashing [24-26] and have been applied increase expressivity when incorporated edge features into certain GNNs [27].
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

Algorithms. Given the broad utility of effective resistances, there have been many methods for estimating and approximately compressing them [5. 28.31. In this paper, our main focus is the following effective resistance estimation problem. (We use Re y shorthand for (1 c)y & & (1 + y and assume all edge weights in graphs are positive. See Section 2 for notation more broadly).
Definition 1 (Effective Resistance Estimation Problem). In the effective resistance estimation problem we are given undirected, weighted graph G = (V, E, w), set of vertex pairs S = V x V. and e E (0, 1) and must output i E IR3 such that with high probability (whp.), ((a.b) Re ra(a, b) for all (a, b) E S.
The state-of-the-an runtimes for solving the effective resistance estimation problem on n-node, m-edge graphs are given in Table 2. To contextualize these results, consider the special case of estimating the effective resistance of a graph's edges, i.e., when S E. This special case appears in many of the aforementioned applications, e.g., [13-15, 19, 20J. The state-of-the-art runtimes for this problem are Ō(n²c1)) 1) due to [28] and Ö(me-1.5 due to [30]. A major open problem is whether improved runtimes, e.g.. (m (which would subsume prior work), are attainable.
One of the main results of this paper is resolving this open problem in the case of well-connected graphs, i.c., expanders. Expanders are a non-trivial, previously studied, special case that is often the first step or key component for developing more general algorithms [32]. In particular we provide an Ómme- (G)) time algorithm where
measure of the graph's 's connectivity. Previously, the only non-trivial improvement in this setting was an independently obtained runtime of Ö(m + ne n (G)) )/2)) for graphs with R (G) Õ(1) [29]. We improve upon the result of [29] for sparse enough graphs and, as we explain in Section 1.1, we can almost match the result of [29] (up to
an m1) factor) in dense graphs.
Interestingly, we obtain our main result by providing new effective resistance sketch algorithms.
Definition (Effective Resistance Sketch). We call a randomized algorithm an (Ta, Ta s)-efecctive resistance sketch algorithm if given input n-node, m-edge undirected, weighted graph G (V,E, w) and c E (0, 1) in time (T, c)) it creates a binary string of length (ss(G. c)) from which when queried with any a, b E V, it outputs Fa,s Re rc(a, b) whp. in time (Ta(G.
Effective resistance sketching algorithms immediately imply algorithms for the effective resistance estimation problem. We obtain our result by obtaining an (0(mc-1), Ö(1) ()n - resistance sketch algorithm for expanders (see Section 1.1 for a comparison prior work).
Lower Bounds. Given the central role of effective resistance estimation and the challenging open- problem of determining its complexity, previous work has sought complexity theoretic lower bounds for the problem. [33] showed a conditional lower bound of that algorithm that computes effective resistances in used to obtain a subcubic algorithm for the triangle detection problem, that we define below.
for the problem by showing for some d > 0 time could be
Definition 3 (Triangle Detection Problem). Given an n-node undirected unweighted graph G = (V, E), determine whether there are distinct o, b, C V with {a,b) E, (b,c] E E and {c, E E.
Currently, the only known subcubic algorithms for the triangle detection problem leverage fast matrix multiplication (FMM) and therefore their practical utility (in the worst case) is questionable.
Theorem 1 (Informal, [34]). Given algorithu which solves the triangle detection problem in subcubic time, we can produce a subcubic algorithm, which only performs combinatorial operations and uses the triangle detection algorithm, for Boolean matrix multiplication (BMM) and additional problems which currently are not known to be solvable subcubicly without FMM
This theorem implies that any subeubic algorithm for triangle detection that doesn't use FMM implies a subcubic BMM algorithm that doesn't 't use FMM. Consequently, subcubic triangle detection is a common hardness assumption used to illustrate barriers towards improving non-FMM based methods, e.g., the effective resistance estimation algorithms of this paper.
'hile our algorithms for the effective resistance estimation problem (Definition 1) were obtained indpendently, our writing and discussion of effective resistance sketch by their paper. We provide more complete comparison of our work with prior results in Table 1.
algorithms (Definition 1) was informed
2

---

In this paper take key step towards closing the gap between the best known running times for effective resistance estimation and lower bounds by improving the conditional lower bound of Mnn2 to (2( for randomized algorithms. We show this lower bound holds even for expander graphs, and hence our effective resistance estimation algorithm (as well as [28]) are optimal up --122ffatoo among non-FMM based algorithms, barring a major breakthrough in BMM.
Broader Linear Algebraic Tools. The effective resistance between vertex a and vertex in graph G has natural linear algebraic formulation. For all a, b E V it is known that ra(a,)) b) = 8, L 5 where LG E I VxV is a natural matrix associated with G known as the Laplacian matrix and 8a.b Ca cb (see Section 2 for notation). Thus, sketching effective resistances can be viewed as problems of preserving information about subsets entries of the pseudoinverse of Laplacian.
Both our algorithms and lower bounds develop more general tools for handling related problems for more general (not-necessarily Laplacian) matrices. On the algorithmic side, show our techniques can also lead to algorithms and data structures for computing certain quadratic forms involving well-conditioned SDD and PSD matrices. On the hardness side, we show our techniques also improve triangle detection hardness bounds for estimating various properties of the singular values of a matrix.
Paper Organization. In the remainder of the introduction we provide more precise statement and comparison of our results in Section 1.1. In the remainder of the paper we cover preliminaries in Section 2. present upper bounds in Section and present lower bounds in Section Omitted proofs and additional discussion of related proofs are deferred to the supplementary material.
1.1 Our Results
Algorithms. Here we outline our main algorithmic results pertaining to effective resistance sketching and estimation, and Section 3 we describe a extensions of our work to broader linear algebraic problems involving SDD and PSD matrices. Our main algorithmic result is effective resistance sketch for expanders, term which is used refer to graphs with <xxeeannnnn.n Definition 4 (Expander). For > O, say that graph G (V, E, w) has a-expansion a & (G)), where (GG) denotes the conductance of G and is defined as
efficient
(GG)
min (CV
S( Wnp
where d,
Σ
Wy-
min (Eues du. Evevi
(u,0)E
Theorem 2. There is an (Ō(me "), (()) ())eee)))-ffecttiiv resistance sketch algorithm graphs with O(1 exxpanninn
Table 1 summarizes and compares Theorem to previous work effective resistance sketches, including naive algorithms to explicitly compute the pseudoinverse of the Laplacian of G, which can be computed in O(n²) time using FMM or Ö(m)) time using Laplacian system solver (labeled Solver). 2 A (Ta, Tq. s) refective-resistance sketch algorithm implies an O(T, + (S(Tg) algorithm for the effective resistance estimation problem. Hence, Theorem 2 implies the following.
Theorem 3 (Effective Resistance Estimation on Expanders). There is an Ö(me + [S]) time algorithu which solves the effective resistance estimation problem for graphs with ÿi expaeexxnnnnnn
Effective resistance sketches common approach to solving the effective resistance estimation problem; but there are also approaches to the problem that do not explicitly construct effective resistance sketches. Table 2 summarizes prior work on effective resistance estimation more broadly.
There has been a long line of research on the problem of computing sketches and sparsifiers of graph Laplacians [5,28,30, 36] (i.c., computing sparse graph G" such that quadratic forms in the Laplacian of G' approximately preserves quadratic forms in the Laplacian of G). Building on this work, [30] showed there is an algorithm which processes graph G on n nodes and m edges in O(m! +0(1)) time and produces sparse sketch graph H with only 1( edges such that ra(a, b) & TH (a, b)
ww n. 2.37188 [35] denotes the fast matrix multiplication constant.
3

---

for all a, E V. Consequently, any algorithm which runs in Ömme expanders can be improved
run in O(m +a(l)) ne (c+ on expanders simply by running the algorithm on H instead of G.
Table I: Effective Resistance Sketch
Table 2: Effective Resistance Estimation
Citation
T
Tg
Citation
Runtime
S Restrictions
FMM
n²
1
n²
FMM
n" + |S]
None
Solver
nm
1
n²
Solver
nm + |.
None
[5]
me 2
e-
ne
[5]
n²e
S V V
[28]
n²c-1
I
nc
[28]
n²²E
S = V x V
[29]
m + nc
1
nc
[19]
m + (n + [S])c
None
This Paper
me
1
71
[37]
+ |S| c-
None
[30]
me 1.5
$ = E
[29]
m nc + [S] + |S|
None
This Paper
mc
None
Summary of prior work on Effective Resistance Sketch (Table 1) and Effective Resistance Estimation (Table 2) algorithms on n-node, m-edge expanders. All time and space complexities reported up to to Ō.)). The methods of This Paper and [29] apply only expanders; however, the remaining works apply general graphs. As discussed, when m +=(()) + ne- (e-(o+)) o(me=)) any runtime dependence on me- in the table can be improved to a dependence on m0)+)+ + ne ne=1))
Lower Bounds For the effective resistance estimation problem, [33] showed that any combinatorial algorithm (i.e., an algorithm that uses only combinatorial operations in the sense of Theorem 1) which solves the effective resistance estimation problem for S = x V in O(n2e-1/13- for some 8 > O. would imply combinatorial subcubic deterministic algorithm which detects triangle in n-node undirected unweighted graph. We improve on their result, as follows.
Theorem Given a combinatorial algorithm which solves the effective resistance estimation problem for S V x V on graphs with ((1)-expansion in (1/2c-1/245) time for 5 > O, we can produce randomized combinatorial algorithm which solves the triangle detection problem on n-node graph in 3-25) time whp.
Theorem 4 implies an M2(i2e-1/2 randomized conditional lower bound for the problem of estimating effective resistances of all pairs of nodes in undirected unweighted expander graph, while [33] shows only an 21/2 lower bound. As we show in Section 4, by a simple reduction we can extend any e lower bound for the all-pairs effective resistance problem lower bound for the all-edges effective resistance problem. Consequently, our result also yields a
(mme-
1/mc randomized lower bound for the problem of estimating effective resistances of all edges an undirected expander graph.
In addition to conditional lower bounds for effective resistance estimation, we also improve on existing conditional lower bounds for the problem of estimating spectral sums that define below.
Definition 5 (Spectral Sum). For J IR. R+ and A E Ruxn with singular values 0
a1 (A) &
(A) < ... & on (A), we define the spectral sum Sy R2 - R+ as (A = - f(o,(A)).
[33] showed that for several spectral sums S,, any combinatorial algorithm that outputs Y ~, S) in (nee=") time on an n x n PSD matrix would imply an Oaa)+ time combinatorial algorithm which solves the triangle detection problem, where the scaling varies depending on the specific Sy (see Table 3). We build on their results to show improved randomized conditional lower bounds for several spectral sum estimation problems, as presented in Theorem 5 below.
Theorem 5. Given combinatorial algorithm which on input B R oulputs spectral sum estimate Y 2. (B) in (n²e time with 7 2 2 for the spectral sums in Table 3, we can produce a randomized combinatorial algorithm that can detect triangle in n-mode graph whp. in Ô (n(+ time, where is scaling that depends on properties of the function f (see Table 3 for values of a for several spectral sums.)

---

[33]
This Paper
Spectral Sum
TD Runtime
Lower Bound
TD Runtime
Lower Bound
Schatten 3-norm
n
n²c-1/4
n'c 2/5 n²e-1/10
Schatten p-norm, p * 1,
n1+13c
112111118
7+100
SVD Entropy
n 7
n²c-1/6 1/6
n²c 1/5
Log Determinant
77
n²e-1/0 1/6
7775
n²c 1/5
Trace of Exponential
127+13c
1 1/13
n 7 10c
n 11/10
Table 3: Runtimes for the triangle detection (TD) problem in an n-node graph using algorithms that produce (1 + <) multiplicative approximations to various spectral sums Onn2c=9) time. The second columns contain the best achievable runtimes for 2 that do not use FMM, barring breakthrough in subcubic triangle detection. All runtimes are reported up to Ö(-).
Preliminaries
General notation. We use Ai,; denote the (i, j-th entry of A. For A E R
(A) for its spectrum, (((A) and (A) for its i-th smallest eigenvalue and singular value respectively, and p(A) (A)) for its spectral radius. 1llpp denotes the l ---mm.. When A is PSD, Amin (A) denotes its smallest nonzero eigenvalue and H m(()) :- An (n)A)/a A ( (A) denotes its pseudo-condition number. We use <.,-> for the Euclidean inner product, 1 for the all ones vector, and e, for the i-th standard basis vector. We define 8.jj : e ej and [A:] : {1 {1...., k). We use x Re y as shorthand for (1 c)y & (1 c)y. For E RR, we use u i j] for the sub-vector from index i to j. We use e 1 to indicate that W E R" are orthogonal (i.e., v
0).
Graphs. We G (V, E. w) to denote weighted undirected graph on V with edges E and edge weights w E R (or G = (V, E) if unweighted). We use Ag to denote its (weighted) adjacency matrix (Ag)a, Wape for u, E V x V and DG to denote its diagonal (weighted) degree matrix (Da)u Lu, Wu, for u V (treated as Wa,v = =11 if G' is unweighted). We define LG == D Ag as its graph Laplacian. dmaax G*) and dmin (G))(G) refer to the max and min diagonal entry in Dg. We may drop the argument or subscript if is clear from context. The effective resistance between nodes i, V is denoted (i, = 5,, L We assume all input graphs are connected, effective resistances can be computed separately connected components. We use BG to denote the E' V edge- edge-incidence matrix of G, where (Ba)e,u = and (Ba)e.v = -1 for all e e E, and {u, v), with BG.. for all * u and
Symmetric Diagonally Dominant (SDD) Matrices decomposed as M DM AM. where the DM is diagonal matrix with non-negative entries and AM is matrix with zeros the diagonal such that d, 2y la,gl- We define the normalization
matrix M Raxa is SDD if it can be
Throughout this paper, assume, without loss of generality that DM has strictly positive entries on the diagonal (otherwise, we can simply remove an entire row and column of zeros). We use Umax(M) and diin (M) denote the max and min entry in the diagonal of DM respectively. We may drop the argument or subscript M if it is clear from context.
of M NM M == D 1/2 MDD 1/2
Spectral Graph Theory. Our results leverage well-known spectral graph theory results. In
particular, our algorithm complexities are parameterized by the normalized pseudo condition number of graph (or SDD matrix).
Definition 6 (Normalized (nseudo)cconditin number). We define the normalized peseudo-)condiigg number of an SDD matrix M E IR" as R (M) : X,
( (/min) (NM).
To connect the normalized condition number expander graphs, can apply Cheeger's inequality, which guarantees that if G has a-expansion for some Ộ(1), then (La)
Xn (/NNr../A2(Na & = Ō
Theorem 6 (Cheeger's Inequality [38]). Let G EV,Eww) be an undirected graph. Then, {22(N) & (G) (2),
5

---

In addition, leverage the fact that effective resistances can be expressed in several equivalent expressions. particular, it is known that:
re(1,)) - ر D.jD-1/2Nc D- (w. B T BoLL
where Wo ExXE is the diagonal matrix of weights in G [5].
Runtimes and Space Complexities. In our algorithmic results and analysis, when clear from context, we use O()) (resp., ((-)) notation to hide polylogarithmic factors (resp., inverse polylogarithmic factors) in the number of vertices, the number of edges, the size of the matrix, the number of nonzero entries a matrix, the maximum and minimum diagonal element of matrix, the maximum and minimum weighted degree of graph, 6, the condition number, and the normalized psuedo-condition number of matrix. We say event E occurs with high probability in t if IP [F]] > - t- where parameters. We may simply say that an event occurs "with high probability" or "whp." it occurs with high probability in the size of matrix number of nodes in graph.
O can be controlled by appropriately configuring the algorithm
3 Algorithmic Results
In this section, we present our main algorithmic results. Section 3.1 outlines our approach to effective resistance sketches and estimation; defer discussion of our approach to SDD and PSD extensions to the supplementary material. Section 3.2, presents our original results on effective resistance sketching and estimation and generalizations to SDD matrices. Section 3.3 extends techniques to yield an interesting data structure for estimating quadratic forms of PSD matrices.
3.1 Our Approach
Approach in prior work: Johnson Lindenstrauss sketches. Our starting inspiration is a classic result of [5], which obtains (Ō(me-2), Ō(c=²). Ô(cc -efffecvveee resistance sketch by using the Johnson Lindenstrauss Lemma (JL) [39] and its algorithmic instantiations [40].
Lemma [40]). Given fixed vectors UI Un E Rdd and E (0, 1), let J be an independently sampled random matrix in (+1/VRjexx exd, For k Ö(log(n)e whp. in [n].
Lemma (Johnson-Lindensteee
n, JJu la Re |eill for all i
[5] observe that ra(i,) n, (JW| //W BaLbda Re ra( With SDD linear system solvers, Jw G BoL can be B
BT "BLL Consequently, w.h.p in /
approximated in O(me-1) time, from which J can queried Ö(e=2) time.
Our approach: asymmetric CountSketch in e, Towards improving upon JL sketches for effective resistance estimation, our key tool is to use other sketching algorithms. In particular we use that there are algoirthms that achieve better than =(keech dimension for vectors with small l norm with comparable guarantees, e.g.. CountSketch. CountSketch is classic memory-efficient algorithm for estimating the number occurences of various datapoints in a data stream [41] and efficiently computing inner products [42]. Given E I= and integer parameters t O, CountSketch transforms to a vector Su 3 where 3t a 34-columm--parse 0/1 matrix. Lemma
is special case of Theorem 4 from [42], which provides accuracy guarantees for inner product estimation using CountSketch.
Lemma 2 (Special Case of [42], Theorem 4). Let vectors v. R". Let S be random CountSketch
matrix. Let 24 <(Sv) 1)s + 1 : i s]. (Sw) - 1)s + 1 i. s)) for i [3t]. and let X denote the median of (xx). For s O min |w/ |
<Koww> (ko,,))=)) )). and = llo(nn))
XX - w)) & eV, w)l with probability as least (211-
To improve the guarantee in Lemma 2 to hold whp. for all v, S rather than for each fixed pair, one can simply choose f. = log (g((n))))) and apply union bound. Consequently, if we knew that w!! / B,LL/o,li//ro(i..)
Ö(1) then building a CountSketch with Ō(e-1) would
6

---

yield ((ne-")-sizz sketch, improving the 3) sketch obtained using the l JL sketch in [5]. Unfortunately, it is unclear if and when such a bound holds, and so, is unclear how the & CountSketches could be useful in this setting. This leads to the main insight that fuels algorithms. Rather than seeking a symmetric factorization of (i,),) as a quadratic form u y and applying a sketching procedure v, we instead work with an axymmetric factorization. In particular, we observe
re(i. = Di DL"
1/2 (NLG)
' DD
1/22
(1)
LG
At first glance, it may seem unclear why (1) is helpful. However, we show that indeed, for expanders Pi 1ol, DL (N 1/2 1/,,,, /ro(i,/))) Ō(1).
Our main result essentially follows from (2). Using SDD linear system solvers, we can efficiently approximate SD (Nr,, (N..) Role *jxn in Ö(me time, yielding our Ta of Ö(me and of Ö(nc=)) (see discussion supplementary material). Moreover, SD Ô(1) Sspasss, due to the structure of Count-Sketch. So, using our (approximate) access to S 1/2 (NL) for any query i.j E V. we can efficiently approximate (1) using the recovery procedure of Lemma 2 in Õ(1) time.
3.2
Our Results
We use the approach in Section 3.1 to develop algorithms to compute spectral sketch data structures for SDD matrices M with Õ(1) normalized condition number, as defined in Definitions 6 and 7. So, as discussed in Section 2, this implies that our spectral sketch algorithms will automatically apply to normalized Laplacians of expanders and enable us to compute effective resistances.
Definition 7 (Spectral Sketch Data Structure). We say an algorithm produces an (Ta, Tap s)specraa sketch data structure for PSD matrix A E igaxn if given A e gux" and E (0, 1), the algorithm A, E)) in time O(T(A,, (TTT(A,)), f).from which, for any supported query b E I", whhp it outputs (b( ~e 6 Ab in time (A, (nnz(b))²).
creates a binary string of length (s{(A,
Our spectral sketches of SDD matrices M will only support D D sparse query vectors. Definition 8 (D-numerically sparse). For diagonal matrix D, the D-numerical sparsity of x E IR" nsp (z) == D |D |</||/ | 1/220| We say x is (c, D)-muerrically sparse if nsp (x) & c.
Definition 8 is restrictive; however, several natural classes of vectors satisfy the requirements. For example, are (1, -umueriiaally sparse and 81,5 (2, ())-mmmrricall) sparse for any i, e [n]] and invertible diagonal matrix D E gnxa (see supplementary material for additional examples.)
The following asymmetric rearrangement of quadratic forms is crucial to our analysis.
Lemma 3. Ler M E Raxn be SDD and e R be orthogonal to ker (M). Then,
F TM x
2 Di v. D (N
1/2 N D ad x) = M x,
1-12
1/2
x)
D
1/2 2 15
M
M
2
Proof. For notational convenience, let NEM NM/2. Let Mr. v (Dar A AM)
vr. Note that
1/2 DT1/ x I ker (N)s), and 2D NeM 1/2 M. Consequently, v JDM
1/2
1/2 N DM 1/2
x,
and hence x MMx DD x, DM N DM -1/22). The second equality now follows immediately by rearranging terms. To obtain the inequality, note that, because M SDD and -1/2 1/22 AND 1/2
D is invertible, NM is PSD. Furthermore, 21 NM I- D
-1/2 which is also PSD,
as (Am) [-dmax dmax]] So, 0 & A(NM) & 2. So, Amin (Na) 1/2 and the lemma follows.
C
Lemma 4 bounds
(N //2 =|1
The proof uses the power series expansion of (N M2)))
Lemma 4. Let M Raxn be an SDD matrix and x B. be a unit vector orthogonal to ker (M). Then
| 1/2
(2 1122 max (1, 2x (M) log (o (Vndmax2 (M)/V dmin
| 1 + 1.
7

---

Combining Lemmas 3 and 4 with the guarantees of Lemma 2 and prior work SDD linear system solvers (see supplementary material), we obtain the following theorem.
Theorem 7. For any SDD matrix M E R there is an algorithm construct an (Ö(R (M) unz(M))-)) (1)), (M) ne -speccralll sketch data structure of M supported over queries S, where S is any set of (O(1), Dm numeriicaly sparse vectors orthogonal to ker (M).
Because the 6i5 queries appearing in effective resistance computations are 2-sparse and (2, D (2) numerically sparse for all SDD matrices M, taking M LG in Theorem immediately implies Theorem and Theorem 3 (see supplementary material for detailed discussion and pseudocode.)
3.3 Extensions to PSD Matrices
Our approach of approximating quadratic forms via asymmetric inner products also yields a query- efficient sketching procedure for approximating quadratic forms of well-conditineed PSD matrices.
Theorem 8. There is an algorithm to construct an (Ö(n(A (x(())nnz(A))) (nnz(A)c=))) 2)))),,) ((((A)nc spectral sketch data structure of A supported over S, where S is any set of vectors orthogonal to ker () and PSD.
sketch data structure using efficient square root algorithms [43]. JL achieves better compression than Theorem 8, while Theorem 8 achieves faster query time. When the matrix is well conditioned and error tolerance is sufficiently high, Theorem may achieve better construction time and query time than JL while maintaining comparable compression.
In comparison, JL [39] gives an
4 Lower Bounds
this section, we present our main hardness results. Section 4. outlines our approach. Section 4.2, present our lower bounds for the problem of estimating effective resistances for all pairs of nodes (case where S = V x V), which we call the "all pairs effective resistance estimation problem." Section 4.3 shows our techniques also yield lower bounds for other spectral sum estimation problems.
4.1 Our Approach
Approaches Previous Work The approach [33] begins with the fact that G has triangle if and only tr (A&) /6 > 1. They use the fact that various spectral sums Sy of the of the SDD matrix I 8Ag (for 8 sufficiently small) can be expressed The first two terms this series can be computed directly. So given ~, S, &AG). one can estimate tr (A&). where the estimation error is controlled by the magnitude the first two terms of the series and the tail error due truncating at the third term. By bounding this estimation error, [33] show that, for appropriate choices of 6, Re ( 5Ag) yields an additive 1/2 approximation to tr (A&), which is sufficient for triangle detection. They also reduce the problem of estimating the spectral sum tr (B-1) for an SDD matrix B to the all pairs effective resistance estimation problem.
power series Sy (1G) Σ. 0² tr t
We use three key techniques better bound the estimation errors incurred in the power-series-inpiire approach of [33]. This yields faster reductions and better lower bounds for effective resistance estimation. Rather than obtaining effective resistance lower bounds by reducing the problem of computing tr (A%) /6 to computing the trace of an SDD matrix as in [33], we use reduction that closely resembles the structure of effective resistances. For sufficiently small,
Our Approach
(I-
I
a
AG
R
k-O
Since Ag is known, given access to (I- -2) we can estimate the entries of A where the estimation is controlled by and the tail error of truncating (3) at the third term. By bounding this estimation error, for appropriate choice of a, we can obtain additive 1/2 approximations to all entries of Ag. which is sufficient to identify all paths of length 2. We can then detect
8

---

triangle by simply scanning for edge {u, e) such that u and v are connected by path of length 2. Estimating the entries of A leads to lower estimation error than estimating tr (Ağ) as in [33]). Second, we use a standard randomized reduction that reduces the triangle detection problem to the triangle detection problem restricted to tripartite graphs. The reduction relies on the fact that randomly sampled tripartition of the original graph preserves triangles with constant probability. To detect triangle in tripartite graph G = (V1 L L V3, E), we construct graph H by removing all edges , ;= {f,, v) E E : u E V1, v E V23 between Vi and V2. G has a triangle if and only if there is an edge {u, w) E E1 and path of length 2 between u and in H. Crucially, we can show that the third term A does not contribute to the tail error when estimating the {u, e)-th entry of (A]r) using (3). Third, to lower the spectral norm of Ah (and consequently better bound the convergence of the power series (3)), we introduce the symmetric random signing of A below.
Definition 9 (Symmetric Random Signing). Given a symmetric matrix A E BRux,, its symmetric random signing A the random matrix with Aijj := Eij where Eig are independent Rademacher random variables that satisfy fi.j f3.5-
We show that this random signing preserves the non-zeroness of entries of A with constant probability, allowing us to detect whether G has a triangle even if we replace AG in (3) with Ah instead. This is beneficial, as matrix Chermoff guarantees A 2 = (n)))) whp. whereas |A may be as large as n. So the tail error of truncating the power series is smaller. To compute entries of A efficiently using effective resistance estimates expanders, we first show that we can use all pairs effective resistance estimates on expanders estimate , " 1 M for all i,j E [n]. where M (I - Q) is an SDD matrix with pl (Q)== & 1/3. Then, by choosing M = I aº A as in (3) for an appropriate constant a, we can estimate A f/ from estimates of 8 M- 5..j This yields our lower bound on the all pairs effective resistance estimation problem.
Additionally, show that random signing also preserves the non-zeroness of tr (A with constant probability, and leverage this to obtain improved randomized conditional lower bounds for various spectral sum estimation problems. We closely follow the trace estimation approach of [33], and again use the smaller spectral radius of Ag to improve bounds on the power series truncation error.
4.2 Improved Lower Bounds for Effective Resistance Estimation
In this section we provide a series of reductions which yield our main result on lower bounds for the all pairs effective resistance estimation problem for all pairs of nodes (case where S V x V).
Definition 10. In the SDD effective resistance estimation problem, given an SDD matrix M such that DM AM Q with p(Q) & 1/33 and e E (0, 1), we must output R.= such that Ta,h Re M Sa, Va, b E [n]. We call 5 the SDD effective resistance of (a, in M.
For brevity, we use F(M) to refer to the solution of the SDD effective resistance problem on input M. Our first step is to show that an algorithm for the all pairs effective resistance estimation problem on expanders implies an algorithm for the SDD effective resistance estimation problem.
Lemma 5. Given an algorithm to solve the all pairs effective resistance estimation problem on graphs with -exeaaxxnn in =1)-=0) time for some c >> O, we can produce an algorithm to solve the SDD effective resistance estimation problem in Ö(n²==9 time.
To prove Lemma 5, we first prove the lemma for the case where Q is entrywise non-negetive by constructing an expander G with n + 1 vertices such that ra(a, b) = 5. M for all a, b E [n]. We extend the reduction to arbitrary Q by constructing Q' of size 2n so that Q' is entrywise non-negative and 7(I Q) is a simple linear transform of F(I Q').
We turn our attention to reducing the triangle detection problem to the SDD effective resistance problem. As discussed, key aspect of our approach is to work with the random signing Ag of Ag. Lemma 6 shows that to determine whether (),) > 0 with constant probability, suffices
to determine whether (A2) i.j > O. Matrix Chernoff ensures whp. p(Ac) Ö(v7). while p(Ac)
could be large as [44]. So, estimating entries of Ag leads to lower power series tail error.
Lemma 6. For i # j. if (A2 (A))..) = O, then (A = 0; if (A)) > 0, P [[(A)) > 1] > 1/2.
9

---

The idea of the proof is that if {a, bj, (6, ej exist in G. either &a,c 1 or Ea,c - results in (Ag)a,c O. Finally,
the power series approach in Section 4.1 to obtain Theorem 9.
Theorem 9. Given an algorithm which solves the SDD effective resistance estimation problem in (9) time, we can produce randomized algorithm that solves the triangle detection problem in ((n)()+))) time whp.
Theorem 9 and Lemma 5 with c 1/2 immediately imply our main result Theorem 4.
Additionally. extend the lower bound of Theorem 4 to the all edges effective resistance estimation by the following reduction.
Lemma 7. Given an algorithm to solve the all edges effectivve resistance estimation problem (i.e., Definition I where S = E) in Ómme time, we can produce an algorithm to solve the all pairs effective resistance estimation problem in (n) time for some > 0.
The rough idea behind the reduction add a complete graph of edges of sufficiently small weight that would not change the effective resistances much. Lemma 7 combined with Theorem 4 then imply a 50mmm= randomized lower bound for the all edges effective resistance estimation problem graphs with graphs with (ex)aexxpnn
4.3 Improved Lower Bounds for Spectral Sum Estimation
Finally, we discuss our improved lower bounds for various spectral sum estimation problems.
Analogous Lemma 6, in the following lemma show that determine whether graph has
triangle (i.e., tr (A2 > 0) with constant probability, it suffices to determine whether tr (Ag) > 0.
Lemma 8. Ir (A)) O, then (A2) O, and tr (A2) 0 then P [[ (A2) 0] 1/4.
The central idea of the proof is that if triangle (a, (b, c). {c, a} exists in G, then amongst the 4 possible configurations of the Rademacher random signing variables Ea, and &b.c. at least one configuration must result in |tr (A%) > O. By following the proof of Theorem 15 from [33], and replacing their use of Ag with a symmetric random signing Ag. we obtain an improved randomized version of their result by leveraging the smaller spectral radius of Ag Theorem 5 follows by applying this result to the functions f that define the corresponding spectral sums (see supplementary material).
5 Conclusion
In this paper we provided improved upper and lower bounds on the problem of estimating and sketching effective resistances on expanders. On the algorithmic side we show how sketches tailored E when carefully applied asymmetric formulations of the quadratic form of the Laplacian pseudoinverse gave our results. On the lower bound side, we provided an alternative to the trace estimation approach of [33] for showing lower bounds and coupled with techniques of randomly signing edges of the graph to obtain our results. Further, we showed that these techniques had broader implications for addressing algorithmic challenges numerical linear algebra.
Beyond the natural open problem of improving both our upper and lower bounds towards bringing them together, there are interesting open problems in broadening the applicability of both our upper and lower bounds. For example, obtaining an Ömm time algorithm for estimating the effective resistance of all edges in general (non-expander) graph and extending our 2 lower bounds to deterministic algorithms remain interesting open problems. We hope that the results of this paper provide useful tools for addressing each.
Acknowledgments and Disclosure of Funding
We thank Hongyue Li for helpful discussions and work on this project at various stages. Aaron Sidford was supported in part by Microsoft Research Faculty Fellowship. NSF CAREER Award CCF-1844855, NSF Grant CCF-1955039, a PayPal research award, and Sloan Research Fellowship. NSF Grant
Ishani Karmarkar was supported in part by an NSF CAREER Award
10

---

CCF-1955039, PayPal research grant, and Stanford Institute for Computational and Mathematical Engineering (ICME) Fellowship. Rajat Vadiraj Dwaraknath was supported by a Stanford ICME Fellowship.
References
[1] Aleksander Madry, Damian Straszak, and Jakub Tarnawski. Fast generation random spanning trees and the effective resistance metric. In Symposium Discrete Algorithms, 2014.
[2] Karel Devriendt. Effective resistance is more than distance: Laplacians, simplices and the schur complement. Linear Algebra and its Applications, 2022.
[3] Huan Li and Zhongzhi Zhang. Kirchhoff index as measure of edge centrality in weighted networks: Nearly linear time algorithms. In Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2018.
[4] Douglas Klein and Milan Randic. Resistance distance. In Journal of Mathematical Chemistry, 1993.
[5] Daniel Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. In SIAM Journal of Computing, 2009,
[6] Yin Tat Lee and He Sun. Constructing linear-sized spectral sparsification in almost-linear time. In SIAM Journal of Computing, 2015.
[7] David Durfee, Yu Gao, Gramoz Goranci, and Richard Peng. Fully dynamic spectral vertex sparsifiers and applications. In Symposium on Theory of Computing, 2019.
[8] Rakshith S Srinivasa, Cao Xiao, Lucas Glass, and Jimeng Sun Justin Romberg. Fast graph attention networks using effective resistance based graph sparsification. In arXiv preprint NCTY::2006007796, 2020.
[9] Tasweer Ahmad, Lianwen Jin, Luojun Lin, and GuoZhi Tang. Skeleton-based action recognition using sparse spatio-temporal gen with edge effective resistance. In Neurocomputting, 2021.
[10] Dehua Cheng, Yu Cheng. Yan Liu, Richard Peng, and Shang-Hua Teng. Efficient sampling for gaussian graphical models via spectral sparsification. In Proceedings of the Conference Learning Theory, 2015.
[11] Daniele Calandriello, Alessandro Lazaric, Ioannis Koutis, and Michal Valko. Improved large- scale graph learning through ridge spectral sparsification. In International Conference on Machine Learning. 2018
[12] Alexander Mercier, Samuel Scarpino, and Cristopher Moore. Effective resistance against pandemics: Mobility network sparsification for high-fidelity epidemic simulations. In PLOS Computational Biology, 2022.
[13] Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang- Shang-Hua Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Symposium Theory of Computing, 2010.
[14] Aleksander Madry. Navigating central path with electrical flows: from flows to matchings, and back. In Symposium on Foundations of Computer Science, 2013.
[15] Aleksander Madry. Computing maximum flow with augmenting electrical flows. In Computing Maximun Flow with Augmenting Electrical Flows, 2016.
[16] Jan van den Brand, Yu Gao, Arun Jambulapati. Yin Tat Lee, Yang P Liu, Richard Peng, and Aaron Sidford. Faster maxflow via improved dynamic spectral vertex sparsifiers. In Symposium on Theory of Computing, 2022.
[17] Jan Van Den Brand, Yang Liu Yin Tat Lee, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, mdps, and fi-regeessoon in nearly linear time for dense instances. In Symposium on Theory of Computing, 2021.
[18] Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in o (vrank) iterations and faster algorithms for maximum flow. In Symposium on Foundations of Computer Science, 2014.

---

[19] David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, and Sushant Sachdeva. Sampling random spanning trees faster than matrix multiplication. In Symposium on Theory of Computing, 2017.
[20] Aaron Schild. An almost-linear time algorithm for uniform random spanning tree generation. In Symposium on Theory of Computing, 2018.
[21] Aleksander Madry, Damian Straszak, and Jakub Tarnawski. Fast generation of random spanning trees and the effective resistance metric. In Symposium on Discrete Algorithms, 2014.
[22] Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. Graph clustering using effective resistance. In arXiv preprint arXiv:1711.06532 2017.
[23] Zhiqiang Zhao and Zhuo Feng. Effectiie-resisttane preserving spectral reduction of graphs. In Proceedings of the Annual Design Automation Conference, 2019.
[24] Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio', and Michael Bronstein. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International Conference on Machine Learning, 2023.
[25] Pradeep Banerjee, Kedar Karhadkar, and Guido Montúfar Yu Guang Wang, Uri Alon. Oversquashing in gnns through the lens of information contraction and graph expansion. In Communication, Control, and Computing, 2022.
Allerton Conference
[26] Mitchell Black, Amir Nayyeri, Zhengchao Wan, and Yusu Wang. Understanding oversquashing in gnns through the lens of effective resistance. In International Conference on Machine Learning, 2023.
[27] Ameya Velingker, Ali Kemal Sinop, Ira Ktena, Petar Velivcković, and Sreenivas Gollapudi. Affinit--aware graph networks. In arXiv preprint arXiv:2206. 1941, 2022.
[28] Arun Jambulapati and Aaron Sidford. Efficient ((n/e) spectral sketches for the laplacian and its pseudoinverse. In Symposium on Discrete Algorithms, 2018.
[29] Lawrence Li and Sushant Sachdeva. A new approach to estimating effective resistances and counting spanning trees in expander graphs. In Symposium on Discrete Algorithmss 2022.
[30] Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, and Junxing Wang. Graph sparsification, spectral sketches, and faster resistance computation, via short cycle decompositions. In Symposium on Foundations of Computer Science, 2018.
[31] Gramoz Goranci, Monika Henzinger, and Pan Peng. Dynamic effective resistances and approximate schur complement on separable graphs. In Embedded Systems and Applications, 2018.
[32] Michael Dinitz, Robert Krauthgamer, and Tal Wagner. Towards resistance sparsifiers, 2015.
[33] Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubara, and David P Woodruff. Spectrum approximation beyond fast matrix multiplication: Algorithms and hardness. In arXiv preprint 1rX4::1704.444
2017.
[34] Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. In Symposium on Foundations of Computer Science, 2018.
[35] Ran Duan, Hongxun Wu, and Renfei Zhou. Faster matrix multiplication via asymmetric hashing.
In https://arsii.orr/////222.... 10117 2023.
[36] Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, and Qin Zhang. On sketching quadratic forms. In Proceedings of the Conference on Innovations in Theoretical Computer Science, 2015.
[37] Huan Li and Aaron Schild. Spectral subspace sparsification. In Symposium Foundations of Computer Science, 2018.
[38] Jeff Cheeger. A lower bound for the smallest cigenvalue of the laplacian. In Problems in Analysis, 1971.
[39] William B. Johnson. Extensions of lipschitz mappings into hilbert space. In Contemporary mathematics, 1984.
[40] Dimitris Achlioptas. Database-friendly random projections. In Proceedings of the Symposium on Principles of Database Systems, 2001.
12

---

[41] Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In Theoretical Computer Science, 2004.
[42] Kasper Green Larsen, Rasmus Pagh, and Jakub Tetek. Countsketches, feature hashing and the median of three. In International Conference on Machine Learning. 2021.
[43] Prateek Jain, Chi Jin, Sham M. Kakade, and Praneeth Netrapalli. Global convergence of non-convex gradient descent for computing matrix squareroot. In International Conference on Artificial Intelligence and Statistics, 2017.
[44] Joel A Tropp. User-friendly tail bounds for sums of random matrices. In Foundations of computational mathematics, 2012.
[45] Yu Gao, Yang Liu, and Richard Peng. Fully dynamic electrical flows: Sparse maxflow faster than goldberg-rao. In SIAM Journal on Computing, 2023.
[46] Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, and Aaron Sidford. Faster maxflow via improved dynamic spectral vertex sparsifiers. In Symposium on Theory of Computing, 2022.
[47] Ignacio Garcia Marcoo Pascal Koiran, Timothée Pecatte, and Stéphan Thomassé. On the complexity of partial derivatives. In Theoretical Computer Science, 2017.
[48] Jacques Morgenstern. Note on a lower bound on the linear complexity of the fast fourier transform. In Journal of the Association for Computing Machinery, 1973.
[49] Amir Shpilka. Lower bounds for matrix product. In SIAM Journal on Computing, 2003.
[50] Virginia Vassilevska Williams, Eyob Woldeghebriel, and Yinzhan Xu. Algorithmss and lower bounds for replacement paths under multiple edge failure. In Symposium on Foundations of Computer Science, 2022.
[51] Mahdi Boroujeni, Sina Dehghani, Soheil Ehsani, MohammadTaghi HajiAghayi, and Saeed Seddighin. Subcubic equivalences between graph centrality measures and complementary problems. In arXiv preprint arXiv:1905.08127, 2019.
[52] Rasmus Kyng and Sushant Sachdeva. Approximate gaussian elimination for laplacians: Fast, sparse, and simple. In Symposium on Foundations of Computer Science, 2016.
[53] Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu. A simple, combinatorial algorithm for solving sdd systems in nearly-linear time. In Symposium on Theory of Computing, 2014.
[54] Daniel A Spielman and Shang-Huu Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. In SIAM Journal on Computing, 2013.
[55] Arun Jambulapati and Aaron Sidford. Ultrasparse ultrasparsifiers and faster laplacian system solvers. In Symposium on Discrete Algorithms, 2021.
[56] Neha Gupta and Aaron Sidford. Exploiting numerical sparsity for efficient learning: Faster eigenvector computation and regression. In Neural Information Processing Systems, 2018.
[57] Suk- Geun Hwang. Cauchy's 's interlace theorem for eigenvalues of hermitian matrices. In The American mathematical monthly, 2004.
13


Reviews:
[{"review_id": "CGwMkvbxBK", "reviewer": "Reviewer_T2X2", "summary": "The paper studies the problem of estimating the effective resistances in $n$-node $m$-edge undirected, expander graphs, and provides a $O(m/\\epsilon)$ time algorithm which produces an effective resistances sketch in $O(n/\\epsilon)$ size of space. This improves the runtime of the previous algorithm that estimates the effective resistance of all edges in such graphs and can be extended to the general problems of sketching the pseudoinverse of positive semidefinite matrices and estimating functions of their eigenvalues. The authors also give a new corresponding conditional lower bound where the $\\epsilon$ dependence is improved.  ", "questions": "1.As summarized in table 1,  [3] has a runtime $O(m + n/\\epsilon^2)$, will this bound be better than this work if $m/n > 1/\\epsilon$?", "limitations": "See the above questions.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The technical contribution is solid. The paper provides the algorithms with better theoretical bounds, along with the corresponding lower bound. To achieve this, one key point of the paper is it considers an asymmetric factorization and the asymmetric CountSketch in $\\ell_1$.\n\n2. The organization of this paper is good. The introduction section is detailed and the authors then first give a technical overview which can help the readers first get a brief understanding of the key point in the algorithm design.", "weaknesses": "1. This paper is a pure theory paper. However, given that it is a NeurIPS submission, I think the experimental evaluations will make the paper stronger.\n\n2. I feel like some parts of the paper are a little technically dense and not very easy to follow. Also, the paper uses many standard facts in spectral graph theory. I think it will make the presentation more clear if the authors can give more detail in the preliminaries section.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and questions! We have discussed interesting directions for future empirical experiments, as well as the modifications to the preliminaries section which you suggested in the general response. Please let us know if you have any additional feedback on those points. \n\n**Question 1: Is the result of [3] better if $m/n > 1/\\epsilon$.** \n\n**Response:** Yes, but we can almost match it. In the regime where $m/n >> 1/\\epsilon$, [3] yields a better runtime than our $\\tilde{O}(m \\epsilon^{-1})$ result in this regime. We can almost match this runtime by noting that our algorithm also immediately yields an $\\tilde{O}({m^{1+o(1)} + n \\epsilon^{-2}})$ runtime. This argument is discussed in Line 118-124 as well as in the caption of Table 1/Table 2; however we summarize the argument briefly in bullet 1 below. Consequently, in the dense regime where $m/n >> 1/\\epsilon$, the result of [3] is better than ours only by an $\\tilde{O}(m^{o(1)})$ factor. As our runtime was obtained independently of [3], we did not consider whether it is possible to remove the $m^{o(1)}$ factor gap between our result and that of [3] in this regime, but it is an interesting question for future work. We point to one approach for trying to remove this gap in bullet 2 below. \n\n* **Summary of procedure to match [3] in dense regime $m/n >> 1/\\epsilon$**: Given $G$, in $\\tilde{O}(m^{1+o(1)})$ time, we can use the result of [1] to construct a sparse “sketch” graph $H$ such that $H$ has only $n \\epsilon^{-1}$ edges and $r_H(i,j) \\approx_{\\epsilon/4} r_G(i,j)$ for all nodes $i,j \\in V$. Now, since $H$ is sparse, in only $\\tilde{O}(n\\epsilon^{-2})$ additional time, we can run our effective resistance estimation algorithm on $H$ to recover $(1 \\pm \\epsilon)$ multiplicative approximations to $r_G(i,j)$. \n \n* **One approach towards removing the $m^{o(1)}$ factor gap in dense regime $m/n >> 1/\\epsilon$**: One approach towards removing the $m^{o(1)}$ factor gap between our results and [3] would be to improve the results of [1] to design an algorithm that generates the sparse “sketch” graph $H$ described above using only $\\tilde{O}(m)$ time (instead of $\\tilde{O}(m^{1 + o(1)}$). If such an algorithm could be obtained, then the procedure discussed in bullet 1 above would immediately run in $\\tilde{O}(m + n\\epsilon^{-2})$ time, allowing us to remove the $m^{o(1)}$ factor gap and match the result of [3] in the regime where $m/n >> 1/\\epsilon$. "}, {"review_id": "1wChemmmg6", "reviewer": "Reviewer_Craf", "summary": "Given a graph $G$, the effective resistance approximation problem is one where you are asked to approximate the effective resistances of some subset $S$ of vertex pairs. The authors have two contributions:\n\nFirstly, the authors demonstrate an $O(m\\epsilon^{-1} + |S|)$ algorithm for computing effective resistances in graphs with constant expansion. This matches the current best known algorithm for computing effective resistances in expanders for dense graphs, and beats it in sparse graphs of total edge count $o(n\\epsilon^{-2})$. To achieve this, the authors make use of CountSketch, and demonstrate that there are sets of vectors from which the effective resistances can be extracted in $\\tilde{O}(1)$ time. These vectors are obtained through the use of CountSketch on vectors with small $\\ell_1$ norm. Furthermore, this data structure is $\\tilde{O}(n\\epsilon^{-1})$ sparse. \n\nSecondly, the authors demonstrate an $\\Omega(n^2\\epsilon^{-1/2})$ conditional lower bound on the time required to compute the effective resistance on all pairs of edges in a graph. They demonstrate that if an effective resistance approximation algorithm is faster than $O(n^2\\epsilon^{-1/2})$ time by a polynomial factor, then the time complexity of triangle detection will be truly subcubic. Currently, the only subcubic algorithms for triangle detection require fast matrix multiplication, so it is unlikely that a combinatorial algorithm for the effective resistance problem on all pairs can be faster. Furthermore, they improve on the lower bounds on a range of similar spectral sum problems using this same reduction, by refining the analysis performed by [4]. \n\nThey achieve this improvement through the use of several techniques. Firstly, by considering a different power series expansion as in [4], they demonstrate that the triangle counting problem can be reduced to a different problem that looks more like effective resistances. To obtain sufficiently good estimation errors, they also make use of symmetric random signing, where each entry of the adjacency matrix is flipped with probability 1/2. ", "questions": "The lower bound obtained by the authors is one on the time required to compute the effective resistance on all pairs of edges. I wonder if there are any lower bounds on the time required to compute the effective resistance on just the edges of the graph. Looking through the use cases of effective resistances in the introduction. It seems to me that a lot of them only care about the effective resistance of just the edges in the graph, while maybe only the most recent works on over-squashing in GNNs care about the total effective resistance. \n\nI am also very confused about the implications of the lower bound with regards to the upper bound. The lower bound is $\\Omega(n^2\\epsilon^{-1/2})$, while the upper bound is $O(m + n\\epsilon^{-2} + n^2)$. Even if the graph were not sparse, the algorithm takes $O(n\\epsilon^{-2} + n^2)$ time, while the lower bound takes $\\Omega(n^2\\epsilon^{-1/2})$. If we pick $\\epsilon$ to be small, say $\\sqrt{n}^{-1}$, isn't the upper bound faster than the lower bound? I don't think I understand lines 82-84, where the authors claim that this lower bound holds on expanders. ", "limitations": "Typos:\n\nLine 240: peridicular\nLine 521: resistance\nLine 536: reisistance ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Originality: \n\nI really like the approaches used by the authors. I think that the technical contributions here in both the upper and lower bounds are very interesting to me. \n\nI like the use of the asymmetric CountSketch, and the fact that the vectors picked are small in $\\ell_1$ norm. The usage of a different power series expansion to obtain a different reduction for the triangle detection problem is also very interesting to me. The former is novel to me, and the latter reads like a novel improvement to obtain better bounds than a preexisting argument. \n\nQuality/Clarity: \nThe full paper is a bit of a rough read, which is the nature of theory papers, but I like that a lot of the intuition is explained in the main section, that makes it a lot easier to understand what is happening. I could follow/guess a lot of what was going to happen in the analysis just from reading the main section which had none of the analysis. \n\nSignificance: \nThe upper bound is relatively significant. Effective resistance approximation is certainly a very important problem that is used as a subroutine for many other problems. They have made an improvement to the approximation time complexity in expanders in sparse graphs, which is a significant contribution to this area. In terms of lower bounds, they have made a significant refinement of the previous approach, which results in an improvement on the lower bounds for a large number of different problems. \n\n", "weaknesses": "The primary weakness of the upper bound is that the contribution made here is relatively marginal in scope. The paper has made improvements in solving a problem that is important, but have only done so in a limited setting (sparse expanders). \n\nThe lower bound is also a very interesting refinement of the previous approach, but it is somewhat unclear to me why this lower bound specifically is one that is important to look at. I feel like there are several other natural lower bounds for effective resistances that are more natural to want to consider. This latter point might just be me since I am not very well versed in this area, but even though this reduction to triangle detection without the use of FMM seems pretty standard is used in many papers, and I understand the arguments as to why it is done, I can't really find myself getting behind it. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your thoughtful comments and questions! We discuss more motivation for considering the expander case in the general response. \n\n**(1) Why consider conditional lower bounds on algorithms using the subcubic non-FMM triangle detection hardness assumption? This is standard, but I can’t find myself getting behind it.**\n\nIt’s an interesting question to obtain other lower bounds, such as interesting lower bounds on tradeoffs between the query time versus sketch size for effective resistance sketching. However, effective resistance estimation and sketching already have various polynomial time algorithms, and unconditional polynomial lower bounds for explicitly polynomial time solvable problems have been elusive. So, it isn’t clear how to approach unconditional runtime lower bounds. \n\nWe wanted to offer some additional reasoning for why the conditional lower bound (based on subcubic non-FMM triangle detection) considered in our paper and [4] is useful _for algorithm designers_. Several recent advances in effective resistance estimation algorithms (in particular, [1], [2], and [3]) don't use FMM. Our lower bounds provide the valuable insight that _FMM is likely essential_ to cross a certain runtime threshold. We show that  to obtain better than $\\tilde{O}(n^2\\epsilon^{-1/2})$ runtime for effective resistance estimation, an algorithm designer must either (1) change the approach of existing methods to figure out _how to incorporate FMM_ into the algorithm (and people debate the practical utility of FMM-based algorithms); or (2) achieve the _algorithmic breakthrough_ of designing subcubic triangle detection algorithms without FMM. Triangle-detection-based reductions highlight that this particular difficulty is also a barrier for several other problems. \n\n**(2) Are there lower bounds for the problem of estimating effective resistance of just all edges?** \n\nYes. Our lower bound $\\tilde{\\Omega}(n^2\\epsilon^{-1/2})$ time directly implies an $\\tilde{\\Omega}(m\\epsilon^{-1/2})$ time lower bound on effective resistance estimation for all edges in a general expander graph. We provide context in the next paragraph and then provide the technical reduction in the third paragraph below.  \n\nYour question is a good one, and it gets at the fact that one could ask the following two interesting questions relating to effective resistance estimation of all edges in a graph:\n\n1. **Our work answers this:** Barring a breakthrough in combinatorial (i.e., non-FMM) algorithms, can we develop a combinatorial algorithm which takes as input an **arbitrary** expander graph on $n$ nodes and $m$ edges and outputs estimates of effective resistances of all $m$ edges in faster than $\\tilde{\\Omega}({m\\epsilon^{-1/2}})$ time? **Our results say NO; we justify technically below.**\n\n2. **Our work doesn't answer this:** Barring a breakthrough in combinatorial algorithms, can we develop a combinatorial algorithm which takes as input a **sparse** expander graph on $n$ nodes and $m < f(n)$ edges and outputs estimates of all $m$ edges in $o(T)$ time?  **Our results leave this question open**, and we are not aware of any lower bounds which answer this question for any nontrivial $T$ when $f(n) = o(n^2)$. This question is more open-ended, because one can choose what sparsity $f(n)$ we demand of the input graph, and it's unclear what choice of $f$ and $T$ would lead to interesting results. We are curious about it as a question future work.  \n\n**Technical justification for 1:** Let $1$ be the ones vector. The idea is, given $n$-node, $m$-edge graph $G$, we can add a complete graph of edges of sufficiently small weight that would not change the effective resistances much. Let $L_G = D-A$ be the graph Laplacian and $H$ be the graph obtained by adding a complete graph with uniform edge weight $\\alpha > 0.$ Then, $L_H = D - A + \\alpha (nI - 11^T)$. Let $M = L_H +  \\alpha 11^T = D - A + \\alpha n I$. As $M$ just completes the kernel of $L_H$, $x^T M^{-1}x = x^\\top (L_H)^\\dagger x$ for all $x \\perp 1$. And, $M^{-1} = (D - A + \\alpha (nI))^{-1} = (Q(\\Lambda + \\alpha nI)^{-1} Q^\\top$ where $Q\\Lambda Q^\\top$ is the eigen-decomposition of $D-A$. The entries $((\\Lambda + \\alpha nI)^{-1})_i$ can be made arbitrarily close to $(\\Lambda^{-1})_i$ by taking $\\alpha$ small enough. So, $x^\\top {L_H}^{\\dagger} x = x^\\top M^{-1} x$ can be made arbitrarily close to $x^\\top {L_G}^{\\dagger} x$ for any $x \\perp 1$. So we can get approximate **all pairs** effective resistances on $G$ from approximate **all edges** effective resistances on $H$. So, any combinatorial algorithm faster than $\\tilde{\\Omega}(m\\epsilon^{-1/2})$ for the all-edges problem would immediately imply a combinatorial algorithm faster than $\\tilde{\\Omega}(n^2\\epsilon^{-1/2})$ for the all-pairs problem– the latter is conditionally ruled out by Theorem 3. We may include this discussion in the next iteration. \n\n**(3)  [3] obtains an $\\tilde{O}(n^2 + n\\epsilon^{-2})$ runtime, which is better that the lower bound if $\\epsilon = 1/\\sqrt{n}$. Is this a contradiction?**\n\nNo, there is no contradiction. When we claim a conditional lower bound of $\\tilde{\\Omega}(n^2 \\epsilon^{-1/2})$, we only mean that it is (conditionally) impossible to obtain a combinatorial all pairs effective resistance algorithm that runs in less than $\\tilde{O}(n^2\\epsilon^{-1/2})$ time for all $n$ and $\\epsilon$ regimes. This doesn’t rule out the fact that there may exist algorithms which run faster than $\\tilde{O}(n^2\\epsilon^{-1/2})$ for certain $\\epsilon$ regimes. The upper bound of $\\tilde{O}(n\\epsilon^{-2} + n^2)$ from [3] is only better than $\\tilde{O}(n^2\\epsilon^{-1/2})$ for certain regimes of $\\epsilon$. In the proof of our lower bound we choose $\\epsilon = \\tilde{O}(n^{-2})$ (see lines 825-830 in the supplemental material). This implies that it is (conditionally) impossible to obtain a combinatorial algorithm that runs in less than $\\tilde{O}(n^2\\epsilon^{-1/2})$ time **for all** $n$ and $\\epsilon$ regimes.\n"}, {"review_id": "NXRPV6OdcQ", "reviewer": "Reviewer_btut", "summary": "The paper theoretically analyzes the time complexity of estimating effective resistances in $n$-node $m$-edge undirected, expander graphs. Specifically, the paper present an algorithm which can achieve $\\tilde{O}(m \\varepsilon^{-1})$ time complexity for estimating the effective resistance of all edges in such graphs. This complexity bound significantly improves the previous result either for general graphs or for expanders. The paper also present a tight lower bound for computing the estimates of effective resistances. ", "questions": "The paper mainly focuses on undirected expander graphs. An interesting question is whether the complexity results given in the paper can be further extended to general graphs. ", "limitations": "I do not see any potential negative societal impact in this paper. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "S1. Computing the effective resistance between a pair of graph nodes is an important and fundamental problem. The paper improves the best complexity result of existing work with non-trivial analysis. A tight lower bound is also provided in the paper. \n\nS2. The paper's technical part is sound and solid. \n\nS3. The paper is well-written and easy to follow. ", "weaknesses": "W1. The paper lacks experimental results to empirically demonstrate the effectiveness of the proposed algorithm. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and questions! \n\nWe have discussed interesting directions for future empirical experiments in the general response, as it was a common theme brought up by multiple reviewers. In addition, we have discussed the primary bottleneck to extending results to general graphs in the general response. Please let us know if you have any additional feedback on these points, and we thank you again for your review. "}, {"review_id": "zBhVWY7usr", "reviewer": "Reviewer_9w9Q", "summary": "In the paper, the authors study the problem of estimating the effective resistance between pairs of vertices in weighted, undirected expander graphs. The authors present a novel algorithm for effective resistance estimation and effective resistance sketching. Moreover, they give a conditional lower bound based on triangle detection.", "questions": "\nMinor:\n1. Line 63: should be $(\\widetilde{O}({m\\epsilon^{-1}}),\\widetilde{O}(1), \\widetilde{O}({n\\epsilon^{-1}}))$-effective\n2. Line 192: the expression of $r_G(i,j)$ missing the $\\delta_{i,j}$ term\n3. Both Equation (1) and Equation (2) missing the $\\delta_{i,j}$ term\n4: Line 240: peridicular should be perpendicular?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "This is a very nice theory paper that studies the problem of effective resistance estimation which a lot of people in the relevant community care.  The contributions of the paper are novel algorithms for both the lower bound and upper bound. The algorithm cleverly uses the countSketch to build a spectral sketch data structure and connects the Laplacian of expanders using Cheeger's inequality. The paper is very well written and it is a pleasure to read. In our opinion, this is an important contribution to the literature.\n\n", "weaknesses": "For the upper bound,  the result looks very similar to the result of [Li, Sachdeva 2022]. It would be great if the authors can provide a more close comparison between the two.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and questions! \n\n**Question 1: It would be helpful if the authors could provide a more close comparison between their work and that of [3].** \n\n**Response:** Thanks for the suggestion. We would be happy to incorporate more of this comparison in the introduction of the paper in the next iteration of our submission. Due to space limitations, we deferred most of this discussion to the supplementary material (beginning on line 536 in Section 6.1). In addition to the comparison in the supplementary material, we would like to highlight the following differences: \n* For expanders, in the regime where $m << n\\epsilon^{-1}$, i.e., for sparse enough graphs, our runtime is faster than that of [3]. In the dense regime where $m >> n\\epsilon^{-1}$, our result can immediately be improved to an $\\tilde{O}(m^{1 + o(1)} + n\\epsilon^{-2})$ runtime algorithm, by running on a standard sparse sketch of the original graph (following the standard approach around Line 118 of the introduction). Consequently, our result improves over that of [3] for sufficiently sparse graphs, and almost matches their result (up to an $m^{o(1)}$) factor in the dense regime. \n* For general graphs, we also obtain a runtime of $\\tilde{O}(m\\bar{\\kappa}(L_G) \\epsilon^{-1})$, while [3] obtain a runtime with a worse dependence on $\\bar{\\kappa}(L_G)$. In this sense, our algorithms are less sensitive to the conditioning of the graph than those of [3].   \n\n**Question 2: There is a typo on line 63.**\n\n**Response:** It should indeed be $\\tilde{O}(m/\\epsilon), \\tilde{O}(1), \\tilde{O}(n/\\epsilon)$ on Line 63 and will be fixed in the next iteration. Thanks!\n\n**Question 3: There is a typo on line 192.** \n\n**Response:** The $\\delta_{i,j}$ was indeed missing in Line 192, as well as in the second term of Equation (1) and (2). This will be fixed in the next iteration of the submission. Thanks!\n\n**Question 4: Perpendicular is miss-spelled in Line 240.** \n\n**Response:** Thanks! This will also be fixed in the next iteration of the submission.  "}, {"review_id": "7MbWBTCrYZ", "reviewer": "Reviewer_AnJp", "summary": "The paper studies the (approximate) estimation of effective resistance on expander graphs, i.e., graphs with edge expansion $\\Omega(1/\\text{polylog}\\ n)$. The main upper-bound result is a data structure (sketch) for effective resistance that takes $\\tilde{O}(m/\\epsilon)$ time to build, answers each query in $\\tilde{O}(1)$ time, and is of size $\\tilde{O}(m/\\epsilon)$. This improves the Li and Sachdeva [SODA’23] on the construction time on sparse expanders with $O(n/\\epsilon)$ edges. The data structure implies an $\\tilde{O}(n^2/\\epsilon)$-time algorithm to compute all-pairs effective resistance. To complement the upper bound result, the paper further includes a lower bound of $\\tilde{\\Omega}(n^2/\\epsilon^{0.5})$ time for computing all-pairs effective resistance for all algorithms that are not based on fast matrix multiplications (FMM).\n\nThe main technical ingredient for the upper bound result is to use asymmetric factorization of the effective resistance in expander graphs (in the form of $\\ell_{1}$ norm) and apply the count-sketch in $\\ell_{1}$ to achieve the $\\epsilon^{-1}$ compression. For the lower bound side, the paper designs a novel reduction to the triangle detection problem, which improves the exponent on $\\epsilon$ from $1/13$ to $1/2$.\n\nMy general evaluation of the paper is positive. The paper seems to require a good deal of background to read, and I did not manage to check the correctness of the proofs. The high-level intuitions make sense to me, and conditioning on equation (2) is correct, I think everything goes through for the upper bound. As such, as far as I can see, the paper is technically solid, and it makes progress toward an interesting open problem. On the flip side, it seems the improvements of this paper are rather restrictive – compared to Li and Sachdeva [SODA’23], it is only better on expander with $O(n/\\epsilon)$ edges. For the presentations, I think the paper generally makes good efforts to define notions and explain ideas clearly. However, I still believe that the writing assumes a very strong level of knowledge from the reader (see the weakness part for details).\n", "questions": "Most of them are presentation-related issues, and some of them are comments\n- Line 63, do you mean $(\\tilde{O}(m \\epsilon^{-1}), \\tilde{O}(1), \\tilde{O}(n \\epsilon^{-1}))$? (The current notation means sublinear time but linear size.) \n- Similarly, the order seems to be wrong in line 187 – should be $(\\tilde{O}(m \\epsilon^{-2}), \\tilde{O}(\\epsilon^{-2}), \\tilde{O}(n \\epsilon^{-2}))$ according to your notation.\n- Line 120: ‘Building on this work’ – what do you mean? Based on this manuscript?\n- Line 198: there are two ‘vectors’.\n- Formatting issue: For some reason, most of your citations do not contain the venue of publication; some of them have the venue but not the title – please fix this.\n- Minor formatting issue: adding *actual citations* in the abstract seems to be non-standard, i.e., I think it is ok to write as (Chu et al. [Arxiv’18]), but not putting the actual pointer there.\n- Did you state the (conditional) hardness result for triangle detection anywhere in the paper? I would recommend including it in the preliminary.\n- I do not quite understand the logic of ruling out FFM-based algorithms: from the statement of theorem 3, it seems the reduction between effective resistance and triangle detection is unconditional. So why the reduction does not work for FFM-based algorithms? Is it because of the hardness result of triangle detection?\n", "limitations": "I do not see any immediate non-technical/societal limitations on the work. Presentation-wise, it would be good if the paper had discussed more downstream applications.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "As I have mentioned in the general evaluation, I think the paper is technically solid, and the presentation is clear in general. The high-level intuitions provided in the paper are helpful to the readers, and the techniques include novel ideas of the symmetric factorization of the effective resistance. \n", "weaknesses": "Most of them are already mentioned in the general evaluation. Here is a list that would help the authors to address:\n- On the upper bound side, the improvement compared to Li and Sachdeva [SODA’23] is rather limited – the bound is only better on expanders with $O(n/\\epsilon)$ edges.\n- As I said in the general evaluation, the paper seems to require a good deal of background to read. I realize that the authors have already put efforts into making the paper more accessible by defining most of the notions clearly from the get-go and presenting the high-level ideas concisely. However, in my (very subjective) opinion, reading the paper still requires some non-trivial efforts.\n- I think some of the presentation problems can be attributed to unclear notations, for instance: \n1. $\\tilde{O}(\\cdot)$ is defined after multiple usages in section 1, and $\\tilde{\\Omega}(\\cdot)$ is never defined. This is especially confusing since I think you hide $\\text{polylog}$ vs. $1/\\text{polylog}$ factors in the two notations. \n2. The edge-vertex incident matrix $B_{G}$ is briefly mentioned but never formally defined (I know that it is): this could be an issue for the general audience at NeurIPS to understand. \n3. Is $J$ in line 194 the matrix for the JL projection? It is never mentioned.\n- Finally, for NeurIPS, it would be good if you could spend more passage talking about downstream applications and what your bound would imply therein.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and questions! In the general response, we have discussed how we plan to incorporate some of the changes to the preliminary/introduction of the paper in response to your helpful suggestions for content to include therein. \n\n**Question 1: Clarifying question on Line 120. What do you mean by “building on this work”?**\n\n**Response:** Thank you for the question, and we apologize for the confusion. “Building on this work” was intended to “Building on this line of research…” We did not mean to imply that [1] builds on our work. Instead, we meant that [1] builds on the aforementioned long line of research on sketching and sparsification. We will update the language to “Building on the aforementioned line of research on graph sketching and sparsification, …” to improve clarity.\n\n**Question 2: There is a formatting issue in the bibliography where venues are not showing up properly.**\n\n**Response:** Thank you for pointing this out; we will update the references to include the venue in the next iteration of the submission. Sorry for any inconvenience this caused.  \n\n**Question 3: There are typos on lines 63, 187, 120, and 198.** \n\n**Response:** Thank you for catching these typos. It should indeed be $\\tilde{O}(m/\\epsilon), \\tilde{O}(1), \\tilde{O}(n/\\epsilon)$ on Line 63, and $(\\tilde{O}(m \\epsilon^{-1}), \\tilde{O}(\\epsilon^{-2}), \\tilde{O}(n\\epsilon^{-2})$ on Line 187. Thank you for catching the duplicated word vector on line 198. These errors will be corrected in the next iteration of the submission.\n\n**Question 4: The triangle detection hardness result is not stated.**\n\n**Response:** We discuss the subcubic triangle detection problem and its conjectured hardness in line 70, in the body, but we did not state it formally inside a definition environment. We will update this in the next iteration of the submission to state the problem formally as well as concrete conjecture in a separate environment to improve the clarity.\n\n**Question 5: The abstract citations are nonstandard.**  \n\n**Response:** Thank you for the feedback, we will modify our abstract towards your suggested form of citations. \n\n**Question 6: I don't quite understand the logic of ruling out FMM-based algorithms, as Theorem 3 does not say anything about FMM.**\n\n**Response:** Thank you for the question. Our reduction from algorithms for effective resistance to algorithms for triangle detection actually works for any type of algorithm for effective resistance. This is why our statement of Theorem 3 does not mention FMM. Informally, Theorem 3 essentially says that if we have some type of effective resistance algorithm, we can produce a similar type of triangle detection algorithm. **One** implication of Theorem 3 is the following: if we have a combinatorial algorithm for effective resistance (i.e., non-FMM based algorithm) with some runtime then we can get a combinatorial algorithm for triangle detection with a related runtime. We elaborate on this below. \n\nAlthough the reduction stated in Theorem 3 does not make any assumption on the type of effective resistance algorithm we start with, Theorem 3 only implies a conditional lower bound against non-FMM based (i.e., combinatorial) algorithms for effective resistance (barring a major advance in combinatorial algorithms). This is because there already exists a simple subcubic algorithm for triangle detection using FMM (we can take the adjacency matrix A raised to the power of 3, and check whether any of the diagonal entries of A^3 are positive.) The **conditional hardness stems from the fundamental challenge** of obtaining subcubic triangle detection algorithms which do not rely on FMM. Obtaining any non-FMM algorithm for triangle detection would be a major algorithmic breakthrough, and consequently, it is a common hardness assumption in the literature. Section 6.1 of the supplementary material points to a few relevant reference. \n\n**Question 7: It would be great if the authors can discuss more downstream applications.**\n\n**Response:** Thank you for your suggestion. We discuss some downstream applications of effective resistance estimation more broadly in the introduction (Line 23-37), but we would be open to include more discussions, perhaps in the conclusion or elsewhere if you feel it would be helpful. Please let us know if you have any recommendations for specific applications or discussions you would like for us to incorporate. "}, {"review_id": "y31KV9RPcY", "reviewer": "Reviewer_UUSU", "summary": "The authors consider the problem of estimating effective resistance both for all edges of a graph and between any pair of nodes. This quantity is incredibly useful for sampling from a graph to produce a sparser graph with similar spectral properties. Furthermore, this quantity can provide a useful metric for the importance of an edge to the connectivity of the network. Within this context the authors restrict to a subclass, expander graphs, which have better connectivity properties. The practical application of these graphs is much more limited, but as the authors point out, they are commonly used as a first step towards giving more general algorithms. The authors provide a new algorithm that for sparse graphs gives an asymptotically faster algorithm than the previous work. In addition, the authors improve upon the lower bound runtime by reducing to the triangle detection problem. ", "questions": "What's the biggest bottleneck in your opinion for applying similar techniques to the ones you provide in this work to improve the runtime for general graphs? ", "limitations": "The authors adequately addressed the limitations", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. Improves the asymptotic runtime for an important problem on sparse graphs of a commonly studied subclass, expander graphs.\n\n2. Applies a new clever factorization technique for expander graphs with substantial technical depth\n\n3. Gives a new approach for lower bounding the runtime through a reduction to the triangle detection problem that extends to additional problems", "weaknesses": "For a broad ML venue the practical application of this theoretical work is quite limited given the restriction to expander graphs. It makes good progress in a well-studied area in the theoretical community but may be more appropriate for a theory-centric venue. To be of more general interest, it would be preferable to see progress upon general graphs by either making asymptotic or practical improvements. I would very much welcome the authors rebuttal (see questions section) but it also feels like these techniques, specifically the asymmetric factorization bounding, which is very clever, could not be reasonably extended to general graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and feedback! We have addressed the limitations of the expander case and high-level motivation for considering the general response (see Comment 3 therein). In addition, we have described the key bottleneck in the general response as well. Thank you again for your suggestions!"}]

Author rebuttal:
We thank the reviewers for their helpful comments and questions. We are encouraged that the reviewers appreciated novelty in our technical contributions (R2, R3, R5) and cleverness in our techniques for obtaining our improved upper and lower bounds (R4, R6). We are glad that they found our paper to be well-organized/well-written (R1, R3, R4) and our discussion of the approach to be helpful for providing intuition for the proofs (R2, R5). We are also glad that reviewers recognized the motivation for studying the effective resistance estimation problem (R3, R4). 

In this general response, we will respond to some common comments/questions relating to the submission. Additional reviewer-specific questions are answered in the individual responses. 

**Comment 1: Additional content to incorporate in the Intro/Prelims}** (R1, R5). Based on the reviewers’ suggestions, below is a list of a changes we plan to make to make to clarify the notation and our results in next iteration of our submission:
* Define the edge incidence matrix in the prelims (R5).
* Include more background on standard facts in spectral graph theory in the preliminaries (e.g., Cheeger’s inequality, equivalent expressions for effective resistance, etc.) (R1, R5).
* Move the informal discussion of the triangle detection problem definition and hardness result from the introduction into a definition/conjecture environment for increased clarity (R5). 
* Define $\tilde{\Omega}$ clearly in the prelims (Section 2) and add a forward reference when $\tilde{\Omega}$ and $\tilde{O}$ is first mentioned in Section 1 (R5).
* Define the Johnson-Lindenstrauss (JL) projection matrix (R5). 

We welcome any other suggestions the reviewers may have for additional background that would be helpful to incorporate into the introduction/prelim of the paper.

**Comment 2: Empirical validation** (R1, R3). R1 and R3 commented that empirical validation of our algorithm against other effective resistance estimation algorithms would be interesting. We agree an extensive empirical comparison of various effective resistance estimation algorithms would be an intriguing direction for future work. One potential obstacle in this direction is that we are unaware of the extent to which previous algorithms for effective resistance estimation such as that of [1], [2], and [3] have been implemented. Nevertheless, we believe it would be interesting to do a comprehensive comparison of the variety of effective resistance estimation algorithms on synthetic and real-world datasets, however this is outside the scope of our current work.

**Comment 3: What are the bottlenecks in extending the algorithmic upper bound of $\tilde{O}(m\epsilon^{-1})$ to general graphs, and what is the motivation for considering expanders?** (R3, R6, and generally touched on by all reviewers). It is indeed a limitation of our analysis that we are only able to shown an $\tilde{O}(m\epsilon^{-1})$ algorithm for expanders, and it is an interesting open question to obtain an $\tilde{O}(m\epsilon^{-1})$ effective resistance estimation algorithm for general graphs. As we have discussed and R6 mentions, in several spectral graph theoretic problems (such as spectral sketching, sparsification, etc.) a key step towards faster algorithms on general graphs is to obtain faster algorithms on expanders. In a variety of problems studied in the literature, fast algorithms on expanders have been combined, for example, with expander decomposition algorithms to generalize algorithms on expanders to algorithms which can obtain comparable guarantees on general graphs. Consequently, the effective resistance estimation problem on expanders is an interesting previously studied problem in the literature ([3, 33]). 

While our techniques do not yield an $\tilde{O}(m\epsilon^{-1})$ time algorithm for general graphs, we have shown our algorithm itself can still be applied to general graphs and may give some interesting results for graphs whose conditioning does not grow too quickly with m or n. For general graphs, the only difference is that the runtime becomes $\tilde{O}(m\bar{\kappa}(G)\epsilon^{-1})$, where $\bar{\kappa}(L_G)$ is the normalized pseudo-condition number of the graph, which we have defined in the preliminaries. For expanders, $\bar{\kappa}(G) = \tilde{O}(1)$, enabling our main result. However, we believe our result still gives an interesting runtime bound for families of graphs where $\bar{\kappa}$ does not grow too quickly with $n$. For instance, compared to the results $\tilde{O}(m\epsilon^{-1.5})$ of [1] our result gives an interesting tradeoff between $\bar{\kappa(L_G)}$ and $\epsilon$. Likewise, compared to the result $\tilde{O}(m + n\epsilon^{-2}\bar{\kappa}^3(L_G))$ obtained by [3], our result is better when $\bar{\kappa}(L_G) > (m \epsilon/n )^{1/2}$. 

The main bottleneck in extending our results to the general graph case is that for general graphs, we do not know how to bound the l1 norm of the second term in the asymmetric factorization of effective resistance  to be $\tilde{O}(1)$ (this was also well-articulated by R6). To be mathematically concrete, we do not have a strong enough lower bound on the second eigenvalue of the normalized graph Laplacian (or equivalently, a strong enough upper bound on the normalized pseudo-condition number of the graph) in order to ensure that the power series expansion converges quickly in l1 norm. For general graphs, we were only able only bound the l1 norm of the second term in the asymmetric factorization to be $\tilde{O}(\bar{\kappa}(G))$, leading to the $\tilde{O}(\bar{\kappa}(G) m \epsilon^{-1})$ time algorithm for general graphs. Compared to the work of [3], our algorithms have a better dependence on $\bar{\kappa}(L_G)$ for general graphs. Technical details of this result are explained in more detail in Section 6.1 and Section 6.2.3 in the supplementary. 

Meta-review: This paper received universally strong reviews, and all were in agreement that it makes an interesting theoretical contribution to an important problem (effective resistance estimation in sparse graphs), using novel techniques. The algorithmic contribution is limited in scope as it applies specifically to expander graphs. However, this is an interesting case which has been studied in prior work.

We encourage the authors to take reviewer suggestions on presentation into account when revising the paper. While perhaps beyond the scope of this paper, we also encourage them to consider an empirical evaluation of their work and related baselines.
Decision: Accept (poster)