Conclusion: The GNN Design Space

The last lecture (given by Charilaos Kanatsoulis) starts with a recap of the whole course in three pictures.

Slide 3, deep learning in graphs: the input is a network; it passes through graph convolutions, an activation function, regularization (e.g. dropout) and more graph convolutions; the outputs are predictions: node labels, new links, and generated graphs and subgraphs. These three outputs match the three big task families of the course: node-level, link-level and generation (Lecture 18).

Slide 4, the general GNN framework (from the "Design Space of GNNs" paper, You, Ying, Leskovec, NeurIPS 2020). The picture shows two stacked GNN layers with five numbered parts:

1. Message: each neighbor computes a message.
2. Aggregation: messages are combined at the target node.
3. Layer connectivity: how layers are stacked (plain stacking, skip connections, …).
4. Graph augmentation: changing the input graph or features (adding virtual nodes, sampling neighbors, …).
5. Learning objective: supervised or self-supervised, node/edge/graph level.

Slide 5, the GNN training pipeline: input graph → graph neural network → node embeddings → prediction head → predictions; predictions are compared with labels by a loss function, and with evaluation metrics. The output of a GNN is a set of node embeddings \(\{\mathbf h_v^{(L)},\ \forall v\in G\}\).

Today's question builds on this: every box in these pictures has many possible choices. Which choices should we make for a new task?

Slide 6 states the key question of GNN architectural design: how do we find a good GNN design for a specific task? It is important but hard:

• Domain experts want to use a state-of-the-art GNN on their task, but there are many possible architectures: GCN, GraphSAGE, GAT, GIN, …
• The best design for one task can perform badly on another.
• Redoing a hyperparameter grid search for every new task is not feasible.

Topic for today: study the GNN design space and the task space, and GraphGym, a platform for exploring GNN designs and tasks.

Slide 7 fixes the vocabulary (keep it exact, the rest of the lecture depends on it):

• Design: one concrete model instance, e.g. a 4-layer GraphSAGE.
• Design dimension: a property that characterizes a design, e.g. the number of layers \(L\in\{2,4,6,8\}\).
• Design choice: the value selected in a dimension, e.g. \(L = 2\).
• Design space: the Cartesian product of all design dimensions.
• Task: a specific task, e.g. node classification on Cora, graph classification on ENZYMES.
• Task space: all the tasks we care about.

Slide 8, intra-layer design: a GNN layer = transformation + aggregation. The paper proposes one general layer: Linear → BatchNorm → Dropout → Activation → Aggregation. The first four form the "GNN transformation" applied to each message; the last combines the messages. The four red boxes (BatchNorm, Dropout, Activation, Aggregation) are the 4 intra-layer design dimensions. So inside one layer we choose whether to use batch normalization, how much dropout, which activation, and which aggregation.

Slide 9, inter-layer design: different ways to organize layers. The figure shows the full stack:

• Pre-process layers (MLP layers before message passing): important when an expressive node-feature encoder is needed, e.g. when nodes are images or text.
• Message-passing layers (GNN layers), joined by a chosen layer connectivity. Skip connections improve the performance of deep GNNs.
• Post-process layers (MLP layers after message passing): important when reasoning or transformation over node embeddings is needed, e.g. graph classification or knowledge graphs.

Slide 10, learning configuration: batch size, learning rate, optimizer, training epochs. These are often neglected in the literature, but the authors found they have a high impact on performance.

Slide 11 lists the concrete choices (each group has 4 dimensions):

• Intra-layer: batch normalization {True, False}; dropout {False, 0.3, 0.6}; activation {ReLU, PReLU, Swish}; aggregation {mean, max, sum}.
• Inter-layer: layer connectivity {stack, skip-sum, skip-cat}; pre-process layers {1, 2, 3}; message-passing layers {2, 4, 6, 8}; post-process layers {1, 2, 3}.
• Learning configuration: batch size {16, 32, 64}; learning rate {0.1, 0.01, 0.001}; optimizer {SGD, Adam}; training epochs {100, 200, 400}.

