On Near Optimal Spectral Expander Graphs of Fixed Size

In order to draw a regular graph we only need to check one criterion, that is, the product of number of vertices with degree of regularity is even. In our case we will only consider simple undirected graphs with no loops. From our first week of graph theory class we remember for a graph $G=(V,E)$ with degree of regularity $d$ we have.

We cannot satisfy this if $d$ and $|V|$ are both odd.

Thus we can split our regular graph generation into two cases for the parity of $d$. In the first, and easier case, we let $d$ be even. This allows us to pick any number of vertices (greater than $d$). The first step is to label our vertices $1$ to $|V|$ ( or 0 to $|V|-1$ mod $|V|$). And create the cycle graph $C_{|V|}$. This gives us a 2 regular graph. Now we iterate for $i=2$ to $d/2$ connecting $v_{n}$ to $v_{n+i}$. Below is pseudo which has been implemented in both Python(3) and Julia (1.4). This is a pseudo-code for generating the adjacency matrix of a regular graph. We assume that the product of vertices and degree of regularity is even.

Let’s take a look at three potential examples. These are all produced by the networkx package in Python. Figure 1 gives 4 regular graphs with no randomness the number of vertices and degrees of regularity are $(9,4),(12.4),(12,6),(14,5)$ respectively.

The general algorithm is quite straight forward once we have a regular graph in place. In plain English we algorithm looks something like:

1. 1.

   Pick two edges at random, swap one end point of each.

2. 2a.

   If the graph is still regular with the same degree and there are no loops accept the switch.

3. 2b.

   If not, pick again.

4. 3.

   Repeat until “sufficiently” randomized.

The supporting procedures of checking for loops (i.e. the diagonal of the adjacency matrixhas a nonzero element) and that the graph is still regular (all rows sum to the same degree) will be assumed. Now we come to the pseudo-code implementation of the graph randomization algorithm. First, we need the ability to switch edges. In the adjacency matrix representation the edges are represented by locations in the matrix which are 1. So the procedure getEdges is simply find the nonzero locations in the adjacency matrix

Now we give three pairs of examples. In order to show that we can use this to generate random graphs of nearly arbitrary degree. We’ll give examples of size (20,8), (30,13), and the much larger (500,25).

For the larger example, the plots are not so enligthening, but we shall show them here and give timing so that we can demonstrate the overall efficacy of our ability to randomize graphs of nearly arbitrary degree.

The second graph in 4 is the results of 1500 random edge switches and on the author’s laptop took 53.6s to complete.

And for posterity let’s examine the spectral propertires of these two graphs.

It’s clear from the spectrum that both graphs are 25 regular and that the randomized graph is closer to the semi-circular distribution than the nonrandom graph.

By the construction in §2.1 we achieve a regular graph of fixed size. In particular we build the adjacency matrix of a regular graph of fixed size. This construction, however, has a small spectral gap and a large graph diameter. Using our randomization scheme we wish to construct an adjacency matrix of a regular graph with a larger spectral gap. We have seen before [BB] that a random regular graph comes close to a Ramanujan bound for spectral expansion. The goal at present is to use our randomization scheme to search for ever larger spectral gaps. In reality, we will use a simulated annealer to minimize the normalized $\lambda_{2}$. Looking a little further down 8 shows how eigenvalues perform with single random switches.

We see that that randomization scheme first brings $\lambda_{2}$ to within the Ramanujan threshold quickly, but eventually moves above it. This does not, however, get to the weak bound of Alon-Bopanna, nor the strong bound. It is our goal to see how close we can get to these bounds. The striking feature or many graphs is how quickly we can cross the simple Ramanujan threshold.

The general structure of a simulated annealing algorithm is straight-forward:

1. 1.

   Guess a solution at random

2. 2.

   Score that solution

3. 3.

   Pick a “neighbor” solution

4. 4.

   Score the neighbor.

5. 5.

   If the neighbor is better, make it the new solution

6. 6.

   if neighbor is worse, still accept neighbor if not too far off

7. 7.

   Lower the algorithm’s “temperature”

8. 8.

   Repeat until satisfied

