When can partial spectral sparsifiers be combined?

Question

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?

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.