Advanced Graph Neural Networks

Contents

• Introduction and overview
• 0. Background: the message passing foundation
• 1. Scale: sampling, systems
• 2. Expressive power: the Weisfeiler-Lehman test
• 3. Over-squashing and deep GNNs
• 4. Positional and structural encodings
• 5. Graph transformers
• 6. Dynamic and temporal graphs
• 7. Robustness and privacy on graphs
• 8. LLGA bridges: 3D, algorithmic reasoning, GNN × LLM
• 9. Research at DaSciM (Vazirgiannis, Lutzeyer)
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: an engineer who has already trained a GCN or a GAT (M1 Graph ML) and has seen accuracy stall with depth, or two different molecules receive identical scores. Empirical first: we start from what fails in practice — information that does not get through a bottleneck, a GNN that cannot separate two regular graphs — and only then name the concepts that explain it: expressive power, positional encodings, graph transformers.

The module is the research follow-up to M1 Graph ML: the Weisfeiler-Lehman test, over-squashing, positional encodings, graph transformers, temporal graphs, scale and robustness. The official sheet is not published; these notes develop the themes announced by the brochure and flag what they add.

What you will be able to do

• Determine the expressive power of a GNN via the Weisfeiler-Lehman test and deduce what it cannot distinguish.
• Diagnose over-squashing in deep GNNs and choose the appropriate remedies.
• Choose a positional or structural encoding depending on the task and the graph.
• Decide between a message passing GNN and a graph transformer, and justify the choice.
• Handle dynamic and temporal graphs.
• Scale a GNN: sampling, systems and trade-offs.
• Analyze the robustness and privacy specific to relational data.
• Situate the open bridges: 3D, algorithmic reasoning, GNN × LLM.

Official objectives and syllabus

Official syllabus: sheet not published — this module appears neither in the S3 track nor in the S4 track of the SynapseS 2026-2027 catalog (both currently empty), and the master’s wiki indicates that the detailed M2 curriculum is still under development: description, teaching hours and instructor are therefore “not communicated”. The themes below are those carried by the module in the master’s brochure, as restated by this material, mapped to its sections.

The exact split between brochure content and the material’s own deepenings can only be settled when the official sheet is published; in any case, chapters 0 (refresher), 8 (bridges) and 9 (team research) belong to the common structure of the repository’s materials.

Where this course fits in the program

An M2 module (period 1), whose official teaching volume is not communicated. It builds directly on the message passing foundation of Graph Machine and Deep Learning for Generative AI (M1 P2), reactivated in chapter 0. Downstream, it prepares Graph Generative Models and Applications, which builds graphs rather than analyzing them, and Fundamentals of Security and Robustness for AI (M2 P2), which recaps Nettack in one case study and a lab and takes the robustness chapter (ch. 7), where Nettack, its successors and the defenses are developed, as optional upstream reading.

Course outline

• Background: the message passing foundation — the M1 base GNN restated, to expose its limits.
• Scale: sampling, systems — making training fit on industrial graphs, and the experimental hygiene used in every later chapter.
• Expressive power: the Weisfeiler-Lehman test — the exact bound of what a standard GNN can distinguish.
• Over-squashing and deep GNNs — why information compresses poorly in deep architectures, and how to remedy it.
• Positional and structural encodings — giving the graph what transformers have beyond message passing.
• Graph transformers — attention applied to vertices: promises, costs and conditions of use.
• Dynamic and temporal graphs — handling structures that evolve over time.
• Robustness and privacy on graphs — attacking and defending models whose data is relational.
• LLGA bridges: 3D, algorithmic reasoning, GNN × LLM — where this research meets the master’s other axes.
• Research at DaSciM (Vazirgiannis, Lutzeyer) — the laboratory’s papers, read with the module’s grid (self-study).
• Exercises — expressiveness tests, encodings and scaling to carry out yourself.
• Projects and assessment — solo and group project subjects, a mock written exam and a grading rubric (proposals).
• References — the research papers underlying each chapter.

Session plan

24 h in class (assumed) = 8 sessions of 3 h. The sheet of this module publishes no volume: 24 h is the M2 volume published for the Large Language Models course (CSC_53432_EP: 24 h, 2 ECTS) and is assumed here. The split below is our proposal for covering these notes in that time. Level 1 = foundations (reviews, definitions, first worked examples), 2 = core methods, 3 = advanced theory; the level never goes down from one session to the next.

Self-study, outside the 24 h (about 3 h in total): ch. 9 Research at DaSciM — PathNN, GOAT, NGG, pseudo-code prompting (≈ 3 h).

How to study this module

