Graph-Agnostic Strong Lottery Tickets for Stable, Transferable Graph Filters

A graph neural network that runs a polynomial graph filter (a weighted sum of powers of the graph's normalized adjacency matrix) has a fixed set of weights on each power. Its frequency response, meaning how strongly it passes smooth versus rapidly varying signals over the graph, is a polynomial whose coefficients are exactly those weights. So when we prune such a network, deciding which weights survive also decides how sharp each filter's frequency response is. Sharpness is what separates a filter that can tell apart fine structural detail from one that stays stable when edges are perturbed, and that keeps working when the graph grows. Pruning is therefore an implicit choice on the stability-discriminability trade-off, yet the pruning literature never measures it, and the graph-filter literature never asks what pruning does to it.

This note proposes to make that choice explicit, in two parts. The first is a theorem. A randomly initialized graph-filter network only logarithmically wider than a target network contains an untrained subnetwork that matches the target on every graph at once. That subnetwork inherits the target's stability constant and its size-transferability rate, up to a controlled error. The second is an empirical test. On citation and recommendation graphs, we ask whether standard data-driven pruning pushes filters toward unstable, high-order responses that transfer badly across graph sizes. We also ask whether a mask search constrained by a stability penalty, run under degree-aware weight rescaling, removes the damage at the same sparsity.

Core Claim

Existing strong lottery ticket results for graph networks are tied to a fixed, finite dataset. Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win proves that random GNNs contain sparse subnetworks preserving 1-Weisfeiler-Leman separation of a given set of graphs. A Unifying Relational Perspective on Expressive Lottery Tickets extends this to relational and temporal GNNs, again over fixed datasets, and lists the population or graph-limit version as open. Our observation is that a dataset is unnecessary if the ticket is built on the filter coefficients rather than on graph-specific computations.

Consider a layer $X_{\ell+1} = \sigma\big(\sum_{k=0}^{K} S^k X_\ell H_{\ell,k}\big)$. Here $S$ is the normalized graph shift with spectral norm at most one, $X_\ell$ the node features, $H_{\ell,k}$ the weight matrix on the $k$-th power, and $\sigma$ a pointwise nonlinearity. The weights never depend on the graph. A subset-sum approximation of each entry of $H_{\ell,k}$ is therefore an approximation that holds for every $S$ simultaneously, including samples of any graphon and, because the layer is pure message passing, sparse graph sequences under graphop limits.

Stability is the delicate part. Following Stability of Graph Neural Networks to Relative Perturbations, a scalar filter $h(\lambda)=\sum_k h_k\lambda^k$ is integral Lipschitz with constant $C$ when $|\lambda h'(\lambda)| \le C$ on the spectrum. This condition is what bounds the output change by $\mathcal{O}(\epsilon)$ under relative edge perturbations of size $\epsilon$. If each coefficient is approximated to within $\delta$, then for $|\lambda|\le 1$

$$|\Delta h(\lambda)| \le (K+1)\delta, \qquad |\lambda\,\Delta h'(\lambda)| \le \tfrac{K(K+1)}{2}\,\delta .$$

The response error grows linearly in the filter order $K$. The stability-constant error grows quadratically. Because subset sum reaches accuracy $\delta$ with $\mathcal{O}(\log(1/\delta))$ random weights per target weight (Optimal Lottery Tickets via Subset Sum: Logarithmic Over-Parameterization is Sufficient), the $K^2$ cost lands inside a logarithm.

We aim to prove the following. A random network of width $\mathcal{O}\big(d\log(dLK/\epsilon)\big)$ and depth $2L$ contains, with high probability, a subnetwork that is within $\epsilon$ of any width-$d$, depth-$L$ target on every graph with $\|S\|\le 1$. That subnetwork's per-filter integral Lipschitz constants exceed the target's by at most $\epsilon$. The extra depth consists of pointwise layers that apply no graph shift. Combining this with the $\mathcal{O}(n^{-1/2})$ transfer bound of Graphon Neural Networks and the Transferability of Graph Neural Networks, the ticket's error between an $n$-node sampled graph and the graphon limit becomes the target's transfer error plus $2\epsilon$. On sparse sequences, the same combination with the bound of Limits, approximation and size transferability for GNNs on sparse graphs via graphops applies.

The empirical half of the claim is falsifiable. Data-driven pruning applied to a trained or random graph-filter network on a small graph tends to keep high-order taps, which raises the measured integral Lipschitz constant and enlarges the transfer gap. Searching for masks under an explicit stability penalty closes that gap at matched sparsity.

How This Sits Against Prior Work

Two papers supply the motivation by connecting pruning to graph limits. Pruning at Initialisation through the lens of Graphon Limit shows that pruning masks converge to bipartite graphons, and that data-driven criteria carve out a heterogeneous "dense core". The Graphon Limit Hypothesis shows that such criteria concentrate neural-tangent-kernel energy in the top eigenvalues. Both treat the mask itself as the graph and stay within MLPs. Neither asks what pruning does to the frequency response of filters running on a data graph, which is our object. Their finding that SNIP-like masks concentrate weight in a few components is what makes us expect high-order taps to survive selectively.

Three papers supply the transfer and stability machinery: the graphon transferability paper above, the graphop paper, and Size Transferability of Graph Convolutional Networks across Sparsity. The last identifies "architectural amplification", where width and depth multiply transfer error. This is the reason a ticket construction that doubles depth needs care: our pointwise intermediate layers add Lipschitz factors but no graph-shift error, and we must verify that amplification stays inside the logarithm.

Two results constrain the design. The graphop paper notes that the spectral gap is not continuous under action convergence, so we state all sparse-graph claims for polynomial, message-passing filters and avoid eigendecomposition-based ones. Graph Neural Networks Are Not Continuous Across Graph Resolutions warns that GNNs need not be continuous under every natural mode of convergence. Our theorem inherits transferability from the target and does not create it, and we say so in the claim.

Two works supply the nonlinearity side. Discriminability of Single-Layer Graph Neural Networks shows that pointwise nonlinearities shift high-frequency content to low frequencies, letting stable filters recover discriminability. Most Activation Functions Can Win the Lottery Without Excessive Depth shows that the subset-sum construction extends to tanh. That matters because tanh is the activation for which nonlinear frequency mixing is certified.

Finally, initialization. Gradient Flow in Sparse Neural Networks and How Lottery Tickets Win shows that heterogeneous per-neuron fan-in is what breaks training of sparse networks, and that rescaling each neuron by its own incoming degree fixes it. Robust Pruning at Initialization gives the global $1/\sqrt{p}$ rescaling, where $p$ is the fraction of weights kept, that returns pruned networks to the edge of chaos. It also flags graph convolutions as uncovered. In a graph-filter layer, a neuron's fan-in is spread across $K+1$ taps, and a mask can keep many order-zero taps and few order-$K$ taps for the same neuron. We use per-neuron, per-tap rescaling during mask search, and test whether it matters.

Research Program

The theoretical work has three pieces. We first prove the uniform-over-graphs ticket theorem for ReLU and tanh, tracking the constants in $K$ and $L$ explicitly. We then prove the stability-inheritance corollary for both relative perturbations and graphon or graphop transfer. Third, we derive a lower bound by adapting the $\Omega(d\log(1/\epsilon))$ argument of the subset-sum paper. The goal is to show that requiring the guarantee on all graphs, rather than on a finite dataset, costs only the $\log K$ factor. A finite dataset of $N$ graphs should need $\log N$ where we need $\log K$, a comparison worth stating precisely against the probability bound in the relational ticket paper.

The empirical work builds a mask search for polynomial graph-filter networks. Scores are learned on frozen random weights, as in score-based untrained-ticket methods. The loss adds a penalty equal to the largest value of $|\lambda h'(\lambda)|$ over $[-1,1]$ for each induced scalar filter. Because the induced filter is a polynomial, this penalty is computed in closed form from the masked coefficients, at no cost in graph size. Surviving weights are rescaled per neuron and per tap by their kept fraction. For validation at toy scale, we solve the exact mixed-integer program used in the subset-sum paper on one- and two-layer filter networks, checking that the gradient-based search reaches the predicted error-versus-width curve.

As a diagnostic, for every pruned model in every experiment we report three quantities computed from its taps: the per-filter integral Lipschitz constant, the energy share of taps of order above one, and the transfer gap.

Baselines

The naive reference point is a dense polynomial-filter GNN of the same order $K$, trained once on a small subgraph and evaluated on the full graph without any stability control. For Cora, Graphon Neural Networks and the Transferability of Graph Neural Networks reports a relative accuracy difference of 23.1% when training on 271 nodes and transferring to 2,708 nodes, and 15.4% when training on 1,354 nodes. Our reimplementation must reproduce these numbers within noise before any comparison counts.

The strongest existing competitor is a dense network trained with the integral Lipschitz penalty of Stability of Graph Neural Networks to Relative Perturbations, using the paper's $\mu=0.5$ and tuned further. It is then magnitude-pruned to the target sparsity and fine-tuned with the per-neuron rescaling of the gradient-flow paper. This pipeline gets stability from training rather than from selection, and it is the most direct threat to any claim that ticket search adds something. The file reports only qualitative results for this method on MovieLens-100k, described as significantly lower RMSE differences under perturbation, with no reported number found on Lacuna. We therefore establish its numbers ourselves under the shared protocol.

The other pruning baselines are SNIP, GraSP, SynFlow, random pruning with $1/\sqrt{p}$ rescaling as in Robust Pruning at Initialization, and iterative magnitude pruning, all applied to the same graph-filter architecture. On TUDataset, the expressive-ticket work reports that GIN matches dense accuracy at 80% sparsity, with no per-dataset numbers found on Lacuna. We run GIN-style and polynomial-filter variants ourselves.

Two ablations isolate the key ingredients. The first removes the stability penalty from the mask search. The second replaces per-neuron, per-tap rescaling with global $1/\sqrt{p}$.

Fairness rules apply to every method. All methods see the same training subgraphs and splits, the same total gradient steps counting both mask-score steps and weight steps, the same $K$, and the same hyperparameter budget of 30 trials per method. The ticket method's frozen network is wider, so we report parameter count, nonzero count, and FLOPs side by side.

Beating the strongest competitor means one of two things at equal nonzero count: a strictly smaller transfer gap with no loss of full-graph accuracy, or matching gap and accuracy with the stability constant certified by construction rather than estimated after training. If the penalized-dense-then-prune pipeline matches us on all three diagnostics, we report that ticket search has no practical advantage. The remaining contribution is then the theorem and the pruning diagnosis.

Why not just…?

Why not just train a dense GNN with a stability penalty and prune it afterward? This is the real threat, and it is the strongest baseline above. Pruning after training can still remove the low-order taps that carry a filter's smooth part, which raises the stability constant after the penalty was enforced. Fine-tuning may or may not repair this. The diagnostic directly measures whether the stability constant rises between the penalized dense model and its pruned version. If it does not, this alternative wins on practice and we say so.

Why not just use first-order filters, as in a plain graph convolutional network, which are stable by construction? A first-order filter is smooth but cannot resolve high-frequency structure. Discriminability of Single-Layer Graph Neural Networks shows that even with nonlinear mixing, a linear filter bank's MSE on high-frequency signals is about 57% higher than a GNN's on synthetic geometric random graphs. We include the $K=1$ model on that synthetic task and on the transfer benchmarks. If it ties on Cora transfer but loses on the high-frequency task, that places the trade-off where theory predicts.

Why not just rely on degree normalization or the generalized-graphon convolution for transfer, and ignore pruning? Normalization fixes the operator, not the filter. The size-transferability-across-sparsity paper shows that depth and width amplify residual transfer error. We run its stretched-graphon convolution as the operator inside every method, so any gain we report is on top of it rather than instead of it.

Why not just use global $1/\sqrt{p}$ rescaling? It assumes uniform fan-in. The gradient-flow paper reports that per-neuron rescaling lifts sparse VGG16 on ImageNet from 51.81% to 62.52% top-1, but in a non-graph setting. Our rescaling ablation tests whether tap-level heterogeneity matters in graph filters. If it does not, we drop the component.

Proposed Experiments

The first experiment checks the theorem. On stochastic block models and smooth graphons, we fix a target filter network and sweep the width of the random network. We measure the best mask's worst-case output error over graph samples of sizes 100 to 10,000. The prediction is that error falls roughly exponentially in width per target weight, with the same width working at every graph size. The ticket's transfer gap should then follow the target's $n^{-1/2}$ slope, offset by about $2\epsilon$. On polymer-like sparse sequences, the graphop paper observed empirical decay of $\mathcal{O}(n^{-1})$, and we test whether tickets inherit the faster rate.

The second experiment is the pruning diagnosis, which is decisive. On Cora, Pubmed, and ogbn-arxiv, we train on subgraphs of 10% and 50% of the nodes and evaluate on the full graph, at sparsities of 80%, 95%, and 99%. If data-driven criteria raise the high-order tap energy and the stability constant, and the transfer gap tracks these quantities across methods, the core mechanism is confirmed. If the transfer gap is uncorrelated with the measured stability constant, the premise fails and the proposal reduces to its theory.

The third experiment covers perturbation and discriminability together. On MovieLens-100k, we measure RMSE change under relative edge perturbations of increasing size. On the synthetic geometric random graphs of the discriminability paper, we measure high-frequency MSE. A method that wins on MovieLens by flattening filters but loses on the synthetic task has only moved along the trade-off. The claim requires matching the dense penalized model on both at equal nonzero count.