Graph Generative Models and Applications

Contents

• Introduction and overview
• 0. Recap: generating graphs in M1
• 1. The problem, formalized
• 2. Autoregressive models: DeepGMG and GraphRNN in depth
• 3. VAEs: GraphVAE, NeVAE and valence constraints
• 4. Normalizing flows: change of variables and GraphAF
• 5. Discrete diffusion: DiGress in detail
• 6. Evaluating rigorously: MMD, validity, FCD
• 7. Conditional generation and text-to-graph
• 8. Applications: drugs, materials, synthetic networks
• 9. Research of the LLGA team
• 10. Open problems
• Exercises / Labs
• Projects and assessment
• References

Introduction and overview

Audience: an engineer working on graphs, chemistry or networks who wants to generate valid structures. Empirical first: we start from what fails in practice — a generated molecule with an impossible valence, a generator with a “good” MMD on degrees but the wrong motifs — and only then name the models that address it: GraphRNN, GraphVAE, flows, DiGress.

This module is the generative part of machine learning on relational data, and the sequel to the graph generation chapter of the M1 Graph ML course.

What you will be able to do

• Formalize graph generation as a distributional problem (a distribution over a combinatorial space);
• Explain the DeepGMG and GraphRNN autoregressive models in detail, from the stopping decision to the enumeration order;
• Derive the ELBO of graph VAEs and handle valence constraints (GraphVAE, NeVAE);
• Apply the change of variables of normalizing flows to mixed discrete/continuous variables (GraphAF);
• Unroll the discrete diffusion of DiGress: noising processes, masking orders, denoising network;
• Evaluate a generation rigorously: MMD on graph statistics, chemical validity, FCD;
• Condition the generation (target properties) and generate graphs from text;
• Situate the real applications — drugs, materials, networks — and read the recent research of the LLGA team.

Official objectives and syllabus

Official course description not published (S3/S4 catalog empty): as of the start of the 2026 academic year, the “LLGA 2 – Semestre 3” and “LLGA 2 – Semestre 4” tracks of the 2026-2027 SynapseS catalog still list no courses, and the master’s wiki indicates that the detailed M2 program is “under development” (period 2: “to be completed soon”).

The program below therefore reflects the master’s brochure (period 2), with an indicative volume of ~24 h; these course materials are calibrated to that volume (see the session plan below). The following table maps each brochure theme to the course sections; the materials’ own additions are marked “going beyond the syllabus”.

Where this course fits in the program

An M2 module announced for period 2 and preselected by the Graph × LLM route of the home page, with an explicitly research flavor: taught by the LLGA / DaSciM team, it prepares for internships and PhDs on the generation of discrete structures.

Prerequisites: chapter 9 of Graph Machine and Deep Learning for Generative AI (first encounter with graph generation, revisited in ch. 0); the GNN architectures of Advanced Graph Neural Networks, which serve as denoisers and encoders everywhere here; and the VAE, diffusion and guidance chapters of Multimodal Generative AI (ch. 1, 3–4, 7). Control in Generative AI (M2 P1, upstream) summarises NeVAE, GraphAF and DiGress; this page is the reference for their details.

Optional deepening: Computational Optimal Transport for ML and Fairness, which is not on the Graph × LLM route; its Gromov-Wasserstein chapter goes beyond the one-box summary of ch. 6.

Downstream: the module leads to the biological and industrial applications of generation (ch. 8) and to the open problems (ch. 10) — as many gateways to the research-oriented internship and, beyond, to the PhD; it also feeds the “LLMs × graphs” crossroads developed in Advanced Topics in Large Language Models (ch. 8).

Course outline

• Recap: generating graphs in M1 — what was already covered in M1: introductive versions of graph VAEs and GANs, and the vocabulary of the problem.
• The problem, formalized — graph space, sampling, combinatorial complexity: why generating graphs is hard.
• Autoregressive models: DeepGMG and GraphRNN in depth — building the graph sequentially, decision by decision.
• VAEs: GraphVAE, NeVAE and valence constraints — the graph encoder-decoder and the art of obtaining valid molecules.
• Normalizing flows: change of variables and GraphAF — one-step generation by dense invertible flows, on mixed variables.
• Discrete diffusion: DiGress in detail — noising then denoising edges and attributes: the state of the art explained step by step.
• Evaluating rigorously: MMD, validity, FCD — why visual quality is not enough, and which distributional metrics to use.
• Conditional generation and text-to-graph — targeting a property, and generating from a natural-language description.
• Applications: drugs, materials, synthetic networks — three industrial and scientific territories examined seriously.
• Research of the LLGA team — the lab’s recent contributions, presented by their authors (self-study).
• Open problems — what the community does not yet know how to do, and the internship topics hiding there (self-study).
• Exercises / Labs — implement a toy GraphRNN, train a small graph VAE, evaluate by MMD.
• Projects and assessment — solo and group project subjects, a written-exam proposal and a grading rubric.
• References — the reference papers of each family, to be read in the original.

Session plan

24 h in class (announced) = 8 sessions of 3 h. The volume is the indicative ~24 h given by the master’s brochure for this module (the SynapseS 2026–2027 sheet is not yet published); no session-by-session programme is published, so 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 5.5 h in total): ch. 9 Research of the LLGA team — PathNN, GOAT, NGG, pseudo-code prompting (≈ 3 h) · ch. 10 Open problems (≈ 2.5 h).

How to study this module

• Read the indicated papers after the corresponding chapter: they are written for specialists, the chapter gives you the keys to read them.
• Implement GraphRNN in a toy version (graphs with fewer than 20 nodes, exercise 9) before moving to frameworks: the sequential logic is easier to see there.
• Always check the chemical validity of the molecules generated in the labs: it is the permanent reminder that combinatorics is not an image.
• For each model family, fill in a small “sampling speed / quality / failure mode” table: it is the reading grid of the field.
• Take notes on ch. 9 (the team’s research): it is the best preparation for research internship interviews.

0. Recap: generating graphs in M1

This chapter recalls what the M1 Graph ML course established about graph generation, so that the rest of the module can prove and extend it.

1. The problem, formalized

Before comparing models, we must say precisely what a “law on graphs” is and what a correct generator must respect. A concrete scene shows why: a generator can produce graphs whose statistics are close to the data and which are nevertheless chemically invalid. This chapter fixes the space of graphs, the invariance that any generator must respect, and the statistics that characterize a law on large graphs.

2. Autoregressive models: DeepGMG and GraphRNN in depth

