Subgraph Sparsification and Nearly Optimal Ultrasparsifiers

Introduction

In this paper, we will mainly be interested in the spectral notion of graph similarity introduced by Spielman and Teng , : we say that a weighted undirected graph $H$ is a $\kappa$-approximation of another $G$ if for all $x\in\mathbf{R}^{V}$,

where for a weighted undirected graph $G$, $\mathcal{L}_{G}$ is the Laplacian matrix of $G$ defined as the following: For each $\mathcal{L}_{G}(i,i)$ is equal to the sum of weights of all edges incident to vertex $i$ and for $i\neq j$, $\mathcal{L}_{G}(i,j)=-w_{i,j}$, where $w_{i,j}$ is the weight on edge $(i,j)$.

In this paper, we introduce a variation of the spectral sparsification problem which we will refer to as the Subgraph Sparsification. In our version, we are given two weighted graphs $G$ and $W$, an integer $k$ and $\kappa\geq 1$. The goal is to find a $k$-edge weighted graph $W_{k}$ such that $(G+W_{k})$ is a $\kappa$-approximation of $(G+W)$. The challenge in the new version of the sparsification problem is that we have to respect part of the graph, i.e., $G$, and only modify part of graph given in $W$.

As the main technical contribution of the paper, we give a nontrivial condition about $G$ and $W$ such that a good sparsifier exists. Our proof critically uses the intuition of Batson, Spielman, and Srivastava , that uses potential functions that guide an incremental process for selecting the edges of the sparisifier. We will refer to that as as the BSS process. We have enhanced their approach with new understanding about subspace sparsification and spectral approximation.

Our challenge, at high level, is the following. The BSS process uses two carefully chosen barriers (see Section 2) so that at each step, all eigenvalues can be kept far enough from these barriers. They have $\Theta(n)$ edges to select. So they consider the entire $n$-dimensional space and have step size $\Theta(1/n)$ on these barriers.

On the other hand, we can only add $k$ edges, where $k$ can be arbitrarily smaller than $n$. The addition of each edge can only increase smallest eigenvalue to the second smallest eigenvalue. Therefore the addition of $k$ edges can only improve the subspace defined by the $k$ smallest eigenvalue. Now, the critical part of the argument is that to build a good sparsifier, we need to ensure that the addition of the edges does not increase the high spectra by too much. So in our incremental process, we need to keep track of two subspaces, a fixed one defined by the $k$ smallest eigenvalues and a floating one defined by the higher spectra.

We developed an analysis for performing spectral analysis in the projection of a sequence of two subspaces, which might be interesting on its own right. Our analysis also provide a nice example for using majorization.

At high level, our solution to ultrasparsification is quite simple, once we have our subgraph sparsification result. Given a weighted graph$G$, we first construct a low-stretch spanning tree $T$ of $G$. We then apply an elegant result of Spielman and Woo which states that the sum of the relative condition numbers of $\mathcal{L}_{G}$ and $\mathcal{L}_{T}$ is equal to the total stretch to embed $G$ onto $T$. We will also use Spielman–Woo’s tail distribution bound on the number of relative eigenvalues of $\mathcal{L}_{G}$ and $\mathcal{L}_{T}$ that are larger than a given parameter.

As another application of our technique on subgraph sparsification, we consider the following spectral optimization problem studied in : Given a graph $G$ and a parameter $k$, we are asked to find $k$ edges amongst a set of candidate edges to add to $G$ so as to maximize its algebraic connectivity. Algebraic connectivity has emerged as an important parameter for measuring the robustness and stability of a network and is an essential factor in the performance of various search, routing and information diffusion algorithms.

The spectral optimization considered in this paper is known to be NP-hard and no approximation guarantee for it was known prior to our work. We give an SDP-based approximation algorithm for the problem. Our techniques for subgraph sparsification enable us to develop a novel rounding scheme in order to find a combinatorial solution. Since the integrality gap of the SDP is unbounded, our analysis involves adding a separate upper bound, which is roughly the $k$-th largest eigenvalue of the Laplacian of $G$ to approximate the optimum solution.

Preliminaries

