Teaching a Message-Passing Network Is Teaching a Halfspace Over Weisfeiler-Lehman Color Counts

Suppose a helpful teacher wants a graph neural network to learn an exact yes/no property of graphs. What is the smallest set of labeled graphs that forces the network to get every graph in a pool right? Machine teaching theory answers this question for abstract concept classes. It measures the teaching dimension, the size of the smallest example set that rules out every competing hypothesis, and the recursive teaching dimension, a cheaper variant in which teacher and learner share an order for eliminating concepts one at a time. Graph neural network theory has separately shown that message-passing networks, which update each node from a sum or average of its neighbors, can see a graph only through its 1-WL colors. These are the node labels produced by the Weisfeiler-Lehman color-refinement heuristic, which repeatedly relabels each node by its own label together with the multiset of its neighbors' labels. The two theories have never been joined. The only bridge on record, WL meet VC, bounds the passive, random-sample capacity of these networks and says nothing about how few well-chosen examples would suffice.

This note proposes that the join is exact and simple for a common architecture. Take a network with sum aggregation, sum pooling, and a linear output layer. Every yes/no concept it computes is a linear threshold, a halfspace, over the vector that counts how many nodes of each 1-WL color a graph contains. Teaching such a network is therefore teaching a halfspace over a finite set of integer count vectors. That problem has usable structure: teaching sets are made of boundary points, checking a candidate teaching set is a linear program, and an elimination order can be matched to the learner's own bias. The same reduction explains which targets cannot be taught at all. It also produces a new, concrete family of concept classes for the open question of whether recursive teaching cost is at most a constant times Vapnik-Chervonenkis (VC) dimension.

Core Claim

Fix $L$ rounds of message passing and a finite pool $X$ of graphs. Let $u$ be the number of distinct 1-WL colors after $L$ rounds across the pool, and let $n_c(G)$ be the number of nodes of color $c$ in graph $G$. Consider a sum-aggregation network in the style of GIN from How Powerful are Graph Neural Networks?, with injective color embeddings $e_c$, sum pooling, and a linear head $w$ with bias $b$. Its output on $G$ is $\sum_c n_c(G)\, w^\top e_c + b$. With enough width the coefficients $a_c = w^\top e_c$ can be any real numbers, so the class of computable concepts is exactly

$$\mathcal{H}_{L}(X) = \{\, G \mapsto \mathbf{1}[\textstyle\sum_{c=1}^{u} a_c\, n_c(G) > b] \;:\; a \in \mathbb{R}^u,\, b \in \mathbb{R} \,\}.$$

Three consequences follow, and they are what would be new. The first concerns tractability. Graphs with identical color histograms are interchangeable examples, so teaching happens in the WL quotient of the pool, which is often far smaller than the pool itself. A candidate set $S$ teaches a target $h$ exactly when, for every other histogram point $x$, the linear program asking for a halfspace that agrees with $S$ but flips $x$ has no solution. Verifying a teaching set is therefore polynomial, even though finding a minimum one stays hard, as it is for graph-ball concepts (The Computational Complexity of Positive Non-Clashing Teaching in Graphs).

The second concerns the teaching-to-VC ratio. By Radon's theorem, the VC dimension of $\mathcal{H}_L(X)$ is at most $u+1$. This is much smaller than the "number of distinguishable graphs" that WL meet VC obtains for arbitrary readouts, and the gap is precisely what the linear head buys. Flat teaching dimension can nonetheless blow up. The extreme-threshold concepts behave like the empty set in the classic singleton-plus-empty-set example, where teaching the empty concept takes one negative example per point. Recursive teaching should repair this.

The third concerns expressivity. A target that is not WL-invariant has no teaching set of any size for this learner. The obstruction comes with a finite certificate: two graphs with the same color histogram and different labels.

Research Program

The theory strand starts from three prior results. Teaching Dimensions based on Cooperative Learning defines recursive teaching by peeling off the easiest concept at each step. RTD-Conjecture and Concept Classes Induced by Graphs shows that this peeling is equivalent to preference-based teaching and proves recursive teaching dimension (RTD) at most VC dimension for concepts formed by stars and by connected vertex sets in a graph. Simon explicitly leaves other graph-induced classes open. Our classes differ in kind: the domain is a set of graphs rather than a set of vertices, and the class is induced by color refinement rather than by a subgraph pattern.

The first theory task is to prove the halfspace characterization and to state exactly what bounded width and nonlinear readouts break. A multilayer-perceptron head makes the class nearly all functions of the histogram. Its teaching dimension then collapses to the quotient size, and we will report that as the uninteresting limit rather than hide it. The second task is to bound flat and recursive teaching dimension in terms of $u$. Here we use the fact that realizable histograms are not arbitrary lattice points: WL-consistent graphs satisfy linear constraints that tie the color counts of adjacent rounds together. The third task is to test whether RTD is at most a constant times VC dimension on these classes. That would add a structurally natural family to the program opened by Open Problem: Recursive Teaching Dimension Versus VC Dimension, where the best general bound is quadratic (Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes). The geometric tool comes from Vadim V. Lozin et al., who characterize minimal teaching sets of threshold functions by their extremal boundary points. Elena Zamaraeva constrains the scope of that tool: combining several thresholds makes the number of minimal teaching sets explode. We therefore restrict the theory to single-threshold heads.