• First secure the foundation: the review chapter 0 conditions everything else in the module.
• Implement the Weisfeiler-Lehman test on small graphs: nothing makes expressive power as concrete as two indistinguishable graphs.
• Read each founding paper after the corresponding chapter: the course is its map, not its substitute.
• Treat the robustness chapter (ch. 7) as the place where Nettack, its successors and the graph defenses are studied for their own sake; the M2 P2 security module only recaps Nettack (case study 9.2 and a lab) and lists ch. 7 as useful if taken.
• Experiment with scaling on large datasets, and measure what sampling costs in quality.
• Explore the bridges of chapter 8 and the research of chapter 9: this is where internship and PhD topics are recruited.

0. Background: the message passing foundation

This chapter restates the M1 message passing GNN and the facts about it that the module assumes; its last item, over-smoothing, is the first of the limits that the following chapters study.

1. Scale: sampling, systems

Real graphs have millions of nodes, and a careless experiment can make a method look better than it is. This chapter covers the systems side of training at scale and the experimental protocol (seeds, confidence intervals, leakage checks) that every later chapter relies on.

• Multi-GPU and partitioning: beyond one GPU, partition the graph (METIS/vertex-cut) across several machines; boundary edges are duplicated (shadow nodes) — the distributed training of the Emerging ML module applies almost as is (parameter server vs all-reduce); PinSage (M1, ch. 6) is the industrial reference;
• Caching and pipelining: neighborhood sampling is a system problem (I/O, reuse of subgraphs across batches — hence PinSage’s importance sampling that freezes the entry points); the frameworks: DGL, PyG + torch_geometric.sampler, Quiver;
• Summary of complexities: Method Memory/batch Bias Notes —————– ————————————- ———– ————————– full-batch \mathcal{O}(|V| + |E|) none breaks beyond ~1M nodes NeighborSampler \mathcal{O}(\prod s_l) variance inductive, standard Cluster-GCN \mathcal{O}(|E|/k) partition deep possible GraphSAINT \mathcal{O}(|\mathcal{G}_s|) corrected dense batches
• Benchmarks and hygiene: OGB (ogbn-arxiv 169k; ogbn-products 2.4M; PCQM4M 3.7M molecules), public leaderboards; the “Benchmarking Graph Neural Networks” paper (Dwivedi et al., 2020/2023) sets the protocol: same parameter budgets, same splits, multiple seeds with confidence intervals — many “SOTAs” die by this yardstick; Bayesian hyperparameter search is the rule (gains < 0.5 point demanding a strict protocol);
• Good research practice: always publish the variance, test significance (paired tests over seeds), and check for leakage (temporal splits for dynamic graphs — ch. 6).

2. Expressive power: the Weisfeiler-Lehman test

Which graphs can a message passing GNN tell apart, and which ones will it always confuse? This chapter answers exactly, with the Weisfeiler-Lehman test. A concrete scene: take two non-isomorphic 6-regular graphs. Your 3-layer GCN produces the same embeddings for both (up to permutation), and a link-prediction AUC around 0.5. This is not an implementation bug but the 1-WL bound, which this chapter makes operational before any architectural gadget is added.

The statement of this bound and of the GIN result is already in Graph ML, Proposition 5.1b. Here we prove both, then go beyond 1-WL.

3. Over-squashing and deep GNNs

Even when a GNN could in principle tell two nodes apart, the information may never reach them: messages from far away must squeeze through a few edges. This chapter defines this over-squashing precisely, links it to the geometry and spectrum of the graph, and presents the two families of remedies — changing the graph or changing the propagation.

4. Positional and structural encodings

A GNN only sees the neighborhood of a node, not where the node sits in the whole graph. This chapter shows how to add this information as positional or structural encodings, and how to do it without breaking the invariances a GNN must respect.

5. Graph transformers

Attention lets every node exchange information with every other node in one step, which removes bottlenecks but forgets the graph. This chapter shows how graph transformers put the structure back into attention, what they cost, and when a plain message passing GNN is enough.

import numpy as np, torch, torch.nn as nn
from scipy.sparse.csgraph import shortest_path

def spd_matrix(adj):                                 # adj: (n, n) 0/1 NumPy array
    d = shortest_path(adj, unweighted=True)          # BFS from every node; inf if unreachable
    d[np.isinf(d)] = -1                              # -1 marks "unreachable"
    return torch.as_tensor(d, dtype=torch.long)

class GraphormerLayer(nn.Module):
    def __init__(self, d, h, max_spd=5):
        super().__init__()
        self.max_spd = max_spd
        self.attn = nn.MultiheadAttention(d, h, batch_first=True)
        self.bias = nn.Embedding(max_spd + 2, h)     # b_phi: 0..max_spd, plus one slot for "unreachable"
        self.ffn = nn.Sequential(nn.Linear(d, 2*d), nn.GELU(), nn.Linear(2*d, d))
    def forward(self, x, spd):                       # x: (1, n, d), one graph; spd: from spd_matrix
        idx = spd.clamp(max=self.max_spd)            # long distances share the last slot
        idx = torch.where(spd < 0, torch.full_like(spd, self.max_spd + 1), idx)
        b = self.bias(idx).permute(2, 0, 1)          # (h, n, n) = (batch * heads, n, n) for a batch of 1
        x = self.attn(x, x, x, attn_mask=b)[0] + x   # a float attn_mask is added to the scores
        return self.ffn(x) + x

