When multiple agents operate in a shared environment—whether they are autonomous vehicles navigating a busy intersection, robots coordinating in a warehouse, or base stations optimizing power consumption—they face a fundamental representation problem. Traditional multi-agent reinforcement learning (MARL) and trajectory forecasting models often treat the state space as a flat vector of absolute coordinates or concatenated local observations. This approach scales poorly: as the number of agents grows, the state space explodes combinatorially, and the model struggles to discern which pieces of information are actually relevant to coordination.
To solve this, a powerful paradigm has emerged: representing multi-agent systems as dynamic graphs. Instead of a flat vector, the environment is modeled as a network where nodes represent individual agents (or static entities like lanes and traffic signals) and edges represent their spatial, social, or functional relationships. By processing this graph structure with Graph Neural Networks (GNNs), systems can explicitly reason about the topology of interactions, building an intuitive and scalable foundation for collective behavior.
The Power of Relational Inductive Biases
Why does a graph structure work so much better than a flat input representation? The answer lies in relational inductive biases. In most multi-agent tasks, an agent's decision depends heavily on its relative constellation to its neighbors rather than its absolute position in the world.
Heechang Ryu et al. demonstrated in Multi-Agent Actor-Critic with Hierarchical Graph Attention Network that structuring agent interactions through relational biases significantly outperforms flat representations, enabling remarkable zero-shot transferability to environments with far more agents. By abstracting the scene into a graph, models can focus entirely on relative formations and coordination patterns. For instance, Yuhang Jiang et al. leveraged this in SPD: Synergy Pattern Diversifying Oriented Unsupervised Multi-agent Reinforcement Learning to learn complex coordination skills—like spatial formations—without any external reward signals, purely by maximizing the diversity of the underlying interaction graphs.
Furthermore, this abstraction allows models to ignore irrelevant geographic details. As noted by Maximilian Zipfl et al. in Traffic Scene Similarity: a Graph-based Contrastive Learning Approach, representing scenes as graphs allows a system to evaluate the structural constellation of participants (such as path intersections or spatial orientations) rather than absolute coordinates, making it possible to map complex multi-agent behaviors into a low-dimensional, generalizable embedding space.
Localized Message Passing and Scalable Communication
In decentralized multi-agent systems, communication is a major bottleneck. Agents cannot simply broadcast their entire high-dimensional local observations to every other agent without overwhelming the network bandwidth.
Graph-based architectures solve this through localized message passing. In a communication graph, edges define the pathways through which information flows. Amanda Prorok et al. in The Holy Grail of Multi-Robot Planning: Learning to Generate Online-Scalable Solutions from Offline-Optimal Experts showed that GNNs can aggregate and compress information from immediate neighbors, allowing each agent to maintain a localized yet context-aware representation of the global environment.
This mechanism drastically reduces communication overhead. For example, Xiaoxia Xu et al. utilized GNNs in Graph-Embedded Multi-Agent Learning for Smart Reconfigurable THz MIMO-NOMA Networks to transform high-dimensional local observations into low-dimensional embedded features for inter-agent communication, capturing critical relational dependencies without saturating the network.
This localized exchange allows agents to dynamically coordinate intent in crowded spaces. In Optimizing Crowd-Aware Multi-Agent Path Finding through Local Communication with Graph Neural Networks, Aniket Bera et al. demonstrated that allowing agents to exchange feature embeddings over a dynamic graph enables them to collectively avoid congested areas, significantly boosting path efficiency and navigation success rates.
Enforcing Social and Scene Consistency
When predicting or planning trajectories for multiple interacting agents, treating each actor independently leads to "scene-inconsistent" outcomes—such as two vehicles trying to occupy the same space simultaneously or ignoring right-of-way rules.
By modeling interactions as edges that signify social or physical influences, graph-based models ensure that the predicted state of one agent is explicitly conditioned on the states of its neighbors. Sergio Casas 0002 et al. addressed this in Implicit Latent Variable Model for Scene-Consistent Motion Forecasting by introducing a relational message-passing mechanism that allows agent nodes to exchange information about their intents. This conditions each actor's latent representation on the surrounding scene context, generating socially coordinated trajectories and drastically reducing predicted collisions.
This edge-based conditioning is widely used across trajectory prediction frameworks. Joon Hee Choi et al. in Shared Cross-Modal Trajectory Prediction for Autonomous Driving and Izzeddin Teeti et al. in Vision-based Intention and Trajectory Prediction in Autonomous Vehicles: A Survey emphasize that representing road users as nodes in a graph where edges signify social influences allows neural networks to capture how a pedestrian's or vehicle's trajectory is altered by the proximity and behavior of others.
Reconstructing Latent Context and Credit Assignment
Beyond spatial coordination, graph structures provide a powerful mechanism for reasoning about hidden variables and credit assignment in cooperative reinforcement learning. In many real-world scenarios, agents have a limited, partial view of the environment, and the global state is completely hidden.
Zhiwei Xu et al. tackled this in SIDE: I Infer the State I Want to Learn by using a graph-based architecture to aggregate local observations into a global context. By explicitly modeling the spatial and functional dependencies between agents, the network can reconstruct a "latent global state" via variational inference, allowing decentralized agents to coordinate effectively even when the true environment state is unobserved.
Similarly, in multi-agent credit assignment, understanding how an individual agent's actions contribute to a global reward is notoriously difficult due to confounding environmental factors. Jiahui Li et al. proposed Deconfounded Value Decomposition for Multi-Agent Reinforcement Learning, which uses graph attention mechanisms to facilitate message passing between agents' local hidden states. This synthesizes a comprehensive joint trajectory representation that captures complex inter-agent dependencies, cutting through spurious correlations to achieve highly accurate value decomposition.
Predictive Social Intelligence
Ultimately, embedding graph-based relational models directly into agents equips them with a form of artificial social intelligence. As Andrea Tacchetti demonstrated with Relational Forward Models for Multi-Agent Learning, treating multi-agent relationships as explicit graph edges allows for highly accurate long-term predictions of group dynamics. When agents can accurately predict their teammates' next moves through a relational forward model, they learn to coordinate significantly faster and scale more effectively than standard vector-based or recurrent architectures.
Key Foundational Work
Extending World Models for Multi-Agent Reinforcement Learning in MALMÖ (2018) — contributed 2 concept elements to this direction.
Graph Neural Networks for Learning Robot Team Coordination (2018) — contributed 1 concept elements to this direction.