GNN Augmentation and Training

Lecture 4 built a general GNN framework with five parts: (1) message, (2) aggregation, (3) layer connectivity, (4) graph augmentation, (5) learning objective. This lecture covers parts 4 and 5. Slide 10 shows the framework figure again (You, Ying and Leskovec, "Design Space of Graph Neural Networks", NeurIPS 2020), now highlighting part (4), graph manipulation. Its idea in one line: raw input graph \(\neq\) computational graph. There are two kinds of manipulation: graph feature augmentation and graph structure manipulation.

Slide 11: so far we assumed raw input graph = computational graph. Reasons to break this assumption:

• Feature level: the input graph lacks features → use feature augmentation.
• Structure level:
  • the graph is too sparse → message passing is inefficient (information needs many hops to travel);
  • the graph is too dense → message passing is too costly (a hub must aggregate a huge number of messages);
  • the graph is too large → the computational graph does not fit into a GPU.
• More generally: it is just unlikely that the input graph happens to be the optimal computation graph for embeddings. The graph was recorded for some other reason (who follows whom, which atoms bond), not designed for message passing.

Slide 12 pairs each problem with a fix:

• Graph feature manipulation: input graph lacks features → feature augmentation (covered more in Lecture 7).
• Graph structure manipulation: too sparse → add virtual nodes / edges; too dense → sample neighbours when doing message passing; too large → sample subgraphs to compute embeddings (covered later in the lecture "Scaling up GNNs").

