Graph Sparsification by Effective Resistances

• p. 15 Theorem 12

  There is an eO(m/ǫ2) time algorithm

• p. 3 Section 1.1, after Theorem 2

  this yields an eO(m(log r)/ǫ2) time for sparsifying graphs

• p. 13 end of proof of Theorem 2

  eO(m log(1/δ)/ǫ2) = eO(m log r/ǫ2) time

• p. 3 Section 1.1, paragraph after Theorem 2

  this yields an eO(m(log r)/ǫ2) time for

Only the authors can say what is right here.

Judge's note: Images p.3, p.13 and p.15 checked. The paper never defines Õ as hiding log r, and it writes log r explicitly inside Õ elsewhere. r = wmax/wmin is not bounded by a function of n, and Theorem 12 takes weighted input G=(V,E,w). The abstract's O(log n) query time and the intro's Õ(m) are consistent with the paper's informal constant-ε statements (Section 4 opening), so they are not counted as separate defects.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 3 Section 1.1, following the normalized-Laplacian variational formula

  we obtain the same relationship between the eigenvalues of the walk matrix of the original graph and its sparsifier.

• p. 2 Normalized-Laplacian discussion

  we obtain the same relationship between the eigenvalues of the walk matrix of the original graph and its sparsifier.

Only the authors can say what is right here.

Judge's note: Read main-p003.png and tex line 179 onwards. Reworked the reviewer's counterexample: a weighted 4-cycle with alternating weights a, b has Laplacian eigenvalues 0, 2b, 2a, 2(a+b). G (a=2, b=1) is 3-regular with normalized spectrum 0, 2/3, 4/3, 2. H (a=16/5, b=2/5) is 18/5-regular with normalized spectrum 0, 2/9, 16/9, 2. Edge-weight ratios are 1.6 and 0.4, so (2) holds with ε=3/5. But (1−ε)·2/3 = 4/15 > 2/9, so the claimed lower bound fails. The correct factors are (1−ε)/(1+ε) and (1+ε)/(1−ε). This is an introductory remark; Theorem 1 is unaffected.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 9 Corollary 6, displayed inequality

  (1 −ǫα)xT ˜Lx ≤xT Lx ≤(1 + ǫα)xT ˜Lx

• p. 7 Lemma 4 conclusion

  (1 −ǫ)xT Lx ≤xT ˜Lx ≤(1 + ǫ)xT Lx

• p. 3 Section 1.1

  (2) of Theorem 1 is not harmed too much

• p. 2 Theorem 1, equation (2)

  (1 −ǫ)xT Lx ≤xT ˜Lx ≤(1 + ǫ)xT Lx

Only the authors can say what is right here.

Judge's note: Page 9 image: the corollary bounds xᵀLx by multiples of xᵀL̃x. Following the proof gives ‖ΠSΠ−Π‖ ≤ εα, and Lemma 4 then gives (1−εα)xᵀLx ≤ xᵀL̃x ≤ (1+εα)xᵀLx. That does not imply the printed upper bound. Counterexample allowed by the proven bound: εα=0.5, xᵀLx=1, xᵀL̃x=0.5; then (1+εα)xᵀL̃x = 0.75 < 1. The intro (p.3) says Corollary 6 preserves guarantee (2), and Theorem 12 cites (2). The intended form is evidently (2) with ε replaced by εα.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 3 Theorem 2

  (1 −ǫ)Ruv ≤∥eZ(χu −χv)∥2 ≤(1 + ǫ)Ruv

• p. 11 Lemma 9 conclusion

  (1 −ǫ)2Ruv ≤∥eZ(χu −χv)∥2 ≤(1 + ǫ)2Ruv

Only the authors can say what is right here.

Judge's note: Reworked the proof. Lemma 7 with k = 24 log n/ε² gives the factor (1±ε) for Z. Lemma 9 (p.11–12) shows |‖Zx‖² − ‖Z̃x‖²| ≤ (ε/3)(2+ε/3)‖Zx‖², which adds a second multiplicative factor, giving (1±ε)² overall. The end of the proof (p.13) never rescales ε. Since (1+ε)² > 1+ε and (1−ε)² < 1−ε for 0<ε<1, the theorem with its explicit row count and (1±ε) factors is not established as stated. It holds after replacing ε by a constant fraction of ε, which changes the stated constant 24.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 8 Lemma 5, displayed expectation bound

  ≤ min

• p. 3 Lemma 5

  \min\left(CM\sqrt{\frac{\log q}{q}},1\right)

