# Beyond the Expanders

Authors: Marianna Bolla
Journal: International Journal of Combinatorics
 (2011)

---

## Abstract

Expander graphs are widely used in communication problems and construction of error
correcting codes. In such graphs, information gets through very quickly. Typically, it is not true for social or biological networks, though we may find a partition of the vertices such that the induced subgraphs on them and the bipartite subgraphs between any pair of them exhibit regular behavior of information flow within or between the vertex subsets. Implications between spectral and regularity properties are discussed.


---

## Body

## 1. Introduction

We want to go beyond the expander graphs that—for four decades—have played an important role in communication networks; for a summary, see for example, Chung [1] and Hoory et al. [2]. Roughly speaking, the expansion property means that each subset of the graph’s vertices has “many” neighbors (combinatorial view), and hence, information gets through such a graph very “quickly” (probabilistic view). We will not give exact definitions of an expander here as those contain many parameters which are not used later. We rather refer to the spectral and random walk characterization of such graphs, as discussed, among others by Alon [3] and Meilă and Shi [4].The general framework of an edge-weighted graph will be used. Expanders have a spectral gap bounded away from zero, where—for a connected graph—this gap is defined as the minimum distance between the normalized Laplacian spectrum (apart from the trivial zero eigenvalue) and the endpoints of the[0,2] interval, the possible range of the spectrum. The larger is the spectral gap, the more our graph resembles a random graph and exhibits some quasirandom properties, for example, the edge densities within any subset and between any two subsets of its vertices do not differ too much of what is expected, see the Expander Mixing Lemma 2.2 of Section 2. Quasirandom properties and spectral gap of random graphs with given expected degrees are discussed in Chung and Graham [5] and Coja-Oghlan and Lanka [6].However, the spectral gap appears not at the ends of the normalized Laplacian spectrum in case of generalized random or generalized quasirandom graphs that, in the presence ofk≥2 underlying clusters, have k eigenvalues (including the zero) separated from 1, while the bulk of the spectrum is located around 1, see for example, [7]. These structures are usual in social or biological networks having k clusters of vertices (that belong to social groups or similarly functioning enzymes) such that the edge density within the clusters and between any pair of the clusters is homogeneous. Such a structure is theoretically guaranteed for any large graph by the Szemerédi Regularity Lemmas [8] with possibly large k, where k does not depend on the number of vertices, it merely depends on the constant ruling the regularity of the cluster pairs.Our conjecture is thatk so-called structural eigenvalues (separated from 1) in the normalized Laplacian spectrum are indications of such a structure, while the near 1 eigenvalues are responsible for the pairwise regularities. The clusters themselves can be recovered by applying the k-means algorithm for the vertex representatives obtained by the eigenvectors corresponding to the structural eigenvalues (apart from the zero). For the k=2 case, we will give an exact relation between the eigenvalue separation (of the nontrivial structural eigenvalue from the bulk of the spectrum) and the volume regularity of the cluster pair that is obtained by the k-means algorithm applied for the coordinates of the transformed eigenvector belonging to the nontrivial structural eigenvalue, see Theorem 3.1 of Section 3. To eliminate the trivial eigenvalue-eigenvector pair, we shall rather use the normalized modularity spectrum of [9] that plays an important role in finding the extrema of some penalized versions of the Newman-Girvan modularity introduced in [10].


## 2. Preliminaries and Statement of Purpose

