Graph Machine and Deep Learning for Generative AI

Contents

• Introduction and overview
• 0. Refresher: graph theory
• 1. Why graphs?
• 2. Learning tasks on graphs
• 3. Node embeddings
• 4. Spectral filters and spectral clustering
• 5. GNNs and message passing
• 6. Link prediction and graph auto-encoders
• 7. GNNs at scale
• 8. Applications and hands-on
• 9. Graph generation
• 10. Graphs × LLMs: GraphRAG and the hybrid
• 11. Research at DaSciM (Lutzeyer, Vazirgiannis)
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: an engineer who has already trained an MLP / CNN and wants to keep structure (fraud, molecules, KGs) instead of flattening it away.

Empirical first: a fraud model whose impressive test score came only from edges leaking across the train/test split; message passing that oversmooths after 4 layers — then we name GNNs, spectra, GraphRAG.

From graph-theory foundations to GNNs, generation and GraphRAG. Core module of the master: concepts reappear in M2 (Advanced GNN, LLMs).

What you will be able to do

• Model an applied problem as a graph and identify the associated learning task (node, edge, or whole graph).
• Explore a graph and compute its descriptive statistics (BFS distances, clustering, centralities).
• Compare nodes and whole graphs with similarity measures and graph kernels (Weisfeiler-Lehman, random-walk).
• Encode the structure of a graph into node embeddings usable by a classical model.
• Understand spectral filters and spectral clustering via the graph Laplacian.
• Build and train a GNN by message passing.
• Diagnose heterophily and handle temporal graphs without leaking the future.
• Build E(3)-invariant and equivariant models for geometric graphs (molecules, proteins).
• Solve link prediction and use graph auto-encoders.
• Scale a GNN to massive graphs (neighborhood sampling, mini-batches).
• Generate realistic graphs with generative models.
• Combine graphs and LLMs: GraphRAG and hybrid approaches.

Official objectives and syllabus (2026-2027 catalog)

The official 2026–2027 sheet (X3A session of the same name, period X-3A-P2, from 04/01/2027 to 19/03/2027, taught in English) sets the objective of introducing students to graph networks and deep learning — their mathematical foundations, the design of architectures and their practical applications — a field it describes as especially important given the current volume of industrial and academic work.

The description announces machine- and deep-learning methods for graph-structured data, defined as an underlying graph with vector data observed on the nodes, the edges or both: fundamental descriptive statistics of graphs and probabilistic models that generate graphs, graph kernel methods, then a complete overview of deep learning on graphs, notably graph neural networks, closing with applications and a perspective on current challenges and future directions.

Assessment: quizzes and team projects (description; the LLGA section of the sheet displays no modality). Our proposal for the team project, started in session 9, is the Team project box of ch. 8; subjects, an exam and a rubric are in Projects and assessment. Prerequisites: not displayed. Teaching volume: not displayed. The sheet lists a nine-lecture programme (“changes may occur during the semester”), matched below.

Every lecture of the official programme now has a section in these notes. Our extensions, beyond the official syllabus: chapter 10 (GraphRAG and the graph × LLM hybrid, an application of lectures 4 and 9) and chapter 11 (the research work of Lutzeyer and Vazirgiannis, self-study).

Where this course fits in the program

Mandatory module of period 2 of M1 (teaching volume not displayed on the 2026–2027 sheet; 36 h and 4.5 ECTS per the LLGA curriculum wiki), of which Johannes Lutzeyer and Michalis Vazirgiannis are the official heads: it is the heart of the master’s program, the one that structures the “graph” axis around which the advanced M2 modules are organized.

Official prerequisites: not displayed on the 2026–2027 sheet.

• Prerequisites — Machine Learning, and Deep Learning P1 or Deep Learning P2 taken in parallel (read its ch. 0 first): attention is recalled in ch. 5 and the ELBO in ch. 6; as well as the graph algorithmic basics of the Refresher in Computer Science (BFS, Dijkstra); the refresher section goes over the graph theory useful for the course.
• Downstream modules — it is the direct foundation of Advanced Graph Neural Networks (M2) and Graph Generative Models and Applications (M2); its GraphRAG chapter prepares the Large Language Models module (M2), and it also feeds Explainability, Security, Privacy of LLMs (M2).

Course outline

• Refresher: graph theory — vocabulary, spectra and random walks, then graph exploration (BFS, DFS, Dijkstra) and the descriptive statistics of a graph.
• Why graphs? — the motivation: relational, non-Euclidean data, everywhere in industry and science.
• Learning tasks on graphs — classifying a node, an edge, a whole graph: the taxonomy of the field; node similarity measures and graph kernels (Weisfeiler-Lehman, random walks).
• Node embeddings — encoding structure into vectors, with the constraints that guide them.
• Spectral filters and spectral clustering — the Laplacian, its eigenvalues, and the partition that follows.
• GNNs and message passing — the central building block: propagating information along the edges, layer after layer; heterophilous and temporal graphs.
• Link prediction and graph auto-encoders — predicting missing edges and compressing graphs.
• GNNs at scale — training on graphs that fit neither in memory nor in a single batch.
• Applications and hands-on — going from equations to libraries on real use cases; geometric graphs, equivariance and biomedicine; benchmarking and open challenges.
• Graph generation — producing new and realistic graphs: the entry into relational generative AI.
• Graphs × LLMs: GraphRAG and the hybrid — making a knowledge graph and a large language model cooperate.
• Research at DaSciM (Lutzeyer, Vazirgiannis) — a tour of the research work of Lutzeyer and Vazirgiannis (self-study).
• Exercises and References — systematic training and sources to go further.

Session plan

36 h in class = 12 sessions of 3 h. The SynapseS 2026–2027 sheet of this course displays no teaching volume (neither in-person hours nor a lecture/tutorial split), but the LLGA curriculum page of the programme wiki (msct.dix.polytechnique.fr/llga, last modified on 9 September 2026 by the programme director) states that “all subsequent M1 courses are 36h and will credit 4.5 ECTS”.

The sheet does publish a nine-lecture programme, and the plan follows its order with two changes, both made so that no session relies on a notion taught later: the spectral lecture (official 6) comes before the GNN lecture (official 5), because the GCN layer is derived from the spectral filter (Derivation 5.2); and the introduction to graph generative AI (official 4) is taught after GNNs, because the deep generative models of ch. 9 use GNN encoders and denoisers.

Level 1 = foundations (reviews, definitions, first worked examples), 2 = core methods, 3 = advanced material and recent research; the level never goes down from one session to the next.

Read ahead for the team project (week 1 = session 9): sections 10.1–10.2 by project week 2 and 9.4–9.7 by week 3, before they are taught in sessions 11–12.

Self-study, outside the 36 h (about 3 h in total): ch. 11 Research at DaSciM — Graph of Words, Path Neural Networks, GOAT, NGG (≈ 3 h, with Ex. 17).

How to study this module

• Redo the refresher section even if you “know” graphs: BFS and Dijkstra are covered again because the rest of the course relies on them without warning.
• Implement a message passing from scratch on a small hand-drawn graph before using a library: it is ten lines that light up the whole field.
• Follow the spectral thread: Laplacian, spectral clustering then GNNs are the same object in three costumes — this thread also prepares the M2 module on geometric data.
• Visualize node embeddings (dimensionality reduction) to check your intuition on each dataset.
• Read the GraphRAG chapter in parallel with the Introduction to Text Mining and NLP module, taught in the same period: the two shed light on each other.
• Redo the exercises of each section before moving on to the next; they build the foundation reused by all the downstream M2 modules.

0. Refresher: graph theory

