Embedding the structural properties of nodes: Riding the GraphWave.

Original article was published on Deep Learning on Medium

How does GraphWave work?

Let’s begin by demonstrating how GraphWave addresses a deficiency in other algorithms; that being the inability to capture the structural similarities of nodes.

Figure 1 — graph showing nodes coloured by their structural role

The plot below (Figure 2) shows how the Node2Vec algorithm encodes the graph at Figure 1, and its limitations. The nodes at the left and right cluster are far apart from each other which renders them far apart in the Node2Vec embedding space, despite the structure around these nodes being visually very similar.

Figure 2 — Plot showing how Node2Vec algorithm encodes node structure at Figure 1. Principle component analysis (PCA) has been used to reduce the dimensionality of the embeddings from GraphWave so the similarity can be plotted.

The GraphWave algorithm is a way to capture the structural similarities of the nodes.

To exemplify this, consider a sound signal travelling from the bottom left node. This signal travels around the graph and will be louder at closer nodes, and quieter at more distant nodes. Figure 3 shows what this might look like with “louder” nodes coloured darker, and Figure 4 is a histogram of these volumes:

Figure 3: Sound signal travelling from the bottom left node and diffused through the graph
Figure 4: Histogram of signal intensities

If the sound signal originates from the bottom right node instead, the volume at each node will be different. However, because this node has the same number of neighbours, and each of those neighbours has the same number of neighbours (and so on), when we look at the histogram of volumes, it’s identical:

Figure 5: Sound signal travelling from the bottom right node and diffused through the graph
Figure 6: Histogram of signal intensities

The basic idea of GraphWave is to diffuse signals throughout the graph for each node, and encode the diffused signal histograms as vectors (Figure 7). In the case of our example graph, the embeddings of structurally similar nodes almost completely overlap.

Figure 7 — GraphWave diffuses signals throughout the graph for each node, encoding the diffused signal histograms as vectors.

The mathematics

GraphWave leverages spectral graph theory to calculate the diffusion of signals across the graph. Spectral graph theory examines the eigenvalues, eigenvalues of the graph adjacency and Laplacian matrix to derive information about the graph. In our case we’re interested in the graph Laplacian matrix, defined as:

Now we decompose the graph Laplacian into eigenvalues and eigenvectors noting that the Laplacian in symmetric:

Where U are the eigenvectors, and the 𝜆 are the eigenvalues. We can filter the graph Laplacian by applying a filter to the eigenvalues, in our case an exponential low-pass filter, getting:

Where the 𝚿ij is amount of signal transferred to node j from node i . So the column i has the signal intensities/volumes we talked about earlier.

Now that we’ve got our signal intensities, how do we turn this into a vector? We consider 𝚿ij as a probability distribution. A probability distribution can be fully characterised by its characteristic function:

We can estimate this function at several values of t by:

We can concatenate the real and imaginary values for many values of t to get a vector representing the characteristic function of the signal diffusion of the node i. And that’s it; GraphWave in a nutshell!