Only the authors can say what is right here.

Judge's note: Read main-p008.png; the tex has \min\left(CM\sqrt{\frac{\log q}{q}},1\right). Reworked the counterexample: d=1, y=2 with probability 1/4 and 0 otherwise, so M=2 and E[y²]=1, and both hypotheses hold. With q=2 and K the number of nonzero samples, the empirical value is 2K and the error is |2K−1|, which is 1, 1, 3 with probabilities 9/16, 6/16, 1/16. The expectation is 9/8 > 1, exceeding the printed right-hand side for every C. The lemma is wrong as printed; presumably the bound is meant to hold only when the first quantity is below 1. The use in Theorem 1 is in the small-error regime and is not affected by this example.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 9 Corollary 6, conclusion

  (1 − ǫα)xᵀL̃x ≤ xᵀLx ≤ (1 + ǫα)xᵀL̃x

• p. 4 Corollary 6, displayed conclusion

  (1-\epsilon\alpha)x^T\tilde{L}x\le x^TLx\le (1+\epsilon\alpha)x^T\tilde{L}x

Only the authors can say what is right here.

Judge's note: Read main-p009.png and tex lines 165, 404 and 488. Theorem 1 and Lemma 4 bound x^T L̃x by multiples of x^T Lx; Corollary 6 reverses the roles. Reworked the counterexample: unit-weight tree, all R_e=1, α=2q, Z=1/α on one edge and α on the rest. Then Z_e ≥ R_e/α and ΣwZ = α(n−2)+1/α ≤ α(n−1), so the hypotheses hold. That edge has p' = 1/(α²(n−2)+1), so it is never sampled with probability ≥ 1 − q/(4q²(n−2)+1) > 3/4. When it is absent, the indicator of one side of the bridge gives x^T Lx=1 and x^T L̃x=0, violating the printed upper inequality. So the success probability is below 1/2. The orientation used in Theorem 1 would not be broken by this example, since its lower factor is non-positive there. Theorem 1 itself is unaffected.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 13 Lemma 11, sample-count hypothesis

  q > 4n log n/β

• p. 14 Proof of Lemma 11, displayed Bennett inequality

  P[|Dᵥ − EDᵥ| > EDᵥ]

• p. 6 Claimed Bennett inequality

  \P[|D_v-\E D_v|>\E D_v]\le \exp\left(\frac{-(\E D_v)^2}{\var(D_v)(1+\frac{\E D_v}{q})}\right)

Only the authors can say what is right here.

Judge's note: Read main-p013.png, main-p014.png and tex lines 732–777. (a) Path on 3 vertices, p=0.1 and 0.9, β=0.3 (required p ≥ 0.3/(3·1) = 0.1), q=100 > 4·3·ln3/0.3 ≈ 43.9. For the leaf on the first edge, D_v = K/10 with K~Bin(100, 0.1), so E=1 and Var=0.09. The printed bound is exp(−1/(0.09·1.01)) ≈ 1.67e-5. By my own log-factorial estimate, P(K=21) alone is about 4.9e-4, so the displayed inequality is false. (b) Star with n=10000, β=1/2, q=736828 (threshold 80000·ln 10000 ≈ 736827.2), p=1/20000 on 9998 edges and 0.5001 on one; the probabilities sum to 1 and meet the lower bound. For a rare edge qp = 36.84, and a count of 74 gives D_v ≈ 2.0086 > 2·deg(v) = 2. My Poisson estimate of P(count=74) is about 2.5e-8 per leaf, and times 9998 leaves that is about 2.4e-4 > 1/n = 1e-4. I did not compute the reviewer's exact multinomial values, but the rough estimate agrees with them. So Lemma 11 fails as stated with constant 4; a larger constant preserves the O(n log n) order.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 9 Proof of Corollary 6, first display

  weSe

• p. 9 Corollary 6 statement

  p′ e = weZe P e weZe

• p. 9 Corollary 6 statement

  Suppose Ze are numbers satisfying Ze ≥Re/α

Judge's note: Viewed the page 9 image: the corollary statement uses Z_e and the first display of the proof uses S_e, clearly a different letter and not a glyph artefact. S_e is not defined anywhere (the text search finds it only here), and S is the diagonal sampling matrix of equation (3). The inequality that follows uses exactly the hypotheses stated for Z_e, so Z_e is meant.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 16 Reference [21]

  J. of Functional Analysis, 163(1):60– 72, 1999

• p. 16 Reference [21]

  163(1):60–