The founding idea (You et al., 2018; Li et al., 2018): sequentialize the construction — a graph becomes a trajectory of local decisions (add a node, add an edge, choose a type), and all the machinery of sequential models (RNNs, then transformers) applies. Two competing formalizations: by nodes (GraphRNN) and by neighborhood expansion (DeepGMG).

• Strengths of autoregressive models: exact likelihood of each ordered sequence, sequential sampling with natural stopping, local constraints injectable at every step (ch. 8 of the Control in Generative AI module);
• Limits: \Theta(n^2) cost in steps, exposure to the order, errors that propagate (a wrong node-type choice contaminates everything after it); diffusion (ch. 5) answers exactly these last two limits.

3. VAEs: GraphVAE, NeVAE and valence constraints

A variational autoencoder generates a whole graph at once from a latent vector, instead of decision by decision. This chapter derives the graph VAE and its matching problem, then shows how NeVAE builds chemical validity into the decoder itself.

3.1. The graph VAE: ELBO and one-shot decoder

3.2. NeVAE in detail: valence as the architect

4. Normalizing flows: change of variables and GraphAF

A VAE only gives a lower bound on the likelihood. A normalizing flow gives it exactly, by transforming simple noise with an invertible map; this chapter proves the change-of-variables formula, shows why triangular Jacobians make it cheap, and applies it to graphs with GraphAF.

The formula and the affine coupling layer were met in Multimodal Generative AI, 4.3 (Proposition 4.3, Definition 4.4) and in the flow box of Deep Learning, 9.4; 4.1 recalls them with the proof, and 4.2 specializes them to graphs.

4.1. The change of variables, proven

4.2. GraphAF: the autoregressive flow for graphs

# GraphAF skeleton (pedagogical): one conditional flow step
import torch, torch.nn as nn

class CouplingStep(nn.Module):
    """y_b = s(h) * x_b + t(h); diagonal Jacobian = prod(s)."""
    def __init__(self, d):
        super().__init__()
        self.net = nn.Linear(64, 2 * d)      # GNN state (64) -> (s, t)
    def forward(self, x_b, h):
        s, t = self.net(h).chunk(2, dim=-1)
        s = torch.sigmoid(s + 2.0)           # s > 0: positive det, stable
        y = s * x_b + t
        return y, s.log().sum(-1)            # y and log|det J|

# generation of an atom/bond decision:
#   h = GNN(G_t); z ~ N(0,1); x, ld = flow(z, h)
#   atom = argmax or sample of softmax(x)  (+ valence mask!)
#   log p(x) = log N(z) - ld   (change of variables theorem)

• Flow balance sheet: exact likelihood, invertible latents (usable for latent optimization), RL fine-tuning of the policy for properties — at the price of a sequential cost equal to the autoregressive models and strong architectural constraints (triangular Jacobians);
• LLGA link: the internal GNN of GraphAF is an MPNN — replacing it by a PathNN (ch. 9) or a graph transformer (cf. Advanced GNN module ch. 5) is an open research question, at the boundary of the two M2 modules.

5. Discrete diffusion: DiGress in detail

Continuous diffusion (Multimodal GenAI module ch. 3) noises with Gaussians — pointless for categorical atom types. DiGress (Vignac et al., ICLR 2023) transposes the machinery to the categorical, via the D3PM framework (Austin et al., 2021): noising = Markov chains on the categories, denoising = closed-form Bayesian posterior. Goal of this chapter: master all the equations.

6. Evaluating rigorously: MMD, validity, FCD

A graph generator is not scored image by image but distribution against distribution (M1 recap); at the M2 level, we require: the formulas, their biases, and their attacks. Why so much rigor? because evaluation drives research: a truncated metric produces truncated models (ch. 10).

7. Conditional generation and text-to-graph

In practice one rarely wants any plausible graph: one wants a molecule with a given property, or a graph matching a description. This chapter compares the three ways of conditioning a generator and the routes by which LLMs now generate graphs from text.

7.1. Three conditioning mechanisms

Classifier-free guidance, recalled. It is proved in Multimodal Generative AI, Theorem 4.1, with the site’s weight convention: w = 1 is the conditional model, w > 1 over-guides. A categorical denoiser outputs logits \ell rather than a noise estimate, and the same rule acts on them, per node and per edge: \tilde\ell_w = \ell(\varnothing) + w\big(\ell(c) - \ell(\varnothing)\big), \qquad \tilde p_w \propto p(\cdot \mid \varnothing)^{1-w}\, p(\cdot \mid c)^{w}. This logit-space version is the one Example 7.3 computes by hand.

7.2. Text-to-graph: the LLM × graphs encounter

The Year 2 end-of-year project Y2.2, a text-to-3D-molecule copilot assembles the pieces of this chapter: a text-conditioned generator, guidance toward properties, and the evaluation of ch. 6.

8. Applications: drugs, materials, synthetic networks

Generating graphs is not an end in itself: it is the operational arm of inverse design — specify what one wants (a property, a structure, a statistic) and let the model explore the space \mathcal{G} on our behalf. This chapter visits the module’s three application territories, each time with the same three questions: which hard constraints? which objectives? which evaluation?

9. Research of the LLGA team

The LLGA master is driven by the DaSciM laboratory (Data Science and Mining, LIX, CNRS — École Polytechnique: M. Vazirgiannis, J. Lutzeyer, G. Nikolentzos and their PhD students), the host laboratory of the internships and PhDs.

This chapter presents four of its works, chosen because they touch directly on the objects of this module: the encoder of the generators (PathNN), the order question (GOAT), a latent-diffusion generator conditioned by features (NGG) and the LLM × graphs frontier (pseudo-code prompting). The other axes of the laboratory are covered by the Graph ML (ch. 11) and Advanced GNN (ch. 9) modules; here, each paper reads as the extension of a chapter.

10. Open problems

The grid of ch. 1 (exchangeability, likelihood, constraints) closes here: four work sites where it still has no satisfactory answer — and a fifth, theoretical one. For each: the 2026 state, the promising direction, and the master’s modules that contribute to it.

Exercises / Labs

