A Theory of Spectral CSP Sparsification

Graph sparsification has emerged as a key topic in algorithmic graph theory. First proposed in the works of Karger [14] and Benczùr and Karger [5], graph sparsification takes as input a graph $G=(V,E)$ and a parameter $\epsilon \in (0,1)$, and returns a reweighted sub-graph $G^{\prime }$ such that the size of every cut in $G$ is simultaneously preserved to a $(1\pm \epsilon )$ multiplicative factor in $G^{\prime }$. Although the algorithm presented in [5] is nearly-optimal for cut sparsification, these works spurred a flurry of research in sparsification in many different directions: for instance, the design of deterministic algorithms for graph sparsification [4], generalizing notions of sparsification to hypergraphs [17, 8, 12] and to norms [9], to CSPs [17, 15], and to arbitrary sets of vectors [6]. Along the way, one of the core advances in the study of sparsification has been the notion of a spectral sparsifier [23]. Here, instead of only preserving the cut-sizes of a graph, the sparsifier instead preserves the energy of the graph, which is defined for a graph $G=(V,E)$, and a vector $x\in {[0,1]}^V$ as $Q_G(x)={\sum }_{e=(u,v)\in E}{w}_e\cdot {(x_u-x_v)}^2$. Specifically, a spectral sparsifier is a re-weighted subgraph $G^{\prime }$ such that for every $x\in {[0,1]}^V$, it is the case that $Q_{G^{\prime }}(x)\in (1\pm \epsilon )Q_G(x)$. This energy can be written as a quadratic form involving the graph’s (un-normalized) Laplacian, which is denoted by $L_G$, and satisfies ${(L_G)}_{i,j}=\{\begin{array}{cc}\mathrm{deg}(i)\text{if }i=j\hfill & \\ -w_{i,j}\text{ else}\hfill & \end{array}.$

In graphs, the benefits from the use of spectral sparsification are several-fold:

1. 1.

   Spectral sparsification is a stronger condition than cut sparsification, as it preserves the eigenvalues of the graph’s Laplacian in addition to the cut sizes.

2. 2.

   The energy of a graph allows for an interpretation of the graph as an electrical network, which allows for well-motivated sampling schemes for designing sparsifiers.

3. 3.

   The energy of the graph has a convenient form as the quadratic form of the Laplacian of the graph. This means that spectral sparsifiers are efficiently certifiable (in the sense that one can verify in polynomial time whether a graph $G^{\prime }$ is a $(1\pm \epsilon )$ spectral-sparsifier of a graph $G$), a key fact that is used when designing deterministic sparsification algorithms [4].

4. 4.

   This property of efficient (and deterministic) certification has also contributed to linear-size spectral sparsifiers of graphs [4], shaving off the $\log (n)$ factor that is inherent to the sampling-based approaches that create cut-sparsifiers.

Given the wide-reaching benefits of spectral sparsification, as research on graph sparsification pivoted to hypergraph sparsification, spectral notions of sparsification in hypergraphs were quick to be proposed. In a hypergraph $H=(V,E)$, each hyperedge $e\in E$ is an arbitrary subset of vertices. A cut in the hypergraph $H$ is given by a subset $S\subseteq V$ of the vertices, and we say that a hyperedge $e$ is cut by $S$ if $S\cap e\ne \mathrm{\varnothing }$ and $\overline{S}\cap e\ne \mathrm{\varnothing }$. A $(1\pm \epsilon )$ cut-sparsifier of a hypergraph is then just a re-weighted subset of hyperedges which simultaneously preserves the weight of every cut to a $(1\pm \epsilon )$ factor. Analogous to the graph case, spectral sparsifiers of hypergraphs instead operate with an energy formulation. Given a hypergraph $H=(V,E)$ and a vector of potentials $x\in {[0,1]}^V$, the energy of the hypergraph is given by $Q_H(x)={\sum }_{e\in E}{w}_e\cdot {\max }_{u,v\in e}{(x_u-x_v)}^2$, and, as with graphs, a spectral sparsifier is simply a re-weighted subset of hyperedges which preserves this energy to a $(1\pm \epsilon )$ factor simultaneously for every $x$.

A line of works by Louis and Makarychev [20], Louis [19], and Chan, Louis, Tang, and Zhang [7] showed that this energy definition in hypergraphs enjoys many of the same properties as the energy definition in graphs: in particular, that it can be viewed as a random walk operator on the hypergraph, that it generalizes the cuts of a hypergraph, and that it admits Cheeger’s inequalities in a manner similar to graphs. Because of these connections, a long line of works simultaneously studied the ability to cut-sparsify ([17, 8]) and spectrally-sparsify ([21, 3, 13, 12, 11, 18]) hypergraphs.

However, subsequent to this unified effort to understand hypergraph sparsification in the cut and spectral settings, the directions of focus from the sparsification community have largely been separate; on the one hand, combinatorial generalizations of cut-sparsification have been studied for more general objects like linear (and non-linear) codes as well as CSPs [15, 16, 6], while on the other hand, continuous generalizations of spectral sparsification have been studied in the context of semi-norms and generalized linear models [9, 10]. The techniques used by these respective research efforts are likewise separate, with combinatorial sparsifiers driven mainly by progress on counting bounds, sampling, and union bounds, while continuous sparsifiers have relied on a deeper understanding of chaining.

In this work, we aim to close this gap between recent work on combinatorial and continuous notions of sparsification by introducing the model of spectral CSP sparsification. This framework simultaneously generalizes cut and spectral sparsification of graphs, cut and spectral sparsification of hypergraphs, and the (combinatorial) sparsification of codes and CSPs. We then show that even under this more general definition, there still exist sparsifiers of small sizes, and moreover, these sparsifiers can even be computed efficiently. We summarize our contributions more explicitly in the following subsection.

The starting point for our approach is a technique used in the work of Soma and Yoshida [21]. To convey the main idea, we will consider the simplified setting of spectrally sparsifying XOR constraints of arity $4$. That is, we consider the predicate $P(y_1,y_2,y_3,y_4)=y_1\oplus y_2\oplus y_3\oplus y_4$, and each constraint $c_i(x)=P(x_{i_1},x_{i_2},x_{i_3},x_{i_4})$. We denote the entire CSP by $C$, which consists of constraints $c_1,\mathrm{\dots }{c}_m$, and we denote the set of variables by $x_1,\mathrm{\dots }{x}_n$. We will often index the set $[m]$ by a constraint $c\in C$ (as there are $m$ different constraints). Note that we choose arity $4$ XORs instead of $3$ so that the all $1$’s assignment is unsatisfying (and thus we can shift any assignment by the all $1$’s vector WLOG). We later show that arity $3$ XORs can be simulated by arity $4$ XORs.

Recall then that our goal is to sparsify the set of constraints while still preserving the energy of the CSP to a $(1\pm \epsilon )$ factor, where the energy is exactly

Now, when we focus on a single constraint, we can actually interpret this energy definition concretely. Since a single constraint is a $4$-XOR over variables $x_{i_1},\mathrm{\dots }{x}_{i_4}$, then with respect to a choice of the rounding parameter $\theta$, the constraint evaluates to $1$ if and only if an odd number of the variables $x_{i_1},\mathrm{\dots }{x}_{i_4}$ are larger than the rounding threshold $\theta$. Thus, if we sort $x_{i_1},\mathrm{\dots }{x}_{i_4}$ according to their value (say the sorted order is $x_{i_{o(1)}}\le x_{i_{o(2)}}\le x_{i_{o(3)}}\le x_{i_{o(4)}}$) the constraint evaluates to $1$ if and only if $\theta \in (x_{i_{o(1)}},x_{i_{o(2)}})$ or $(x_{i_{o(3)}},x_{i_{o(4)}})$. Because $\theta$ is chosen uniformly at random from $[0,1]$, we can directly calculate this probability to be

Ultimately, the energy is the square of this expression, and so it can be written as

Here is where we use a simple observation: for a fixed ordering of the variables $\pi$ (i.e., such that $x_{\pi (1)}\le x_{\pi (2)}\le \mathrm{\cdots }\le x_{\pi (n)}$), the energy expression for each constraint evaluates to a fixed quadratic form. We denote this set of vectors that satisfies the ordering $\pi$ by ${[0,1]}^{\pi }$, and call a vector $x$ satisfying $x_{\pi (1)}\le x_{\pi (2)}\le \mathrm{\cdots }\le x_{\pi (n)}$ $\pi$-consistent. Said another way, once we fix the ordering of the variables, then $o(1),o(2),o(3),o(4)$ in the above expression would also all be fixed. For such a permutation $\pi$, we call this resulting quadratic form the induced quadratic form by $\pi$. For example, if we take the ordering $\pi$ to be the identity permutation (i.e., $x_1\le x_2\le \mathrm{\cdots }\le x_n$), and we suppose that , then the formula for the energy of the expression would be exactly ${(x_{i_4}-x_{i_3}+x_{i_2}-x_{i_1})}^2$. Note that our choice of the words quadratic form is intentional, as once the energy expression is a fixed sum of these quadratic terms, we can express the energy as $Q_C(x)=x^T{(B^{\pi })}^T{W}_C{B}^{\pi }x$, where $x\in {[0,1]}^{\pi }$, and $B^{\pi }\in {\{-1,0,1\}}^{m\times n}$ is the matrix such that ${((B^{\pi })x)}_i={\mathrm{Pr}}_{\theta \in [0,1]}[c_i(x^{(\theta )})=1]$, and $W_C$ is simply the diagonal matrix whose $i,i$th entry is the weight of the $i$th constraint in $C$.

Now, as observed in [21], in order to sparsify the CSP $C$, it suffices to choose a re-weighted subset of indices $\widehat{S}\subseteq [m]$, such that simultaneously for every ordering $\pi$, the induced quadratic form by $\pi$ has its energy preserved to a $(1\pm \epsilon )$ factor. Because of our above simplifications, we can re-write this another way: we want to find a new, sparser set of weights on our constraints (which we denote by $\widehat{C}$), such that for every ordering $\pi$, and for every vector $x\in {[0,1]}^{\pi }$, it is the case that

We can re-write this condition as saying that

and

If this condition holds, then we will have indeed created a $(1\pm \epsilon )$ spectral sparsifier. Recall that we want to use as few re-weighted constraints as possible, and so we want this new set of re-weighted constraints $\widehat{C}$ to be as sparse as possible.

Next, observe that the expression above is a type of positive definiteness condition, where we focus our attention on vectors in ${[0,1]}^{\pi }$, and want to ensure that the quadratic form of some matrix is non-negative. In particular, the work of [21] studied similar matrices, and gave an exact characterization for when such a claim holds:

This lemma gives us a roadmap for how to proceed. Recall that there are two matrices that we wish to show satisfy the positivity condition, namely $\left({(B^{\pi })}^T{W}_{\widehat{C}}{B}^{\pi }-(1-\epsilon ){(B^{\pi })}^T{W}_C{B}^{\pi }\right)$ and $\left((1+\epsilon ){(B^{\pi })}^T{W}_C{B}^{\pi }-{(B^{\pi })}^T{W}_{\widehat{C}}{B}^{\pi }\right)$, and these will each be the matrix $A$ in the above lemma (though to simplify discussion, we will simply focus on the first, as the analysis will be identical). Our goal is to show that we can re-write the matrix as

where the matrix $K$ is co-positive (meaning for all positive vectors, the quadratic form is non-negative). To do this, we will ultimately define a new, specific matrix $B_{\mathrm{cross}}^{\pi }$ with the intention that $B^{\pi }=B_{\mathrm{cross}}^{\pi }J{P}_{\pi }$. While [21] also define a crossing matrix, ours is necessarily different as it models a different structure. It is here where our analysis begins to diverge from theirs.

However, before defining this crossing matrix $B_{\mathrm{cross}}^{\pi }$, we first require some definitions. First is the notion of an active region, which is essentially the intervals where the contribution to the energy comes from (i.e., the choices of $\theta$ for which a constraint is satisfied):

For an index $i\in [n-1]$, let us consider the bisector between $x_{{\pi }_i}$ and $x_{{\pi }_{i+1}}$ (i.e., between the $i$th and $i+1$st smallest elements in the ordering $\pi$). This bisector takes on value $(x_{{\pi }_i}+x_{{\pi }_{i+1}})/2$. We use this to define crossing indices:

Likewise, we generalize this definition to a pair of indices $i,j\in [n-1]$:

For instance, let us consider what happens when the permutation $\pi ={\mathrm{Id}}_n$, and suppose we are looking at a constraint $c_i(x)$ which is the XOR of $x_2,x_3,x_6,x_9$. Then the crossing indices are exactly $2,6,7$ and $8$. More intuitively, the crossing indices correspond to the intervals $[x_i,x_{i+1}]$ which contribute to the overall energy (i.e., for which choices of $\theta$ does the constraint evaluate to $1$). For instance, because $[x_6,x_9]$ is an active region the energy contributed from these points is $x_9-x_6$ and so every sub-interval $[x_6,x_7],[x_7,x_8],[x_8,x_9]$ contributes to the energy. This is because if $\theta \in [x_7,x_8]$ for instance, then in the rounding $x_2=x_3=x_6=1$, and $x_9=0$, and hence the constraint is satisfied.

With these definitions established, we define the crossing matrix $B_{\mathrm{cross}}^{\pi }\in {ℝ}^{m\times n-1}$ such that $B_{\mathrm{cross}}^{\pi }(c,i)=1$ if and only if $i$ is a crossing index for the constraint $c$ under permutation $\pi$ (and otherwise, the $c,i$th entry is $0$). In particular, this specific definition allows us to show that

We do not discuss this equality exactly here, as it requires an extensive case analysis; we defer this to the technical sections below.

However, using this, we can re-write our original expression:

Thus, if we revisit Lemma 9, the matrix $K$ is exactly this interior portion of the expression $K=({(B_{\mathrm{cross}}^{\pi })}^T{W}_{\widehat{C}}{B}_{\mathrm{cross}}^{\pi }-(1-\epsilon ){(B_{\mathrm{cross}}^{\pi })}^T{W}_C{B}_{\mathrm{cross}}^{\pi })$, and thus our goal becomes to show that $y^{T}Ky\ge 0$ $\forall y\in {ℝ}_{+}^{n-1}$ (while allowing for sparsity in the selected constraints of course).

Now, we make a simple observation: a sufficient (but not necessary) condition for $K$ to satisfy $y^{T}Ky\ge 0$ $\forall y\in {ℝ}_{+}^{n-1}$ is for every entry in $K$ to be non-negative. Thus, it remains to understand exactly what the entries in $K$ look like: we start by looking at a simpler expression, namely ${(B_{\mathrm{cross}}^{\pi })}^T{W}_C{B}_{\mathrm{cross}}^{\pi }$. Indeed, in this matrix the $i,j$th entry can be written as

where we simply use $d_{C,\pi }(i,j)$ to denote the total weight of constraints that have both $i$ and $j$ as crossing indices under the permutation $\pi$.

Here comes the final, key technical lemma: we show that there is a matrix $G\in {𝔽}_2^{m\times n^2}$ such that for every choice of $i,j$ and permutation $\pi$, there is a vector $z_{\pi ,i,j}\in {𝔽}_2^{n^2}$ such that ${(G{z}_{\pi ,i,j})}_c$ (i.e., the $c$th coordinate of the vector $(G{z}_{\pi ,i,j})$) is exactly the indicator of whether or not $i,j$ are crossing indices for the constraint $c$ under permutation $\pi$. Thus, this value $d_{C,\pi }(i,j)={\left({(B_{\mathrm{cross}}^{\pi })}^T{W}_C{B}_{\mathrm{cross}}^{\pi }\right)}_{i,j}$ can be written as the weighted hamming weight of the vector $(G{z}_{\pi ,i,j})$.

To construct this matrix $G$, we start with the generating matrix of our original XOR CSP $C$: this is the matrix $F\in {𝔽}_2^{m\times n}$, where for the constraint $c$ operating on $x_{u_1},x_{u_2},x_{u_3},x_{u_4}$, there is a single row in the matrix $F$ corresponding to $c$, with $1$’s exactly in columns $u_1,u_2,u_3,u_4$. Now, the matrix $G$ is a type of tensor-product code that is generated by $F\oplus F$. Explicitly, when we consider the linear space generated by $F$ (denoted $\mathrm{Im}(F)$), we want

where $z_1\cdot z_2$ refers to the entry-wise multiplication of the two vectors. Note that $G$ will be expressible as a space of dimension $\le O(n^2)$ as it essentially corresponds to a space of degree $2$ polynomials over $n$ variables (though see the full version for a more thorough discussion).

Now, recall that our goal is to show that for a fixed permutation $\pi$, as well as indices $i,j$, that we can find a vector in $\mathrm{Im}(G)$ whose $\mathrm{\ell }$th coordinate is exactly the indicator of whether $i,j$ are crossing indices for the $\mathrm{\ell }$th constraint under permutation $\pi$. For simplicity, let us suppose that the permutation $\pi$ is just the identity permutation; under this permutation, recall that an index $i$ is considered to be a crossing index for a constraint $c$ if and only if $i$ is in an active region of $c$. If we denote the variables in the constraint $c$ by $x_{u_1},\mathrm{\dots }{x}_{u_4}$, then $i$ is a crossing index under $\pi$ if and only if $x_i$ is greater than or equal to an odd number of $x_{u_1},x_{u_2},x_{u_3},x_{u_4}$: this is because the active regions are $[x_{u_1},x_{u_2}]$ and $[x_{u_3},x_{u_4}]$, and so $x_i$ must either be between $[x_{u_1},x_{u_2}]$, or between $[x_{u_3},x_{u_4}]$.

A priori, it may seem that this condition is completely arbitrary. However, it can be exactly captured by our matrix $F$: indeed, let us consider the vector $e_{\le i}\in {𝔽}_2^n$ which is $1$ in the first $i$ entries, and $0$ in the others. The $\mathrm{\ell }$th constraint then performs an XOR on the variables $x_{u_1},x_{u_2},x_{u_3},x_{u_4}$. Plugging this vector in, we obtain that

which is exactly the indicator of whether $x_i$ is greater than or equal to an odd number of $x_{u_1},x_{u_2},x_{u_3},x_{u_4}$ (since we are using the identity ordering of $x_1\le x_2\le \mathrm{\cdots }\le x_n$).

Thus, the matrix $F$ alone captures when single indices are crossing a constraint. To generalize to pairs of crossing indices, we then simply take the coordinate-wise product of whether indices $i,j$ are both crossing a constraint $c$ under a permutation $\pi$. This is exactly what is captured by the code $\mathrm{Im}(G)$.

Because of this correspondence above, this means that $d_{C,\pi }(i,j)$ can be exactly written as the weighted hamming weight of the codeword $G{z}_{\pi ,i,j}$, where $z_{\pi ,i,j}$ is the particular vector we use to enforce

To conclude then, we recall the work of Khanna, Putterman, and Sudan [15], who showed that every code admits a sparsifier which preserves only a set of coordinates of size nearly-linear in the dimension of the code. In our case, the dimension is $O(n^2)$, so this means that there exists a re-weighted subset of coordinates $\widehat{C}$, of size $\tilde{O}(n^2/{\epsilon }^2)$ which preserves the weight of every codeword to a $(1\pm \epsilon )$ factor. In particular, this means for the CSP defined on the same re-weighted subset of constraints, it must be the case that

By sparsifying this auxiliary code, we obtain a re-weighted subset of the constraints which satisfies that the parameter $d_{C,\pi }(i,j)$ is approximately preserved. When we revisit the matrices we created: $K=({(B_{\mathrm{cross}}^{\pi })}^T{W}_{\widehat{C}}{B}_{\mathrm{cross}}^{\pi }-(1-\epsilon ){(B_{\mathrm{cross}}^{\pi })}^T{W}_C{B}_{\mathrm{cross}}^{\pi })$, because the entries in ${(B_{\mathrm{cross}}^{\pi })}^T{W}_{\widehat{C}}{B}_{\mathrm{cross}}^{\pi }$ are exactly $d_{\widehat{C},\pi }(i,j)$, and the entries in ${(B_{\mathrm{cross}}^{\pi })}^T{W}_C{B}_{\mathrm{cross}}^{\pi }$ are exactly $d_{C,\pi }(i,j)$, we see that the constraints $\widehat{C}$ computed by the code sparsifier do indeed lead to a matrix with all non-negative entries as

and thus this matrix is non-negative on all non-negative vectors (and so too constitutes a spectral sparsifier by our previous discussions).

Likewise, observe that because the matrix $G$ we defined above is the same for all permutations $\pi$ (we only need to change the vector $e_{\le i}$ above that we multiply the matrix by), this implies that the same set of constraints will be a sparsifier across all choices of permutations, and thus we have a set of $\tilde{O}(n^2/{\epsilon }^2)$ constraints which is a spectral CSP sparsifier of our original instance. By generalizing this argument (and using the efficient constructions of code sparsifiers [16]), we obtain Theorem 7.

We end the technical overview with some high-level remarks:

1. 1.

   Although we build on the framework of [21], the hypergraph sparsifiers in [21] were of size $O(n^3/{\epsilon }^2)$. Our refinement of their framework (specifically, the explicit connection with codes), allows for an improved sparsifier size of $\tilde{O}(n^2/{\epsilon }^2)$.

2. 2.

   Likewise, the framework from [21] is particular suited for sparsifying hypergraphs. Our framework reveals a much more general connection between spectral sparsification and sparsifying a type of tensor product of the underlying object which holds across the entire CSP landscape.

3. 3.

   The method presented in this paper avoids any complex continuous machinery like chaining or matrix-chernoff, which have appeared in prior works on spectral sparsification [13, 12, 9]. We view it is an interesting open question whether those techniques can be combined with ours to create nearly-linear size spectral CSP sparsifiers.