Bonus B: Geometry, Subgraphs and Trust

The thread so far. The second bonus page extends the invariance idea of sessions 6–8 to geometry, the structural encodings of session 7 to motifs, and the trust theme of session 14 to explanations.

Those sessions in one minute each

More questions from every session you have reached, with spaced repetition: the cumulative review.

This bonus page covers three chapters of the 2024 lecture notes that this year's slides do not: geometric graph learning (notes ch. 17), subgraph matching and motifs (ch. 18) and trustworthy graph AI (ch. 21). One thread joins them: each asks how to put structure we already know into a GNN. In geometry the structure is a symmetry group. In subgraph matching it is a partial order ("is contained in"). In explainability it is a small subgraph that a human can read.

1. Geometric GNNs. A molecule is a graph whose nodes also have 3D coordinates. If you rotate or translate the molecule, its energy stays the same (invariant) and its forces rotate with it (equivariant). Invariant GNNs (SchNet, DimeNet) only feed the network distances and angles, which do not change under rotation. Equivariant GNNs (PaiNN) also carry vector features that rotate together with the input. Geometric diffusion (GeoDiff) generates 3D shapes of molecules by learning to remove noise with an equivariant network.

2. Subgraphs and motifs. A motif is a small pattern that appears in a real network much more often than in a random network with the same degrees. Its significance is a Z-score; the vector of Z-scores (the significance profile) is a fingerprint of a network's domain. Exact subgraph matching is NP-hard, so neural subgraph matching trains a GNN so that "query is a subgraph of target" becomes "query embedding \(\le\) target embedding in every coordinate" (an order embedding). SPMiner then grows frequent motifs greedily in that embedding space.

3. Explainability. GNNExplainer learns a soft mask over edges and features so that the masked graph keeps the model's prediction while the mask stays small. Explanations are judged by fidelity: does the prediction change when you remove the explanation (necessity, \(\text{fid}^+\)), and does the explanation alone keep the prediction (sufficiency, \(\text{fid}^-\))? The characterisation score combines both.

How to read it (hover a step)

1. Decompose and anchor. Around a node \(t\) of the big target graph, take its \(k\)-hop neighbourhood (here a "bowtie": two triangles sharing \(t\)). Each query also has an anchor node, chosen by the user. Query 1 (a triangle) is contained in the bowtie with its anchor mapped to \(t\). Query 2 (a 4-cycle) is not: the bowtie has no 4-cycle.
2. Embed. One shared GNN maps every anchored graph to a vector \(z\) with non-negative entries (the embedding of the anchor node is the embedding of the whole anchored graph).
3. Read the order. The GNN is trained so that "\(G_Q\) is a subgraph of \(G_T\)" holds exactly when \(z_Q\le z_T\) in every coordinate. Geometrically, all subgraphs of \(G_T\) live in the box between the origin and \(z_T\). Query 1 lands inside the box: predicted "yes".
4. Measure the violation. Query 2 sticks out of the box along dimension 1. The squared amount it sticks out, summed over dimensions, is the violation \(E(q,t)\). Training pushes \(E\) to 0 for true subgraph pairs and above a margin \(\alpha\) for non-subgraph pairs. At test time, predict "subgraph" when \(E\lt\epsilon\).

Setting (notes p.93). An ordinary attributed graph is \(G=(A,S)\): \(A\) is the \(n\times n\) adjacency matrix and \(S\in\mathbb R^{n\times f}\) holds \(f\) scalar features per node (for an atom: its type and charge). A geometric graph adds positions: \(G=(A,S,R)\) with \(R\in\mathbb R^{n\times d}\), so node \(i\) sits at a point \(r_i\in\mathbb R^d\) (usually \(d=3\)). A molecule is the standard example: atoms are nodes, bonds are edges with features \(a_{ij}\) (bond type), and sometimes we know each atom's 3D position \(r_i\). Proteins, materials and point clouds are other examples.

The problem: coordinates are arbitrary

Coordinates depend on the frame you choose: where you put the origin and how you orient the axes. The same molecule, rotated by 90°, gives a completely different matrix \(R\). A normal GNN that takes \(r_i\) as plain input features would give a different output for the rotated copy, even though physically nothing changed. We want the model to know the symmetry of space.

Invariance and equivariance

Let \(\rho\) be a transformation (for example a rotation), acting on inputs as \(\rho_X\) and on outputs as \(\rho_Y\). A function \(F:X\to Y\) is

• equivariant if \(F\circ\rho_X=\rho_Y\circ F\): transforming the input and then applying \(F\) gives the same as applying \(F\) and then transforming the output. Transformation and model commute.
• invariant if \(F\circ\rho_X=F\): the output does not change at all. (Invariance is the special case where \(\rho_Y\) is the identity.)

Physics gives examples of both (notes p.94). The energy of a molecule is a single number; rotating the molecule leaves it unchanged, so it is invariant. The force on each atom is a 3D vector; rotate the molecule and the forces rotate with it, so they are equivariant: \(F(QR)=Q\,F(R)\) for a rotation matrix \(Q\).