In total: about 315K possible designs. The authors do not want to (and cannot) test them all. Their purpose is a mindset transition: show that studying a design space is more effective than studying individual GNN designs.

Check the count yourself: \(2\cdot3\cdot3\cdot3\) (intra) \(\times\ 3\cdot3\cdot4\cdot3\) (inter) \(\times\ 3\cdot3\cdot2\cdot3\) (learning) \(= 54\cdot108\cdot54 = 314{,}928 \approx 315\text{K}\).

Slide 12: how should we categorize GNN tasks? The common practice is node / edge / graph level. This is reasonable but not precise: "predict a node's clustering coefficient" and "predict a node's subject area in a citation network" are both node prediction, but completely different tasks (one is purely structural, one depends on text features). A precise hand-made taxonomy is very hard: it is subjective, and new tasks always appear. The innovation: a quantitative task-similarity metric, to understand tasks and to transfer the best model across tasks.

Slide 13, the metric in three steps:

1. Select a fixed set of anchor models \(M_1,\dots,M_5\) (in practice 12).
2. Characterize a task by the ranking of the anchor models' performance on it.
3. Tasks with similar rankings are similar.

Example table: on Task A the ranking is \(M_1,M_2,M_3,M_4,M_5\) (similarity to A: 1.0). On Task B it is \(M_1,M_3,M_2,M_4,M_5\) (similarity 0.8): A and B are similar. On Task C it is \(M_5,M_1,M_4,M_3,M_2\) (similarity −0.4): A and C are not similar.

These numbers are exactly Kendall rank correlations: among the 10 pairs of models, B disagrees with A on one pair, giving \((9-1)/10 = 0.8\); C agrees on 3 pairs and disagrees on 7, giving \((3-7)/10 = -0.4\). (Check it yourself.)

Slides 14–15, how to choose the anchors: (1) take a small dataset, e.g. node classification on Cora; (2) randomly sample \(N\) models from the design space and run them on it (e.g. \(N = 100\)); (3) sort them by performance and pick \(M\) models evenly spaced from the worst to the best (12 in the experiments). The goal is to cover a wide spectrum of models, because a model that is bad on one task can be great on another. Anchors that are all good would not tell tasks apart.

