Robot swarms and other mobile multi-agent systems increasingly run learned controllers built from graph neural networks (GNNs, models that compute each agent's output by repeatedly mixing in messages from the agents it can hear). These controllers can only use the communication graph they observe, and that graph changes every fraction of a second as agents move. The robustness theory for these controllers covers only one kind of damage: links that randomly disappear. The static-graph literature points to a worse case. Links that should not exist, such as spoofed transmissions, multipath reflections, or an adversary's rewiring, inject wrong information rather than removing some. Carefully chosen edits are far more destructive than random ones. We propose to measure how badly dynamic swarm controllers fail under spurious and targeted link perturbations. We also propose a defense that each agent runs locally, using only what it already stores.
The defense rests on one observation. In a moving swarm, changing topology is usually treated as a nuisance, but it also supplies a second view of each link. A real neighbor's messages evolve smoothly and follow physics from one time step to the next, and real links persist while agents stay within range. Links that are injected or corrupted tend to appear abruptly and carry messages that do not match what that sender said a moment ago. Each agent can therefore score every incoming link by how well it agrees with that sender's recent history, and down-weight links that disagree. This takes a single forward pass and needs no central coordinator. It does not need the matrix decompositions that current graph-cleaning methods require.
Core Claim
We make two claims. The first is that space-time GNN controllers are much more fragile to spurious link additions and to perturbations aligned with the swarm's state correlations than to the random link drops that current theory analyzes. The second is that a per-link trust weight computed from temporal consistency closes most of that gap at negligible cost. This weight should outperform three alternatives: robustness training alone, robust aggregation, and trust scores computed from a single snapshot.
The closest prior work is Hadou et al. (2023). It bounds the change in a space-time GNN's output when edges of a time-varying graph are dropped independently with probability $1-p$, and it confirms in flocking simulations that cost grows linearly with drop probability. We differ from it in three ways. We study additions and structured perturbations rather than independent drops. We build a defense rather than a bound. And we use the temporal dimension as a source of redundancy rather than as extra perturbation surface.
Research Program
Setting and base model. The testbed is the decentralized flocking task of Tolstaya et al. (2019). There, 100 to 250 point-mass agents learn, by imitating a centralized expert through dataset aggregation, to align velocities without colliding. Communication is limited to a radius, and information travels multiple hops with one step of delay per hop. The controller is the space-time GNN of Hadou et al. (2022). It combines graph shifts with time delays so that multi-hop filtering is physically realizable, and it was shown stable to irregular sampling but analyzed on a fixed graph. We add the 12-agent unlabeled motion-planning task from the same paper as a second task.
Characterizing vulnerability. We define four perturbation families on the time-varying graph, each matched by the number of perturbed edges per step. The first is independent drops, which reproduces Hadou et al.'s regime. The second is independent spurious additions, in which an injected link carries a plausible but false neighbor state. The third is spatially correlated bursts, in which a region's links fail or duplicate together, as under jamming. The fourth is a space-time alignment attack.
The alignment attack extends the distribution-aware attack of Zhang et al. (2025). That work showed that expected worst-case bounds overstate typical harm, and that an edge perturbation is most damaging when it aligns with the second-moment matrix of the node signals. With this principle, their greedy attack cut GCN accuracy on MUTAG from about 70% to about 43%. We estimate the second-moment matrix of agent velocity signals over a sliding window. At each step, we pick the edits within budget that best align with it.
This part of the program motivates the defense. If additions and aligned edits are not markedly worse than drops at equal budget, existing drop-based theory is adequate and the defense is unnecessary.
The defense. Each agent $i$ keeps a short buffer of the last $H$ messages received from each neighbor $j$. From the buffer and a simple kinematic predictor, it forms a one-step forecast $\hat m_{ij}^t$ of what $j$ should send. The predictor is constant velocity over the sampling interval, refined by a small learned residual. Agent $i$ then assigns the trust weight
$$w_{ij}^t = \sigma\!\left(\alpha\,\mathrm{age}_{ij}^t - \beta\,\|m_{ij}^t - \hat m_{ij}^t\|\right),$$
where $m_{ij}^t$ is the received message, $\mathrm{age}_{ij}^t$ is the number of consecutive steps the link has existed, $\sigma$ is the logistic function, and $\alpha,\beta$ are learned. The weights rescale that agent's incoming shift in every filter tap and are renormalized over its neighbors.
This is a local, single-pass version of the idea behind Causal GCN Inference of Feng et al.. That method decides whether to trust neighborhood aggregation by comparing predictions with and without neighbors, using Monte Carlo edge dropping. It raised Citeseer accuracy with 50% misleading edges from 64.2% to 68.6%. The Monte Carlo passes do not fit within a control sampling interval, and a whole-neighborhood trust decision is coarser than we need. We replace both with a per-edge score whose evidence comes from time.
Theory. We extend the Hadou et al. (2023) analysis from drops to additions. A dropped edge changes a normalized shift operator by a bounded amount. A spurious edge's effect grows with the magnitude of the false message it carries, so no drop-style bound controls it. With gating, the added error should scale with the largest weight the gate assigns to edges whose forecast residual exceeds a threshold. The bound would then read roughly as layer-depth-amplified error times the sum of the drop term and that leaked weight times the number of spurious edges. We will check this form empirically by plotting cost against measured leaked weight.
Secondary transfer to decentralized optimization. Decentralized training over directed, time-varying graphs uses Push-Sum (Nedic et al.). In Push-Sum, each node carries a scalar mass $y_i$ beside its parameters $x_i$ and reports the ratio $x_i/y_i$, which cancels imbalances from uneven link weights. Receiver-side down-weighting normally breaks the mass conservation that averaging relies on. If the same trust weight scales both $x$ and $y$, however, the ratio becomes an average weighted toward trusted senders rather than a biased one. In a small pilot, we test this on noisy directed links using the CIFAR-10 setup of Zhou et al. (2024). The main claims do not depend on this pilot.
Baselines
Naive reference points. The unprotected space-time GNN trained on clean graphs shows the damage. The local controller that uses only one hop of information marks the floor below which communication is not worth having. Tolstaya et al. report that one-hop controllers fragment the swarm while three to four hops match the expert, so any defense that effectively shuts off communication should fall toward that floor.
Robustness through training. Here we retrain the same controller with dataset aggregation on graphs perturbed by the same four families. It uses identical expert rollouts, architecture, and number of training episodes, and the perturbation mix is tuned on held-out seeds. This is the strongest simple competitor.
Robust aggregation. Each agent replaces the weighted sum over neighbors with a coordinate-wise median or trimmed mean in every tap. It also needs no history. We found no paper in the file that evaluates it for swarm GNNs.
Spectral stability regularization. SR-GNN from Gao and Isufi (2022) penalizes filter frequency responses away from one so that errors are not amplified across layers. We apply it at training time only, with eigendecompositions computed centrally offline, since a 100-agent graph makes this cheap.
Attention. This is a graph-attention variant of the controller with matched parameter count.
Test-time structural intervention. This is CGI, run with its Monte Carlo passes, reported both at equal accuracy and at equal per-step compute.
Centralized cleaning. As a non-deployable upper reference, Pro-GNN (Jin et al., 2020) is run centrally on each snapshot. It jointly learns a clean adjacency, regularized to be sparse, low-rank, and feature-smooth, together with the GNN weights. On Cora under 25% Metattack it held 69.7% accuracy, against 47.5% for a vanilla GCN, which makes it the strongest reported structure denoiser in the file. It uses a public codebase (Pro-GNN Codebase).
Ablations. The key ablation computes the same gate from the current snapshot only, dropping age and forecast residual. A second ablation assigns random gate weights at matched sparsity.
For flocking cost under spurious additions or aligned attacks, we found no reported result on Lacuna, so the relevant baseline numbers will be produced here. The only quantitative anchor on these tasks is the 0.524 m final target-distance error for the space-time GNN on clean motion planning (Hadou et al., 2022).
What counts as beating the baselines. Averaged over 20 seeds, the gated controller should recover at least half of the cost gap between the unprotected and the centralized Pro-GNN controllers under additions and the alignment attack. It must beat both robustness training and robust aggregation with non-overlapping 95% confidence intervals. And it should keep clean-graph cost within 5% of the unprotected model.
Why not just…?
Why not just train with perturbed graphs? This is the most serious threat. If augmentation alone matches the gate, the temporal mechanism is not needed. Augmentation teaches the filters to be less sensitive on average, but a filter shared across all agents cannot tell which particular link is false at test time. We expect it to trade clean performance for robustness and to fail on an attack not seen in training. The experiment settles this by training on three perturbation families and testing on the held-out fourth, and by also combining augmentation with the gate. If augmentation matches the gate on held-out attacks, we will report that and treat the gate as unnecessary.
Why not just use a median or trimmed mean over neighbors? Robust aggregation is local and cheap. However, flocking agents have few neighbors, often under ten, and the attacker can concentrate on one agent. Median aggregation also throws away legitimate outlying neighbors, such as an agent at the swarm edge. We expect it to raise clean-graph cost and to fail when injected links are a local majority. The equal-budget concentrated attack and the clean-cost comparison will show whether this happens.
Why not rely on attention to ignore bad links? Feng et al. report that attention does not reliably reject misleading structure when supervision is sparse or test patterns are unseen. Jin et al. note that attention scores are computed from the perturbed inputs themselves. The attention baseline tests whether this carries over to swarms, where messages come from moving physical agents.
Why not just bound the damage with stability-regularized filters? Spectral regularization limits how much error grows across layers. It does not stop a spurious edge from contributing a false term in the first place, so it should help against drops and small noise but not against injected messages. Running SR-GNN against each perturbation family measures exactly this distinction.
Proposed Experiments
Check 1: are additions worse than drops? The first decisive check reproduces the linear growth of flocking cost with drop probability reported by Hadou et al. (2023). It then shows, at equal edges per step, how much faster cost and swarm fragmentation grow under additions and under the alignment attack. We measure velocity-variance cost relative to the expert, the fraction of episodes in which the communication graph splits permanently, collisions, and motion-planning final distance error. If additions and aligned edits are no worse than drops, we stop and report that existing theory suffices.
Check 2: does the temporal ingredient matter? The second check is the snapshot-only ablation. If a gate without history performs as well as the temporal gate, time is not the operative ingredient, and the claim reduces to learned edge reweighting.
Check 3: does it scale? The third check trains at 100 agents and tests zero-shot at 250 agents, following Tolstaya et al.'s transfer protocol. We report per-agent memory and compute against CGI.
Check 4: where does it break? The fourth check targets the method's known weakness. An adaptive adversary impersonates a physically consistent phantom agent whose messages are smooth and whose link persists, and its link age is swept upward. We expect the gate's advantage to shrink as the phantom's history lengthens. Reporting where it vanishes defines the method's scope honestly. This result would also motivate the natural next step: cross-checking a sender's claims against what the receiver's other neighbors report about it.
Check 5: transfer to decentralized training. Finally, the Push-Sum pilot reports CIFAR-10 accuracy with noisy directed links for SGP, AWPS, and gated SGP. The only reported reference is AWPS's +3.34% gain over SGP on clean directed graphs (Zhou et al., 2024).
References
- Space-Time Graph Neural Networks with Stochastic Graph Perturbations
- Learning Decentralized Controllers for Robot Swarms with Graph Neural Networks
- Space-Time Graph Neural Networks
- On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective
- Should Graph Convolution Trust Neighbors? A Simple Causal Inference Method
- Distributed Optimization Over Time-Varying Directed Graphs
- Adaptive Weighting Push-SUM for Decentralized Optimization With Statistical Diversity
- Learning Stable Graph Neural Networks via Spectral Regularization
- Graph Structure Learning for Robust Graph Neural Networks