A few important papers about spectral sparsifiers and friends contain a technical idea that involves building many different sparsifiers that each "partially" solve the problem, and then combining them at the end. To give two examples:

  • The original paper by Spielman and Teng works roughly by partitioning the graph into parts of good expansion and $\le |E|/2$ edges going between the parts, then building a sparsifier of each part, and then recursing on the "remainder" graph to depth $\log n$ to get the rest. Implicitly, one then combines these partial solutions at the end for a full solution.
  • This paper by Jambulapati and Sidford builds spectral sketches, which are data structures (not subgraphs) that can approximate Laplacian quadratic forms $x^T L x$ with probability $\ge 2/3$ for any given $x$. As they mention, one can easily amplify this probability to $p$ by computing $\log (1/p)$ sketches and taking their median. This critically uses that they sketch with data structures, not graphs, and it raises the question of whether a similar probability amplification is possible for subgraphs with this property.

Formalizing the question, let $G = (V, E, w)$ be a graph and let $H_1, H_2$ be reweighted subgraphs such that, for some $X_1, X_2 \subseteq \mathbb{R}^n$ we have $$x^T L_{H_i} x \in (1 \pm \varepsilon) x^T L_G x \qquad \text{for all } x \in X_i.$$

  • I imagine that this does not imply generally that one can reweight $H_1 \cup H_2$ so that the above equation holds for all $x \in X_1 \cup X_2$. Is this accurate, and is there a nice example that demonstrates this?
  • Are there natural additional assumptions we can make about $G, H_1, H_2$ so that this combination of $H_1, H_2$ does work in general, e.g. to enable recursive computation techniques like in the first paper?

1 Answer 1


Regarding your 1st question: no, this would not hold in general.

Rather (answering your 2nd question), the right way to interpret the approach by Spielman and Teng is as follows: let $G'$ be a vertex-induced subgraph of $G$, and $H'$ a spectral sparsifier of $G'$. Then the graph $G-G'+H'$ (replace all edges in $G'$ by those in $H'$) will be a spectral sparsifier of $G$. This easily follows by combining the Laplacians of $G$ and $H'$. As a result, we can sparsify $G$ by subsequently sparsifying subgraphs.

And finally, you are asking about ways to amplify the success probability of a sparsification algorithm. For spectral sparsification, there is a rather easy way: construct one with constant success probability, check whether it is indeed a spectral sparsifier (this amounts to checking whether a certain matrix is PSD, which can be done efficiently), if not, reiterate. After $O(\log(1/\epsilon))$ iteration this outputs a spectral sparsifier with probability at least $1-\epsilon$. Note that this cannot be done for say cut sparsification, as there is no efficient "verification procedure" to check whether a graph is a cut sparsifier of another graph.

  • $\begingroup$ Thanks for the response and for the clarification on the Spielman and Teng paper, very helpful. For the last point: the model is that the subgraph has $x^T L_H x \approx x^T L_G x$ with constant probability for any given $x$. What you are describing would work if there was constant probability that it holds for all $x$ simultaneously, which is stronger. $\endgroup$
    – GMB
    Feb 15, 2020 at 5:15
  • $\begingroup$ Oh, I see now that the question was about sketches, not sparsifiers. I guess you can easily restrict the input graph to a subgraph, so that's probably not your question. $\endgroup$
    – smapers
    Feb 15, 2020 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.