Every later chapter manipulates the same few objects — the adjacency matrix, the degrees, the Laplacian, random walks — and uses their properties without stopping to prove them. This refresher states and proves those properties once, so that the walks of ch. 3 and the spectral arguments of ch. 4 rest on solid ground.

Exploring and describing a graph

The second lecture of the official programme covers graph exploration and traditional graph algorithms, and the course description opens with the fundamental descriptive statistics of graphs. Before any learning, these are the first things computed on a new graph: they reveal its scale, its hubs and its local density, and they remain strong hand-crafted features for classical models.

import networkx as nx
G = nx.karate_club_graph()                       # 34 members, 78 friendships
deg = dict(G.degree())
dist = nx.single_source_shortest_path_length(G, 0)       # BFS from member 0, the instructor
bc = nx.betweenness_centrality(G)                         # Brandes, normalized
pr = nx.pagerank(G, alpha=0.85, weight=None)              # NetworkX alpha = 1 - our teleport α
comms = nx.community.louvain_communities(G, weight=None, seed=0)
print(sorted(deg, key=deg.get)[-2:], max(dist.values()), nx.diameter(G))
print(sorted(bc, key=bc.get)[-2:], sorted(pr, key=pr.get)[-2:])
print(len(comms), nx.community.modularity(G, comms, weight=None))
print(nx.transitivity(G), nx.average_clustering(G), nx.degree_assortativity_coefficient(G))

1. Why graphs?

Concrete scene: fraud detection on a transaction graph (nodes = accounts, edges = transfers). A tabular classifier on account features hits 0.71 AUC; the same model enriched with a 2-hop neighborhood reaches 0.89 — until a random split leaks train↔︎test edges and inflates the score. This chapter states why structure matters, before writing a GNN.

Real-world data is relational: the structure carries information that i.i.d. methods ignore.

Social networks (friendships), molecules (bonds), transaction networks (fraud!), enterprise knowledge graphs (customers, products, processes), computer networks, citation clusters, legal ontologies… All are naturally graphs, often heterogeneous (typed nodes/edges: “buys”, “owns”, “works with”) and dynamic (timestamped edges: transactions second by second).

Also typically: few labels (a few dozen annotated nodes out of millions) — the semi-supervised regime of ch. 5 — and distributions biased by sampling (the observed edges are not a uniform sample of the interactions).

2. Learning tasks on graphs

Before choosing a model, one must say what is predicted: a label per node, a score per pair of nodes, or a property of the whole graph. This chapter fixes that taxonomy, then the two constraints that every later model must respect: the symmetry under renumbering of the nodes, and the distinction between predicting on the training graph and on new graphs.

Similarity measures and graph kernels

The third lecture of the official programme is devoted to graph kernels and similarity measures — the way graphs were learned on before neural networks, and still the strongest baselines on many small benchmarks. Two questions are asked: how similar are two nodes of one graph (the basis of link prediction, ch. 6), and how similar are two whole graphs of different sizes, without any correspondence between their nodes (the basis of graph classification with kernel machines).

import collections, numpy as np, networkx as nx
from sklearn.svm import SVC
from sklearn.model_selection import GridSearchCV, StratifiedKFold, cross_val_score

def load_tu(path, name="MUTAG"):                 # the TUDataset text format
    f = lambda s: np.loadtxt(f"{path}/{name}_{s}.txt", delimiter=",", dtype=int)
    gid, lab, y = f("graph_indicator"), f("node_labels"), f("graph_labels")
    Gs = [nx.Graph() for _ in y]
    for v, (g, l) in enumerate(zip(gid, lab)): Gs[g - 1].add_node(v, label=str(l))
    for u, v in f("A") - 1: Gs[gid[u] - 1].add_edge(u, v)
    return Gs, y

def wl_features(Gs, H):                          # Algorithm 2.5, one dictionary for all graphs
    labels = [{v: G.nodes[v]["label"] for v in G} for G in Gs]
    vocab, rows = {}, [collections.Counter() for _ in Gs]
    for h in range(H + 1):
        for i, G in enumerate(Gs):
            for v in G: rows[i][vocab.setdefault((h, labels[i][v]), len(vocab))] += 1
        labels = [{v: lab[v] + "|" + ",".join(sorted(lab[u] for u in G[v])) for v in G}
                  for G, lab in zip(Gs, labels)]  # the string is the injective relabel
    X = np.zeros((len(Gs), len(vocab)))
    for i, r in enumerate(rows): X[i, list(r)] = list(r.values())
    return X

Gs, y = load_tu("MUTAG")
for H in (0, 3):
    X = wl_features(Gs, H)
    K = X @ X.T
    K /= np.sqrt(np.outer(np.diag(K), np.diag(K)))     # normalized kernel
    svm = GridSearchCV(SVC(kernel="precomputed"), {"C": [0.01, 0.1, 1, 10, 100]}, cv=5)
    outer = StratifiedKFold(10, shuffle=True, random_state=0)
    print(H, cross_val_score(svm, K, y, cv=outer).mean())   # nested CV: C chosen inside

3. Node embeddings

A classical model (logistic regression, k-means) needs one vector per node, but a graph only gives relations. Node embeddings solve this by learning a vector z_v \in \mathbb{R}^d for each node from the structure alone, so that nodes close in the graph get close vectors.

import numpy as np, networkx as nx
from gensim.models import Word2Vec
from sklearn.cluster import KMeans
from sklearn.metrics import normalized_mutual_info_score

G = nx.karate_club_graph()
y = np.array([0 if G.nodes[v]["club"] == "Mr. Hi" else 1 for v in G])

def biased_walk(G, v, p, q, length):
    walk, prev = [v], None
    for _ in range(length):
        cand = list(G.neighbors(walk[-1]))
        probs = []
        for x in cand:
            d = 0 if x == prev else nx.shortest_path_length(G, prev, x) if prev is not None else 1
            probs.append({0: 1/p, 1: 1.0, 2: 1/q}[d])
        probs = np.array(probs) / sum(probs)
        prev, nxt = walk[-1], np.random.choice(cand, p=probs)
        walk.append(nxt)
    return walk

walks = [ [str(u) for u in biased_walk(G, v, p=1, q=0.25, length=30)]
          for _ in range(80) for v in G.nodes() ]
model = Word2Vec(walks, vector_size=64, window=5, min_count=0, sg=1, epochs=10)
Z = np.array([model.wv[str(v)] for v in sorted(G.nodes())])
km = KMeans(n_clusters=2, n_init=10, random_state=0).fit(Z)
print("NMI :", normalized_mutual_info_score(y, km.labels_))   # ~0.5-0.8 depending on p, q, seed

4. Spectral filters and spectral clustering

To filter a signal carried by the nodes (smooth it, detect its sharp variations) or to cut a graph into communities, one needs a notion of frequency on a graph. The eigenvectors of the Laplacian (Definition 0.4) provide it; this chapter builds the graph Fourier transform, uses it for spectral clustering, then turns it into the first graph convolutions.

5. GNNs and message passing

Spectral filters are tied to the eigenvectors of one fixed graph. We want instead a layer that applies to any graph, costs time linear in the number of edges and trains like an ordinary network layer; message passing is that layer — each node updates its vector from the vectors of its neighbors.

input : G, features X, depth K, sample sizes s_1..s_K
for v in V : h_v^(0) = x_v
for l = 1 .. K :
    for v in V :
        S_v = uniform sample of N(v) of size s_l               # K neighbors in the paper
        a_v^(l) = AGG({ h_u^(l-1) : u in S_v })                 # mean / LSTM / pool
        h_v^(l) = sigma( W_l . [ h_v^(l-1) || a_v^(l) ] )       # concatenation!
        h_v^(l) = h_v^(l) / ||h_v^(l)||                          # L2 normalization
output : z_v = h_v^(K)

Heterophily: when neighbors differ