We say that a graph is $k$–ultra-sparse if it has at most $n-1+k$ edges. We note that a spanning tree is –ultra-sparse. A ($\kappa,k)$ ultra-sparsifier of a graph $G=(V,E,w)$ is a $k$–ultra-sparse subgraph of $G$ such that $U\preceq G\preceq\kappa\cdot U$ .

Matrix Sparsifiers

In this section, we prove an analog of the sparsification theorem of Batson, Spielman, and Srivastava .

(Graph Patch) Let $G$ be a (weighted) graph. A graph $W$ on the vertices of $G$ is a $(k,T,\lambda^{*})$-patch for $G$ if the following properties holdwe have $\lambda_{k+1}(\mathcal{L}_{G}\mathcal{L}_{G+W}^{\dagger})=\lambda_{k+1}((\mathcal{L}_{G+W}^{\dagger})^{1/2}\mathcal{L}_{G}(\mathcal{L}_{G+W}^{\dagger})^{1/2})$, since $\lambda_{i}(AB)=\lambda_{i}(BA)$ for every two square matrices $A$ and $B$,

$\lambda_{k+1}(\mathcal{L}_{G}\mathcal{L}_{G+W}^{\dagger})\equiv\lambda_{k+1}((\mathcal{L}_{G+W}^{\dagger})^{1/2}\mathcal{L}_{G}(\mathcal{L}_{G+W}^{\dagger})^{1/2})\geq\lambda^{*}$;

$\operatorname{tr}(\mathcal{L}_{W}\mathcal{L}_{G+W}^{\dagger})\leq T$.

We prove that for every patch, there exists a “patch sparsifier” supported on $O(k)$ edges. Specifically, we prove the following theorem.

$W_{k}$ has at most $N$ edges; $E_{W_{k}}\subseteq E_{W}$.

$c_{1}\min(N/T,1)\lambda^{*}\mathcal{L}_{G+W}\preceq\mathcal{L}_{G+W_{k}}\preceq c_{2}\mathcal{L}_{G+W}$, for some absolute constants $c_{1}$ and $c_{2}$.

We say that $W_{k}$ is a patch sparsifier of $W$ with respect to $G$.

The claim will follow immediately from the following theorem, which is is of independent interest. We will also show another (related) application of this theorem in Section 5.

Suppose we are given a positive definite $n\times n$ matrix $X$ and a sequence of matrices $Y_{i}=v_{i}v_{i}^{T}$ ($i=1,\dots,m$) with

where $c_{1}$ and $c_{2}$ are some absolute constants, and $\sum_{i=1}^{m}w_{i}cost_{i}\leq\min(1,N/T)$.

In our proof, however, we cannot keep an eye on all eigenvalues. After each step, only one eigenvalue increases, and thus we need $\theta(n)$ steps to increase all eigenvalues participating in the definition of $\Phi_{l}(M)$. But our goal is to “patch” $X$ in roughly $k$ steps. So we focus our attention only on $k$ smallest and $T$ largest eigenvalues.

Let $S$ be the eigenspace of $X$ corresponding to $k$ smallest eigenvalues, and $P_{S}$ be the projection onto $S$. We define the lower potential function as follows,

where $\left.A\right|_{S}$ denotes the restriction of $A$ to the space $S$ ($\left.A\right|_{S}$ is a $k\times k$ matrix). Note that the space $S$ is fixed, and the eigenvector corresponding to the smallest eigenvalue will not necessarily lie in $S$ after a few steps. We want to ensure that after $N$ steps,

Note that both definitions of $\Phi^{u}(A)$ — in terms of regular inverse and in terms of pseudoinverse — are equivalent since $L(A)$ is an invariant subspace of $A$. However, $\Phi_{l}(A)$ is not equal to $\operatorname{tr}(P_{S}(A-lI)^{-1}P_{S})$ in general since $S$ is not necessarily an invariant subspace of $A$.

Our algorithm and analysis are similar to those of Batson, Spielman, and Srivastava . However, several complications arise because we are controlling eigenvalues in different subspaces and, moreover, one of these subspaces, $L(A)$, is not fixed.

Let us summarize the proof. We construct the matrix $M$ iteratively in $N$ steps. Let $A^{(q)}$ be the matrix and $w_{i}^{(q)}$ be the weights after $q$ steps. We define an auxiliary matrix $B^{(q)}$ as $Z(A^{(q)}-X)Z$. We have,

