Elected Hubs: Long-Range Coordination for Large Agent Networks Without All-to-All Messaging

When hundreds of learning agents share a physical network, such as traffic lights across a city, each agent can usually talk only to its immediate neighbors. That keeps communication cheap, but it makes the system blind to distant events. A jam forming twenty blocks away reaches an intersection only after it has already arrived. The obvious fix is to let every agent hear every other agent, but message and compute cost then grow with the square of the number of agents. We propose a middle path borrowed from scalable graph learning. A small, changing set of agents is elected at runtime as temporary "hubs." Every other agent reports a compressed summary to one hub, the hubs exchange summaries among themselves, and each hub sends a digest back to its members. Information can then travel between any two agents in two virtual hops, while each agent sends and receives a constant number of messages per step.

The new element is that the hub structure is an organization the agents maintain. It is not a fixed preprocessing step. Hubs are elected, retired, and reassigned as demand shifts or agents fail. Each change goes through an explicit test of whether the expected gain outweighs the cost of changing. Changes are applied incrementally, so the structure is never rebuilt from scratch. In plain terms, the claim is this: under non-stationary conditions, a dynamically re-elected hub layer beats both purely local communication and a fixed partition computed once from the road map, at roughly linear communication cost.

What exists, and the gap this fills

The closest work is Bayesian Ego-graph Inference for Networked Multi-Agent Reinforcement Learning (BayesG). Each agent learns a stochastic mask that decides which of its physical neighbors to listen to, trained by variational inference with a sparsity prior. It scales to the 167-intersection NewYork167 traffic map, where unpruned neighbor communication baselines plateau. BayesG motivates this proposal because it shows that adapting the communication structure matters at scale. It also defines the gap. BayesG can only remove edges within the fixed one-hop physical neighborhood, so it can never create a long-range link.

The mechanism comes from Bridging Indexing Structure and Graph Learning: Expressive and Scalable Graph Neural Network via Core-Fringe (CFGNN). CFGNN splits a static graph into dense "core" nodes and "fringe" nodes, then routes messages fringe-to-core and back. This yields a two-hop cover, meaning any node can reach any other through at most one core in between, which gives a global receptive field on one GPU. CFGNN is a graph-learning method on fixed graphs, with no agents, rewards, or reorganization. We reuse its routing pattern, but the cores become agents chosen by a learned, reward-driven process that changes over time.

Two lines of work supply how the structure is maintained. Adapting to Evolving Graphs: A Scalable Framework for Dynamic Coarsening shows that incrementally reassigning nodes when the graph drifts (its ACNR algorithm) is 10–20x faster than recomputing from scratch and retains 98–99% of downstream accuracy. It also reports a temporal-smoothing benefit. We adopt its incremental-reassignment idea for hub membership. Rational Multiagent Organization and Reorganization frames reorganization as acting only when the expected utility gain exceeds the reorganization cost. An Approach to Analyzing the Need for Meta-Level shows analytically and in sensor-network simulation that dynamic restructuring can hurt when its coordination overhead exceeds its benefit. These two papers constrain our design: a hub layer that reshuffles constantly should lose.

That rational-reorganization work was validated on tens of agents with hand-built decision networks. We replace the hand-built models with learned value estimates.

Other related work is adjacent but does not cover this case. Cooperative Multi-Agent Reinforcement Learning with Hypergraph Convolution learns dynamic group relations through dense hypergraph operations, which are tested only up to about 57 units. CARD: Towards Conditional Design of Multi-agent Topological Structures generates condition-aware communication graphs for small language-model agent teams. Neither bounds per-agent communication on networks of hundreds of agents.

The systems motivation comes from Scalability Bottlenecks in Multi-Agent Reinforcement Learning Systems. It reports that MASAC training time grows from about 1.2 hours at 3 agents to over 131 hours at 48 agents, and that mini-batch sampling over joint states consumes about 61% of update time. Any design that lets every agent attend to every other inherits this growth.

Core Claim

We make three claims. First, an elected hub layer gives each agent information from the whole network at a per-step message count of about $2N + C^2$, where $N$ is the number of agents and $C$ the number of hubs. That count comes from $N$ uplinks, $C^2$ hub-to-hub exchanges, and $N$ downlinks. With $C$ on the order of $\sqrt{N}$, the total is linear in $N$, compared with $N^2$ for all-to-all communication.

Second, the advantage over a fixed partition appears specifically when traffic demand moves or agents fail.

Third, gating changes by gain minus switching cost is necessary. Without it, hub churn erases the benefit, which is the failure mode that the meta-level analysis predicts.

Research Program

Each agent runs a local policy and is trained with centralized critics and decentralized execution, matching BayesG's networked actor-critic setup so that comparisons are direct.

Each agent computes a scalar "hubness" score from its local state, its load, and a learned embedding. The top $C$ agents by score, subject to a minimum spacing on the road graph, are hubs. Every other agent assigns itself to one hub through a Gumbel-softmax choice over a candidate set. The candidates are the nearest few hubs by road distance plus its current hub. This makes assignment trainable in the same way BayesG trains its masks.

Fringe agents send a compressed vector to their hub. Hubs run one round of attention among themselves, then return a per-member digest. Each agent's policy receives its own observation, its BayesG-style masked local messages, and this hub digest.

