Link Prediction Scoring Functions: Jaccard, Adamic-Adar, Common Neighbors

Link prediction asks whether a missing or future edge should exist between two nodes in a graph. It is one of the fundamental graph mining tasks, with applications in recommendation systems (friend suggestions), biological network completion (predicting protein-protein interactions), and knowledge base completion. Before graph neural networks became standard, classical scoring functions dominated the field. Understanding these functions — what they compute, when they work, and where they fail — remains valuable even in the GNN era.

TGraphX provides these classical scoring functions through the tgraphx.mining.link_prediction module. This article covers the mathematical definitions, intuitions, practical usage, and an honest comparison of when each function is appropriate.

What Link Prediction Scoring Functions Do

A scoring function takes a pair of nodes (u, v) that are not currently connected and returns a scalar score. A higher score means the function predicts a higher probability that the edge should exist. These functions do not train parameters — they compute scores directly from the graph structure, specifically from the neighborhoods of the two nodes.

This makes them fast, interpretable, and zero-shot: no training data is required. The cost is that they cannot learn complex patterns or incorporate node features. They are structural heuristics, not learned models.

Common Neighbors

Common Neighbors is the simplest scoring function. The score for a node pair (u, v) is the number of nodes that are neighbors of both u and v:

CN(u, v) = |N(u) ∩ N(v)|
        

The intuition is direct: if two people have many mutual friends, they are likely to know each other. In social networks, this is the friend-of-a-friend effect. In citation graphs, papers that cite many of the same references are likely related.

Common Neighbors does not normalize for node degree. A node with 1,000 neighbors will have many common neighbors with almost anyone. This creates a bias toward high-degree nodes.

Jaccard Coefficient

The Jaccard Coefficient normalizes Common Neighbors by the size of the union of both neighborhoods:

Jaccard(u, v) = |N(u) ∩ N(v)| / |N(u) ∪ N(v)|
        

This is the same Jaccard similarity used in set theory and information retrieval. It bounds the score between 0 and 1, where 1 means the two nodes have identical neighborhoods. Jaccard corrects for the high-degree bias in Common Neighbors: a hub node with 1,000 neighbors and a regular node with 10 neighbors will have a lower Jaccard score than two regular nodes with the same 10 neighbors, even if they share the same 10 mutual neighbors.

Jaccard works well when the graph has moderate degree heterogeneity. It can underestimate link probability for high-degree nodes in power-law networks.

Adamic-Adar Index

Adamic-Adar weights each common neighbor by the inverse log of that neighbor's degree:

AA(u, v) = Σ_{z ∈ N(u) ∩ N(v)} 1 / log(|N(z)|)
        

The key insight is that a common neighbor with a low degree is more informative than one with a high degree. If Alice and Bob are both connected to a specialist who follows only 10 people, that is stronger evidence of a connection than if they are both connected to a celebrity who follows 10 million people.

Adamic-Adar was originally proposed for the Web — a link from a niche page carries more weight than a link from a universal hub. It consistently outperforms Common Neighbors and Jaccard on many real-world social networks.

Preferential Attachment

Preferential Attachment scores node pairs by the product of their degrees:

PA(u, v) = |N(u)| * |N(v)|
        

This is inspired by the Barabási-Albert preferential attachment model of network growth: new edges are more likely to form between high-degree nodes. Unlike the other scoring functions, Preferential Attachment does not require finding common neighbors, making it O(1) per pair (after precomputing degrees). This makes it practical for very large graphs where computing neighborhoods is expensive.

Preferential Attachment is a rough heuristic that works best on networks where degree distribution strongly predicts future connectivity. It ignores shared structure entirely and will predict high scores for disconnected hubs that have no structural relation.

TGraphX Implementation

The tgraphx.mining.link_prediction module provides all four scoring functions with a consistent interface:

import torch
        from tgraphx import Graph
        from tgraphx.mining.link_prediction import (
            common_neighbors_score,
            jaccard_score,
            adamic_adar_score,
            preferential_attachment_score,
        )
        
        # Build a small graph
        edge_index = torch.tensor([
            [0, 1, 1, 2, 3, 4, 0, 3],
            [1, 2, 3, 3, 4, 0, 4, 5],
        ], dtype=torch.long)
        
        g = Graph(
            node_features=torch.randn(6, 8),
            edge_index=edge_index,
        )
        
        # Score a set of candidate pairs
        candidate_pairs = torch.tensor([
            [0, 2],
            [1, 4],
            [2, 5],
            [0, 5],
        ], dtype=torch.long)
        
        cn_scores = common_neighbors_score(g, candidate_pairs)
        j_scores = jaccard_score(g, candidate_pairs)
        aa_scores = adamic_adar_score(g, candidate_pairs)
        pa_scores = preferential_attachment_score(g, candidate_pairs)
        
        for i, (u, v) in enumerate(candidate_pairs.tolist()):
            print(f"({u},{v}): CN={cn_scores[i]:.3f}, "
                  f"Jaccard={j_scores[i]:.3f}, "
                  f"AA={aa_scores[i]:.3f}, "
                  f"PA={pa_scores[i]:.3f}")
        

Evaluating Link Prediction Quality

For evaluation, you need positive pairs (edges that exist) and negative pairs (non-edges). A standard protocol holds out a fraction of existing edges as test positives and samples an equal number of non-edges as test negatives:

from tgraphx.mining.link_prediction import (
            split_edges_for_evaluation,
            evaluate_link_prediction,
        )
        
        # Split edges: 80% train, 20% test positive
        train_edges, test_pos, test_neg = split_edges_for_evaluation(
            g, test_fraction=0.2, neg_sampling_ratio=1.0, seed=42
        )
        
        # Score test pairs with Adamic-Adar
        test_pairs = torch.cat([test_pos, test_neg], dim=0)
        scores = adamic_adar_score(g, test_pairs)
        
        # True labels: 1 for positive, 0 for negative
        labels = torch.cat([
            torch.ones(test_pos.shape[0]),
            torch.zeros(test_neg.shape[0]),
        ])
        
        metrics = evaluate_link_prediction(scores, labels)
        print(f"AUC-ROC: {metrics['auc_roc']:.4f}")
        print(f"Average Precision: {metrics['average_precision']:.4f}")
        

AUC-ROC measures how well the scores separate positives from negatives across all thresholds. Average Precision is more sensitive to ranking quality at the top of the list, which matters when only the top-k predictions will be acted upon.

Scoring Function Comparison

Here d is the average degree of the graph. For dense graphs with high average degree, all neighborhood-based methods become expensive.

Combining Scores

For better coverage, you can combine multiple scores into a single predictor. A simple approach is a linear combination:

import torch
        
        # Normalize each score to [0, 1] range
        def normalize(s):
            s_min, s_max = s.min(), s.max()
            if s_max == s_min:
                return torch.zeros_like(s)
            return (s - s_min) / (s_max - s_min)
        
        combined = (
            0.4 * normalize(aa_scores) +
            0.4 * normalize(j_scores) +
            0.2 * normalize(pa_scores)
        )
        

The weights should be treated as hyperparameters and tuned on a validation set. This ensemble approach often outperforms any single scoring function, though it introduces three parameters that require tuning.

Limitations vs GNN Approaches

Classical scoring functions have important limitations that GNNs address:

They cannot use node features. If a citation network has text embeddings for each paper, Jaccard ignores them entirely. GNNs incorporate both structural and feature information.

They are local. Common Neighbors, Jaccard, and Adamic-Adar all look at 1-hop neighborhoods. Paths of length 3 or longer are invisible to them. Graph neural networks with multiple layers aggregate information from multi-hop neighborhoods.

They do not learn from examples. A GNN-based link predictor can adapt to the specific prediction patterns in a dataset. Classical functions apply the same formula to every graph regardless of the domain.

They fail on bipartite or heterogeneous graphs. A user-item bipartite graph has zero common neighbors between any two items — because items are never directly connected. Classical functions collapse to zero and provide no signal.

For link prediction with GNN-based approaches, see the knowledge graph embedding tutorial which covers learned entity representations for link prediction in knowledge graphs.