We will ensure that the following properties hold after each step (for some values of constants $l_{0}$, $\delta_{L}$, $u_{0}$, $\delta_{U}$, $\epsilon_{L}$, $\epsilon_{U}$, which we will specify later).

$\Phi_{l_{0}}(B^{(0)})\leq\epsilon_{L}$ and $\Phi^{u_{0}}(A^{(0)})\leq\epsilon_{U}$.

Each matrix $A^{(q)}$ and $B^{(q)}$ is obtained by a rank-one update of the previous one:

Lower and upper potentials do not increase. Namely, for every $q=0,1,\dots,N$,

At each step $q$, the total cost is at at most $q/\max(N,T)$: $\sum w_{i}^{(q)}cost_{i}\leq q/\max(N,T)$.

We present the complete proof in Sections 3.2 and 3.3. In Section 3.2, we first find conditions under which we can update $A^{(q)}$ and $u$ (Lemma 3.10), and $B^{(q)}$ and $l$ (Lemma 3.11). Then we show that both conditions can be simultaneously satisfied (Lemma 3.12). In Section 3.1.2, we prove several theorems that we need later to deal with a non-fixed subspace $L(A)$. Finally, in Section 3.3, we combine all pieces of the proof together.

We use the Sherman–Morrison Formula, which describes the behavior of the inverse of a matrix under rank-one updates. We first state the formula for regular inverse , and then we show that a similar expression holds for the pseudoinverse.

If $A$ is a nonsingular $n\times n$ matrix and $Y=vv^{T}$ is a rank-one update, then

If $A$ is a symmetric (possibly singular) $n\times n$ matrix, $Y=vv^{T}$ is a rank-one update, then

where $P$ is the orthogonal projection on $\operatorname{Im}(A)$.

Let $\bar{v}=Pv$ and $\bar{Y}=PYP=\bar{v}\bar{v}^{T}$ . Note that $A^{\dagger}YA^{\dagger}=A^{\dagger}\bar{Y}A^{\dagger}$, since $PA^{\dagger}=P$, and

Since $A$ is a symmetric matrix, $AA^{\dagger}=A^{\dagger}A=P$. Since $P^{2}=P$, $P\bar{Y}P=\bar{Y}$ and $\bar{Y}A^{\dagger}\bar{Y}=\bar{v}\bar{v}^{T}A\bar{v}\bar{v}^{T}=\bar{v}(A\bullet\bar{Y})\bar{v}^{T}=(A\bullet\bar{Y})\bar{Y}$. We calculate,

1.2 Majorization

(Majorization) For every positive semidefinite matrix $A$, every projection matrix $P$, and every $r\in\{1,\dots,n\}$

The weight of each eigenvalue $\lambda_{j}(A)$ in the sum is at most $1$:

Therefore, the sum does not exceed the sum of the $r$ largest eigenvalues $\sum_{i=n-r+1}^{n}\lambda_{r}(A)$. ∎

The statement follows from the Karamata Majorization Inequality. The inequality claims that for every two non-increasing sequences that satisfy (2) and for every increasing convex function $f$,

Plugging in $f(x)=\frac{1}{u-x}$ (defined on $(0,u)$), we obtain the desired inequality. ∎

By von Neumann’s inequality , $A\bullet M=\operatorname{tr}(AM)\leq\sum_{i=1}^{n}\lambda_{i}(A)\lambda_{i}(M)$. Since $\sum_{i=1}^{n}\lambda_{i}(A)\leq r$ and all $\lambda_{i}(A)\leq 1$, we can easily see that the above product achieves its maximum when the largest $r$ eigenvalues of $A$ are $1$ and the rest are . In this case, we have, $A\bullet M\leq\sum_{i=1}^{n}\lambda_{i}(A)\lambda_{i}(M)=\sum_{i=n-r+1}^{n}\lambda_{i}(M)$. ∎

As a corollary we get the following result.

Let $X$, $M^{*}$ and $T$ be as in Theorem 3.3. Then for any positive semidefinite matrix $U$, we have $U\bullet(M^{*}-X)\leq\sum_{i=n-T+1}^{n}\lambda_{i}(U)$.

2 Barrier Shifts