The seventh lecture of the official programme treats heterophily and temporal graphs. GCN-style averaging implicitly assumes homophily — linked nodes tend to share their label. Fraud rings (fraudsters link to honest accounts they exploit), dating networks, protein interactions or the “is a student of” relation violate it.

Temporal graphs

import torch
from torch_geometric.nn import GCNConv, GATConv
from torch_geometric.datasets import Planetoid

dataset = Planetoid(root="/tmp/Cora", name="Cora")   # 2708 nodes, 5278 undirected edges, 7 classes
data = dataset[0]

class GCN(torch.nn.Module):
    def __init__(self, d_in, d_hid, n_classes):
        super().__init__()
        self.c1, self.c2 = GCNConv(d_in, d_hid), GCNConv(d_hid, n_classes)
    def forward(self, x, edge_index):
        return self.c2(torch.relu(self.c1(x, edge_index)), edge_index)

model = GCN(dataset.num_features, 64, dataset.num_classes)
opt = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)
for epoch in range(200):
    opt.zero_grad()
    out = model(data.x, data.edge_index)
    loss = torch.nn.functional.cross_entropy(out[data.train_mask], data.y[data.train_mask])
    loss.backward(); opt.step()
acc = (model(data.x, data.edge_index).argmax(1)[data.test_mask]
       == data.y[data.test_mask]).float().mean()
print(f"Cora test accuracy : {acc:.3f}")   # ~0.81 with this simple setting

6. Link prediction and graph auto-encoders

Many graphs are incomplete: a recommender wants the purchases that have not happened yet, a knowledge graph misses true facts. This chapter turns the node representations of ch. 3 and 5 into scores for pairs of nodes, and trains them to recover the missing edges.

7. GNNs at scale

The models of ch. 5 were trained on Cora, which fits in memory; industrial graphs have millions of nodes and billions of edges. This chapter explains why full-batch training breaks at that scale and presents the three standard ways of training on pieces of the graph.

N_L = B                                             # the target nodes of the batch
for l = L .. 1 :                                    # from the output layer down to the input
    N_{l-1} = N_l + (s_l sampled neighbors of each node of N_l)
compute h^(1), ..., h^(L) layer by layer, layer l only on the nodes of N_l
update the parameters with the loss on the outputs of B only

8. Applications and hands-on

The previous chapters gave the models; this chapter maps them onto the use cases met in industry, then gives the protocol of a first honest experiment — the step where most graph projects go wrong.

• Recommendation: user-item graph, link prediction (ch. 6); PinSage (3B nodes, 18B edges) = GraphSAGE at industrial scale; cold-start = the inductive case par excellence;
• Fraud detection: node classification on the transaction graph; typical signals: counter proximities, money-laundering cycles (the motifs matter!), card hubs — GNNs capture the multihop neighborhood that an iid model ignores; temporal version in M2 (ch. 6);
• Chemistry / biotech: molecule = graph (atoms = nodes, bonds = edges); graph classification to predict properties (toxicity, solubility, HIV activity); benchmarks: ZINC, QM9, ogbg-mol*; 3D geometry and equivariance: Definition 8.2 below, developed in M2 (ch. 8);
• Knowledge graph completion: link prediction on heterogeneous KGs (TransE, R-GCN — ch. 6); the basis of “enterprise” RAG (ch. 10);
• Logistics — demand forecasting on a zone graph: the zones of a city are the nodes, linked when adjacent or weighted by travel time, and the node signal is the number of pick-ups per zone and per 15 minutes (public NYC taxi trip records, for example). A spatio-temporal GNN forecasts the next hour: a graph convolution in space (ChebNet, ch. 4) with a recurrent or temporal convolution in time (DCRNN, Li et al., 2018; STGCN, Yu et al., 2018). The split is chronological (causality rule, Definition 5.6), and the forecast feeds the dispatcher of the RL module (capstone Y1.2);
• Scale up: neighborhood minibatching, clustering, sampling (ch. 7), multi-node GPUs (M2, ch. 1); open benchmarks: OGB.

Geometric graphs and applications in biomedicine

The eighth lecture of the official programme concerns geometric graphs — graphs whose nodes live in physical space — and their applications in biomedicine, where molecules and proteins are the central objects. The new ingredient is a second symmetry, on top of the permutations of Definition 2.1: moving or rotating a molecule does not change its chemistry.

import torch, torch.nn as nn

class EGNNLayer(nn.Module):                      # Proposition 8.3, dense version
    def __init__(self, d, hidden=64):
        super().__init__()
        mlp = lambda i, o: nn.Sequential(nn.Linear(i, hidden), nn.SiLU(), nn.Linear(hidden, o))
        self.phi_e, self.phi_x, self.phi_h = mlp(2 * d + 1, hidden), mlp(hidden, 1), mlp(d + hidden, d)

    def forward(self, h, x, A):                  # h: n x d, x: n x 3, A: n x n adjacency
        n = h.shape[0]
        diff = x[:, None, :] - x[None, :, :]      # diff[v, u] = x_v - x_u
        pair = torch.cat([h[:, None].expand(n, n, -1), h[None, :].expand(n, n, -1),
                          (diff ** 2).sum(-1, keepdim=True)], -1)
        m = self.phi_e(pair)                      # m[v, u] = phi_e(h_v, h_u, |x_v - x_u|^2)
        off = 1 - torch.eye(n, dtype=x.dtype)     # all u != v
        x_new = x + (diff * self.phi_x(m) * off[..., None]).sum(1) / (n - 1)
        h_new = self.phi_h(torch.cat([h, (A[..., None] * m).sum(1)], -1))
        return h_new, x_new

def test_egnn(n=8, d=5):
    torch.manual_seed(0)
    layer, dt = EGNNLayer(d).double(), torch.double
    h, x = torch.randn(n, d, dtype=dt), torch.randn(n, 3, dtype=dt)
    A = torch.triu((torch.rand(n, n) < 0.4).to(dt), 1); A = A + A.T
    Q, _ = torch.linalg.qr(torch.randn(3, 3, dtype=dt))           # random orthogonal matrix
    t, Pi = torch.randn(3, dtype=dt), torch.eye(n, dtype=dt)[torch.randperm(n)]
    h1, x1 = layer(h, x, A)
    h2, x2 = layer(Pi @ h, (Pi @ x) @ Q.T + t, Pi @ A @ Pi.T)      # move and renumber
    assert torch.allclose(h2, Pi @ h1, atol=1e-10)                 # features: invariant
    assert torch.allclose(x2, (Pi @ x1) @ Q.T + t, atol=1e-10)     # coordinates: equivariant

test_egnn()

9. Graph generation

The previous chapters analyzed given graphs; this chapter learns to produce new ones — molecules with a target property, synthetic networks for testing — which raises difficulties that images and text do not have.

10. Graphs × LLMs: GraphRAG and the hybrid

A large language model answers fluently but does not know the private documents of a company, and it loses track of relations spread across many of them. GraphRAG addresses both problems: it builds a knowledge graph from the documents with the LLM itself, then uses the graph — its entities, relations and communities — to retrieve what the model needs in order to answer.

• Agents on graphs: the plan of a multi-agent system is a graph (orchestration DAG); “graph engineering” (2026) = programming the topology of the agents — the master loop: the graph in the model (attention), the graph for the model (RAG), the graph between the models (agents).

import json, re, time, difflib, unicodedata, collections
import numpy as np, networkx as nx

FIELDS = ("subject", "relation", "object", "evidence")
SCHEMA = {"type": "array", "items": {"type": "object", "required": list(FIELDS),
          "properties": {f: {"type": "string"} for f in FIELDS}}}