Only the authors can say what is right here.

Judge's note: Rests on outside knowledge: that Rudelson's 'Random vectors in the isotropic position' appeared in J. Funct. Anal. volume 164(1), pp. 60–72, 1999. Cluster C025 reports that Crossref (doi:10.1006/jfan.1998.3384) records volume 164. The page 16 image confirms the entry prints '163(1):60–72, 1999'. The true volume cannot be verified from the PDF, so this goes to the authors as a query.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 3 first display (Courant-Fischer for L)

  λi = max S:dim(S)=k min x∈S

• p. 3 second display (normalized Laplacian)

  xT D−1/2LD−1/2x

• p. 3 Section 1.1, first display (Courant-Fischer)

  S:dim(S)=k

• p. 3 Section 1.1, Courant-Fischer display (and the normalized-Laplacian display below it)

  S:dim(S)=k min

Judge's note: Checked on page image p.3: both displays have λi on the left and dim(S)=k under the max. k is not defined before this point (it is later the JL dimension). The index should match i (or n−i+1, depending on how the eigenvalues are ordered). The deduction (1−ε)λi ≤ λ̃i ≤ (1+ε)λi is unaffected.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 10 Section 4, construction step 1

  matrix of dimension k × n where k = 24 log n/ǫ2

• p. 10 Section 4, step 2

  Compute Y = QW 1/2B

• p. 4 Section 2.1

  Wm×m is the diagonal matrix

• p. 4 enumerate, item 1

  Let $Q$ be a random $\pm 1/\sqrt{k}$ matrix of dimension $k\times n$

Judge's note: Page 10 image confirms 'k × n'. W is m×m (Section 2.1) and the projected vectors W^{1/2}BL⁺χv lie in R^m (Lemma 7 with d=m), so Q must be k×m. The k×n shape is correct for Y and Z̃. The reviewer remark that the intro's 'O(log n) linear systems' drops ε is an informal statement for constant ε and is not counted here.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 10 Theorem 8 (Spielman-Teng), displayed inequality

  ∥x − L+y∥L ≤ ǫ∥L+y∥L

• p. 10 Theorem 8 statement

  and an error parameter δ > 0

• p. 11 Lemma 9, eq. (4)

  ∥zi − ˜zi∥L ≤ δ∥zi∥L

• p. 10 Theorem 8

  an error parameter δ > 0

Judge's note: Page 10 image shows ε in the Theorem 8 display. In this section ε is the JL accuracy, and δ (eq. 5) is much smaller than ε. Read literally, Theorem 8 would not give (4), and δ would affect only the running time. Evident fix: replace ε with δ.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 14 Proof of Lemma 11, Var(Xi) display, first line

  Var(Xi) = X e∋v pe 1 p2e −1 pe

• p. 14 Proof of Lemma 11, first line of the Var(X_i) chain

  Var(Xi) =

• p. 5 Proof of Lemma mindeg

  \var (X_i) &= \sum_{e\ni v}p_e\left(\frac{1}{p_e^2}-\frac{1}{p_e}\right)

Only the authors can say what is right here.

Judge's note: Page 14 image. Xi = 1/pe with probability pe for each e∋v and 0 otherwise. Since these outcomes are mutually exclusive, E[Xi²] = Σ1/pe and (EXi)² = deg(v)². Counterexample: two incident edges with pe = 1/4 give true variance 8−4 = 4, while the printed expression gives 2·(1/4)·(16−4) = 6. The next line only uses Var ≤ Σ1/pe, which still holds, so the lemma stands.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 14 Section 5, final sampling formula

  Sampling with probabilities

• p. 6 Sampling formula preceding Theorem 12

  p'_e=p'_{(u,v)}=\frac{1}{2}\left(\frac{\|Zb_e^T\|^2w_e}{\sum_e \|Zb_e^T\|^2w_e} + \frac{1}{n\min(\deg(u),\deg(v))}\right)

• p. 14 Section 5, display after the proof of Lemma 11

  n min(deg(u), deg(v))

Only the authors can say what is right here.

Judge's note: Page 14 image. The first term sums to 1 over edges, but the second does not. On K_n each of the n(n−1)/2 edges has min degree n−1, so the second terms sum to 1/2 and the total is 3/4 (the triangle gives 3/4 too). The text says 'Sampling with probabilities p′e = ...' and assigns α=2, β=1/2 to these exact values; no normalisation is stated. Normalising fixes it at the cost of bounded changes to the constants.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send