In this section, we analyze how we can update matrices $A^{(q)}$ and $B^{(q)}$, and increment barriers $l$ and $r$ so that the upper and lower potentials do not increase. Let us think of $\Phi^{u}(A)$ as a function of an $n^{2}$ dimensional vector (consisting of entries of $A$). Then in the first approximation $\Phi^{u+\delta_{U}}(A+tY)\approx\Phi^{u+\delta_{U}}(A)+tY\bullet U$, where $U$ is the gradient of $\Phi^{u+\delta_{U}}$ at $A$ ($U$ is an $n\times n$ matrix). Thus the potential function does not increase, $\Phi^{u+\delta_{U}}(A+tY)\leq\Phi^{u}(A)$, roughly when $tY\bullet\frac{U}{\Phi^{u}(A)-\Phi^{u+\delta_{U}}(A)}\leq 1$. Similarly, $\Phi_{l+\delta_{L}}(B+tY)\leq\Phi_{l}(B)$, roughly when $tY\bullet\frac{L}{\Phi_{l+\delta_{L}}(B)-\Phi_{l}(B)}\geq 1$, where $L$ is the gradient of $\Phi_{l+\delta_{L}}$ at $B$. Following , we make these statements precise (we need to take into account lower order terms). We define matrices $U_{A}$ and $L_{B}$,

Let $u^{\prime}=u+\delta_{U}$ and $P=P_{L(A+tY)}$. By the Sherman–Morrison formula (Lemma (3.4)), we can write the updated potential as:

Here, we used Corollary 3.7 for the inequality on line 4.

We proceed as in the proof for the upper potential. Let $l^{\prime}=l+\delta_{L}$ and $P=P_{S}$. By the Sherman–Morrison formula for the pseudoinverse (Lemma 3.5), we have:

Note that matrix $U_{A}$ is positive semidefinite. Rearranging shows that $\Phi_{l+\delta_{L}}(B+Y)\leq\Phi_{l}(B)$ when $L_{A}(\pi)\geq 1/t$. It is immediate that $\lambda_{\text{min}}(P_{S}(A+t\pi\pi^{T})P_{S})>l+\delta_{L}$ since $\lambda_{\text{min}}(P_{S}AP_{S})>l+\delta_{L}$. ∎

Now we prove that we can choose $Y_{i}$ and $t$ so that conditions of both lemmas are satisfied.

(Both Barriers) If $\Phi^{u}(A)\leq\epsilon_{U}$ and $\Phi_{l}(B)\leq\epsilon_{L}$ and $\epsilon_{U},\epsilon_{L},\delta_{U},\delta_{L}$ satisfy

and $X$, $Y_{i}$, $cost_{i}$, $Z$, $T$ and $N$ as in Theorem 3.3, $M^{*}-X$ is non-singular on $S$, then there exists $i$ and positive $t$ for which

$\sum_{i=1}^{m}U_{A}\bullet Y_{i}\leq\frac{1}{\delta_{U}}+\epsilon_{U}$ and $\sum_{i=1}^{m}L_{B}\bullet(ZY_{i}Z)\geq\frac{1}{\delta_{L}}-\epsilon_{L}.$

1. We use Corollary 3.9 to bound the Frobenius product of $Y_{i}$ with each of the two summands in the definition of $U_{A}$ (note that they are positive semidefinite), we get

Note that the first term is at most $1/\delta_{U}$, since

and the second term equals $\Phi^{u+\delta_{U}}(A)$. Thus $\sum_{i=1}^{m}U_{A}\bullet Y_{i}\leq\epsilon_{U}+1/\delta_{U}$.

2. Let $P$ be the projection on $\operatorname{Im}(M^{*}-X)$. Since $(M^{*}-X)$ is non-singular on $S$, $PP_{S}=P_{S}$. We have,

where the last line follows from Claim 3.6 in .

(Of Lemma 3.12) For the previous lemma, we get: $\sum_{i=1}^{m}(U_{A}\bullet Y_{i}+\max(N,T)cost_{i})\leq\frac{1}{\delta_{U}}+\epsilon_{U}+\max(N,T)\leq L_{B}\bullet(ZY_{i}Z).$ Thus for some $i$, $U_{A}\bullet Y_{i}+\max(N,T)cost_{i}\leq L_{B}\bullet(ZY_{i}Z)$. Letting $t=(L_{B}\bullet(ZY_{i}Z))^{-1}$, we satisfy (4) and (5). ∎