Reorganization is event-driven. Each period, a hub-layer critic estimates the value of the current hub structure and of a few candidate edits. The candidate edits are promoting an agent to hub, retiring a hub, and moving individual members whose assignment quality has drifted beyond a threshold, in the manner of ACNR. An edit is applied only if

$$\hat{V}(\text{edited}) - \hat{V}(\text{current}) > \lambda \, c(\text{edit}),$$

where $\hat{V}$ is the critic's estimate of discounted return, $c(\text{edit})$ counts the extra messages and agents whose state must be resynchronized, and $\lambda$ converts message cost into reward units. We sweep $\lambda$, which traces a curve of return against communication.

The analysis has three parts. We measure total messages and wall-clock time per step against $N$. We measure hub churn over time. We also check whether hubs track demand hotspots, which tests whether the learned structure is interpretable rather than arbitrary.

Baselines

The naive reference point is BayesG's own lower end: independently learning signal agents with no communication, plus the fixed-time signal plan that SUMO scenarios ship with. Any communication scheme must clear these.

The strongest existing method is BayesG (Bayesian Ego-graph Inference for Networked Multi-Agent Reinforcement Learning). It is the best published adaptive-topology method on exactly these maps. The file reports no numeric return: there is no reported result on Lacuna for BayesG's return on NewYork167, only that it reached "significantly higher returns" while other methods plateaued. We will therefore rerun BayesG from its released configuration on all maps under our seeds, with the same environment steps, network widths, and hyperparameter search budget as our method. Our hub layer is added on top of BayesG's local masking, so the comparison isolates the long-range channel. Beating BayesG means a higher mean episode return and lower average vehicle delay on NewYork51 and NewYork167, with non-overlapping 95% intervals across at least five seeds, at no more than twice BayesG's per-step message count.

The key ablation is a static hub layer. We compute cores once from the road graph using CFGNN's hub-labeling selection (Bridging Indexing Structure and Graph Learning: Expressive and Scalable Graph Neural Network via Core-Fringe), assign members by road distance, and train the same policy and digest networks. This differs from our method only in that the organization never changes. A second ablation removes the cost gate, setting $\lambda = 0$ and recomputing hubs and assignments from scratch every period. This tests whether incremental, cost-aware maintenance matters.

We add two reference points. One is a single global hub, essentially a mean-field summary broadcast to all agents. The other is full all-to-all attention, run on maps small enough to fit, as an approximate upper bound on what long-range information can buy.

All methods share compute, environment steps, and tuning trials. Message counts are reported alongside returns so that no method wins by simply communicating more.

Why not just…?

Why not just give BayesG a two- or three-hop neighborhood? Widening the radius is the most direct extension, and it is a real competitor on small grids. But the neighborhood size grows with degree raised to the number of hops. On a Manhattan-style grid, a three-hop neighborhood is still local relative to a 167-node map, while its message count already exceeds our hub layer's. We will run BayesG at one, two, and three hops on NewYork167 and plot return against messages. The claim fails if any radius lies on or above our curve.

Why not just partition the road network once and fix the leaders? This is the most serious threat, because the road graph never changes. If demand is stationary, a fixed partition may do as well. The static hub ablation tests exactly this, under three regimes. The first is stationary demand. The second is a mid-episode origin-destination shift that mimics rush-hour reversal. The third disables 10% of intersections as fixed-time controllers to simulate agent failure. Both demand changes are scenario modifications we build in SUMO. We expect parity in the stationary regime and a gap only in the shifted and failure regimes. If the gap does not appear, the dynamic-organization claim is wrong and we will report it.

Why not just broadcast one global summary to everyone? A single pooled vector is cheap and gives every agent some global context. Its weakness is that one summary must serve agents with very different needs, such as downtown and outer-borough signals. The single-hub baseline is the $C = 1$ endpoint of our hub-count sweep. If return does not improve as $C$ grows beyond 1, regional structure is not needed.

Why not just recompute the clustering from scratch periodically? The dynamic-coarsening results (Adapting to Evolving Graphs: A Scalable Framework for Dynamic Coarsening) report 10–20x speedups and a smoothing benefit from incremental updates on data graphs. For agents there is an additional cost. Each reassignment forces policies to adapt to a new digest source. The no-gate ablation measures churn and return directly. The meta-level analysis (An Approach to Analyzing the Need for Meta-Level) predicts it loses once churn is high.

Proposed Experiments

The main testbed is BayesG's SUMO suite: ATSC_Grid (25 agents), Monaco (28), and NewYork33, NewYork51, and NewYork167. Each is run under the stationary, demand-shift, and failure regimes. Metrics are episode return, average vehicle delay and queue length, per-step messages, hub churn per hour of simulated time, and wall-clock time per training step.

The first decisive check is the regime interaction. Our method should beat the static hub layer under demand shift and failure, with the gap growing from NewYork33 to NewYork167, while roughly matching it under stationary demand.

The second check is the $\lambda$ sweep. Too small a $\lambda$ should increase churn and lower return, and too large a $\lambda$ should freeze the structure into the static baseline. An interior optimum would confirm that gain-minus-cost gating is doing the work.

The third check is a scaling test on the Multi-Agent Particle Environment from 3 to 48 agents and beyond. We compare training time and memory against the profile reported in Scalability Bottlenecks in Multi-Agent Reinforcement Learning Systems (MASAC: 4,335 s at 3 agents to 474,027 s at 48 agents). The prediction is near-linear growth in message volume and per-step time for the hub layer. All-to-all attention should show super-linear growth on the same hardware.