6. Dynamic and temporal graphs

Many graphs change over time — transactions, edits, interactions — and the order of events carries the signal. This chapter presents the two ways of representing such graphs and the two reference architectures, TGAT and TGN.

7. Robustness and privacy on graphs

Graph models are exposed to attackers who can add or remove a few edges, and graph data often reveals private information. This chapter studies attacks at test and training time, defenses and certification, then privacy and fairness on graphs.

8. LLGA bridges: 3D, algorithmic reasoning, GNN × LLM

This chapter connects the module to the other axes of the master: geometric graphs (3D molecules), GNNs that learn to execute algorithms, and the combination of GNNs with LLMs.

9. Research at DaSciM (Vazirgiannis, Lutzeyer)

The DaSciM laboratory (LIX, École Polytechnique — M. Vazirgiannis, J. Lutzeyer) is the master’s host laboratory: this chapter studies its papers in depth, positioning them relative to the program. General-audience introductions were given in M1 (ch. 11); here we go into the machinery.

Exercises

1. ★ 1-WL by hand. Run 1-WL on C6 and 2×C3 and verify indistinguishability (detail Example 2.4); then on the “house” graph (square + roof) versus the pentagon; conclude on the exact family of indistinguishable pairs.

   Partial solution: the house has degrees 3, 3, 2, 2, 2 — the two eaves, where the roof meets the square, have degree 3, and the roof top has degree 2 (an even number of odd degrees, as the handshake lemma requires). The pentagon is 2-regular, so 1-WL distinguishes them from iteration 1 (initial color = degree).

   Generalization: 1-WL confuses every pair of d-regular graphs with the same number of nodes, since all colors stay equal — for instance all unions of cycles with the same total number of nodes. It also confuses non-regular pairs: two graphs are 1-WL-equivalent exactly when they admit equitable partitions with the same cell sizes and the same numbers of neighbors between cells (fractional isomorphism: Tinhofer, 1986; Ramana, Scheinerman & Ullman, 1994).

2. ★ LapEig. Compute the first 2 nontrivial eigenvectors of the Laplacian of the karate club graph; project the nodes; verify that the visualized separation ≈ the actual partition; rerun 5 times and observe the sign flips; implement the SignNet correction (ch. 4.1) and measure stability (distance between the encodings of two runs).

   Partial solution: \rho\big([\phi(v_i) + \phi(-v_i)]_{i}\big) with MLPs \phi, \rho — each even term is invariant under the flip of its eigenvector; compare with the baseline “sign fixed by the first positive component” (unstable at nodes of near-zero value).

3. ★ RWSE by hand and in code. Recover the computations of Example 4.2 (triangle vs hexagon), then compute the RWSEs (K = 4) of all nodes of the karate club graph. Show that two nodes exchanged by an automorphism always get the same RWSE. Then take the 2-regular graph C3 ∪ C6 (disjoint union), where all nodes are 1-WL-equivalent, and show that RWSE separates the triangle’s nodes from the hexagon’s. Explain why automorphism invariance is both a feature (the encoding does not depend on the numbering) and a limit (no such encoding separates automorphic nodes, even when a task needs it).

   Partial solution: let \Pi be the permutation matrix of an automorphism \sigma. Then \Pi A \Pi^\top = A, \quad \text{so} \quad \Pi P^k \Pi^\top = P^k \quad \text{and} \quad (P^k)_{\sigma(v)\sigma(v)} = (P^k)_{vv} . In C3 ∪ C6, (P^3)_{vv} = \frac14 on the triangle and 0 on the hexagon.

4. ★★ GIN vs GCN. Show that the mean is not injective on multisets (give the counterexamples {a, a, a} vs {a} and {a, a, b, b} vs {a, b}) and that sum+MLP is (discrete features); check experimentally: train GIN and GCN on a 1-WL-indistinguishable pair and measure.

   Partial solution: mean: {a, a, a} → a and {a} → a (collision); discrete sum: encode a by \log 2, b by \log 3 — \{a,a,b,b\} \mapsto 2\log 2 + 2\log 3 = \log 36 and \{a, b\} \mapsto \log 6 — no collision by uniqueness of factorization (th. 2.3); in practice, the mean does better on continuous real features — discuss why (estimation variance).