3 Proof of Theorem 3.3

Now we are ready to prove Theorem 3.3. We assume that $M^{*}-X$ is non-singular on $S$ (which we can ensure by an arbitrary small pertrubation).

We start with $A^{(0)}=X$, $B^{(0)}=0$ and all weights $w^{(0)}_{i}=0$. We define parameters as follows,

so as to satisfy conditions of Lemma 3.12, $\Phi^{u}(A^{(0)})=\Phi^{u}(X)=\sum_{i=1}^{T}\frac{1}{u_{0}-\lambda_{n+1-i}(X)}\leq T/(u_{0}-1)=\epsilon_{U}$, $\Phi_{l}(B^{(0)})=\sum_{i=1}^{k}\frac{1}{0-l_{0}}=-k/l_{0}=\epsilon_{L}$, $1/\delta_{U}+\epsilon_{U}+\max(N,T)=\frac{3}{2}\max(N,T)=1/\delta_{L}-\epsilon_{L}$. Then we iteratively apply Lemma 3.12. At iteration $q$, we find an index $i$ and a positive $t$ such that $L_{B^{(q)}}(ZY_{i}Z)\geq 1/t\geq U_{A^{(q)}}(Y_{i})$, $cost_{i}\cdot t\leq 1/\max(N,T)$, and increment the weight of matrix $Y_{i}$ by $t$: $w^{(q+1)}_{i}=w^{(q)}_{i}+t$; update $l=l+\delta_{L}$ and $u=u+\delta_{U}$. The total cost increases by at most $1/\max(N,T)$. Finally, after $N$ iterations we obtain matrices $A^{(N)}$ and $B^{(N)}$ with

On the other hand, since $S$ is an eigenspace of $X$ corresponding to $k$ smallest eigenvalues,

Plugging in the values of parameters, we get the statement of the theorem for $M=A^{(N)}$. The total cost is at most $N/\max(N,T)=\min(1,N/T)$. ∎

Let $V=\operatorname{Im}(\mathcal{L}_{G+W})=\ker(\mathcal{L}_{G+W})^{\perp}$. Let $\mathcal{L}_{e}$ be the Laplacian of the edge $e$. Define

Since $\mathcal{L}_{G}+\sum_{e\in E_{W}}^{m}w_{e}\mathcal{L}_{e}=\mathcal{L}_{G+W}$, we have $X+\sum_{e\in E_{W}}Y_{e}=I$. By the definition of the $(k,T,\lambda^{*})$-patch, $\operatorname{tr}(I-X)\leq T$ and $\lambda^{*}\leq\lambda^{k+1}(X)$. We apply Theorem 3.3 to matrices $X$, $Y_{e}$ and $M^{*}=I$. We obtain a set of weights $\rho_{e}$ — supported on at most $N$ edges — such that

The total weight of edges of $W_{k}$ is $\sum_{e\in E_{W}}\rho_{e}w_{e}=(\sum_{e\in E_{W}}\rho_{e}cost_{e})\sum_{d\in E_{W}}w_{d}\leq\min(1,N/T)\sum_{d\in E_{W}}w_{d}$. ∎

Constructing Nearly-Optimal Ultrasparsifiers

We now apply our subgraph sparsification to build ultrasparsifiers. Recall that a weighted graph $U$ is a $(\kappa,k)$-ultrasparsifier of another graph $G$ if $U\preceq G\preceq\kappa\cdot U$ and $U$ has only $n-1+k$ edges, where $n$ is the number of vertices in $U$ and $G$. The main result of this section is the following theorem.

Our basic idea to build a good ultrasparsifier $U$ is quite simple. Without loss of generality, we can assume that $G$ is connected and has $O(n)$ edges. Otherwise given a graph $G$, we can first find a linear size sparsifier using , for each of its connected components, and build a good ultrasparsifier for each component. Because $U$ is only $k$ edges aways from a tree, our construction starts with good tree $T$. As it will be much more clear below, the quality of a tree is measured by its stretch, as introduced by Alon, Karp, Peleg and West .

