# towards_optimal_effective_resistance_estimation__c20712f9.pdf

Towards Optimal Effective Resistance Estimation

Rajat Vadiraj Dwaraknath

Stanford University rajatvd@stanford.edu

Ishani Karmarkar Stanford University ishanik@stanford.edu

Aaron Sidford Stanford University sidford@stanford.edu

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 r Opm 1q-time algorithm that produces with high probability, an r Opn 1qbit sketch from which the effective resistance between any pair of nodes can be estimated, to p1 q-multiplicative accuracy, in r Op1q-time. Consequently, we obtain an r Opm 1q-time algorithm for estimating the effective resistance of all edges in such graphs, improving (for sparse graphs) on the previous fastest runtimes of r Opm 3{2q [Chu et. al. 2018] and r Opn2 1q [Jambulapati, Sidford 2018] for general graphs and r Opm n 2q 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 r pn2 1{2q-time, improving upon the previous best such lower bound of r pn2 1{13q [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.

1 Introduction

In a weighted, undirected graph G the effective resistance between a pair of vertices a and b, denoted r Gpa, bq, is defined as the energy of a unit of electric current sent from a to b in the natural resistor network induced by G. Effective resistances arise for a broad set of graph processing tasks and have multiple equivalent definitions. For example, r Gpa, bq is proportional to the expected roundtrip commute time between a and b in the natural random walk induced on the graph and when ta, bu is an edge in the graph, it is proportional to the probability that the edge is in a random spanning tree.

Effective resistances also form a particular class of metrics on the vertices [1,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 in social networks [3] as 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 to 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]. More recently, effective resistances have also been used to analyze the problem of oversquashing in GNNs and in designing algorithms to alleviate oversquashing [24 26] and have been applied to increase expressivity when incorporated as edge features into certain GNNs [27].

37th Conference on Neural Information Processing Systems (Neur IPS 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 x y as shorthand for p1 qy x p1 qy 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 an undirected, weighted graph G p V, E, wq, a set of vertex pairs S Ñ V ˆ V , and P p0, 1q and must output r P RS such that with high probability (whp.), rpa,bq r Gpa, bq for all pa, bq P S.

The state-of-the-art 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,20]. The state-of-the-art runtimes for this problem are r Opn2 1q due to [28] and r Opm 1.5q due to [30]. A major open problem is whether improved runtimes, e.g., r Opm 1q (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.e., expanders. Expanders are a non-trivial, previously studied, special case that is often the first step or a key component for developing more general algorithms [32]. In particular we provide an r Opm 1s p Gqq time algorithm where s is a measure of the graph s connectivity. Previously, the only non-trivial improvement in this setting was an independently obtained runtime of

r Opm n 2ps p Gqq3{2q for graphs with s p Gq r Op1q [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 mop1q factor) in dense graphs. 1

Interestingly, we obtain our main result by providing new effective resistance sketch algorithms. Definition 2 (Effective Resistance Sketch). We call a randomized algorithm an p Ts, Tq, sq-effective resistance sketch algorithm if given an input n-node, m-edge undirected, weighted graph G p V, E, wq and P p0, 1q in time Op Tsp G, qq it creates a binary string of length Opsp G, qq from which when queried with any a, b P V , it outputs ra,b r Gpa, bq whp. in time Op Tqp G, qq.

Effective resistance sketching algorithms immediately imply algorithms for the effective resistance estimation problem. We obtain our result by obtaining an p r Opm 1q, r Op1q, r Opn 1qq-effective resistance sketch algorithm for expanders (see Section 1.1 for a comparison to prior work).

Lower Bounds. Given the central role of effective resistance estimation and the challenging openproblem of determining its complexity, previous work has sought complexity theoretic lower bounds for the problem. [33] showed a conditional lower bound of pn2 1{13q for the problem by showing that an algorithm that computes effective resistances in pn2 1{13 δq for some δ 0 time could be used to obtain a subcubic algorithm for the triangle detection problem, that we define below. Definition 3 (Triangle Detection Problem). Given an n-node undirected unweighted graph G p V, Eq, determine whether there are distinct a, b, c P V with ta, bu P E, tb, cu P E and tc, au P 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 an algorithm 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 subcubic algorithm for triangle detection that doesn t use FMM implies a subcubic BMM algorithm that doesn 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.

1While our algorithms for the effective resistance estimation problem (Definition 1) were obtained indpendently, our writing and discussion of effective resistance sketch algorithms (Definition 1) was informed by their paper. We provide a more complete comparison of our work with prior results in Table 1.

In this paper we take a 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 pn2 1{13q to r pn2 1{2q 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 to an 1{2-factor among non-FMM based algorithms, barring a major breakthrough in BMM.

Broader Linear Algebraic Tools. The effective resistance between vertex a and vertex b in a graph G has a natural linear algebraic formulation. For all a, b P V it is known that r Gpa, bq ~δa,b L:

G~δa,b, where LG P RV ˆV is a natural matrix associated with G known as the Laplacian matrix and ~δa,b ea eb (see Section 2 for notation). Thus, sketching effective resistances can be viewed as problems of preserving information about subsets of entries of the pseudoinverse of a 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, we 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 a 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 3, and present lower bounds in Section 4. 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 in Section 3 we describe a extensions of our work to broader linear algebraic problems involving SDD and PSD matrices. Our main algorithmic result is a new efficient effective resistance sketch for expanders, a term which is used to refer to graphs with r p1q-expansion. Definition 4 (Expander). For 0, we say that a graph G p V, E, wq has -expansion if φp Gq, where φp Gq denotes the conductance of G and is defined as

φp Gq : min SÑV,SRt0,V u

tu,vu:u PS,v PV z S wu,v

v PV z S du

, where du :

Theorem 2. There is an p r Opm 1q, r Op1q, r Opn 1qq-effective resistance sketch algorithm for graphs with r p1q-expansion.

Table 1 summarizes and compares our Theorem 2 to previous work on effective resistance sketches, including naive algorithms to explicitly compute the pseudoinverse of the Laplacian of G, which can be computed in Opn!q time using FMM or r Opmnq time using a Laplacian system solver (labeled Solver). 2 A p Ts, Tq, sq effective-resistance sketch algorithm implies an Op Ts |S|Tqq algorithm for the effective resistance estimation problem. Hence, Theorem 2 implies the following.

Theorem 3 (Effective Resistance Estimation on Expanders). There is an r Opm 1 |S|q time algorithm which solves the effective resistance estimation problem for graphs with r p1q-expansion.

Effective resistance sketches are a 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.e., computing a sparse graph G1 such that quadratic forms in the Laplacian of G1 approximately preserves quadratic forms in the Laplacian of G). Building on this work, [30] showed there is an algorithm which processes a graph G on n nodes and m edges in Opm1 op1qq time and produces a sparse sketch graph H with only r Opn 1q edges such that r Gpa, bq r Hpa, bq

2! n2.37188 [35] denotes the fast matrix multiplication constant.

for all a, b P V . Consequently, any algorithm which runs in r Opm cq on expanders can be improved to run in r Opm1 op1q n pc 1qq on expanders simply by running the algorithm on H instead of G.

Table 1: Effective Resistance Sketch

Citation Tp Tq s

FMM n! 1 n2

Solver nm 1 n2

[5] m 2 2 n 2

[28] n2 1 1 n 1

[29] m n 2 1 n 1

This Paper m 1 1 n 1

Table 2: Effective Resistance Estimation Citation Runtime S Restrictions

FMM n! |S| None Solver nm |S| None [5] n2 2 S V ˆ V [28] n2 1 S V ˆ V [19] m pn |S|q 2 None [37] m |S| 2 None [30] m 1.5 S E [29] m n 2 |S| None This Paper m 1 |S| 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 are reported up to to r Op q. The methods of This Paper and [29] apply only to expanders; however, the remaining works apply to general graphs. As discussed, when m1 op1q n pc 1q opm cq, any runtime dependence on m c in the table can be improved to a dependence on mop1q 1 n pc 1q.

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 V ˆ V in r Opn2 1{13 δq for some δ 0, would imply a combinatorial subcubic deterministic algorithm which detects a triangle in an n-node undirected unweighted graph. We improve on their result, as follows.

Theorem 4. Given a combinatorial algorithm which solves the effective resistance estimation problem for S V ˆ V on graphs with r p1q-expansion in r Opn2 1{2 δq time for δ 0, we can produce a randomized combinatorial algorithm which solves the triangle detection problem on an n-node graph in r Opn3 2δq time whp.

Theorem 4 implies an r pn2 1{2q randomized conditional lower bound for the problem of estimating effective resistances of all pairs of nodes in an undirected unweighted expander graph, while [33] shows only an pn2 1{13q lower bound. As we show in Section 4, by a simple reduction we can extend any r pn2 cq lower bound for the all-pairs effective resistance problem to a r pm cq lower bound for the all-edges effective resistance problem. Consequently, our result also yields a

r pm 1{2q randomized lower bound for the problem of estimating effective resistances of all edges in 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 we define below. Definition 5 (Spectral Sum). For f : R Ñ R and A P Rnˆn with singular values σ1p Aq σ2p Aq σnp Aq, we define the spectral sum Sf : Rnˆn Ñ R as Sfp Aq : n

i 1 fpσip Aqq.

[33] showed that for several spectral sums Sf, any combinatorial algorithm that outputs Y Sfp Aq in pnγ cq time on an n ˆ n PSD matrix would imply an Opnγ cq time combinatorial algorithm which solves the triangle detection problem, where the scaling varies depending on the specific Sf (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 a combinatorial algorithm which on input B P Rnˆn outputs a spectral sum estimate Y Sfp Bq in O pnγ cq time with γ 2 for the spectral sums in Table 3, we can produce a randomized combinatorial algorithm that can detect a triangle in an n-node graph whp. in

r O pnγ cq time, where is a scaling that depends on properties of the function f (see Table 3 for values of for several spectral sums.)

[33] This Paper

Spectral Sum TD Runtime Lower Bound TD Runtime Lower Bound

Schatten 3-norm nγ 4c n2 1{4 nγ 5c{2 n2 2{5

Schatten p-norm, p 1, 2, nγ 13c n2 1{13 nγ 10c n2 1{10

SVD Entropy nγ 6c n2 1{6 nγ 5c n2 1{5

Log Determinant nγ 6c n2 1{6 nγ 5c n2 1{5

Trace of Exponential nγ 13c n2 1{13 nγ 10c n2 1{10

Table 3: Runtimes for the triangle detection (TD) problem in an n-node graph using algorithms that produce p1 q multiplicative approximations to various spectral sums in Opnγ cq time. The second columns contain the best achievable runtimes for γ 2 that do not use FMM, barring a breakthrough in subcubic triangle detection. All runtimes are reported up to r Op q.

2 Preliminaries

General notation. We use Ai,j to denote the pi, jq-th entry of A. For A P Rnˆn we use λ p Aq for its spectrum, λip Aq and σip Aq for its i-th smallest eigenvalue and singular value respectively, and p Aq : |λnp Aq| for its spectral radius. } }p denotes the p-norm. When A is PSD, λminp Aq denotes its smallest nonzero eigenvalue and p Aq : λnp Aq{λminp Aq denotes its pseudo-condition number. We use x , y for the Euclidean inner product,

for the all ones vector, and ei for the i-th standard basis vector. We define ~δi,j : ei ej and rks : t1, ..., ku. We use x y as shorthand for p1 qy x p1 qy. For v P Rn, we use vri : js for the sub-vector from index i to j. We use v K w to indicate that v, w P Rn are orthogonal (i.e., v Jw 0).

Graphs. We use G p V, E, wq to denote a weighted undirected graph on V with edges E and edge weights w P RE

0 (or G p V, Eq if unweighted). We use AG to denote its (weighted) adjacency matrix p AGqu,v wu,v for u, v P V ˆV and DG to denote its diagonal (weighted) degree matrix p DGqu

tu,vu PE wu,v for u P V (treated as wu,v 1 if G is unweighted). We define LG : DG AG as its graph Laplacian. dmaxp Gq and dminp Gq refer to the max and min diagonal entry in DG. We may drop the argument or subscript G if it is clear from context. The effective resistance between nodes i, j P V is denoted r Gpi, jq ~δJ

G~δi,j. We assume all input graphs are connected, as effective resistances can be computed separately on connected components. We use BG to denote the E ˆ V edge-incidence matrix of G, where p BGqe,u 1 and p BGqe,v 1 for all e P E, and e tu, vu, with BGe,l 0 for all l u and l v.

Symmetric Diagonally Dominant (SDD) Matrices A matrix M P Rnˆn is SDD if it can be decomposed as M DM AM, where the DM is a diagonal matrix with non-negative entries and AM is a matrix with zeros on the diagonal such that di,i n

j 1 |ai,j|. We define the normalization

of M as NM : D 1{2

M . Throughout this paper, we 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 dmaxp Mq and dminp Mq to 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.

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 a graph (or SDD matrix).

Definition 6 (Normalized (pseudo-)condition number). We define the normalized (pseudo-)condition number of an SDD matrix M P Rn as s p Mq : λnp NMq{λminp NMq.

To connect the normalized condition number to expander graphs, we can apply Cheeger s inequality, which guarantees that if G has -expansion for some p1q, then s p LGq λnp NLGq{λ2p NLGq 4{ 2 r Op1q. Theorem 6 (Cheeger s Inequality [38]). Let G p V, E, wq be an undirected graph. Then, 1 2λ2p NLq φp Gq

In addition, we leverage the fact that effective resistances can be expressed in several equivalent expressions. In particular, it is known that:

r Gpi, jq ~δJ

G~δi,j ~δi,j D 1{2NG

:D 1{2~δi,j p W1{2

G~δi,jq Jp W1{2

where WG P REˆE 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 r Op q (resp., r p q) 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 in a matrix, the maximum and minimum diagonal element of a matrix, the maximum and minimum weighted degree of a graph, , the condition number, and the normalized psuedo-condition number of a matrix. We say event E occurs with high probability in t if P r Es 1 t c, where c 0 can be controlled by appropriately configuring the algorithm parameters. We may simply say that an event occurs with high probability or whp. if it occurs with high probability in the size of a matrix or number of nodes in a graph.

3 Algorithmic Results

In this section, we present our main algorithmic results. Section 3.1 outlines our approach to effective resistance sketches and estimation; we 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 our 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 an ( r Opm 2q, r Op 2q, r Opn 2q)-effective resistance sketch by using the Johnson Lindenstrauss Lemma (JL) [39] and its algorithmic instantiations [40]. Lemma 1 (Johnson-Lindenstrauss Lemma [40]). Given fixed vectors v1, ..., vn P Rd and P p0, 1q, let J be an independently sampled random matrix in t 1{

kukˆd. For k r Oplogpnq 2q, whp. in n, }Jvi}2 }vi}2 for all i P rns.

[5] observe that r Gpi, jq p W1{2

G~δi,jq Jp W1{2

G~δi,jq. Consequently, w.h.p in n, }JW1{2

G~δi,j}2 r Gpi, jq. With SDD linear system solvers, JW1{2

G can be approximated in r Opm 1q time, from which }JW1{2

G~δi,j}2 can be queried in r Op 2q time.

Our approach: asymmetric Count Sketch in 1. 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 r Op 2q-sketch dimension for vectors with small 1 norm with comparable guarantees, e.g., Count Sketch. Count Sketch is a classic memory-efficient algorithm for estimating the number of occurences of various datapoints in a data stream [41] and efficiently computing inner products [42]. Given v P Rn and integer parameters s, t 0, Count Sketch transforms v to a vector Sv P R3tsˆn, where S P R3tsˆn is a 3t-column-sparse 0/1 matrix. Lemma 2 is a special case of Theorem 4 from [42], which provides accuracy guarantees for inner product estimation using Count Sketch.

Lemma 2 (Special Case of [42], Theorem 4). Let vectors v, w P

n. Let S be a random Count Sketch matrix. Let xi xp Svqrpi 1qs 1 : i ss, p Swqrpi 1qs 1 : i ssy for i P r3ts, and let X denote the median of txiu. For s O

|xv,wy| , }v}2

2 2|xv,wy|2

, and t logpncq,

|X xv, wy| |xv, wy| with probability at least p1 n cq.

To improve the guarantee in Lemma 2 to hold whp. for all v, w P S rather than for each fixed pair, one can simply choose t logpnc|S|q and apply a union bound. Consequently, if we knew that }W1{2

1{r Gpi, jq r Op1q, then building a Count Sketch with s r Op 1q would

yield a r Opn 1q-size sketch, improving over the r Opn 2q sketch obtained using the 2 JL sketch in [5]. Unfortunately, it is unclear if and when such a bound holds, and so, it is unclear how the 1 Count Sketches could be useful in this setting. This leads to the main insight that fuels our algorithms. Rather than seeking a symmetric factorization of r Gpi, jq as a quadratic form v Jv and applying a sketching procedure to v, we instead work with an asymmetric factorization. In particular, we observe

r Gpi, jq x D 1

LG~δi,j, D1{2

L p NLGq:D 1{2

LG ~δi,jy. (1)

At first glance, it may seem unclear why (1) is helpful. However, we show that indeed, for expanders

L p NLq:D 1{2

1 {r Gpi, jq r Op1q. (2)

Our main result essentially follows from (2). Using SDD linear system solvers, we can efficiently approximate SD1{2

L p NLq:D 1{2

L P R r Op 1qˆn in r Opm 1q time, yielding our Tq of r Opm 1q and s of r Opn 1q (see discussion in supplementary material). Moreover, SD 1

L is r Op1q-sparse, due to the structure of Count-Sketch. So, using our (approximate) access to SD1{2

L p NLq:D 1{2

L , for any query i, j P V , we can efficiently approximate (1) using the recovery procedure of Lemma 2 in r Op1q 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 r Op1q 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 p Ts, Tq, sq-spectral sketch data structure for a PSD matrix A P Rnˆn if given A P Rnˆn and P p0, 1q, the algorithm creates a binary string of length Opsp A, qq in time Op Tsp A, q, from which, for any supported query b P Rn, w.h.p it outputs q Apbq b JAb in time Op Tqp A, qpnnzpbqq2q.

Our spectral sketches of SDD matrices M will only support DM-numerically sparse query vectors.

Definition 8 (D-numerically sparse). For a diagonal matrix D, the D-numerical sparsity of x P Rn

is ns D pxq :

2. We say x is pc, Dq-numerically sparse if ns D pxq c.

Definition 8 is restrictive; however, several natural classes of vectors satisfy the requirements. For example,

i are (1, D)-numerically sparse and ~δi,j is (2, DM)-numerically sparse for any i, j P rns and invertible diagonal matrix D P Rnˆn (see supplementary material for additional examples.)

The following asymmetric rearrangement of quadratic forms is crucial to our analysis. Lemma 3. Let M P Rnˆn be SDD and x P Rn be orthogonal to ker p Mq. Then,

M p NM{2q:D 1{2

Proof. For notational convenience, let N M NM{2. Let v M:x p DM AMq:x. Note that D 1{2

M x K ker p NMq, and 2D1{2

M M. Consequently, v 1 2D 1{2

M x, and hence x JM:x 1 2x DM

1{2xy. The second equality now follows immediately by rearranging terms. To obtain the inequality, note that, because M is SDD and D is invertible, NM is PSD. Furthermore, 2I NM I D 1{2

M , which is also PSD, as λ p AMq Ä r dmax, dmaxs. So, 0 λ p NMq 2. So, λminp NMq 1{2 and the lemma follows.

Lemma 4 bounds

M p NM{2q:D 1{2

1. The proof uses the power series expansion of p NM{2q:.

Lemma 4. Let M P Rnˆn be an SDD matrix and x P Rn be a unit vector orthogonal to ker p Mq. Then

M p NM{2q:DM

1, 2s p Mq log

ndmax2s p Mq{

Combining our Lemmas 3 and 4 with the guarantees of Lemma 2 and prior work on SDD linear system solvers (see supplementary material), we obtain the following theorem. Theorem 7. For any SDD matrix M P Rnˆn, there is an algorithm to construct an p r Ops p Mq nnzp Mq 1q, r Op1q, r Ops p Mq n 1qq-spectral sketch data structure of M: supported over queries S, where S is any set of p r Op1q, DMq-numerically sparse vectors orthogonal to ker p Mq.

Because the ~δi,j queries appearing in effective resistance computations are 2-sparse and p2, DMqnumerically sparse for all SDD matrices M, taking M LG in Theorem 7 immediately implies Theorem 2 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 queryefficient sketching procedure for approximating quadratic forms of well-conditioned PSD matrices.

Theorem 8. There is an algorithm to construct an p r Op p Aqnnzp Aq 2q, r Op1q, r Op p Aqn 2qqspectral sketch data structure of A supported over S, where S is any set of vectors orthogonal to ker p Aq and A is PSD.

In comparison, JL [39] gives an p r Opn!q, r Op 2q, r Opn 2qq-spectral 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 8 may achieve better construction time and query time than JL while maintaining comparable compression.

4 Lower Bounds

In this section, we present our main hardness results. Section 4.1 outlines our approach. In Section 4.2, we present our lower bounds for the problem of estimating effective resistances for all pairs of nodes (case where S V ˆ 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 of Previous Work The approach of [33] begins with the fact that G has a triangle if and only if tr

{6 1. They use the fact that various spectral sums Sf of the of the SDD matrix I δAG (for δ sufficiently small) can be expressed as a power series Sfp I δAGq 8

k 0 ckδk trp Ak

Gq. The first two terms of this series can be computed directly. So given Y Sfp I δAGq, one can estimate tr

, where the estimation error is controlled by the magnitude of the first two terms of the series and the tail error due to truncating at the third term. By bounding this estimation error, [33] show that, for appropriate choices of δ, Y Sfp I δAGq yields an additive 1/2 approximation to tr

, which is sufficient for triangle detection. They also reduce the problem of estimating the spectral sum tr

for an SDD matrix B to the all pairs effective resistance estimation problem.

Our Approach We use three key techniques to better bound the estimation errors incurred in the power-series-inspired 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

{6 to computing the trace of an SDD matrix as in [33], we use a reduction that closely resembles the structure of effective resistances. For 0 sufficiently small,

Since AG is known, given access to ~δJ

n AGq 1~δi,j, we can estimate the entries of A2

G, where the estimation error is controlled by and the tail error of truncating (3) at the third term. By bounding this estimation error, for appropriate choice of , we can obtain additive 1/2 approximations to all entries of A2

G, which is sufficient to identify all paths of length 2. We can then detect a

triangle by simply scanning for an edge tu, vu such that u and v are connected by a path of length 2. Estimating the entries of A2

G leads to lower estimation error than estimating tr

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 a randomly sampled tripartition of the original graph preserves triangles with constant probability. To detect a triangle in a tripartite graph G p V1 \ V2 \ V3, Eq, we construct a graph H by removing all edges E1,2 : ttu, vu P E : u P V1, v P V2u between V1 and V2. G has a triangle if and only if there is an edge tu, vu P E1,2 and a path of length 2 between u and v in H. Crucially, we can show that the third term s A3

H does not contribute to the tail error when estimating the tu, vu-th entry of

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 AH below. Definition 9 (Symmetric Random Signing). Given a symmetric matrix A P Rnˆn, its symmetric random signing s A is the random matrix with s Ai,j : i,j Ai,j, where i,j are independent Rademacher random variables that satisfy i,j j,i.

We show that this random signing preserves the non-zeroness of entries of A2

H with constant probability, allowing us to detect whether G has a triangle even if we replace AG in (3) with s AH instead. This is beneficial, as matrix Chernoff guarantees

2 r Op?nq whp. whereas }AH}2 may be as large as n. So the tail error of truncating the power series is smaller. To compute entries of s A2

H efficiently using effective resistance estimates on expanders, we first show that we can use all pairs effective resistance estimates on expanders to estimate ~δT

i,j M 1~δi,j for all i, j P rns, where M p I Qq is an SDD matrix with p Qq 1{3. Then, by choosing M I

n s AH as in (3) for an appropriate constant , we can estimate s A2

H from estimates of ~δT

i,j M 1~δi,j. This yields our lower bound on the all pairs effective resistance estimation problem.

Additionally, we show that random signing also preserves the non-zeroness of tr

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 s 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 ˆ V ). Definition 10. In the SDD effective resistance estimation problem, given an SDD matrix M such that DM I, AM Q, with p Qq 1{3 and P p0, 1q, we must output rr P Rn2 such that rra,b ~δJ

a,b M 1~δa,b @a, b P rns. We call ~δJ

a,b M 1~δa,b the SDD effective resistance of pa, bq in M.

For brevity, we use rrp Mq 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 r p1q-expansion in r Opn2 cq time for some c 0, we can produce an algorithm to solve the SDD effective resistance estimation problem in r Opn2 cq time.

To prove Lemma 5, we first prove the lemma for the case where Q is entrywise non-negative by constructing an expander G with n 1 vertices such that r Gpa, bq ~δJ

a,b M 1~δa,b for all a, b P rns. We extend the reduction to arbitrary Q by constructing Q1 of size 2n so that Q1 is entrywise non-negative and rrp I Qq is a simple linear transform of rrp I Q1q.

We turn our attention to reducing the triangle detection problem to the SDD effective resistance problem. As discussed, a key aspect of our approach is to work with the random signing s AG of AG. Lemma 6 shows that to determine whether p A2

Gqi,j 0 with constant probability, it suffices to determine whether p s A2

Gqi,j 0. Matrix Chernoff ensures whp. p s AGq r Op?nq, while p AGq could be as large as n [44]. So, estimating entries of s AG leads to lower power series tail error. Lemma 6. For i j, if p A2

Gqi,j 0, then p s A2

Gqi,j 0; if p A2

The idea of the proof is that if ta, bu, tb, cu exist in G, either a,c 1 or a,c 1 results in p s A2

Gqa,c 0. Finally, we use 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

r Opn2 cq time, we can produce a randomized algorithm that solves the triangle detection problem in r Opn2p1 cqq time whp.

Theorem 9 and Lemma 5 with c 1{2 δ immediately imply our main result Theorem 4.

Additionally, we 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 effective resistance estimation problem (i.e., Definition 1 where S E) in r Opm cq time, we can produce an algorithm to solve the all pairs effective resistance estimation problem in r Opn2 cq time for some c 0.

The rough idea behind the reduction is to 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 r pm 1{2q randomized lower bound for the all edges effective resistance estimation problem on graphs with graphs with r p1q-expansion.

4.3 Improved Lower Bounds for Spectral Sum Estimation

Finally, we discuss our improved lower bounds for various spectral sum estimation problems. Analogous to Lemma 6, in the following lemma we show that to determine whether a graph has a triangle (i.e., tr

0) with constant probability, it suffices to determine whether tr

Lemma 8. If tr

0, and if tr

The central idea of the proof is that if a triangle ta, bu, tb, cu, tc, au exists in G, then amongst the 4 possible configurations of the Rademacher random signing variables a,b and b,c, at least one configuration must result in

ˇˇ 0. By following the proof of Theorem 15 from [33], and replacing their use of AG with a symmetric random signing s AG, we obtain an improved randomized version of their result by leveraging the smaller spectral radius of s 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 to 1 when carefully applied to 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 it 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 in 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 r Opm 1q time algorithm for estimating the effective resistance of all edges in a general (non-expander) graph and extending our r pn2 1{2q 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 a Microsoft Research Faculty Fellowship, NSF CAREER Award CCF-1844855, NSF Grant CCF-1955039, a Pay Pal research award, and a Sloan Research Fellowship. Ishani Karmarkar was supported in part by an NSF CAREER Award CCF-1844855, NSF Grant

CCF-1955039, a Pay Pal research grant, and a Stanford Institute for Computational and Mathematical Engineering (ICME) Fellowship. Rajat Vadiraj Dwaraknath was supported by a Stanford ICME Fellowship.

[1] Aleksander Madry, Damian Straszak, and Jakub Tarnawski. Fast generation of random spanning

trees and the effective resistance metric. In Symposium on Discrete Algorithms, 2014. [2] Karel Devriendt. Effective resistance is more than distance: Laplacians, simplices and the schur

complement. In Linear Algebra and its Applications, 2022. [3] Huan Li and Zhongzhi Zhang. Kirchhoff index as a 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 A. 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 ar Xiv preprint ar Xiv:2006.08796, 2020. [9] Tasweer Ahmad, Lianwen Jin, Luojun Lin, and Guo Zhi Tang. Skeleton-based action recognition

using sparse spatio-temporal gcn with edge effective resistance. In Neurocomputing, 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 on 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-Hua

Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Symposium on 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

Maximum 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 P Liu Yin Tat Lee, Thatchaphol Saranurak, Aaron Sidford, Zhao

Song, and Di Wang. Minimum cost flows, mdps, and 1-regression 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 ar Xiv preprint ar Xiv:1711.06530, 2017. [23] Zhiqiang Zhao and Zhuo Feng. Effective-resistance 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 Allerton Conference on Communication, Control, and Computing, 2022. [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 c, and Sreenivas Gollapudi.

Affinity-aware graph networks. In ar Xiv preprint ar Xiv:2206.11941, 2022.

[28] Arun Jambulapati and Aaron Sidford. Efficient r Opn{ q 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 Algorithms, 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 ar Xiv preprint ar Xiv:1704.04163, 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://arxiv.org/abs/2210.10173, 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 on Foundations of

Computer Science, 2018. [38] Jeff Cheeger. A lower bound for the smallest eigenvalue 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.

[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-Marco, 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. Algorithms 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, Mohammad Taghi Haji Aghayi, and Saeed

Seddighin. Subcubic equivalences between graph centrality measures and complementary problems. In ar Xiv preprint ar Xiv: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-Hua 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 interlace theorem for eigenvalues of hermitian matrices. In The

American mathematical monthly, 2004.