# Spectrahedral Geometry of Graph Sparsifiers

Catherine Babecki  Department of Mathematics, University of Washington,
Seattle, WA 98195, USA<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>,
Stefan Steinerberger  and  Rekha R. Thomas

###### Abstract.

We propose an approach to graph sparsification based on the idea of preserving
the smallest $k$ eigenvalues and eigenvectors of the Graph Laplacian. This is
motivated by the fact that small eigenvalues and their associated eigenvectors
tend to be more informative of the global structure and geometry of the graph
than larger eigenvalues and their eigenvectors. The set of all weighted
subgraphs of a graph $G$ that have the same first $k$ eigenvalues (and
eigenvectors) as $G$ is the intersection of a polyhedron with a cone of
positive semidefinite matrices. We discuss the geometry of these sets and
deduce the natural scale of $k$. Various families of graphs illustrate our
construction.

###### Contents

  1. 1 Introduction and Definition
  2. 2 Two Concrete Examples
  3. 3 The Geometry of $k-$Sparsifiers
  4. 4 Bounds on the Maximal Sparsification
  5. 5 Families of Band-limited Spectral Sparsifiers
  6. 6 Preserving the Quadratic Form
  7. 7 Proofs
  8. 8 Conclusion

##  1\. Introduction and Definition

###  1.1. Motivation

The purpose of this paper is to introduce a new type of graph sparsification
motivated by spectral graph theory. Let $G=([n],E,w)$ be a connected,
undirected, positively weighted graph with vertex set $[n]$, edge set $E$ and
weights $w_{ij}>0$ for all $(i,j)\in E$. The Laplacian of $G$ is the weakly
diagonally dominant positive semidefinite matrix $L_{G}$ defined as