5. ★★ Minimal pair GNN. Implement a pair GNN with the folklore rule of Example 2.4: a representation h_{uv} per pair, updated from the multiset of (h_{uw}, h_{wv}) over all w. Verify that it separates C6 and 2×C3 (disjoint readout outputs) where GIN fails. Then implement the 2-WL rule (two separate multisets) and check that it fails, as the k-WL box predicts.

   Hint: start with hashed colors (exact 2-FWL and 2-WL) before learning. With dense tensors, the sum over w of h_{uw} \odot h_{wv} is one matrix product per channel — the trick of PPGN.

6. ★★ Over-squashing. Build two “communities” connected by a single bottleneck node; measure the classification performance of a GCN as a function of the distance to the bottleneck; compare GPS (ch. 5), GCN + SDRF and GCN + DIGL. Plot the spectral gap \lambda_2 of L_{\mathrm{sym}} (or the effective resistance between the two sides) before and after rewiring, with the Jacobian sensitivity of Definition 3.1 computed by autograd.

   Partial solution (expected): gradient of accuracy with distance for the GCN; GPS nearly uniform. With two random communities of 30 nodes (edge probability 0.3), three edges added across the bottleneck raise \lambda_2 from about 0.003 to about 0.02. DIGL (PPR with teleport 0.15, top-8 per node) only reaches about 0.005, as Theorem 6 of Topping et al. predicts.

   The effective resistance R_{uv} = (e_u - e_v)^\top L^{+} (e_u - e_v) across the bottleneck falls accordingly (Black et al., 2023); the curve of accuracy against \lambda_2 is the graph to produce.

7. ★★ Graphormer-PE. Implement the attention bias by shortest-path distance (distance matrix by BFS; learned bias table — skeleton in ch. 5.1); train on ogbg-molhiv and compare GCN / GIN / Graphormer-mini; report means ± standard deviations over 5 seeds.

   Partial solution: BFS \mathcal{O}(n(|V| + |E|)) per graph — precompute; clamp distances at a max_spd read from the distance histogram of the training molecules, with a separate slot for unreachable pairs (code of 5.1); expected: a small but systematic gain of the SPD bias over GCN.

8. ★★ Temporal. On a standard TGN dataset (Wikipedia/Reddit): train a TGN (torch_geometric.nn.models.TGNMemory from PyTorch Geometric, or the paper’s code); ablation: remove memory (keep the TGAT embedding); plot the AUC of future link prediction as a function of the horizon \Delta t.

   Partial solution (expected): memory dominates on recent interactions; without memory, the AUC drops by several points at small \Delta t (the information of the last events is no longer compressed).

9. ★★ Attack. Implement a Nettack-style structure attack on a target node (ch. 7.1): train the linearized two-layer surrogate, score every candidate edge flip by the exact surrogate margin after the flip, apply the best one and repeat k times. Measure the prediction flip rate of a normally trained GCN against the budget k; test a defense (RGCN or training on perturbed graphs).

   Partial solution: with \hat A^2 updated incrementally, each candidate is cheap to score. Compare with the gradient ranking of FGA (magnitude of the gradient of the attack loss per candidate edge), cheaper but only a first-order approximation of the same choice. The surrogate suffices (transfer). A defense raises the budget needed to flip a target but makes no target immune; conclude on certification (ch. 7.3).

10. ★★ Edge-DP. Prove that randomized response — each pair of nodes reported truthfully with probability p > \tfrac12, flipped otherwise — is (\varepsilon, 0)-edge-DP with \varepsilon = \ln \frac{p}{1-p} (the convention of Privacy & UQ, Proposition 4.2). Then estimate the number of edges between two groups from the released graph, and compare its error with the Laplace mechanism applied to the true count by a trusted curator.

    Solution: for two graphs neighboring in one edge, all other pairs have the same output law, and the differing pair is reported present with probability p in one graph and 1-p in the other. The likelihood ratio of any output is therefore at most \frac{p}{1-p}, hence the \varepsilon.

    Counting: over the m pairs between the two groups, with c true edges, the released count S has mean \mathbb{E}[S] = c\,p + (m - c)(1 - p) = m(1 - p) + (2p - 1)\,c , so \hat c = \big(S - m(1-p)\big)/(2p - 1) is unbiased, with variance \mathrm{Var}(\hat c) = \frac{m\, p(1-p)}{(2p-1)^2} .

    The Laplace mechanism on the true count (sensitivity 1, scale 1/\varepsilon) has variance 2/\varepsilon^2, independent of m. With p = 0.75, \varepsilon = \ln 3 \approx 1.10 and m = 1000 pairs, the standard deviations are about 27 edges for randomized response and 1.3 for Laplace: local noise is the price of not trusting a curator.

