ProjectsMECC 2024Multi-Agent Systems

Graph Attention Inference of Network Topology

Inferring the hidden graph behind a multi-agent system by training attention to predict what each agent does next.

Akshay Kolli/Reza Azadeh/Kshitij Jerath

arXiv PDF DOI

attention matrixunknown graph

querykeyedge

No known graph

Learns topology without prior adjacency examples.

Unknown dynamics

Uses observed states instead of hand-specified equations.

Attention as edges

Interprets learned attention scores as the graph estimate.

Overview

Predict the next state, then read the graph from what the model attended to.

The paper studies a practical problem in networked multi-agent systems: the agents move, synchronize, or converge, but the interaction graph behind that behavior is not given.

The model is trained on state trajectories from consensus dynamics and Kuramoto oscillators. During prediction, attention scores between agent embeddings become an interpretable approximation of the adjacency matrix.

Consensus and Kuramoto simulation examples with adjacency matrices — Simulation examples: consensus dynamics and Kuramoto oscillators paired with their hidden adjacency matrices.

Method

A topology estimate falls out of the attention layer.

Instead of supervising the graph directly, the model learns to forecast the system. The attention matrix is then thresholded and compared with the true graph.

01Embed every agent into a shared latent space.
02Project embeddings into key/query vectors and compute pairwise attention.
03Translate observed agent states into values.
04Predict the next state and read the attention matrix as topology.

Architecture diagram showing agent embeddings, key-query attention, values, predictions, and loss — Architecture: embeddings produce key/query vectors; observed states produce values; the attention matrix approximates adjacency.

Results

Strongest graph recovery appears with smaller systems, and more simulations help larger systems.

F1 link-prediction scores are above a random baseline for both tested dynamics. Consensus dynamics are easier than Kuramoto oscillators, while additional simulation data improves larger-agent inference.

F1 score results for consensus dynamics and Kuramoto oscillators — F1 results across system size and number of simulations for consensus dynamics and Kuramoto oscillators.

training behavior

Attention first learns the obvious self-dependencies, then gradually recovers inter-agent structure as training progresses.

Attention matrices over training epochs and predicted graphs — Attention values through training stages, from true graph to predicted graph.

Citation

Paper

Graph Attention Inference of Network Topology in Multi-Agent Systems. Akshay Kolli, Reza Azadeh, and Kshitij Jerath. Accepted at the Modeling and Estimation Control Conference, 2024.

@misc{kolli2024graphattentioninference,
  title={Graph Attention Inference of Network Topology in Multi-Agent Systems},
  author={Kolli, Akshay and Azadeh, Reza and Jerath, Kshitij},
  year={2024},
  eprint={2408.15449},
  archivePrefix={arXiv},
  primaryClass={cs.MA}
}