Link prediction

As explained in Graph Algorithms for Data Science

Link prediction is a graph machine learning task that predicts prospective relationships between nodes, optionally including their relationship types.

Link prediction estimates whether a relationship between two nodes is likely to appear, or whether a missing relationship should exist. It is useful when networks change over time, such as friendships, and when incomplete networks hide plausible connections, such as drug–disease relationships. In a user–product graph, predicted links can become personalized recommendations. section 10.0 section 10.6

Treat each candidate connection as a pair of nodes, not as an isolated node. Build pair features from combined node properties or embeddings, shortest-path distance, and neighborhood overlap. Common-neighbor counts and Jaccard similarity capture shared local context; degree products capture preferential attachment. section 10.1 section 10.6

Figure 10.4 Link prediction flow

Use the workflow diagram to distinguish the feature graph from the labeled relationship samples used to train and test a classifier. section 10.1

Build a link prediction workflow in separate stages:

• Split relationships into a feature set and train/test samples. When timestamps exist, derive features from earlier links and label later links; keep feature relationships out of training and testing to avoid leakage. section 10.2.1 section 10.6
• Create positive samples from observed links and negative samples from pairs without the target relationship. Subsample negatives to avoid severe class imbalance. section 10.4 section 10.6
• Train a binary classifier on the pair features and evaluate it on held-out samples. A random forest is one option; logistic regression and support vector machines are alternatives. section 10.4

Predicting new friendships

If Luke and Rajiv share friends and are close in the network, their pair can receive a higher predicted probability than Jose and Alice. The prediction uses network structure rather than personal characteristics alone, because shared social context helps indicate whether people may meet. section 10.0 section 10.1

Inspect feature distributions before modeling. A feature with little variation, such as a distance that is almost always two hops, may be less useful than a feature with a wider range. Also account for embedding limits: transductive node embeddings cannot represent unseen nodes, so they cannot predict links for nodes absent during training. section 10.4 section 10.6

How Graph Algorithms for Data Science covers it

How deep it goes

Walks through pair-feature construction, leakage-safe splitting, negative sampling, and binary-classifier training without optimization details.

Examples

Uses friendship pairs, user–product purchases, drug–disease links, and Twitch shared audiences.

What it assumes

Introduces graph pair features from concrete networks without assuming graph-theory expertise.

What you can do after

Apply it via Cypher, pandas, and a classifier to train and evaluate relationship predictions from graph features.

How it connects

Connects node embeddings, shortest paths, Jaccard similarity, preferential attachment, Adamic-Adar, and binary classification.

liveBookmanning.com

Read Graph Algorithms for Data Science on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Knowledge Graphs and LLMs in ActionLink prediction is a graph-learning technique that forecasts missing, future, or otherwise unobserved connections between nodes, optionally assigning scores or probabilities to candidate links.
• 

  liveBookmanning.com
  Graph Neural Networks in ActionLink prediction, or edge prediction, is a graph-learning task that estimates whether an edge exists or should exist between graph entities.

Compare how 3 books explain link prediction →

Related concepts

• graph neural networkused by · A graph neural network is a neural-network model that learns representations or predictions from graph-structured data by combining information from connected entities.
• Adamic-Adar indexused by · The Adamic-Adar index is a link-prediction metric that scores node pairs by weighting common neighbors more highly when they have lower degree.
• recommender systemuses · A recommender system is software that predicts, selects, or ranks items, content, or actions for users based on available information about users, items, or context.
• semi-supervised learninguses · Semi-supervised learning is a machine-learning approach that trains models using both labeled and unlabeled data.
• graph autoencoderaddressed by · A graph autoencoder is a graph neural network encoder-decoder model that learns latent graph representations and reconstructs graph-related inputs or structure.

This explainer was generated by Manning's knowledge graph from the text of Graph Algorithms for Data Science. The section links point to the parts of the book it draws on.