What is link prediction and what architectures are used?

Link prediction is a task in graph analysis where the goal is to predict the likelihood of an edge existing between two nodes, based on the graph's structure and node properties.

Main architectures and approaches for link prediction:

• Feature-based methods: utilize node characteristics and their neighbors, such as common neighbors, Jaccard coefficients.

• Graph Neural Networks (GNN): learn node representations considering their surroundings. Popular architectures include:

  • Graph Convolutional Networks (GCN)
  • Graph Attention Networks (GAT)
  • GraphSAGE

• Embedding-based models: nodes are mapped into a vector space, and the connection is predicted through operations on vectors (e.g., dot product).

• Probabilistic graph models: use probabilistic models to evaluate connections.

An example with GNN for link prediction: first, train a GNN to obtain node embeddings, then compute the probability of an edge between two nodes using a similarity function (e.g., dot product) and apply a sigmoid to get the probability.