What Do Frozen Graph Encoders Add Beyond Counting Triangles?

Pre-trained graph encoders are usually judged by linear probing. The encoder's weights are frozen, a single linear classifier is fitted on its output vectors, and a high score is read as evidence that the encoder has organized useful structure. For graphs this reading has an obvious hole. A few hundred lines of classical code can compute degree histograms, cycle and clique counts, clustering coefficients and Weisfeiler-Lehman label histograms. No study compares a probed encoder against a linear model on those features at the same probe capacity and the same number of labeled examples. The Weisfeiler-Lehman (WL) histogram records how often each rooted-neighborhood pattern occurs after a few rounds of relabeling.

We propose to measure what a frozen graph encoder contributes on top of cheap hand-crafted features. We measure it as a function of how many labeled graphs the downstream task provides, and with the probe's capacity explicitly controlled. The expected output is a crossover curve for each task: below some number of labels $N^*$ the hand-crafted features win, and above it the embedding pays for itself. We also expect the location of $N^*$ to depend predictably on whether the target is a function of topology or of something topology alone does not reveal.

Core Claim

Current graph probing results mix three effects. The first is information the encoder actually learned. The second is information that a trivial structural summary already contains. The third is extra fitting capacity that a 1024-dimensional input gives a linear head compared with a 16-dimensional one.

Probing Graph Representations trains unconstrained linear probes on frozen GNNs and Graph Transformers pre-trained on PCQM4Mv2. It reports about 0.99 AUC for Transformers versus about 0.80 for GIN on functional groups, and $R^2$ up to 0.87 for radius of gyration. It also reports that randomly initialized GNNs already encode substantial structure. That last finding motivates this proposal. Random wide projections of a graph's local structure are exactly what one would expect to score well if a probe is partly rewarding input dimension and simple structural statistics.

Our claim is that once three conditions hold, the reported gaps shrink and become interpretable. Probe capacity must be matched. Hand-crafted features must be available to the probe as a free baseline. The number of labels must be swept rather than fixed. Concretely, we predict that the Transformer–GIN gap narrows sharply on targets determined by topology, such as ring and functional-group presence or TRIANGLES classes. We also predict that it survives on targets that 2D counts cannot express, such as radius of gyration and bioactivity.

The central quantity is an incremental Pareto gain, built on Pareto Probing: Trading Off Accuracy for Complexity. That paper scores a representation by the area under its accuracy-versus-probe-complexity frontier, called the Pareto hypervolume. Let $h$ be the hand-crafted feature vector of a graph and $z$ the frozen encoder's embedding. Let $\mathrm{PH}_N(x)$ be the Pareto hypervolume of probes on input $x$ trained with $N$ labeled graphs. Probe complexity is measured by the nuclear norm of the probe weight matrix, which is its total singular-value mass, and it is swept over a shared grid. Then

$$\Delta(N) = \mathrm{PH}_N([h; z]) - \mathrm{PH}_N(h),$$

and $N^*$ is the smallest $N$ at which $\Delta(N)$ is reliably positive across seeds. Because the concatenated probe is charged for its full nuclear norm, $z$ cannot win simply by adding parameters.

Research Program

We build a probing harness with four representation families. The first is a tiered hand-crafted vector. The base tier holds the degree histogram, clustering coefficient statistics, and counts of 3- to 8-cycles and 3- and 4-cliques, which is the substructure dictionary of Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting. A second tier adds a hashed WL subtree histogram. A third tier adds pooled characteristic-function signatures from GraphWave (Donnat et al.), which summarizes each node's heat-diffusion profile in linear time and provably gives identical vectors to structurally equivalent nodes.

The second family is frozen pre-trained encoders: GIN, Graphormer and GraphGPS pre-trained on PCQM4Mv2, following the probing setup of Akhondzadeh et al. The third family is the same architectures with random weights. The fourth is a dimension control, in which a random Gaussian lift of $h$ is matched to the dimension of $z$. This isolates whether width alone inflates probe scores, which is the "one-hot" memorization trap Pimentel et al. identified in text.

For each representation we fit probes along the complexity grid in two ways: nuclear-norm-penalized logistic or ridge regression, and hard rank constraints. Pimentel et al.'s label-shuffle test serves as an independent, non-parametric capacity measure. We repeat this at $N \in \{5, 10, 50, 100, 500, 1000, 5000\}$, with many resamples at small $N$.

Following A Non-Linear Structural Probe, we add an RBF-kernel probe with a fixed parameter budget. That work showed kernels recover syntax that linear probes miss without enlarging the parameter count, reaching an 8.44-point gain on Tamil dependency trees. Including the kernel probe lets us tell "GIN lacks the information" apart from "GIN stores it non-linearly." Probes train on cached features, so the full sweep is cheap. Choi reports 9–10 seconds per linear head on cached foundation-model features. We report calibration error alongside accuracy, since that work shows probe calibration varies strongly with the training objective.