Check yourself: in a bipartite user–item graph, what does the \((u,u')\) entry of \(A^2\) count? show answer

The number of items that users \(u\) and \(u'\) have in common.

Why do we need feature augmentation? Reason (1) (slides 13–14): the input graph does not have node features. This is common when we only have the adjacency matrix. A GNN needs some vector \(\mathbf{h}_v^{(0)}\) at each node to start message passing, so we must invent one. Two standard approaches:

• (a) Assign constant values to nodes (slide 13). The figure shows a small graph with the value 1 written next to every node.
• (b) Assign unique IDs to nodes (slide 14), and convert the IDs into one-hot vectors. In the figure the graph has 6 nodes, so the total number of IDs is 6; the node with ID = 5 gets the one-hot vector \([0,0,0,0,1,0]\).

Slide 15 compares the two in a table:

• Expressive power. Constant: medium — all the nodes are identical, but the GNN can still learn from the graph structure (for example, with sum aggregation a node can learn its degree). One-hot: high — each node has a unique ID, so node-specific information can be stored.
• Inductive learning (generalise to unseen nodes). Constant: high — simple to generalise to new nodes: assign them the constant feature, then apply the GNN. One-hot: low — new nodes bring new IDs, and the GNN does not know how to embed unseen IDs.
• Computational cost. Constant: low — only a 1-dimensional feature. One-hot: high — a \(|V|\)-dimensional feature, which cannot be applied to large graphs.
• Use cases. Constant: any graph, inductive settings (generalise to new nodes). One-hot: small graphs, transductive settings (no new nodes).

Intuition: one-hot IDs make the first GNN layer \(\mathbf{W}\mathbf{h}_v^{(0)}\) pick out one column of \(\mathbf{W}\) per node — so each node gets its own free trainable vector, exactly like the shallow embeddings of Lecture 3 (DeepWalk, node2vec). That explains both the high expressiveness and the failure to generalise.

Reason (2) for feature augmentation (slide 16): certain structures are hard to learn by a GNN. Example: the cycle-count feature. Can a GNN learn the length of the cycle that node \(v_1\) lies on? The figure shows \(v_1\) on a triangle (cycle of length 3) and \(v_1\) on a square (cycle of length 4). The answer: unfortunately, no.

Slide 17 explains why. \(v_1\) cannot tell which graph it lives in, because all the nodes in both graphs have degree 2. Unroll the computational graph of \(v_1\): it has 2 children, each child has 2 children, and so on — the same binary tree in both cases (all nodes have the same feature, so the tree carries no other information). The slide adds a third case: \(v_1\) on a cycle of infinite length (an infinite path, drawn as a line with dots at both ends) gives the same binary tree too. So a message-passing GNN maps \(v_1\) to the same embedding in all three graphs.

Slide 18 gives the fix (from You, Gomes-Selman, Ying and Leskovec, "Identity-aware Graph Neural Networks", AAAI 2021): use the cycle count as an augmented node feature. The feature vector counts cycles by length, starting from length 0. For \(v_1\) on the triangle the vector is \([0,0,0,1,0,0]\) (a 1 at position 3); for \(v_1\) on the square it is \([0,0,0,0,1,0]\) (a 1 at position 4). Now the two nodes have different input features, so the GNN can separate them.

Other augmented features in the same spirit: node degree, clustering coefficient, PageRank, centrality — any of the hand-crafted features from Lecture 1 can be appended to \(\mathbf{x}_v\).

This is a preview of Lecture 6: a message-passing GNN can only distinguish nodes whose rooted computation trees differ. Hand-computed structural features are one way to break that ceiling; Lecture 7 shows others.

Check yourself: a 2-layer GNN, constant features. Does \(v_1\) on a triangle get the same embedding as a node in the middle of a long path? show answer

Yes — both see a node with 2 neighbours, each with 2 neighbours.

Augmenting sparse graphs (slide 19). Besides virtual edges, we can add a virtual node that connects to all the nodes in the graph. Suppose two nodes in a sparse graph have shortest-path distance 10. After adding the virtual node, all pairs of nodes are at distance at most 2 (node A – virtual node – node B). Benefit: this greatly improves message passing in sparse graphs. The figure shows a small graph with one extra grey node above it, joined to every original node.

Neighbour sampling for dense graphs (slide 20; Hamilton et al., "Inductive Representation Learning on Large Graphs", NeurIPS 2017 — GraphSAGE). Our approach so far: all the neighbours are used for message passing. Problem: dense or large graphs and high-degree nodes make this expensive. New idea: (randomly) determine a node's neighbourhood for message passing. The figure shows target node A in the input graph and its computation tree with every neighbour present.

• Slide 21: for example, randomly choose 2 neighbours to pass messages. Only nodes \(B\) and \(D\) pass a message to \(A\); the other branches are crossed out in red in both the graph and the tree.
• Slide 22: next time we compute the embeddings, we can sample different neighbours — now only \(C\) and \(D\) pass a message to \(A\). (Sampling also happens at the second level of the tree.)
• Slide 23 (Ying et al., "Graph Convolutional Neural Networks for Web-Scale Recommender Systems", KDD 2018 — PinSage): in expectation we get embeddings similar to the case where all the neighbours are used. Benefit: a large reduction in computational cost. "And in practice it works great!"

Why "in expectation"? With mean aggregation, the mean of a uniformly random subset of neighbours is an unbiased estimate of the mean over all neighbours. Each epoch sees a different sample, so the noise averages out during training, much like mini-batch SGD.

Check yourself: a virtual node connected to everyone in a social graph with 1 million nodes. What new cost problem does it create? show answer

The virtual node has degree 1 million — it is itself a super-dense hub, so you may need to sample its neighbours too.

Slide 25 returns to the framework figure, now highlighting part (5), the learning objective. Next question: how do we train a GNN?

Slide 26 draws the full GNN training pipeline as a row of boxes: Input graph → Graph Neural Network → Node embeddings → Prediction head → Predictions; the predictions are compared with the Labels by a Loss function (for training) and by Evaluation metrics (for judging the model). So far we have covered the first three boxes (shown inside a dashed frame). The output of a GNN is a set of node embeddings \(\{\mathbf{h}_v^{(L)},\ \forall v\in G\}\). The rest of the lecture walks through the other boxes in order: (1) prediction heads, (2) labels, (3) loss, (4) metrics, (5) dataset split.

Slide 27 highlights box (1): different prediction heads for node-level, edge-level and graph-level tasks. Slide 28: the idea is that different task levels require different prediction heads. The figure shows one graph with three arrows: node-level prediction (one node), edge-level prediction (a pair of nodes) and graph-level prediction (the whole graph).

Node-level prediction (slide 29): we can make a prediction directly from the node embeddings. After GNN computation we have \(d\)-dimensional embeddings \(\{\mathbf{h}_v^{(L)}\in\mathbb{R}^d,\ \forall v\in G\}\). Suppose we want a \(k\)-way prediction: classification among \(k\) categories, or regression on \(k\) targets. Then

\[ \hat{\mathbf{y}}_v=\mathrm{Head}_{\text{node}}\big(\mathbf{h}_v^{(L)}\big)=\mathbf{W}^{(H)}\mathbf{h}_v^{(L)},\qquad \mathbf{W}^{(H)}\in\mathbb{R}^{k\times d}. \]

\(\mathbf{W}^{(H)}\) maps the embedding \(\mathbf{h}_v^{(L)}\in\mathbb{R}^d\) to \(\hat{\mathbf{y}}_v\in\mathbb{R}^k\), so that we can compute the loss. For classification, a softmax is then applied (see the loss block).

Check yourself: why is a linear head usually enough? show answer

The GNN layers already did the non-linear work; the head only has to read the answer out of the embedding. If not, add post-processing MLP layers, as in Lecture 4.

Edge-level prediction (slide 30): make a prediction from pairs of node embeddings. For a \(k\)-way prediction,

\[ \hat{\mathbf{y}}_{uv}=\mathrm{Head}_{\text{edge}}\big(\mathbf{h}_u^{(L)},\mathbf{h}_v^{(L)}\big). \]

The figure marks two nodes \(u\) and \(v\) with a question mark between them. What are the options for \(\mathrm{Head}_{\text{edge}}\)?

(1) Concatenation + Linear (slide 31). We have seen this in graph attention (the attention mechanism of GAT in Lecture 4):

\[ \hat{\mathbf{y}}_{uv}=\mathrm{Linear}\big(\mathrm{Concat}(\mathbf{h}_u^{(L)},\mathbf{h}_v^{(L)})\big). \]

Here \(\mathrm{Linear}(\cdot)\) maps the \(2d\)-dimensional concatenated vector to a \(k\)-dimensional output (\(k\)-way prediction). The figure stacks the two embedding bars, then a Linear box, then \(\hat y_{uv}\).

(2) Dot product (slide 32):

\[ \hat{y}_{uv}=\big(\mathbf{h}_u^{(L)}\big)^{\!\top}\mathbf{h}_v^{(L)}. \]

This only gives a 1-way prediction (a single number), e.g. link prediction: does an edge exist? To get a \(k\)-way prediction, do something similar to multi-head attention: introduce trainable matrices \(\mathbf{W}^{(1)},\dots,\mathbf{W}^{(k)}\) and compute one bilinear score per head,

\[ \hat{y}_{uv}^{(i)}=\big(\mathbf{h}_u^{(L)}\big)^{\!\top}\mathbf{W}^{(i)}\mathbf{h}_v^{(L)},\quad i=1,\dots,k,\qquad \hat{\mathbf{y}}_{uv}=\mathrm{Concat}\big(\hat{y}_{uv}^{(1)},\dots,\hat{y}_{uv}^{(k)}\big)\in\mathbb{R}^k. \]

A difference worth noticing: the plain dot product is symmetric (\(\hat y_{uv}=\hat y_{vu}\)), which suits undirected friendship. Concat + linear and a non-symmetric \(\mathbf{W}\) can be asymmetric, which suits directed relations like "follows".

Graph-level prediction (slide 33): make a prediction using all the node embeddings in the graph. For \(k\)-way prediction,

\[ \hat{\mathbf{y}}_G=\mathrm{Head}_{\text{graph}}\big(\{\mathbf{h}_v^{(L)}\in\mathbb{R}^d,\ \forall v\in G\}\big). \]

\(\mathrm{Head}_{\text{graph}}(\cdot)\) is similar to \(\mathrm{AGG}(\cdot)\) in a GNN layer: it turns a set of vectors into one vector. The figure puts the whole graph under one aggregation box, next to the message/aggregation picture of a GNN layer.

Options (slide 34; the citation is Xu, Hu, Leskovec and Jegelka, "How Powerful Are Graph Neural Networks?", ICLR 2019 — the GIN paper of Lecture 6):

1. Global mean pooling: \(\hat{\mathbf{y}}_G=\mathrm{Mean}(\{\mathbf{h}_v^{(L)}\in\mathbb{R}^d,\ \forall v\in G\})\).
2. Global max pooling: \(\hat{\mathbf{y}}_G=\mathrm{Max}(\{\mathbf{h}_v^{(L)}\in\mathbb{R}^d,\ \forall v\in G\})\).
3. Global sum pooling: \(\hat{\mathbf{y}}_G=\mathrm{Sum}(\{\mathbf{h}_v^{(L)}\in\mathbb{R}^d,\ \forall v\in G\})\).

These options work great for small graphs. Can we do better for large graphs?

Slide 35 shows the issue: global pooling over a (large) graph loses information. Toy example with 1-dimensional node embeddings:

• \(G_1\): \(\{-1,-2,0,1,2\}\); \(G_2\): \(\{-10,-20,0,10,20\}\).
• Clearly \(G_1\) and \(G_2\) have very different node embeddings, so their structures should be different.
• Global sum pooling: \(\hat y_{G_1}=\mathrm{Sum}(\{-1,-2,0,1,2\})=0\) and \(\hat y_{G_2}=\mathrm{Sum}(\{-10,-20,0,10,20\})=0\). We cannot differentiate \(G_1\) and \(G_2\)!

Slide 36 gives this year's fix: to embed a graph, add a virtual super node that connects to all the nodes in the graph (the figure shows a grey node above the graph, linked to every node). Then the graph embedding is the embedding of the super node. Benefit: the GNN learns how to encode the entire input graph, instead of using a fixed pooling rule.

Check yourself: in the toy example, does mean pooling help? show answer

Max pooling? (Mean gives 0 and 0 — no. Max gives 2 and 20 — yes here, but it is easy to build cases where max fails, e.g. \(\{0,2\}\) vs \(\{0,0,2\}\).)

Slide 38 highlights box (2) of the pipeline: where does the ground truth come from? Supervised labels or unsupervised signals.

Slide 39:

• Supervised learning on graphs: labels come from external sources, e.g. predict the drug likeness of a molecular graph.
• Unsupervised learning on graphs: signals come from the graphs themselves, e.g. link prediction: predict whether two nodes are connected.
• Sometimes the difference is blurry. We still have "supervision" in unsupervised learning, e.g. train a GNN to predict the node clustering coefficient. An alternative name for "unsupervised" here is "self-supervised".

Supervised labels come from the specific use case (slide 40):

• Node labels \(y_v\): in a citation network, which subject area a node belongs to.
• Edge labels \(y_{uv}\): in a transaction network, whether an edge is fraudulent.
• Graph labels \(y_G\): among molecular graphs, the drug likeness of the graphs.

Advice: reduce your task to node / edge / graph labels, since they are easy to work with. For example, if we know that some nodes form a cluster, we can treat the cluster a node belongs to as a node label.

Unsupervised (self-supervised) signals (slide 41). The problem: sometimes we only have a graph, without any external labels. The solution: find supervision signals within the graph. For example, let the GNN predict:

• Node level \(y_v\): node statistics such as clustering coefficient or PageRank.
• Edge level \(y_{uv}\): link prediction — hide the edge between two nodes and predict whether there should be a link.
• Graph level \(y_G\): graph statistics, for example predict whether two graphs are isomorphic.

These tasks do not require any external labels.

Why would you train a GNN to predict PageRank, which you could just compute? Because the goal is not the prediction itself but the embeddings it forces the GNN to learn — a form of pre-training. The learned weights can then be fine-tuned on a task with few real labels.

Slide 42 highlights box (3): how do we compute the final loss? Classification loss or regression loss.

Setting (slide 43): we have \(N\) data points, each a node, edge or graph. Node level: prediction \(\hat{\mathbf{y}}_v^{(i)}\), label \(\mathbf{y}_v^{(i)}\); edge level: \(\hat{\mathbf{y}}_{uv}^{(i)}\), \(\mathbf{y}_{uv}^{(i)}\); graph level: \(\hat{\mathbf{y}}_G^{(i)}\), \(\mathbf{y}_G^{(i)}\). From now on, \(\hat{\mathbf{y}}^{(i)}\) and \(\mathbf{y}^{(i)}\) refer to predictions and labels at any level.

Slide 44: classification — labels \(\mathbf{y}^{(i)}\) have discrete values (e.g. which category a node belongs to). Regression — labels have continuous values (e.g. the drug likeness of a molecular graph). GNNs can be applied to both settings; the differences are the loss function and the evaluation metrics.

Classification loss (slide 45). Cross-entropy (CE) is a very common loss for classification. For a \(K\)-way prediction on the \(i\)-th data point:

\[ \mathrm{CE}\big(\mathbf{y}^{(i)},\hat{\mathbf{y}}^{(i)}\big)=-\sum_{j=1}^{K}\mathbf{y}_j^{(i)}\log\big(\hat{\mathbf{y}}_j^{(i)}\big), \]

where \(\mathbf{y}^{(i)}\in\mathbb{R}^K\) is the one-hot label encoding (the slide's example: \([0,0,1,0,0]\)) and \(\hat{\mathbf{y}}^{(i)}\in\mathbb{R}^K\) is the prediction after \(\mathrm{Softmax}(\cdot)\) (example: \([0.1,0.3,0.4,0.1,0.1]\)). Total loss over all \(N\) training examples: \(\mathrm{Loss}=\sum_{i=1}^N\mathrm{CE}(\mathbf{y}^{(i)},\hat{\mathbf{y}}^{(i)})\).

With a one-hot label only one term survives: CE is \(-\log\) of the probability given to the correct class. In the slide's example that is \(-\log 0.4\approx 0.92\). A perfect prediction (probability 1) gives loss 0.

Regression loss (slide 46). We often use Mean Squared Error (MSE), also called L2 loss. For a \(K\)-way regression on data point \(i\):

\[ \mathrm{MSE}\big(\mathbf{y}^{(i)},\hat{\mathbf{y}}^{(i)}\big)=\sum_{j=1}^{K}\big(\mathbf{y}_j^{(i)}-\hat{\mathbf{y}}_j^{(i)}\big)^2, \]

where \(\mathbf{y}^{(i)}\in\mathbb{R}^k\) is the real-valued vector of targets (example: \([1.4,2.3,1.0,0.5,0.6]\)) and \(\hat{\mathbf{y}}^{(i)}\in\mathbb{R}^k\) the real-valued vector of predictions (example: \([0.9,2.8,2.0,0.3,0.8]\)). Total loss: \(\mathrm{Loss}=\sum_{i=1}^N\mathrm{MSE}(\mathbf{y}^{(i)},\hat{\mathbf{y}}^{(i)})\).

Check yourself: compute the MSE for the slide's example. show answer

Differences 0.5, −0.5, −1.0, 0.2, −0.2; squares 0.25+0.25+1.0+0.04+0.04 = 1.58.

Slide 47 highlights box (4): how do we measure the success of a GNN? Accuracy, ROC AUC. Slide 48: we use standard evaluation metrics (the content is in any ML course); in practice we use sklearn. Suppose we make predictions for \(N\) data points.

Regression (slide 48):

\[ \mathrm{RMSE}=\sqrt{\sum_{i=1}^{N}\frac{\big(\mathbf{y}^{(i)}-\hat{\mathbf{y}}^{(i)}\big)^2}{N}},\qquad \mathrm{MAE}=\frac{\sum_{i=1}^{N}\big|\mathbf{y}^{(i)}-\hat{\mathbf{y}}^{(i)}\big|}{N}. \]

Classification (slide 49). (1) Multi-class: simply report the accuracy, \(\frac1N\sum_{i}\mathbb{1}\big[\arg\max(\hat{\mathbf{y}}^{(i)})=\mathbf{y}^{(i)}\big]\). (2) Binary: some metrics are sensitive to the classification threshold — accuracy, precision / recall (if predictions lie in \([0,1]\), we use 0.5 as the threshold). One metric is agnostic to the threshold: ROC AUC.

Slide 50 defines them with the confusion matrix (rows: predicted positive / negative; columns: actually positive / negative; cells TP, FP, FN, TN):

\[ \text{Accuracy}=\frac{TP+TN}{TP+TN+FP+FN}=\frac{TP+TN}{|\text{Dataset}|},\quad P=\frac{TP}{TP+FP},\quad R=\frac{TP}{TP+FN},\quad F1=\frac{2PR}{P+R}. \]

The slide links to sklearn's classification report, which prints all of these per class.

ROC curve (slide 51): it captures the trade-off between TPR and FPR as the classification threshold is varied for a binary classifier, where \(\mathrm{TPR}=\mathrm{Recall}=\frac{TP}{TP+FN}\) and \(\mathrm{FPR}=\frac{FP}{FP+TN}\). The plot (from Wikipedia) has FPR on the x-axis and TPR on the y-axis, both from 0 to 1, with a few classifiers drawn as staircase curves above the diagonal. The dashed diagonal is the performance of a random classifier.

ROC AUC (slide 52): the area under the ROC curve. Intuition: the probability that the classifier ranks a randomly chosen positive instance higher than a randomly chosen negative one. A random classifier gets 0.5, a perfect ranking gets 1.

Why does the threshold not matter? Sweeping the threshold from high to low traces the whole curve; AUC summarises all thresholds at once and depends only on the ordering of the scores. That makes it natural for link prediction, where we care whether true edges are ranked above non-edges.

Check yourself: positives scored 0.9 and 0.6, negatives 0.7 and 0.2. AUC? show answer

Of the 4 positive–negative pairs, 3 are ordered correctly, so AUC = 0.75.

Slide 54 highlights box (5): how do we split the dataset into train / validation / test sets?

Fixed split vs random split (slide 55). Fixed split: split the dataset once. The training set is used for optimising GNN parameters; the validation set for developing the model and hyperparameters; the test set is held out until we report final performance. A concern: sometimes we cannot guarantee that the test set will really be held out. Random split: randomly split the dataset into training / validation / test, and report the average performance over different random seeds.

Why splitting graphs is special. Slide 56: for an image dataset each data point is an image, and the data points are independent — image 5 will not affect our prediction on image 1. The figure assigns nodes 1, 2 to training, 3, 4 to validation and 5, 6 to test, with no edges between them. Slide 57: splitting a graph dataset is different. In node classification each data point is a node, and the data points are not independent: node 5 will affect our prediction on node 1, because it participates in message passing and so affects node 1's embedding. The figure is the same six nodes, now joined by edges. What are our options?

• Solution 1: transductive setting (slide 58). The input graph can be observed in all the dataset splits; we only split the (node) labels. At training time we compute embeddings using the entire graph and train using the labels of nodes 1 and 2. At validation time we compute embeddings using the entire graph and evaluate on the labels of nodes 3 and 4.
• Solution 2: inductive setting (slide 59). We break the edges between splits to get multiple graphs. Now we have 3 independent graphs, and node 5 no longer affects our prediction on node 1. At training time we compute embeddings using the graph over nodes 1 and 2 and train using their labels; at validation time we compute embeddings using the graph over nodes 3 and 4 and evaluate on their labels.

Slide 60 summarises. Transductive: training / validation / test sets are on the same graph; the dataset consists of one graph; the entire graph can be observed in all splits, only the labels are split; applicable only to node / edge prediction tasks. Inductive: the splits are on different graphs; the dataset consists of multiple graphs; each split can only observe the graph(s) within it, and a successful model must generalise to unseen graphs; applicable to node / edge / graph tasks.

Examples. Slide 61, node classification: transductive — all the splits observe the entire graph structure but only the labels of their own nodes (one graph with nodes coloured by split); inductive — with a dataset of 3 graphs, each split contains an independent graph. Slide 62, graph classification: only the inductive setting is well defined, because we have to test on unseen graphs. With a dataset of 5 graphs, each split contains independent graph(s) (the figure: 3 graphs for training, 1 for validation, 1 for test).

Check yourself: in the transductive setting the GNN sees the features of the test nodes during training. Is that cheating? show answer

No: it never sees their labels. It is the realistic scenario of a single network where you know everyone's profile but only some labels.

Slide 63: the goal of link prediction is to predict missing edges. Setting it up is tricky. Link prediction is an unsupervised / self-supervised task: we need to create the labels and dataset splits on our own. Concretely, we hide some edges from the GNN and let the GNN predict whether those edges exist. The figure: the original graph (5 nodes); the input graph to the GNN, with two edges removed; the predictions made by the GNN, with question marks on the hidden edges.

For link prediction we split edges twice.

Step 1 (slide 64): assign 2 types of edges in the original graph.

• Message edges: used for GNN message passing.
• Supervision edges: used for computing objectives.

After step 1, only message edges remain in the graph. Supervision edges are used as supervision for the edge predictions made by the model; they are not fed into the GNN. (In the figure, black edges are message edges, orange ones are supervision edges.)

Step 2: split edges into train / validation / test.

• Option 1: inductive link prediction split (slides 65–66). Suppose we have a dataset of 3 graphs \(G_1,G_2,G_3\). Each inductive split contains an independent graph: \(G_1\) training, \(G_2\) validation, \(G_3\) test. In each split, each graph has 2 types of edges: message edges + supervision edges. Supervision edges are not input to the GNN.
• Option 2: transductive link prediction split (slides 67–70). This is the default setting when people talk about link prediction. Suppose we have a dataset of 1 graph. By definition of "transductive", the entire graph can be observed in all splits. But since edges are both part of the graph structure and the supervision, we must hold out validation / test edges; and to train, we further hold out supervision edges for the training set.

The exact settings (slide 69):

1. At training time: use training message edges to predict training supervision edges.
2. At validation time: use training message edges and training supervision edges to predict validation edges.
3. At test time: use training message edges, training supervision edges and validation edges to predict test edges.

Why a growing number of edges (slide 70)? After training, the supervision edges are known to the GNN. Therefore an ideal model should use the supervision edges in message passing at validation time. The same applies at test time.

Slide 71 summarises: the original graph is split into a graph with 4 types of edges — training message edges, training supervision edges, validation edges and test edges. Note: link prediction settings are tricky and complex, and you may find papers that do link prediction differently. Luckily, PyG and GraphGym fully support it. Slide 72 closes with the full pipeline figure, now including the dataset-split box (a row of small graphs above the pipeline). Implementation resource: GraphGym further implements the full pipeline to facilitate GNN design.

The most common bug: forgetting to remove the supervision edges from the graph during training. The GNN then passes messages along the very edge it must predict, the task becomes trivial, and the scores look excellent but mean nothing.

Check yourself: why can we not use validation edges for message passing at validation time? show answer

They are the answers. Message passing along them would leak the label into the embeddings.