Embedding the structural properties of nodes: riding the GraphWave.

Photo by Ant Rozetsky on Unsplash

GraphWave is a novel algorithm that effectively embeds the structural properties of nodes and provides valuable insights into the roles of nodes in our network datasets.

Graphs are complex, irregular objects that don’t play nice with our standard machine learning and data science toolkit. One way to wrangle these beasts into something more manageable is to use graph representation learning, like GraphWave.

Graph representation is basically any method that takes a graph and spits out vectors which usually correspond to either the nodes, edges, or the entire graph itself and encode some important information about these objects. Graph representation learning is powerful because we can then use neural networks, principal component analysis, support vector machines, or any of our normal tools and algorithms on graphs.

This leaves us with the question: How do we best represent our graphs? The answer depends on what we want to do.

In this article we’ll discuss how Graphwave can be used to effectively represent the structure of nodes without using features, making it a valuable tool for its inherent capacity to cluster structurally similar nodes.

StellarGraph 1.0 — taking graph machine learning to a new level

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!

In summary —

If you’re looking to infer node information from network structure, GraphWave far outperforms traditional random walk algorithms like Node2Vec. GraphWave also has the added advantage of working without meaningful node features, unlike GCN type algorithms.

At StellarGraph, we’ve implemented a scalable and parallel version of GraphWave in our open source library. Check out our 1.0 release and ride the GraphWave!

This work is supported by CSIRO’s Data61, Australia’s leading digital research network.