PROMPT = ("Extract every factual triple stated in the passage. Reply with JSON only, valid "
          "against this schema: {schema}. Copy 'evidence' verbatim from the passage.\n"
          "Passage [{cid}]: {text}")

class Metered:                                   # tokens and latency of every LLM call
    def __init__(self, llm): self.llm, self.tokens, self.seconds = llm, 0, 0.0
    def __call__(self, prompt):
        t0 = time.perf_counter(); out = self.llm(prompt)
        self.seconds += time.perf_counter() - t0
        self.tokens += (len(prompt) + len(out)) // 4      # about 4 characters per token
        return out

def extract(llm, cid, text):                     # 1. triples, anchored on their chunk
    out = json.loads(llm(PROMPT.format(schema=json.dumps(SCHEMA), cid=cid, text=text)))
    return [(t["subject"], t["relation"], t["object"], cid)
            for t in out if t["evidence"] in text]

def norm(s):
    s = unicodedata.normalize("NFKD", s).encode("ascii", "ignore").decode()
    return " ".join(re.sub(r"[^\w\s]", " ", s.lower()).split())

def resolve(names, embed, tau_str=0.9, tau_emb=0.9):     # 2. entity resolution
    canon, alias = [], {}
    for n in sorted(set(names), key=lambda n: (-len(n), n)):
        alias[n] = next((c for c in canon
                         if difflib.SequenceMatcher(None, norm(n), norm(c)).ratio() >= tau_str
                         or embed(n) @ embed(c) >= tau_emb), n)
        if alias[n] == n: canon.append(n)
    return alias

def build_graph(triples, alias):                 # one edge per entity pair, with its chunks
    G = nx.Graph()
    for s, r, o, cid in triples:
        u, v = alias[s], alias[o]
        if not G.has_edge(u, v): G.add_edge(u, v, relation=r, chunks=set())
        G[u][v]["chunks"].add(cid)
    return G

def communities(G, seed=0):                      # 3. Leiden (NetworkX 3.7, or leidenalg)
    return nx.community.leiden_communities(G, metric="modularity", seed=seed)

def local_search(G, q, embed, n_seeds=1, k=2, top=2):    # 4. seeds, k hops, chunk ranking
    ents = list(G)
    sims = np.array([embed(e) @ embed(q) for e in ents])
    hop = {}
    for s in [ents[i] for i in np.argsort(-sims)[:n_seeds]]:
        for v, d in nx.single_source_shortest_path_length(G, s, cutoff=k).items():
            hop[v] = min(d, hop.get(v, k))
    score = collections.Counter()
    for u, v, a in G.subgraph(hop).edges(data=True):
        for c in a["chunks"]: score[c] += 1 / (1 + min(hop[u], hop[v]))
    return [c for c, _ in score.most_common(top)]

def global_search(llm, q, summaries, top=3):     # 5. map-reduce over community summaries
    maps = [json.loads(llm(f"Answer '{q}' from this community summary only. Reply as "
                           f'JSON {{"answer": str, "score": 0-100}}.\n{s}')) for s in summaries]
    best = sorted(maps, key=lambda m: -m["score"])[:top]
    return llm(f"Merge these partial answers to '{q}' into one answer: {json.dumps(best)}")

def em_f1(pred, gold):                           # 6. evaluation, SQuAD-style normalization
    p, g = ([w for w in norm(s).split() if w not in ("a", "an", "the")] for s in (pred, gold))
    common = sum((collections.Counter(p) & collections.Counter(g)).values())
    return float(p == g), (2 * common / (len(p) + len(g)) if common else 0.0)

def support_recall(retrieved, gold):
    return len(set(retrieved) & set(gold)) / len(gold)

def citation_faithfulness(cited, retrieved, answer, chunks):
    return np.mean([c in retrieved and norm(answer) in norm(chunks[c]) for c in cited])

import zlib

def embed(s, dim=512):                           # toy encoder: hashed character trigrams
    s, v = f"  {norm(s)} ", np.zeros(dim)
    for i in range(len(s) - 2): v[zlib.crc32(s[i:i + 3].encode()) % dim] += 1
    return v / np.linalg.norm(v)

P = {"Atlas":  ("Ana Ben Chen Dina Eli Fay", "TaxiZones FleetLogs", "Rhone Freight"),
     "Boreal": ("Gus Hana Ivo Jade Kai Lea", "ClaimsDB PolicyText", "Helios Bank"),
     "Cirrus": ("Mia Noor Omar Pia Quin Rui", "ScanSet TrialNotes", "Medina Clinic")}
T = [("Fay", "works on", "Boreal", "memo"), ("Lea", "works on", "Cirrus", "memo"),
     ("Cirrus", "uses", "Policy Text", "memo"), ("Atlas", "uses", "Taxi Zones", "memo"),
     ("Rhône Freight", "pays", "Atlas", "memo")]
for p, (team, data, client) in P.items():
    m = team.split()
    T += [(x, "works on", p, p + "/team") for x in m] + [(m[1], "reports to", m[0], p + "/team")]
    T += [(p, "uses", d, p + "/delivery") for d in data.split()]
    T += [(p, "delivers to", client, p + "/delivery")]
chunks = collections.defaultdict(str)
for s, r, o, c in T: chunks[c] += f"{s} {r} {o}. "

G = build_graph(T, resolve([x for s, _, o, _ in T for x in (s, o)], embed))
C = communities(G)
print(G.number_of_nodes(), G.number_of_edges(), len(C), nx.community.modularity(G, C))
q, gold = "Which client receives the work of Gus?", ["Boreal/team", "Boreal/delivery"]
top = local_search(G, q, embed)
print(top, support_recall(top, gold), em_f1("Helios", "Helios Bank"))

11. Research at DaSciM (Lutzeyer, Vazirgiannis)

The LLGA master is taught by the DaSciM laboratory (Data Science and Mining, LIX, École Polytechnique): M. Vazirgiannis, J. Lutzeyer and their PhD students. This chapter presents four research directions of the laboratory in direct connection with the program; the papers are to be read and presented as a project — this is the module’s “paper” exercise (and the daily bread of M2, ch. 9).

Exercises

1. ★ Triangles by the trace. From \mathrm{tr}(A^3), count the triangles of the “two K_4s sharing an edge” graph. Generalize: what does \mathrm{tr}(A^4) count?

   Solution: each K_4 contains \binom{4}{3} = 4 triangles, and no triangle belongs to both (it would need a third common vertex); total 8, hence \mathrm{tr}(A^3) = 48.

   \mathrm{tr}(A^4) counts the closed walks of length 4 (squares, back-and-forths…) — not only the squares; one must subtract the degree contributions (formula with \sum_v d_v^2 for the back-and-forths).

2. ★ node2vec. Simulate walks with (p, q) = (1, 1), (0.25, 4), (4, 0.25) on the karate club graph (code 3.4); project the embeddings in 2D (t-SNE) and relate p, q to the BFS/DFS strategies.

   Expected solution: (p,q) = (0.25, 4) — strong return, weak exploration → BFS, embeddings grouped by role (the two hubs “Mr. Hi” and “Officer” move closer); (4, 0.25) → DFS, clustering by factions (homophily), higher NMI for the split task; (1,1) intermediate.