This is a gross oversimplification, but there are two salient points we need to consider. The first being: How do we pick an effective “neighbor” solution. The second being: How do we deal with the temperature parameter? Changes in either of this points can drastically affect the quality of solutions in a simulated annealer. In particular, lowering the temperature too quickly (i.e. quenching) tends to land a solution in the first deep local minimum the algorithm finds. On the other hand, lowering the temperature too slowly, takes too long and begins to look like a brute-force solution, which we don’t have time for.

In the case of the random regular graph, we will set our annealing algorithm to look for the lowest possible normalized $\lambda_{2}$ rather than the largest spectral gap. As it is set up, however, we will never achieve a bipartite graph as the second normalized eigenvalue is 1. In particular a bipartite graph of degree $d$ has eigenvalues $\pm d$, which we normalize and consider absolute values. Thus this algorithm ignores bipartite graphs as good expanders since we wish to achieve the steady state vector quickly by starting a random walk at a single vertex rather than in a superposition of vertices in different partition sets. We see, from the figure 8 that switching a pair of edges does well, however, for larger and sparser graphs, this takes too long. Consider, for example, a large cubic or 4-regular graph. That is a graph with several thousand vertices. A single edge switch does very little to affect the eigenvalue gap. Thus, one may consider using multiple edge swaps as the neighboring solution. This means that a “neighbor” graph should swap a dozen or so pairs of edges before measuring $\lambda_{2}$.

As with a standard annealing algorithm we want to move from essentially a random walk when the temperature is hot to a stochastic gradient descent type algorithm. We, however, wish to slow down not only the random selection of temporary solutions, but also slow down or speed up the edge switching as necessary. Thus we have decided to move from a simple single simulated annealer to a coupled annealer.

A single simulated annealer is an example of a Markov chain Monte Carlo method tuned for optimization as opposed to finding a posterior probability distribution. As discussed in the previous section we wish to couple multiple simulated annealing algorithms to find a solution which is closerto a global maximum. The idea of coupling was first (published) in the late 1990s [MNL] with an eye toward bimodal and multimodal distributions where MCMC algorithms are slow to converge. From the perspective of this work, we shall leverage multiple optimizers to look for a (closer to) global optimum. In order to tune our coupling we implement the following procedure:

1. 1.

   Initialize $N$ simulated annealers with initial temperatures $\tau_{1},\dots,\tau_{N}=1$ with different cooling rates $\alpha_{1}\dots,\alpha_{N}$ These are called chains.

2. 2.

   Each chain gets a different method of selecting a neighboring solution. For this work the $n^{th}$ chain has a neighbor selection of $n$ random edge switches.

3. 3.

   For each chain run one step of the simulated annealing algorithm and cool each chain $\tau_{i}\leftarrow\tau_{i}*\alpha_{i}$

4. 4.

   Rank order the chains by best solution. The best current solution gets the lowest temperature. This is the “cold chain.”

5. 5.

   Randomly select two other chains, score them and compute an acceptance probability for switching (or more simply one can simply exchange them without the extra computation).

6. 6.

   Select a number from a uniform variable $U\sim[0,1]$. If the acceptance probabilty is higher than the randomly drawn number, switch the chains. That is, switch their neighbor solutions, temperatures and cooling rates.

7. 7.

   Repeat steps 3-6 until the hottest chain has reached the temperature threshold, or we have reached an acceptable bound (e.g. We have found a Ramanujan graph, or reached a weak lower bound for $\lambda_{2}$).

For this section we will present the results as they were originally stated and then show the results for normalized eigenvalues. We will also let a graph $G=(V,E)$ have degree of regularity $d$ throughout.

There are several well-known constructions for families of Ramanujan graphs, in particular, LPS, Morgenstern, Paley, MSS, Zig-Zag, and Super-Singular Isogeny graphs. Additionally [F,BB] points out that with high probability a $d$-regular random graph is Ramanujan or near Ramanujan (ie $\lambda_{2}\leq 2\sqrt{d-1}+\varepsilon$)

The known constructions cover the following cases