LetG=(V,W) be a graph on n vertices, where the n×n symmetric matrix W has nonnegative real entries and zero diagonal. Here wij is the similarity between vertices i and j, where 0 similarity means no connection/edge at all. A simple graph is a special case of it with 0-1 weights. Without loss of generality,(2.1)∑i=1n∑j=1nwij=1
will be supposed. Hence, W is a joint distribution, with marginal entries (2.2)di=∑j=1nwij,i=1,…,n,
which are the generalized vertex degrees collected in the main diagonal of the diagonal degree matrixD=diag(d), d=(d1,…,dn)T. In [11, 12], we investigated the spectral gap of the normalized LaplacianLD=I-D-1/2WD-1/2, where I denotes the identity matrix of appropriate size.Suppose that our graph is connected (W is irreducible). Let 0=λ1<λ2≤···≤λn≤2 denote the eigenvalues of the symmetric normalized Laplacian LD with corresponding unit-norm, pairwise orthogonal eigenvectors u1,…,un. Namely, u1=(d1,…,dn)T=d. In the random walk setup, D-1W is the transition matrix (its entry in the (i,j)th position is the conditional probability of moving from vertex i to vertex j in one step, given that we are in i) which is a stochastic matrix with eigenvalues 1-λi and corresponding eigenvectors D-1/2ui(i=1,…,n). “Good” expanders have a λ2 bounded away from zero, that also implies the separation of the isoperimetric number(2.3)h(G)=min⁡U⊂V:Vol(U)≤1/2e(U,U¯)Vol(U),
where for X,Y⊂V: e(X,Y)=∑i∈X∑j∈Ywij is the weighted cut between X and Y, while Vol(U)=∑i∈Udi is the volume of U⊂V. In view of (2.1), Vol(V)=1, this is why the minimum is taken on vertex sets having volume at most 1/2. In [12], we proved that(2.4)12λ2≤h(G)≤min⁡{1,2λ2},
while in the λ2≤1 case the stronger upper estimation (2.5)h(G)≤λ2(2-λ2)
holds.If a network does not have a “large”λ2 (compared to the natural lower bound), or equivalently—in view of the above inequalities—it has a relatively “small” isoperimetric number, then the 2-partition of the vertices giving the minimum in (2.3) indicates a bottleneck, or equivalently, a low conductivity edge-set between two disjoint vertex clusters such that the random walk gets through with small probability between them, but—as some equivalent notions will indicate—it is rapidly mixing within the clusters. To find the clusters, the coordinates of the transformed eigenvector D-1/2u2 will be used. In [11], we proved that for the weighted 2-variance of this vector's coordinates(2.6)S22(D-1/2u2)≤λ2λ3
holds. For a general 2≤k≤n, the notion of k-variance—in the Analysis of Variance sense—is the following. The weighted k-variance of the k-dimensional vertex representatives x1,…,xn comprising the row vectors of the n×k matrix X is defined as (2.7)Sk2(X)=min⁡Pk∈PkSk2(Pk,X)=min⁡Pk=(V1,…,Vk)∑a=1k∑j∈Vadj∥xj-ca∥2,
where ca=(1)/Vol(Va)∑j∈Vadjxj is the weighted center of clusterVa (a=1,…,k) and 𝒫k denotes the set of k-partitions of the vertices. We remark that S22(D-1/2u1,D-1/2u2)=S22(D-1/2u2), since D-1/2u1=1 is the all 1’s vector.The above results were generalized for minimizing the normalizedk-way cut(2.8)fk(Pk,G)=∑a=1k-1∑b=a+1k(1Vol(Va)+1Vol(Vb))e(Va,Vb)=k-∑a=1ke(Va,Va)Vol(Va)
of the k-partition Pk=(V1,…,Vk) over the set of all possible k-partitions. Hence, (2.9)fk(G)=min⁡Pk∈Pkfk(Pk,G)
is the minimum normalized k-way cut of the underlying weighted graph G=(V,W). In fact, f2(G) is the symmetric version of the isoperimetric number and f2(G)≤2h(G). In [12], we proved that(2.10)∑i=1kλi≤fk(G)≤c2∑i=1kλi,
where the upper estimation is relevant only in the case when Sk2(D-1/2u1,…,D-1/2uk) is small enough and the constant c depends on this minimum k-variance of the vertex representatives.Thenormalized Newman-Girvan modularity is defined in [9] as the penalized version of the Newman-Girvan modularity [10] in the following way. The normalized k-way modularity of Pk=(V1,…,Vk) is(2.11)Qk(Pk,G)=∑a=1k1Vol(Va)∑i,j∈Va(wij-didj)=∑a=1k1Vol(Va)[e(Va,Va)-Vol2(Va)]=∑a=1ke(Va,Va)Vol(Va)-1=k-1-fk(Pk),(2.12)Qk(G)=max⁡Pk∈PkQk(Pk,G)
is the maximum normalized k-way Newman-Girvan modularity of the underlying weighted graph G=(V,W). For given k, maximizing this modularity is equivalent to minimizing the normalized cut and can be solved by the same spectral technique. In fact, it is more convenient to use the spectral decomposition of the normalized modularity matrix BD=I-LD-ddT with eigenvalues β1≥···≥βn, that are the numbers 1-λi with eigenvectors ui (i=2,…,n) and the zero with corresponding unit-norm eigenvector d. In [9, 12], we also show that a spectral gap between λk and λk+1 is an indication of k clusters with low intercluster connections; further, the intracluster connections (wij) between vertices i and j of the same cluster are higher than expected under the hypothesis of independence (in view of which vertices i and j are connected with probability didj). In the random walk framework, the random walk stays within the clusters with high probability.Conversely, minimizing the above modularity will result in clusters with high inter- and low intra-cluster connections. In [9], we proved that(2.13)min⁡Pk∈PkQk(Pk,G)≥∑i=1kβn+1-i.
The existence of k “large” (significantly larger than 1) eigenvalues in the normalized Laplacian spectrum, or equivalently, the existence of k negative eigenvalues (separated from 0) in the normalized modularity spectrum is an indication of k clusters with the above property. In the random walk setup, the walk stays within the clusters with low probability.These two types of network structures are frequently called community or anticommunity structure. Some networks exhibit a more general, still regular behavior: the vertices can be classified intok clusters such that the information-flow within them and between any pair of them is homogeneous. In terms of random walks, the walk stays within clusters or switches between clusters with probabilities characteristic for the cluster pair. That is, if the random walk moves from a vertex of cluster Va to a vertex of cluster Vb, then the probability of doing this does not depend on the actual vertices, it merely depends on their cluster memberships, a,b=1,…,k.In this context, we examined the following generalized random graph model, that corresponds to the ideal case: given the number of clustersk, the vertices of the graph independently belong to the clusters; further, conditioned on the cluster memberships, vertices i∈Va and j∈Vb are connected with probability pab, independently of each other, 1≤a,b≤k. Applying the results [7] for the spectral characterization of some noisy random graphs, we are able to prove that the normalized modularity spectrum of a generalized random graph is the following: there exists a positive number δ<1, independent of n, such that there are exactly k-1 so-called structural eigenvalues of BD that are greater than δ-o(1), while all the others are o(1) in absolute value. It is equivalent that LD has k eigenvalues (including the zero) separated from 1.Thek=1 case corresponds to quasirandom graphs, and the above characterization corresponds to the eigenvalue separation of such graphs, discussed in [5]. The authors also prove some implications between the so-called quasirandom properties. For example, for dense graphs, “good” eigenvalue separation is equivalent to “low” discrepancy (of the induced subgraphs’ densities from the overall edge density).For thek≥2 case, generalized quasirandom graphs were introduced by Lovász and Sós [13]. These graphs are deterministic counterparts of generalized random graphs with the same spectral properties. In fact, the authors define so-called generalized quasirandom graph sequences by means of graph convergence that also implies the convergence of spectra. Though, the spectrum itself does not carry enough information for the cluster structure of the graph, together with some classification properties of the structural eigenvectors it does. We want to prove some implication between the spectral gap and the volume-regularity of the cluster pairs, also using the structural eigenvectors.The notion of volume regularity was introduced by Alon et al. [14]. We shall use a slightly modified version of this notion.Definition 2.1.
LetG=(V,W) be weighted graph with Vol(V)=1. The disjoint vertex pair (A,B) is α-volume regular if for all X⊂A, Y⊂B we have
(2.14)|e(X,Y)-ρ(A,B)Vol(X)Vol(Y)|≤αVol(A)Vol(B),
where ρ(A,B)=e(A,B)/Vol(A)Vol(B) is the relative inter-cluster density of (A,B).Our definition was inspired by the Expander Mixing Lemma stated for example, in [2] for regular graphs and in [1] for simple graphs in the context of quasirandom properties. Now we formulate it for edge-weighted graphs on a general degree sequence. We also include the proof as a preparation for the proof of Theorem 3.1 of Section 3.Lemma 2.2 (Expander Mixing Lemma for Weighted Graphs).
LetG=(V,W) be a weighted graph and suppose that Vol(V)=1. Then for all X,Y⊂V:
(2.15)|e(X,Y)-Vol(X)Vol(Y)|≤∥BD∥⋅Vol(X)(1-Vol(X))Vol(Y)(1-Vol(Y))≤∥BD∥⋅Vol(X)Vol(Y),
where ∥BD∥ is the spectral norm of the normalized modularity matrix of G.Proof.
LetX⊂A, Y⊂B, and 1U∈ℝn denote the indicator vector of U⊂V. Further, x:=D1/21X and y:=D1/21Y.
We use the spectral decompositionD-1/2WD-1/2=∑i=1nρiuiuiT, where ρi=1-λi (i=2,…,n) are eigenvalues of BD and ρ1=1 with corresponding unit-norm eigenvector u1=d=D1/21. We remark that u1 is also an eigenvector of BD corresponding to the eigenvalue zero, hence ∥BD∥=maxi≥2|ρi|. Let x=∑i=1naiui and y=∑i=1nbiui be the expansions of x and y in the orthonormal basis u1,…,un with coordinates ai=xTui and bi=yTui, respectively. Observe that a1=Vol(X), b1=Vol(Y) and ∑i=1nai2=∥x∥2=Vol(X), ∑i=1nbi2=∥y∥2=Vol(Y). Based on these,(2.16)|e(X,Y)-Vol(X)Vol(Y)|=|∑i=2nρiaibi|≤‖BD‖⋅|∑i=2naibi|≤‖BD‖⋅∑i=2nai2∑i=2nbi2≤‖BD‖⋅Vol(X)(1-Vol(X))Vol(Y)(1-Vol(Y))≤‖BD‖⋅Vol(X)Vol(Y),
where we also used the triangle and the Cauchy-Schwarz inequalities.We remark that the spectral gap ofG is 1-∥BD∥; hence—in view of Lemma 2.2—the density between any two subsets of “good” expanders is near to what is expected. On the contrary, in the above definition of volume regularity, the X,Y pairs are disjoint, and a “small” α indicates that the (A,B) pair is like a bipartite expander, see for example, [1].In the next section, we shall prove the following statement for thek=2 case: if one eigenvalue jumps out of the bulk of the normalized modularity spectrum, then clustering the coordinates of the corresponding transformed eigenvector into 2 parts (by minimizing the 2-variance of its coordinates) will result in an α-volume regular partition of the vertices, where α depends on the spectral gap.Our conjecture is that we may go further: ifk-1 (so-called structural) eigenvalues jump out of the normalized modularity spectrum, then clustering the representatives of the vertices—obtained by the corresponding eigenvectors in the usual way—into k clusters will result in α-volume regular pairs, where α depends on the spectral gap (between the structural eigenvalues and the bulk of the spectrum) and the k-variance of the vertex representatives based on the eigenvectors corresponding to the structural eigenvalues.