3. ★ NetMF by hand. For the triangle K_3, compute M = \log\big(\frac{\mathrm{vol}}{kT}(\sum_{r=1}^T P^r) D^{-1}\big) with window T = 2 and k = 1 negative per pair, and interpret the signs.

   Solution: the adjacency is J - I (J = all-ones matrix) and every degree is 2, so P = \frac12 (J - I) and, using J^2 = 3J, P^2 = \frac14 (J + I).

   Hence \sum_{r \leq 2} P^r = \frac14 (3J - I), with \frac12 on the diagonal and \frac34 off it. With \mathrm{vol} = 6 and D^{-1} = \frac12 I: M = \log\big(\frac{6}{2} \cdot \frac14 (3J - I) \cdot \frac12\big) = \log\big(\frac38 (3J - I)\big) \quad \text{entrywise}, i.e. \log\frac98 > 0 off the diagonal and \log\frac34 < 0 on it.

   Reading: two distinct vertices co-occur in the walks a little more than the degree baseline predicts, a vertex with itself less; all the off-diagonal entries are equal because the triangle has no structure to reveal — DeepWalk on a structureless graph can only reflect the degrees; conclusion: the target matrix is the signal.

4. ★ GCN by hand. Implement a GCN layer without PyG (compute \tilde A, \tilde D), check the equality of the outputs with GCNConv at fixed weights, then measure the over-smoothing: mean cosine similarity of the embeddings as a function of the number of layers (1 to 10). Solution (PyG-guided):

   import torch, torch_geometric
   from torch_geometric.datasets import Planetoid
   data = Planetoid(root="/tmp/Cora", name="Cora")[0]
   A = torch.zeros(2708, 2708)
   A[data.edge_index[0], data.edge_index[1]] = 1.0
   A_tilde = A + torch.eye(2708)
   D_inv_sqrt = A_tilde.sum(1).pow(-0.5).diag()
   A_hat = D_inv_sqrt @ A_tilde @ D_inv_sqrt        # renormalized propagator
   H = data.x
   for L in range(1, 11):
       H = A_hat @ H                                 # pure propagation (thm. 5.3)
       Hn = torch.nn.functional.normalize(H, dim=1)  # unit rows
       cos = Hn @ Hn.T                               # 2708 x 2708, not 2708 x 2708 x 1433
       print(L, ((cos.sum() - 2708) / (2708 * 2707)).item())
   # 0.15 at L = 1, 0.52 at L = 10, 0.82 at L = 64; the limit is 0.89, not 1

   Reading: the mean cosine rises steadily, which is over-smoothing, but it does not tend to 1. Theorem 5.3 assumes a connected regular graph, and Cora has 78 connected components (the largest has 2,485 nodes). On each component C, \hat A^L tends to the projection onto \tilde D^{1/2} \mathbf{1}_C: rows become parallel inside a component, not across components.

5. ★ Spectral clustering. Apply algorithm 4.4 (k = 2) to the “two K_5s + bridge” graph, validating the Fiedler vector of example 4.3; compare Ncut and RatioCut for the found partition.

   Solution: signs of the vector (1,1,1,1,0.70,-0.70,-1,-1,-1,-1) → exact partition.

   \mathrm{cut} = 1, RatioCut = \frac{1}{5} + \frac{1}{5} = 0.4; Ncut = \frac{1}{21} + \frac{1}{21} \approx 0.095 (each side has volume 4 \times 4 + 5 = 21).

   A cut isolating a single node removes at least 4 edges, hence a RatioCut of at least \frac{4}{1} + \frac{4}{9} \approx 4.4 — the weighting by size does the job.

6. ★ Link prediction. On Cora: mask 10% of the edges, encode with a GAE (ch. 6), score the pairs by \sigma(z_u^\top z_v); evaluate the AUC against sampled negatives; compare GAE vs VGAE vs DeepWalk embeddings (ch. 3). Solution (PyG-guided):

   import torch.nn as nn
   from torch_geometric.nn import GCNConv
   from torch_geometric.utils import negative_sampling
   
   class GAE(nn.Module):
       def __init__(self, d_in, d_hid):
           super().__init__()
           self.e1, self.e2 = GCNConv(d_in, d_hid), GCNConv(d_hid, d_hid)
       def forward(self, x, ei):
           return self.e2(torch.relu(self.e1(x, ei)), ei)
   
   model, opt = GAE(1433, 64), None
   opt = torch.optim.Adam(model.parameters(), lr=0.01)
   # split: train_pos = 90% of the edges; test_pos = 10% + as many negatives
   for ep in range(200):
       Z = model(data.x, train_pos_ei)
       neg = negative_sampling(train_pos_ei, num_nodes=2708)
       ei_all = torch.cat([train_pos_ei, neg], dim=1)
       lbl = torch.cat([torch.ones(train_pos_ei.size(1)),
                        torch.zeros(neg.size(1))])
       score = (Z[ei_all[0]] * Z[ei_all[1]]).sum(-1)
       loss = nn.functional.binary_cross_entropy_with_logits(score, lbl)
       opt.zero_grad(); loss.backward(); opt.step()
   # AUC: rank the scores of the test edges and of fresh negatives

   Expected: AUC \approx 0.90–0.92.

7. ★★ Laplacian. Show x^\top L x = \sum_{(u,v) \in E}(x_u - x_v)^2, then that \lambda_2 > 0 \iff connected. Compute the spectrum of the path and of the cycle.

   Solution (sketch): expand x^\top D x - x^\top A x = \sum_v d_v x_v^2 - 2\sum_{(u,v)} x_u x_v and group by edges.

   \lambda_2 = 0 is equivalent to the existence of a non-zero x \perp \mathbf{1} constant per component (the multiplicity computation of Definition 0.4), hence \lambda_2 > 0 \iff a single component.

   Path: 2(1 - \cos\frac{k\pi}{n}); cycle: 2(1 - \cos\frac{2k\pi}{n}).

8. ★★ Permutation equivariance. Check that the GCN layer satisfies f(\Pi X, \Pi A \Pi^\top) = \Pi f(X, A) and interpret; show that a classic dense layer (MLP over concatenated features) does not satisfy it.

   Solution (sketch): \tilde D_{\Pi A \Pi^\top} = \Pi \tilde D \Pi^\top (the degrees follow the permutation), hence \tilde D_{\Pi A \Pi^\top}^{-1/2} (\Pi \tilde A \Pi^\top) \tilde D_{\Pi A \Pi^\top}^{-1/2}\, \Pi X = \Pi\, \tilde D^{-1/2} \tilde A \tilde D^{-1/2} X; a dense MLP over the concatenation [x_1 \| \dots \| x_n] applies different weights to each position — permuting the nodes changes the output other than through \Pi.