Suppose $T$ is a spanning tree of $G=(V,E,w)$. For any edge $e\in E$, let $e_{1},\cdots,e_{k}\in F$ be the edges on the unique path in $T$ connecting the endpoints of $e$. The stretch of $e$ w.r.t. $T$ is given by $\text{st}_{T}(e)=w(e)(\sum_{i=1}^{k}\frac{1}{w(e_{i})})$. The stretch of the graph $G$ with respect to $T$ is defined by $\text{st}_{T}(G)=\sum_{e\in E}\text{st}_{T}(e).$ Our construction will start with a spanning tree with the lowest possible stretch. By , we can in polynomial time grow a spanning tree $T$ with

For the sake of simplicity of the presentation, we will show the construction of ultrasparsifiers with $\Theta(k)$ edges. We note that by choosing the appropriate constants, the number of edges can be made exactly $k$.

(Theorem 2.1 in ) (1) $\text{Tr}({\mathcal{L}^{\dagger}_{T}}^{1/2}\mathcal{L}_{G}{\mathcal{L}^{\dagger}_{T}}^{1/2})=\text{st}_{T}(G).$ (2) For every $t>0$, the number of eigenvalues of ${\mathcal{L}^{\dagger}_{T}}^{1/2}\mathcal{L}_{G}{\mathcal{L}^{\dagger}_{T}}^{1/2}$ greater than $t$ is at most $\text{st}_{T}(G)/t$.

We now use Lemma 4.3 to prove the following lemma, from which Theorem 4.1 follows directly.

$W$ is a $(k,O(k),\Theta(1))$–patch for $T$.

Let $\lambda_{i}=\lambda_{i}((\mathcal{L}_{T+W}^{\dagger})^{1/2}\mathcal{L}_{T}(\mathcal{L}_{T+W}^{\dagger})^{1/2})$ be the $i$-th eigenvalue, and $y_{i}$ be the corresponding eigenvector. Let $x_{i}=L_{T+W}^{1/2}y_{i}$. Then,

It follows from the definition of $\lambda_{i}$ that $0\leq\lambda_{i}<1$. Hence, $(1-\lambda_{i-1})/\lambda_{i-1}\geq(1-\lambda_{i})/\lambda_{i}$. By Courant—Fischer theorem and the property 2 of Lemma 4.3, we have $k\leq\frac{k}{c_{1}c_{3}}\frac{\lambda_{k+1}}{1-\lambda_{k+1}}.$ Therefore, $\lambda_{k+1}\geq\frac{c_{1}c_{3}}{1+c_{1}c_{3}}=\Theta(1)$. We also have,

We proved that $W$ is a $(k,O(k),\Theta(1))$–patch for $T$. ∎

We next show that the parameters of the ultrasparsifiers we obtained are optimal, up to low order terms.

Let $G$ be a Ramanujan $d$-regular expander graph, for some constant $d$. Let $U$ a $(\kappa,N)$ ultrasparsifier for $G$. Then $\kappa\geq\frac{n}{N}\log n.$

Let T be a low-stretch spanning tree of $G$, as above. As mentioned in , $\text{st}_{T}(G)=\Omega(m\log n)$ where $m$ is the number of edges of the original graph. From lemma 4.3, and the conditions on the stretch of $T$ we have $\text{Tr}(\mathcal{L}_{G}{\mathcal{L}_{T}}^{\dagger})=\text{st}_{T}(G)\geq C\cdot n\log n$ for some constant $C$.

Since $x^{T}\mathcal{L}_{G}x=\Theta(1)$ for the expander, the above inequality implies that $\sum_{i=1}^{n}\frac{1}{x^{T}\mathcal{L}_{T}x}\geq n\log n$ where $x_{i}$ are the eigenvectors of $\mathcal{L}_{G}(\mathcal{L}_{T})^{\dagger}$. It is immediate from Markov’s inequality that there exists some $k$ such that ${x_{k}}^{T}\mathcal{L}_{T}x_{k}\leq\frac{C_{1}k}{n\log n}$. Assume that for all $i\leq k$ we have ${x_{i}}^{T}\mathcal{L}_{T}x_{i}\leq{x_{k}}^{T}\mathcal{L}_{T}x_{k}\leq\frac{C_{1}k}{n\log n}$. (Otherwise take $k^{\prime}<k$ appropriately). Then also $\lambda_{k}(\mathcal{L}_{T})\leq\frac{C_{1}k}{n\log n}$. By the minmax theorem for eigenvalues this implies that adding $N=k-2$ edges to $T$ will result to a graph $U$ with $\lambda_{2}(\mathcal{L}_{U})\leq\lambda_{k}(\mathcal{L}_{T})\leq\frac{C_{1}k}{n\log n}$. Thus any ultrasparsifier $U$ with $N$ edges will have