Frequently Asked Questions

When should I use classical scoring functions over GNNs? When you have a small graph, no node features, limited compute, or you need interpretable scores with no training phase. Classical functions are also useful as baselines to check whether your GNN is actually learning something non-trivial.

Do these functions work on directed graphs? Neighborhoods in directed graphs can be defined as in-neighbors, out-neighbors, or both. The TGraphX implementations treat the graph as undirected by default. For directed graphs, pass directed=True and specify the neighborhood direction.

How many candidate pairs can these functions evaluate efficiently? For a graph with 10,000 nodes and average degree 20, scoring 100,000 candidate pairs takes under a second on CPU. For millions of pairs or very dense graphs, consider GPU-accelerated alternatives or approximate methods.

Is Adamic-Adar always better than Common Neighbors? Not always. On graphs with very homogeneous degree distributions, the two produce nearly identical rankings. The advantage of Adamic-Adar is most pronounced on power-law degree distributions.

What This Article Builds On

This article assumes familiarity with graph construction using TGraphX Graph objects. If you are new to TGraphX, the shape-aware validation guide covers the data construction and validation patterns that underpin all downstream analysis. For learned link prediction using knowledge graph embeddings, see the knowledge graph embedding tutorial.

Classical Scoring Functions as Baselines

An underappreciated use case for classical scoring functions is as baselines in research papers. When proposing a new GNN-based link prediction method, comparing against Adamic-Adar and Jaccard takes negligible compute and provides context for how much structure can be captured without learning. If a proposed GNN barely outperforms Adamic-Adar, that suggests either the model is not learning effectively or the task primarily depends on local structure that the classical method already captures.

This is a common oversight in link prediction papers: the ablation includes many GNN variants but omits the trivial non-learned baselines. TGraphX makes it easy to include classical baselines in any experiment through the tgraphx.mining.link_prediction module, so there is no excuse for omitting them.

Using Scoring Functions for Negative Sampling

Beyond evaluation, classical scoring functions can guide negative sampling during GNN training. Instead of sampling negative edges uniformly at random, you can sample challenging negatives — node pairs that have moderate Adamic-Adar scores (suggesting structural proximity) but are not actually connected. This produces harder training negatives that force the model to learn more discriminative features.

from tgraphx.mining.link_prediction import adamic_adar_score
        from tgraphx.sampling_negative import HardNegativeSampler
        
        # Create a hard negative sampler using Adamic-Adar to score candidates
        sampler = HardNegativeSampler(
            scoring_fn=adamic_adar_score,
            num_negatives=5,
            difficulty="medium",  # sample from mid-range scores, not trivial zeros
        )
        
        # During training
        neg_edges = sampler.sample(g, pos_edges=batch_pos_edges)
        

Hard negative sampling is not always beneficial — it can slow convergence and sometimes hurts performance if the negatives are too similar to positives. But for tasks where the graph is dense or the positive edges are structurally predictable, hard negatives often improve final model quality.

Scalability Considerations

For graphs with millions of nodes and billions of candidate pairs, neighborhood-based scoring functions become expensive. The main bottleneck is computing neighborhood intersections. Several strategies reduce this cost:

Locality-sensitive hashing (LSH). Approximate the Jaccard similarity using min-hash signatures without computing exact intersections. This reduces per-pair cost from O(d) to O(hash_size), at the cost of some approximation error.

Degree-based pre-filtering. For Preferential Attachment, the score is just a product of degrees. You can pre-rank all candidate pairs by PA score in O(n) time using sorted degree sequences, then only compute expensive neighborhood-based scores for the top-k candidates.

Batched sparse operations. For Common Neighbors on sparse graphs, the intersection can be computed as the dot product of binary adjacency row vectors. With sparse matrix operations, this is efficient for graphs where the adjacency matrix fits in memory.

TGraphX implements these scoring functions with dense tensor operations suitable for graphs up to ~100,000 nodes on a standard GPU. For larger graphs, interface with specialized graph databases or approximate methods.

For more on scalable sampling strategies in TGraphX, see the neighbor sampling article.