11. ★★ Aligning a GNN with a text encoder on ogbn-arxiv. On ogbn-arxiv (169,343 papers, 40 subject classes; titles and abstracts from the OGB mapping to MAG), train a 2-layer GraphSAGE and embed each title with a frozen sentence encoder. Train two linear heads with the symmetric InfoNCE loss of 8.3 (batches of 512, learned \tau). Report:

    • 1. graph → text recall@10 among 1,000 random test candidates;
    • 2. zero-shot node classification by cosine similarity with the embedded names of the 40 classes, against a GraphSAGE trained with labels;
    • 3. optionally, one soft token per node in a small open LLM, with the projector trained to generate the class name.

    Partial solution (expected): chance level is 1 % for (a) (10 out of 1,000) and 2.5 % for (b) (1 out of 40); the aligned model should be far above both, and (b) below supervised training. Expect most zero-shot confusions between neighboring fields. Map your pipeline onto the table of 8.3: (a)–(b) align the spaces, (c) is the soft-token architecture.

12. ★★★ Research project. Reproduce an experiment from one of (PathNN / GOAT / GPS / TGN / NGG) on OGB or TU; report: protocol, seeds, comparison to the published numbers, failure analysis — the M2’s “paper” exercise; for PathNN: compare the three variants (SP / SP+ / AP) on a molecular dataset (ZINC12K) and explain the observed hierarchy via ch. 9.1.

Projects and assessment

The fiche above records that the SynapseS 2026–2027 sheet of this module is “not published”: the module appears in neither the S3 nor the S4 track of the catalog, so no official assessment is displayed. Everything below is a proposal of these notes, not an official rule. The subjects are sized for an M2 module and reuse the experimental protocol of ch. 1 (seeds, confidence intervals, leakage checks), which every rubric line assumes.

The projects exercise mainly O4 (graph-structured data: expressive power, over-squashing, encodings, temporal graphs), O5 (Graph × LLM: soft tokens, alignment, graph prompting) and O8 (robustness and privacy on graphs), with O7 (hands-on, reproducible research practice). They feed the end-of-year projects Y2.1, Y2.4 and Y2.5.

Solo projects

1. [Solo · ≈ 20 h] A test bench for expressive power. Which models separate which hard pairs of graphs, and does every outcome match a statement of ch. 2 and ch. 4?
   • Work: implement 1-WL, 2-WL and 2-FWL by hashing, GCN, GIN, an ego-net subgraph GNN in the style of ESAN, and GIN with RWSE or LapEig + SignNet inputs.
   • Data: synthetic pairs built with NetworkX — C6 vs 2×C3, house vs pentagon, the 4 \times 4 rook’s graph vs the Shrikhande graph (both strongly regular with parameters (16, 6, 2, 2)) — and the CSL graphs of Murphy et al. (ICML 2019), 41-node 4-regular cycles with skip links, in 10 classes.
   • Success criterion: a models × pairs table in which each entry is predicted, before running, by a result of the page — including the negative ones: 2-FWL and RWSE must both fail on the strongly regular pair.
   • Deliverables: code, a 4–6 page report, a 10-minute talk; chapters 2 and 4, exercises 1, 3 and 5.
2. [Solo · ≈ 25 h] Paper study: Path Neural Networks (Michel, Nikolentzos, Lutzeyer & Vazirgiannis, ICML 2023). Do the three variants rank as their theory says, on synthetic pairs and on real benchmarks?
   • Work: reimplement PathNN-SP, SP+ and AP (path enumeration up to length K, LSTM path encoder of 9.1); check the separation claims on the pairs of solo project 1; then train on ZINC12K and two TU datasets.
   • Data: ZINC12K (Dwivedi et al.’s benchmarking subset) and PROTEINS and IMDB-B from TUDataset, with the 10-fold splits of Errica et al. (2020).
   • Success criterion: published numbers reproduced within one standard deviation, or the gap explained (budget, splits, K); the SP ≤ SP+ ≤ AP ordering tested, with its cost in time and memory.
   • Deliverables: code, report, talk; chapters 2 and 9, extending exercise 12.

Group projects

1. [Group of 3 · ≈ 30 h each] Diagnosing and curing over-squashing. Do rewiring, deep propagation and global attention fix the long-range failures that the bound of Definition 3.1 predicts?
   • Work: measure the Jacobian sensitivity by autograd against distance, the spectral gap \lambda_2, the effective resistance and the edge curvatures; then compare SDRF, DIGL, APPNP, GCNII, GPS and Exphormer under one parameter budget.
   • Data: synthetic barbell graphs and the Tree-NeighborsMatch task of Alon & Yahav (2021), depths 2–6; then Peptides-func from the Long Range Graph Benchmark (Dwivedi et al., NeurIPS 2022), with its budget of about 500k parameters.
   • Split: diagnostics and rewiring; deep MPNNs; graph transformers — with one shared training harness.
   • Success criterion: average precision on Peptides-func with 95 % intervals over 5 seeds; \lambda_2 before and after each rewiring; a decision guide that confirms or corrects 5.4.
   • Deliverables: code, an 8–10 page joint report, a 20-minute talk; chapters 1, 3 and 5.