## 3. Eigenvalue Separation and Volume Regularity (k=2 Case)

Theorem 3.1.
LetG=(V,W) is an edge-weighted graph on n vertices, with generalized degrees d1,…,dn and D=diag(d1,…,dn). Suppose that Vol(V)=1 and there are no dominant vertices: max1≤i≤ndi=o(1) as n→∞. Let the eigenvalues of D-1/2WD-1/2, enumerated in decreasing absolute values, be
(3.1)1=ρ1>|ρ2|=δ>ε=|ρ3|≥|ρi|,i≥4.
The partition (A,B) of V is defined in such a way that it minimizes the weighted 2-variance of the coordinates of D-1/2u, where u is the unit-norm eigenvector belonging to ρ2. Then the (A,B) pair is 𝒪((1-δ)/(1-ε)) -volume regular.Remark 3.2.
The statement of Theorem3.1 has relevance only if δ is much larger than ε. In this case, the spectral gap between the largest absolute value eigenvalue and the others in the normalized modularity spectrum indicates a regular 2-partition of the graph that can be constructed based on the eigenvector belonging to the structural eigenvalue.Remark 3.3.
The statement of the above theorem also has relevance in the dense case (supported by the condition that there are no dominant vertices). We remark that in the sparse case there is an exceptional set comprising low degree vertices. Authors of [14] prove equivalences of quasirandom properties for the core of the graph (the vertex set deprived of the exceptional set). Using the modularity spectrum of this core, the above theorem remains valid for it.Proof of Theorem3.1.
We use the notations in Lemma2.2’s proof. Let X⊂A, Y⊂B. For short, x:=D1/21X, y:=D1/21Y, a:=D1/21A, and b:=D1/21B. With the notations ρ=ρ(A,B) and M=W-ρddT,
(3.2)|e(X,Y)-ρVol(X)Vol(Y)|=|1XTM1Y|=|xT(D-1/2WD-1/2-ρddT)y|.
Using the spectral decomposition D-1/2WD-1/2=∑i=1nρiuiuiT and the fact that u1=d=D1/21, we can write (3.2) as
(3.3)|(1-ρ)a1b1+ρ2a2b2+∑i=3nρiaibi|,
where x=∑i=1naiui and y=∑i=1nbiui is the expansion of x and y in the orthonormal basis u1,…,un with coordinates ai=xTui and bi=yTui, respectively.
By Lemma2.2, for all X,Y⊂V:(3.4)|ρ(X,Y)-1|≤∥BD∥⋅1-Vol(X)Vol(X)⋅1-Vol(Y)Vol(Y),
that is also applicable to the special two-partition A,B⊂V satisfying the postulates. Hence, |1-ρ| is governed by the spectral norm |ρ2| of the normalized modularity matrix. In [11], as a by-product of the proof of (2.6) it came out that to get the partition (A,B), the coordinates of D-1/2u2 should be divided into two parts at the median, hence Vol(A) and Vol(B) are approximately equal to 1/2 (the approximation is good for large n if the underlying graph does not have dominant vertex-weights). Further, the estimation
(3.5)S22(D-1/2u2)≤λ2λ3≤1-ρ21-ɛ≤1-δ1-ɛ
also follows. This applies to the ρ2=1-λ2 case. In the ρ2=1-λn case, the optimum A,B is obtained by minimizing the 2-variance of the coordinates of the transformed eigenvector D-1/2un for which the following relation—like (2.6)—can be proved:
(3.6)S22(D-1/2un)≤2-λn2-λn-1≤ρ2+11-ɛ≤1-δ1-ɛ,
and the optimum cut-point of the coordinates D-1/2un is also not far from the median. Summarizing, |1-ρ|≤|ρ2|+η, where η=o(1).
Therefore, (3.3) can be estimated from above with(3.7)|ρ2|⋅|a1b1+a2b2|+ηa1b1+ɛ⋅|∑i=3naibi|.
As for the second term, ηa1b1=ηVol(X)Vol(Y).
Using the Cauchy-Schwarz inequality, the last term can be estimated from above with(3.8)ɛ∑i=3nai2∑i=3nbi2≤ɛ∑i=2nai2∑i=2nbi2≤ɛVol(X)(1-Vol(X))Vol(Y)(1-Vol(Y))≤ɛVol(X)Vol(Y)≤ɛVol(A)Vol(B),
since a1=Vol(X), b1=Vol(Y) and ∑i=1nai2=∥x∥2=Vol(X), ∑i=1nbi2=∥y∥2=Vol(Y). The first term is reminiscent of an equation for the coordinates of orthogonal vectors. Therefore, we project the vectors u1, u2 onto the subspace F=Span{a,b}. In fact, u1=a+b, therefore u1∈F. The vector u2 can be decomposed as
(3.9)u2=u2TaVol(A)a+u2TbVol(B)b+q,
where q is the component orthogonal to F. For the squared distance ∥q∥2 between u2 and F, in [11], we proved that it is equal to the weighted 2-variance S22(D-1/2u2) and in (3.5) we estimated it from above with (1-δ)/(1-ɛ). In the ρ2=1-λn case similar estimation works using (3.6). First we estimate (u1Ta)(u1Tb)+(u2Ta)(u2Tb). The problem is that the pairwise orthogonal vectors u1,u2 and a,b are not in the same subspace of ℝn as, in general, u2∉F. However, by an argument proved in [11], we can find orthogonal, unit-norm vectors ũ1,ũ2∈F such that
(3.10)‖u1-ũ1‖2+‖u2-ũ2‖2≤2s2,
where, in view of u1∈F, ũ1=u1. Let r:=u2-ũ2. Since ũ1Ta,ũ2Ta and ũ1Tb,ũ2Tb are coordinates of the orthogonal vectors a,b in the basis ũ1,ũ2,
(3.11)(ũ1Ta)(ũ1Tb)+(ũ2Ta)(ũ2Tb)=0,
and because of ũ2Ta+ũ2Tb=ũ2Tu1=0,
(3.12)ũ2Ta=-ũ2Tb=Vol(A)Vol(B)=:c.
Therefore,
(3.13)|(u1Ta)(u1Tb)+(u2Ta)(u2Tb)|=|Vol(A)Vol(B)+[(ũ2+r)Ta,(ũ2+r)Tb]|=|Vol(A)Vol(B)+(c+rTa)⋅(-c+rTb)|=|c(-rTa+rTb)+(rTa)(rTb)|≤|c|‖r‖2‖b-a‖2+‖r‖2‖a‖2‖r‖2‖b‖2≤Vol(A)Vol(B)(‖r‖+‖r‖2)≤Vol(A)Vol(B)(2s+2s2),
using (3.10) and the fact that ∥b-a∥2=1.
Now we estimatea1b1+a2b2=(u1Tx)(u1Ty)+(u2Tx)(u2Ty). Going back to (3.9), we have(3.14)u2Tx=u2TaVol(A)aTx+u2TbVol(B)bTx+qTx=Vol(X)Vol(A)u2Ta+qTx,
and similarly,
(3.15)u2Ty=u2TaVol(A)aTy+u2TbVol(B)bTy+qTy=Vol(Y)Vol(B)u2Tb+qTy,
that in view of ∥q∥2=s2 yields
(3.16)|(u1Tx)(u1Ty)+(u2Tx)(u2Ty)|=|Vol(X)Vol(Y)+(Vol(X)Vol(A)u2Ta+qTx)(Vol(Y)Vol(B)u2Tb+qTy)|≤|Vol(X)Vol(Y)+(Vol(X)Vol(A)u2Ta)(Vol(Y)Vol(B)u2Tb)|+|(qTx)(Vol(Y)Vol(B)u2Tb)+(qTy)(Vol(X)Vol(A)u2Ta)+(qTx)(qTy)|≤Vol(X)Vol(A)Vol(Y)Vol(B)|Vol(A)Vol(B)+(u2Ta)(u2Tb)|+‖q‖‖x‖Vol(Y)Vol(B)‖u2‖‖b‖+‖q‖‖y‖Vol(X)Vol(A)‖u2‖‖a‖+‖q‖2‖x‖‖y‖≤Vol(A)Vol(B)(2s+2s2)+‖q‖Vol(X)Vol(Y)Vol(B)Vol(B)+‖q‖Vol(Y)Vol(X)Vol(A)Vol(A)+‖q‖2Vol(X)Vol(Y)=Vol(A)Vol(B)(2s+2s2)+‖q‖Vol(X)Vol(Y)×(Vol(Y)Vol(B)+Vol(X)Vol(A)+‖q‖)≤Vol(A)Vol(B)[2s+2s2+s(2+s)]=Vol(A)Vol(B)[(2+2)s+3s2]≤Vol(A)Vol(B)(2+5)s≤Vol(A)Vol(B)(2+5)1-δ1-ε.
Summarizing, the second and third terms in (3.7) are estimated from above with ηVol(X)Vol(Y)≤ηVol(A)Vol(B) and ɛVol(A)Vol(B), respectively. Because of η=o(1) and ε<δ, by an easy calculation it follows that they are less than (1-δ)/(1-ε) for n “large” enough. Therefore, α=2+7 will do.



---

*Source: 787596-2011-06-28.xml*