The symmetry group for 3D geometric graphs is SE(3), the special Euclidean group: all rigid motions \(r\mapsto Qr+b\) with \(Q\) a rotation (\(Q^\top Q=I\), \(\det Q=1\)) and \(b\in\mathbb R^3\) a translation. "Special" means no reflections (\(\det Q=+1\)). (E(3) also allows reflections; mirror-image molecules can behave differently, so the choice matters.)

Two ways to get symmetry

1. Data augmentation. Use any model and train it on many randomly rotated and translated copies of every example. The model may learn the symmetry approximately. This is expensive (many copies) and gives no guarantee.
2. Build the symmetry into the architecture. Design layers that are invariant or equivariant by construction. This shrinks the search space: the model never wastes capacity learning that rotated molecules are the same molecule. This leads to two classes: invariant GNNs (learn invariant scalar features) and equivariant GNNs (learn equivariant vector/tensor features).

Continuous-filter convolution

On an image, a convolution filter has one weight per grid offset ("one pixel left, one up"). Atoms are not on a grid: the offset \(r_i-r_j\) can be any real vector. So the filter must be a function of the offset, not a lookup table. A continuous-filter convolution (notes p.94) is

• \(h_j^{(l)}\in\mathbb R^f\): the feature vector of atom \(j\) at layer \(l\); \(H^{(l)}\) stacks them.
• \(W^{(l)}:\mathbb R^d\to\mathbb R^f\): the filter-generating function, a small neural network that turns a relative position into a weight vector.
• \(\odot\): element-wise product. Each feature channel of the neighbour is scaled by its own weight.
• The sum runs over neighbours \(j\) (in practice all atoms within a cutoff radius).

This is just message passing where the message from \(j\) to \(i\) is "neighbour features, re-weighted by where the neighbour is".

SchNet: only distances