2. [Group of 3 · ≈ 30 h each] Abuse detection on an event stream, under attack and under privacy. How much do memory, a budgeted attacker and an edge-DP release each cost a temporal detector?
   • Work: TGN and TGAT for dynamic node classification with a chronological 70/15/15 split; the memory ablation of exercise 8; an evasion attack that injects k events from attacker-controlled accounts, and a pruning or RGCN-style defense; a release of the training graph by randomized response (7.4) at several \varepsilon.
   • Data: the Wikipedia and Reddit interaction streams of JODIE (Kumar, Zhang & Leskovec, KDD 2019), with their banned-user labels; for a finance variant, the Elliptic Bitcoin graph (Weber et al., 2019) with snapshot models.
   • Split: temporal models and leakage checks; attack and defense; privacy release and evaluation.
   • Success criterion: AUC against attack budget and against \varepsilon, with intervals over 5 seeds; the leakage checklist of Graph ML 5.6–5.8 passed.
   • Deliverables: code, joint report, talk; chapters 1, 6 and 7, exercises 8–10. It is a first version of Y2.5 and links to Security ch. 9 and Privacy & UQ ch. 4.
3. [Group of 3 · ≈ 30 h each] Graph tokens for an LLM. For a small open LLM, which input answers graph-reasoning questions best as graphs grow: text, pseudo-code or soft tokens?
   • Work: three pipelines on the same questions — text serialization with the encodings of Talk like a Graph (Fatemi, Halcrow & Perozzi, ICLR 2024); pseudo-code prompting (Skianis, Nikolentzos & Vazirgiannis, 2024; 9.4); and a GPS + RWSE encoder whose outputs enter the LLM as soft tokens, after the symmetric InfoNCE alignment of 8.3, with LoRA on the LLM.
   • Data: synthetic questions in the style of GraphQA (edge existence, degree, cycle check, connectivity, shortest path) on random graphs of 5 to 50 nodes, and the NLGraph benchmark (Wang et al., NeurIPS 2023); a model of 0.5B to 1.5B parameters on a free GPU.
   • Split: prompting pipelines; encoder, projector and alignment; evaluation harness and size curves.
   • Success criterion: accuracy against the number of nodes for each task and pipeline, with intervals over 3 seeds and an equal training-data budget for the trained pipelines.
   • Deliverables: code, joint report, talk; chapters 4, 5, 8 and 9. It connects to LLM 4.3 (LoRA) and LLM ch. 7 (retrieval), to Graph ML 10.2, and is the graph-token option of Y2.1.

Written exam (proposal)

Two hours, one handwritten A4 sheet allowed, no calculator needed; four questions, 20 points.

1. Question (5 points). Define over-squashing with the Jacobian of Definition 3.1 and state the bound of Topping et al. Explain how a bottleneck, the Cheeger constant and the spectral gap are related. Then say how rewiring, APPNP/GCNII and graph transformers each act on the problem, and why over-squashing is not over-smoothing.
   • Expected: the sensitivity |\partial h_v^{(r+1)} / \partial x_u| is at most (\alpha\beta)^{r+1}(\hat A^{r+1})_{vu}, small when few walks of u reach v.
   • A bottleneck is a small h_G; by Cheeger, \lambda_2/2 \leq h_G \leq \sqrt{2\lambda_2}, so a small gap — not a large top eigenvalue.
   • Rewiring (SDRF) raises the curvature of negative edges and the gap; APPNP/GCNII change the propagation and anchor to the input; transformers make the channel all-to-all.
   • Over-smoothing is the collapse of representations with depth; over-squashing is the loss of distant inputs in the channel, even at moderate depth.
2. Question (5 points). Two triangles \{0,1,2\} and \{3,4,5\} are joined by the bridge (2,3). (a) Compute the Ollivier-Ricci curvature of the bridge, with uniform measures on the neighbors. (b) Compute the Cheeger constant and deduce an upper bound on \lambda_2 of L_{\mathrm{sym}}. (c) Add the edge (1,4) and recompute the Cheeger constant.
   • Expected: (a) mass \frac13 on each of the neighbors 0, 1, 3 of node 2 moves to the neighbors 2, 4, 5 of node 3. The best plan moves 3 to 4 and 0 to 2 at cost 1, and 1 to 5 at cost 3, so W_1 = \frac53, \qquad \kappa = 1 - \frac53 = -\frac23 .
   • 2. The cut around one triangle: one edge over a volume 2 + 2 + 3 = 7, so h_G = \frac17 (no cut does better), and \lambda_2 \leq 2h_G = \frac27; the true value is about 0.205.
   • 3. The same cut now has 2 edges for a volume of 8: h_G = \frac14, and the bound on \lambda_2 rises to \frac12 (the true value is about 0.423).