9. ★★ GAT. Show that the memory complexity of the T-head attention is \mathcal{O}(T |E| F'), and that with self-loops GCN is obtained as a special case of uniform attention. How does GAT handle the irregular graphs that GCN normalizes poorly?

10. ★★ Scale. Derive the bound 1 + s_L(1 + s_{L-1}(\dots)) of the NeighborSampler; for ogbn-arxiv (mean degrees \approx 7, max 200+), which fanout (s_1, s_2) do you recommend and why? Evaluate the accuracy gap vs full-batch on Cora while increasing the variance (fanouts (2,2), (5,5), (10,10)).

11. ★★ Random generation. (a) After 9.2: implement ER and SBM (SBM: 4 blocks, B_{aa} = 0.8, B_{ab} = 0.05) and generate 500 graphs of each. Which minimal k of the spectral k-means (ch. 4) recovers the blocks? (b) After 9.6: check with degree-MMD that an ER model of the same density does not reproduce the degree distribution of the SBM.

12. ★★ WL kernel and its blind spot. (a) Run two iterations of Algorithm 2.5 on the kite of Example 0.10 and on the 5-cycle, starting from constant labels, and compute the normalized kernel between them. (b) Show that two disjoint triangles and the 6-cycle receive identical WL feature vectors at every iteration, and name a graph statistic of Definition 0.9 that tells them apart. Solution (b): both graphs are 2-regular, so every node keeps the same label at every iteration; the number of triangles (\mathrm{tr}(A^3)/6 = 2 versus 0) or the transitivity (1 versus 0) separates them.

13. ★★ Heterophily and time. (a) For the bipartite example of Proposition 5.5 with d = 4, compute the output after one and two GCN propagations, then with ego/neighbor separation. (b) For the event stream of Example 5.8 extended by (b, d, 8), list the temporal neighbors of d admissible for a query at t = 9, with their elapsed times.

    Solution: (a) -0.6\,x_v, then 0.36\,x_v; with separation the pair (x_v, -x_v) is kept intact.

    (b) c (\Delta t = 2) and b (\Delta t = 1).

14. ★★ Equivariance check. Implement one EGNN layer (Proposition 8.3) in NumPy with random small MLPs, apply it to a random 3D point cloud, then to the same cloud rotated by a random orthogonal matrix and translated; verify numerically that the features are unchanged and the coordinates transformed, and that a layer fed raw coordinates as features fails the test.

    Solution: port the PyTorch layer that follows Proposition 8.3, with fixed random two-layer maps as MLPs. In double precision the features agree to rounding error (below 10^{-10}) and the coordinates satisfy x' \mapsto Qx' + t: the distances, hence the messages, do not move, and Q factors out of the update. With [h_v \| x_v] as input features, the messages see absolute positions, and the test fails with errors of order 0.1 to 1.

15. ★★ GraphRAG on the toy graph. Run the code of 10.4 on its toy corpus. (a) Use k = 1 hop instead of 2: which chunks come back, and what is the support recall? (b) Use two seeds instead of one. (c) Lower the string threshold of resolve to 0.85: which names merge, what false fact does the graph now state, and how many Leiden communities remain? (d) Compute EM and F1 of the answers “Helios” and “the Helios bank” against the gold “Helios Bank”.

    Solution: (a) Only Boreal/team, a recall of 0.5: Helios Bank is two hops from Gus, so the delivery chunk is never a candidate. The number of hops must match the question.

    (b) The second seed is Cirrus, a spurious match of the toy encoder. Its chunks crowd out Boreal/delivery: the top two are Cirrus/team and Boreal/team, recall 0.5. Seeds need a similarity threshold, not only a count.

    (c) “Ana” and “Hana” have ratio 2 \cdot 3 / 7 \approx 0.857 \geq 0.85, so Ana is merged into Hana. The graph now states that Hana works on Atlas and that Ben reports to Hana. With 29 entities, Leiden (seed 0) returns 4 communities, one of them {Ben, Gus, Hana}, and the modularity drops from 0.57 to 0.51. Short names need a stricter rule, such as an exact match or the embedding of the name in its context.

    (d) “Helios”: EM 0 and F1 = 2 \cdot 1 / (1 + 2) \approx 0.67. “The Helios bank”: EM 1 and F1 1, since case, punctuation and articles are normalized away.

16. ★★★ Neural generation. Train a small autoregressive model (sequential addition of nodes/edges, MLP + softmax — the GraphRNN scheme of ch. 9.4) on ZINC molecules; measure validity (chemical valence) and uniqueness of the generated graphs; compare with an Erdős-Rényi sampler of the same density. Hints: encode the binary S^i (max 4 atom types), teacher forcing, 200 epochs are enough for the lab; reading: low validity (< 50\%) without a valence constraint — explain why the NeVAE architecture (ch. 9.3) changes everything.

    Solution sketch:

    • Order the atoms by BFS. At step i the model outputs a softmax over the atom types and one Bernoulli per earlier atom in a window of the last M atoms, with M the largest BFS bandwidth of the training set.
    • A sample is valid if it is connected and no atom exceeds its valence (C 4, N 3, O 2, F 1). Without constraints, violations accumulate over about 23 atoms, hence the low validity.
    • Masking every bond that would exceed the remaining valence, and forcing each new atom to bond to an earlier one, gives validity close to 100%. That is the NeVAE idea of 9.3: the constraint is in the decoder, not in post-processing.
    • ER at the same density (n \approx 23 atoms, about 25 bonds, p \approx 0.1) is disconnected in more than 90% of samples, so its validity stays below 10% before any valence check.

17. ★★★ Paper. Choose a paper from ch. 11 (Graph of Words, PathNN, GOAT or NGG), read it, and present it in 10 minutes: problem, contribution, results, limits, position in the course. Grid: clarity of the key figure, reproduction of a number with commentary, one open question proposed.

Projects and assessment

The official assessment, from the course description, is “quizzes and team projects”; the LLGA section of the 2026–2027 sheet displays no modality, resit rule or weighting. Everything below is a proposal. The solo and group subjects can serve as the team project, the graph work package of a Year 1 capstone (Team project box, ch. 8), and the written exam is a model for the quizzes or a final test. The projects exercise O4 (graph-structured data) and O5 (graph × LLM) at their core, with O2 (graph generation), O3 (retrieval and LLM evaluation) and O7 (protocols, reproducibility, industry cases).

Solo projects

1. [Solo · ≈ 20 h] Kernels versus GNNs under a fair protocol. Do graph kernels still match GNNs on small molecular benchmarks once model selection is honest? A paper study of Errica, Podda, Bacciu & Micheli, “A Fair Comparison of Graph Neural Networks for Graph Classification” (ICLR 2020).
   • Implement: GIN and GraphSAGE in PyG and the paper’s structure-agnostic baseline (an MLP on summed node features), under the paper’s protocol (10 outer folds, model selection on an inner holdout). Then add what the paper does not test: the WL-subtree and shortest-path kernels with an SVM (lab sheet of session 3), under the same protocol.
   • Data: NCI1, PROTEINS and D&D from TUDataset, three chemical datasets of the paper; MUTAG, which the paper does not use, for a first run.
   • Probe: the WL blind spot on regular graphs (Example 2.6). Do triangle counts (Theorem 0.3) added as features separate non-isomorphic regular pairs, such as the CSL graphs of Murphy et al. (2019)?
   • Deliverables: code, a 4–6 page report, a 10-minute talk. Chapters: ch. 0, 2, 5, 8.
   • Success: GIN, GraphSAGE and the baseline within the paper’s standard deviations on at least two of the three datasets, the kernels in the same table, and a measured answer on the blind spot.
2. [Solo · ≈ 20 h] Heterophily as a spectral problem. Does a learned polynomial filter turn high-pass on heterophilous graphs, as Proposition 5.5 suggests? A paper study of Chien, Peng, Li & Milenkovic, “Adaptive Universal Generalized PageRank Graph Neural Network” (GPR-GNN, ICLR 2021).
   • Implement: edge homophily (Definition 5.4); GCN, an ego/neighbor-separation model in the style of H2GCN, and GPR-GNN, which learns the coefficients \gamma_k of \sum_k \gamma_k \hat A^k H.
   • Data: Cora, Texas and Chameleon (benchmarks of Pei et al., 2020), with ten random 60/20/20 splits, the paper’s dense setting (the paper itself averages 100 runs).
   • Analysis: plot the learned frequency response on the spectrum [0, 2) of \tilde L_{\mathrm{sym}}, using \hat A = I - \tilde L_{\mathrm{sym}} (Proposition 4.6): g(\lambda) = \sum_k \gamma_k\, (1 - \lambda)^k.
   • Deliverables: code, a 4–6 page report, a 10-minute talk. Chapters: ch. 4, 5.
   • Success: accuracies as mean ± standard deviation over the ten splits, and learned responses checked against Proposition 5.5: low-pass on Cora, and on Texas?
3. [Solo · ≈ 15 h] Temporal link prediction: how much do the negatives matter? Does a temporal GNN still beat plain memorization once the negatives are hard? A paper study of Poursafaei, Huang, Pelrine & Rabbany, “Towards Better Evaluation for Dynamic Link Prediction” (NeurIPS 2022, Datasets and Benchmarks).
   • Implement: the protocol of ch. 5 (causal split, random, historical and inductive negatives); TGN with PyG’s TGNMemory, against EdgeBank, the memorization baseline of the paper.
   • Data: the Wikipedia (page edits) and Reddit (posts) interaction streams of JODIE (Kumar, Zhang & Leskovec, 2019).
   • Deliverables: code, a 4-page report, a 10-minute talk. Chapters: ch. 5, 8.
   • Success: AP under the three negative samplers, transductive and inductive, over 3 seeds, and a check of the paper’s finding that rankings change between random and historical negatives.

Group projects

1. [Group of 3–4 · ≈ 30 h each] GraphRAG against vector RAG on multi-hop questions. When does an LLM-built knowledge graph beat BM25 and dense retrieval, and at what token cost? This is the graph work package of capstone Y1.1.
   • Implement: the final lab of ch. 10 at scale, on 1,000 questions of the 2WikiMultiHopQA dev split (Ho et al., COLING 2020), 600 to tune and 400 to test. Score the extraction against the gold evidence triples, complete the graph with R-GCN + DistMult on a leakage-free split (ch. 6, Example 8.1), then compare local search, global search and pseudo-code prompting.
   • Other modules: relation extraction from NLP, 6.4; a bandit router from Reinforcement Learning, ch. 4; RAG evaluation from Large Language Models, ch. 7.
   • Split: extraction and entity resolution; graph, completion and communities; retrieval, evaluation and statistics.
   • Deliverables: repository, an 8–10 page report, a 15-minute defence. Chapters: ch. 0, 3, 6, 8, 10.
   • Success: EM, F1 and support recall per question type with paired bootstrap intervals, token cost per question, a re-identification audit (10.3), and a clear verdict on where the graph helps.
2. [Group of 3 · ≈ 30 h each] How much of the score is leakage? Temporal fraud detection. How much does a random split inflate graph-based fraud detection, and do GNNs survive a change of regime?
   • Data and paper: the Elliptic Bitcoin graph (203,769 transactions, 234,355 payment flows, 49 time steps, about 2% labelled illicit) of Weber et al., “Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics” (KDD workshop, 2019).
   • Implement: a tabular random forest, GCN and GAT, and EvolveGCN (Pareja et al., 2020), each under a random node split and under the paper’s temporal split (train on steps 1–34, test on 35–49).
   • Split: protocol and tabular baseline; static GNNs; temporal model and analysis.
   • Deliverables: repository, an 8-page report, a 15-minute defence. Chapters: ch. 1, 5, 8.
   • Success: illicit-class F1 under both splits over 3 seeds, the inflation quantified, and the collapse after the dark-market shutdown (step 43) explained.
3. [Group of 3 · ≈ 30 h each] Valence-aware molecule generation. Do constraints inside the decoder beat post-processing, and can a property predictor steer the sampler? This is the graph work package of capstone Y1.4.
   • Implement: a GraphRNN-style generator with valence masking (the NeVAE idea, 9.3); a small discrete-diffusion model trained with the cross-entropy loss of 9.5; guidance (9.7) by a GIN predictor of logP, with an EGNN on RDKit conformers as an option.
   • Data: QM9 (about 134k molecules) and the 250k-molecule ZINC subset of Gómez-Bombarelli et al. (2018).
   • Other modules: diffusion and guidance from Multimodal GenAI, ch. 3–4.
   • Split: autoregressive model; diffusion model; evaluation and guidance.
   • Deliverables: repository, an 8-page report, a 15-minute defence. Chapters: ch. 5, 8, 9.
   • Success: validity, uniqueness, novelty, degree and orbit MMD and FCD, against an ER baseline; validity above 90% with masking; a measurable shift of the logP distribution under guidance.

Written exam (proposal)

Two hours, one handwritten A4 sheet allowed, no electronic device; four questions, 20 points.

1. Question (4 points). A colleague reports an AUC of 0.95 for link prediction with a GAE trained on all the edges, then evaluated on 10% of them. Explain why the number is optimistic, give the three steps of a leakage-free protocol, and say what changes when the edges carry timestamps.

   Expected:

   • The encoder passed messages along the test edges, so their endpoints have similar embeddings by construction (1 pt).
   • Remove the test and validation edges and draw negatives before training; train, and compute structural features, on the remaining graph only; score the held-out positives against the negatives, with hyperparameters chosen on validation (2 pts).
   • With timestamps: a chronological split, the causality rule, and historical negatives (1 pt).

2. Question (5 points). The star K_{1,3} has center 0 and leaves 1, 2, 3. (a) Give L = D - A, its spectrum and a Fiedler vector. (b) Compute \hat A e_0 for the GCN propagator \hat A. (c) Compute the PageRank of the center for a teleport probability \alpha.

   Expected:

   • 1. D = \mathrm{diag}(3, 1, 1, 1); spectrum 0, 1, 1, 4; a Fiedler vector is (0, 1, -1, 0), or any vector null at the center whose leaf values sum to zero (2 pts).
   • 2. The degrees with self-loops are (4, 2, 2, 2), so the first column of \hat A is (1.5 pts) \hat A e_0 = \Big(\frac14, \frac{1}{2\sqrt2}, \frac{1}{2\sqrt2}, \frac{1}{2\sqrt2}\Big) \approx (0.25, 0.35, 0.35, 0.35).
   • 3. The leaves share 1 - \pi_0 and send all their mass to the center, so \pi_0 = (1 - \alpha)(1 - \pi_0) + \alpha / 4 and \pi_0 = \frac{1 - 3\alpha/4}{2 - \alpha}, which is d_0 / 2m = 1/2 at \alpha = 0 and about 0.48 at \alpha = 0.15 (1.5 pts).

3. Question (5 points). Show that the GCN layer f(X, A) = \sigma(\hat A X W), with \sigma applied entrywise, is permutation-equivariant: f(\Pi X, \Pi A \Pi^\top) = \Pi f(X, A) for every permutation matrix \Pi. Deduce that a sum readout makes the model invariant.

   Expected:

   • The new adjacency with self-loops is \Pi \tilde A \Pi^\top and its degree matrix is \Pi \tilde D \Pi^\top. Since \tilde D is diagonal and \Pi orthogonal, its inverse square root is \Pi \tilde D^{-1/2} \Pi^\top (2 pts).
   • Hence the new propagator is \Pi \hat A \Pi^\top, and \Pi \hat A \Pi^\top \Pi X W = \Pi \hat A X W because \Pi^\top \Pi = I (1.5 pts).
   • An entrywise \sigma commutes with a permutation of the rows (0.5 pt).
   • \mathbf{1}^\top \Pi = \mathbf{1}^\top, so the readout \mathbf{1}^\top H is invariant (1 pt).

4. Question (6 points). On the 6-cycle C_6, consider pure GCN propagation H^{(\ell)} = \hat A^\ell X. (a) Give the eigenvalues of A and of \hat A. (b) Give the rate \rho of Theorem 5.3, and the number of layers after which the non-constant part of any signal has shrunk by a factor 100. (c) What happens to the alternating signal x = (1, -1, 1, -1, 1, -1)?

   Expected:

   • 1. \mu_k = 2\cos(2\pi k / 6), that is 2, 1, 1, -1, -1, -2. Since \hat A = (A + I)/3, its eigenvalues are 1, \frac23, \frac23, 0, 0, -\frac13 (2 pts).
   • 2. \rho = 2/3, and (2/3)^\ell \leq 1/100 requires \ell \geq \ln 100 / \ln 1.5 \approx 11.4, so 12 layers (2 pts).
   • 3. x is the eigenvector of \mu = -2, so \hat A x = -x/3: each layer flips its sign and divides it by 3, which is Proposition 5.5 with d = 2 (2 pts).

Grading rubric (proposal)

References

• W. Hamilton, Graph Representation Learning, Morgan & Claypool, 2020 — free online: the textbook of the module.
• T. Kipf, M. Welling, Semi-Supervised Classification with Graph Convolutional Networks (GCN), ICLR 2017.
• P. Veličković et al., Graph Attention Networks, ICLR 2018.
• W. Hamilton et al., Inductive Representation Learning on Large Graphs (GraphSAGE), NeurIPS 2017.
• M. Defferrard et al., Neural Networks on Graphs with Fast Localized Spectral Filtering (ChebNet), NeurIPS 2016.
• J. Gilmer et al., Neural Message Passing for Quantum Chemistry (MPNN), ICML 2017.
• B. Perozzi et al., DeepWalk: Online Learning of Social Representations, KDD 2014.
• A. Grover, J. Leskovec, node2vec: Scalable Feature Learning for Networks, KDD 2016.
• J. Qiu et al., Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec (NetMF), WSDM 2018.
• T. Kipf, M. Welling, Variational Graph Auto-Encoders, 2016.
• R. Ying et al., Graph Convolutional Neural Networks for Web-Scale Recommender Systems (PinSage), KDD 2018.
• F. Schlichtkrull et al., Modeling Relational Data with Graph Convolutional Networks (R-GCN), ESWC 2018.
• Z. Ying et al., Hierarchical Graph Representation Learning with Differentiable Pooling (DiffPool), NeurIPS 2018.
• K. Xu et al., Representation Learning on Graphs with Jumping Knowledge Networks, ICML 2018.
• W.-L. Chiang et al., Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks, KDD 2019.
• H. Zeng et al., GraphSAINT: Graph Sampling Based Inductive Learning Method, ICLR 2020.
• W. Hu et al., Open Graph Benchmark: Datasets for Machine Learning on Graphs, NeurIPS 2020.
• M. Simonovsky, V. Komodakis, GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders, ICML 2018 (workshop).
• B. Samanta et al., NeVAE: A Deep Generative Model for Molecular Graphs, AAAI 2019.
• J. You et al., GraphRNN: Generating Realistic Graphs with Deep Recurrent Network Models, ICML 2018.
• C. Vignac et al., DiGress: Discrete Denoising Diffusion for Graph Generation, ICLR 2023.
• M. Gerlach, T. Peixoto, E. Altmann, A Network Approach to Topic Models (TopSBM), Science Advances 2018.
• M. Newman, Networks, 2nd ed., Oxford University Press, 2018 — descriptive statistics, centralities and random graph models (ch. 0, ch. 9); U. Brandes, “A Faster Algorithm for Betweenness Centrality”, Journal of Mathematical Sociology, 2001.
• N. Shervashidze et al., “Weisfeiler-Lehman Graph Kernels”, JMLR 12, 2011; S. Vishwanathan et al., “Graph Kernels”, JMLR 11, 2010; N. Kriege, F. Johansson, C. Morris, A Survey on Graph Kernels, Applied Network Science, 2020; D. Liben-Nowell, J. Kleinberg, “The Link-Prediction Problem for Social Networks”, JASIST, 2007 — ch. 2.
• J. Zhu et al., Beyond Homophily in Graph Neural Networks (H2GCN), NeurIPS 2020; E. Chien et al., Adaptive Universal Generalized PageRank Graph Neural Network (GPR-GNN), ICLR 2021; H. Pei et al., Geom-GCN, ICLR 2020; Y. Ma et al., Is Homophily a Necessity for Graph Neural Networks?, ICLR 2022 — heterophily, ch. 5.
• D. Xu et al., Inductive Representation Learning on Temporal Graphs (TGAT), ICLR 2020; E. Rossi et al., Temporal Graph Networks for Deep Learning on Dynamic Graphs (TGN), 2020; A. Pareja et al., EvolveGCN, AAAI 2020 — temporal graphs, ch. 5.
• V. Satorras, E. Hoogeboom, M. Welling, E(n) Equivariant Graph Neural Networks, ICML 2021; J. Jumper et al., “Highly accurate protein structure prediction with AlphaFold”, Nature, 2021 — geometric graphs, ch. 8.
• O. Shchur et al., Pitfalls of Graph Neural Network Evaluation, 2018; F. Errica et al., A Fair Comparison of Graph Neural Networks for Graph Classification, ICLR 2020; V. P. Dwivedi et al., Long Range Graph Benchmark, NeurIPS 2022 — benchmarking, ch. 8.
• M. Bronstein et al., Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, Gauges, 2021 — the “unified charter” (E(n)-equivariance).
• D. Edge et al., From Local to Global: A Graph RAG Approach to Query-Focused Summarization, 2024.
• H. Wang et al., Can Language Models Solve Graph Problems in Natural Language? (NLGraph), NeurIPS 2023.
• B. Fatemi et al., Talk like a Graph: Encoding Graphs for Large Language Models, ICLR 2024.
• Z. Wu et al., A Comprehensive Survey on Graph Neural Networks, IEEE TNNLS, 2021.
• 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 — expressivity, ch. 5.
• S. Fortunato, M. Barthélemy, “Resolution limit in community detection”, PNAS 104, 2007; T. Peixoto, “Parsimonious module inference in large networks”, Physical Review Letters 110, 2013, and “Hierarchical block structures and high-resolution model selection in large networks”, Physical Review X 4, 2014 — resolution limits, ch. 0 and ch. 9.
• F. Poursafaei, S. Huang, K. Pelrine, R. Rabbany, Towards Better Evaluation for Dynamic Link Prediction, NeurIPS 2022; S. Huang et al., Temporal Graph Benchmark for Machine Learning on Temporal Graphs, NeurIPS 2023 — the temporal protocol, ch. 5.
• Y. Li et al., Diffusion Convolutional Recurrent Neural Network (DCRNN), ICLR 2018; B. Yu, H. Yin, Z. Zhu, Spatio-Temporal Graph Convolutional Networks (STGCN), IJCAI 2018 — demand forecasting, ch. 8.
• J. Austin et al., Structured Denoising Diffusion Models in Discrete State-Spaces (D3PM), NeurIPS 2021; J. Feydy et al., Interpolating between Optimal Transport and MMD using Sinkhorn Divergences, AISTATS 2019 — ch. 9.
• X. Ho et al., Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps (2WikiMultiHopQA), COLING 2020; T. Gao et al., Enabling Large Language Models to Generate Text with Citations (ALCE), EMNLP 2023 — GraphRAG worked and final lab, ch. 10.
• C. Morris et al., TUDataset: A collection of benchmark datasets for learning with graphs, 2020; M. Weber et al., Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics, KDD workshop, 2019 — labs and projects.
• Research at DaSciM (LIX): F. Rousseau, M. Vazirgiannis, Main Core Retention on Graph-of-Words for Single-Document Keyword Extraction, ECIR 2015; A. Tixier, F. Malliaros, M. Vazirgiannis, A Graph Degeneracy-based Approach to Keyword Extraction, EMNLP 2016; G. Michel, G. Nikolentzos, J. Lutzeyer, M. Vazirgiannis, Path Neural Networks: Expressive and Accurate Graph Neural Networks, ICML 2023; M. Chatzianastasis, J. Lutzeyer, G. Dasoulas, M. Vazirgiannis, Graph Ordering Attention Networks, AAAI 2023; I. Evdaimon et al., Neural Graph Generator: Feature-Conditioned Graph Generation using Latent Diffusion, 2024; K. Skianis, G. Nikolentzos, M. Vazirgiannis, Graph Reasoning with Large Language Models via Pseudo-code Prompting, 2024.
• PyTorch Geometric — the framework for the labs; OGB — the benchmarks.