1. ★ Guided lab: a complete “home-grown” evaluation (the module’s lab, ch. 6).

   1. Build three reference families: 500 Erdős-Rényi graphs G(n, p{=}0.15), 500 two-block SBMs (p_{in} = 0.3, p_{out} = 0.05), 500 Barabási-Albert (m = 2), with n \sim \mathcal{U}\{20, \dots, 40\};

   2. implement three features per graph (mean degree, mean clustering coefficient, triangles per node) and the Gaussian-kernel MMD of def. 6.1, with both the unbiased estimator (diagonals removed) and the biased one; extensions: full degree and clustering histograms, orbit counts;

   3. compute the 3×3 MMDs families against families, feature by feature, each family against a fresh sample of itself on the diagonal;

   4. redo (c) with n = 20, 50 and 200 graphs drawn per family, and plot the biased and unbiased estimates of the same-family MMD² against n;

   5. bootstrap: 95% intervals on each MMD (200 resamplings);

   6. write the table of ch. 6 and conclude: which pair of families does each feature separate, which does it confuse?

   # lab skeleton (networkx + numpy)
   import networkx as nx, numpy as np
   
   def features(gs):                     # gs: list of graphs
       return np.array([[np.mean([d for _, d in g.degree()]),          # a mean degree
                         nx.average_clustering(g),                     # b clustering
                         sum(nx.triangles(g).values()) / (3 * g.number_of_nodes())]  # c triangles per node
                        for g in gs])
   
   def mmd2(X, Y, sigma=None, unbiased=True):   # squared MMD, Gaussian kernel, median bandwidth
       Z = np.vstack([X, Y]); n, m = len(X), len(Y)
       D2 = ((Z[:, None] - Z[None]) ** 2).sum(-1)
       sigma = sigma or np.sqrt(np.median(D2[D2 > 0]))
       K = np.exp(-D2 / (2 * sigma ** 2))
       Kxx, Kyy, Kxy = K[:n, :n], K[n:, n:], K[:n, n:]
       if unbiased:                      # diagonals removed: can be slightly negative, no sqrt
           return ((Kxx.sum() - np.trace(Kxx)) / (n * (n - 1))
                   + (Kyy.sum() - np.trace(Kyy)) / (m * (m - 1)) - 2 * Kxy.mean())
       return Kxx.mean() + Kyy.mean() - 2 * Kxy.mean()            # biased (V-statistic)

   Proof. Guidance (expected results, from a run of this skeleton with 500 graphs per family):

   • mean degree separates BA from the other two: for BA it is almost fixed at 2m(n-m)/n \approx 3.7, while ER and SBM average about 4.35 (0.15 \times 29) and 5 with a spread of about 1, so ER and SBM are close;
   • clustering separates ER (about 0.14, close to p) from SBM and BA (about 0.23 and 0.26), which it confuses;
   • triangles per node separate SBM (about 0.94) from BA (about 0.41).

   Each feature confuses a different pair: always report several features.

   On two samples of the same family, the biased MMD² exceeds the unbiased one by about \tfrac{2}{n}\big(1 - \mathbb{E}\,k(x, x')\big), here roughly 0.9/n (ch. 6, trap 2), and its square root shrinks like 1/\sqrt n. The lab measures why models must be compared at equal n.

   The bootstrap gives the last lesson: with 20 graphs per family, the 95% interval of ER against SBM on mean degree contains 0 in most runs; with 500, it no longer does. An MMD without an interval is not a conclusion. ∎

2. ★ Valence mask (ch. 3). Alphabet \{C, O, N\} with valences \{4, 2, 3\}, single bonds only. (a) Write the masked sequential decoder (state = remaining valences r_v, Proposition 3.3); (b) sample 1,000 molecules without the mask (unconstrained heads, logits \mathcal{N}(0,1)) then with the mask, up to 12 atoms; (c) measure the validity (no atom exceeds its valence; free valences are filled by implicit hydrogens, as RDKit does) and compare it with the reasoning of Proposition 3.3.

   Proof. Solution: without the mask, each sampled bond violates a valence with increasing probability as generation proceeds (the r_v are no longer respected); the observed validity is typically a few percent at 12 atoms — and 1-(1-\varepsilon)^T \to 1 explains the collapse (prop. 3.3).

   With the mask: 100% validity by construction under this definition (the support is restricted to legal outputs), at the price of a bias bounded by Proposition 3.3 — the renormalization redistributes the forbidden mass onto the legal ones. Requiring instead that every atom be saturated without hydrogens would not be guaranteed: the mask prevents overflow, it does not force the generation to use every free valence before stopping.

   The code: maintain r_v, forbid bonds b with b > r_u or b > r_v, resample among the legal ones — eight lines, the most profitable investment of the module. ∎

3. ★ The CFG sweep (ch. 7). Take up example 7.3 (unconditioned logits (2.0;\ 1.5;\ 0.5), conditioned (3.0;\ 0.5;\ 0.5)) and plot w \mapsto (probability of carbon, entropy) for w \in \{0, 1, 2, 3, 8\}. Where is the “elbow”?

   Proof. Solution: guided logits u + w(c - u) = (2 + w;\ 1.5 - w;\ 0.5).

   • w = 0: probs (0.55;\ 0.33;\ 0.12), H \approx 0.95 nats;
   • w = 1: (0.86;\ 0.07;\ 0.07), H \approx 0.50;
   • w = 2: (0.96;\ 0.01;\ 0.03), H \approx 0.19;
   • w = 3: (0.987;\ 0.002;\ 0.011), H \approx 0.07;
   • w = 8: carbon at 99.99%, H \approx 0.

   Fidelity (probability of carbon) is already nearly maximal at w = 2 while entropy has been divided by five: the elbow is at w \approx 2 — beyond, one pays diversity without gaining the target. The exact curve of Theorem 9.2 of the Control module, on a single step. ∎

4. ★ FCD in dimension 2 (ch. 6). Two Gaussian embedding families of diagonal \mathbb{R}^2: \mu_1 = (0, 0), \Sigma_1 = \mathrm{diag}(1, 4); \mu_2 = (1, 0), \Sigma_2 = \mathrm{diag}(4, 9). Compute the Fréchet distance; what does it become if the two families have the same mean?

   Proof. Solution: for diagonal covariances, (\Sigma_1 \Sigma_2)^{1/2} is diagonal with square roots of the products: \sqrt{1 \times 4} = 2, \sqrt{4 \times 9} = 6. Hence \|\mu_1 - \mu_2\|^2 = 1 and \mathrm{tr}(\Sigma_1 + \Sigma_2 - 2(\Sigma_1\Sigma_2)^{1/2}) = (1 + 4 + 4 + 9) - 2(2 + 6) = 2 , so FCD = 3.

   With equal means, only the trace remains (here 2): the FCD separates means and covariances — why it detects at once a shift in mean properties (logP…) and an impoverishment of diversity (reduced variances), the two typical failures of generators. ∎

5. ★★ The absorbing posterior, in closed form (ch. 5). For the absorbing kernel (stay in state k with probability \alpha_t = 1 - \beta_t, be masked otherwise: sink state [\textsf{MASK}]), prove: q(X_{t-1} = X_0 \mid X_t = \textsf{MASK},\ X_0) = \frac{\bar\alpha_{t-1}\,\beta_t}{1 - \bar\alpha_t}, \qquad \bar\alpha_t = \prod_{s \leq t} \alpha_s, and check that the remaining mass is on X_{t-1} = \textsf{MASK}.

   Proof. Solution: X_t = \textsf{MASK} occurs with probability 1 - \bar\alpha_t (complement of “never masked up to t”); jointly X_{t-1} = X_0, X_t = \textsf{MASK} requires “never masked up to t-1 then masked exactly at t”: probability \bar\alpha_{t-1}\beta_t.

   The quotient gives the formula; the remaining mass equals (1 - \bar\alpha_{t-1})/(1 - \bar\alpha_t) — the two sum to 1 since 1 - \bar\alpha_t = (1 - \bar\alpha_{t-1}) + \bar\alpha_{t-1}\beta_t . This is the D3PM-absorbing posterior: when X_t is masked, X_{t-1} is never revealed — the network must guess it (\hat X_0) then sample it with these probabilities: the inpainting machine of ch. 5. ∎

6. ★★ Flow and latent gradient ascent (ch. 4). (a) For the CouplingStep of ch. 4, show that the log-determinant of the Jacobian equals \sum_i \log s_i and is computed in \mathcal{O}(d); (b) derive a latent gradient step, an alternative to the RL fine-tuning that GraphAF actually uses (Theorem 4.3): to maximize Q(G_t), show that \nabla_{z_t} Q\big(G_t\big) = J_{f_\theta}(z_t)^\top\, \nabla_{x_t}\, Q\big(\mathrm{disc}(x_t)\big), where \mathrm{disc} is the discretization (argmax/sampling); discuss going through the discretization (straight-through gradient / Gumbel-softmax).

   Proof. Hints: (a) the Jacobian is block-triangular \begin{pmatrix} I & 0 \\ \ast & \mathrm{diag}(s) \end{pmatrix} (prop. 4.2): the determinant is the product of the diagonals; for (b), apply the chain rule on z_t \mapsto x_t = f_\theta(z_t) \mapsto G_t.

   Since the discretization is not differentiable, one replaces it with a relaxation (temperature softmax) or propagates back the gradient of the continuous predictor: the guidance step moves z_t without changing the weights — but each displacement pulls the trajectory away from the learned law: too large, it fabricates out-of-distribution graphs that the predictor scores well but that chemistry rejects (the fidelity/diversity trade-off of the Control module ch. 9). ∎

7. ★★ Step-function graphon and triangle density (ch. 1 and 6). Let W be constant by blocks on [0,1]^2 with two blocks: density p in the block 1 (x, y \leq \tfrac{1}{2}), q in block 2, r between blocks.

   1. Show t(K_3, W) = \tfrac{1}{8}\big(p^3 + q^3 + 3 p r^2 + 3 q r^2\big) (integral over the 8 block combinations);

   2. verify numerically with p = 0.9, q = 0.6, r = 0.05 and by sampling a graph with n = 100 nodes (50/50) — why do the two coincide to within \mathcal{O}(1/\sqrt{n})?

   Proof. Solution: each triplet (a, b, c) of blocks contributes \tfrac{1}{8} W_{ab} W_{bc} W_{ac}:

   • (1,1,1) gives p^3, (2,2,2) gives q^3;
   • the three permutations of (1,1,2) give p r^2 each, those of (2,2,1) give q r^2.

   Numerically t = (0.729 + 0.216 + 0.0068 + 0.0045)/8 \approx 0.1195 . The sampling realizes Bernoulli variables with parameters W(x_i, x_j), independent conditionally on the latents: the empirical triangle density is an average of bounded terms in which each edge has a small influence — concentration (McDiarmid’s bounded-differences inequality) around t(K_3, W) at rate \mathcal{O}(1/\sqrt{n}): this is the sampling lemma of Theorem 1.4, verified hands in the mud. ∎

8. ★★★ Open: text-to-graph and target features (ch. 7, 9).

   1. Ask an LLM to produce NetworkX code generating 500 graphs with a statistical specification (mean degree 4, clustering 0.3, n between 20 and 40) — the “Demystifying” route of ch. 7;

   2. evaluate with the MMD of lab 1 against an SBM family calibrated to the same features;

   3. critique: did the LLM optimize the features (by reading them in the prompt) or generate a law (unrequested distributional properties)? Compare with the NGG approach (conditioning by features, ch. 9): what additional guarantees does the trained model give? (Synthesis question — defense.)

   Proof. Hints: also measure unrequested features (spectrum, diameter, motifs): the LLM/SBM difference there is proof that the LLM satisfies the letter of the specification without capturing its distributional spirit (or the opposite); NGG, for its part, learns the law conditional on the features from real data — the unspecified correlations come from the data, not from the prompt. This is the exact frontier of open problem 10.4. ∎

9. ★★★ Lab: a toy GraphRNN, and the order question (ch. 2, 6).

   1. Read the code: each node contributes its BFS row S^i (Proposition 2.2), truncated to its M predecessors; check that an all-zero row can serve as STOP, because in BFS order every new node is linked to an earlier one;

   2. train on 300 connected two-block SBMs with 12 to 18 nodes, then sample 100 graphs;

   3. evaluate with the harness of exercise 1 (features, mmd2) against the held-out graphs (the 54 connected SBMs beyond the first 300), and against an Erdős-Rényi baseline with the same sizes and densities;

   4. open: replace the random-root BFS by a fixed root, then by a uniformly random order with M = n. How do the loss, the samples and the training time change? Which graphs does each order make hard (rings, long paths)?

   # toy GraphRNN (torch); nx, np, features and mmd2 come from the skeleton of exercise 1
   import torch, torch.nn as nn
   torch.manual_seed(0); rng = np.random.default_rng(0)
   M = 12                                    # bandwidth: node i links only to its M predecessors
   
   def bfs_rows(g):                          # (n-1, M): row i-1, column k = edge to node i-1-k
       root = int(rng.integers(g.number_of_nodes()))
       order = [root] + [v for _, v in nx.bfs_edges(g, root)]
       A, S = nx.to_numpy_array(g, nodelist=order), np.zeros((len(order) - 1, M))
       for i in range(1, len(order)):
           prev = A[i, max(0, i - M):i][::-1]
           S[i - 1, :len(prev)] = prev
       return S
   
   class GraphRNN(nn.Module):
       def __init__(self, h=64):
           super().__init__()
           self.node, self.edge = nn.GRU(M, h, batch_first=True), nn.GRU(1, h, batch_first=True)
           self.init, self.out = nn.Linear(h, h), nn.Linear(h, 1)
       def forward(self, S):                 # S: (B, L, M); an all-zero row means STOP
           B, L, _ = S.shape
           h, _ = self.node(torch.cat([torch.ones(B, 1, M), S[:, :-1]], 1))   # teacher forcing
           bits = S.reshape(B * L, M, 1)
           o, _ = self.edge(torch.cat([torch.ones(B * L, 1, 1), bits[:, :-1]], 1),
                            self.init(h).reshape(1, B * L, -1))
           return self.out(o).reshape(B, L, M)                                 # one logit per bit
   
   @torch.no_grad()
   def sample(model, n_max=40):
       x, hn, g = torch.ones(1, 1, M), None, nx.empty_graph(1)
       for i in range(1, n_max):
           h, hn = model.node(x, hn)
           he, b, row = model.init(h), torch.ones(1, 1, 1), []
           for k in range(M):
               o, he = model.edge(b, he)
               b = torch.bernoulli(torch.sigmoid(model.out(o)))
               row.append(int(b))
           if sum(row) == 0: break           # STOP: in BFS order every new node has a parent
           g.add_edges_from((i, i - 1 - k) for k in range(M) if row[k] and i - 1 - k >= 0)
           x = torch.tensor(row, dtype=torch.float).reshape(1, 1, M)
       return g
   
   data = [g for s, k in enumerate(rng.integers(6, 10, 400))   # connected 2-block SBMs, 12-18 nodes
           if nx.is_connected(g := nx.stochastic_block_model([k, k], [[0.6, 0.05], [0.05, 0.6]], seed=s))]
   train, test = data[:300], data[300:]
   model = GraphRNN(); opt = torch.optim.Adam(model.parameters(), lr=3e-3)
   for step in range(1500):                  # about a minute on a laptop CPU
       rows = [bfs_rows(train[i]) for i in rng.integers(len(train), size=32)]
       L = max(len(r) for r in rows) + 1     # + one STOP row
       S, mask = torch.zeros(len(rows), L, M), torch.zeros(len(rows), L)
       for b, r in enumerate(rows):
           S[b, :len(r)], mask[b, :len(r) + 1] = torch.tensor(r), 1
       nll = nn.functional.binary_cross_entropy_with_logits(model(S), S, reduction="none").sum(-1)
       loss = (nll * mask).sum() / mask.sum()
       opt.zero_grad(); loss.backward(); opt.step()
   gen = [sample(model) for _ in range(100)]

   Proof. Expected results (one run of this code, about a minute on a laptop CPU): every sample is connected — the BFS construction guarantees it — and the sizes match (about 15 nodes). The clustering MMD² is about 0.03, against 0.35 for the density-matched ER baseline; on degrees and triangles both are close to the data.

   Hints for (d): a random order breaks the bandwidth bound of BFS, so M must grow to n and the rows lose their local structure; and the training losses of two orders are bounds on different quantities, \log p_\theta(G, \pi) for different laws of \pi (Theorem 2.1, point 2) — compare samples, not losses. ∎

10. ★★★ Lab: a small graph VAE, and the matching problem (ch. 3).

    1. Read the code: a GCN-style encoder with mean pooling gives q_\phi(z \mid G); the decoder emits the N(N-1)/2 edge logits and N node-existence logits in one shot (Theorem 3.1). A canonical BFS order from a node of maximal degree replaces the Hungarian matching;

    2. train on the graphs of exercise 9, with a KL weight that rises from 0 to 1 over the first 2,000 steps (why is the final loss still minus the ELBO?), sample 100 graphs and evaluate them as in exercise 9;

    3. encode one test graph in its canonical order, then after a random permutation of its nodes: compare the latent means and the reconstruction losses;

    4. open: replace the fixed order by a matching — at each training step, match decoded nodes to true nodes with scipy.optimize.linear_sum_assignment on a node-similarity matrix — and compare the samples with those of (b). Which global properties does a one-shot decoder with independent edges lose?

    # small one-shot graph VAE; data, train, test as in exercise 9
    N, H, Z = 18, 64, 8                       # max nodes, hidden width, latent size
    iu = torch.triu_indices(N, N, 1)          # the N(N-1)/2 upper-triangle slots
    
    def canon(g):                             # padded adjacency, BFS order from a max-degree node
        root = max(g.degree, key=lambda t: t[1])[0]
        order = [root] + [v for _, v in nx.bfs_edges(g, root)]
        A = np.zeros((N, N)); A[:len(order), :len(order)] = nx.to_numpy_array(g, nodelist=order)
        return torch.tensor(A, dtype=torch.float), torch.arange(N) < len(order)
    
    class GraphVAE(nn.Module):
        def __init__(self):
            super().__init__()
            self.l1, self.l2 = nn.Linear(2, H), nn.Linear(H, H)
            self.mu, self.lv = nn.Linear(H, Z), nn.Linear(H, Z)
            self.dec = nn.Sequential(nn.Linear(Z, 256), nn.ReLU(), nn.Linear(256, len(iu[0]) + N))
        def encode(self, A, node):            # dense GCN + mean pooling: permutation-invariant
            P = A + torch.diag_embed(node.float()); P = P / P.sum(-1, keepdim=True).clamp(min=1)
            x = torch.relu(self.l1(torch.stack([node.float(), A.sum(-1) / 4], -1)))  # inputs: 1, degree
            x = torch.relu(self.l2(P @ x)) + x
            hg = (x * node.unsqueeze(-1)).sum(1) / node.sum(1, keepdim=True)
            return self.mu(hg), self.lv(hg)
        def forward(self, A, node):
            mu, lv = self.encode(A, node)
            out = self.dec(mu + torch.randn_like(mu) * (0.5 * lv).exp())       # reparameterization
            return out[:, :-N], out[:, -N:], mu, lv                            # edge, node logits
    
    T = [canon(g) for g in train]
    A_all, n_all = torch.stack([a for a, _ in T]), torch.stack([m for _, m in T])
    vae = GraphVAE(); opt = torch.optim.Adam(vae.parameters(), lr=1e-3)
    bce = nn.functional.binary_cross_entropy_with_logits
    for step in range(3000):                  # about 20 s on a laptop CPU
        i = torch.as_tensor(rng.integers(len(train), size=64)); A, node = A_all[i], n_all[i]
        e_log, n_log, mu, lv = vae(A, node)
        rec = bce(e_log, A[:, iu[0], iu[1]], reduction="sum") + bce(n_log, node.float(), reduction="sum")
        kl = -0.5 * (1 + lv - mu ** 2 - lv.exp()).sum()
        loss = (rec + min(1.0, step / 2000) * kl) / len(i)   # KL warm-up, then loss = -ELBO
        opt.zero_grad(); loss.backward(); opt.step()
    
    @torch.no_grad()
    def sample_vae(k):
        gs = []
        for out in vae.dec(torch.randn(k, Z)):
            keep = torch.bernoulli(torch.sigmoid(out[-N:])).bool()
            A = torch.zeros(N, N); A[iu[0], iu[1]] = torch.bernoulli(torch.sigmoid(out[:-N]))
            gs.append(nx.from_numpy_array(((A + A.T)[keep][:, keep]).numpy()))
        return gs

    Proof. Expected results (one run, about 20 s): the KL stays near 2 nats per graph (in our run without the warm-up and the degree input, it fell to almost 0: posterior collapse, the decoder then outputs an average graph). Only about two samples in three are connected, against all of them for GraphRNN, because the edges are independent given z; the clustering MMD² (about 0.09) lies between GraphRNN’s and the ER baseline’s.

    In (c) the latent means coincide — the encoder is invariant — but the reconstruction loss jumps (from about 58 to 140–190 nats, depending on the permutation): the decoder only knows the canonical order. This is the matching problem of Theorem 3.1, and the reason why GOAT (Work 9.2) studies orders. ∎

Projects and assessment

No official sheet is published yet for this module: the “LLGA 2 – Semestre 3” and “LLGA 2 – Semestre 4” lists of the 2026–2027 SynapseS catalog are empty, so its assessment is not displayed. The subjects, the exam and the rubric below are therefore proposals of these notes, for instance half project and half written exam. They exercise objectives O2 (generative modelling theory), O4 (graph-structured data) and O5 (Graph × LLM), with O7 (hands-on practice) throughout and O8 (trustworthy AI) in solo project 2.

Group project 1 is the generator work package of the Year 2 end-of-year project Y2.2, a text-to-3D-molecule copilot.

Solo projects

1. [Solo · ≈ 20 h] Paper study: graph-generation evaluation done right (O’Bray et al., ICLR 2022). Can the ranking of two graph generators flip with the kernel, its bandwidth or the sample size, and how should an MMD be reported?
   • Implement: extend lab 1 (exercise 1) into a small tested library — unbiased MMD² on degree, clustering and orbit histograms (orbits counted with ORCA, Hočevar & Demšar, 2014), bootstrap intervals, and the Gromov-Wasserstein distance of the ch. 6 box on 50 pairs of graphs.
   • Paper: L. O’Bray, M. Horn, B. Rieck, K. Borgwardt, Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions, ICLR 2022.
   • Data: the ER, SBM and BA families of exercise 1; samples of the GraphRNN of exercise 9 and of the VAE of exercise 10; if a free GPU is available, a DiGress trained with the public code on the SPECTRE SBM set (Martinkus et al., 2022).
   • Deliverables: the library, a 5-page report, a 10-minute talk. Chapters: ch. 1, 6.
   • Success: one ranking flip reproduced (or an explanation of why it does not occur); the 1/n bias of the biased estimator measured within 20%; every MMD reported with a 95% interval.
2. [Solo · ≈ 25 h] Synthetic networks: fidelity against leakage. Can a generator trained on one real network reproduce its statistics without leaking its edges?
   • Implement: train CELL (Rendsburg, Heidrich & von Luxburg, ICML 2020), the low-rank simplification of NetGAN (Bojchevski et al., 2018), on 85% of the edges of a real network. Measure fidelity by MMD on degrees, clustering and orbits (ch. 6), and leakage by an edge-level membership-inference attack: the AUC of “edge present in the synthetic graph” for training edges against the 15% held-out edges.
   • Privacy knob: randomized response on the training adjacency, each bit kept with probability p, so \varepsilon = \ln(p/(1-p)), for 5 values of \varepsilon.
   • Data: the SNAP email-Eu-core network (1,005 nodes). Deliverables: code, a 5-page report with the fidelity–leakage curve, a 10-minute talk.
   • Chapters: ch. 6, 8 (Proposition 8.4); it connects this course to Privacy and Uncertainty.
   • Success: a fidelity–leakage curve over the 5 budgets with error bars over 3 seeds, and a membership AUC near 0.5 at the smallest \varepsilon — or a diagnosis of why not.

Group projects

1. [Group of 3 · ≈ 30 h each] Mask against diffusion: scaffold-constrained molecule generation. On small molecules, which gives the better validity–diversity–property trade-off, with and without an imposed scaffold: a valence-masked autoregressive decoder or discrete diffusion?
   • Implement: (a) a masked autoregressive graph decoder (exercise 2 scaled up, Example 3.4); (b) a small DiGress trained with the public code, with scaffold inpainting (Theorem 5.4); (c) regressor guidance toward QED, swept over the guidance scale.
   • Paper and data: C. Vignac et al., DiGress: Discrete Denoising Diffusion for Graph Generation, ICLR 2023; QM9 (Ramakrishnan et al., 2014: about 134k molecules with at most 9 heavy atoms); RDKit for validity and QED, the fcd package for the FCD.
   • Split: member A the masked decoder; member B DiGress and inpainting; member C the evaluation harness (validity, uniqueness, novelty, FCD; ch. 6) and the guidance sweep.
   • Deliverables: a repository, a 6-page report, a 15-minute talk. Chapters: ch. 2, 3, 5, 6, 7; it uses the fidelity–diversity analysis of Control in Generative AI, ch. 9.
   • Success: DiGress validity and uniqueness within a few points of the paper’s QM9 table; 100% valence validity for the masked decoder (Proposition 3.3); a curve of mean QED against internal diversity over at least 5 guidance scales and 3 seeds.
2. [Group of 3 · ≈ 30 h each] Text-to-graph: LLM-written generators against feature-conditioned latent diffusion. Given a natural-language statistical specification, which approach matches the requested statistics, and which also gets the unrequested ones right? This scales up exercise 8.
   • Implement: (a) an LLM pipeline that turns 20 specifications (size, mean degree, clustering, number of communities) into NetworkX code, run in a sandbox, with natural-language and pseudo-code prompts (Work 9.4); (b) a small NGG-style latent diffusion conditioned on the same features (Work 9.3); (c) the harness of exercise 1, extended to the Laplacian spectrum, the diameter and motif counts.
   • Papers: I. Evdaimon et al., Neural Graph Generator: Feature-Conditioned Graph Generation using Latent Diffusion Models, 2024; Y. Wang et al., Demystifying the Power of Large Language Models in Graph Generation, Findings of NAACL 2025. Model: an open instruction model such as Qwen2.5-7B-Instruct, on a free GPU tier.
   • Split: member A the LLM pipeline and the sandbox; member B the latent diffusion; member C the specifications, the evaluation and the statistics.
   • Deliverables: a repository, a 6-page report, a 15-minute talk. Chapters: ch. 6, 7, 9 and problem 10.4; it connects this course to Large Language Models, ch. 8 and Advanced Topics in LLMs.
   • Success: for both methods, the mean absolute error on the requested features and the MMD on the unrequested ones, with intervals, over the 20 specifications; a paragraph that explains the gap with the “letter against spirit” argument of exercise 8.
3. [Group of 2 · ≈ 25 h each] Multi-objective inverse design with honest Pareto reporting. When properties conflict, does reinforcement-learning fine-tuning of a generator or a genetic baseline give the better Pareto front, and does the scalarization matter?
   • Implement: a SELFIES language model pre-trained on a ZINC-250k subset (ch. 7), fine-tuned by REINVENT-style policy gradient on a weighted and on a geometric scalarization (Definition 8.1); a graph genetic algorithm as baseline (Graph GA, Jensen, 2019).
   • Benchmark: three GuacaMol MPO tasks, for example Osimertinib, Fexofenadine and Ranolazine MPO (Brown et al., 2019).
   • Split: member A the language model and its fine-tuning; member B the baseline, the scalarizations and the Pareto analysis.
   • Deliverables: code, a 5-page report, a 10-minute talk. Chapters: ch. 6, 7, 8; it reuses the policy gradient of Reinforcement Learning.
   • Success: MPO scores over 3 seeds; Pareto fronts and top-10 quality reported rather than batch means (Theorem 8.2); the internal diversity of the top 100.

Written exam (proposal)

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

1. Question (5 points). Place GraphRNN, GraphAF and DiGress in the reading grid of ch. 1: how is each one exchangeable, what does its likelihood objective compute, and which hard constraints can it enforce? Say also how each original paper optimizes or conditions on a molecular property.

   Expected:

   • GraphRNN: exchangeable only on average over BFS orders; it trains \log p_\theta(G, \pi), a lower bound on \log p_\theta(G); step masks are possible; the paper does no property optimization (1.5 points).
   • GraphAF: an autoregressive flow, with the exact likelihood of the dequantized ordered sequence; a valence check at each bond gives 100% validity; properties are optimized by RL fine-tuning with PPO (1.5 points).
   • DiGress: exactly exchangeable (equivariant denoiser, noise independent per node and per edge); a variational bound only; hard constraints only by inpainting a fixed subgraph; property conditioning by regressor guidance on noisy graphs (2 points).

2. Question (6 points). Uniform discrete diffusion on K = 3 types, with \beta_1 = 0.1 and \beta_2 = 0.2, in the row convention of Definition 5.1.

   1. Write Q_1 and Q_2, and compute q(X_2 \mid X_0 = e_1). (b) Compute the posterior q(X_1 \mid X_2 = e_2, X_0 = e_1) with Theorem 5.3. (c) Interpret the result.

   Expected:

   • (a) The uniform kernel Q_t = (1-\beta_t) I + \tfrac{\beta_t}{3}\mathbf{1}\mathbf{1}^\top gives diagonal entries 14/15 and off-diagonal entries 1/30 for Q_1, and 13/15 and 1/15 for Q_2. With \bar\alpha_2 = 0.72, Proposition 5.2 gives q(X_2 \mid X_0 = e_1) = 0.72\, e_1 + 0.28\, \mathbf{u} \approx (0.813,\ 0.093,\ 0.093) \quad \text{(2 points)}.
   • (b) The unnormalized weights (Q_2)_{j2}(Q_1)_{1j} are 14/225, 13/450 and 1/450 for j = 1, 2, 3. They sum to 7/75 = (\bar Q_2)_{12}, so the posterior is q(X_1 \mid X_2 = e_2, X_0 = e_1) = \big(\tfrac23,\ \tfrac{13}{42},\ \tfrac{1}{42}\big) \approx (0.667,\ 0.310,\ 0.024) \quad \text{(3 points)}.
   • (c) The jump to type 2 most likely happened at step 2, the noisier step: X_1 is still the original type with probability 2/3 (1 point).

3. Question (5 points). A valence mask renormalizes each decision on its legal subset. (a) Prove that every sample is valid. (b) Build a two-step example where the masked law differs from the law conditioned on validity. (c) If the mask never removes more than a mass \varepsilon and sequences have at most T steps, prove that for every valid y (1-\varepsilon)^{T} \leq \frac{\tilde p_\theta(y)}{p_\theta(y \mid \text{valid})} \leq (1-\varepsilon)^{-T}.

   Expected: (a) the support argument of Proposition 3.3 (1 point); (b) its counterexample, where the mask gives 0.5 to aa and conditioning gives 0.05/0.55 \approx 0.09 (2 points); (c) write the ratio as P_\theta(\text{valid}) / \prod_t Z(y_{<t}) and show that both terms lie in [(1-\varepsilon)^T, 1] (2 points).

4. Question (4 points). Let X and Y be two independent samples of size n from the same law, and k a Gaussian kernel, so k(x, x) = 1. (a) Show that the biased estimate of \mathrm{MMD}^2 (diagonals included) has mean \frac{2}{n}\big(1 - \mathbb{E}\,k(x, x')\big), \qquad x, x' \text{ independent draws}.

   2. Deduce why two generators must be compared with the same number of samples.

   Expected: (a) for each sample, \mathbb{E}\Big[\frac{1}{n^2}\sum_{i,i'} k(x_i, x_{i'})\Big] = \frac{1}{n} + \Big(1 - \frac{1}{n}\Big)\,\mathbb{E}\,k(x, x'), and the cross term has mean \mathbb{E}\,k(x, x'); subtracting twice the cross term gives the result (3 points). (b) The bias is positive and depends on n: with fewer samples a generator looks worse for no reason (1 point).

Grading rubric (proposal)

References

• Theory: graphons and limits: L. Lovász, Large Networks and Graph Limits, AMS Colloquium Publications 60, 2012 — the reference for the theorems of ch. 1 (Aldous 1981 and Hoover 1979 are presented there in detail).
• Autoregressive models (ch. 2): J. You, R. Ying, X. Ren, W. Hamilton, J. Leskovec, GraphRNN: Generating Realistic Graphs with an Auto-Regressive Model, ICML 2018; Y. Li, O. Vinyals, C. Dyer, R. Pascanu, P. Battaglia, Learning Deep Generative Models of Graphs (DeepGMG), ICML 2018; W. Jin, R. Barzilay, T. Jaakkola, Junction Tree Variational Autoencoder for Molecular Graph Generation, ICML 2018 (generation by fragments).
• VAE (ch. 3): M. Simonovsky, N. Komodakis, GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders, 2018; B. Samanta, A. De, G. Jana, P. K. Chattaraj, N. Ganguly, M. Gomez-Rodriguez, NeVAE: A Deep Generative Model for Molecular Graphs, AAAI 2019; R. Gómez-Bombarelli et al., Automatic Chemical Design Using a Data-Driven Continuous Representation of Molecules, ACS Central Science 2018 (latent optimization).
• Flows (ch. 4): C. Shi, M. Xu, Z. Zhu, W. Zhang, M. Zhang, J. Tang, GraphAF: A Flow-based Autoregressive Model for Molecular Graph Generation, ICLR 2020; Y. Luo, K. Yan, S. Ji, GraphDF: A Discrete Flow Model for Molecular Graph Generation, ICML 2021; D. Tran, K. Vafa, K. K. Agrawal, L. Dinh, B. Poole, Discrete Flows: Invertible Generative Models of Discrete Data, NeurIPS 2019; E. Hoogeboom, D. Nielsen, P. Jaini, P. Forré, M. Welling, Argmax Flows and Multinomial Diffusion: Learning Categorical Distributions, NeurIPS 2021 (argmax surjections).
• Diffusion (ch. 5): J. Austin, D. Johnson, J. Ho, D. Tarlow, R. van den Berg, Structured Denoising Diffusion Models in Discrete State Spaces (D3PM), NeurIPS 2021; C. Vignac, I. Krawczuk, A. Siraudin, B. Wang, V. Cevher, P. Frossard, DiGress: Discrete Denoising Diffusion for Graph Generation, ICLR 2023 (code); C. Niu, Y. Song, J. Song, S. Ermon, Permutation Invariant Graph Generation via Score-Based Generative Modeling (EDP-GNN), AISTATS 2020; J. Jo, S. Lee, S. J. Hwang, Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations (GDSS), ICML 2022; G. Liu, J. Xu, T. Luo, M. Jiang, Graph Diffusion Transformers for Multi-Conditional Molecular Generation (Graph DiT, classifier-free guidance), NeurIPS 2024.
• Evaluation (ch. 6): K. Preuer, P. Renz, T. Unterthiner, S. Hochreiter, G. Klambauer, Fréchet ChemNet Distance, J. Chem. Inf. Model. 2018 (code); V. P. Dwivedi, C. K. Joshi, A. T. Luu, T. Laurent, Y. Bengio, X. Bresson, Benchmarking Graph Neural Networks, JMLR 2023; L. O’Bray, M. Horn, B. Rieck, K. Borgwardt, Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions, ICLR 2022; G. Peyré, M. Cuturi, J. Solomon, Gromov-Wasserstein Averaging of Kernel and Distance Matrices, ICML 2016.
• Molecular benchmarks (ch. 8): T. Sterling, J. Irwin, ZINC 15 — Ligand Discovery for Everyone, J. Chem. Inf. Model. 2015; N. Brown, M. Fiscato, M. H. S. Segler, A. C. Vaucher, GuacaMol: Benchmarking Models for De Novo Molecular Design, J. Chem. Inf. Model. 2019; D. Polykovskiy et al., Molecular Sets (MOSES): A Benchmarking Platform for Molecular Generation Models, Front. Pharmacol. 2020; G. R. Bickerton, G. V. Paolini, J. Besnard, S. Muresan, A. L. Hopkins, Quantifying the Chemical Beauty of Drugs (QED), Nature Chemistry 2012; M. Olivecrona, T. Blaschke, O. Engkvist, H. Chen, Molecular De-novo Design through Deep Reinforcement Learning (REINVENT), J. Cheminformatics 9:48, 2017.
• Materials and networks (ch. 8): T. Xie, X. Fu, O.-E. Ganea, R. Barzilay, T. Jaakkola, Crystal Diffusion Variational Autoencoder for Periodic Material Generation (CDVAE), ICLR 2022; C. Zeni et al., A Generative Model for Inorganic Materials Design (MatterGen), Nature 638, 2025 (models); A. Bojchevski, O. Shchur, D. Zügner, S. Günnemann, NetGAN: Generating Graphs via Random Walks, ICML 2018.
• LLMs × graphs (ch. 7): C. Edwards, T. Lai, K. Ros, G. Honke, K. Cho, H. Ji, Translation between Molecules and Natural Language (MolT5), EMNLP 2022; M. Krenn et al., SELFIES: A Robust Representation for Semantically Valid Graphs, 2020; A. Bran et al., Augmenting Large Language Models with Chemistry Tools (ChemCrow), Nature Machine Intelligence 2024; Y. Wang, R. A. Rossi, N. Park, N. K. Ahmed, D. Koutra, F. Dernoncourt, T. Derr, Demystifying the Power of Large Language Models in Graph Generation, Findings of NAACL 2025; J. Ji et al., Dynamic and Textual Graph Generation via Large-Scale LLM-based Agent Simulation, 2024; Y. Yao et al., Exploring the Potential of Large Language Models in Graph Generation, 2024.
• Research of the DaSciM team (ch. 9): G. Michel, G. Nikolentzos, J. F. Lutzeyer, M. Vazirgiannis, Path Neural Networks: Expressive and Accurate Graph Neural Networks, ICML 2023 (code); M. Chatzianastasis, J. F. Lutzeyer, G. Dasoulas, M. Vazirgiannis, Graph Ordering Attention Networks (GOAT), AAAI 2023; I. Evdaimon, G. Nikolentzos, C. Xypolopoulos, A. Kammoun, et al., Neural Graph Generator: Feature-Conditioned Graph Generation using Latent Diffusion Models, 2024 (code); K. Skianis, G. Nikolentzos, M. Vazirgiannis, Graph Reasoning with Large Language Models via Pseudo-code Prompting, 2024 (code); laboratory page: DaSciM (LIX, École Polytechnique).
• Related modules: M1 foundation and overview: Graph Machine and Deep Learning (ch. 9); expressive encoders: Advanced GNN (M2); control and constraints: Control in Generative AI (M2); continuous diffusion and FID: Multimodal GenAI ch. 3-4, 7; agents and LLMs: Large Language Models (M2) ch. 8; privacy of synthetic networks: Privacy and Uncertainty (M2).