<p>Regarding your 1st question: no, this would not hold in general.</p>

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

<p>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 <span class="math-container">$O(\log(1/\epsilon))$</span> iteration this outputs a spectral sparsifier with probability at least <span class="math-container">$1-\epsilon$</span>. 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.</p>

CC BY-SA 4.0
2020-02-15T05:15:32.800Z
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.
GMB
CC BY-SA 4.0
2020-02-15T07:48:24.157Z
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.
smapers
CC BY-SA 4.0
2020-02-14T09:05:26.923Z
2020-02-14T09:05:26.923Z
smapers
<p>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:</p>

<ul>
<li>The <a href="https://arxiv.org/abs/0808.4134" rel="nofollow noreferrer">original paper</a> by Spielman and Teng works roughly by partitioning the graph into parts of good expansion and <span class="math-container">$\le |E|/2$</span> edges going between the parts, then building a sparsifier of each part, and then recursing on the "remainder" graph to depth <span class="math-container">$\log n$</span> to get the rest.  Implicitly, one then combines these partial solutions at the end for a full solution.</li>
<li><a href="https://arxiv.org/pdf/1711.00571.pdf" rel="nofollow noreferrer">This paper</a> by Jambulapati and Sidford builds spectral sketches, which are data structures (not subgraphs) that can approximate Laplacian quadratic forms <span class="math-container">$x^T L x$</span> with probability <span class="math-container">$\ge 2/3$</span> for any given <span class="math-container">$x$</span>.  As they mention, one can easily amplify this probability to <span class="math-container">$p$</span> by computing <span class="math-container">$\log (1/p)$</span> 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 <em>subgraphs</em> with this property.</li>
</ul>

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

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

<graph-theory><spectral-graph-theory>
When can partial spectral sparsifiers be combined?
GMB
# When can partial spectral sparsifiers be combined?

(Asked by: username_0 on 2020-02-13)

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](https://arxiv.org/abs/0808.4134) 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](https://arxiv.org/pdf/1711.00571.pdf) 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?

**Tags:** graph-theory, spectral-graph-theory

---

## 1 answers

### Answer by username_1 on 2020-02-14. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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.  

---