The algorithmic strand turns recursive elimination into something a gradient-trained network can actually use. Recursive teaching assumes the learner knows the elimination order, and a network trained by gradient descent does not. Through the preference-based view, however, we can choose the preference to be the learner's own bias. Examples are the largest-margin separator, or the lowest-norm one under weight decay. The teacher then only needs to rule out alternatives the learner would prefer over the target. We will compute three kinds of teaching set on each WL quotient: a flat minimum set by integer programming with LP verification, a greedy set-cover approximation, and a margin-preference set. For higher-order learners we repeat the construction with 2-WL or 3-WL colors. The expected result is that the larger color space makes teaching sets grow. That would be the teaching-side counterpart of the expressivity-generalization trade-off reported in WL meet VC.

Baselines

The naive reference point is uniform random sampling from the pool. A GIN is trained on $k$ random labeled graphs, and we record the smallest $k$ at which it labels the entire pool correctly, together with held-out accuracy. This is the passive regime that VC bounds describe. The proposal beats it only if its teaching sets are several-fold smaller at equal final accuracy.

The strongest existing method is GraNT from Nonparametric Teaching for Graph Property Learners. It greedily selects the graphs with the largest prediction discrepancy under the graph neural tangent kernel, a kernel describing how a wide network's predictions change during training. The paper reports training-time reductions of 36.62% on ZINC and 38.19% on ogbg-molpcba at comparable error, but it reports time, not example counts: no reported result found on Lacuna for GraNT's number of selected examples needed to reach exact pool accuracy. We will therefore run GraNT ourselves. It gets the same GIN backbone, the same pools, and the same hyperparameter search budget, and we measure examples consumed until the learner is exact on the pool. Beating it means reaching exact pool accuracy with fewer examples on planted targets, and matching or exceeding its held-out accuracy on real labels.

The ablation that isolates the key ingredient is greedy set cover run on the WL quotient. It uses the same reduction and LP verification but no recursive or preference structure. If this ablation matches the margin-preference sets, the contribution is the reduction and not the recursion, and we will say so. Lower Bounds for Greedy Teaching Set Constructions gives reason to expect it to fall short on some classes, but that is an expectation to test, not a result to assume.

For the expressivity side, the reference numbers on the Circular Skip Links (CSL) graphs are as follows. Standard GIN reaches 10% accuracy, which is chance. Ring-GNN, which adds matrix multiplication to reach 3-WL power, reaches 80% (On the equivalence between graph isomorphism testing and function approximation with GNNs). CLIP, which breaks symmetry by assigning random node colors, reaches over 90% (Coloring Graph Neural Networks for Node Disambiguation).

Why not just…?

Why not just use random node colorings so that expressivity stops being a problem? CLIP does reach universal approximation, and it scores over 90% on CSL (Coloring Graph Neural Networks for Node Disambiguation). That answers whether a target can be represented, not how many examples it takes to pin the target down. Random colors also destroy the quotient: every graph becomes its own equivalence class, so the teaching dimension relative to CLIP should approach the pool size. We will measure this directly by teaching CLIP and GIN the same WL-invariant targets. If CLIP needs no more examples than GIN, our reduction adds nothing, and that outcome would falsify the proposal's practical value.

Why not just train GraNT, which already selects examples? GraNT is greedy and runs on a 1-WL-bounded kernel. Graphs with identical histograms get identical kernel rows, so on pools that contain WL-twins its selection can waste budget on redundant examples, and it offers no certificate that a selected set is sufficient. The comparison above settles whether this matters in practice. If GraNT matches our example counts on the real-benchmark pools, the remaining contribution is the certificates and the theory.

Why not just rely on VC bounds and enough random data? VC dimension describes worst-case random sampling. WL meet VC shows that growing capacity on ENZYMES widened the generalization gap from 5% to over 45%. Adish Singla et al. show that teaching cost can be decoupled from VC dimension altogether. The random-sampling baseline measures exactly this gap.

Proposed Experiments

Pools are built from MUTAG, PTC, PROTEINS, NCI1, ENZYMES, IMDB-BINARY, and ZINC, and each is collapsed by 1-WL hashing for $L = 1$ to $3$. The experiments proceed in three stages.

The first stage uses planted targets. These are random halfspaces over color counts, including extreme thresholds with very few positives, and they are realizable by construction. For each target we compute flat, greedy, and margin-preference teaching sets, then train GIN with a linear head from scratch on only those graphs. The decisive check is whether the gradient-trained network reaches 100% pool accuracy from the margin-preference set alone, without being told any elimination order. If it needs substantially more examples than the combinatorial minimum, recursive teaching does not transfer to neural learners, and that negative result is informative in its own right.

The second stage uses the real labels. We measure how much of each dataset's labeling is realizable by a histogram halfspace, by LP-checking consistency on the whole pool. We then teach the nearest realizable concept and report held-out accuracy against GraNT and random sampling at matched example counts.

The third stage tests expressivity. On CSL and on the triangle and 6-cycle pairs of Breaking the Limits of Message Passing Graph Neural Networks, we verify that the inexpressibility certificates appear and that GIN fails no matter how many examples it receives. We then compute teaching sets relative to 3-WL colors for Ring-GNN. The prediction is that Ring-GNN's larger color space raises its teaching cost on WL-invariant targets relative to GIN, the teaching-side mirror of the generalization trade-off.

Throughout, we report the empirical ratio of recursive teaching cost to $u+1$ on every pool as direct evidence on the recursive-teaching-versus-VC question.