(4) $\displaystyle(L_{G})_{ij}=\left\\{\begin{array}[]{ll}-w_{ij}&\textup{ if
}i\neq j\textup{ and }(i,j)\in E\\\ 0&\textup{ if }i\neq j\textup{ and
}(i,j)\not\in E\\\ \sum_{\\{l\,:\,(i,l)\in E\\}}w_{il}&\textup{ if
}i=j\end{array}\right.$

with eigenvalues $\lambda_{1}\leq\lambda_{2}\leq\ldots\leq\lambda_{n}$. The
all-ones vector $\mathbbm{1}$ shows that the smallest eigenvalue of $L_{G}$ is
$\lambda_{1}=0$ with eigenvector $\varphi_{1}=\mathbbm{1}$. The lower end of
the spectrum of $L_{G}$ is sometimes referred to as the low frequency
eigenvalues of $G$.

Spectral graph theory is broadly concerned with how the structure of $G$ is
related to the spectrum of $L_{G}$. For example, $G$ has $k$ connected
components if and only if $\lambda_{1}=\dots=\lambda_{k}=0<\lambda_{k+1}$. In
this paper we will only consider connected graphs; in this case,
$\lambda_{2}>0$ plays an important role. This second eigenvalue is also known
as the ‘algebraic connectivity’ of $G$ and serves as a quantitative measure of
how connected $G$ is. A fundamental result in spectral graph theory is
Cheeger’s inequality [9], which connects $\lambda_{2}$ to the density of the
sparsest cut in $G$. Eigenvectors associated to small eigenvalues also carry
important information. For example, these eigenvectors can be used to produce
an approximate Euclidean embedding of a graph (see §8 for the connection to
dimensionality reduction). The common theme that underlies all these results
can be summarized in what we will refer to as the Spectral Graph Theory
Heuristic.

> Spectral Graph Theory Heuristic. The low-frequency eigenvalues (and
> eigenvectors) of $L_{G}$ capture the global structure of $G$.

Another way of interpreting this heuristic is by saying that eigenvectors
corresponding to small eigenvalues tend to change very little across edges –
they are ‘smooth’ over the graph and capture global structure. In contrast,
eigenvectors corresponding to very large eigenvalues tend to oscillate rapidly
and capture much more local phenomena (see, for example, [26]). All of these
results point to the low frequency portion of the Laplacian spectrum as the
‘fingerprint’ of $G$ that captures the global structure of $G$ (while the high
frequency portion adds finer detail).

Sparsifying a graph $G$ is the process of modifying the weights on edges (or
removing them altogether) while preserving ‘essential’ properties of $G$. This
raises the question of which properties are essential, and how to sparsify in
a way that preserves these properties. Motivated by the Spectral Graph Theory
Heuristic, we introduce a Spectral Sparsification Heuristic (see §8 for
additional motivation).

> Spectral Sparsification Heuristic. A sparsification of $G$ should preserve
> the first $k$ eigenvalues and eigenvectors of $L_{G}$.

The motivation is clear from what has been said above about the interplay
between the eigenvalues of $L_{G}$ and the properties of $G$. As one would
expect, the parameter $k\in\mathbb{N}$ in the heuristic will determine a
natural scale. Small values of $k$ only ask for the preservation of relatively
few eigenvectors and eigenvalues which allows for a larger degree of
sparsification. If one requires that many eigenvectors and eigenvalues remain
preserved, then this will restrict how much sparsification one could hope for.
There is a natural linear algebra heuristic (see §4) suggesting a value of
$k_{0}$ such that when $k>k_{0}$, the only $k-$sparsifier of $G$ is $G$
itself. We now make these notions precise.

###  1.2. Bandlimited Spectral Sparsification

Let $G$ be a connected graph and let the eigenvalues of $L_{G}=D-A$ be
$0=\lambda_{1}<\lambda_{2}\leq\cdots\leq\lambda_{n}$. All graphs in this paper
are connected and hence the eigenspace of $\lambda_{1}=0$ is spanned by
$\mathbbm{1}$, the all-ones vector. Fix an orthonormal eigenbasis
$\\{\varphi_{1}=\mathbbm{1}/\sqrt{n}$, $\varphi_{2},\dots,\varphi_{n}\\}$ of
$L_{G}$ so that $L_{G}\varphi_{i}=\lambda_{i}\varphi_{i}$ for all
$i=1,\ldots,n$. Then the spectral decomposition of $L_{G}$ is

(5) $\displaystyle
L_{G}=\Phi\Lambda\Phi^{\top}=\sum_{i=2}^{n}\lambda_{i}\varphi_{i}\varphi_{i}^{\top}.$

where

(6)
$\displaystyle\Lambda:=\operatorname{diag}(0,\lambda_{2},\ldots,\lambda_{n})\quad\textup{
and
}\quad\Phi:=\begin{bmatrix}\varphi_{1}&\varphi_{2}&\cdots&\varphi_{n}\end{bmatrix}\in\mathbb{R}^{n\times
n}.$

We denote the eigenpairs of a graph $G$ as $(\lambda_{i},\varphi_{i})$. Fixing
the above notation, we can now give a formal definition of sparsification.

######  Definition 1.1.

  1. (1)

A subgraph $\tilde{G}=([n],\tilde{E},\tilde{w})$ of $G$ where
$\tilde{E}\subseteq E$ and $\tilde{w}>0$ is $k-$isospectral to $G$ if
$\tilde{G}$ and $G$ have the same first $k$ eigenvalues and eigenvectors,
i.e., the first $k$ eigenpairs of $\tilde{G}$ are
$(0,\varphi_{1}),\ldots,(\lambda_{k},\varphi_{k})$.

  2. (2)

A $k-$isospectral subgraph $\tilde{G}=([n],\tilde{E},\tilde{w})$ of $G$ is a
$k-$sparsifier if $\tilde{E}\subsetneq E$, i.e., at least one edge of $G$ does
not appear in $\tilde{G}$.

While the eigenvalues are unique, there is a choice of eigenbasis
$\\{\varphi_{1},\ldots,\varphi_{n}\\}$. The above definition is made with
respect to a fixed eigenbasis of $L_{G}$. We will see that there is no
ambiguity if we choose to preserve all eigenpairs in a given eigenspace, in
particular, if the eigenvalues of $L_{G}$ do not have multiplicity. We
illustrate Definition 1.1 on a simple example in Figure 1.

Figure 1. The lollipop graph on $n=12$ vertices and $m=26$ edges can be
sparsified to a spanning tree while keeping the first $k=3$ eigenpairs
unchanged.

We note that graphs which are $1-$isospectral to $G$ are not interesting –
these include every subgraph of $G$, even the empty graph and need not
preserve any of the desirable structure of $G$. For this reason, we restrict
our attention to $k-$isospectral subgraphs and $k-$sparsifiers for $k\geq 2$.

######  Lemma 1.2.

For $k\geq 2$, a $k-$isospectral subgraph
$\tilde{G}=([n],\tilde{E},\tilde{w})$ of a connected graph $G=([n],E,w)$ is
connected (and hence spanning).

This follows at once from the fact that $\lambda_{2}>0$ if and only if the
graph is connected. For $k\geq 2$, any $k-$isospectral subgraph $\tilde{G}$
preserves $\lambda_{2}(\tilde{G})=\lambda_{2}(G)>0$.

Recall that the quadratic form associated to $L_{G}$ is
$Q_{G}(x):=x^{\top}L_{G}x$. An immediate consequence of Definition 1.1 is that
if $\tilde{G}$ is a $k-$isospectral subgraph of $G$, then its quadratic form
$Q_{\tilde{G}}(x)$ agrees with $Q_{G}(x)$ on the span of the $k$ eigenvectors
of $G$ that we are fixing.

######  Lemma 1.3.

If $\tilde{G}$ is a $k-$isospectral subgraph of $G$ then

$Q_{G}(x)=Q_{\tilde{G}}(x)\qquad\mbox{for
all}~{}x\in\textup{span}\\{\varphi_{1},\ldots,\varphi_{k}\\}.$

The _ Proof of Lemma 1.3._ (and all other proofs) are in § 7. We note that the
converse of Lemma 1.3 is false, namely that if $G^{\prime}$ is a subgraph of
$G$ with the property that $Q_{G^{\prime}}(x)=Q_{G}(x)$ for all
$x\in\textup{span}\\{\varphi_{1},\ldots,\varphi_{k}\\}$ then it does not mean
that the smallest $k$ eigenpairs of $G^{\prime}$ and $G$ agree (see Example
6.6). Therefore, the notion of $k-$isospectrality is stronger than asking for
the quadratic forms to agree on the span of the low frequency eigenvectors of
$G$.

###  1.3. Summary of Results and Organization of Paper

We start by illustrating the concepts of $k-$isospectral graphs and
$k-$sparsifiers in Section 2 on two small and completely explicit examples,
which amounts to some concrete computations.

Section 3 contains our main result, the Structure Theorem 3.1. It describes
the overall structure of $k-$isospectral graphs as a set of positive
semidefinite (psd) matrices satisfying linear constraints coming from the
requirements that we (a) should not create new edges and (b) want edge weights
to be non-negative. The search for $k-$sparsifiers with few edges corresponds
to finding points in this set satisfying many inequality constraints at
equality.

The heart of Section 4 is a Linear Algebra Heuristic saying that, generically,
if

$|E|\leq\binom{n}{2}-\binom{n-k+1}{2}$

then the only $k-$sparsifier of $G$ is $G$ itself. This is not always true but
is generically true (for example for random graphs) for reasons that will be
explained. This suggests that dense graphs with many edges will usually lead
to $k-$sparsifiers for reasonable large $k$ while graphs with few edges are
not so easily sparsified (which naturally corresponds to our intuition).
Section 4 discusses a number of results in this spirit. The Structure Theorem
explains the effectiveness of the Linear Algebra Heuristic: generically,
linear systems of equations are solvable when the number of variables is at
least as large as the number of equations. Having analyzed the hypercube graph
$Q_{d}$ on $\\{0,1\\}^{d}$ in Section 4, we illustrate our model of graph
sparsification on several more graph families in Section 5. Section 6
discusses an alternative notion of sparsification centered only around
preserving the quadratic form $Q(x)=x^{\top}L_{G}x$ on low-frequency
eigenvalues and eigenvectors. We contrast this model to our main model.
Section 7 contains all the proofs. We conclude with a number of remarks in
Section 8.

Figure 2. A graph $G$ on $n=10$ vertices and $m=21$ edges. There exists a
sparsification which removes the three dotted edges while preserving the first
$k=5$ eigenvalues and eigenvectors of $G$.

###  1.4. Related Work

The problem of graph sparsification is classical. The approach that is perhaps
philosophically the closest to ours is that of spectral sparsification
(Spielman & Teng [22]). The main idea there is, given a graph $G$ and a
tolerance $\varepsilon$, to find a graph $G^{\prime}$ whose (weighted) edges
are a subset of the edges of $G$ while, simultaneously, satisfying

$\forall~{}x\in\mathbb{R}^{n}\qquad(1-\varepsilon)\cdot Q_{G^{\prime}}(x)\leq
Q_{G}(x)\leq(1+\varepsilon)\cdot Q_{G^{\prime}}(x).$

The goal is thus to find a subset of the edges of $G$ such that (after
changing their weights) the new graph $G^{\prime}$ has a Laplacian whose
quadratic form behaves very similarly to that of $L_{G}$. We have

$Q_{G}(x)=\sum_{(i,j)\in E}w_{ij}(x(i)-x(j))^{2}.$

Thus, one way of interpreting spectral sparsification is that one finds a
sparser graph that assigns to each function $x:V\rightarrow\mathbb{R}$ a
nearly identical level of smoothness. This notion has been very influential,
see e.g. [4, 5, 7, 13, 23].

Our approach is similar in spirit in the sense that it relies on spectral
geometry as a measure of graph similarity, but it also differs in essential
ways.

  1. (1)

We do not even approximately preserve large eigenvalues of $L_{G}$. This is
bolstered by the Spectral Graph Theory Heuristic that the low-frequency
eigenpairs of $L_{G}$ are the heart of the graph.

  2. (2)

However, we preserve the first $k$ eigenvalues and their associated
eigenvectors exactly, again motivated by the Spectral Graph Theory Heuristic,
producing subgraphs that exactly preserve many of the essential structural
properties of $G$. See § 8 for more on this.

  3. (3)

A major result of spectral sparsification is that there necessarily exists
sparsifiers of $G$ with a small number of edges, whereas in our notion, some
graphs simply cannot be sparsified. A simple example is the Hamming cube graph
$Q_{d}$ on $\left\\{0,1\right\\}^{d}$ which cannot be sparsified (see Theorem
4.5) once we require that the first nontrivial eigenspace is preserved. This
is well aligned with the idea that certain graphs, especially those with
extraordinary degrees of symmetry, are already as sparse as possible.

Perhaps the common denominator of the two approaches is for the quadratic form
to be preserved (exactly or approximately) on the low-frequency eigenvectors.
By Lemma 1.3, our notion of isospectrality subsumes this requirement even
under exact preservation. We refer to § 8 for further comments.

##  2\. Two Concrete Examples

In this section, we explicitly construct the set of $k-$isospectral subgraphs
of two small graphs, and use these examples to highlight various aspects of
the underlying geometry. The needed computations were done ‘by hand’ and their
details will become clear after the main structure theorem is introduced in
Section 3. We will record only the upper triangular part of a symmetric matrix
and will denote the identical lower triangular entries with a –.

###  2.1. The Butterfly Graph.

Let $G$ be the Butterfly Graph in Figure 3.

$1$$2$$3$$4$$5$ Figure 3. The Butterfly Graph with weight $1$ on all edges.

The eigenvalues of $L_{G}$ are $0,1,3,3,5$, and suppose we ask to preserve the
first $k=2$ eigenvectors and eigenvalues. Since the first two eigenvalues, $0$
and $1$, both have multiplicity 1, there is a unique choice of eigenvectors
(up to sign):

$\displaystyle\varphi_{1}=\frac{1}{\sqrt{5}}(1,1,1,1,1)\qquad\mbox{and}\qquad\varphi_{2}=\frac{1}{2}(0,-1,-1,1,1).$

Our goal is to find edge weights leading to (sub)graph Laplacians whose first
eigenpair is $(0,\varphi_{1})$ (this is easily achieved: any connected
subgraph of $G$ will do) and whose second eigenpair is $(1,\varphi_{2})$ (this
is not quite so automatic).

The (weighted) $2-$isospectral subgraphs of $G$ are indexed by the non-
negative orthant of the $ab$-plane as seen in Figure 4, with each point
$(a,b)\geq 0$ indexing the subgraph $\tilde{G}$ of $G$ with edge weights

$\tilde{w}_{12}=\tilde{w}_{13}=\tilde{w}_{14}=\tilde{w}_{15}=1,\,\,\tilde{w}_{23}=a,\,\,\tilde{w}_{45}=b.$

$1$$2$$3$$4$$5$$a$$b$$1$$1$$1$$1$ Figure 4. The $2-$isospectral subgraphs of
the Butterfly Graph are indexed by $(a,b)\geq 0$. The axes and origin of the
non-negative $ab$-orthant index the $2-$sparsifiers of $G$.

On the $a$-axis we get the $2-$sparsifiers of $G$ that are missing the edge
$(2,3)$, and on the $b$-axis we get the $2-$sparsifiers that are missing the
edge $(4,5)$. At $(0,0)$ we get the spanning tree $2-$sparsifier with edges
$(1,2),(1,3),(1,4),(1,5)$ and all edge weights equal to $1$. The set of
Laplacians of all $2-$isospectral subgraphs of $G$ is

$\textup{Sp}_{G}(2)=\left\\{L=\begin{bmatrix}4&-1&-1&-1&-1\\\ -&1+a&-a&0&0\\\
-&-&1+a&0&0\\\ -&-&-&1+b&-b\\\ -&-&-&-&1+b\end{bmatrix}\,:\,a,b\geq
0\right\\}.$

For example, if we choose $a=5/2,b=5$, then we get a Laplacian with
eigenvalues $0,1,5,6,11$ and the same first two eigenvectors
$\varphi_{1},\varphi_{2}$ as $G$.

###  2.2. The complete graph $K_{4}$

For our second example, we consider the complete graph $K_{4}$ whose
eigenvalues are $0,4,4,4$. We want to preserve the first $k=2$ eigenvectors
and eigenvalues. Since the second eigenspace has a high multiplicity, we must
specify which one-dimensional subspace of the three-dimensional eigenspace
associated to eigenvalue $\lambda=4$ we wish to preserve. We choose

$\displaystyle\varphi_{1}=\frac{1}{2}(1,1,1,1)\qquad\mbox{and}\qquad\varphi_{2}=\frac{1}{\sqrt{2}}(1,-1,0,0).$

A computation shows that there indeed exists a nonempty set of $2-$isospectral
graphs indexed by three parameters $a,b,c$ subject to seven inequalities. It
is a fairly large space and contains all sorts of different $2-$isospectral
graphs and $2-$sparsifiers, see Fig. 6 for some examples. Fixing $\varphi_{2}$
breaks the symmetry of $K_{4}$ since we are deciding that this eigenvector is
the most important one among all eigenvectors with eigenvalue $4$, and needs
to be preserved. The weights can be read off the associated graph Laplacian.
The set of Laplacians of $2-$isospectral subgraphs of $K_{4}$ subject to
fixing $\varphi_{1}$ and $\varphi_{2}$ is given explicitly by

$\operatorname{Sp}_{K_{4}}(2)=\left\\{\begin{array}[]{r}L=\begin{bmatrix}3+\frac{a}{4}&\frac{a}{4}-1&\frac{-a}{4}+\frac{c}{2\sqrt{2}}-1&\frac{-a}{4}+\frac{-c}{2\sqrt{2}}-1\\\
&&&\\\
-&3+\frac{a}{4}&\frac{-a}{4}+\frac{c}{2\sqrt{2}}-1&\frac{-a}{4}+\frac{-c}{2\sqrt{2}}-1\\\
&&&\\\
-&-&3+\frac{a}{4}+\frac{b}{2}-\frac{c}{\sqrt{2}}&\frac{a}{4}-\frac{b}{2}-1\\\
&&&\\\ -&-&-&3+\frac{a}{4}+\frac{b}{2}+\frac{c}{\sqrt{2}}\end{bmatrix}\,:\\\
\\\ a\leq 4,\,\,-a+\sqrt{2}c\leq 4,\,\,-a-\sqrt{2}c\leq 4,\,\,a-2b\leq 4\\\
\\\ a\geq 0,\,\,b\geq 0,\,\,ab\geq c^{2}\end{array}\right\\}.$

Each $2-$isospectral subgraph of $K_{4}$ that preserves eigenvectors
$\varphi_{1}$ and $\varphi_{2}$ is indexed by a point $(a,b,c)$ in the ‘boat-
like’ set shown in Figure 5. We note that this region is quite nontrivial and
comprised of a mixture of curved surfaces (which come from the spectral
requirement that a Laplacian is positive semidefinite) and flat hyperplanes
(which come from linear inequalities defining non-negative edge weights). The
set $\operatorname{Sp}_{K_{4}}(2)$ is unbounded in direction $(0,1,0)$ and
hence the apparent “back” side of the boat-like shape is not actually there
and the set extends infinitely far in the $b$ direction.

Figure 5. Each $(a,b,c)$ in the above set indexes a $2-$isospectral subgraph
of $K_{4}$. There are $2-$sparsifers missing $1,2$ and $3$ edges indexed by
the polyhedral faces of the set as explained in the text.

The geometric region describing admissible choices of weights has three flat
sides coming from the intersections of $\mathcal{S}^{2}_{+}$, the cone of
$2\times 2$ positive semidefinite matrices, with the hyperplanes $a=4,$ which
corresponds to the ‘lid’ of the boat and $-a+\sqrt{2}c=4,$ and
$-a-\sqrt{2}c=4$ which correspond to the two sides of the boat. The fourth
hyperplane $a-2b=4$ supports $\textup{Sp}_{K_{4}}(2)$ at $p=(4,0,0)$; the
black dot in the top and front of the bow of the boat. In the relative
interior of the flat side cut out by $a=4$ we get $2-$sparsifiers missing the
edge $(1,2)$. In the relative interior of each of the flat sides cut out by
$-a\pm\sqrt{2}c=4$ we get $2-$sparsifiers missing two edges: either $(1,3)$
and $(2,3)$, or $(1,4)$ and $(2,4)$. On the intersections of $a=4$ and
$-a\pm\sqrt{2}c=4$ we get $2-$sparsifiers that are spanning trees. The point
$p$ is at the intersection of $a=4$ and $a-2b=4$ and indexes a $2-$sparsifier
missing the edges $(1,2)$ and $(3,4)$.

$1$$2$$3$$4$ | $1$$2$$3$$4$ | $1$$2$$3$$4$
---|---|---
$\begin{bmatrix}4&0&-2&-2\\\ -&4&-2&-2\\\ -&-&4&0\\\ -&-&-&4\end{bmatrix}$ | $\begin{bmatrix}4&0&0&-4\\\ -&4&0&-4\\\ -&-&50&-50\\\ -&-&-&58\end{bmatrix}$ | $\begin{bmatrix}4&0&0&-4\\\ -&4&0&-4\\\ -&-&4&-4\\\ -&-&-&12\end{bmatrix}$
Figure 6. The first graph is the $2-$sparsifier of $K_{4}$ corresponding to
$p=(4,0,0)$. The next two graphs correspond to $(4,100,4\sqrt{2})$ and
$(4,8,4\sqrt{2})$ which lie on the edge created by the intersection of $a=4$
and $-a+2\sqrt{c}=4$. They are both spanning trees with different weights.
Dashed lines represent missing edges.

We conclude by pointing out various features of these two examples that will
be made rigorous in subsequent sections.

  1. (1)

The set $\textup{Sp}_{G}(k)$ is the set of Laplacians of the $k-$isospectral
subgraphs of $G$. These Laplacians are parameterized by

$\ell\leq{n-k+1\choose 2}$

variables corresponding to the degrees of freedom in a symmetric matrix of
size ${n-k}$, allowing us to identify $\operatorname{Sp}_{G}(k)$ with a subset
of ${\mathbb{R}}^{\ell}$.

  2. (2)

The set $\textup{Sp}_{G}(k)$ is the intersection of the cone of positive
semidefinite (psd) matrices, an affine space determined by the edges not in
$G$, and a polyhedron described by linear inequalities corresponding to the
weights of edges in $G$. In the first example, the psd constraints are
automatically satisfied by all points that satisfy the linear constraints. In
the second example, the psd constraints contribute, making
$\textup{Sp}_{G}(2)$ non-polyhedral.

  3. (3)

The $k-$sparsifiers of $G$ are indexed by the faces of the polyhedron that
survive in $\textup{Sp}_{G}(2)$. A $k-$sparsifier on a face of the polyhedron
cut out by $t$ linear inequalities is missing at least $t$ edges.

##  3\. The Geometry of $k-$Sparsifiers

We now describe the set $\operatorname{Sp}_{G}(k)$ of $k-$isospectral
subgraphs of $G$. The main structure statement is in § 3.1, followed by a
discussion of the implied geometry in § 3.2. This includes a precise statement
about where the sparsifiers are located in $\operatorname{Sp}_{G}(k)$. In §
3.3 we illustrate the computation of $\operatorname{Sp}_{G}(k)$ on a full
example.

###  3.1. Main Structure Theorem

As explained in Lemma 1.2 every $k-$isospectral subgraph $\tilde{G}$ of
$G=([n],E,w)$ is spanning and connected when $k\geq 2$. Since the Laplacians
uniquely identify the subgraphs, we begin with a complete description of
$\textup{Sp}_{G}(k)$, the set of Laplacians associated to all $k-$isospectral
subgraphs of $G$.

######  Theorem 3.1.

Let $G=([n],E,w)$ be a connected, weighted graph with eigenpairs
$(0,\varphi_{1}),(\lambda_{2},\varphi_{2}),\ldots,(\lambda_{n},\varphi_{n})$
where $0=\lambda_{1}<\lambda_{2}\leq\cdots\leq\lambda_{n}$ and
$\\{\varphi_{i}\\}_{i=1}^{n}$ are orthonormal. Fix $2\leq k\leq n$ and define
the matrices

$\Phi_{k}=\begin{bmatrix}\varphi_{1}&\cdots&\varphi_{k}\end{bmatrix}\in{\mathbb{R}}^{n\times
k},\,\,\,\Phi_{>k}=\begin{bmatrix}\varphi_{k+1}&\cdots&\varphi_{n}\end{bmatrix}\in{\mathbb{R}}^{n\times(n-k)},$
$\Lambda_{k}=\operatorname{diag}(0,\lambda_{2},\ldots,\lambda_{k})\in{\mathbb{R}}^{k\times
k}.$

Then the set of Laplacians of all $k-$isospectral subgraphs of $G$ is

$\displaystyle\textup{Sp}_{G}(k)=\left\\{L=\underbrace{\Phi_{k}\Lambda_{k}\Phi_{k}^{\top}+\lambda_{k}\Phi_{>k}\Phi_{>k}^{\top}}_{F}+\Phi_{>k}Y\Phi_{>k}^{\top}\,:\,\begin{array}[]{cc}Y\in\mathcal{S}_{+}^{n-k}\\\
L_{st}\leq 0\,\,\forall\,\,(s,t)\in E\\\ L_{st}=0\,\,\forall\,\,s\neq
t,\,(s,t)\not\in E\end{array}\right\\}.$

_Proof of Theorem 3.1_

For $G$ and $k$ fixed, the matrix
$F:=\Phi_{k}\Lambda_{k}\Phi_{k}^{\top}+\lambda_{k}\Phi_{>k}\Phi_{>k}^{\top}$
is fully determined and easily computable. The set $\operatorname{Sp}_{G}(k)$
lies in the psd cone $\mathcal{S}^{n}_{+}$ and each $k-$isospectral subgraph
of $G$ has a Laplacian of the form $L=F+\Phi_{>k}Y\Phi_{>k}^{\top}$ where $Y$
is a psd matrix in $\mathcal{S}^{n-k}_{+}$. The entries of $Y$ satisfy linear
inequalities indexed by the edges present in $G$ and linear equations indexed
by the edges missing in $G$. The smaller the value of $k$, the larger the
potential dimension of $\operatorname{Sp}_{G}(k)$.

###  3.2. The Geometric Structure of $\operatorname{Sp}_{G}(k)$

Each $Y$ satisfying the conditions in the description of
$\operatorname{Sp}_{G}(k)$ determines a matrix $L$ which in turn determines a
unique $k-$isospectral subgraph $\tilde{G}$ of $G$ with $L_{\tilde{G}}=L$.
Identifying $Y$ with its $n-k+1\choose 2$ entries $y_{ij}$ in the upper
triangle (including the diagonal), we may take $\operatorname{Sp}_{G}(k)$ to
be a subset of ${\mathbb{R}}^{n-k+1\choose 2}.$ Thus,
$\operatorname{Sp}_{G}(k)$ is the set of $k-$isospectral subgraphs of $G$, or
the set of Laplacians of $k-$isospectral subgraphs of $G$, or a subset of
${\mathbb{R}}^{n-k+1\choose 2}$, each point of which provides a $Y$ that in
turn provides the Laplacian $L=F+\Phi_{>k}Y\Phi_{>k}^{\top}$ of a
$k-$isospectral subgraph of $G$. This last interpretation is the most helpful
for computations and we describe its geometry.

The expressions $L_{st}$ are linear functions in the entries $y_{ij}$ of $Y$.
If we denote the columns of $\Phi_{>k}^{\top}$ as
$c_{1},c_{2},\ldots,c_{n}\in{\mathbb{R}}^{n-k}$ then the $st$ entry of
$\Phi_{>k}Y\Phi_{>k}^{\top}$ is

(7) $\displaystyle c_{s}^{\top}Yc_{t}=\langle Y,c_{s}c_{t}^{\top}\rangle.$

Therefore,

(8) $\displaystyle L_{st}=F_{st}+\langle Y,c_{s}c_{t}^{\top}\rangle.$

Define the polyhedron

(10) $\displaystyle P_{G}(k):=$
$\displaystyle\left\\{(y_{ij})\in{\mathbb{R}}^{n-k+1\choose
2}\,:\,\begin{array}[]{cc}L_{st}\leq 0\,\,\forall\,\,(s,t)\in
E\end{array}\right\\}$

and the spectrahedron (the intersection of a psd cone with an affine space)

(11)
$\displaystyle\begin{split}S_{G}(k):=&\left\\{(y_{ij})\in{\mathbb{R}}^{n-k+1\choose
2}\,:\,\begin{array}[]{cc}L_{st}=0\,\,\forall\,\,(s,t)\not\in E,s\neq t,\\\
Y\succeq 0\end{array}\right\\}\end{split}$

The set $\textup{Sp}_{G}(k)$ is the intersection of the (convex) polyhedron
$P_{G}(k)$ and the (convex) spectrahedron $S_{G}(k)$. Alternately it is the
intersection of the psd cone $\mathcal{S}^{n-k}_{+}$ with the (convex)
polyhedron defined the linear inequalities $L_{st}\leq 0$ for all $(s,t)\in E$
and the linear equations $L_{st}=0$ for all $(s,t)\not\in E,s\neq t$. Further,
the sets $\operatorname{Sp}_{G}(k)$, when thought of as sets of Laplacians,
are nested since any subgraph that shares the first $k$ eigenvalues and
eigenvectors with $G$ also shares the first $k-1$ of them with $G$. This
aligns with our intuition that the difficulty of finding a $k-$sparisfier must
increase with $k$.

######  Corollary 3.2.

The sets $\\{\textup{Sp}_{G}(k)\\}$ are convex and nested;
$\operatorname{Sp}_{G}(k)\subseteq\operatorname{Sp}_{G}(k-1)$ for all $2\leq
k\leq n$.

In Example 2.1, the psd constraints on $Y$ are redundant while in Example 2.2,
the psd constraints are active. In both examples, the polyhedron $P_{G}(k)$ is
unbounded.

Recall that a $k-$sparsifier of $G$ is a $k-$isospectral subgraph of $G$ that
has at least one less edge than $G$. A natural goal when sparsifying a graph
is to delete as many edges as possible (while possibly reweighting others to
preserve the first $k$ eigenvectors and eigenvalues). The equations $L_{st}=0$
for all $(s,t)\not\in E$ ensure that $E(\tilde{G})\subseteq E(G)$ for the
graphs $\tilde{G}\in\operatorname{Sp}_{G}(k)$. An edge $(s,t)\in E$ is missing
in $\tilde{G}$ if and only if the linear inequality $L_{st}\leq 0$ holds at
equality in $L_{\tilde{G}}$. Using this, we can locate the $k-$sparsifiers in
$\operatorname{Sp}_{G}(k)$.

######  Corollary 3.3.

Suppose a $k-$sparsifier $\tilde{G}$ of $G$ has Laplacian

$L=F+\Phi_{>k}Y_{\tilde{G}}\Phi_{>k}^{\top}$

in ${\textup{Sp}}_{G}(k)$. The sparsity of $\tilde{G}$, namely the edges of
$G$ that are not present in $\tilde{G}$, is determined by the face of
$P_{G}(k)$ that contains $Y_{\tilde{G}}$. More precisely, $(s,t)\in
E\setminus\tilde{E}$ if and only if the inequality $L_{st}\leq 0$ holds at
equality on the face containing $Y_{\tilde{G}}$.

_Proof of Corollary 3.3_

Less formally, the sparsity patterns of $k-$sparsifiers of $G$ are indexed by
the faces of $P_{G}(k)$ contained (at least partially) in
$\textup{Sp}_{G}(k)$. If $Y_{\tilde{G}}$ lies on an $\ell$-dimensional face of
$P_{G}(k)$, then $\tilde{G}$ is missing at least $|E|-\ell$ edges that were
present in $G$. However, it can miss many more edges in particular graphs,
because the equations defining the off-diagonal entries of $L_{\tilde{G}}$
need not be unique, see Example 3.3.

In general, $\operatorname{Sp}_{G}(k)$ depends on the choice of eigenbasis of
$L_{G}$ since the construction picks $k$ specific eigenpairs to freeze in the
$k-$isospectral subgraphs of $G$. Therefore, the $k-$sparsifiers you get will
depend on the choice of eigenbasis. See for example the two different
$\operatorname{Sp}_{K_{5}}(4)$ in § 3.3. However, this discrepancy only occurs
when we freeze some eigenpairs with a specific eigenvalue and leave out
others. In other words, if the choice of $k$ preserves entire eigenspaces,
then $\operatorname{Sp}_{G}(k)$ does not depend on the choice of eigenbasis of
$L_{G}$.

######  Theorem 3.4.

If $\lambda_{k}<\lambda_{k+1}$, then $\operatorname{Sp}_{G}(k)$ is independent
of the choice of eigenbasis of the Laplacian $L_{G}$.

_Proof of Theorem 3.4_

###  3.3. The complete graph $K_{5}$

We now compute $\operatorname{Sp}_{G}(k)$ in detail for two values of $k$ for
the complete graph $G=K_{5}$. Suppose we fix the following eigenpairs of $G$:

$\left(0,\varphi_{1}=\frac{1}{\sqrt{5}}\begin{bmatrix}1\\\ 1\\\ 1\\\ 1\\\
1\end{bmatrix}\right),\left(5,\varphi_{2}=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\\
-1\\\ 0\\\ 0\\\
0\end{bmatrix},\varphi_{3}=\frac{1}{\sqrt{2}}\begin{bmatrix}0\\\ 0\\\ 1\\\
-1\\\ 0\end{bmatrix},\varphi_{4}=\frac{1}{2}\begin{bmatrix}1\\\ 1\\\ -1\\\
-1\\\ 0\end{bmatrix},\varphi_{5}=\frac{1}{2\sqrt{5}}\begin{bmatrix}1\\\ 1\\\
1\\\ 1\\\ -4\end{bmatrix}\right).$

For any $k$, the first step in computing $\operatorname{Sp}_{G}(k)$ is to
compute the fixed matrix $F$. Here is a helpful observation that holds in
general.

######  Lemma 3.5.

For any graph $G$, if $\lambda_{2}=\cdots=\lambda_{k}$, then $F$ is a scaling
of the Laplacian of $K_{n}$, namely
$F=\frac{\lambda_{2}}{n}L_{K_{n}}=\lambda_{2}(I_{n}-\frac{1}{n}J_{n})$, where
$J_{n}$ is the $n\times n$ matrix of all ones.

_Proof of Lemma 3.5_

Consider $k=3$. By Lemma 3.5, $F=L_{K_{5}}=5I_{5}-J_{5}$. Setting

$Y=\begin{bmatrix}a&c\\\ c&b\end{bmatrix},$

compute $L=F+\Phi_{>3}Y\Phi_{>3}^{\top}$. Since $K_{5}$ has no missing edges,
all off-diagonal entries of $L$ contribute an inequality $L_{st}\leq 0$ to the
polyhedron $P_{K_{5}}(3)$. We list the inequalities with the edges
contributing each inequality on the right:

(12) $\displaystyle 5a+b+2\sqrt{5}c$ $\displaystyle\leq 20$
$\displaystyle(1,2)$ (13) $\displaystyle 5a+b-2\sqrt{5}c$ $\displaystyle\leq
20$ $\displaystyle(3,4)$ (14) $\displaystyle-5a+b\phantom{,-2\sqrt{5}c}$
$\displaystyle\leq 20$ $\displaystyle(1,3),(1,4),(2,3),(2,4)$ (15)
$\displaystyle-b-\sqrt{5}c$ $\displaystyle\leq 5$ $\displaystyle(1,5),(2,5)$
(16) $\displaystyle-b+\sqrt{5}c$ $\displaystyle\leq 5$
$\displaystyle(3,5),(4,5)$

Note that several edges can contribute the same inequality. The polyhedron
$P_{K_{5}}(3)$ is a square pyramid as seen in Figure 7. The base is given by
the hyperplane $-5a+b=20$. Intersecting it with $\mathcal{S}^{2}_{+}$ we get
$\operatorname{Sp}_{3}(K_{5})$, seen in Figure 8.

Figure 7. The polyhedron $P_{K_{5}}(3)$ and its intersection with
$\mathcal{S}^{2}_{+}$.

The two flat faces of $\textup{Sp}_{K_{5}}(3)$ are defined by $5a+b\pm
2\sqrt{5}c=20$. The interiors of these faces index $3-$sparsifiers missing
edge $(1,2)$ or $(3,4)$.

Figure 8. The first picture shows $\operatorname{Sp}_{K_{5}}(3)$, the set of
points $(a,b,c)$ indexing $3-$isospectral subgraphs of $K_{5}$. Its flat sides
are cut out by the first two hyperplanes as seen in the middle picture. The
last picture shows the vertex $(0,20,0)$ of $\operatorname{Sp}_{K_{5}}(3)$
(black dot) at which the first three hyperplanes intersect.

The hyperplanes with equations $-b\pm\sqrt{5}c=5$ do not touch
$\textup{Sp}_{K_{5}}(3)$. This means that with this choice of basis, $K_{5}$
has no $3-$isospectral subgraph that is missing any edge incident to vertex 5.
The intersection of the other three hyperplanes with $\textup{Sp}_{K_{5}}(3)$
is the point $(0,20,0)$. This point produces a spanning tree sparsifier
consisting of all edges incident to vertex 5. We depict these intersections in
Figure 8.

Now consider $k=4$. If we hold the first four eigenpairs fixed, then
$\Phi_{>4}=\varphi_{5}$, $Y=[a]$, and the inequalities defining $P_{K_{5}}(4)$
are

(17) $\displaystyle-5\leq a\leq 20.$

The lower bound comes from the edges $(1,5),(2,5),(3,5),(4,5)$ and the upper
bound comes from the other edges. Since $Y\succeq 0$, $a\geq 0$, and
$\textup{Sp}_{K_{5}}(4)=[0,20]$. This means that there is a unique
$4-$sparsifier indexed by $a=20$ and it corresponds to the spanning tree with
edges $(1,5),(2,5),(3,5),(4,5)$.

On the other hand, if we had chosen $\Phi_{>4}=\varphi_{4}$, then
$P_{K_{5}}(4)$ is defined by $-4\leq a\leq 4$, which makes
$\textup{Sp}_{K_{5}}(4)=[0,4]$. The bound $a\leq 4$ is given by the edges
$(1,2)$ and $(3,4)$. Therefore, the unique $4-$sparsifier is now indexed by
$a=4$ and is missing edges $(1,2)$ and $(3,4)$. In particular, there is no
spanning tree $4-$sparsifier for this choice of eigenvectors to hold constant.

Lastly, if we had chosen $\Phi_{>4}=\varphi_{2}$, then
$\operatorname{Sp}_{K_{4}}(4)=[0,\infty]=\mathcal{S}^{1}_{+}$. The only
inequality is of the form $a\geq-2$ and the hyperplane $a=-2$ does not support
$\operatorname{Sp}_{K_{4}}(4)$. Therefore, there are no $4-$sparsifiers for
this ordering of eigenvectors.

By Theorem 3.4 we see this wild behavior as the choice of $\varphi_{n}$
changes because we are not choosing to preserve all the eigenvectors
corresponding to $\lambda_{2}=5$.

##  4\. Bounds on the Maximal Sparsification

Given our notion of a $k-$sparsifier, the main question now is: how large can
we choose $k$ and still obtain nontrivial sparsification? Or, conversely, if
we wish to aggressively remove edges, how much of the spectrum can we
reasonably hope to preserve? The purpose of this section is to introduce some
basic bounds. At the heart of it is a Linear Algebra Heuristic, introduced in
§4.1, which provides a guideline for what is true generically. Before
discussing the general case, we start with two different extreme settings: the
(weighted) complete graph can be sparsified to a high degree and a tree can
never be sparsified.

######  Theorem 4.1.

If $G$ is a weighted complete graph, then $G$ is guaranteed to have a
$k-$sparsifier for all $k\leq n-2$.

_Proof of Theorem 4.1 _

This result is sharp. As we saw at the end of Example 3.3, if $\varphi_{n}$ is
chosen to be $(1/\sqrt{2},-1/\sqrt{2},0,0,0)$ then $K_{5}$ has no
$4-$sparsifiers. This counterexample is also sharp in the sense that whenever
the eigenvector $\varphi_{n}$ has at least three nonzero coordinates, then the
graph has an $(n-1)-$sparsifier – see Proposition 7.1.

On the other extreme, if $G$ is a tree, then removing any edge disconnects the
graph. Since all $k-$isospectral subgraphs of $G$ are connected when $k\geq 2$
(Lemma 1.2), we have the following.

######  Lemma 4.2.

If $G=([n],E,w)$ is a tree, then even at $k=2$, a $k-$isospectral subgraph of
$G$ cannot lose any edges.

More generally, recalling that the multiplicity of the first eigenvalue
captures the number of connected components, we see that any sparsifier
preserving the eigenspace corresponding to eigenvalue 0 needs to necessarily
preserve the number of connected components.

###  4.1. The Linear Algebra Heuristic

In our model, $\operatorname{Sp}_{k}(G)$ is parameterized by at most
$n-k+1\choose 2$ variables corresponding to the distinct entries of
$Y\in\mathcal{S}^{n-k}_{+}$. Every missing edge of $G$ contributes a linear
equation to the description of $\operatorname{Sp}_{G}(k)$ while every edge
contributes a linear inequality. If $G$ is sufficiently generic, then we would
expect that the equations are linearly independent; equivalently, each missing
edge decreases the dimension of $\operatorname{Sp}_{G}(k)$ by one. However $G$
itself is in $\operatorname{Sp}_{G}(k)$ for all $k$. So, if $G$ is missing at
least $\binom{n-k+1}{2}$ edges, then we expect $\operatorname{Sp}_{G}(k)$ to
contain just $G$, and $G$ to have no $k-$sparsifiers. We refer to this basic
principle as the Linear Algebra Heuristic, which tells us what one can
generically expect of $k-$sparsifiers.

######  Principle (Linear Algebra Heuristic).

If $G=([n],E,w)$ is a ‘generic’ graph and

$|E|\leq{n\choose 2}-{n-k+1\choose 2}$

then, generically, the only $k-$isospectral subgraph of $G$ is $G$ itself.

The notion of ‘generic’ is to be understood as follows: ‘typical’ linear
systems are solvable as long as the number of variables is at least as large
as the number of equations. This is not always true: the equations could be
linearly dependent and only be solvable for particular right-hand sides.
However, having such a dependence is delicate and not ‘generically’ the case:
in particular, if one were to perturb the weights $w$ of a graph ever so
slightly, one would expect the Linear Algebra Heuristic to apply to ‘most’ (in
the measure-theoretic sense) perturbations. Simultaneously, since having such
dependencies is non-generic, failures of the Linear Algebra Heuristic are
interesting and a sign of a great degree of underlying structure.

We quickly mention an easy sample application of the Linear Algebra Heuristic.
If we consider all unweighted graphs with $n=12$ vertices and $|E|=36$ edges,
then according to the Linear Algebra Heuristic, we expect that ‘generically’,
there are $4-$sparsifiers, but the only $5-$isospectral subgraph is the graph
itself. Some numerical experiments show that this is typically true for Erdős-
Renyi random graphs $G(12,1/2)$ conditioned on having 36 edges.

###  4.2. Exceptions

To be clear, no direction of the Linear Algebra Heuristic is true for all
graphs. Figure 9 exhibits an unweighted graph $G$ with $n=12$ and

$|E|=36\leq{n\choose 2}-{n-5+1\choose 2}=38$

that sparsifies up to $k=8$. Unsurprisingly, these exceptions typically
possess some type of symmetry.

Figure 9. A graph on $n=12$ vertices and $|E|=36$ edges that admits an
$8-$sparsifier with 4 edges being deleted. The Linear Algebra Heuristic
predicts that this should not happen

It is also possible for a graph to have more edges than the difference of
binomial coefficients in the linear algebra bound and not have
$k-$sparsifiers. Theorem 4.3 exhibits a family of weighted graphs on $n$
vertices where

$|E|>{n\choose 2}-{n-(n-2)+1\choose 2}={n\choose 2}-3,$

and yet, $G$ has no $(n-2)-$sparsifiers. The reason is that the spectrahedron
$S_{G}(n-2)$ lies strictly inside the polyhedron $P_{G}(n-2)$ and hence no
face of $P_{G}(n-2)$ supports $\operatorname{Sp}_{G}(n-2)$, see Figure 17.

######  Theorem 4.3.

For each $n\geq 4$, there is a weighted graph missing only one edge that does
not sparsify at $k=n-2$.

_Proof of Theorem 4.3 _

For $n=4$, Theorem 4.3 provides an example of a non-tree weighted graph that
does not sparsify even at $k=2$ (see Figure 10). In contrast, the unweighted
graph missing exactly one edge always has a spanning tree $2-$sparsifier.

1234 Figure 10. A weighted graph that cannot sparsify even at $k=2$. Thinner
edges have weight 1, and thicker edges have weight 11.

######  Theorem 4.4.

Let $G=([n],E)$ be the unweighted complete graph missing an edge. Then
$\operatorname{Sp}_{G}(2)$ contains a spanning tree sparsifier for any choice
of eigenbasis.

_Proof of Theorem 4.4 _

These last two theorems highlight the role of weights in the geometry of
isospectral subgraphs and sparsifiers. The geometry is controlled by the
arithmetic of the weights and the ensuing eigenstructure of the Laplacian, not
just by combinatorics.

Lastly, we discuss a particularly interesting extremal case: the cube graph
$Q_{d}$ on $V=\left\\{0,1\right\\}^{d}$ where any two vertices are connected
if they differ on exactly one coordinate. The Linear Algebra Heuristic
suggests that

$d\cdot 2^{d-1}=|E|\sim{2^{d}\choose 2}-{2^{d}-k+1\choose 2}$

should be the natural cut-off after which no further sparsification is
possible. Solving the quadratic polynomial, this predicts that as
$d\rightarrow\infty$, we can sparsify up to $k\sim d/2$. Due to the
extraordinary symmetry of the cube graph and the special structure of its
eigenvalues and eigenvectors, sparsification up to a higher value of $k$ is
possible, up to $k=d$. However, the first two eigenspaces uniquely determine
the cube graph, which is to say that no sparsification is possible at $k=d+1$.

######  Theorem 4.5.

There is no sparsification of the cube graph $Q_{d}$ that preserves the first
two eigenspaces (the first $d+1$ eigenvectors and eigenvalues) except for the
trivial sparsification which leaves all edge weights invariant; $w_{ab}=1$.

_Proof of Theorem 4.5_

One would naturally wonder whether other graphs with special symmetries might
perhaps admit a similar type of rigidity structure; this seems like an
interesting problem but is outside the scope of this paper.

##  5\. Families of Band-limited Spectral Sparsifiers

The purpose of this section is to discuss different graph families and
describe what can be said about their sparsification properties. This leads to
problems at the interface of combinatorics, polyhedral geometry and spectral
geometry.

###  5.1. The Complete Graph.

The unweighted complete graph plays a special role; it has eigenvalues $0$ and
$n$ (with multiplicity $n-1$) with eigenspaces
$\operatorname{span}\\{\mathbbm{1}\\}$ and $\mathbbm{1}^{\perp}$ respectively.
Since there is only one non-trivial eigenspace, any sparsification of $K_{n}$
must depend on a choice of eigenbasis. Recall the $4-$sparsifiers of $K_{5}$
from § 3.3.

######  Theorem 5.1.

There is a choice of eigenbasis so that for every $k<n$, a spanning tree is a
$k-$sparsifier of $K_{n}$. The spanning tree we exhibit is the star graph
$K_{1,n-1}$, where every edge has equal weight $n$.

_Proof of Theorem 5.1_

123456 Figure 11. A $5-$sparsifier of $K_{6}$.

###  5.2. The Wheel Graph

Let $W_{n+1}$ denote the wheel graph on $n+1$ vertices, for $n\geq 3$. We will
assume that the vertices are ordered so that $n+1$ is the center of the wheel
and that $i\sim(i+1\mod n)$ for $i\in[n]$ (see Figure 12). The spectrum of
$W_{n+1}$ is well understood from its formulation as the join of the cycle
$C_{n}$ and a single vertex $n+1$, see Table 3 for more details [8, 21]. The
least nonzero eigenvalue of $L_{W_{n+1}}$ is $3-2\cos(2\pi/n)$ which has
multiplicity 2.

$9$12345678 Figure 12. A $3-$sparsifier of $W_{9}$.

######  Theorem 5.2.

There is a $3-$sparsifier of $W_{n+1}$ which is a spanning tree. The spanning
tree we exhibit is the star graph $K_{1,n}$, where every edge has equal weight
$3-2\cos(2\pi/n)$.

_Proof of Theorem 5.2_

We do not expect any $4-$sparsifiers of the wheel by the Linear Algebra
Heuristic. Recalling that $W_{n+1}$ has $2n$ edges and $n+1$ vertices, this
follows because

$|E|=2n<3(n-1)=\binom{n+1}{2}-\binom{(n+1)-4+1}{2}.$

###  5.3. A General Principle

The existence of $k-$sparsifiers in a graph family is a statement about the
eigenvectors and eigenvalues of the Graph Laplacian of graphs in the family.
There appears to be a general principle that is worth recording.

######  Theorem 5.3.

Let $G=([n],E,w)$ be a connected, weighted graph and let
$T=([n],E_{T},w|_{E_{T}})$ be a spanning tree of $G$. Let $k\in[n]$ be
arbitrary and let $\varphi_{1},\dots,\varphi_{k}$ be eigenvectors
corresponding to the $k$ smallest eigenvalues of the spanning tree $T$.
Suppose that for all $(u,v)\in E$ either

$(u,v)\in
E_{T}\qquad\mbox{or}\qquad\varphi_{i}(u)=\varphi_{i}(v)\qquad\mbox{for
all}~{}1\leq i\leq k,$

then the spanning tree $T$ is a $k-$sparsifier of $G$ with respect to
$\left\\{\varphi_{1},\dots,\varphi_{k}\right\\}.$

_Proof of Theorem 5.3_ The result says that if a graph has the property that
eigenvectors only change along the edges of a spanning tree, then that
spanning tree is actually a $k-$sparsifier.

Figure 13. A $2-$sparsifier of $B_{6,5}$.

The first application of Theorem 5.3 is for the Barbell Graph $B_{n,n}$, which
is two $n$-cliques joined by a bridge. Its Laplacian is

$L_{B_{n,n}}=\left(\begin{array}[]{@{}c|c@{}}nI_{n}-J_{n}&0_{n,n}\\\ \hline\cr
0_{n,n}&mI_{n}-J_{m}\end{array}\right)+E_{n,n}+E_{n+1,n+1}-E_{n+1,n}-E_{n,n+1}$

where $E_{i,j}$ is the matrix with a single 1 in the $(i,j)$-th place. A
general statement is possible for a slight generalization to $B_{n,m}$, an
$n$-clique and $m$-clique joined by a bridge, but we restrict to $B_{n,n}$ for
brevity.

######  Corollary 5.4.

Let $G=B_{n,n}$. The spanning tree given by the two copies of the star graph
$K_{1,n-1}$ together with the bridge (every edge has weight $1$) is a
2-sparsifier.

The result follows immediately from Theorem 5.3 together with the spectral
information of $B_{n,n}$ which is recorded in Table 1. We have not seen this
information recorded in the literature elsewhere.

eigenvalue | dimension | spanning eigenvectors
---|---|---
0 | 1 | $\mathbbm{1}_{2n}$
$1+\alpha$ | 1 | $(-\mathbbm{1}_{n-1},\alpha,-\alpha,\mathbbm{1}_{n-1})$
$n$ | $2n-3$ | $\\{e_{i}-e_{i+1}\\}_{i=1}^{n-2}\,\cup\,\\{e_{n+1+i}-e_{n+2+i}\\}_{i=1}^{n-2}$
|  | $\cup\,\\{(\mathbbm{1}_{n-1},1-n,1-n,\mathbbm{1}_{n-1})\\}$
$1+\beta$ | 1 | $(-\mathbbm{1}_{n-1},\beta,-\beta,\mathbbm{1}_{n-1})$
Table 1. The spectral information of the Barbell Graph $B_{n,n}$ by increasing
eigenvalue. Here $-1<\alpha=n/2-\sqrt{n^{2}+4(n-1)}/2<0$ and
$\beta=n/2+\sqrt{n^{2}+4(n-1)}/2>n.$

The second family of examples will be given by the lollipop graph. We define
the $(m,p)$-Lollipop Graph to be an $m$-clique joined to the path graph on $p$
vertices by a bridge. The $(7,5)$-Lollipop Graph is exhibited in Figure 14
(and was also seen in Figure 1).

Figure 14. Lollipop graph on $n=12$ vertices and $m=26$ edges has a spanning
tree $3$-sparsifier.

The spectrum of these graphs appears to be somewhat difficult to write down,
however, the dynamics of the first few eigenvectors is easy to understand from
a qualitative perspective. We recall that eigenvectors corresponding to small
eigenvalues can really be understood as minimizers of the Rayleigh-Ritz
functional

$\frac{\left\langle f,L_{G}f\right\rangle}{\left\langle
f,f\right\rangle}=\frac{\sum_{(u,v)\in E}(f(u)-f(v))^{2}}{\sum_{v\in
V}f(v)^{2}}.$

In the case of the lollipop graph, the functional is easy to understand:
variation across the path is ‘energetically’ cheaper than variation within the
complete graph since there are many more connections within the complete graph
and variations show up in many more additional terms. Writing the vertex set
as $V=K_{m-1}\cup P_{p+1}$, we expect the first few eigenvectors to be
constant on $K_{m-1}$. The effect becomes more pronounced as the attached path
becomes longer. Whenever that happens, Theorem 5.3 immediately applies. Many
other such examples can be constructed.

##  6\. Preserving the Quadratic Form

In the work of Batson, Spielman, Srivastava and Teng (see [5] and references
therein) the sparsifiers of a graph $G$ are graphs $\tilde{G}$ on the same
vertices whose quadratic forms $x^{\top}L_{\tilde{G}}x$ are approximately the
same as $x^{\top}L_{G}x$. If one were to focus on the quadratic form, but
think along the lines of this paper, then it is natural to consider a band-
limited sparsifier of a graph $G$ as a subgraph $\tilde{G}$ such that
$Q_{G}(x)=Q_{\tilde{G}}(x)$ for all
$x\in\textup{span}\\{\varphi_{1},\ldots,\varphi_{k}\\}$.

######  Definition 6.1.

A graph $\tilde{G}=([n],\tilde{E},\tilde{w})$ is a $Q_{k}(x)-$sparsifier of
$G$ if $\tilde{E}\subseteq E$, $\tilde{w}_{e}>0$ for all $e\in\tilde{E}$ and
$Q_{G}(x)=Q_{\tilde{G}}(x)$ for all
$x\in\textup{span}\\{\varphi_{1},\ldots,\varphi_{k}\\}$.

Unlike in previous sections, we do not insist that a $Q_{k}(x)-$sparsifier of
$G$ should lose edges. Definition 6.1 yields a polyhedron containing all
possible Laplacians $L$ that correspond to $Q_{k}(x)-$sparsifiers of $G$. We
derive this model below and compare it to Definition 1.1. Note that the only
$Q_{n}(x)-$sparsifier of $G$ is $G$ itself, but when $k<n$, this definition
admits non-trivial sparsifiers.

Recall that a spectrahedron is the intersection of a psd cone with an affine
subspace of symmetric matrices.

######  Lemma 6.2.

For a given matrix $A\succeq 0$ and a proper subspace
$\Lambda\subset{\mathbb{R}}^{n}$, the set

$S_{A}(\Lambda)=\\{B\succeq
0\,:\,x^{\top}Ax=x^{\top}Bx\,\,\forall\,x\in\Lambda\\}$

is a spectrahedron.

_Proof of Lemma 6.2_

The $Q_{k}(x)-$sparsifier set of $G$ is the intersection of
$S_{L_{G}}(\textup{span}\\{\varphi_{1},\ldots,\varphi_{k}\\})$ and the set of
Laplacians of weighted subgraphs of $G$. When $A=L_{G}$, the proof of Lemma
6.2 shows that

$S_{L_{G}}(\textup{span}\\{\varphi_{1},\ldots,\varphi_{k}\\})=\left\\{L\succeq
0:\begin{array}[]{c}\langle
L,\varphi_{i}\varphi_{i}^{\top}\rangle=\lambda_{i}\text{ for }i=1,\ldots,k\\\
\langle
L,\varphi_{i}\varphi_{j}^{\top}+\varphi_{j}\varphi_{i}^{\top}\rangle=0\text{
for }i\neq j\end{array}\right\\}.$

The additional conditions needed for $L\in
S_{L_{G}}(\textup{span}\\{\varphi_{1},\ldots,\varphi_{k}\\})$ to be the
Laplacian of a weighted subgraph of $G$ are:

  1. (1)

$L_{ij}=0$ for all $i\neq j,\,(i,j)\not\in E$. This guarantees that
$\tilde{E}\subseteq E$.

  2. (2)

$L_{ij}\leq 0$ for all $i\neq j$. This guarantees that
$\tilde{w}_{ij}=-L_{ij}\geq 0$.

  3. (3)

$L_{ii}=-\sum_{(i,j)\in E}L_{ij}$ for all $i$.

Also, $\tilde{G}$ is connected if and only if $\operatorname{rk}(L)=n-1$. We
can bake conditions (1)–(3) into the following structured symbolic matrix:

(18) $\displaystyle L({\tt w})=\begin{bmatrix}\sum_{j\neq
1}{\tt{w}}_{1j}&-{\tt{w}}_{12}&-{\tt{w}}_{13}&\cdots&-{\tt{w}}_{1n}\\\
-{\tt{w}}_{12}&\sum_{j\neq
2}{\tt{w}}_{2j}&-{\tt{w}}_{23}&\cdots&-{\tt{w}}_{2n}\\\
\vdots&\vdots&\vdots&\vdots&\vdots\\\
-{\tt{w}}_{1n}&\cdots&\cdots&\cdots&\sum_{j\neq n}{\tt{w}}_{nj}\end{bmatrix}$

with ${\tt{w}}_{ij}=0$ if $(i,j)\not\in E$. Then all subgraphs of $G$ will
have Laplacians of the form $L(\bar{w})$ for some
$\bar{w}\in{\mathbb{R}}^{E}_{\geq 0}$. By construction
$L({\tt{w}})\mathbbm{1}=0=L({\tt{w}})\varphi_{1}$. Using this, and the fact
that $L({\tt{w}})$ is symmetric, we get the following facts:

######  Lemma 6.3.

  1. (1)

$\varphi_{1}^{\top}L({\tt{w}})\varphi_{1}=0$,

  2. (2)

$\varphi_{1}^{\top}L({\tt{w}})\varphi_{j}=0=\varphi_{j}^{\top}L({\tt{w}})\varphi_{1}$
for all $j>1$, and

  3. (3)

$\langle L({\tt{w}}),\varphi_{i}\varphi_{j}^{\top}\rangle=\langle
L({\tt{w}}),\varphi_{j}\varphi_{i}^{\top}\rangle$ which implies that

(19) $\displaystyle\langle
L({\tt{w}}),\varphi_{i}\varphi_{j}^{\top}+\varphi_{j}\varphi_{i}^{\top}\rangle=2\langle
L({\tt{w}}),\varphi_{i}\varphi_{j}^{\top}\rangle=2\langle
L({\tt{w}}),\varphi_{j}\varphi_{i}^{\top}\rangle.$

Define $L^{\prime}({\tt{w}})$ to be the principal submatrix of $L({\tt{w}})$
obtained by deleting the last row and column.

######  Theorem 6.4.

The Laplacians of $Q_{k}(x)-$sparsifiers of $G$ are the matrices $L(w)$ for
all $w$ in the polyhedron

$P^{Q(x)}_{G}(k)=\left\\{w\in{\mathbb{R}}^{E}_{\geq
0}\,:\,\begin{array}[]{l}\langle
L(w),\varphi_{i}\varphi_{i}^{\top}\rangle=\lambda_{i}\,\,\forall\,i=2,\ldots,k\\\
\langle L(w),\varphi_{i}\varphi_{j}^{\top}\rangle=0,\,\,\forall\,2\leq i<j\leq
k\\\ \end{array}\right\\}$

which lies in the semialgebraic region $\det(L^{\prime}(w))\geq 0$.

  1. (1)

The sparsity patterns of the $Q_{k}(x)-$sparsifiers of $G$ are in bijection
with the faces of $P^{Q(x)}_{G}(k)$.

  2. (2)

The connected sparsifiers correspond to faces where $\det(L^{\prime}(w))>0$.

_Proof of Theorem 6.4_

Lemma 1.3 implies the following.

######  Lemma 6.5.

The set $\textup{Sp}_{G}(k)$ of $k-$isospectral subgraphs of $G$ is contained
in the polyhedron $P^{Q(x)}_{G}(k)$.

A disadvantage of the the larger $P^{Q(x)}_{G}(k)$ is that the spectrum of
$\tilde{G}$ can be wildly different from that of $G$, even when restricting
our attention to connected sparsifiers. We illustrate this on the
3-dimensional cube graph. We avoid the notation $Q_{d}$ for cube graphs here
to avoid confusion with the $Q_{k}(x)-$sparsifier notation. Recall from
Theorem 4.5 that the 3-dimensional cube graph has no $4-$sparsifiers. The
following example contrasts this with the set of $Q_{4}(x)-$sparsifiers of the
cube graph.

######  Example 6.6.

Let $G=([8],E)$ be the 3-dimensional cube graph. There is a spanning tree
$Q_{4}(x)-$sparsifier of $G$ which preserves no eigenpair of $G$. In
particular, the second eigenvalue of this tree is approximately $.3677$,
whereas for $G$, $\lambda_{2}=2$.

Figure 15. The 3-cube graph and a spanning tree $Q_{4}(x)-$sparsifier of it.
Thin edges have weight 1, the medium edge has weight 2, and the thickest edges
have weight 3.

To see this, label the vertices of $G$ as in Figure 15. The eigenvalues of
$L_{G}$ are

$0^{(1)},2^{(3)},4^{(3)},6^{(1)},$

where the exponents record multiplicity. The following vectors form a
orthonormal basis for the eigenspace of $\lambda_{2}=2$ of $L_{G}$.

$\displaystyle\varphi_{2}=[1\,\,,\,\,-1\,\,,\,\,1\,\,,\,\,1\,\,,\,\,-1\,\,,\,\,-1\,\,,\,\,1\,\,,\,\,-1]^{\top}/\sqrt{8}$
$\displaystyle\varphi_{3}=[1\,\,,\,\,1\,\,,\,\,-1\,\,,\,\,1\,\,,\,\,-1\,\,,\,\,1\,\,,\,\,-1\,\,,\,\,-1]^{\top}/\sqrt{8}$
$\displaystyle\varphi_{4}=[1\,\,,\,\,1\,\,,\,\,1\,\,,\,\,-1\,\,,\,\,1\,\,,\,\,-1\,\,,\,\,-1\,\,,\,\,-1]^{\top}/\sqrt{8}.$

From Theorem 6.4, we have the polyhedron

$P_{G}^{Q(x)}(4)=\left\\{w\in{\mathbb{R}}^{E}_{\geq
0}:\begin{array}[]{l}w_{12}+w_{35}+w_{46}+w_{78}=4\\\
w_{13}+w_{25}+w_{47}+w_{68}=4\\\
w_{14}+w_{26}+w_{37}+w_{58}=4\end{array}\right\\}.$

A valid choice of edge weights is

$\displaystyle w_{12}=w_{14}=3$ $\displaystyle w_{13}=2$ $\displaystyle
w_{25}=w_{37}=w_{46}=w_{68}=1$ $\displaystyle
w_{26}=w_{35}=w_{47}=w_{58}=w_{78}=0.$

This spanning tree sparsifier $\tilde{G}$ is shown in Figure 15. Its Laplacian
eigenvalues are

$0,0.3677,0.6383,1.3889,2.4974,3.6368,4.3896,11.0814,$

and none of the eigenvectors of $\tilde{G}$ are eigenvectors of $G$. We can
confirm, however, that the quadratic form is indeed preserved on the
appropriate subspace:

$\displaystyle\varphi_{2}^{\top}L_{\tilde{G}}\varphi_{2}=\varphi_{3}^{\top}L_{\tilde{G}}\varphi_{3}=\varphi_{4}^{\top}L_{\tilde{G}}\varphi_{4}=2\text{,
and}$
$\displaystyle\varphi_{i}^{\top}L_{\tilde{G}}\varphi_{j}=0,\,\,\forall\,i\neq
j\in\\{2,3,4\\}.$

######  Example 6.7.

Consider the weighted complete graph $G=K_{3}$ with edge weights
$w_{12}=1,w_{13}=2,w_{23}=2$. Then

(20) $\displaystyle L_{G}=\begin{bmatrix}3&-1&-2\\\ -1&3&-2\\\
-2&-2&4\end{bmatrix}$

has eigenpairs:

$\left(\lambda_{1}=0,\varphi_{1}=\frac{1}{\sqrt{3}}\begin{bmatrix}1\\\ 1\\\
1\end{bmatrix}\right),\,\,\left(\lambda_{2}=4,\varphi_{2}=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\\
-1\\\
0\end{bmatrix}\right),\,\,\left(\lambda_{3}=6,\varphi_{3}=\frac{1}{\sqrt{6}}\begin{bmatrix}1\\\
1\\\ -2\end{bmatrix}\right).$

Suppose we consider all graphs $\tilde{G}$ with Laplacian

(21) $\displaystyle L=\begin{bmatrix}a+b&-a&-b\\\ -a&a+c&-c\\\
-b&-c&b+c\end{bmatrix}$

and $Q_{\tilde{G}}(x)=Q_{G}(x)$ for all
$x\in\textup{span}\\{\varphi_{1},\varphi_{2}\\}$. Then

(25) $\displaystyle P^{Q(x)}_{G}(2)=\left\\{(a,b,c)\in{\mathbb{R}}^{3}_{\geq
0}\,:\,4a+b+c=8\right\\}\cong\left\\{(a,b)\in{\mathbb{R}}^{2}\,:\,\begin{array}[]{l}a\geq
0\\\ b\geq 0\\\ 8-4a-b\geq 0\end{array}\right\\}$

which is the triangle with corners $\\{(0,0),(0,8),(2,0)\\}$ shown in Figure
16. Each point in the triangle corresponds to a $Q_{2}(x)-$sparsifier of $G$.

Figure 16. Left: Triangle $P^{Q(x)}_{G}(2)$ of all graphs $\tilde{G}$ with
$Q_{G}(x)=Q_{\tilde{G}}(x)$ for all
$x\in\textup{span}\\{\varphi_{1},\varphi_{2}\\}$. The triangle is contained
inside the parabolic region $\det(L^{\prime}(w))\geq 0$. Right: Triangle
$P^{Q(x)}_{G}(2)$ with the line segment $\operatorname{Sp}_{G}(2)$ inside it.

The triangle is contained in the parabolic region cut out by
$\det(L^{\prime}(w))=-4a^{2}-b^{2}-4ab+8a+8b\geq 0$. Its boundary intersects
the triangle at its three corners where $\operatorname{rank}(L)=1$ and
$\tilde{G}$ is disconnected. The sides of the triangle except for the corners
correspond to $Q_{2}(x)-$sparsifiers of $G$ that are spanning trees.

On the other hand, the $2-$isospectral subgraphs of $G$ have Laplacians:

$L=\begin{bmatrix}\frac{16+y}{6}&\frac{y-8}{6}&\frac{-2y-8}{6}\\\
\frac{y-8}{6}&\frac{16+y}{6}&\frac{-2y-8}{6}\\\
\frac{-2y-8}{6}&\frac{-2y-8}{6}&\frac{16+4y}{6}\end{bmatrix},\quad 0\leq y\leq
8.$

Equating to (21),
$\operatorname{Sp}_{G}(2)=[(0,4,4),(\frac{4}{3},\frac{4}{3},\frac{4}{3})]\subset
P^{Q(x)}_{G}(2)$, and $L_{G}$ corresponds to

$(a,b,c)=(1,2,2)=\frac{1}{4}(0,4,4)+\frac{3}{4}(4/3,4/3,4/3).$

The point $(1,1,3)\in P^{Q(x)}_{G}(2)\setminus\operatorname{Sp}_{G}(2)$
corresponds to the graph $G^{\prime}$ with

$L_{G^{\prime}}=\begin{bmatrix}2&-1&-1\\\ -1&4&-3\\\ -1&-3&4\end{bmatrix}$

and eigenpairs

$(0,\psi_{1}=\frac{1}{\sqrt{3}}(1,1,1)^{\top}),(3,\psi_{2}=\frac{1}{\sqrt{6}}(2,-1,-1)^{\top}),(7,\psi_{3}=\frac{1}{\sqrt{2}}(0,-1,1)^{\top}).$

Therefore, $G^{\prime}$ is not $2-$isospectral to $G$, but
$Q_{G}(x)=Q_{G^{\prime}}(x)$ for all
$x\in\textup{span}\\{\varphi_{1},\varphi_{2}\\}$. Indeed, a linear combination
of $\varphi_{1},\varphi_{2}$ looks like
$x=(\alpha+\beta,\alpha-\beta,\alpha)^{\top}$. Check that you get $8\beta^{2}$
when you plug in $x$ into both

$Q_{G}(x)=4(\varphi_{2}^{\top}x)^{2}+6(\varphi_{3}^{\top}x)^{2}\textup{ and
}Q_{G^{\prime}}(x)=3(\psi_{2}^{\top}x)^{2}+7(\psi_{3}^{\top}x)^{2}.$

##  7\. Proofs

### Proof of Lemma 1.3.

If $x\in\textup{span}\\{\varphi_{1},\ldots,\varphi_{k}\\}$, then
$x=\sum_{j=1}^{k}\beta_{j}\varphi_{j}$ for some $\beta_{j}\in{\mathbb{R}}$.
Therefore,

$\displaystyle
Q_{G}(x)=\sum_{i=2}^{n}\lambda_{i}(\varphi_{i}^{\top}x)^{2}=\sum_{i=2}^{n}\lambda_{i}(\varphi_{i}^{\top}\sum_{j=1}^{k}\beta_{j}\varphi_{j})^{2}=\sum_{i=2}^{n}\lambda_{i}(\sum_{j=1}^{k}\beta_{j}\varphi_{i}^{\top}\varphi_{j})^{2}=\sum_{i=1}^{k}\lambda_{i}\beta_{i}^{2}.$

On the other hand,

$\displaystyle
Q_{\tilde{G}}(x)=\sum_{i=2}^{k}\lambda_{i}(\varphi_{i}^{\top}x)^{2}+\sum_{j=1}^{n-k}\mu_{j}(\psi_{j}^{\top}x)^{2}.$

Since every $\psi_{j}$ is orthogonal to every $\varphi_{i}$ we have that the
second sum

$\displaystyle\sum_{j=1}^{n-k}\mu_{j}(\psi_{j}^{\top}x)^{2}=\sum_{j=1}^{n-k}\mu_{j}(\psi_{i}^{\top}\sum_{j=1}^{k}\beta_{j}\varphi_{j})^{2}=0.$

Therefore,

$\displaystyle
Q_{\tilde{G}}(x)=\sum_{i=1}^{k}\lambda_{i}\beta_{i}^{2}=Q_{G}(x).$

∎

### Proof of Theorem 3.1

Denote the eigenpairs of a $k-$isospectral subgraph $\tilde{G}$ as

(26)
$\displaystyle(0,\varphi_{1}),(\lambda_{2},\varphi_{2}),\ldots,(\lambda_{k},\varphi_{k}),(\mu_{1},\psi_{1}),\ldots,(\mu_{n-k},\psi_{n-k})$

where the first $k$ are the same as those of $G$. The Laplacian of $\tilde{G}$
then has the form

$L=\Phi_{k}\Lambda_{k}\Phi_{k}^{\top}+\Psi
D\Psi^{\top}=\sum_{i=2}^{k}\lambda_{i}\varphi_{i}\varphi_{i}^{\top}+\sum_{j=1}^{n-k}\mu_{j}\psi_{j}\psi_{j}^{\top}$

where $\Psi=\begin{bmatrix}\psi_{1}&\cdots&\psi_{n-k}\end{bmatrix}$ and
$D=\operatorname{diag}(\mu_{1},\ldots,\mu_{n-k})$ are variables that satisfy
the following conditions:

  1. (1)

$\Phi_{k}^{\top}\Psi=0$ since each $\varphi_{i}$ must be orthogonal to each
$\psi_{j}$.

  2. (2)

$\Psi^{\top}\Psi=I_{n-k}$ since $\\{\psi_{j}\\}$ must be a set of orthonormal
vectors.

  3. (3)

$\mu_{j}\geq\lambda_{k}$ for all $j$ since we want $\tilde{G}$ to have the
same first $k$ eigenvalues as $G$.

A ready-made candidate for $\Psi$ that satisfies conditions (1)–(2) is

(27)
$\displaystyle\Phi_{>k}:=\begin{bmatrix}\varphi_{k+1}&\cdots&\varphi_{n}\end{bmatrix}.$

Any other $\Psi$ is of the form $\Phi_{>k}B$ for an orthogonal matrix $B$ in
${\mathbb{R}}^{(n-k)\times(n-k)}$ since $\\{\psi_{j}\\}$ is an orthogonal
basis for $\textup{Span}\\{\varphi_{k+1},\ldots,\varphi_{n}\\}$. Letting
$X=BDB^{\top}$ we can rewrite $L$ as

$\displaystyle L$
$\displaystyle=\Phi_{k}\Lambda_{k}\Phi_{k}^{\top}+(\Phi_{>k}B)D(\Phi_{>k}B)^{\top}$
$\displaystyle=\Phi_{k}\Lambda_{k}\Phi_{k}^{\top}+\Phi_{>k}(BDB^{\top})\Phi_{>k}^{\top}=\Phi_{k}\Lambda_{k}\Phi_{k}^{\top}+\Phi_{>k}X\Phi_{>k}^{\top}.$

The set of all matrices of the form $BDB^{\top}$ where $B$ is an orthogonal
matrix and $D$ is diagonal with all entries positive is the set of positive
definite matrices of size $n-k$, namely the interior of the psd cone
$\mathcal{S}^{n-k}_{+}$. Since we want $D_{ii}\geq\lambda_{k}$, we require
$D\succeq\lambda_{k}I_{n-k}$ which implies that
$X=BDB^{\top}\succeq\lambda_{k}I_{n-k}$, or equivalently,
$X=\lambda_{k}I_{n-k}+Y,\,\,\,Y\succeq 0.$ Hence

(28)
$\displaystyle\Phi_{>k}X\Phi_{>k}^{\top}=\Phi_{>k}(\lambda_{k}I_{n-k}+Y)\Phi_{>k}^{\top}=\lambda_{k}\Phi_{>k}\Phi_{>k}^{\top}+\Phi_{>k}Y\Phi_{>k}^{\top}.$

Putting all of the above together, the Laplacians of $k-$isospectral subgraphs
$\tilde{G}$ of $G$ must be a subset of matrices of the form

(29) $\displaystyle
L=\underbrace{\Phi_{k}\Lambda_{k}\Phi_{k}^{\top}+\lambda_{k}\Phi_{>k}\Phi_{>k}^{\top}}_{=:F}+\Phi_{>k}Y\Phi_{>k}^{\top}.$

where $Y\succeq 0$. By construction, any $L$ of the form (29) has $n-1$
positive eigenvalues and hence its rank is $n-1$. The matrix $F$ has spectral
decomposition

$F=\Phi\operatorname{diag}(0,\lambda_{2},\ldots,\lambda_{k},\lambda_{k},\ldots,\lambda_{k})\Phi^{\top},$

and hence, $F\in\mathcal{S}^{n}_{+}$ and $\operatorname{rank}(F)=n-1$. Since
$L$ is obtained by adding $F$ to a psd matrix
$\Phi_{>k}Y\Phi_{>k}^{\top}\in\mathcal{S}^{n}_{+}$, we have that
$L\in\mathcal{S}^{n}_{+}$.

For $L$ in (29) to be the Laplacian of a subgraph of $G$ we impose the
conditions:

(30) $\displaystyle L_{st}\leq 0\,\,\forall\,(s,t)\in E$ (31) $\displaystyle
L_{st}=0\,\,\forall\,s\neq t,\,(s,t)\not\in E$

The only property left to check is that $L$ is now weakly diagonally dominant.

By construction, $(0,\mathbbm{1})$ is the first eigenpair of $L$ which means
that $L\mathbbm{1}=0$. This guarantees that $-L_{ii}$ is the sum of the off-
diagonal entries in row $i$. Since, $L\succeq 0$, $L_{ii}\geq 0$, and by (30)
and (31), $L_{ii}$ is the only potential positive entry in row $i$. If
$L_{ii}=0$ then all entries in row $i$ are $0$ since $L\succeq 0$ which means
that vertex $i$ in the subgraph $\tilde{G}$ associated to $L$ is isolated.
However, this is impossible since $k\geq 2$ which means that we are requiring
that $\lambda_{2}>0$ is the second eigenvalue of $L$. Thus,
$\operatorname{Sp}_{G}(k)$ is contained in the set of Laplacians of
$k-$isospectral subgraphs of $G$.

On the other hand, $L_{\tilde{G}}$ for any $k-$isospectral subgraph
$\tilde{G}$ of $G$ is in $\operatorname{Sp}_{G}(k)$; choose
$Y=\operatorname{diag}(\mu_{k+1}-\lambda_{k},\ldots,\mu_{n}-\lambda_{k})$.
This proves Theorem 3.1. ∎

### Proof of Corollary 3.3

Every face of $P_{G}(k)$ is determined by some collection of inequalities from
$\\{L_{st}\leq 0\,:\,(s,t)\in E\\}$ holding at equality. The graph $\tilde{G}$
is missing the edge $(s,t)\in E$ if and only if $L_{st}=0$. Thus the faces of
$P_{G}(k)$ that are contained in $\textup{Sp}_{G}(k)$ index all possible
sparsity patterns of $k-$sparsifiers of $G$. ∎

### Proof of Theorem 3.4

Recall that for a fixed eigenbasis $\Phi$,

$\operatorname{Sp}_{G}(k)=\\{L=\Phi_{k}\Lambda_{k}\Phi_{k}^{\top}+\lambda_{k}\Phi_{>k}\Phi_{>k}^{\top}+\Phi_{>k}Y\Phi_{>k}^{\top}\\},$

where $Y\succeq 0$, and the edges of the graph provide additional constraints
on valid choices of $Y$. The ‘fixed’ matrix in this expression is

$F=\Phi_{k}\Lambda_{k}\Phi_{k}^{\top}+\lambda_{k}\Phi_{>k}\Phi_{>k}^{\top}.$

We first show that $F$ does not depend on the choice of basis.

Let $L_{G}$ have $m$ eigenspaces, and let
$0<\lambda_{i_{2}}<\ldots<\lambda_{i_{m}}$ be its distinct positive
eigenvalues where $i_{j}$ is the index of the first eigenvalue associated to
the $j$-th eigenspace. If $\operatorname{Sp}_{G}(k)$ preserves the first
$\ell\in\\{2,\ldots,m-1\\}$ positive eigenspaces, then $k=i_{\ell+1}-1$. Let
$\Phi$ and $\Psi$ be two eigenbases of $L_{G}$, and let $\Phi_{\lambda}$
denote the submatrix of $\Phi$ consisting of the columns which span the
eigenspace with eigenvalue $\lambda$. Then there is an orthogonal matrix
$U_{j}$ such that $\Phi_{\lambda_{i_{j}}}U_{j}=\Psi_{\lambda_{i_{j}}}$ for
each $j\in[m]$. Since $U_{j}U_{j}^{\top}$ is the identity, we have that

$\displaystyle F$
$\displaystyle=\Phi_{k}\Lambda_{k}\Phi_{k}^{\top}+\lambda_{k}\Phi_{>k}\Phi_{>k}^{\top}$
$\displaystyle=\sum_{j=2}^{\ell}\lambda_{i_{j}}\Phi_{\lambda_{i_{j}}}\Phi_{\lambda_{i_{j}}}^{\top}+\lambda_{i_{\ell}}\sum_{j=\ell+1}^{m}\Phi_{\lambda_{i_{j}}}\Phi_{\lambda_{i_{j}}}^{\top}$
$\displaystyle=\sum_{j=2}^{\ell}\lambda_{i_{j}}\Phi_{\lambda_{i_{j}}}U_{j}U_{j}^{\top}\Phi_{\lambda_{i_{j}}}^{\top}+\lambda_{i_{\ell}}\sum_{j=\ell+1}^{m}\Phi_{\lambda_{i_{j}}}U_{j}U_{j}^{\top}\Phi_{\lambda_{i_{j}}}^{\top}$
$\displaystyle=\sum_{j=2}^{\ell}\lambda_{i_{j}}\Psi_{\lambda_{i_{j}}}\Psi_{\lambda_{i_{j}}}^{\top}+\lambda_{i_{\ell}}\sum_{j=\ell+1}^{m}\Psi_{\lambda_{i_{j}}}\Psi_{\lambda_{i_{j}}}^{\top}$
$\displaystyle=\Psi_{k}\Lambda_{k}\Psi_{k}^{\top}+\lambda_{k}\Psi_{>k}\Psi_{>k}^{\top}$

Thus $F$ does not depend on the choice of eigenbasis. Now, let
$\tilde{U}=\operatorname{diag}(U_{\ell+1},\ldots,U_{m})$, and note that

$\displaystyle\Psi_{>k}Y\Psi_{>k}^{\top}$
$\displaystyle=\Phi_{>k}\tilde{U}Y\tilde{U}^{\top}\Phi_{>k}^{\top},$

and moreover that $Y\succeq 0$ if and only if
$\tilde{U}Y\tilde{U}^{\top}\succeq 0$. Thus $L=F+\Psi_{>k}Y\Psi_{>k}^{\top}$if
and only if $L=F+\Phi_{>k}\tilde{U}Y\tilde{U}^{\top}\Phi_{>k}^{\top}.$ Hence
the set $\operatorname{Sp}_{G}(k)$ is independent of the choice of eigenbasis.
∎

### Proof of Lemma 3.5

Recall that the Laplacian of $K_{n}$ is $L_{K_{n}}=nI_{n}-J_{n}$. If
$\lambda_{2}=\ldots=\lambda_{k}$, then

$\displaystyle
F=\Phi_{k}\Lambda_{k}\Phi_{k}^{\top}+\lambda_{k}\Phi_{>k}\Phi_{>k}^{\top}=\lambda_{2}\sum_{i=2}^{n}\varphi_{i}\varphi_{i}^{\top}=\lambda_{2}(I_{n}-\varphi_{1}\varphi_{1}^{\top})=\lambda_{2}\left(I_{n}-\frac{1}{n}J_{n}\right).$

∎

### Proof of Theorem 4.1

Since a weighted, complete graph $G$ has no missing edges,

$\operatorname{Sp}_{G}(k)=\\{L=\Phi_{k}\Lambda_{k}\Phi_{k}^{\top}+\lambda_{k}\Phi_{>k}\Phi_{>k}^{\top}+\Phi_{>k}Y\Phi_{>k}^{\top}\,:\,L_{st}\leq
0\,\,\forall\,\,s\neq t,\,\,Y\succeq 0\\}.$

No $k-$isospectral subgraph will sparsify if and only if none of the
hyperplanes $L_{st}=0$ intersect the psd cone $\mathcal{S}^{n-k}_{+}$, or
equivalently, $\mathcal{S}^{n-k}_{+}$ lies in the open halfspace $L_{st}<0$
for all $s\neq t$. Recall that $L_{st}\leq 0$ is $\langle
Y,c_{s}c_{t}^{\top}\rangle\leq-F_{st}$ where $c_{i}$ is the $i$th column of
$\Phi_{>k}^{\top}$. Suppose there is some $\bar{Y}\succeq 0$ such that
$\langle\bar{Y},c_{s}c_{t}^{\top}\rangle>0$. Then for a fixed $Y_{0}\succeq 0$
and $\alpha>0$

(32) $\displaystyle\langle
Y_{0}+\alpha\bar{Y},c_{s}c_{t}^{\top}\rangle=c_{s}^{\top}Y_{0}c_{t}+\alpha(c_{s}^{\top}\bar{Y}c_{t})\longrightarrow\infty\textup{
as }\alpha\longrightarrow\infty.$

Therefore, for large enough $\alpha$, the psd matrix $Y_{0}+\alpha\bar{Y}$
violates $L_{st}\leq 0$. This means that $L_{st}\leq 0$ is not valid on all of
$\mathcal{S}^{n-k}_{+}$ and the plane $L_{st}=0$ cuts through
$\mathcal{S}^{n-k}_{+}$.

By the above argument, if $\mathcal{S}^{n-k}_{+}$ lies in the open halfspace
$L_{st}<0$, then it must be that $\langle Y,c_{s}c_{t}^{\top}\rangle\leq 0$
for all $Y\succeq 0$. The polar of the psd cone $\mathcal{S}^{n-k}_{+}$ is the
set of all matrices $X$ such that $\langle Y,X\rangle\geq 0$ for all
$Y\in\mathcal{S}^{n-k}_{+}$. It is well known that the psd cone is the polar
dual of itself, and hence $\langle Y,c_{s}c_{t}^{\top}\rangle\leq 0$ for all
$Y\succeq 0$ if and only if $-c_{s}c_{t}^{\top}$ lies in the polar dual cone,
or equivalently, $-c_{s}c_{t}^{\top}$ is a psd matrix. Since
$-c_{s}c_{t}^{\top}$ is a rank one matrix, it is psd if and only if
$c_{t}=-\beta c_{s}$ for some $\beta\geq 0$. We conclude that if
$\mathcal{S}^{n-k}_{+}$ lies in the open halfspace $L_{st}<0$ for all
$(s,t)\in E$, then there are scalars

(33) $\displaystyle\beta_{st}\geq 0\textup{ such that
}c_{t}=-\beta_{st}c_{s}\,\,\forall\,s\neq t.$

If $k\leq n-2$, then $\Phi_{>k}^{\top}$ has at least two rows and at least one
nonzero column (say $c_{1}$). Since all edges $(1,t)$ are present in $G$, if
$\eqref{eq:needed condn}$ holds, then $c_{2},\ldots,c_{n}$ are nonpositive
multiples of $c_{1}$. This makes the rows of $\Phi_{>k}$ dependent which
contradicts that the rows are part of an eigenbasis.

Therefore, when $k\leq n-2$, some hyperplane $L_{st}=0$ cuts through the psd
cone and in particular, supports $\textup{Sp}_{G}(k)$. Points lying on this
face of $\textup{Sp}_{G}(k)$ are $k-$sparsifiers which miss the edge $(s,t)$.
∎

In the above proof, if $k=n-1$ then $\Phi_{>n-1}=\varphi_{n}$ which has at
least two nonzero entries (say the first and second) since
$\varphi_{n}^{\top}\mathbbm{1}=0$. If it has a third nonzero entry as well
(say the third), then the second and third entries are negative multiples of
the first but then the third is not a negative multiple of the second which
contradicts (33) and we get that some $L_{st}=0$ supports
$\operatorname{Sp}_{G}(k)$ and $G$ has a $(n-1)-$sparisifer.

The requirement that $\varphi_{n}$ has at least three nonzero entries is a
type of genericity condition. Recall from the $K_{5}$ example that if
$\varphi_{n}$ has only two nonzero entries then a $(n-1)-$sparsifier can fail
to exist. In the generic case, we can also give a direct constructive proof
that shows the existence of a $(n-1)-$sparsifier.

######  Proposition 7.1.

Let $G=(V,E,w)$ be a complete graph where every edge has a positive weight. If
the largest eigenvalue $\lambda_{n}$ has an eigenvector $\varphi_{n}$ with at
least three nonzero entries, then there is a $(n-1)-$sparsifier deleting at
least one edge.

###### Proof.

We start by considering the Laplacian $L_{G}=D-A$ of $G$. Since none of the
edge weights vanish, $L_{G}$ has positive entries on the diagonal and negative
entries everywhere else. Our goal is to construct a sparsifier $H$ that
preserves the first $k=n-1$ eigenvectors and eigenvalues. Since the last
eigenvector is isolated, $\lambda_{n}\geq\lambda_{n-1}$, we have very concrete
knowledge of how the Laplacian $L_{H}$ has to look like: the difference
$L_{G}-L_{H}$, interpreted as a linear operator, can only act on the
eigenspace corresponding to $\varphi_{n}$. Thus $L_{H}$ is a rank one
perturbation of $L_{G}$ and, for some constant $c\in\mathbb{R}$

$L_{H}=L_{G}+c(\varphi_{n}\varphi_{n}^{\top}).$

Moreover, we observe that the largest eigenvalue then obeys

$\lambda_{n}(L_{H})=\lambda_{n}(L_{G})+c.$

In particular, this shows that by setting $c\geq 0$ we are guaranteed to
obtain a new Laplacian whose first $n-1$ eigenvalues and eigenvectors coincide
exactly with those of $L_{G}$. It remains to check whether $L_{H}$ corresponds
to a Laplacian of a weighted graph: for this, we require that the matrix is
symmetric, each row sums to zero, and that the off-diagonal entries are all
non-negative. Since the graph is connected, $\varphi_{1}$ is constant. By
orthogonality, this implies that the entries of $\varphi_{n}$ sum to 0.
Moreover, if $\varphi_{n}$ has at least three non-zero coordinates, then there
are at least two with the same sign which gives rise to at least one off-
diagonal entry of the matrix $(\varphi_{n}\varphi_{n}^{\top})$. This shows
that there exists a choice of $c>0$ such that $L_{H}$ has at least one off-
diagonal entry that is zero while all other off-diagonal entries are negative
and leads to an $(n-1)-$sparsifier. ∎

We note that for ‘generic’ weights and ‘generic’ eigenvectors, the above
procedure will typically result in an $(n-1)-$sparsifier that deletes exactly
one edge. Recalling the Linear Algebra Heuristic with $k=n-1$, we see that

$|E|\leq{n\choose 2}-{n-k+1\choose 2}={n\choose 2}-{n-(n-1)+1\choose
2}={n\choose 2}-1,$

and this coincides exactly with the previous proof: one can hope to erase a
single edge but not more than that.

### Proof of Theorem 4.5

We argue by contradiction and assume that there exists a sparsification
$Q_{d}^{\prime}$ of $Q_{d}$ at $k=d+1$. This corresponds to an assignment of
weights to the $d\cdot 2^{d-1}$ edges $e\in E$ of $Q_{d}$ such that at least
one of the edge weights is zero (which corresponds to the vanishing of an
edge). The spectrum and eigenvectors of the Laplacian of $Q_{d}$ are well
studied. The eigenvectors are of the form $\varphi_{s}(v)=(-1)^{s^{\top}v}$
for $s,v\in\\{0,1\\}^{d}$. The eigenvectors $\varphi_{s}$ and $\varphi_{t}$
have the same eigenvalue if and only if
$\mathbbm{1}_{d}^{\top}s=\mathbbm{1}_{d}^{\top}t$. In particular, the
eigenspace for $\lambda_{2}=2$ is spanned by the eigenvectors
$\\{\varphi_{e_{i}}\\}_{i=1}^{d}$. We start by noting that, since the bottom
of the spectrum of $Q_{d}$ is preserved in $Q_{d}^{\prime}$ (both the
eigenvalues and the eigenvectors), we have that for all functions
$f:V\rightarrow\mathbb{R}$ on $Q_{d}^{\prime}$ with mean value 0,

$\frac{\sum_{(i,j)\in E}w_{ij}(f(i)-f(j))^{2}}{\sum_{i\in
V}f(i)^{2}}\geq\lambda_{2}.$

We first show that every single edge weight in $Q_{d}^{\prime}$ has to be at
least $w_{ab}\geq 1$. Suppose $(a,b)$ is an edge of $Q_{d}^{\prime}$ such that
$w_{ab}<1$. Since $a,b\in\\{0,1\\}^{d}$ are adjacent in $Q_{d}$, there is
exactly one coordinate $\ell\in[d]$ for which $a_{\ell}\neq b_{\ell}$. The
eigenvector $\varphi=\varphi_{e_{\ell}}$ has eigenvalue 2 and is such that
$\varphi(a)=(-1)^{a_{\ell}}=(-1)(-1)^{b_{\ell}}=-\varphi(b)$. We may assume
without loss of generality that $\varphi(a)=1$ and so, $\varphi(b)=-1$. We
will now introduce a new function $\psi:V\rightarrow\mathbb{R}$ as follows

$\psi(v)=\begin{cases}1+\varepsilon\qquad&\mbox{if}~{}v=a\\\
-1-\varepsilon\qquad&\mbox{if}~{}v=b\\\
\varphi(v)\qquad&\mbox{otherwise.}\end{cases}$

Then,

$\sum_{i\in V}\psi(v)=0.$

We consider the Rayleigh-Ritz quotient and observe that

$\displaystyle\frac{\sum_{(i,j)\in E}w_{ij}(\psi(i)-\psi(j))^{2}}{\sum_{i\in
V}\psi(i)^{2}}$ $\displaystyle=\frac{\sum_{(i,j)\in
E}w_{ij}(\psi(i)-\psi(j))^{2}}{4\varepsilon+2\varepsilon^{2}+2^{d}}.$

To analyze the numerator, we split the sum into four different sums: (1) the
edge $(a,b)$, (2) the other edges incident to $a$, (3) the other edges
incident to $b$ and (4) edges incident to neither $a$ nor $b$. We obtain

$\displaystyle\sum_{(i,j)\in E}w_{ij}(\psi(i)-\psi(vj)^{2}$
$\displaystyle=w_{ab}(\psi(a)-\psi(b))^{2}+\sum_{(i,j)\in E\atop{i,j\neq
a,b}}w_{ij}(\psi(i)-\psi(j))^{2}$ $\displaystyle+\sum_{(a,j)\in E\atop{j\neq
b}}w_{aj}(\psi(a)-\psi(j))^{2}+\sum_{(b,j)\in E\atop{j\neq
a}}w_{bj}(\psi(b)-\psi(j))^{2}.$

The first term is simple:

$\displaystyle w_{ab}(\psi(a)-\psi(b))^{2}$
$\displaystyle=w_{ab}(2+2\varepsilon)^{2}$
$\displaystyle=4w_{ab}+8w_{ab}\varepsilon+4w_{ab}\varepsilon^{2}$
$\displaystyle=w_{ab}(\varphi(a)-\varphi(b))^{2}+8w_{ab}\varepsilon+4w_{ab}\varepsilon^{2}.$

The second sum is also easy to analyze: the edges are not incident to $a$ or
$b$ and thus the function $\psi$ coincides with the function $\varphi$ for all
terms and

$\sum_{(i,j)\in E\atop{i,j\neq a,b}}w_{ij}(\psi(i)-\psi(j))^{2}=\sum_{(i,j)\in
E\atop{i,j\neq a,b}}w_{ij}(\varphi(i)-\varphi(j))^{2}.$

For an edge $(a,j)$ where $j\neq b$, since $a$ and $j$ do not differ in the
$\ell$-th coordinate, we have that $\psi(j)=\varphi(j)=\varphi(a)=1$.
Therefore,

$\displaystyle\sum_{(a,j)\in E\atop{j\neq b}}w_{aj}(\psi(a)-\psi(j))^{2}$
$\displaystyle=\sum_{(a,j)\in E\atop{j\neq
b}}w_{aj}\varepsilon^{2}=\varepsilon^{2}\sum_{(a,j)\in E\atop{j\neq b}}w_{aj}$

and, via the same reasoning

$\displaystyle\sum_{(b,j)\in E\atop{j\neq
a}}w_{bj}(\psi(b)-\psi(j))^{2}=\varepsilon^{2}\sum_{(b,j)\in E\atop{j\neq
a}}w_{bj}.$

Therefore,

$\displaystyle\sum_{(i,j)\in E}w_{ij}(\psi(i)-\psi(j))^{2}$
$\displaystyle=\sum_{(i,j)\in E}w_{ij}(\varphi(i)-\varphi(j))^{2}$
$\displaystyle+8\omega_{ab}\varepsilon+4\omega_{ab}\varepsilon^{2}$
$\displaystyle+\varepsilon^{2}\left(\sum_{(a,j)\in E}w_{aj}+\sum_{(b,j)\in
E}w_{bj}\right),$

Note that the first sum on the right of the equal sign is over all edges in
$E$. Indeed, the second sum from the four sums above accounts for all edges
not adjacent to $a$ or $b$. The term $w_{ab}(\varphi(a)-\varphi(b))^{2}$ from
the first of the four sums contributes the edge $(a,b)$. Further, since
$\varphi(a)=\varphi(j)$ when $(a,j)\in E$ and $j\neq b$, there is no harm in
adding the sum of terms $w_{aj}(\varphi(a)-\varphi(j))^{2}$ for all $(a,j)\in
E,\,j\neq b$, and similarly, also the sum of the terms
$w_{bj}(\varphi(b)-\varphi(j))^{2}$ for all $(b,j)\in E,\,j\neq a$. Therefore,

$\frac{\sum_{(i,j)\in E}w_{ij}(\psi(i)-\psi(j))^{2}}{\sum_{i\in
V}\psi(i)^{2}}=\frac{8w_{ab}\varepsilon+\mathcal{O}(\varepsilon^{2})+\sum_{(i,j)\in
E}w_{ij}(\varphi(i)-\varphi(j))^{2}}{4\varepsilon+\mathcal{O}(\varepsilon^{2})+\sum_{i\in
V}\varphi(i)^{2}}$

Since $\varphi$ assumes values in $\left\\{-1,1\right\\}$ and corresponds to
eigenvalue 2, we have

$\sum_{i\in V}\varphi(i)^{2}=2^{d}\quad\mbox{and}\quad\sum_{(i,j)\in
E}w_{ij}(\varphi(i)-\varphi(j))^{2}=2^{d+1}.$

Thus,

$\frac{\sum_{(i,j)\in E}w_{ij}(\psi(i)-\psi(j))^{2}}{\sum_{i\in
V}\psi(i)^{2}}=\frac{2^{d+1}+8w_{ab}\varepsilon+\mathcal{O}(\varepsilon^{2})}{2^{d}+4\varepsilon+\mathcal{O}(\varepsilon^{2})}.$

Differentiating the expression on the right in $\varepsilon$ at
$\varepsilon=0$, we obtain

$\frac{d}{d\varepsilon}\quad\frac{2^{d+1}+8w_{ab}\varepsilon+\mathcal{O}(\varepsilon^{2})}{2^{d}+4\varepsilon+\mathcal{O}(\varepsilon^{2})}\bigg{|}_{\varepsilon=0}=-\frac{8(1-w_{ab})}{2^{d}}<0.$

This shows that, for $\varepsilon>0$ sufficiently small,

$\frac{\sum_{(i,j)\in E}w_{ij}(\psi(i)-\psi(j))^{2}}{\sum_{i\in
V}\psi(i)^{2}}<\lambda_{2}$

which contradicts the Courant-Fischer theorem. Thus $w_{ab}\geq 1$ for all
edges.

Suppose now $w_{ab}>1$ for some $(a,b)\in E$. Letting $\ell$ be the coordinate
on which $a$ and $b$ differ, the eigenvector $\varphi=\varphi_{e_{\ell}}$ of
$\lambda_{2}$ which has $\varphi(a)=-\varphi(b)$ shows that

$2=\lambda_{2}=\frac{\sum_{(i,j)\in
E}w_{ij}(\varphi(i)-\varphi(j))^{2}}{\sum_{i\in
V}\varphi(i)^{2}}>\frac{\sum_{(i,j)\in
E}(\varphi(i)-\varphi(j))^{2}}{\sum_{i\in V}\varphi(i)^{2}}=2$

which is a contradiction. Therefore all the weights are necessarily
$w_{ab}=1$. ∎

### Proof of Theorem 4.3

We will construct these graphs from a specifically chosen spectrum, which we
show in Table 2.

distinct eigenvalues | eigenspaces
---|---
$\lambda_{1}=0$ | $\Lambda_{1}=\operatorname{span}\\{\varphi_{1}^{\prime}=\mathbbm{1}\\}$
$\lambda_{2}=n$ | $\operatorname{span}\\{\varphi_{1}^{\prime},\varphi_{n-1}^{\prime},\varphi_{n}^{\prime}\\}^{\perp}$
$\lambda_{n-1}=3n$ | $\Lambda_{n-1}=\operatorname{span}\\{\varphi_{n-1}^{\prime}=e_{n-1}-e_{n}\\}$
$\lambda_{n}=7n+6$ | $\Lambda_{n}=\operatorname{span}\\{\varphi_{n}^{\prime}=(0,\ldots,0,2,-1,-1)\\}$
Table 2. The spectrum of a weighted graph with $n$ vertices that has no
$(n-2)-$sparsifier.

Let $\\{\varphi_{i}\\}$ be an orthonormal basis chosen from these eigenspaces
with $\varphi_{1},\varphi_{n-1},\varphi_{n}$ being the normalized
$\varphi_{1}^{\prime},\varphi_{n-1}^{\prime},\varphi_{n}^{\prime}$, and let
$\Lambda=\operatorname{diag}(0\,,\,n\mathbbm{1}^{\top}_{n-3}\,,\,3n\,,\,7n+6).$
The resulting matrix $\Phi\Lambda\Phi^{\top}=L_{G}$ defines the graph
$G=([n],E,w)$ with edge weights

$w_{ij}=\begin{cases}1&i\in[n-3],j>i\\\ 2n+3&i=n-2,j=n-1,n\\\
0&i=n-1,j=n\end{cases}.$

See Figure 10 for a depiction of the graph when $n=4.$ Because
$\lambda_{2}=\ldots=\lambda_{n-2},$ by Lemma 3.5, Laplacians in
$\operatorname{Sp}_{G}(n-2)$ have the form

$nI_{n}-J_{n}+\Phi_{>n-2}Y\Phi_{>n-2}^{\top},\,\,Y\succeq 0.$

Letting $Y=\begin{bmatrix}a&b\\\ b&c\end{bmatrix}$, we see that

$(\Phi_{>n-2}Y\Phi_{>n-2}^{\top})_{ij}=\begin{cases}0&i\in[n-3],j\in[n]\\\
b/\sqrt{3}-c/3&i=n-2,j=n-1\\\ -b/\sqrt{3}-c/3&i=n-2,j=n\\\
c/6-a/2&i=n-1,j=n\end{cases}.$

Most entries of this matrix are zero due to the structure of $\varphi_{n-1}$
and $\varphi_{n}$; only three edges of the graph have flexibility. Because
$(n-1,n)\not\in E(G)$, we must have that

$(L_{G})_{n-1,n}=(nI_{n}-J_{n}+\Phi_{>n-2}Y\Phi_{>n-2}^{\top})_{n-1,n}=0,$

which is to say $-1+c/6-a/2=0.$ Thus we can write

$Y=\begin{bmatrix}c/3-2&b\\\ b&c\end{bmatrix}.$

The psd constraints on $Y$ are then

$c\geq 6,\quad|b|\leq\sqrt{c^{2}/3-2c}.$

The remaining two edge inequalities defining the sparsifier set from edges
$(n-2,n-1)$ and $(n-2,n)$ respectively are

$-1-b/\sqrt{3}-c/3\leq 0,\,\qquad-1+b/\sqrt{3}-c/3\leq 0.$

We can consolidate these as $|b|\leq\sqrt{3}+c/\sqrt{3}$. Thus the psd
constraints on $Y$ are strictly contained in the polyhedron defined by the
edge inequalities:

$\displaystyle|b|\leq\sqrt{c^{2}/3-2c}\text{ and }c\geq 0$
$\displaystyle\implies|b|\leq c/\sqrt{3}\implies|c|<c/\sqrt{3}+\sqrt{3}.$

Therefore no edge can be deleted by a psd choice of $Y$. We note that while
these graphs have no $(n-2)-$sparsifiers, the set of $(n-2)-$isospectral
graphs is not a point – even more than that, it is full dimensional and
unbounded. Any matrix $Y$ satisfying the psd constraints provides a valid
$(n-2)-$isospectral graph.

Figure 17. The valid $(b,c)$ for $(n-2)-$isospectral graphs of the graph
family in Theorem 4.3 are in orange. The yellow region is the polyhedron
defined by the edge inequalities, and the orange region is defined by the psd
constraints on $Y$. Because these regions are strictly nested, these graphs
cannot lose any edges.

∎

We note that the choice $\lambda_{2}=\ldots=\lambda_{n-2}$ in the above proof
serves only to make the argument cleaner. There are likely many choices of
eigenvalues and eigenvectors for which a similar construction produces a graph
that does not sparsify.

### Proof of Theorem 4.4

We can assume the missing edge is $(n-1,n)$. This graph has three eigenspaces.
The first two eigenpairs are $(0,\mathbbm{1})$, $(n-2,e_{n-1}-e_{n}),$ and the
eigenspace for $\lambda=n$ is spanned by the eigenvectors

$\\{e_{1}-e_{j}\\}_{j=2}^{n-2}\cup\\{\mathbbm{1}_{n}-n(e_{n-1}+e_{n})/2\\}.$

Let $\Phi$ be any orthonormal eigenbasis of $L_{G}$ so that
$\varphi_{n}=(\mathbbm{1}_{n}-ne_{n-2})/\sqrt{n(n-1)}$. (This is a convenient
choice for $\varphi_{n}$, different from the ones listed. Check that it is an
eigenvector with eigenvalue $n$.) Then, the Laplacians in
$\operatorname{Sp}_{G}(2)$ look like

$L=(n-2)(I_{n}-J_{n}/n)+\Phi_{>2}Y\Phi_{>2}^{\top}$

where $Y\succeq 0$. Restricting our attention to matrices $Y$ of the form
$\operatorname{diag}(0,\ldots,0,y)$, we get Laplacians of the form

$L=(n-2)(I_{n}-J_{n}/n)+y\varphi_{n}\varphi_{n}^{\top}:\,\,y\geq 0$

The condition $L_{n-1,n}=0$ implies that
$(y\varphi_{n}\varphi_{n}^{\top})_{n-1,n}=y/(n(n-1))=(n-2)/n,$ that is,
$y=(n-2)(n-1).$ Plugging this in, we get the Laplacian of the star graph
$K_{1,n}$ with equal edge weights $n-2$, where the center of the star is the
vertex $n-2$. This choice of central vertex is not special – to place vertex
$j\in[n-2]$ at the center of the star, set
$\varphi_{n}=(\mathbbm{1}_{n}-ne_{j})/\sqrt{n(n-1)}$. ∎

### Proof of Theorem 5.1

By Corollary 3.2, it suffices to show that the result holds for $k=n-1$.
Consider a fixed orthonormal basis of ${\mathbb{R}}^{n}$ where
$\varphi_{1}=\mathbbm{1}/\sqrt{n}$ and the last eigenvector is
$\varphi_{n}=(-\mathbbm{1}_{n-1},n-1)/\sqrt{n(n-1)}$. By Lemma 3.5,

$\displaystyle\textup{Sp}_{K_{n}}(n-1)=\left\\{L=nI-
J_{n}+y\varphi_{n}\varphi_{n}^{\top}:y\geq 0,L_{st}\leq 0\,\,\forall\,\,s\neq
t\right\\}.$

Additionally,

$\varphi_{n}\varphi_{n}^{\top}=\frac{1}{n(n-1)}\begin{bmatrix}J_{n-1}&(1-n)\mathbbm{1}_{n-1}\\\
(1-n)\mathbbm{1}_{n-1}^{\top}&(n-1)^{2}\end{bmatrix}.$

For $s<t$ we see that

$L_{st}=\begin{cases}-1+y/(n(n-1))&t\leq n-1\\\ -1-y/n&t=n\end{cases}.$

The conditions $L_{st}\leq 0$ and $y\geq 0$ imply that $0\leq y\leq n(n-1)$.
Therefore we can simplify again:

$\displaystyle\textup{Sp}_{K_{n}}(n-1)=\left\\{nI-J+y\varphi_{n}\varphi_{n}^{\top}:0\leq
y\leq n(n-1)\right\\}.$

Choosing $y=n(n-1)$ produces the Laplacian

$L=\begin{bmatrix}nI_{n-1}&-n\mathbbm{1}_{n-1}\\\
-n\mathbbm{1}_{n-1}^{\top}&n(n-1)\end{bmatrix}.$

This corresponds to the star graph where the vertex $n$ is at the center, and
every edge has weight $n$. There is nothing special about the choice of vertex
$n$ as the center of the star, by relabeling the vertices any vertex can be
made the center. ∎

### Proof of Theorem 5.2

We start by recording the eigenvalues and an eigenbasis of the wheel graph in
Table 3, which are well understood from the formulation of $W_{n+1}$ as a cone
over the cycle $C_{n}$ [8, 21]. We use the following notation for the
nontrivial eigenvectors of $C_{n}$ arising from the representations of
${\mathbb{Z}}/n$, $j\in[\lfloor(n-1)/2\rfloor]$.

$\varphi_{j}:=\begin{bmatrix}1\\\ \cos(2\pi j/n)\\\ \vdots\\\
\cos(2\pi(n-1)j/n)\end{bmatrix},\psi_{j}:=\begin{bmatrix}0\\\ \sin(2\pi
j/n)\\\ \sin(2\pi 2j/n)\\\ \vdots\\\ \sin(2\pi(n-1)j/n)\end{bmatrix}.$

Eigenvalue | Multiplicity | Eigenvectors
---|---|---
0 | 1 | $\mathbbm{1}_{n+1}$
$\lambda_{j}=3-2\cos(2\pi j/n)$ | $2^{*}$ | $[\varphi_{j},0],[\psi_{j},0]$
$n+1$ | 1 | $[-\mathbbm{1}_{n},n]$
Table 3. The spectrum of $W_{n+1}$, where $j=2,\ldots,\lfloor(n-1)/2\rfloor$.
∗If $n$ is even, $\lambda_{n/2}$ has multiplicity 1 because
$\varphi_{n/2}=-\psi_{n/2}$. Here the index $j$ reflects an ordering natural
to the cycle rather than by increasing eigenvalue.

We can also write the Laplacian of $W_{n+1}$ in terms of that of $C_{n}$.

$L_{W_{n+1}}=\left(\begin{array}[]{@{}c|c@{}}\begin{matrix}3&-1&0&\ldots&0&-1\\\
-1&3&-1&0&\ldots&0\\\ &\ddots&\ddots&\ddots&\ddots\\\
-1&0&\ldots&0&-1&3\end{matrix}&\begin{matrix}-\mathbbm{1}_{n}\end{matrix}\\\
\hline\cr\begin{matrix}-\mathbbm{1}_{n}^{\top}\end{matrix}&\begin{matrix}n\end{matrix}\end{array}\right)=\left(\begin{array}[]{@{}c|c@{}}L_{C_{n}}+I_{n}&-\mathbbm{1}_{n}\\\
\hline\cr-\mathbbm{1}_{n}^{\top}&n\end{array}\right),$

Let $\Phi$ be any orthonormal eigenbasis of $L_{W_{n+1}}$, let
$\lambda=3-2\cos(2\pi/n)$, and let

$\Lambda^{\prime}=\operatorname{diag}(0,\mathbbm{1}_{n-1}^{\top},n+1)$. We
will show that

$L=\lambda\Phi\Lambda^{\prime}\Phi^{\top}\in\textup{Sp}_{W_{n+1}}(3),$

and moreover that $L=\lambda L_{K_{1,n}}$ is the Laplacian of the claimed
spanning tree. By construction, the first three eigenpairs of $L$ are
$(0,\varphi_{1}),(\lambda,\varphi_{2}),(\lambda,\varphi_{3})$ – this agrees
with the first three eigenpairs of $L_{W_{n+1}}$. All other eigenvalues of $L$
are $\lambda$ or $\lambda n$, which are both at least $\lambda$. Taking
$\Lambda$ to be the matrix of eigenvalues of $L_{W_{n+1}}$,

$\displaystyle\Phi\Lambda^{\prime}\Phi^{\top}$
$\displaystyle=\Phi\Lambda\Phi^{\top}-\Phi\left(\Lambda-\Lambda^{\prime}\right)\Phi^{\top}$
$\displaystyle=L_{W_{n+1}}-\Phi\operatorname{diag}(0,\lambda_{2}-1,\ldots,\lambda_{n}-1,0)\Phi^{\top}$
$\displaystyle=L_{W_{n+1}}-\left(\begin{array}[]{@{}c|c@{}}L_{C_{n}}&\bf{0}\\\
\hline\cr\bf{0}^{\top}&0\end{array}\right)=\left(\begin{array}[]{@{}c|c@{}}I_{n}&-\mathbbm{1}_{n}\\\
\hline\cr-\mathbbm{1}_{n}^{\top}&n\end{array}\right)=L_{K_{1,n}}.$

So we see that $L=\lambda L_{K_{1,n}}$, which satisfies all the constraints
$L_{st}\leq 0$ for $s\neq t$, $L_{st}=0$ for $st\notin E(W_{n+1})$. Thus, $L$
defines a $3-$sparsifier of $L_{W_{n+1}}$. ∎

### Proof of Theorem 5.3

It is clear from the variational characterization and the quadratic form

$\left\langle f,L_{G}f\right\rangle=\sum_{(u,v)\in E}w_{uv}(f(u)-f(v))^{2}$

that removing edges cannot increase any eigenvalue. We will now prove the
statement for $k=2$, the general argument is then identical via Rayleigh-Ritz
and the variational characterization. We can therefore remove edges until we
arrive at the spanning tree and compute its first non-trivial eigenvector
$\varphi_{2}$. If it is now the case that for all edges in $(u,v)\in
E\setminus E_{T}$ that $\varphi_{2}(u)=\varphi_{2}(v)$, then it means that
adding these edges back in does not change the value of the quadratic form.
This shows that $\varphi_{2}$ is also an eigenvector on $G$ corresponding to
the same eigenvalue as on the tree since it minimizes the quadratic form. This
proves that the tree is a $k=2$ sparsifier for the choice of basis of
eigenspaces given by $\left\\{\mathbbm{1},\varphi_{2}\right\\}$. In general,
we may now repeat the same argument for any $k$ and the result follows. ∎

### Proof of Lemma 6.2

Suppose $\Lambda=\textup{span}\\{\varphi_{1},\ldots,\varphi_{k}\\}$. Then
$x\in\Lambda$ implies that $x=\sum_{j=1}^{k}\beta_{j}\varphi_{j}$ for
$\beta_{j}\in{\mathbb{R}}$. Therefore,

(34) $\displaystyle
xx^{\top}=(\sum_{j=1}^{k}\beta_{j}\varphi_{j})(\sum_{j=1}^{k}\beta_{j}\varphi_{j}^{\top})=\sum\beta_{i}^{2}\varphi_{i}\varphi_{i}^{\top}+\sum_{i\neq
j}\beta_{i}\beta_{j}(\varphi_{i}\varphi_{j}^{\top}+\varphi_{j}\varphi_{i}^{\top}).$

Set $s_{ii}:=\langle A,\varphi_{i}\varphi_{i}^{\top}\rangle\geq 0$ and
$s_{ij}=\langle
A,\varphi_{i}\varphi_{j}^{\top}+\varphi_{j}\varphi_{i}^{\top}\rangle\in{\mathbb{R}}$.
These are constants that we can compute from $A$ and a basis of $\Lambda$.
Then

(35) $\displaystyle x^{\top}Ax$ $\displaystyle=\langle
A,xx^{\top}\rangle=\sum\beta_{i}^{2}\langle
A,\varphi_{i}\varphi_{i}^{\top}\rangle+\sum_{i\neq j}\beta_{i}\beta_{j}\langle
A,\varphi_{i}\varphi_{j}^{\top}+\varphi_{j}\varphi_{i}^{\top}\rangle$ (36)
$\displaystyle=\sum\beta_{i}^{2}s_{ii}+\sum_{i\neq
j}\beta_{i}\beta_{j}s_{ij}.$

Setting $y_{ii}:=\langle B,\varphi_{i}\varphi_{i}^{\top}\rangle$ and
$y_{ij}=\langle
B,\varphi_{i}\varphi_{j}^{\top}+\varphi_{j}\varphi_{i}^{\top}\rangle\in{\mathbb{R}}$
we have

$\displaystyle S_{A}(\Lambda)=$ $\displaystyle\left\\{B\succeq
0\,:\,Q_{A}(x)=Q_{B}(x)\,\,\forall\,\,x\in\Lambda\right\\}$ $\displaystyle=$
$\displaystyle\left\\{B\succeq 0\,:\,\langle A,xx^{\top}\rangle=\langle
B,xx^{\top}\rangle\,\,\forall\,\,x\in\Lambda\right\\}$ $\displaystyle=$
$\displaystyle\left\\{B\succeq 0\,:\,\sum\beta_{i}^{2}s_{ii}+\sum_{i\neq
j}\beta_{i}\beta_{j}s_{ij}=\sum\beta_{i}^{2}y_{ii}+\sum_{i\neq
j}\beta_{i}\beta_{j}y_{ij}\,\,\forall\,\,\beta\in{\mathbb{R}}^{k}\right\\}$
$\displaystyle=$ $\displaystyle\left\\{B\succeq
0\,:\,y_{ii}=s_{ii},y_{ij}=s_{ij}\right\\}$ $\displaystyle=$
$\displaystyle\left\\{B\succeq 0\,:\,\langle
B,\varphi_{i}\varphi_{i}^{\top}\rangle=s_{ii},\langle
B,\varphi_{i}\varphi_{j}^{\top}+\varphi_{j}\varphi_{i}^{\top}\rangle=s_{ij}\right\\}.$

∎

### Proof of Theorem 6.4

For any point $w\in{\mathbb{R}}^{E}_{\geq 0}$, $L_{G}(w)$ is the Laplacian of
a subgraph $\tilde{G}$ of $G$ by the definition of $L_{G}({\tt{w}})$. In
particular, it is already psd and has the edge sparsity of $G$ built in.
Therefore all points in $P^{Q(x)}_{G}(k)$ are $Q_{k}(x)-$sparsifiers of $G$.
The faces of $P^{Q(x)}_{G}(k)$ correspond to a collection of inequalities
$w_{i}\geq 0$ holding at equality. Therefore, the sparsest sparsifiers lie on
the smallest dimensional faces of $P^{Q(x)}_{G}(k)$. It could be that some of
the graphs on the boundary of $P^{Q(x)}_{G}(k)$ are disconnected but they
still satisfy the needed conditions on the quadratic form. Connected subgraphs
of $G$ must have Laplacians of rank $n-1$, and $\det(L^{\prime}_{G}(w))=0$ if
and only if $\operatorname{rank}(L_{G}(w))<n-1$. Since $L^{\prime}_{G}(w)$ is
a principal minor of $L_{G}(w)$, and $L_{G}(w)\succeq 0$ for all $w$ in the
polyhedron $P^{Q(x)}_{G}(k)$, it must be that the polyhedron satisfies
$\det(L_{G}^{\prime}(w))\geq 0$. ∎

##  8\. Conclusion

We conclude with a number of final remarks, comments and observations.

A Dynamical Systems Motivation. Instead of considering a graph, one could
think about the behavior of dynamical systems on graphs. A particularly
natural example is the behavior of the heat equation: given a temperature
$f:V\rightarrow\mathbb{R}$, one would naturally ask that vertices that are
surrounded by warmer vertices should heat up while vertices surrounded by
colder vertices should get colder. This suggests that the temperature
$u:[0,\infty]\times V\rightarrow\mathbb{R}$ is initially given by the function
$f$, meaning $u(0,v)=f(v)$ and, at time $t$, satisfies

$\frac{\partial u}{\partial t}(v)=\sum_{(v,w)\in E}w_{vw}\cdot(u(t,w)-u(t,v))$

which can be concisely written as $\partial_{t}u=-(D-A)u$ or $u_{t}=-Lu$. We
also note since every edge is summed over twice, we have $\sum_{v\in
V}u(t,v)=\sum_{v\in V}u(0,v)$ and the total amount of caloric energy in the
graph remains constant. Since $L$ is diagonalizable, we deduce that if

$u(0,x)=\sum_{i=1}^{n}a_{i}\varphi_{i}\qquad\mbox{then}\qquad
u(t,x)=\sum_{i=1}^{n}a_{i}e^{-\lambda_{i}t}\varphi_{i}$

which can be observed by noting that $e^{-\lambda_{i}t}\varphi_{i}$ is a
solution when the initial condition is given by $\varphi_{i}$. The general
case then follows from linearity. Since the exponential decay is larger for
larger eigenvalues, we see that the behavior of $u(t,x)$ for large values of
$t$ is, to leading order, well-approximated by

$u(t,x)=\sum_{i=1}^{n}a_{i}e^{-\lambda_{i}t}\varphi_{i}\sim\sum_{i\leq
k}a_{i}e^{-\lambda_{i}t}\varphi_{i}$

with an error at scale $\sim\exp(-\lambda_{k+1}\cdot t)$. In light of this,
one can motivate the graph sparsification as one that preserves the long-time
behavior of the heat equation as accurately as possible.

A Cheeger Inequality Motivation. Cheeger’s inequality [9] shows that the
eigenvalue $\lambda_{2}$ (the ‘algebraic connectivity’) gives bounds on how
easily the graph can be decomposed into two graphs with relatively few edges
running between them. This can be seen as an extension of the basic algebraic
fact that $\lambda_{2}=0$ if and only if $G$ is comprised of at least two
disjoint graphs. Pushing the analogy, we know that $\lambda_{m}=0$ if and only
if $G$ is comprised of at least $m$ mutually disconnected graphs. One could
now naturally wonder whether $\lambda_{m}$ can say anything about how easy or
hard it is to decompose a graph into $m$ clusters with relatively few edges
running between them. Results of this type have indeed recently been obtained,
we refer to [15, 18, 19, 20]. It is an immediate consequence of our
sparsification approach that the number of connected components remains
preserved once $k>m$.

A Diffusion Map Interpretation. Laplacian eigenvectors of graphs have proven
tremendously useful in obtaining low-dimensional embeddings
$\varphi:V\rightarrow\mathbb{R}^{d}$ that reflect the overall structure of the
graph. Famous methods of this type are Laplacian eigenmaps [6] or diffusion
maps [12]. By the nature of our sparsification, the sparsifiers share the same
low-dimensional embeddings. These mappings have been used successfully in
dimensionality reduction exactly because these lower-dimensional embeddings
tend to capture important information contained in the low-frequency part of
the spectrum of the Laplacian. This could also be seen as an alternative
(equivalent) motivation for our sparsification ansatz.

Spectrally Extremal Examples. Theorem 4.5 completely resolved the case of the
cube $\left\\{0,1\right\\}^{d}$ and shows a very natural type of stability
result: the first two eigenvalues (and the $(d+1)$-dimensional associated
eigenspaces) fix the cube completely. This is particularly satisfying insofar
as one would not expect there to be any particular canonical subgraph that
shares many of the same properties and symmetries: the cube graph is already
perfect just the way it is. It would be interesting to see whether similar
results exist for other families of graphs that arise in a similar fashion, in
particular the example of Cayley graphs.

Preserving other Laplacians. Throughout the paper, our goal was to preserve
the low frequency eigenvalues and eigenvectors of the Kirchhoff Laplacian
$L=D-A$. However, there are several other notions of Graph Laplacian that have
a number of different properties, examples being $I-D^{-1/2}AD^{-1/2}$ and
$I-AD^{-1}$. They preserve different types of properties and emphasize a
somewhat different aspect of graph geometry. The Laplacian $I-AD^{-1}$, for
example, is intimately connected to the behavior of the random walk and
sparsifying while preserving the low-frequency spectrum of $I-AD^{-1}$ would
lead to another way of preserving the local geometry. In these examples edge
weights enter nonlinearly into the Laplacian while entering linearly into
$L=D-A$. As such it is reasonable to assume that the case $L=D-A$ is somewhat
distinguished and perhaps allows for the most complete analysis. Nonetheless,
it would be interesting to see whether the main idea that underlies our ansatz
could be carried out in other, more nonlinear, settings.

Approximate Preservation. The main philosophy that underlies our approach to
sparsification is that small eigenvalues and eigenvectors encapsulate the
overall global structure of a graph which suggests preserving them while
making the graph more sparse. While there are some results of a purely
algebraic nature, many of the results like Cheeger’s inequality and statements
of this nature, are continuous in the underlying parameters. This suggests
that it would be quite feasible to preserve low frequency eigenvalues and
eigenvectors approximately, although we don’t develop it in this paper.

Acknowledgments. S.S. is supported by the NSF (DMS-2123224) and the Alfred P.
Sloan Foundation. R.T. is supported by the Walker Family Endowed Professorship
at the University of Washington. C.B. was supported by the NSF (DMS-1929284)
while in residence at ICERM in Providence, RI, during the Discrete
Optimization Semester program. We thank Nikhil Srivastava for an inspiring
conversation at the 2023 Joint Math Meetings.

## References

  * [1] C. Babecki, Codes, cubes, and graphical designs. Journal of Fourier Analysis and Applications 27, no. 5 (2021), 1–34.
  * [2] C. Babecki and D. Shiroma, Eigenpolyope Universality and Graphical Designs, arXiv:2209.06349
  * [3] C. Babecki and R. Thomas, Graphical designs and Gale duality. Math. Programming (2022).
  * [4] J. Batson, D. Spielman and N. Srivastava, Twice-Ramanujan sparsifiers. In Proceedings of the forty-first annual ACM symposium on Theory of computing (2009), 255–262.
  * [5] J. Batson, D. Spielman, N. Srivastava and S.-H. Teng. Spectral sparsification of graphs: theory and algorithms. Communications of the ACM 56, no. 8 (2013), 87–94.
  * [6] M. Belkin and P. Niyogi, Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation 15 (2003), 1373–1396.
  * [7] R. Bhattacharjee, G. Dexter, C. Musco, A. Ray and D. P. Woodruff, Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra. arXiv:2305.05826.
  * [8] A. E. Brouwer and W. H. Haemers, Spectra of Graphs. Springer, New York, 2012.
  * [9] J. Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, Proc. of Princeton Conf. in Honor of Prof. S. Bochner (1969) 195–199.
  * [10] X. Cheng, G. Mishne and S. Steinerberger, The Geometry of Nodal Sets and Outlier Detection, Journal of Number Theory 185 (2018), 48–64.
  * [11] X. Cheng, M. Rachh and S. Steinerberger, On the Diffusion Geometry of Graph Laplacians and Applications, Appl. Comp. Harm. Anal., 46 (2019), 674–688.
  * [12] R. Coifman and S. Lafon, Diffusion maps. Applied and computational harmonic analysis, 21 (2006), 5–30.
  * [13] M. K. De Carli Silva, N. Harvey and C. M. Sato. Sparse sums of positive semidefinite matrices. ACM Transactions on Algorithms (TALG) 12, no. 1 (2015), 1–17.
  * [14] A. DePavia and S. Steinerberger, Spectral Clustering Revisited: Information Hidden in the Fiedler Vector, Foundations of Data Science 3 (2021), 225–249.
  * [15] T. Dey, P. Peng, A. Rossi and A. Sidiropoulos, Spectral concentration and greedy k-clustering. Comput. Geom. 76 (2019), 19–32.
  * [16] K. Golubev, Graphical designs and extremal combinatorics, Linear Algebra and its Applications 604 (2020), 490–506.
  * [17] S. Hoory, N. Linial and A. Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. 43:4 (2006), 439–561.
  * [18] T. Kwok, L.C. Lau and Y. T. Lee, Improved Cheeger’s inequality and analysis of local graph partitioning using vertex expansion and expansion profile, SIAM J. Comput. 46 (3) (2017), 890–910.
  * [19] J. Lee, S. Oveis Gharan and L. Trevisan, Multi-way spectral partitioning and higher-order Cheeger inequalities. STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing, 1117–1130, ACM, New York, 2012.
  * [20] S. Liu, Multi-way dual Cheeger constants and spectral bounds of graphs. Adv. Math. 268 (2015), 306–338.
  * [21] R. Merris, Laplacian graph eigenvectors. Linear Algebra Appl. 278 (1998), 221–236.
  * [22] D. Spielman and S.-H. Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. Proceedings of the thirty-sixth annual ACM Symposium on Theory of Computing. 2004.
  * [23] D. Spielman and S.-H. Teng, Spectral sparsification of graphs. SIAM Journal on Computing, 40 (2011), 981–1025.
  * [24] S. Steinerberger, Generalized designs on graphs: sampling, spectra, symmetries. Journal of Graph Theory, 93 (2020), 253–267.
  * [25] S. Steinerberger, Spectral limitations of quadrature rules and generalized spherical designs. International Mathematics Research Notices (2021), 12265–12280
  * [26] S. Steinerberger, The product of two high-frequency Graph Laplacian eigenfunctions is smooth, Discrete Mathematics 346, no. 3 (2023), 113246.
  * [27] U. von Luxburg, A tutorial on spectral clustering. Stat. Comput. 17, no.4 (2007), 395–416.