Combinatorics (Fall 2010)/Graph spectrum, expanders

From EtoneWiki
Jump to: navigation, search

Graph Expansion

According to wikipedia:

"Expander graphs have found extensive applications in computer science, in designing algorithms, error correcting codes, extractors, pseudorandom generators, sorting networks and robust computer networks. They have also been used in proofs of many important results in computational complexity theory, such as SL=L and the PCP theorem. In cryptography too, expander graphs are used to construct hash functions."

We will not explore everything about expander graphs, but will focus on the performances of random walks on expander graphs.

Expander graphs

Consider an undirected (multi)graph , where the parallel edges between two vertices are allowed.

Some notations:

  • For , let .
  • The Edge Boundary of a set , denoted , is .
Definition (Graph expansion)
The expansion ratio of an undirected graph on vertices, is defined as

Expander graphs are -regular (multi)graphs with and .

This definition states the following properties of expander graphs:

  • Expander graphs are sparse graphs. This is because the number of edges is .
  • Despite the sparsity, expander graphs have good connectivity. This is supported by the expansion ratio.
  • This one is implicit: expander graph is a family of graphs , where is the number of vertices. The asymptotic order and in the definition is relative to the number of vertices , which grows to infinity.

The following fact is directly implied by the definition.

An expander graph has diameter .

The proof is left for an exercise.

For a vertex set , the size of the edge boundary can be seen as the "perimeter" of , and can be seen as the "volume" of . The expansion property can be interpreted as a combinatorial version of isoperimetric inequality.

Vertex expansion
We can alternatively define the vertex expansion. For a vertex set , its vertex boundary, denoted is defined as that
,
and the vertex expansion of a graph is .

Existence of expander graph

We will show the existence of expander graphs by the probabilistic method. In order to do so, we need to generate random -regular graphs.

Suppose that is even. We can generate a random -regular graph as follows:

  • Let be the vertex set. Uniformly and independently choose cycles of .
  • For each vertex , for every cycle, assuming that the two neighbors of in that cycle is and , add two edges and to .

The resulting is a multigraph. That is, it may have multiple edges between two vertices. We will show that is an expander graph with high probability. Formally, for some constant and constant ,

.

By the probabilistic method, this shows that there exist expander graphs. In fact, the above probability bound shows something much stronger: it shows that almost every regular graph is an expander.

Recall that . We call such that a "bad ". Then if and only if there exists a bad of size at most . Therefore,

Let be the set of vertices in which has neighbors in , and let . It is obvious that , thus, for a bad , . Therefore, there are at most possible choices such . For any fixed choice of , the probability that an edge picked by a vertex in connects to a vertex in is at most , and there are such edges. For any fixed of size and of size , the probability that all neighbors of all vertices in are in is at most . Due to the union bound, for any fixed of size ,

Therefore,

The last line is when . Therefore, is an expander graph with expansion ratio with high probability for suitable choices of constant and constant .

Computation of graph expansion

Computation of graph expansion seems hard, because the definition involves the minimum over exponentially many subsets of vertices. In fact, the problem of deciding whether a graph is an expander is co-NP-complete. For a non-expander , the vertex set which has low expansion ratio is a proof of the fact that is not an expander, which can be verified in poly-time. However, there is no efficient algorithm for computing the unless NP=P.

The expansion ratio of a graph is closely related to the sparsest cut of the graph, which is the dual problem of the multicommodity flow problem, both NP-complete. Studies of these two problems revolutionized the area of approximation algorithms.

We will see right now that although it is hard to compute the expansion ratio exactly, the expansion ratio can be approximated by some efficiently computable algebraic identity of the graph.

Graph spectrum

Laplacian

The adjacency matrix of an -vertex graph , denoted , is an matrix where is the number of edges in between vertex and vertex .

Graph eigenvalues

Because adjacency matrix is a symmetric matrix with real entries, due to the Perron-Frobenius theorem, it has real eigenvalues , which associate with an orthonormal system of eigenvectors with . We call the eigenvalues of the spectrum of the graph .

The spectrum of a graph contains a lot of information about the graph. For example, supposed that is -regular, the following lemma holds.

Lemma
  1. for all .
  2. and the corresponding eigenvector is .
  3. is connected if and only if .
  4. If is bipartite then .
Proof.
Let be the adjacency matrix of , with entries . It is obvious that for any .
  • (1) Suppose that , and let be an entry of with the largest absolute value. Since , we have
and so
Thus .
  • (2) is easy to check.
  • (3) Let be the nonzero vector for which , and let be an entry of with the largest absolute value. Since , we have
Since and by the maximality of , it follows that for all that . Thus, if and are adjacent, which implies that if and are connected. For connected , all vertices are connected, thus all are equal. This shows that if is connected, the eigenvalue has multiplicity 1, thus .
If otherwise, is disconnected, then for two different components, we have and , where the entries of and are nonzero only for the vertices in their components components. Then . Thus, the multiplicity of is greater than 1, so .
  • (4) If if bipartite, then the vertex set can be partitioned into two disjoint nonempty sets and such that all edges have one endpoint in each of and . Algebraically, this means that the adjacency matrix can be organized into the form
where is a permutation matrix, which has no change on the eigenvalues.
If is an eigenvector corresponding to the eigenvalue , then which is obtained from by changing the sign of the entries corresponding to vertices in , is an eigenvector corresponding to the eigenvalue . It follows that the spectrum of a bipartite graph is symmetric with respect to 0.

The spectral gap

It turns out that the second largest eigenvalue of a graph contains important information about the graph's expansion parameter. The following theorem is the so-called Cheeger's inequality.

Theorem (Cheeger's inequality)
Let be a -regular graph with spectrum . Then

The theorem was first stated for Riemannian manifolds, and was proved by Cheeger and Buser (for different directions of the inequalities). The discrete case is proved independently by Dodziuk and Alon-Milman.

For a -regular graph, the value is known as the spectral gap. The name is due to the fact that it is the gap between the first and the second eigenvalue in the spectrum of a graph. The spectral gap provides an estimate on the expansion ratio of a graph. More precisely, a -regular graph has large expansion ratio (thus being an expander) if the spectral gap is large.


We will not prove the theorem, but we will explain briefly why it works.

For the spectra of graphs, the Cheeger's inequality is proved by the Courant-Fischer theorem in linear algebra. The Courant-Fischer theorem is a fundamental theorem in linear algebra which characterizes the eigenvalues by a series of optimizations:

Theorem (Courant-Fischer theorem)
Let be a symmetric matrix with eigenvalues . Then

For a -regular graph with adjacency matrix and spectrum , its largest eigenvalue with eigenvector . According to the Courant-Fischer theorem, the second largest eigenvalue can be computed as

and

The later is an optimization, which shares some resemblance of the expansion ratio , where is the characteristic vector of the set , defined as if and if . It is not hard to verify that and .

Therefore, the spectral gap and the expansion ratio both involve some optimizations with the similar forms. It explains why they can be used to approximate each other.

Reference

  • Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander Graphs and Their Applications. American Mathematical Society, 2006. [PDF]