If \(W\) took the full vector \(r_i-r_j\), the layer would not be rotation-invariant. SchNet (2017) makes it invariant by scalarising: \(W\) only sees the distance \(d_{ij}=\lVert r_i-r_j\rVert\). The distance is first expanded in radial basis functions, \[ e_k(r_i-r_j)=\exp\!\big(-\gamma\,(d_{ij}-\mu_k)^2\big),\qquad k=1,\dots,K, \] and an MLP maps the vector \((e_1,\dots,e_K)\) to the filter. Here \(\mu_k\) are fixed centres spread over the useful distance range and \(\gamma\) sets the width of each bump. (The notes' formula is printed without the square; the standard SchNet radial basis is Gaussian in \(d_{ij}-\mu_k\), as above.)

Why the expansion? A single number \(d_{ij}\) is a poor input for an MLP at the start of training: the network would need many layers to carve it into "very close", "bonded", "far". The Gaussian bumps do this carving for free: each \(e_k\) is large only when \(d_{ij}\) is near \(\mu_k\), like a soft one-hot encoding of the distance (notes: "to curb the initial training difficulties").

Mini-example. Centres \(\mu=(1.0, 1.5, 2.0)\) Å and \(\gamma=10\). A bond of length 1.5 Å gives \(e=(e^{-2.5}, 1, e^{-2.5})\approx(0.08, 1, 0.08)\). A distance of 1.1 Å gives \((e^{-0.1}, e^{-1.6}, e^{-8.1})\approx(0.90, 0.20, 0.0003)\). Different distances light up different channels.

DimeNet: distances and angles

Using only distances throws away angular information about how bonds are arranged. DimeNet (2020) passes messages along edges and includes the angle between consecutive bonds \(k\to j\to i\) in the message. Angles are still invariant, so the model stays invariant.

The limit of invariant features

Distances and angles are not a complete description of 3D shape. The notes' example is cis- and trans-1,2-dichloroethene: two molecules with the same atoms and bonds, where the two chlorine atoms sit on the same side (cis) or opposite sides (trans) of the double bond. Local distance and angle sets can coincide, but the molecules are different (they are geometric isomers). To tell them apart, the model needs directional information: which way vectors point relative to each other.

The general limitation (notes p.94): an invariant GNN only works well if its input features already contain every needed interaction between directions. Anything that requires comparing directions across several hops is lost when you reduce each edge to a scalar.

An equivariant GNN keeps two kinds of features at every node: scalars \(s_i\in\mathbb R^F\) (invariant: they do not change under rotation) and vectors \(v_i\in\mathbb R^{F\times 3}\) (equivariant: under a rotation \(Q\), each of the \(F\) channels rotates, \(v_i\mapsto v_iQ^\top\)). PaiNN (2021) is the example in the notes (p.94–95). Each layer adds residual updates: \[ s_i^{(l+1)}=s_i^{(l)}+\Delta s_i^{(l)},\qquad v_i^{(l+1)}=v_i^{(l)}+\Delta v_i^{(l)}. \]

The scalar message is a continuous-filter convolution with a distance-only filter, just like SchNet: \[ \Delta s_i^{(l)}=\sum_j \phi_s\big(s_j^{(l)}\big)\odot W_s\big(\lVert r_{ij}\rVert\big). \] The vector message has two parts: \[ \Delta v_i^{(l)}=\underbrace{\sum_j v_j^{(l)}\odot\phi_{vv}\big(s_j^{(l)}\big)\odot W_{vv}\big(\lVert r_{ij}\rVert\big)}_{\text{rescale neighbour's vectors}}+\underbrace{\sum_j \phi_{vs}\big(s_j^{(l)}\big)\odot W_{vs}\big(\lVert r_{ij}\rVert\big)\,\frac{r_{ij}}{\lVert r_{ij}\rVert}}_{\text{new vectors along the bond direction}}. \] \(r_{ij}=r_i-r_j\) is the relative position; \(\phi_s,\phi_{vv},\phi_{vs}\) are MLPs on scalars; \(W_s,W_{vv},W_{vs}\) are filter networks on distances.

Why this is equivariant

Look at what each term multiplies. Every weight (\(\phi(\cdot)\), \(W(\cdot)\)) is computed from scalars and distances, which are invariant. Those invariant weights multiply either an existing vector \(v_j\) or the unit vector \(r_{ij}/\lVert r_{ij}\rVert\), both of which rotate with the input. "Invariant number × equivariant vector" is equivariant, and a sum of equivariant vectors is equivariant. So rotating the molecule rotates every \(v_i\) and leaves every \(s_i\) unchanged, at every layer. Translations cancel because only differences \(r_i-r_j\) appear. The key design rule: never apply a nonlinearity directly to vector components (that would break rotation); apply nonlinearities only to scalars, and use scalars to gate vectors.

PaiNN also has an "update" block that mixes the scalar and vector channels inside a node, for example via the norms \(\lVert v_i\rVert\) and dot products \(\langle Uv_i, Vv_i\rangle\), which are invariant and can feed back into the scalars. The notes print the initialisation as \(s^{(0)}=0,\ v^{(0)}=e_i\); in the PaiNN paper the scalars start from an embedding of the atom type and the vectors start at zero (the first vectors are created by the bond-direction term).

Invariant vs equivariant, in one sentence. Invariant models throw away direction at the input and keep only numbers that cannot change; equivariant models keep direction all the way through, at the cost of more careful (and more expensive) layers.

Geometric generative models are used for molecule and protein design, biomolecule structure prediction and simulating how proteins and drug molecules bind (notes p.95).

The task: molecular conformation generation

Input: a molecular graph \(\mathcal G\) (atoms and bonds, no positions). Output: a conformation \(C\), i.e. 3D coordinates for every atom, that is physically stable. One molecule can fold into several stable shapes, so this is a distribution \(p(C\mid\mathcal G)\), not a single answer. Physics says stable shapes follow the Boltzmann distribution \[ p(C)\propto\exp\!\big(-E(C)/T\big), \] where \(E(C)\) is the energy of the shape and \(T\) the temperature (in energy units). Low-energy shapes are exponentially more likely; higher temperature flattens the distribution. The model must learn to sample from this distribution.

Diffusion models in four lines

1. Forward process (fixed, no learning). Take a real sample \(x_0\) and destroy it gradually with noise over time steps \(t=0,\dots,T\): \(x_t=\mu_t x_0+\sigma_t\epsilon\), with \(\epsilon\sim\mathcal N(0,I)\). \(\mu_t\) shrinks and \(\sigma_t\) grows with \(t\), so \(x_T\) is almost pure noise.
2. Reverse process (learned). Train a network to undo one step: given \(x_t\), predict \(x_{t-1}\) (equivalently, predict the noise \(\epsilon\) that was added).
3. Sampling. Start from pure noise \(x_T\) and apply the learned denoiser step by step down to \(x_0\).
4. Why it works. Each step is a small, easy correction; chaining many small corrections can produce a complex distribution.

GeoDiff

GeoDiff (2022) applies this to conformations. The forward process \(q(C^{(t)}\mid C^{(t-1)})\) adds Gaussian noise to the atom positions. The model learns the reverse \(p_\theta(C^{(t-1)}\mid\mathcal G, C^{(t)})\), conditioned on the molecular graph. The denoising network is an equivariant GNN. This matters: if you rotate the noisy input, the predicted correction must rotate too. Then the learned distribution over shapes is itself rotation-invariant: the model never prefers one orientation of the molecule over another.

Subgraphs are the building blocks of networks: they help to characterise and to tell apart different kinds of networks. In chemistry, functional groups (such as –OH) are subgraphs that decide much of a molecule's behaviour (notes p.97).

Definitions

Let \(G=(V,E)\).

• Node-induced subgraph: choose nodes \(V'\subseteq V\) and keep every edge of \(G\) among them: \(E'=\{(u,v)\in E: u,v\in V'\}\). (Also just "induced subgraph".)
• Edge-induced subgraph: choose edges \(E'\subseteq E\) and keep the nodes they touch: \(V'=\{v\in V:\exists u,\ (v,u)\in E'\}\).

Example: in a triangle \(\{a,b,c\}\), the node set \(\{a,b,c\}\) induces the full triangle. The path \(a\)–\(b\)–\(c\) is an edge-induced subgraph (edges \(ab, bc\)) but not a node-induced one, because inducing on \(\{a,b,c\}\) must also keep the edge \(ac\).

Graph isomorphism. \(G_1=(V_1,E_1)\) and \(G_2=(V_2,E_2)\) are isomorphic if there is a bijection \(f:V_1\to V_2\) with \((u,v)\in E_1\iff(f(u),f(v))\in E_2\). The complexity of finding \(f\) is famously open: no polynomial algorithm is known, and it is not known to be NP-hard. Subgraph isomorphism: \(G_2\) is subgraph-isomorphic to \(G_1\) if some subgraph of \(G_2\) is isomorphic to \(G_1\); we then say "\(G_1\) is a subgraph of \(G_2\)". This problem is NP-hard (it contains, for example, the clique problem).

Motifs

A network motif is a recurring, significant pattern of interconnections (notes p.97):

• Pattern: a small node-induced subgraph.
• Recurring: it is found many times (we need a definition of frequency).
• Significant: it is more frequent than expected in a suitable random graph (we need a null model).

Classic examples (notes Fig. 18.1): the feed-forward loop (\(a\to b\), \(b\to c\), and also \(a\to c\)) in neuron networks, where it filters out short "noise" signals; the parallel loop in food webs; the single-input module (one regulator controlling many genes) in gene control networks. In social networks the closest relative is the triangle: triadic closure ("friends of friends become friends") makes triangles strongly over-represented.

Frequency

Let \(G_Q\) be a small query graph and \(G_T\) the target graph. Overlapping occurrences are allowed.

• Graph-level frequency: the number of distinct node subsets \(V_T'\subseteq V_T\) whose induced subgraph is isomorphic to \(G_Q\).
• Node-level (anchored) frequency: pick an anchor \(v\in V_Q\). Count the nodes \(u\in V_T\) such that some subgraph of \(G_T\) is isomorphic to \(G_Q\) with the isomorphism mapping \(u\) to \(v\). Each \(u\) counts once, however many copies it sits in.

Why two definitions? Graph-level counts can explode. Take a star with one centre and 100 leaves, and let \(G_Q\) be a star with 6 leaves. Every choice of 6 leaves gives an induced copy, so the graph-level frequency is \(\binom{100}{6}\approx1.2\times10^9\). The node-level frequency with the anchor at the query's centre is just 1 (only the centre can play that role). Node-level counts are robust and, as section 6 shows, match how GNNs embed anchored neighbourhoods. A dataset of many graphs is treated as one big disconnected \(G_T\).

Null models: what is "random"?

• Erdős–Rényi \(G_{n,p}\): \(n\) nodes; each edge appears independently with probability \(p\). Degrees are binomial, which is unrealistic for social graphs (they have hubs). Comparing a social network to \(G_{n,p}\) would make almost every pattern look "significant" just because of the hubs.
• Configuration model: keep the real graph's degree sequence. Give each node as many "spokes" (half-edges) as its degree, then pair up all spokes uniformly at random. The result \(G^{\text{rand}}\) has exactly the same degrees as \(G^{\text{real}}\). (Self-loops and multi-edges may appear; they are rare in large sparse graphs and are usually discarded.)
• Switching: start from the real graph and repeat \(Q\cdot|E|\) times (\(Q\) large, e.g. 100): pick two edges \((a,b),(c,d)\) at random and rewire them to \((a,d),(c,b)\), but only if this creates no self-loop or multi-edge. Every node keeps its degree, so the result is a random graph with the same degree sequence. It is the slowest method.

Degree-preserving models ask the right question: "is this pattern frequent beyond what the degrees alone explain?" They deliberately destroy everything else, such as clustering (notes p.99: you must decide which properties not to preserve).

Significance: Z-scores and the significance profile

For motif \(i\), let \(N_i^{\text{real}}\) be its count in the real graph, and \(\bar N_i^{\text{rand}}\), \(\operatorname{Std}(N_i^{\text{rand}})\) the mean and standard deviation of its count over many random graphs from the null model. Then \[ Z_i=\frac{N_i^{\text{real}}-\bar N_i^{\text{rand}}}{\operatorname{Std}(N_i^{\text{rand}})},\qquad SP_i=\frac{Z_i}{\sqrt{\sum_j Z_j^2}}. \] \(Z_i\gt 0\): over-represented (a motif); \(Z_i\lt 0\): under-represented (an "anti-motif"). The significance profile \(SP\) is the vector of Z-scores normalised to unit length. Larger graphs tend to give larger Z-scores, so normalising lets you compare networks of very different sizes: only the relative significance of the patterns remains.

Toy example. Suppose a follower graph has 500 triangles, and 100 degree-preserving random graphs have on average 200 triangles with standard deviation 50. Then \(Z_\triangle=(500-200)/50=6\): triangles are strongly over-represented. If the open triad (a path of length 2) has \(Z=-2\) and these are the only two patterns, \(SP=(6,-2)/\sqrt{40}\approx(0.95,-0.32)\).

Extensions: directed or undirected, coloured (node types) or not, temporal or static motifs; and variations in the frequency definition, the significance test and the null model (notes p.99).

Problem (notes p.100). Given a large target graph \(G_T\) (possibly disconnected) and a connected query \(G_Q\): is \(G_Q\) a subgraph of \(G_T\)? Exact algorithms are exponential in the worst case. The neural approach (NeuroMatch) trains a GNN to predict the answer, using node-anchored subgraphs. The idea is to use the geometry of the embedding space to mirror the logic of subgraph isomorphism.

Step 1: decompose into anchored neighbourhoods

1. For each node \(v\) of \(G_T\), extract the \(k\)-hop neighbourhood around \(v\) (for example by BFS), with \(v\) as the anchor.
2. Do the same for the query \(G_Q\), around its user-chosen anchor.
3. Embed every anchored neighbourhood with a GNN. The embedding of the anchor node is the embedding of the anchored subgraph.

The answer is "yes" if the query fits inside the neighbourhood of some target node. A \(k\)-layer GNN only sees \(k\) hops, so a query whose radius around the anchor exceeds \(k\) cannot be captured (notes p.102).

Step 2: order embeddings

Define a partial order on \(\mathbb R^D\): \(u\le v\) iff \(u_i\le v_i\) for every coordinate \(i\). Subgraph isomorphism is also a partial order on graphs, with the same three properties (notes Fig. 18.5):

• Transitivity: \(G_1\subseteq G_2\) and \(G_2\subseteq G_3\) imply \(G_1\subseteq G_3\). In the embedding: \(z_1\le z_2\le z_3\) implies \(z_1\le z_3\).
• Anti-symmetry: \(G_1\subseteq G_2\) and \(G_2\subseteq G_1\) imply \(G_1\cong G_2\). In the embedding: \(z_1\le z_2\le z_1\) implies \(z_1=z_2\).
• Closure under intersection: the trivial one-node graph is a subgraph of everything. In the embedding: the origin (embeddings are forced to be non-negative) is below every point, and any two points have a common lower bound, their coordinate-wise minimum.

So if the GNN maps "\(\subseteq\)" to "\(\le\)", these logical properties hold for free in the geometry. Checking a candidate pair is then just \(D\) comparisons, instead of an NP-hard search.

Step 3: the loss

We want \(\forall i:\ z_q[i]\le z_t[i]\iff G_Q\subseteq G_T\). The amount by which a pair violates the order is \[ E(G_q,G_t)=\sum_{i=1}^{D}\max\big(0,\ z_q[i]-z_t[i]\big)^2. \] \(E=0\) exactly when \(z_q\le z_t\). The loss is a max-margin loss: \[ L(G_q,G_t)=\begin{cases}E(G_q,G_t) & \text{if } G_q\subseteq G_t \ \text{(positive pair: push the violation to 0)}\\ \max\big(0,\ \alpha-E(G_q,G_t)\big) & \text{if } G_q\not\subseteq G_t \ \text{(negative pair: violation at least } \alpha)\end{cases} \] with margin \(\alpha\gt 0\). Why cap the negative loss at \(\alpha\)? Without the cap, the network could lower the loss forever by pushing negative pairs infinitely far apart, which would dominate training and teach nothing useful (notes p.102). Once a negative pair is "far enough" (\(E\ge\alpha\)), it contributes zero.

Mini-example. \(D=2\), \(\alpha=1\). Target \(z_t=(3,1)\). Query A: \(z_A=(1,0.5)\), so \(E=0\): predicted subgraph. Query B: \(z_B=(2,2)\), so \(E=\max(0,-1)^2+\max(0,1)^2=1\). If B really is not a subgraph, its loss is \(\max(0,1-1)=0\): already fine. If B is a subgraph, the loss is 1 and the gradient pushes \(z_B[2]\) down (or \(z_t[2]\) up).

Step 4: training data

Each iteration samples a target \(G_T\), a positive query \(G_Q^+\) and a negative query \(G_Q^-\) (notes p.103):

• Positive: sample an induced subgraph of \(G_T\) by BFS sampling. Start with \(S=\{v\}\), visited \(V=\emptyset\). At each step, let \(N(S)\) be all neighbours of \(S\); add a random 10% of \(N(S)\setminus V\) to \(S\) and put the rest into \(V\). After \(K\) steps, take the subgraph induced by \(S\), anchored at \(v\). Typically 3–5 BFS layers, trading runtime against accuracy.
• Negative: corrupt \(G_Q\) by adding or removing nodes and edges so that it is no longer a subgraph.

Half the pairs are positive and half negative. At inference, embed the anchored query and every anchored target neighbourhood, and predict "subgraph" if \(E(G_Q,G_T)\lt\epsilon\). Target embeddings can be precomputed once and reused for many queries.

Problem (notes p.103): among all graphs with \(k\) nodes, find the \(r\) with the highest frequency in \(G_T\). Classic methods must (1) enumerate all size-\(k\) connected subgraphs and (2) count each type, which needs isomorphism tests. Both explode combinatorially, so exact motif counting is feasible only for small sizes (about 3 to 7 nodes).

SPMiner reuses the order embedding from section 6:

1. Decompose \(G_T\) into overlapping node-anchored neighbourhoods.
2. Embed them into the order embedding space with the trained subgraph-matching GNN.
3. Estimate frequency fast. For a candidate motif \(G_Q\) with embedding \(z_Q\), count the sampled neighbourhoods \(G_N\) whose embedding lies in its supergraph region: \[ S_E=\{\,z_N:\ z_Q\le z_N,\ G_N\subseteq G_T\,\}. \] Every neighbourhood above-right of \(z_Q\) contains the motif, so \(|S_E|\) estimates the node-level frequency. No isomorphism tests are needed.
4. Motif walk (a greedy, beam-search-like procedure):
   • Pick a random start node \(u\) in \(G_T\); set \(S=\{u\}\).
   • Repeatedly add one neighbour (in \(G_T\)) of some node of \(S\). Among the candidates, choose the one whose new motif (the subgraph induced by \(S\)) keeps \(|S_E|\) largest. Equivalently, minimise the total violation: the sum of \(E(G_Q,G_N)\) over neighbourhoods \(G_N\) that are not above \(z_Q\).
   • Stop when \(S\) reaches the target size \(k\).

Intuition for the walk. Adding a node can only make a motif bigger, so its embedding moves up and to the right, and fewer neighbourhoods lie above it. The walk picks, at each step, the growth direction that loses the fewest neighbourhoods. In the notes' Fig. 18.7 the red dots move from the dense lower-left of the cloud (small, common patterns) toward the upper right, and the shaded supergraph region of the final motif still contains many blue neighbourhood points. This lets the method target motifs far larger than exact counting allows (the notes' example: the most common motifs with 20 nodes).

The search is greedy, so it can miss the true top motif; running several walks from different start nodes (a beam) reduces this risk. Accuracy also depends on how well the encoder has learned the order: false "yes" answers inflate \(|S_E|\).

Trustworthy AI covers explainability, fairness, robustness and privacy; for graphs, the role of topology in each was long unexplored (notes p.114). The notes' chapter focuses on explainability.

Deep models are black boxes. Explainable AI (XAI) is the umbrella term for research that opens them. Why we want it (notes p.114):

• Trust: people accept a prediction more readily when they can see the reason.
• Causality: attribute importance suggests causes ("attribute X makes the outcome Y"), which can generate scientific hypotheses. (Careful: importance for the model is not automatically causal in the world.)
• Transferability: before deploying on new data, we need to know whether the model's reasoning will still hold there.
• Fair and ethical decisions: society needs to check that the reasons for a decision are acceptable (e.g. a loan refusal).

What makes a model explainable?

• Importance values: scores for input features, pixels, words, nodes or edges.
• Attributions: simple relationships between the prediction and the inputs.
• Concepts and prototypes: explanations in terms of human concepts or typical examples.

Some models are explainable by design. Linear regression \(y=w_1x_1+\dots+w_dx_d\): the weight \(w_i\) is the effect of feature \(x_i\) on the prediction. Decision trees: each internal node is a readable logical test. Dimension reduction lets us look at the data and the class boundary. For black-box models we use add-on methods:

• Proxy (surrogate) model: learn an interpretable model that imitates the black box locally around one input (the idea behind LIME).
• Saliency map: the gradient of the output with respect to the input; large gradients mark sensitive inputs.
• Attention weights: visualise them in transformers or GAT. (They give "some" explanation, but high attention does not always mean high importance.)

Settings: instance-level explanations explain one input \(x\) and its prediction \(\hat y\); model-level explanations describe what the model does over a dataset or a whole class.

Explanations for graphs

For a GNN, an explanation is an important subgraph plus a small subset of node features that play a crucial role in the prediction (notes p.116). Two different goals:

• Explain the phenomenon: what makes a molecule toxic, in reality?
• Explain the model: why does this model recommend no loan for person X?

The two coincide only when the model is right for the right reasons. This distinction returns in section 10.

GNNExplainer (2019) is post-hoc and model-agnostic: train any GNN as usual and save it; at test time, explain its prediction on a given instance. It works for node classification, link prediction and graph classification, and for many architectures (GCN, GAT, GraphSAGE, gated graph sequence networks, graph networks). It explains structure (which edges) and features (which feature dimensions) together (notes p.116).

Setting (node classification)

• \(G_c(v)\): the computation graph of node \(v\), i.e. its \(L\)-hop neighbourhood for an \(L\)-layer GNN; \(A_c(v)\) its adjacency matrix; \(X_c(v)=\{x_u:u\in G_c(v)\}\) its node features.
• The trained GNN \(\phi\) gives a distribution \(P_\phi(Y\mid A_c(v),X_c(v))\) over labels.
• The explainer outputs \((\hat A,\hat X^F)\): a subgraph \(\hat G\subseteq G_c(v)\) with adjacency \(\hat A\), and features \(\hat X^F=\{x_u^F:u\in\hat G\}\) where \(F\) is a mask that removes unimportant feature dimensions.

Objective: mutual information

The mutual information of two random variables measures how much knowing one reduces uncertainty about the other: \[ I(X,Y)=D_{KL}\big(P_{(X,Y)}\,\Vert\,P_X\otimes P_Y\big)=H(X)-H(X\mid Y)=H(Y)-H(Y\mid X). \] It is 0 exactly when \(X\) and \(Y\) are independent, and symmetric. \(H\) is entropy (uncertainty). A good explanation should carry as much information about the prediction as possible: \[ \max_{\hat G}\ I\big(Y,(\hat G,\hat X^F)\big)=H(Y)-H\big(Y\mid A=\hat A,\ X=\hat X^F\big). \] For a fixed trained model, \(H(Y)\) is a constant, so this means: choose the subgraph and features that make the model most certain of its prediction, i.e. minimise the conditional entropy.

From discrete to continuous

There are exponentially many subgraphs, so we cannot try them all. GNNExplainer treats the explanation as a distribution over subgraphs, which (1) can capture several plausible explanations and (2) turns a discrete search into a continuous optimisation. It learns a real matrix \(M\) (one entry per edge) and uses the soft mask \[ A_c\odot\sigma(M), \] where \(\sigma\) is the sigmoid, squashing each entry to \([0,1]\): roughly "probability that this edge is kept". The expected-adjacency approximation \(\mathbb E[H(\cdot\mid\tilde A)]\approx H(\cdot\mid\mathbb E[\tilde A])\) is used, even though \(H\) is not convex (notes p.117). Features get a mask \(\sigma(F)\) in the same way.

The full objective (notes p.118): \[ \min_{M,F}\ -\log P_\phi\big(Y=y\mid A=A_c\odot\sigma(M),\ X=\hat X^F\big)\ +\ \lambda_1\sum\sigma(M)\ +\ \lambda_2\sum\sigma(F). \] The first term keeps the prediction confident (it is the cross-entropy for the predicted class \(y\)); the two regularisers make the masks small, so the explanation is concise. \(\lambda_1,\lambda_2\) trade fidelity against size. After optimisation, threshold \(A_c\odot\sigma(M)\) to get the discrete explanation \(\hat G\).

Which graph to mask: node classification, the node's computation graph; link prediction, the union of the two endpoints' computation graphs; graph classification, the whole graph.

Alternatives (notes p.118): GNN saliency maps (gradients of the output score with respect to edges or features) and GAT attention scores. Both are cheaper, but gradients are local (they measure sensitivity, not the effect of removing an edge) and attention may not reflect importance.

Usually there is no ground-truth explanation, and evaluation has several dimensions: the goal (phenomenon or model), the masking type, and the kind of explanation (sufficient or necessary) (notes p.120). The GraphFramEx framework (diagram on notes p.119) separates the two goals: it trains the GNN, generates a mask with either the true label or the prediction as target, turns the mask into an explanation, and scores it with the characterisation score.

• Phenomenon focus: the target is the true label \(y\). Does the explanation capture the real reason?
• Model focus: the target is the model's own prediction \(\hat y\). Does the explanation capture why the model said what it said?

Fidelity

Let \(S\) be the explanation subgraph, \(G_S\) the graph with only \(S\) kept, and \(G_{C\setminus S}\) the graph with \(S\) removed. Over \(N\) explained instances: \[ \text{fid}^+=\frac1N\sum_{i=1}^N\Big(\mathbb 1(\hat y_i=y_i)-\mathbb 1\big(\hat y_i^{G_{C\setminus S}}=y_i\big)\Big),\qquad \text{fid}^-=\frac1N\sum_{i=1}^N\Big(\mathbb 1(\hat y_i=y_i)-\mathbb 1\big(\hat y_i^{G_S}=y_i\big)\Big). \] \(\hat y_i\) is the prediction on the full graph and \(y_i\) the target (true label or model prediction, depending on the focus). Fidelity measures how much correctness you lose.

• \(\text{fid}^+\) (remove the explanation): high means removing \(S\) destroys the prediction, so \(S\) is necessary. Ideal: \(\text{fid}^+\to1\).
• \(\text{fid}^-\) (keep only the explanation): low means \(S\) alone reproduces the prediction, so \(S\) is sufficient. Ideal: \(\text{fid}^-\to0\).

Characterisation score

To summarise both in one number, take a weighted harmonic mean of \(\text{fid}^+\) and \(1-\text{fid}^-\): \[ c=\frac{w_++w_-}{\dfrac{w_+}{\text{fid}^+}+\dfrac{w_-}{1-\text{fid}^-}}=\frac{(w_++w_-)\,\text{fid}^+\,(1-\text{fid}^-)}{w_+(1-\text{fid}^-)+w_-\,\text{fid}^+}, \] usually with \(w_+=w_-=1\). Like the F1 score, the harmonic mean is high only if both parts are high. (The notes' first fraction prints \(w_-/\text{fid}^-\) in the denominator; the second, expanded form shows it must be \(w_-/(1-\text{fid}^-)\).)

Worked example. Explain 10 correctly predicted nodes (so \(\mathbb 1(\hat y_i=y_i)=1\) for all). Removing the explanation flips 6 predictions: \(\text{fid}^+=6/10=0.6\). Keeping only the explanation, 9 of 10 stay correct: \(\text{fid}^-=1/10=0.1\). Then \(c=\dfrac{2\cdot0.6\cdot0.9}{0.9+0.6}=\dfrac{1.08}{1.5}=0.72\). The explanation is quite sufficient but only moderately necessary: the model can often find another route to the same answer when \(S\) is gone.

Other criteria and other kinds of explanation

• Quality: high fidelity and characterisation. Stability: similar explanations across random seeds of the optimisation. Complexity: short, readable explanations.
• Counterfactual explanations: what minimal change would move the instance to a different class? ("If these three edges were missing, this account would be classified as human.")
• Model-level explanations: what do all instances of a class have in common, for example a typical subgraph the model associates with "toxic"?

Build known structure into graph learning. Symmetry: make layers invariant or equivariant to rotations and translations, so a model of molecules cannot depend on the coordinate frame. Order: embed anchored subgraphs so that "is a subgraph of" becomes "is below-left of", turning an NP-hard check into coordinate comparisons. Readability: explain a GNN by the smallest subgraph and feature set that keep its prediction, and test explanations by removing them and by keeping only them.

All three replace an expensive or ill-defined discrete question (all frames, all subgraphs, all explanations) with a continuous object that gradient descent can handle.

Three topics, each with its own piece of mathematics: symmetry under rotations for molecules, an order relation between embeddings for subgraph matching, and information theory for explanations. The cards keep the three apart and give each formula its small numeric check.

Symbols used in this session

Carried forward. These three topics are good project directions; the Frontier section on each page lists where the 2025–26 literature has gone.

One problem in olympiad style. Give it fifteen minutes on paper before you open the first hint; the hints are graded, so open them one at a time.

Not in the lecture notes. Three or four points where the chapter rounds something off: the exact statement, a second way to see it, and where it stops being true. Each is short and has a pointer for going further.

Try it live. In the Graph Explorer: test whether triangles are over-represented against degree-preserving rewiring and explain a GCN's prediction by removing edges, with a fidelity check. Each lesson has predict-then-check questions.

notebook · L21 geometry, subgraphs, trust builds invariant and equivariant layers, computes motif Z-scores, trains order embeddings for subgraph matching, and runs GNNExplainer with fidelity scores.

Flashcards (click to flip)

• 1872 — Klein's Erlangen programme: a geometry is the study of the invariants of a transformation group. Geometric deep learning (Bronstein et al., 2021) applies the same idea to neural networks: choose the symmetry group first, then the architecture.
• 1970s — the triad census (Holland and Leinhardt) in sociology: counting all 16 directed 3-node configurations in social networks and comparing them with random baselines. This is the direct ancestor of network motifs. 2002 — Milo et al. coin "network motifs" for gene, neural and food-web networks; 2004 significance profiles and "superfamilies" of networks.
• 1971 — Cook lists subgraph isomorphism among the first NP-complete problems; 1976 — Ullmann's algorithm, the classic backtracking matcher. 2015 — Babai announces a quasi-polynomial algorithm for graph isomorphism, the biggest step on that open problem in decades. 2016 order embeddings; 2020 NeuroMatch.
• 2017 — SchNet; 2020 — DimeNet; 2021 — EGNN, PaiNN, and AlphaFold 2 (whose structure module is SE(3)-equivariant) solves much of protein structure prediction; 2022 — GeoDiff; then diffusion for proteins (RFdiffusion, 2023).
• 2016 — LIME (local surrogate models); 2017 — SHAP; 2019 — GNNExplainer, then PGExplainer, SubgraphX and GraphFramEx-style evaluation (2022).

Go deeper in the SNA course. The twelve-unit course on social network analysis in this repository gives the classic side of this lecture in full, with labs and real-data analyses: Unit 7 · Cascades, contagion & influence (small temporal patterns (motifs) as signatures of how something spread); Unit 11 · Polarization, algorithms & misinformation (subgraph patterns and trust: detecting coordination, and knowing when not to believe the detector).

Running project. Section L21 · motifs of notebooks/project/retweet_thread.py applies this lecture to one synthetic X world with coordinated rings, the same graph across the whole course.

Research extension. experiments/motif-signatures (hypotheses written before running): which motifs give rings away: mutual triangles for reciprocal rings, repeated co-retweets with one partner for co-amplification rings; a time-shuffled synchrony null flags organic cascades, not rings.

Generated by scripts/sync_guides.py from the experiments' committed results and the dataset catalogue; rerun it (make sync-guides) after an experiment changes.

motif-signatures

Question. Which small patterns give rings away, and does timing help? experiment folder ↗

Verdicts (hypotheses written before running): H1 refuted, H2 supported, H3 refuted, H4 refuted.

conformal-shift

Question. Do conformal guarantees hold when bots change tactics, or when a platform changes country? experiment folder ↗

Verdicts (hypotheses written before running): H1 supported, H2 supported, H3 supported, H4 supported; H8 supported, H9 supported, H10 refuted, H11 supported.

Datasets for this session

From the repo's catalogue (gl.datasets; the full list with sources and licences is in data/README.md). Load one with gl.datasets.graph(name), temporal(name) or node_data(name).

• Previous: Bonus A — traditional features, label propagation and scaling. Its graphlet counts and WL colours are the classical side of this page's motifs.
• Beyond scalarisation: spherical-tensor equivariant models (Tensor Field Networks, e3nn, MACE) carry higher-order features; Satorras et al. (2021) EGNN is the simplest equivariant layer (arXiv:2102.09844).
• Subgraph GNNs: counting substructures is a way to go beyond the WL limit: GNNs given subgraph counts as features (GSN) or run on many node-deleted subgraphs (ESAN) separate graphs that plain message passing cannot.
• Open question: how do you evaluate an explanation for a real social network where no ground-truth reason exists? Fidelity measures faithfulness to the model, not truth about the world. Can planted-motif benchmarks or counterfactual user studies close this gap?