3. Question (5 points). (a) Compute the RWSE \big[(P^k)_{vv}\big]_{k=1}^{6} of a node of C3 and of a node of C6. (b) Show that 1-WL gives the same color to every node of the disjoint union C3 ∪ C6. (c) Conclude on the power of a GIN with RWSE inputs, and name two graphs that this GIN still cannot separate.
   • Expected: (a) for C3, (P^k)_{vv} = \frac13\big(1 + 2(-\frac12)^k\big); for C6, the odd terms vanish and the even ones agree with C3: \mathrm{C3}: \Big(0, \tfrac12, \tfrac14, \tfrac38, \tfrac{5}{16}, \tfrac{11}{32}\Big), \qquad \mathrm{C6}: \Big(0, \tfrac12, 0, \tfrac38, 0, \tfrac{11}{32}\Big) .
   • 2. The graph is 2-regular: all nodes start with the same color and see two neighbors of that color at every round.
   • 3. GIN + RWSE separates what 1-WL cannot (here, through k = 3 or k = 5); it still fails on strongly regular graphs with the same parameters, such as the 4 \times 4 rook’s graph and the Shrikhande graph, whose return probabilities are fixed by the parameters.
4. Question (5 points). Randomized response releases each pair of nodes truthfully with probability p > \frac12 and flipped otherwise. (a) Prove that it is \varepsilon-edge-DP with \varepsilon = \ln \frac{p}{1-p}. (b) Give an unbiased estimator of the number c of edges among m given pairs, and its variance. (c) For p = 0.75 and 400 pairs, compare its standard deviation with that of the Laplace mechanism on the true count, at the same privacy level (take ln 3 ≈ 1.10).
   • Expected: (a) neighboring graphs differ on one pair; all other pairs have the same output law, and on that pair the probabilities of each output are p and 1 - p in some order, so every likelihood ratio is at most \frac{p}{1-p}.
   • 2. The released count S has mean m(1-p) + (2p-1)c, so \hat c = \big(S - m(1-p)\big)/(2p-1) is unbiased, with variance m p (1 - p)/(2p - 1)^2.
   • 3. With p = 0.75: variance 400 \times 0.1875 / 0.25 = 300, standard deviation about 17.3; Laplace with \varepsilon = \ln 3 \approx 1.10 has standard deviation \sqrt 2 / \varepsilon \approx 1.29.

Grading rubric (proposal)

References