Targets fall into two groups by construction. Topological targets are ones the base hand-crafted tier can in principle express: TRIANGLES and ENZYMES classes, ring and functional-group presence, and REDDIT-B. Beyond-topology targets require 3D geometry or chemistry: radius of gyration on PCQM4Mv2, ogbg-molhiv, ZINC solubility, and MoleculeNet tasks.

The analogy that motivates the prediction comes from FLIP. There, frozen protein language models dominate ridge regression when data is scarce and transfer is out of distribution (Spearman 0.77 vs 0.15). Ridge becomes competitive when labels are dense (0.59 on GB1). We expect the graph version to split along our target groups: small or nonexistent $N^*$ for beyond-topology targets, and large $N^*$ for topological ones.

Baselines

The do-nothing reference is a linear probe on the base hand-crafted tier alone, fitted with the same nuclear-norm grid, the same label samples and the same tuning budget as every other probe. $\Delta(N)$ is defined relative to this reference, so it is the bar every encoder must clear. A stronger version of the same competitor is the full hand-crafted stack (counts, WL histogram and GraphWave signatures). We run it identically and report it separately, because a reviewer will rightly insist on the best cheap features rather than the weakest.

The strongest learned representation is the frozen Graph Transformer. Probing Graph Representations reports about 0.99 AUC for its functional-group probes on PCQM4Mv2 and $R^2$ 0.87 for radius of gyration. We reproduce those numbers at full $N$ with unconstrained probes before adding capacity control. That step keeps any shrinkage we find from being an artifact of our own pipeline.

As absolute reference points for what end-to-end models reach, we use the reported results of Bouritsas et al.'s substructure-count network: 0.115 test MAE on ZINC against 0.209 for a plain message-passing network, 0.8039 ROC-AUC on ogbg-molhiv, and parity with a full-data message-passing network at 20% of ZINC. Moment-GNN (Kanatsoulis et al.), which learns substructure counts from random node inputs, reports 0.140 MAE on ZINC and 92.0% on REDDIT-B. Metric Based Few-Shot Graph Classification reports 66.8% (5-shot) and 68.7% (10-shot) average accuracy on the TRIANGLES/ENZYMES suite. On the few-shot suite, a probe beats the strongest existing method only if its accuracy exceeds those figures. On the other benchmarks it only needs to approach them, since those are end-to-end models, not frozen probes. For MoleculeNet sub-tasks we found no reported result on Lacuna.

Two ablations isolate the key ingredient. The random-weight encoder asks whether pre-training, rather than architecture, produces $\Delta(N)$. The dimension-matched random lift of $h$ asks whether width alone produces it. The proposal's claim succeeds if the pre-trained $\Delta(N)$ is positive and exceeds both controls at matched capacity.

Why not just…?

Why not just fit ridge regression on hand-crafted features and skip encoders entirely? This is a real threat, and the design treats it as the null hypothesis rather than a strawman. If the full hand-crafted stack Pareto-dominates every encoder at every $N$ on a target group, that is a publishable negative result about graph pre-training for that group. Ferrara et al. argue that hand-crafted pipelines cannot discover non-linear latent patterns. FLIP's thermostability split, where ridge falls to Spearman 0.15, suggests the argument should hold for targets beyond topology. The beyond-topology group tests exactly this.

Why not just fine-tune the encoder end-to-end? Fine-tuning answers a different question, namely the best achievable accuracy, and at low $N$ it risks overfitting. Hu et al. report GraphSAGE at 94.09% train versus 78.50% test accuracy on ogbn-products. We still run full fine-tuning at each $N$ as an upper reference. If fine-tuning at small $N$ beats hand-crafted probes where frozen probes do not, the encoder's value is in its weights as an initialization rather than in its frozen geometry, and we report that distinction explicitly.

Why not just use an MLP probe? An unconstrained MLP can learn the task itself, which is the failure Pimentel et al. document with one-hot inputs. Instead we place MLP probes on the same complexity plane, with capacity measured by label-shuffle memorization. We also include the fixed-budget kernel probe, which tests non-linear accessibility without buying capacity.

Why not just apply Pareto probing to graph embeddings? Doing so would fix the capacity confound but not the baseline confound. A capacity-controlled probe can still credit an encoder for triangle counts that a four-line script supplies. It would also say nothing about how the answer changes with label budget. The incremental gain $\Delta(N)$, measured over free hand-crafted features along a sweep of $N$, is the specific addition this proposal makes.

Decisive Checks

Three outcomes would settle the claim. First, on topological targets the capacity-matched Transformer–GIN gap from Akhondzadeh et al. should shrink to within seed noise once $h$ is included. If it does not, our reading of that gap is wrong. Second, $N^*$ should be ordered by target group, small for radius of gyration and molhiv and large for TRIANGLES and ring detection. If the two groups show indistinguishable crossovers, the topology-versus-beyond-topology account fails. Third, the random-weight encoder's advantage over the dimension-matched random lift of $h$ should largely vanish under nuclear-norm control. That would show the reported informativeness of random GNNs is mostly a width effect, and it would refine rather than contradict the original finding.