ever puzzled the way it’s potential that Fb is aware of who you may know? Or why it generally suggests a complete stranger? This drawback known as hyperlink prediction. In a social community graph, persons 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 matter! It may be used to advocate buddies in social networks, counsel merchandise on e-commerce websites or films on Netflix, or predict protein interactions in biology. On this put up, 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 coated 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 will be discovered right 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 present edges and ask the mannequin to foretell them. In fact, the check set ought to have optimistic samples (actual edges), and unfavourable samples (random node pairs that aren’t related). You may prepare the mannequin on the remaining graph.
The output of the mannequin is a hyperlink rating or chance for every node pair. You may consider this with metrics like AUC or common precision.
We’ll 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 ‘simple’ strategies into two classes: native and world. Native heuristics are based mostly 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 identify says, native heuristics depend on the rapid 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 take a look at the shut neighborhood, so capturing the complexity of relationships is proscribed.
Frequent Neighbors
The thought is straightforward: if two nodes share many widespread neighbors, they’re extra prone to be related.
For calculation you rely the variety of neighbors the nodes have in widespread. One problem right here is that it doesn’t take into consideration 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 overall 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 seemingly, 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 provides much less weight to extra in style 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 method?
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 in style 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 kind hyperlinks. Calculation is tremendous simple, 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 generally.
International Heuristics
International heuristics take into account paths, walks, or all the graph construction. They will seize richer patterns, however are extra computationally costly.
Katz Index
Essentially the most well-known world heuristic for Hyperlink Prediction is the Katz Index. It takes all of the totally 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 smart intuitively, as a result of the shorter a path, the extra necessary it’s (buddies in widespread means loads). Alternatively, oblique paths matter as nicely! They will trace at potential hyperlinks.
The Katz System:
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 will calculate the Katz index, let’s select 0.1 for beta:
Rooted PageRank
This methodology makes use of random walks to find out how seemingly 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, you then both stroll to a random neighbor, otherwise you soar again to the primary node. The chance that you find yourself on the second node tells how carefully the 2 nodes are. If the chance is excessive, there’s a good likelihood the nodes must be linked.
ML-Based mostly Hyperlink Prediction
Machine studying approaches take hyperlink prediction past heuristics by studying patterns straight from the information. As a substitute 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 job: for every node pair (u, v), we create a characteristic vector and prepare 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 chance of edges, generally the sting between A and B was extra seemingly, whereas for others the sting between C and D was the higher alternative. By together with a number of scores as options we don’t have to decide on one heuristic. In fact relying on the issue some heuristics may 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 forth.
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 put up we’ll use the Cora dataset to check totally different approaches to hyperlink prediction. The Cora dataset accommodates scientific papers. The perimeters symbolize citations between papers. Let’s prepare 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 prepare/val/check splits
path = osp.be part of(osp.dirname(osp.realpath(__file__)), '..', 'information', 'Planetoid')
dataset = Planetoid(path, identify='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 prepare 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 straight 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 could actually 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 area. The encoder is a Graph Convolutional Community (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 at least one single level.
The following step is the decoding step. The VGAE will guess if there’s an edge between two nodes. It does this by calculating the inside product between the embeddings of the 2 nodes:
The thought behind it’s: if the nodes are nearer collectively within the hidden area, it’s extra seemingly they’re related.
VGAE visualized:
How does the mannequin study? It optimizes two issues:
- Reconstruction Loss: Do the expected edges match the actual ones?
- KL Divergence Loss: Is the latent area 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
# identical as earlier than
from torch_geometric import seed_everything
seed_everything(42)
path = osp.be part of(osp.dirname(osp.realpath(__file__)), '..', 'information', 'Planetoid')
dataset = Planetoid(path, identify='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
# prepare VGAE mannequin
for epoch in vary(1, 101):
vgae.prepare()
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.system)
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! Large 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 stylish: as an alternative of world node embeddings, SEAL appears on the native subgraph round every node pair.
Right here’s a step-by-step rationalization:
- 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 mirror 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 may be very highly effective as a result of it learns structural patterns straight 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 pattern code from PyTorch geometric (test it out by following the hyperlink), since SEAL requires fairly some processing. You may acknowledge the totally different steps within the code (getting ready the information, extracting the subgraphs, labeling the nodes). Coaching for 50 epochs provides 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 drawback, VGAE may be the only option (VGAE is considerably sooner than SEAL). In fact this could fluctuate, relying in your drawback.
Conclusion
On this put up, 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 job complexity, it’s value exploring each!
Thanks for studying, till subsequent time!
Associated
Graph Neural Networks Half 1. Graph Convolutional Networks Defined
Graph Neural Networks Half 2. Graph Consideration Networks vs. GCNs
Graph Neural Networks Half 3: How GraphSAGE Handles Altering Graph Construction