Graph coarsening with spectral and cut guarantees

This post complements my recent paper Graph reduction by local variation, a follow up of Spectrally Approximating Large Graphs with Smaller Graphs published in ICML 2018. The research was kindly supported by the Swiss National Science Foundation.

You can download the code here and the slides of my presentation here. If you find this useful, consider citing the above papers.

Andreas Loukas,
November 1st 2018


Problem setup

We will consider three representative networks:

  • minnesota: a road network consisting of 2642 nodes
G = graphs.Minnesota()
  • airfoil: a mesh consisting of 4000 nodes.
G = graphs.Airfoil()
G = graphs.Graph(G.W[:,:4000][:4000,:], G.coords[:4000,:])
  • yeast: consists of protein-to-protein interactions in budding yeast. The data were taken from networkrepository.com. I am not sure of the source, unfortunately. After keeping only the giant component, the graph consists of 819 nodes.
W = np.load('./data/bio-yeast.npy')
G = graphs.Graph(W = W[0:1000,0:1000])
if not G.is_connected(): G,_ = graph_utils.get_giant_component(G)

For the yeast network we will also need to compute some node coordinates using graphviz. This will help us visualize things later on.

if not hasattr(G, 'coords'): 
   graph = nx.from_scipy_sparse_matrix(G.W)
   pos = nx.nx_agraph.pygraphviz_layout(graph, prog='neato')  
   G.set_coordinates(np.array(list(pos.values())))

Let’s do some local variation coarsening

We focus on the following two methods:

  • variation_edges: contracts edges
  • variation_neighborhood: contracts sets formed by node neighborhoods

There are two parameters we need to set:

  • First the dimensionality reduction ratio r = 1 - n/N controls how many nodes to remove. Remember, N is the size of the original graph and n the target size.
  • The parameter k is the size of the eigenspace we are interested in preserving.
# Parameters
r = 0.5  
k = 10

To coarsen our graph, we simply execute the following:

C, Gc, Call, Gall = coarsen(G, K=k, r=r, method='variation_neighborhood')

Visual inspection

We use the following utility function to inspect the result

fig = plot_coarsening(Gall, Call);

This will plot c+1 graphs in total, where c is the number of levels. The left-most is the original graph and the right-most is the final coarse graph. Colors are used to indicate the size of each contraction set C:

  • green is for |C|=2 blue is for |C|=3, red is for |C|=4, and yellow for |C|>4

Below, I illustrate the code output for all three graphs and both coarsening methods.

minnesota_neighborhood

minnesota_edges.pngairfoil_neighborhoodairfoil_edges

yeast_neighborhoodyeast_edges

Few general remarks:

  • Selecting larger contraction sets (as the neighborhood variation method does) means that we generally need fewer levels of coarsening and often yields better results.
  • In many instances it is difficult to say why the algorithm choose what it did. Informally, the methods aim to reduce a graph such that what is smooth remains smooth also after coarsening. It is an interesting and non-trivial consequence then that all good cuts of the original large graph will also be (approximately) preserved in the coarse graph.

Some quantitative results

We consider three metrics for coarsening quality:

  • (Left) The restricted similarity \epsilon is defined such that, for every x \in span(U_k) we have

(1 - \epsilon) x^\top L x \leq x_c^\top L_c x_c \leq (1+\epsilon) x^\top L x.

Note that U_k consists of the first k eigenvectors of the Laplacian L associated with G.

  • (Center) The relative eigenvalue error is computed as

\frac{\lambda_i - \tilde{\lambda}_i}{\lambda_i} for every i = 1, \ldots, k, \ldots,

where $latex\lambda_i$ and \tilde{\lambda}_i are respectively the eigenvalues of the Laplacian L of G and L_c of G_c.

  • (Right) The angle matrix contains the angles between the eigenvectors of L (y-axis) and the lifted eigenvectors of L_c. The closer to counter-diagonal it is, the better.

I will only show the results for the neighborhood-based method.

Minnesota graph:quantitative_minnesota-e1541437256626.pngAirfoil graph:quantitative_airfoil.pngYeast graph:quantitative_yeast.png

For reference, in the paper I also include exhaustive comparison with other standard methods for graph coarsening (heavy edge, kron reduction, affinity, algebraic distance) that can be found in the literature.

What about the signals?

Finally, let’s inspect how coarsening affects the information defined on the nodes of a graph (i.e., graph signals in the GSP lingo).  The code is as follows:

size = 2.04; fig, axes = plt.subplots(2, 2, figsize=(2*size*4, 2*3*size)); lineWidth = 1

# a random smooth signal 
x = G.U[:,:k] @ np.random.randn(k,1)
x = x / np.linalg.norm(x)
G.plot_signal(x, ax=axes[0][0], title='signal')

# coarsen it 
xc = coarsen_vector(x, C)
Gc.plot_signal(xc, ax=axes[0][1], title='coarsened signal')

# lift it 
xp = lift_vector(xc, C)
G.plot_signal(xp, ax=axes[1][0], title='lifted signal')

# reconstruction error
G.plot_signal(np.abs(x-xp), ax=axes[1][1], title='reconstruction error')

print('signal error: {}'.format(np.linalg.norm(x - xp)))

Again, I show only the results for the neighborhood-based method.

Minnesota graph:

signal error: 0.022988891880551716

signal_minnesota.png

Airfoil graph:

From the small reconstruction error it can be deduced that smooth signals are almost unaffected by coarsening. This is an indirect consequence of optimizing restricted similarity. Indeed, the signal of interest is unknown at coarsening time.

 

Advertisements

1 Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s