Maximizing Algebraic Connectivity by Adding few edges

In this section, we present an approximation algorithm for the following problem: given a graph $G=(V,E_{base})$, a set of candidate edges $E_{cand}$, and a parameter $k$, add at most $k$ candidate edges to $G$ so as to maximize its algebraic connectivity, that is, find a subset $E\subset E_{cand}$ that maximizes $\lambda_{2}(\mathcal{L}_{G+E})$. The problem was introduced by Ghosh and Boyd , who presented a heuristic for it. It is known that the problem is NP-hard . But prior to this work, no approximation algorithm was known for it.

We use two upper bounds for the cost of the combinatorial solution in order to prove an approximation guarantee: one upper bound is the SDP value, $\lambda_{SDP}$, and the other is $\lambda_{k+2}(\mathcal{L}_{G})$ (see Lemma 5.1). Note that neither of these two bounds are good approximations for the value of the optimum solution by themselves (for instance, if $G$ consists of $n$ isolated vertices, $(V,E_{cand})$ is an expander, $k<n$, then the value of the combinatorial solution is but $\lambda_{SDP}\sim k/n$), but their combinations lead to a good upper bound for the optimum solution $\lambda_{OPT}$.

For clarity and simplicity of exposition, we assume here that $(V,E_{base})$ and $(V,E_{cand})$ are bounded degree graphs with the maximum degree $\Delta$. Our algorithm uses a natural semidefinite relaxation that was also used by Ghosh and Boyd . We introduce a variable $w_{e}$ (the weight of the edge $e$) for each candidate edge $e\in E_{cand}$; add constraints that all edge weights are between and $1$, and the total weight is at most $k$. Then we require that $\lambda_{2}(\mathcal{L}_{G}+\sum_{e}w_{e}\mathcal{L}_{e})\geq\lambda_{SDP}$ (where $\mathcal{L}_{e}$ is the Laplacian of the edge $e$). We do that by adding an SDP constraint $\mathcal{L}_{G}+\sum_{e}w_{e}\mathcal{L}_{e}\succeq\lambda_{SDP}P_{(1,\dots,1)^{\perp}}$, where $P_{(1,\dots,1)^{\perp}}$ is the projection on the space orthogonal to $(1,\dots,1)^{\perp}$. We get the following SDP relaxation.

We solve the semidefinite program and obtain solution $\{w_{e}\}_{e\in E_{cand}}$. The total weight of all edges is $k$, however, the number of edges involved, or the support of the solution could be significantly higher than $k$.

The value of the optimal solution, $\lambda_{OPT}$, is at most $\lambda_{k+2}(\mathcal{L}_{G})$.

There is a polynomial time approximation algorithm that finds a solution of value at least $c\lambda_{OPT}^{2}/\Delta$ supported on at most $8k$ edges with total weight at most $k$. If $k\geq n$ the algorithm finds a constant factor approximation.

We present two corollaries for special instances of the problem.

If it is possible to make $G$ an expander by adding $k$ edges (and thus $\lambda_{OPT}\sim\Delta$), then the algorithm finds a constant factor approximation.

Note that if the graph formed by candidate edges is an expander then the value of the following SDP solution $w_{e}=k/|E_{cand}|$ for each edge $e\in E_{cand}$ is $\Omega(k/n)$, thus $\lambda_{SDP}\geq ck/n$.

If the graph formed by candidate edges is an expander, then the approximation algorithm from Theorem 5.2 finds a solution of value at least $c\frac{k}{n\Delta}\lambda_{OPT}$.

It is possible to get rid of the dependence on $\Delta$ in Theorem 5.2 and Corollary 5.4 and obtain approximation guarantees of $c\min(\lambda_{OPT},\lambda_{OPT}^{2})$ and $\frac{ck}{n}\lambda_{OPT}$ respectively. We omit the details in this extended abstract.

References