ever puzzled the way it’s doable that Fb is aware of who you would possibly know? Or why it typically suggests a complete stranger? This downside is known as hyperlink prediction. In a social community graph, individuals are nodes and friendships are edges, the objective is to foretell if a connection ought to exist between two nodes.
Hyperlink prediction is a very fashionable subject! It may be used to advocate buddies in social networks, recommend merchandise on e-commerce websites or motion pictures on Netflix, or predict protein interactions in biology. On this publish, you’ll discover how hyperlink prediction works. First you’ll study easy heuristics, and we finish with highly effective GNN-based strategies like SEAL.
The earlier posts defined GCNs, GATs, and GraphSage. They primarily lined predicting node properties, so you may learn this text standalone, as a result of this time we shift focus to predicting edges. If you wish to dive a bit deeper into node representations, I like to recommend to revisit the earlier posts. The code setup might be discovered here.
What’s Hyperlink Prediction?
Hyperlink prediction is the duty of forecasting lacking or future connections (edges) between nodes in a graph. Given a graph G = (V, E), the objective is to foretell whether or not an edge ought to exist between two nodes (u, v) ∉ E.
To guage hyperlink prediction fashions, you may create a check set by hiding a portion of the prevailing edges and ask the mannequin to foretell them. After all, the check set ought to have optimistic samples (actual edges), and unfavourable samples (random node pairs that aren’t related). You may practice the mannequin on the remaining graph.
The output of the mannequin is a hyperlink rating or likelihood for every node pair. You may consider this with metrics like AUC or common precision.
We are going to check out easy heuristic-based strategies, after which we transfer on to extra complicated strategies.
Heuristic-Based mostly Strategies
We are able to divide these ‘straightforward’ strategies into two classes: native and world. Native heuristics are primarily based on native construction, whereas world heuristics use the entire graph. These approaches are rule-based and work nicely as baselines for hyperlink prediction duties.
Native Heuristics
Because the title says, native heuristics depend on the instant neighborhood of the 2 nodes you might be testing for a possible hyperlink. And truly they are often surprisingly efficient. Advantages of native heuristics are that they’re quick and interpretable. However they solely have a look at the shut neighborhood, so capturing the complexity of relationships is restricted.
Frequent Neighbors
The thought is straightforward: if two nodes share many widespread neighbors, they’re extra more likely to be related.
For calculation you rely the variety of neighbors the nodes have in widespread. One challenge right here is that it doesn’t bear in mind the relative variety of widespread neighbors.
Within the examples beneath, the variety of widespread neighbors between A and B is 3, and the variety of widespread neighbors between C and D is 1.
Jaccard Coefficient
The Jaccard Coefficient fixes the problem of widespread neighbors and computes the relative variety of neighbors in widespread.
You’re taking the widespread neighbors and divide this by the full variety of distinctive neighbors of the 2 nodes.
So now issues change a bit: the Jaccard coefficient of nodes A and B is 3/5 = 0.6 (they’ve 3 widespread neighbors and 5 complete distinctive neighbors), whereas the Jaccard coefficient of nodes C and D is 1/1 = 1 (they’ve 1 widespread neighbor and 1 distinctive neighbor). On this case the connection between C and D is extra doubtless, as a result of they solely have 1 neighbor, and it’s additionally a standard neighbor.
Adamic-Adar Index
The Adamic-Adar index goes one step additional than widespread neighbors: it makes use of the recognition of a standard neighbor and offers much less weight to extra well-liked neighbors (they’ve extra connections). The instinct behind that is that if a node is related to everybody, it doesn’t inform us a lot a couple of particular connection.
What does that appear to be in a formulation?
So for every widespread neighbor z, we add a rating of 1 divided by the log of the variety of neighbors from z. By doing this, the extra well-liked the widespread neighbor, the smaller its contribution.
Let’s calculate the Adamic-Adar index for our examples.
Preferential Attachment
A special strategy is preferential attachment. The thought behind it’s that nodes with greater levels usually tend to type hyperlinks. Calculation is tremendous straightforward, you simply multiply the levels (variety of connections) of the 2 nodes.
For A and B, the levels are respectively 5 and three, so the rating is 5*3 = 15. C and D have a rating of 1*1 = 1. On this case A and B usually tend to have a connection, as a result of they’ve extra neighbors typically.
International Heuristics
International heuristics take into account paths, walks, or all the graph construction. They’ll seize richer patterns, however are extra computationally costly.
Katz Index
Essentially the most well-known world heuristic for Link Prediction is the Katz Index. It takes all of the completely different paths between two nodes (normally solely paths as much as three steps). Every path will get a weight that decays exponentially with its size. This is sensible intuitively, as a result of the shorter a path, the extra necessary it’s (buddies in widespread means quite a bit). However, oblique paths matter as nicely! They’ll trace at potential hyperlinks.
The Katz Components:
We take two nodes, C and E, and rely the paths between them. There are three paths with as much as three steps: one path with two steps (orange), and two paths with three steps (blue and inexperienced). Now we are able to calculate the Katz index, let’s select 0.1 for beta:
Rooted PageRank
This methodology makes use of random walks to find out how doubtless it’s {that a} random stroll from the primary node, will find yourself within the second node. So that you begin within the first node, then you definately both stroll to a random neighbor, otherwise you bounce again to the primary node. The likelihood that you find yourself on the second node tells how intently the 2 nodes are. If the likelihood is excessive, there’s a good likelihood the nodes needs to be linked.
ML-Based mostly Hyperlink Prediction
Machine studying approaches take hyperlink prediction past heuristics by studying patterns instantly from the info. As an alternative of counting on predefined guidelines, ML fashions can study complicated options that sign whether or not a hyperlink ought to exist.
A primary strategy is to deal with hyperlink prediction as a binary classification activity: for every node pair (u, v), we create a characteristic vector and practice a mannequin to foretell 1 (hyperlink exists) or 0 (hyperlink doesn’t exist). You may add the heuristics we calculated earlier than as options. The heuristics didn’t agree on a regular basis on probability of edges, typically the sting between A and B was extra doubtless, whereas for others the sting between C and D was the higher selection. By together with a number of scores as options we don’t have to decide on one heuristic. After all relying on the issue some heuristics would possibly work higher than others.
One other sort of options you may add are aggregated options: for instance node diploma, node embeddings, attribute averages, and so on.
Then use any classifier (e.g., logistic regression, random forest, XGBoost) to foretell hyperlinks. This already performs higher than heuristics alone, particularly when mixed.
On this publish we’ll use the Cora dataset to check completely different approaches to hyperlink prediction. The Cora dataset accommodates scientific papers. The perimeters signify citations between papers. Let’s practice a machine studying mannequin as baseline, the place we solely add the Jaccard coefficient:
import os.path as osp
from sklearn.linear_model import LogisticRegression
from sklearn.metrics import roc_auc_score, average_precision_score
from torch_geometric.datasets import Planetoid
from torch_geometric.transforms import RandomLinkSplit
from torch_geometric.utils import to_dense_adj
# reproducibility
from torch_geometric import seed_everything
seed_everything(42)
# load Cora dataset, create practice/val/check splits
path = osp.be a part of(osp.dirname(osp.realpath(__file__)), '..', 'information', 'Planetoid')
dataset = Planetoid(path, title='Cora')
data_all = dataset[0]
rework = RandomLinkSplit(num_val=0.05, num_test=0.1, is_undirected=True, split_labels=True)
train_data, val_data, test_data = rework(data_all)
# add Jaccard and practice with Logistic Regression
adj = to_dense_adj(train_data.edge_index, max_num_nodes=data_all.num_nodes)[0]
def jaccard(u, v, adj):
u_neighbors = set(adj[u].nonzero().view(-1).tolist())
v_neighbors = set(adj[v].nonzero().view(-1).tolist())
inter = len(u_neighbors & v_neighbors)
union = len(u_neighbors | v_neighbors)
return inter / union if union > 0 else 0.0
def extract_features(pairs, adj):
return [[jaccard(u, v, adj)] for u, v in pairs]
train_pairs = train_data.pos_edge_label_index.t().tolist() + train_data.neg_edge_label_index.t().tolist()
train_labels = [1] * train_data.pos_edge_label_index.dimension(1) + [0] * train_data.neg_edge_label_index.dimension(1)
test_pairs = test_data.pos_edge_label_index.t().tolist() + test_data.neg_edge_label_index.t().tolist()
test_labels = [1] * test_data.pos_edge_label_index.dimension(1) + [0] * test_data.neg_edge_label_index.dimension(1)
X_train = extract_features(train_pairs, adj)
clf = LogisticRegression().match(X_train, train_labels)
X_test = extract_features(test_pairs, adj)
probs = clf.predict_proba(X_test)[:, 1]
auc_ml = roc_auc_score(test_labels, probs)
ap_ml = average_precision_score(test_labels, probs)
print(f"[ML Heuristic] AUC: {auc_ml:.4f}, AP: {ap_ml:.4f}")
We consider with AUC. That is the end result:
[ML Model] AUC: 0.6958, AP: 0.6890We are able to go a step additional and use neural networks that function instantly on the graph construction.
VGAE: Encoding and Decoding
A Variational Graph Auto-Encoder is sort of a neural community that learns to guess the hidden construction of the graph. It might then use that hidden data to foretell lacking hyperlinks.
A VGAE is definitely a mixture of a GAE (Graph Auto-Encoder) and a VAE (Variational Auto-Encoder). I’ll get again to the distinction between a GAE and a VGAE in a while.
The steps of a VGAE are as follows. First, the VGAE encodes nodes into latent vectors, after which it decodes node pairs to predict whether or not an edge exists between them.
How does the encoding work? Every node is mapped to a latent variable, that may be a level in some hidden house. The encoder is a Graph Convolutional Network (GCN) that produces a imply and a variance vector for every node. It makes use of the node options and the adjacency matrix as enter. Utilizing the vectors, the VGAE samples a latent embedding from a standard distribution. It’s necessary to notice that every node isn’t simply mapped to a single level, however to a distribution! That is the distinction between a GAE and a VGAE, in a GAE every node is mapped to 1 single level.
The following step is the decoding step. The VGAE will guess if there may be an edge between two nodes. It does this by calculating the internal product between the embeddings of the 2 nodes:
The thought behind it’s: if the nodes are nearer collectively within the hidden house, it’s extra doubtless they’re related.
VGAE visualized:
How does the mannequin study? It optimizes two issues:
- Reconstruction Loss: Do the anticipated edges match the actual ones?
- KL Divergence Loss: Is the latent house good and common?
Let’s check the VGAE on the Cora dataset:
import os.path as osp
import numpy as np
import torch
from sklearn.metrics import roc_auc_score, average_precision_score
from torch_geometric.datasets import Planetoid
from torch_geometric.nn import GCNConv, VGAE
from torch_geometric.transforms import RandomLinkSplit
# similar as earlier than
from torch_geometric import seed_everything
seed_everything(42)
path = osp.be a part of(osp.dirname(osp.realpath(__file__)), '..', 'information', 'Planetoid')
dataset = Planetoid(path, title='Cora')
data_all = dataset[0]
rework = RandomLinkSplit(num_val=0.05, num_test=0.1, is_undirected=True, split_labels=True)
train_data, val_data, test_data = rework(data_all)
# VGAE
class VGAEEncoder(torch.nn.Module):
def __init__(self, in_channels, out_channels):
tremendous().__init__()
self.conv1 = GCNConv(in_channels, 2 * out_channels)
self.conv_mu = GCNConv(2 * out_channels, out_channels)
self.conv_logstd = GCNConv(2 * out_channels, out_channels)
def ahead(self, x, edge_index):
x = self.conv1(x, edge_index).relu()
return self.conv_mu(x, edge_index), self.conv_logstd(x, edge_index)
vgae = VGAE(VGAEEncoder(dataset.num_features, 32))
vgae_optimizer = torch.optim.Adam(vgae.parameters(), lr=0.01)
x = data_all.x
edge_index = train_data.edge_index
# practice VGAE mannequin
for epoch in vary(1, 101):
vgae.practice()
vgae_optimizer.zero_grad()
z = vgae.encode(x, edge_index)
# reconstruction loss
loss = vgae.recon_loss(z, train_data.pos_edge_label_index)
# KL divergence
loss = loss + (1 / data_all.num_nodes) * vgae.kl_loss()
loss.backward()
vgae_optimizer.step()
vgae.eval()
z = vgae.encode(x, edge_index)
@torch.no_grad()
def score_edges(pairs):
edge_tensor = torch.tensor(pairs).t().to(z.machine)
return vgae.decoder(z, edge_tensor).view(-1).cpu().numpy()
vgae_scores = np.concatenate([score_edges(test_data.pos_edge_label_index.t().tolist()),
score_edges(test_data.neg_edge_label_index.t().tolist())])
vgae_labels = np.array([1] * test_data.pos_edge_label_index.dimension(1) +
[0] * test_data.neg_edge_label_index.dimension(1))
auc_vgae = roc_auc_score(vgae_labels, vgae_scores)
ap_vgae = average_precision_score(vgae_labels, vgae_scores)
print(f"[VGAE] AUC: {auc_vgae:.4f}, AP: {ap_vgae:.4f}")And the end result (ML mannequin added for comparability):
[VGAE] AUC: 0.9032, AP: 0.9179
[ML Model] AUC: 0.6958, AP: 0.6890Wow! Huge enchancment in comparison with the ML mannequin!
SEAL: Studying from Subgraphs
One of the crucial highly effective GNN-based approaches is SEAL (Subgraph Embedding-based Hyperlink prediction). The thought is straightforward and chic: as an alternative of taking a look at world node embeddings, SEAL appears on the native subgraph round every node pair.
Right here’s a step-by-step clarification:
- For every node pair (u, v), extract a small enclosing subgraph. E.g., neighbors solely (1-hop neighborhood) or neighbors and neighbors from neighbors (2-hop neighborhood).
- Label the nodes on this subgraph to replicate their position: which of them are u, v, and which of them are neighbors.
- Use a GNN (like DGCNN or GCN) to study from the subgraph and predict if a hyperlink ought to exist.
Visualization of the steps:
SEAL could be very highly effective as a result of it learns structural patterns instantly from examples, as an alternative of counting on handcrafted guidelines. It additionally works nicely with sparse graphs and generalizes throughout various kinds of networks.
Let’s see if SEAL can enhance the outcomes of the VGAE on the Cora dataset. For the SEAL code, I took the sample code from PyTorch geometric (test it out by following the hyperlink), since SEAL requires fairly some processing. You may acknowledge the completely different steps within the code (getting ready the info, extracting the subgraphs, labeling the nodes). Coaching for 50 epochs offers the next end result:
[SEAL] AUC: 0.9038, AP: 0.9176
[VGAE] AUC: 0.9032, AP: 0.9179
[ML Model] AUC: 0.6958, AP: 0.6890Nearly precisely the identical end result because the VGAE. So for this downside, VGAE could be your best option (VGAE is considerably quicker than SEAL). After all this could fluctuate, relying in your downside.
Conclusion
On this publish, we dived into the subject of hyperlink prediction, from heuristics to SEAL. Heuristic strategies are quick and interpretable and might function good baselines, however ML and GNN-based strategies like VGAE and SEAL can study richer representations and provide higher efficiency. Relying in your dataset dimension and activity complexity, it’s price exploring each!
Thanks for studying, till subsequent time!
Associated
Graph Neural Networks Part 1. Graph Convolutional Networks Explained
Graph Neural Networks Part 2. Graph Attention Networks vs. GCNs
Graph Neural Networks Part 3: How GraphSAGE Handles Changing Graph Structure