Slide 16, the task collection: 32 tasks (link prediction results are in the paper's appendix):

• 6 real-world node classification tasks;
• 12 synthetic node classification tasks: predict node properties such as clustering coefficient and PageRank;
• 6 real-world graph classification tasks;
• 8 synthetic graph classification tasks: predict graph properties such as average path length.

Slide 17 shows the whole study as one figure: (a) the GNN design space and (b) the GNN task space are combined in (c) controlled random search; then (d) design choices are ranked by performance, and (e) the rankings are analyzed. A side table shows the best designs found in different tasks. The study gives: general guidelines for GNN design, an understanding of GNN tasks, and transfer of the best designs across tasks.

Slide 18 asks: is BatchNorm generally useful for GNNs? The common practice: (1) pick one model (e.g. a 5-layer, 64-dim GCN); (2) train it with BN = True and BN = False and compare. The conclusion then holds only for that one model and task. The new approach: there are \(315\text{K models}\times 32\text{ tasks}\approx 10\text{M}\) model–task combinations. (1) Sample from these 10M combinations; (2) rank the models with BN = True vs False. How do we make this scalable and convincing?

Slide 19, step (a): sample random model–task configurations (random activation, number of layers, connectivity, task level, dataset, …) and, for each one, perturb only the dimension of interest: BatchNorm = [True, False]. Everything else stays fixed, so each pair is a controlled experiment. The computational budget is also controlled across all models (so a model does not win just by having more parameters).

Slide 20, steps (b) and (c). (b) Within each pair, rank the two choices by validation performance (lower rank is better). The table shows three pairs: accuracies 0.75 vs 0.54 give True rank 1, False rank 2; 0.88 vs 0.88 is a tie (both rank 1); 0.89 vs 0.36 gives True rank 1, False rank 2. (c) Plot the average and the distribution of the ranks of each choice over many pairs. In the plot, BN = True has a lower average rank than False, and its rank distribution is concentrated at 1.

Why ranks, not raw accuracy? Accuracies on different tasks are not comparable (0.54 on one dataset can be excellent, on another terrible). Ranks inside a controlled pair remove the task scale. Summary: this method can convincingly evaluate any new design dimension, e.g. a new GNN layer you propose.

Each result plot has two rows: the average accuracy ranking (bars, lower is better) and the distribution of rankings (violin plots). A dotted red box marks the winning choice.

Slide 21, intra-layer designs:

• Batch normalization: True is better. Explanation: GNNs are hard to optimize, and BN helps optimization.
• Dropout: 0.0 (none) is best, 0.3 worse, 0.6 worst. Explanation: GNNs underfit more often than they overfit, so extra regularization hurts.
• Activation: PReLU is best, ahead of ReLU and Swish. The authors call this their new finding.
• Aggregation: sum is best, then mean, then max. Explanation: sum is the most expressive aggregator (recall Lecture 6 and GIN: sum can count neighbors, mean and max cannot).

Slide 22, inter-layer designs:

• Pre-process layers (1, 2, 3), post-process layers (1, 2, 3) and message-passing layers (2, 4, 6, 8): the average ranks are close and the distributions overlap. The optimal number of layers is hard to decide and highly dependent on the task.
• Layer connectivity: skip-cat is best, then skip-sum, then plain stack. Explanation: skip connections enable a hierarchical node representation (embeddings from several depths are kept).

Slide 23, learning configurations:

• Batch size (16, 32, 64) and learning rate (0.001, 0.01, 0.1): no clear winner; highly task-dependent.
• Optimizer: Adam beats SGD. Explanation: Adam is more robust.
• Training epochs: 400 beats 200 and 100. Explanation: more training epochs is better (again consistent with underfitting).

Slide 24: the best design varies a lot across tasks, which shows that studying the task space is crucial. Examples from the bar plots (average ranking):

• Aggregation: max is best on BZR, mean on PROTEINS, sum on smallworld.
• Message-passing layers: 8 is best on Cora and on scalefree, but 2 is best on IMDB.

So the general guidelines of Results 1 are averages; for one specific task the best choice can be the opposite.

Slide 25, build the task space. Compute task similarity (as on slide 13) for every pair of the 32 tasks. The heatmap shows the pairwise similarities (computed from 12 anchor models), with tasks named "Level-Dataset-Feature-Label" (e.g. node-smallworld-const-clustering). Is 12 anchors enough? The scatter plot compares similarity from 12 anchors with similarity from all models: Pearson correlation 0.94. So task similarity is cheap to compute and 12 anchors are a good approximation.

Slide 26: the task space is informative. The heatmap splits into two blocks:

• Group 1: tasks that rely on feature information: node/graph classification where the input graphs have high-dimensional features (Cora nodes have 1000+ dimensional features); e.g. AmazonComputers, AmazonPhoto, CiteSeer, CoauthorCS, CoauthorPhysics, Cora.
• Group 2: tasks that rely on structural information: nodes have few features and predictions depend heavily on graph structure, e.g. predicting clustering coefficients on synthetic scalefree and smallworld graphs.

Slide 27 projects the tasks to 2D with PCA: Group 1 (blue, feature-rich datasets) and Group 2 (red, structural tasks) form separate clusters; circles are node-level and crosses graph-level tasks. Key finding: similar tasks have similar best architectures. The table: Task A (2 pre, 8 MP, 2 post layers, skip-sum, sum) and Task B (1, 8, 2, skip-sum, sum) are close in task space and have nearly the same best design; Task C (2, 6, 2, skip-cat, mean) is far away and its best design differs.

Slide 28, a case study: transfer the best designs to the unseen OGB task ogbg-molhiv (molecule property prediction). It is unlike the 32 tasks: 20× larger, imbalanced (1.4% positive), and it needs out-of-distribution generalization. Steps for any new task:

1. Measure the performance of the 12 anchor models on the new task.
2. Compute the similarity between the new task and the existing tasks.
3. Recommend the best designs from existing tasks with high similarity.

The scatter plot: for each existing task, its similarity with ogbg-molhiv (x-axis) against how well its best design ranks after transfer (y-axis). Pearson correlation 0.78: the more similar the task, the better its design transfers.

Slide 29 picks two tasks. Task A: graph-scalefree-const-path (similar to OGB, similarity 0.47); its best design is (1, 8, 3, skipcat, sum), i.e. 1 pre-process layer, 8 message-passing layers, 3 post-process layers, skip-cat, sum aggregation. Task B: node-CoauthorPhysics (not similar, similarity −0.61); best design (1, 4, 2, skipcat, max). After transfer to ogbg-molhiv, A's design reaches ROC-AUC 0.785, above the previous state of the art 0.771; B's design gets only 0.736. So the task space guides model transfer to new tasks, with only 12 cheap anchor runs instead of a full search.

Slide 30 summarizes the paper: a systematic study giving (1) general guidelines for GNN design, (2) understanding of GNN tasks, (3) transfer of the best designs across tasks, and (4) GraphGym, an easy-to-use code platform for GNNs.

The second part of the lecture wraps up the course.

Slide 32: the modern deep learning toolbox is designed for simple sequences and grids. Images are grids of pixels (CNNs); text and speech are sequences (RNNs, transformers).

Slide 33: how can we build neural networks that are much more broadly applicable? Graphs are the new frontier of deep learning.

Slide 34 shows the variety of relational data: knowledge graphs, gene regulatory networks, scene graphs, code graphs, molecules and 3D shapes (meshes). The main question of the course: how do we take advantage of relational structure for better prediction?

Slide 35 repeats the picture of slide 3: input network → GNN → predictions (node labels, new links, generated graphs and subgraphs).

Slide 36, models of interest and their invariances: each successful architecture builds in a symmetry of its data.

• Perceptrons: function regularity.
• CNNs: translation.
• Group-CNNs: translation + rotation, global groups.
• LSTMs: time warping.
• DeepSets / Transformers: permutation (of set elements / tokens).
• GNNs: permutation (of node labels).
• Intrinsic CNNs (on meshes and manifolds): isometry / gauge choice.

This is the "geometric deep learning" view: a GNN is the architecture whose output does not depend on how we number the nodes, just as a CNN does not depend on where an object sits in the image. It links back to Lecture 6 (permutation invariance and equivariance) and to the expressiveness results (WL test).

Slide 37, the bottom line:

• Many real-world problems contain rich relational structure: molecules and proteins can be treated as strings or as graphs; relational databases have primary–foreign key structure (Lectures 12–13).
• Identifying and using this structure leads to better predictions: AlphaFold (protein structure), biomedicine, recommender systems.

Slide 38, what the course covered: theory (models, architectures, approaches), practice (Colab notebooks, homeworks), creative research (the course project), and real-world use cases and applications.

Slide 39, what next. The project write-ups are due at the deadline shown (no late days). For further study the slide recommends CS246: Mining Massive Datasets (Winter): data mining and machine learning for big data that does not fit in memory or on one machine, fast clever algorithms for real-world problems, and distributed frameworks such as MapReduce and Spark.

For a self-learner: a good review exercise is to go back to slide 4's five design parts (message, aggregation, layer connectivity, graph augmentation, learning objective) and name, for each, the lecture where it was taught and one concrete choice you now know (e.g. aggregation: sum in GIN, attention in GAT).