We see now that the smallest positive integer for which a family of constructions is not known is $d=7$ for graphs with chromatic number 3 or more. We also have a few other small unknown cases $d=11,13,15,19,21,22,23,24$ Additionally, we see that there are some graphs with specific numbers of vertices which are not known in constructions. For example, the Zig-Zag product requires the number of vertices to be composite and Paley graphs have vertices which are elements of a finite field so we have powers of primes. In the case where $p\equiv 1\mod 4$ the smallest degree of regularity for a Paley graph is $(p-1)/2$ which quickly becomes quite large. We will explore some relatively smaller graphs for visualization purposes and some moderate sized graphs for the purposes of numerical demonstration.

To demonstrate the efficacy of the heuristic search involved, let’s begin with some well-known graphs which are near optimal, the fullerenes [AKS]. In particular we’ll look explicitly at the dodecahedron and the “bucky-ball.” These are well known 3-regular (cubic) graphs with 20 and 60 vertices respectively. To get our eyes adjusted to the way we will draw graphs, here are depictions of the respective fullerene graphs.

In our scenario we initialize two graphs, a 20 vertex 3-regular and a 60 vertex 3-regular which look like this.

These graphs are nowhere near expanders, much less optimal expanders. In particular the normalized threshold for a cubic graph to Ramanujan is $\lambda_{2}\leq 2\sqrt{2}/3\approx 0.9428$. In our case the initialized graphs have $\lambda_{2}\approx 0.96737$ for the 20 vertex graph and $\lambda_{2}\approx 0.99634$ for the 60 vertex graph.

Again, from [F,BB] we know with high probability that a random regular graph will be Ramanujan. So let’s follow two progressions randomly switching edges for each of these graphs and see how often they fall below the required threshold.

A couple of immediate observations. The smaller the graph, the easier it is to be a spectral expander. This agrees with our intuition about edge expanders as we require very few moves with a small number of vertices to reach any vertex via random walk when the graph is “small.” Larger graphs, however, require more moves and we see this in the fact that a single random switch affects $\lambda_{2}$ far less in the 60 vertex case than in the 20 vertex case. We also see that a vast majority of random regular graphs are below the Ramanujan threshold. In particular in two random trials of 499 graphs, we have 345 such graphs below the threshold in the 20 vertex case and 432 in the 60 vertex case. Additionally we have 68 and 196 graphs below the bucky ball line respectively. However, nothing gets below the dodecahedron line.

Consider now two graphs that we have generated with our Metropolis coupled simulated annealer. These are noth first run algorithms, and thus if we had tuned our parameters very specifically, we could have achieved lower eigenvalues.

Again we notice that neither of these graphs can quite hit the dodecahedon threshold, but they have both surpassed the bucky ball threshold easily as well as exceeding any graph achieved by single random switches.

Now for just a moment let’s turn our attention to 7-regular graphs. This is one of the cases which is not explicitly covered in known constructions. Drawing a graph with more than 60 or so vertices becomes rather unattractive on a page this small, so we will stick to 50 vertices for the sake of demonstration. In a timed run, we flagged the algorithm to stop once it had a achieved a Ramanujan graph. This particular 50 vertex, 7-regular graph cost the author’s laptop 1.1373 seconds of cpu time. The normalized threshold for a 7-regular graph is

As we can see, this is significantly lower than the required Ramanujan threshold. This is even below a weak optimal expander as defined in Equation 2.

Now consider a graph that we did not flag.

In the case of 7-regular graphs the thresholds we’re dealing with are

In nearly every case attempted by the author the heuristic optimizer was able to find a graph close to (and in many cases below) the weak optimal expansion constant. In every case, we were able to find a Ramanujan graph, but again, this is not surprising based on the work of [F] However, we were never able to find a graph which met the strict lower bound as given by [N]. In simple numerical trials we were able to find Ramanujan graphs with degree of regularity 7 for every (even) number of vertices between 8 and 2000. This work, however, does not answer the question of whether there is an explicit construction for such graphs.

While the drawing of a graph with 2000 vertices is not very attractive, we can still show the histogram of normalized eigenvalues to show the spectral expansion. Below is a histogram of a 2000 vertex 7-regular graph discovered by Metropolis coupled simulated annealing. The author has also added a spreadsheet of its adjacency matrix into github (email author for address) so that researchers can explore its random properties further at their desire.