Predicting Links with Graph Neural Networks

Link prediction is one of the most popular tasks performed with graphs. It is defined as the problem of predicting the existence of a link between two nodes. This ability is at the core of social networks and recommender systems. A good example is how social media networks display friends and followers you have in common with others. Intuitively, if this number is high, you are more likely to connect with these people. This likelihood is precisely what link prediction tries to estimate.

In this chapter, we will first see how to perform link prediction without any machine learning. These traditional techniques are essential to understanding what GNNs learn. We will then refer to previous chapters about DeepWalk and Node2Vec to link prediction through matrix factorization. Unfortunately, these techniques have significant limitations, which is why we will transition to GNN-based methods.

We will explore three methods from two different...

Technical requirements

All the code examples from this chapter can be found on GitHub at https://github.com/PacktPublishing/Hands-On-Graph-Neural-Networks-Using-Python/tree/main/Chapter10.

Installation steps required to run the code on your local machine can be found in the Preface section of this book.

Predicting links with traditional methods

The link prediction problem has been around for a long time, which is why numerous techniques have been proposed to solve it. First, this section will describe popular heuristics based on local and global neighborhoods. Then, we will introduce matrix factorization and its connection to DeepWalk and Node2Vec.

Heuristic techniques

Heuristic techniques are a simple and practical way to predict links between nodes. They are easy to implement and offer strong baselines for this task. We can classify them based on the number of hops they perform (see Figure 10.1). Some of them only require 1-hop neighbors that are adjacent to the target nodes. More complex techniques also consider 2-hop neighbors or an entire graph. In this section, we will divide them into two categories – local (1-hop and 2-hop) and global heuristics.

Figure 10.1 – Graph with 1-hop, 2-hop, and 3-hop neighbors

Local heuristics measure...

Predicting links with node embeddings

In the previous chapters, we saw how to use GNNs to produce node embeddings. A popular link prediction technique consists of using these embeddings to perform matrix factorization. This section will discuss two GNN architectures for link prediction – the Graph Autoencoder (GAE) and the Variational Graph Autoencoder (VGAE).

Introducing Graph Autoencoders

Both architectures were introduced by Kipf and Welling in 2016 [5] in a three-page paper. They represent the GNN counterparts of two popular neural network architectures – the autoencoder and the variational autoencoder. Prior knowledge about these architectures is helpful but not necessary. For ease of understanding, we will first focus on the GAE.

The GAE is composed of two modules:

• The encoder is a classic two-layer GCN that computes node embeddings as follows:

• The decoder approximates the adjacency matrix, , using matrix factorization...

Predicting links with SEAL

The previous section introduced node-based methods, which learn relevant node embeddings to compute link likelihoods. Another approach consists of looking at the local neighborhood around the target nodes. These techniques are called subgraph-based algorithms and were popularized by SEAL (which could be said to stand for Subgraphs, Embeddings, and Attributes for Link prediction – though not always!). In this section, we will describe the SEAL framework and implement it using PyTorch Geometric.

Introducing the SEAL framework

Introduced in 2018 by Zhang and Chen [6], SEAL is a framework that learns graph structure features for link prediction. It defines the subgraph formed by the target nodes and their -hop neighbors as the enclosing subgraph. Each enclosing subgraph is used as input (instead of the entire graph) to predict a link likelihood. Another way to look at it is that SEAL automatically learns a local heuristic for link prediction.

...

Summary

In this chapter, we explored a new task with link prediction. We gave an overview of this field by presenting heuristic and matrix factorization techniques. Heuristics can be classified according to the k-hop neighbors they consider – from local with 1-hop neighbors to global with the knowledge of the entire graph. Conversely, matrix factorization approximates the adjacency matrix using node embeddings. We also explained how this technique was connected to algorithms described in previous chapters (DeepWalk and Node2Vec).

After this introduction to link prediction, we saw how to implement it using GNNs. We outlined two kinds of techniques, based on node embeddings (GAE and VGAE) and subgraph representations (SEAL). Finally, we implemented a VGAE and SEAL on the Cora dataset with an edge-level random split and negative sampling. Both models obtained comparable performance, although SEAL is strictly more expressive.

In Chapter 11, Generating Graphs with Graph Neural...

Further reading

• [1] H. Tong, C. Faloutsos and J. -y. Pan. “Fast Random Walk with Restart and Its Applications” in Sixth International Conference on Data Mining (ICDM’06), 2006, pp. 613-622, doi: 10.1109/ICDM.2006.70.
• [2] Yehuda Koren, Robert Bell, and Chris Volinsky. 2009. Matrix Factorization Techniques for Recommender Systems. Computer 42, 8 (August 2009), 30–37. https://doi.org/10.1109/MC.2009.263.
• [3] J. Qiu, Y. Dong, H. Ma, J. Li, K. Wang, and J. Tang. Network Embedding as Matrix Factorization. Feb. 2018. doi: 10.1145/3159652.3159706.
• [4] D. P. Kingma and M. Welling. Auto-Encoding Variational Bayes. arXiv, 2013. doi: 10.48550/ARXIV.1312.6114.
• [5] T. N. Kipf and M. Welling. Variational Graph Auto-Encoders. arXiv, 2016. doi: 10.48550/ARXIV.1611.07308.
• [6] M. Zhang and Y. Chen. Link Prediction Based on Graph Neural Networks. arXiv, 2018. doi: 10.48550/ARXIV.1802.09691.
• [7] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin...