Scoring Connections We Have Not Observed

Botie’s network map is incomplete. Some connections were recorded, while others have not yet been inspected. He wants a useful order in which to check possible missing links.

We can score a possible connection using the representations of its two endpoints. But how were those representations obtained? If they already used the connection we supposedly held out, the test would reveal its own answer. We will calculate a simple pair score and follow which edges are available at each stage.

Node A: [1, 0]
Node B: [2, 1]
Logit = (1 × 2) + (0 × 1) = 2

Sigmoid(2) = 1 / (1 + exp(−2)) ≈ 0.881

Change one candidate representation and inspect the pair score. A high score is a reason to investigate a connection, not evidence that an unrecorded edge is known to exist.

0.8808

An undirected graph usually needs each pair only once and may exclude self-links. A directed graph needs an orientation. A symmetric dot product cannot distinguish one direction from the reverse.

Observed non-links can be confirmed absences or simply missing records. Sampling unobserved pairs as negatives creates a training convention, not certainty that every sampled pair is impossible.

Record candidate and negative-sampling rules alongside the model.

Take the dot product of the two node vectors to obtain a logit. A sigmoid maps that value to a bounded score. In supervised binary training, a suitable loss compares these outputs with link labels.

Logit = dot([1,0], [2,1]) = 2
Sigmoid(2) ≈ 0.881

Ranking can use logits directly because sigmoid preserves their order.

If a graph encoder passes messages along a supposedly hidden test edge, it has already seen structural information about the answer. Build the training graph without held-out target edges, including reverse copies in an undirected representation.

Time-based link prediction must also exclude edges that appear only later. State whether node features and node identities were available when the prediction would have been made.

Hiding an edge label is insufficient if the edge still remains in adjacency.

import numpy as np
first = np.array([1., 0.])
second = np.array([0., 2.])
logit = first @ second
print(float(logit))
print(float(1 / (1 + np.exp(-logit))))

0.0
0.5

Rank eligible candidate pairs, inspect precision at an operational cutoff, and compare with simple common-neighbour or degree-based baselines. Report performance for new or isolated nodes separately.

High scores may reflect popularity or recording habits. They do not prove a physical connection exists, and a symmetric decoder is inadequate when direction is essential.

Botie’s workshop scores a pair; the coding exercises also compare candidate rankings.

An undirected connection is often stored twice, once in each direction. Holding out only one stored direction leaves the same connection visible to the encoder through the other entry.

Split unique physical edges first, then construct the training adjacency. Recompute graph-derived features from that training graph too. Removing an edge from the target list alone does not prevent degree counts, paths or embeddings from revealing it.

A dot-product decoder gives the same score to a pair in either order. That can suit an undirected connection task. It cannot express that flow from A to B is likely while flow from B to A is unlikely.

A directed relation needs an order-sensitive decoder or separate source and destination representations. Choose that representation from the relation, not from whichever scoring formula is shortest.

import numpy as np
a = np.array([1.,2.])
b = np.array([3.,1.])
print(float(a@b), float(b@a))
W = np.array([[0.,1.],[0.,0.]])
print(float(a@W@b), float(b@W@a))

5.0 5.0
1.0 6.0

A missing edge is not necessarily a verified absence. Negative sampling chooses unrecorded candidate pairs for a training or evaluation task, and some may be genuine undiscovered connections.

State candidate restrictions, time boundaries and how negatives were obtained. Easy random pairs can inflate scores compared with plausible inspection candidates. Evaluate the ranking against the inspection process the model is intended to support.