Course contentsShow
← Machine Learning and Deep Learning
Lesson 2524 of 3,53854. Graph Neural NetworksFree lesson

Link Prediction

Predicting missing or future edges in graphs for friend recommendation, drug interactions, and knowledge completion.

Link Prediction

What you'll learn: How GNNs predict missing or future connections in graphs, enabling friend suggestions, drug interaction forecasting, and knowledge graph completion.

What Is Link Prediction?

Link prediction is the task of determining whether an edge should exist between two nodes in a graph. Unlike node classification (which labels individual nodes), link prediction answers: "Should there be a connection here?"

Think of it like predicting friendships on social media. Given your current network, who should the platform recommend you connect with? Or in molecular biology: if two drugs interact with similar proteins, might they interact with each other?

The Core Approach

Link prediction typically works by:

  1. Encoding nodes using a GNN (like GCN, GraphSAGE, or GAT) to create meaningful embeddings based on graph structure and features
  2. Combining node pairs using operations like concatenation, element-wise product, or inner product
  3. Scoring the likelihood that an edge exists between them (often via a simple classifier or distance metric)

For example, after running message passing layers, you might have embeddings h_u and h_v for nodes u and v. The edge probability could be computed as sigmoid(h_u · h_v) — similar nodes have high scores.

Training Strategy

You train on known edges (positive examples) and non-edges (negative examples, often sampled randomly). The model learns what patterns in the graph structure indicate likely connections. At test time, you predict on unseen or future pairs.

Real-World Applications

  • Social networks: Friend or follower recommendations
  • Drug discovery: Predicting unknown drug-drug or drug-protein interactions
  • Knowledge graphs: Completing missing facts (e.g., "Paris capital_of ?")
  • E-commerce: Product recommendation as user-item links

Key Takeaway: Link prediction uses GNN embeddings to score potential edges, enabling recommendations and discovery of hidden relationships in graph-structured data.