• K. Xu, W. Hu, J. Leskovec, S. Jegelka, How Powerful are Graph Neural Networks? (GIN), ICLR 2019.
• C. Morris et al., Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks, AAAI 2019.
• C. Morris et al., Weisfeiler and Leman go Machine Learning: The Story so far (survey), JMLR 2023.
• H. Maron, H. Ben-Hamu, H. Serviansky, Y. Lipman, Provably Powerful Graph Networks (PPGN, 3-WL), NeurIPS 2019.
• G. Tinhofer, “Graph isomorphism and theorems of Birkhoff type”, Computing 36, 1986; M. V. Ramana, E. R. Scheinerman, D. Ullman, “Fractional isomorphism of graphs”, Discrete Mathematics 132, 1994 — the exact family of 1-WL-equivalent pairs (exercise 1).
• U. Alon, E. Yahav, On the Bottleneck of Graph Neural Networks (over-squashing), ICLR 2021.
• J. Topping, F. Di Giovanni et al., Understanding over-squashing and bottlenecks on graphs via curvature (Jacobian bound, Balanced Forman curvature, SDRF), ICLR 2022.
• M. Black, Z. Wan, A. Nayyeri, Y. Wang, Understanding Oversquashing in GNNs through the Lens of Effective Resistance, ICML 2023.
• J. Klicpera (now Gasteiger), S. Weißenberger, S. Günnemann, Diffusion Improves Graph Learning (DIGL), NeurIPS 2019.
• J. Klicpera et al., Predict then Propagate: Graph Neural Networks Meet Personalized PageRank (APPNP), ICLR 2019.
• M. Chen et al., Simple and Deep Graph Convolutional Networks (GCNII), ICML 2020.
• L. Rampasek et al., Recipe for a General, Powerful, Scalable Graph Transformer (GPS), NeurIPS 2022.
• C. Ying et al., Do Transformers Really Perform Bad for Graph Representation? (Graphormer), NeurIPS 2021.
• H. Shirzad et al., Exphormer: Sparse Transformers for Graphs, ICML 2023.
• D. Lim, J. Robinson, L. Zhao, T. Smidt, S. Sra, H. Maron, S. Jegelka, Sign and Basis Invariant Networks for Spectral Graph Representation Learning (SignNet, BasisNet), ICLR 2023.
• M. Zaheer et al., Deep Sets, NeurIPS 2017.
• V. P. Dwivedi, A. T. Luu, T. Laurent, Y. Bengio, X. Bresson, Graph Neural Networks with Learnable Structural and Positional Representations (LSPE, RWPE), ICLR 2022.
• R. Rossi et al., Temporal Graph Networks (TGN), ICML 2020 (workshop).
• D. Xu et al., Inductive Representation Learning on Temporal Graphs (TGAT), ICLR 2020.
• V. P. Dwivedi et al., Benchmarking Graph Neural Networks, JMLR 2023 — experimental hygiene.
• M. Bronstein et al., Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, Gauges, 2021.
• D. Zügner, A. Akbarnejad, S. Günnemann, Adversarial Attacks on Neural Networks for Graph Data (Nettack), KDD 2018.
• D. Zügner, S. Günnemann, Adversarial Attacks on Graph Neural Networks via Meta Learning (Metattack, Meta-Self), ICLR 2019.
• C. Finn, P. Abbeel, S. Levine, Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks (MAML), ICML 2017.
• J. Chen et al., Fast Gradient Attack on Network Embedding (FGA), 2018.
• D. Zhu, Z. Zhang, P. Cui, W. Zhu, “Robust Graph Convolutional Networks Against Adversarial Attacks” (RGCN), KDD 2019.
• D. Zügner, S. Günnemann, Certifiable Robustness and Robust Training for Graph Convolutional Networks, KDD 2019 — certification, 7.3.
• V. Garcia Satorras, E. Hoogeboom, M. Welling, E(n) Equivariant Graph Neural Networks (EGNN), ICML 2021.
• E. Hoogeboom, V. Garcia Satorras, C. Vignac, M. Welling, Equivariant Diffusion for Molecule Generation in 3D (EDM), ICML 2022; M. Xu et al., GeoDiff: a Geometric Diffusion Model for Molecular Conformation Generation, ICLR 2022.
• G. Michel, G. Nikolentzos, J. F. Lutzeyer, M. Vazirgiannis, Path Neural Networks: Expressive and Accurate Graph Neural Networks (PathNN-SP, SP+, AP), ICML 2023 — the “home” paper to present.
• F. Errica, M. Podda, D. Bacciu, A. Micheli, A Fair Comparison of Graph Neural Networks for Graph Classification, ICLR 2020 — the TU protocol.
• M. Chatzianastasis, J. F. Lutzeyer, G. Dasoulas, M. Vazirgiannis, Graph Ordering Attention Networks (GOAT), AAAI 2023.
• I. Evdaimon et al., Neural Graph Generator: Feature-Conditioned Graph Generation using Latent Diffusion (NGG), 2024.
• K. Skianis, G. Nikolentzos, M. Vazirgiannis, Graph Reasoning with Large Language Models via Pseudo-code Prompting, 2024.
• P. Veličković et al., The CLRS Algorithmic Reasoning Benchmark, ICML 2022.
• H. Wang et al., Can Language Models Solve Graph Problems in Natural Language? (NLGraph), NeurIPS 2023.
• B. Fatemi, J. Halcrow, B. Perozzi, Talk like a Graph: Encoding Graphs for Large Language Models, ICLR 2024.
• J. Tang et al., GraphGPT: Graph Instruction Tuning for Large Language Models, SIGIR 2024; X. He et al., G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering, NeurIPS 2024; X. He et al., Harnessing Explanations: LLM-to-LM Interpreter for Enhanced Text-Attributed Graph Representation Learning (TAPE), ICLR 2024 — the three architectures of 8.3.
• A. Radford et al., Learning Transferable Visual Models From Natural Language Supervision (CLIP, symmetric InfoNCE), ICML 2021.
• B. Bevilacqua et al., Equivariant Subgraph Aggregation Networks (ESAN), ICLR 2022; F. Frasca, B. Bevilacqua, M. Bronstein, H. Maron, Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries, NeurIPS 2022.
• G. Bouritsas et al., Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting, IEEE TPAMI 2022.
• For the M1 reviews: T. Kipf, M. Welling, GCN ICLR 2017; J. Qiu et al., NetMF WSDM 2018; T. Kipf, M. Welling, Variational Graph Auto-Encoders 2016; W.-L. Chiang et al., Cluster-GCN KDD 2019; H. Zeng et al., GraphSAINT ICLR 2020; J. You et al., GraphRNN ICML 2018; B. Samanta et al., NeVAE AAAI 2019; C. Vignac et al., DiGress ICLR 2023.
• Project data: R. Murphy et al., Relational Pooling for Graph Representations (CSL graphs), ICML 2019; V. P. Dwivedi et al., Long Range Graph Benchmark, NeurIPS 2022 Datasets and Benchmarks; S. Kumar, X. Zhang, J. Leskovec, Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks (JODIE: Wikipedia and Reddit streams), KDD 2019; M. Weber et al., Anti-Money Laundering in Bitcoin (Elliptic), KDD workshop 2019.
• PyTorch Geometric; OGB — labs and benchmarks.