A graph neural ODE treats a node's hidden state as something that flows continuously in time, with the rate of change set by a small network that reads each node's neighbors. The resulting trajectories are handled by a numerical integrator, the routine that steps a differential equation forward in time. Such an integrator may evaluate that network dozens of times per prediction, and every evaluation touches every edge of the graph. Graph compression methods already shrink graphs for ordinary layered graph networks. They merge nodes that behave identically, or replace the graph with a few synthetic nodes. But they are tuned to preserve a fixed number of message-passing steps. Nobody has asked whether a compressed graph stays faithful when states are integrated for a long time, where small mismatches can compound.
This note proposes that the right unit of compression for continuous-time graph models is the whole trajectory, not the single forward pass. The approach borrows "lumping" from the theory of differential equations: some groups of variables provably evolve together, so they can be replaced by one variable per group without error. The note then asks how far lumping can be relaxed while keeping a controlled error. The practical payoff is a graph ODE that is integrated on a graph tens of times smaller, together with a certificate saying how long its predictions remain close to the full model's.
Core Claim
Let $H(t) \in \mathbb{R}^{n \times d}$ be the node states of a graph ODE $\dot H = F(\hat A, H)$, where $\hat A$ is the normalized adjacency matrix and $F$ applies a shared neural map to aggregated neighbor states, as in the graph convolutional differential equations of Graph Neural Ordinary Differential Equations. Let $P \in \{0,1\}^{n \times m}$ assign each of the $n$ nodes to one of $m \ll n$ groups. The partition is exactly lumpable when $\hat A P = P B$ for some $m \times m$ matrix $B$, meaning every node in a group sends the same total weight into each other group.
When the partition is exactly lumpable and the initial states satisfy $H(0) = P Z(0)$, uniqueness of ODE solutions forces $H(t) = P Z(t)$ for all $t$. Here $Z(t)$ solves the small system $\dot Z = F(B, Z)$. This settles, for the exact case, the open worry raised about compression built from $H(0)$: equivalence holds for the entire trajectory, not just a few layers. It also holds for any integrator, any step size, and any weights.
For approximate partitions, define the lifting residual $\delta = \sup_t \lVert F(\hat A, P Z(t)) - P F(B, Z(t)) \rVert$, and let $L$ be the Lipschitz constant of $F$ in $H$. Grönwall's inequality, the standard bound on how perturbations of an ODE grow, then gives
$$\lVert H(t) - P Z(t) \rVert \le \frac{\delta}{L}\left(e^{Lt} - 1\right).$$
Two consequences follow, and both can be tested. First, a compression should be fitted to minimize $\delta$ along the trajectory, not the one-pass propagation error that Serving Graph Compression for Graph Neural Networks minimizes. Second, the exponential factor means compression error and the stability of the learned vector field interact. Vector fields that are constrained to be non-expansive should tolerate much coarser graphs. One example is the anti-symmetric weights of the stable variant in CSG-ODE: ControlSynth Graph ODE For Modeling Complex Evolution of Dynamic Graphs, which make the effective growth rate near zero. The claim, then, is a compression method for graph ODEs that comes with a trajectory-level error bound, plus the empirical finding that bounded-growth dynamics are what make aggressive compression possible.
Research Program
The work builds three things.
The first is an exact lumper. It computes the coarsest partition that is lumpable and consistent with the node features, by iterating color refinement to a fixed point. It then integrates the reduced system with the aggregation counts stored in a small table. This is the continuous-time analogue of the structural merging and memoization table in Inference-friendly Graph Compression for Graph Neural Networks. That paper proves equivalence only for $L$-layer discrete networks; we extend it to all integration times and to adaptive solvers.
The second is an approximate lumper. Starting from degree-weighted k-means over node states, as VNG does, it fits $B$ and the group assignments by minimizing the lifting residual averaged over states sampled along training trajectories. The trajectory samples come from the solver itself, at points chosen by the integrator of Neural Ordinary Differential Equations. Compression and model training alternate: the vector field is trained on the full graph, the lumping is fitted to its trajectories, and a short fine-tuning pass runs on the reduced system.
The third is adaptive refinement. The residual can be estimated cheaply at solver steps by lifting $Z$ and evaluating $F$ on a sampled subset of original edges. When the accumulated bound crosses a tolerance, the group with the largest residual is split. This turns the Grönwall bound from a passive guarantee into a control signal.
Supporting streaming edge updates through compressed dynamic structures such as C-trees (Low-Latency Graph Streaming Using Compressed Purely-Functional Trees) is a natural follow-up, because an edge insertion only invalidates the groups of its endpoints. We treat it as out of scope, so the core claim can be tested cleanly on static topologies.
Baselines
The naive reference point is the uncompressed graph ODE: GCDE with a fourth-order Runge-Kutta solver on node classification, and GCDE-GRU on traffic with missing data. Both are re-trained under our pipeline with the same hidden size and solver tolerance. Every compressed method is scored against it on accuracy or error, and on edges touched per prediction, wall-clock time and peak memory. The reported numbers to match are 83.8% accuracy on Cora for GCDE-rk4 and RMSE 10.95 on PeMS with 70% of readings missing for GCDE-GRU, both from Graph Neural Ordinary Differential Equations. On the synthetic Springs dataset, the strongest continuous-time model in the file is CSG-ODE, at extrapolation MSE 0.1550 with 40% of points observed, from CSG-ODE. We run it on the full graph as the accuracy ceiling for dynamics tasks.
The strongest compression competitor is VNG from Serving Graph Compression for Graph Neural Networks, applied directly to the graph ODE. It builds virtual nodes and a low-rank virtual adjacency matrix that minimize the error of one forward propagation, and we then integrate the ODE on that virtual graph. It is the strongest competitor because it is the best reported learned compression on the same large benchmarks. It reaches ratios of 37.5× on ogbn-arxiv, 41.1× on Reddit and 69.1× on ogbn-products, and keeps about 91% accuracy on Reddit with 5% of nodes, where random dropping falls to 70–80%. VNG and our method will use the same number of groups, the same vector field weights, the same solver, and the same hyperparameter search budget.
The exact-merging competitor is ExGIS-style structural merging from Inference-friendly Graph Compression for Graph Neural Networks, computed with its $L$-layer equivalence criterion and then integrated. It reports 92.4% node compression with 100% accuracy retention on the Elliptic Bitcoin transaction graph for discrete networks. If its $L$-layer partition is coarser than our trajectory-exact partition, it should visibly break under long integration.
Random node dropping at matched size is the cheap floor.
Two ablations isolate the key ingredient. The first swaps our trajectory-averaged residual for VNG's one-pass objective while keeping everything else fixed. The second varies the stability of the vector field, comparing unconstrained weights with anti-symmetric ones, at each compression ratio. Beating VNG means one of two things: equal accuracy at a compression ratio at least twice as high, or a measurably smaller gap to the full model at matched ratio that persists over long horizons.
Why not just…?
Why not just run VNG unchanged on the graph ODE? This is the real threat. If the one-pass objective already keeps $\delta$ small along trajectories, our method adds nothing. The bound predicts that VNG's error should grow with integration time much faster than ours, and faster still for unconstrained vector fields. The prediction does not hold for short integration intervals, where one step dominates. We will report error against integration horizon for both methods. If the curves coincide, we will say so and recast the contribution as a certificate for VNG rather than a replacement.
Why not just bin time and run a discrete network on an already-compressed graph? Continuous models behave clearly better under irregular sampling and long rollouts. On a multi-agent physics task at 50 steps, the GDE's MAPE is 73.75 against 668.47 for a non-graph baseline (Graph Neural Ordinary Differential Equations). The file does not report binned discrete graph networks at scale on these tasks. We will therefore include a time-binned GCN on the VNG-compressed PeMS and Springs graphs, with matched compute, to show whether keeping the ODE is worth its cost.
Why not just cut solver cost with a cheap fixed-step integrator or neighbor sampling on the full graph? Fewer function evaluations attack the time factor. Compression attacks the per-evaluation factor, and the two combine. CSG-ODE's report of more than 70% extra runtime from the adaptive Dopri5 solver on only 170 nodes shows that the time factor matters. But a cheaper solver still touches every edge and keeps the full graph in memory. On Reddit, that graph is over 460MB against 7.6MB of model weights (Serving Graph Compression for Graph Neural Networks). We will compare three settings at equal wall-clock budget: a fixed-step solver on the full graph, the adaptive solver on the lumped graph, and both combined.
Proposed Experiments
The first decisive check tests exactness. On Cora and Elliptic, the trajectory-exact lumper must reproduce full-graph GCDE outputs to numerical precision at every integration time. The compression ratio it achieves is itself the finding, since Elliptic reports 92.4% for the discrete criterion. The ExGIS $L$-layer partition should diverge once integration exceeds the depth it was built for.
The second tests the bound. On Springs and on the multi-agent synthetic task, we plot measured error $\lVert H(t) - PZ(t)\rVert$ against the Grönwall prediction across compression ratios and horizons. We then check whether anti-symmetric vector fields flatten the growth as predicted.
The third tests scale. On ogbn-arxiv, Reddit and ogbn-products, we train a GCDE on the full graph and report accuracy, edges touched per solve, peak memory and time at VNG's reported ratios and at twice those ratios, for all baselines. The file lists no reported result for graph ODEs on ogbn-papers100M, and no reported number for ExGIS latency there. Running the reduced system at that size, where the full ODE may not fit in memory, is therefore a stretch goal rather than a comparison.
The fourth tests refinement. On PeMS with 70% missing data, we start from an aggressive partition and let residual-triggered splitting grow it. We count how many groups are needed to recover within 0.1 RMSE of the full model's 10.95.
The proposal fails if VNG matches our accuracy-versus-horizon curves at equal ratio. It also fails if, on the dynamics tasks, the approximate lumper cannot beat random dropping by a margin comparable to VNG's reported 91% versus 70–80% gap on Reddit.
References
- Graph Neural Ordinary Differential Equations
- Serving Graph Compression for Graph Neural Networks
- CSG-ODE: ControlSynth Graph ODE For Modeling Complex Evolution of Dynamic Graphs
- Inference-friendly Graph Compression for Graph Neural Networks
- Neural Ordinary Differential Equations
- Low-latency graph streaming using compressed purely-functional trees