summaries: This paper presents a method for dynamic relational inference for multi-agent trajectory prediction. The method extends the neural relational inference (NRI) (Kipf et al., 2018) by changing the static relations between agents to dynamic relations. This equates to inferring time-varying latent variables $z_t^{ij}$ as opposed to learning time-independent latent variables $z^{ij}$. The paper conducts experiments on physics simulations and basketball trajectories to show the superiority of the proposed method against different variants of NRI.

summaries: The authors propose a novel Relational Inference system that learns to predict the graph structure underlying the data as well as the updated state of the system. Relational reasoning has received considerable attention in recent year. Predicting the graph structure underlying a system from data in a dynamic way is an great next step, which could help alleviate some of the scalability issue currently afflicting these methods.

summaries: This paper builds on Kipf et al. (2018)’s Neural Relational Inference. In particular, this work introduces a latent variable model which treats the interactions (i.e. relations) between different agents as dynamic and time-varying. As in NRI, the interaction variable between any two agents is conditioned on the history of those agents’ states. An agent’s future state is conditioned on its history of states as well as its interaction variables with other agents.

authors:
Alexandre Alahi
Kratarth Goel
Vignesh Ramanathan
Alexandre Robicquet
Li Fei-Fei
Silvio Savarese

title: Social lstm: Human trajectory prediction in crowded spaces

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Stefano V Albrecht
Peter Stone

title: Autonomous agents modelling other agents: A comprehensive survey and open problems

venue: Artificial Intelligence,

authors:
Ferran Alet
Erica Weng
Tomás Lozano-Pérez
Leslie Pack Kaelbling

title: Neural relational inference with fast modular meta-learning

venue: In Advances in Neural Information Processing Systems,

authors:
Peter Battaglia
Razvan Pascanu
Matthew Lai
Danilo Jimenez Rezende

title: Interaction networks for learning about objects, relations and physics

venue: In Advances in neural information processing systems,

authors:
Samy Bengio
Oriol Vinyals
Navdeep Jaitly
Noam Shazeer

title: Scheduled sampling for sequence prediction with recurrent neural networks

authors:
Steffen Bickel
Michael Brückner
Tobias Scheffer

title: Discriminative learning under covariate shift

venue: Journal of Machine Learning Research,

authors:
Tian Qi Chen
Yulia Rubanova
Jesse Bettencourt
David K Duvenaud

title: Neural ordinary differential equations

authors:
Kyunghyun Cho
Bart Van Merriënboer
Caglar Gulcehre
Dzmitry Bahdanau
Fethi Bougares
Holger Schwenk
Yoshua Bengio

title: Learning phrase representations using rnn encoder-decoder for statistical machine translation

venue: arXiv preprint arXiv:1406.1078,

authors:
Junyoung Chung
Kyle Kastner
Laurent Dinh
Kratarth Goel
Aaron C Courville
Yoshua Bengio

title: A recurrent latent variable model for sequential data

authors:
Marco Fraccaro
Søren Kaae Sønderby
Ulrich Paquet
Ole Winther

title: Sequential neural models with stochastic layers

authors:
Lise Getoor
Nir Friedman
Daphne Koller
Avi Pfeffer

title: Learning probabilistic relational models

venue: In Relational data mining,

authors:
Palash Goyal
Emilio Ferrara

title: Graph embedding techniques, applications, and performance: A survey

venue: Knowledge-Based Systems,

authors:
Colin Graber
Alexander Schwing

title: Dynamic neural relational inference

authors:
Roger Grosse
Ruslan R Salakhutdinov
William T Freeman
Joshua B Tenenbaum

title: Exploiting compositionality to explore a large space of model structures

venue: arXiv preprint arXiv:1210.4856,

authors:
Aditya Grover
Maruan Al-Shedivat
Jayesh K Gupta
Yura Burda
Harrison Edwards

title: Learning policy representations in multiagent systems

venue: Proceedings of the 35th International Conference on Machine Learning,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

authors:
Irina Higgins
Loic Matthey
Arka Pal
Christopher Burgess
Xavier Glorot
Matthew Botvinick
Shakir Mohamed
Alexander Lerchner

title: beta-vae: Learning basic visual concepts with a constrained variational framework

authors:
Jonathan Ho
Stefano Ermon

title: Generative adversarial imitation learning

authors:
Chin-Wei Huang
David Krueger
Alexandre Lacoste
Aaron Courville

title: Neural autoregressive flows

authors:
Max Jaderberg
Wojciech M Czarnecki
Iain Dunning
Luke Marris
Guy Lever
Antonio Garcia Castaneda
Charles Beattie
Neil C Rabinowitz
Ari S Morcos
Avraham Ruderman

title: Humanlevel performance in 3d multiplayer games with population-based reinforcement learning

authors:
Eric Jang
Shixiang Gu
Ben Poole

title: Categorical reparametrization with gumble-softmax

venue: In International Conference on Learning Representations (ICLR 2017). OpenReview

authors:
Charles Kemp
Joshua B Tenenbaum

title: The discovery of structural form

venue: Proceedings of the National Academy of Sciences,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Diederik P Kingma
Max Welling

title: Auto-encoding variational bayes

venue: arXiv preprint arXiv:1312.6114,

authors:
Thomas Kipf
Ethan Fetaya
Kuan-Chieh Wang
Max Welling
Richard Zemel

title: Neural relational inference for interacting systems

authors:
Daphne Koller
Nir Friedman
Sašo Džeroski
Charles Sutton
Andrew McCallum
Avi Pfeffer
Pieter Abbeel
Ming-Fai Wong
David Heckerman
Chris Meek

title: Introduction to statistical relational learning

venue: MIT press,

authors:
Tjalling C Koopmans
Olav Reiersol

title: The identification of structural characteristics

venue: The Annals of Mathematical Statistics,

authors:
Rahul G Krishnan
Uri Shalit
David Sontag

title: Structured inference networks for nonlinear state space models

venue: In Thirty-first aaai conference on artificial intelligence,

authors:
Hoang M Le
Yisong Yue
Peter Carr
Patrick Lucey

title: Coordinated multi-agent imitation learning

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Shiyang Li
Xiaoyong Jin
Yao Xuan
Xiyou Zhou
Wenhu Chen
Yu-Xiang Wang
Xifeng Yan

title: Enhancing the locality and breaking the memory bottleneck of transformer on time series forecasting

authors:
Yunzhu Li
Jiajun Wu
Russ Tedrake
Joshua B Tenenbaum
Antonio Torralba

title: Learning particle dynamics for manipulating rigid bodies, deformable objects, and fluids

venue: arXiv preprint arXiv:1810.01566,

authors:
Yukai Liu
Rose Yu
Stephan Zheng
Eric Zhan
Yisong Yue

title: Naomi: Non-autoregressive multiresolution sequence imputation

authors:
Christos Louizos
Uri Shalit
Joris M Mooij
David Sontag
Richard Zemel
Max Welling

title: Causal effect inference with deep latent-variable models

authors:
Ryan Lowe
Yi I Wu
Aviv Tamar
Jean Harb
OpenAI Pieter Abbeel
Igor Mordatch

title: Multi-agent actor-critic for mixed cooperative-competitive environments

authors:
Sindy Löwe
David Madras
Richard Zemel
Max Welling

title: Amortized causal discovery: Learning to infer causal graphs from time-series data

venue: arXiv preprint arXiv:2006.10833,

authors:
Sarthak Mittal
Alex Lamb
Anirudh Goyal
Vikram Voleti
Murray Shanahan
Guillaume Lajoie
Michael Mozer
Yoshua Bengio

title: Learning to combine top-down and bottom-up signals in recurrent neural networks with attention over modules

venue: arXiv preprint arXiv:2006.16981,

authors:
Damian Mrowca
Chengxu Zhuang
Elias Wang
Nick Haber
Li F Fei-Fei
Josh Tenenbaum
Daniel L Yamins

title: Flexible neural representation for physics prediction

authors:
Syama Sundar Rangapuram
Matthias W Seeger
Jan Gasthaus
Lorenzo Stella
Yuyang Wang
Tim Januschowski

title: Deep state space models for time series forecasting

authors:
Alvaro Sanchez-Gonzalez
Jonathan Godwin
Tobias Pfaff
Rex Ying
Jure Leskovec
Peter W Battaglia

title: Learning to simulate complex physics with graph networks

venue: arXiv preprint arXiv:2002.09405,

authors:
Adam Santoro
David Raposo
David G Barrett
Mateusz Malinowski
Razvan Pascanu
Peter Battaglia
Timothy Lillicrap

title: A simple neural network module for relational reasoning

authors:
Michael Shum
Max Kleiman-Weiner
Michael L Littman
Joshua B Tenenbaum

title: Theory of minds: Understanding behavior in groups through inverse planning

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Jiaming Song
Hongyu Ren
Dorsa Sadigh
Stefano Ermon

title: Multi-agent generative adversarial imitation learning

authors:
Sainbayar Sukhbaatar
Rob Fergus

title: Learning multiagent communication with backpropagation

authors:
Andrea Tacchetti
H Francis Song
Pedro AM Mediano
Vinicius Zambaldi
Neil C Rabinowitz
Thore Graepel
Matthew Botvinick
Peter W Battaglia

title: Relational forward models for multi-agent learning

venue: International Conference on Learning Representations (ICLR

authors:
Ronald J Williams
David Zipser

title: A learning algorithm for continually running fully recurrent neural networks

venue: Neural computation,

authors:
Zonghan Wu
Shirui Pan
Fengwen Chen
Guodong Long
Chengqi Zhang
Philip S Yu

title: A comprehensive survey on graph neural networks

authors:
Jinsung Yoon
Daniel Jarrett
Mihaela van der Schaar

title: Time-series generative adversarial networks

authors:
Hengshuang Zhao
Jianping Shi
Xiaojuan Qi
Xiaogang Wang
Jiaya Jia

title: Pyramid scene parsing network

text:
DYNAMIC RELATIONAL INFERENCE IN MULTI-AGENT TRAJECTORIES
Anonymous authors Paper under double-blind review
ABSTRACT
Unsupervised learning of interactions from multi-agent trajectories has broad applications in physics, vision and robotics. However, existing neural relational inference works are limited to static relations. In this paper, we consider a more general setting of dynamic relational inference where interactions change over time. We propose DYnamic multi-Agent Relational Inference (DYARI) model, a deep generative model that can reason about dynamic relations. Using a simulated physics system, we study various dynamic relation scenarios, including periodic and additive dynamics. We perform comprehensive study on the trade-off between dynamic and inference period, the impact of training scheme, and model architecture on dynamic relational inference accuracy. We also showcase an application of our model to infer coordination and competition patterns from real-world multi-agent basketball trajectories.

heading: 1 INTRODUCTION

text:
Particles, friends, and teams are multi-agent relations at different scales. Learning multi-agent interactions is essential to our understanding of the structures and dynamics underlying many systems. Practical examples include understanding social dynamics among pedestrians (Alahi et al., 2016), learning communication protocols in traffic (Sukhbaatar et al., 2016; Lowe et al., 2017) and predicting physical interactions of particles (Mrowca et al., 2018; Li et al., 2018; Sanchez-Gonzalez et al., 2020). Most existing work on modeling relations assume the interactions are observed and train the models with supervised learning. For multi-agent trajectories, the interactions are hidden and thus need to be inferred from data in an unsupervised fashion. While one could impose an interaction graph structure (Battaglia et al., 2016), it is difficult to find the correct structure as the search space is very large (Grosse et al., 2012). The search task is computationally expensive and the resulting model can potentially suffer from the model misspecification issue (Koopmans & Reiersol, 1950). Neural Relational Inference for Interacting Systems
Thomas Kipf * 1 Ethan Fetaya * 2 3 Kuan-Chieh Wang 2 3 Max Welling 1 4 Richard Zemel 2 3 4
Abstract
Interacting systems are prevalent in nature, from dynamical systems in physics to complex societal dynamics. The interplay of components can give rise to complex behavior, which can often be explained using a simple model of the system’s constituent parts. In this work, we introduce the neural relational inference (NRI) model: an unsupervised model that learns to infer interactions while simultaneously learning the dynamics purely from observational data. Our model takes the form of a variational auto-encoder, in which the latent code represents the underlying interaction graph and the reconstruction is based on graph neural networks. In experiments on simulated physical systems, we show that our NRI model can accurately recover ground-truth interactions in an unsupervised manner. We further demonstrate that we can find an interpretable structure and predict complex dynamics in real motion capture and sports tracking data.
1. Introduction A wide range of dynamical systems in physics, biology, sports, and other areas can be seen as groups of interacting components, giving rise to complex dynamics at the level of individual constituents and in the system as a whole. Modeling these type of dynamics is challenging: often, we only have access to individual trajectories, without knowledge of the underlying interactions or dynamical model.
As a motivating example, let us take the movement of basketball players on the court. It is clear that the dynamics of a single basketball player are influenced by the other players, and observing these dynamics as a human, we are
*Equal contribution 1University of Amsterdam, Amsterdam, The Netherlands 2University of Toronto, Toronto, Canada 3Vector Institute, Toronto, Canada 4Canadian Institute for Advanced Research, Toronto, Canada. Correspondence to: Thomas Kipf <t.n.kipf@uva.nl>.
Proceedings of the 35 th International Conference on Machine Learning, Stockholm, Sweden, PMLR 80, 2018. Copyright 2018 by the author(s).
Observed dynamics Interaction graph
Figure 1. Physical simulation of 2D particles coupled by invisible
springs (left) according to a latent interaction graph (right). In this
example, solid lines between two particle nodes denote connections
via springs whereas dashed lines denote the absence of a coupling.
In general, multiple, directed edge types – each with a different associated relation – are possible.
able to reason about the different types of interactions that might arise, e.g. defending a player or setting a screen for a teammate. It might be feasible, though tedious, to manually annotate certain interactions given a task of interest. It is more promising to learn the underlying interactions, perhaps shared across many tasks, in an unsupervised fashion.
Recently there has been a considerable amount of work on learning the dynamical model of interacting systems using implicit interaction models (Sukhbaatar et al., 2016; Guttenberg et al., 2016; Santoro et al., 2017; Watters et al., 2017; Hoshen, 2017; van Steenkiste et al., 2018). These models can be seen as graph neural networks (GNNs) that send messages over the fully-connected graph, where the interactions are modeled implicitly by the message passing function (Sukhbaatar et al., 2016; Guttenberg et al., 2016; Santoro et al., 2017; Watters et al., 2017) or with the help of an attention mechanism (Hoshen, 2017; van Steenkiste et al., 2018).
In this work, we address the problem of inferring an explicit interaction structure while simultaneously learning the dynamical model of the interacting system in an unsupervised way. Our neural relational inference (NRI) model learns the dynamics with a GNN over a discrete latent graph, and we perform inference over these latent variables. The inferred edge types correspond to a clustering of the interactions. Using a probabilistic model allows us to incorporate prior beliefs about the graph structure, such as sparsity, in a principled manner.
ar X
iv :1
80 2.
04 68
7v 2
[s ta
t.M L]
6 Ju
n 20
18
Figure 1: Neural R lational I ference for learning th interaction graph. Picture taken from (Kipf et al., 2018)
Relational inference aims to discover hidden interactions from data and has been studied for decades. Statistical relational learning are based on probabilistic graphical models such as probabilistic relational model (Kemp & Tenenbaum, 2008; Getoor et al., 2001; Koller et al., 2007; Shum et al., 2019). However, these methods may require significant feature engineering and high computational costs. Recently, Battaglia et al. (2016); Santoro et al. (2017) propose to reason about relations using graph neural networks but still requires supervision. One exception is Neural Relational Inf rence (NRI) (Kipf et al., 2018), a flexible deep generative mo el that can infer pot ntial relations in an unsupervised fashi n. As shown in Figure 1, NRI simul-
taneously learns the dynamics from multi-agent trajectories and infers their re ations. In particular, NRI builds upon variational auto-encoder (VAE) (Kingma & Welling, 2013) and introduces latent variables to represent the hidden relations. Despite its flexibility, a major limiting factor of NRI is that it assumes the relations among the agents are static. Th t is, two agents ar either interacting or n t interacting regardless of their states at different time steps, which is rath r restrictive.
1
In this paper, we study a more realistic setting: dynamic relational inference. For example, in game plays, players can coordinate and compete dynamically depending on the strategy. We propose a novel deep generative model, which we call DYnamic multi-Agent Relational Inference (DYARI). DYARI encodes trajectory interactions at different time steps. It utilizes deep temporal CNN models with pyramid pooling to extract rich representations from the interactions. DYARI infers the relations for each sub-sequence dynamically and jointly decode a sequence of relations.
As relational inference is unsupervised, we use simulated dynamics physics systems as ground truth for validation. We find that the performance of the static NRI model deteriorates significantly with shorter output trajectories, making it unsuitable for dynamic relational inference. In contrast, DYARI is able to accurate infer the hidden relations with various dynamics scenarios. We also perform extensive ablative study to understand the effect of inference period, training schemes and model architecture. Finally, We showcase our DYARI model on real-world basketball trajectories.
In summary, our contributions include:
• We tackle the challenging problem of unsupervised learning of hidden dynamic relations given multi-agent trajectories. • We develop a novel deep generative model called DYARI to handle time-varying interactions
and predict a sequence of hidden relations in an end-to-end fashion. • We demonstrate the effectiveness our method on both the simulated physics dynamics and
real-world basketball game play datasets.

heading: 2 RELATED WORK

text:
Deep sequence models Deep sequence models include both deterministic models (Alahi et al., 2016; Li et al., 2019; Mittal et al., 2020) and stochastic models (Chung et al., 2015; Fraccaro et al., 2016; Krishnan et al., 2017; Rangapuram et al., 2018; Chen et al., 2018; Huang et al., 2018; Yoon et al., 2019). For GAN-like models, (Yoon et al., 2019) combine adversarial training and a supervised learning objective for time series forecasting. Liu et al. (2019) propose a non-autoregressive model for sequence generation. Compared with GANs, VAE-type models can provide explicit inference and are preferable for our purpose. For instance, Chung et al. (2015) introduces stochastic layers in recurrent neural networks to model speech and hand-writing. Rangapuram et al. (2018) parameterizes a linear state-space model for probabilistic time series forecasting. Chen et al. (2018); Huang et al. (2018) combine normalizing flows with autoregressive models. However, all existing models only model the temporal latent states for individual sequences rather than their interactions.
Relational inference Graph neural networks (GNNs) seek to learn representations over relational data, see several recent surveys on GNNs and the references therein, e.g. (Wu et al., 2019; Goyal & Ferrara, 2018). Unfortunately, most existing work assume the graph structure is observed and train with supervised learning. In contrast, relational inference aims to discover the hidden interactions and is unsupervised. Earlier work in relational reasoning (Koller et al., 2007) use probabilistic graphical models, but requires significant feature engineering. The seminal work of NRI (Kipf et al., 2018) use neural networks to reason in dynamic physical systems. Alet et al. (2019) reformulates NRI as meta-learning and proposes simulated annealing to search for graph structures. Relational inference is also posed as Granger causal inference for sequences (Louizos et al., 2017; Löwe et al., 2020). Nevertheless, all existing work are limited to static relations while we focus on dynamic relations.
Multi-agent learning Multi-agent trajectories arises frequently in reinforcement learning (RL) and imitation learning (IL) (Albrecht & Stone, 2018; Jaderberg et al., 2019). Modeling agent interactions given dynamic observations from the environment remains a central topic. In the RL setting, for example, Sukhbaatar et al. (2016) models the control policy in a fully cooperative multi-agent setting and applies a GNN to represent the communications. Le et al. (2017) models the agents coordination as a latent variable for imitation learning. Song et al. (2018) generalizes GAIL (Ho & Ermon, 2016) to multi-agent through a shared generator. However, these coordination models only capture the global interactions implicitly without the explicit graph structure. Tacchetti et al. (2019) combines GNN with a forward dynamics model to model multi-agent coordination but also requires supervision. Grover et al. (2018) directly models the episodes of interaction data with GNs for learning multiagent policies. Our method instantiates the multi-agent imitation learning framework, but focuses on relational inference. Our approach is also applicable to dynamic modeling in model-based RL.

heading: 3 DYNAMIC MULTI-AGENT RELATIONAL INFERENCE

text: Given a collection of multi-agent trajectories, we aim to reason about their hidden relations over time. First we describe the underlying probabilistic inference problem.

heading: 3.1 PROBABILISTIC INFERENCE FORMULATION

text:
For each agent i ∈ {1, · · · , N}, define its state (coordinates) as xt ∈ RD. A trajectory τ (i) = (x1, x2, · · · , xT ) is a sequence of states that are sampled from a policy. Given trajectories from N agents {τ (i)}Ni=1, dynamic relational inference aims to infer the pairwise interactions of N agents at every time step. Mathematically speaking, the joint distribution of the trajectories can be written as:
p(τ (1), · · · , τ (N)) = T∏ t=1 p(xt+1|xt, · · · ,x1) (1)
where p(xt+1|xt, · · · ,x1) represents the state transition dynamics. We use the bold form xt := (x (1) t , · · · , x(N)t ) to indicate the concatenation of all agents observations and x<t := (x1, · · · ,xt).
We introduce latent variables z(ij)t to denote the interactions between agent i and j at time t. To make the problem tractable, we restrict z(ij)t to be categorical, representing discrete interactions such as coordination or competition. We assume that the dynamics model can be decomposed into the individual dynamics, in conjunction with the pairwise
interaction. This substantially reduces the dimensionality of the distribution and simplifies learning. Therefore, we can rewrite the transition dynamics as:
p(xt+1|x<t) ≈ ∫ z N∏ i=1 p(x (i) t+1|x (i) <t, z (ij) t ) N∏ i=1 N∏ j=1,j 6=i p(z (ij) t |x(i)<t, x(j)<t )dz (2)
Here each p(x(i)t+1|x (i) <t) captures the state transition dynamics of a single agent. p(z (ij) t |x(i)<t, x(j)<t ) represents the latent interactions between two agents. Figure 2 visualizes the graphical model representation for three agents over t number of time steps. The shaded nodes represent observed variables and the unshaded nodes are latent variables. Dynamic relational inference is to estimate distributions of the hidden variables {z(ij)t } at different time steps.

heading: 3.2 DYNAMIC MULTIAGENT RELATIONAL INFERENCE (DYARI)

text:
We propose a deep generative model: Dynamic multi-Agent Relational Inference (DYARI). Given the trajectories (x1, · · · ,xT ) of all agents, DYARI first concatenates the trajectories based on a fully connected graph. The concatenated trajectories are used as interaction features for the encoder. Then we sample the sequence of relations from the encoded hidden states. Finally, we generate the future trajectory predictions conditioned on the sampled relations. Figure 3 visualizes the overall architecture of our model which encodes and decodes multi-agent trajectories. The bottom cut-out diagram shows the architecture of our encoder.
Encoder. A key ingredient of DYARI is an encoder that is inspired by PSPNet (Zhao et al., 2017) to learn rich representations of trajectories at different scales. In particular, we define a residual block as a two-layer CNN with residual connections (He et al., 2016). Our encoder has four modules: feature extraction, pyramid pooling, an aggregation module, and an interpolation module.
• Feature extraction: the feature extraction module consists of multiple residual blocks interleaved with pooling layers to extract rich temporal features. • Pyramid pooling: the pyramid pooling module learns multi-scale temporal representations from
the extracted features. First, the output of the feature extraction module is downsampled by 2x
and 5x through average pooling. Then, the downsampled features are passed through two residual blocks and finally upsampled by 2x and 5x to generate features which are of the same size as the input. The representations learned at 2x and 5x resolutions are concatenated with the input to generate composite multi-scale features.
• Aggregation module: a 1-D convolution that aggregates the multi-scale features. • Interpolation module: it average-pools the aggregated features corresponding to the dynamic
period. Then the outputs are upsampled through nearest neighbours interpolation to obtain the hidden presentations for the relations.
Sampling. We utilize variational inference (Kingma & Welling, 2013) to sample the latent variables from hidden representations. Specifically, assume the interaction posterior z(ij)t to be categorical:
qφ(z (ij) t |x<t) ∼ Cat(p1, · · · , pk)
Using the Gumbel-Max trick (Jang et al., 2017), we can reparameterize the categorical distribution as: z (ij) t = Softmax(h (ij) t + g (ij) t ). Here h (ij) t is the hidden states of the encoder and g (ij) t is a random Gumbel vector. Note that a defining feature of DYARI is that the latent variable z(ij)t is time-dependent, requiring fine-grained modeling. Our encoder ensures that the learned representations are expressive enough to capture such complex dynamics.
Decoder. Given the sampled latent variables, the decoder generates the prediction auto-regressively following a Gaussian distribution:
p(x (i) t+1|x<t, z (ij) t ) = N (x(i)t+1|µ (i) t+1, σ 2I) (3) µit+1 = fdec( ∑ j 6=i ∑ k z (ij) t,k uk; θ), uk = f k mlp(x (i) t , x (j) t ) (4)
Here the output x(i)t+1 is reparameterized by a Gaussian distribution with mean µ (i) t+1 and a fixed standard deviation σ2. The mean vector µ(i)t+1 of agent i is computed by aggregating the hidden states of all other agents. We use a separate MLP to encode the previous inputs into different type of edges in a k-dimensional one-hot vector z(ij)t . To generate long-term predictions using the model in Eqn. (4), we can also incorporate the predictions from the previous time step. The decoder architecture is the same as in NRI at a given time step, which consists of message passing GNN operations, followed by a GRU (Cho et al., 2014) decoder.
Inference. At every time step t, we learn a different distribution for the hidden relation z(ij)t . We assume a uniform prior for pθ(zt) and use ELBO as the optimization objective:
LELBO = E[log pθ(x<T |z<T )]− βdKL[qφ(z<T |x<T )||pθ(z<T )]] (5)
= − N∑ i=1 T∑ t=1 (µ (i) t − x(i)t )2 2σ2 + β N∑ i,j T∑ t=1 H(qφ(z (ij) t |xt))
where the mean vector µ(i)t is parameterized by the decoder. H is the entropy function and β balances the two terms in ELBO (Higgins et al., 2016).

heading: 4 EXPERIMENTS

text:
We conduct extensive experiments on simulated physics dynamics and real-world basketball trajectories. The majority of our experiments are based on the physics simulation in the Spring environment. This is ideal for model verification and ablative study as we know the ground truth relations.
4.1 PHYSICS SIMULATIONS
Data Generation The Spring environment (Kipf et al., 2018) simulates the movements of a group of particles connected by a spring in a box. The hidden relation is whether there is a spring connecting the two particles. To simulate dynamic relations, we generate the trajectories by removing and adding back the springs following certain patterns. Figure 4 visualizes the trajectories resulting from such dynamic relations. Starting from the bottom, the two-particle trajectories appear as straight lines and bend in the middle due to the spring force, and return to straight lines after the removal of the spring.
We define the number of time steps between the change of relations as the dynamic period. The primary challenges for dynamic relation inference arise along two dimensions:
1. The shorter the dynamic period, the more frequent the relation changes. Hence, it becomes more difficult to infer relations with shorter dynamic period.
2. If the dynamic period itself also changes, then the task becomes much harder because the model also needs to adapt to the unknown period in the changing relations. Note that the way relations change in the trajectories must follow certain pattern and not be completely random. Otherwise it would be impossible to learn anything meaningful.
We experiment with two types of dynamic relations: periodic dynamics and additive dynamics. For periodic dynamics, we generate the trajectories by periodically removing and adding back the springs. We investigate the model performance by generating data with different frequencies of periodicity. For additive dynamics, we assume the dynamic period is increasing arithmetically. Each trajectory is of length 50 and the decoding length is 40, see details of the generated dataset in Appendix.
Baselines and Setup We consider several baselines for comparison: (1) NRI (static): unsupervised NRI with an encoder trained using the entire trajectory and infer repeatedly over time. This corresponds to NRI (learned) in (Kipf et al., 2018). (2) NRI (adaptive): NRI (static) with an encoder trained over sub-trajectories. The encoding length corresponds exactly to the dynamic period of the dataset. We use the NRI (static) decoder to predict the entire trajectory in an auto-regressive fashion. (3) Interaction Networks (IN) (Battaglia et al., 2016): a supervised GNN model which uses the ground truth relations to predict future trajectories. We include this supervised learning model as the “gold standard” for our inference tasks. It is important to note here that (Graber & Schwing, 2020) also propose a model, dNRI, for this problem but the focus of their work is trajectory prediction whereas we focus on unsupervised relational inference. In our experiments with their model, we observed a relational inference accuracy of 0.505 on our periodic data with dynamic period 20. On the other hand, the same model gives an accuracy of 0.66 on the 3-particle synthetic data presented in their paper. Therefore, dNRI is unable to infer relations in an unsupervised setting.
In practice, we do not know the dynamic period beforehand. Therefore, how often we infer the relations is a difficult choice: rare inference would miss the time steps where relations change while predicting too frequently introduces more latent variables and complicates the inference. To investigate this trade-off, we define inference period as the number of time steps between two
predicted relations. Unless otherwise noted, the inference period in our experiments is the same as the dynamic period. All the models are trained to predict the sequence in an auto-regressive fashion: the prediction of the current time step is fed as the input to the next time step. We use Adam (Kingma & Ba, 2014) optimizer with learning rate 5e−4 and weight decay 1e−4 and train for 300 epochs.

heading: 4.1.1 PATHOLOGICAL CASES OF NEURAL RELATIONAL INFERENCE

text:
It is known that latent variable models suffer from the problem of identifiability (Koopmans & Reiersol, 1950), which means certain parameters, in principle, cannot be estimated consistently. NRI infers correlation-like relations between trajectories which highly depend on the length of the time lag. To test this hypothesis, we follow the exact same setting as Kipf et al. (2018) to infer the interaction graph. Instead of decoding 50 time steps, we vary the length of input and output sequence.
Table 1 summarizes the inference accuracy with different sequence length in the encoder and decoder. We can see that the performance of NRI deteriorates drastically with shorter training sequences, simply increasing the capacity of the encoder (NRI++) does not help. One plausible explanation is that NRI is learning correlation-like interactions. Shorter decoding sequences carry less information about correlations, making it harder to learn. Meanwhile, we also observed that using auto-regressive can achieve better inference accuracy compared to teacher forcing. The pathological cases highlight the issue of NRI for dynamic relational inference. If the interactions change frequently every few time steps, repeatedly applying NRI to different time steps would suffer from short decoding sequences. Therefore, having a model that can jointly infer a sequence of relations is critical.

heading: 4.1.2 DYNAMIC RELATIONAL INFERENCE COMPARISON

text:
We compare the performance of different models for dynamic relational inference tasks.
Periodic dynamics In the periodic scenario, the dynamic period is fixed. We generate four datasets with a dynamic period of 40, 20, 8, 4 to simulate relational dynamics with increasing frequency. Table. 2 columns “40, 20, 8, 4” show the trajectory prediction mean square error (MSE) and interaction inference accuracy comparison of different methods.
We can see that all methods can achieve almost perfect predictions of the trajectories with very low MSE. However, there is a sharp difference in relational inference accuracy. NRI (static) is incapable of learning dynamic interactions. NRI(adaptive) can learn but has lower accuracy due to short decoding sequences. With a more expressive encoder and joint decoding, DYARI is able to reach higher accuracy. When the dynamic period is very small at 4, even DYARI struggles slightly, suggesting the fundamental difficulty with frequently changing dynamics.
Additive Dynamics In the additive scenario, we allow the dynamic period itself to increase arithmetically. We increase the dynamic period in steps of 4 starting from a dynamic period of 4 timesteps. In a sequence of 40 timesteps, this implies that the relations (spring connection) get flipped at timesteps 4, 12 and 24. We use four NRI(static) models, each trained separately with 4, 8, 12 and 16 encoding timesteps. We combine the ensemble model predictions into NRI(adaptive). Table. 2 “Add” columns show the performance comparison. Similar to the periodic scenario, DYARI outperforms the baselines in this challenging task as well. Note that NRI(adaptive) is a close competitor w.r.t inference accuracy, but it is a four model ensemble and takes a long time to train.

heading: 4.1.3 ABLATIVE STUDY

text:
We perform ablative study to further validate our experiment design and understand the behavior of DYARI. In particular, we study the trade-off between dynamic and inference period, the effect of training scheme, as well as the ablative study of model architecture design.
Table 3: Inference accuracy for different combinations of dynamic and inference periods with DYARI.
Dynamic Period 40 8 4
Inference Period
40 0.99 0.50 0.50 8 0.88 0.80 0.50 4 0.80 0.76 0.74
Dynamic vs. Inference Period. To understand the relations between dynamic and inference period, we repeat the periodic scenario experiments by varying both dynamic and inference period in 40, 8, 4 time steps.
In Table 3, we observe that dynamic relational inference reaches the highest accuracy when the inference period matches the dynamic period. If the inference period is longer than the dynamic period, the model can miss the changes in the relations and completely fails to perform inference. Meanwhile, if the inference period is shorter than the dynamic period, the model still can learn but suffers from low accuracy. This is potentially due to the extra uncertainty introduced by estimating more latent variables.
Decoder Training Scheme Another fundamental challenge in sequence prediction is covariate shift (Bickel et al., 2009) – a mismatch between distribution in training and testing – due to sequential dependency. Common solutions to mitigate covariate shift include teacher forcing (Williams & Zipser, 1989) and scheduled sampling (Bengio et al., 2015). However, all these work are focused the prediction of observed sequence while our sequence predictions are on the latent variables. It is not evident that covariate shift exists in this setting. We demonstrate the empirical evidence for the effect of different training schemes on the accuracy of relational inference.
Quite surprisingly, we found that auto-regressive training is most effective for dynamic relations inference. Figure. 5 summarizes the difference in learning curve between using teacher forcing and auto-regressive for different dynamic periods. We also include a version of scheduled sampling (hybrid): in the first 30 time-steps, we train the model with teacher forcing and then switch to auto-regressive in the last 10 time-steps. We observe that while teacher forcing converges faster, it
leads to lower accuracy. This observation is consistent across different dynamic periods. Therefore, auto-regressive training is preferred for dynamic relation inference.

heading: 4.2 REAL-WORLD BASKETBALL DATA EXPERIMENTS

text:
To showcase the practical value of dynamic relational inference, we apply DYARI to a real-world basketball trajectory dataset. The goal of the experiment is to extract meaningful “hidden” relations in competitive basketball plays. The basketball dataset contains trajectories for 10 players in a game. As the ground-truth relations are unknown, we use the trajectory prediction MSE and negative ELBO as in-direct measures for the dynamic relational inference performance. We assume there are two types of hidden relations: coordination and competition. We defer the details of the dataset and training setup to the Appendix.
We report performance comparisons for different inference periods. As shown in Table 4, we observe lower MSE loss and negative ELBO with shorter inference period. Intuitively, the interactions in the real world may change constantly, thus shorter inference period can capture the dynamics better. DYARI outperforms the baselines in trajectory prediction MSE and negative ELBO loss. Notice that NRI(adaptive) is using encoder and decoder that are trained separately and this results in a high negative ELBO loss on the test set. Fig. 6 visualizes a sample trajectory of 10 basketball players with inferred relations from DYARI over different time steps. We separate coordination and competition interactions in different rows. In Fig. 6, Kobe Bryant is moving along with three-point line and guarded by a defender. We can see clear attention drawn to the specific players throughout the play. See Appendix for other inferred relations.

heading: 5 CONCLUSION

text: We investigate unsupervised learning of dynamic relations in multi-agent trajectories. We propose a novel deep generative model: Dynamic multi-Agent Relational Inference (DYARI) to infer changing relations over time. We conduct extensive experiments using a simulated physics system to study the performance of DYARI in handling various dynamic relations. We perform ablative study to understand the effect of dynamic and inference period, training scheme and model design choice. Compared with static NRI and its variant, our DYARI model demonstrates significant improvement in simulated physics systems as well as in a real-world basketball trajectory dataset.

heading: A MODEL IMPLEMENTATION DETAILS

text:
In this section, we include some details about the model implementation, especially the encoder part. Our encoder is analogical to ResNet CNNs (He et al., 2016) used in the field of image recognition, where the task can be abstracted to be a classification problem on 1D dimension. Meanwhile, inspired by PSPNet used in visual scene semantic parsing (Zhao et al., 2017), we add additional 2 global feature extractors to combine the whole-sequence (global) features and the sub-sequence (local) features.
for DYARI, each residual block shown in Fig. 3 consists of 4 skip connections structure.

heading: B EXPERIMENTAL DETAILS

text:
Particle dataset In general, we use the same pre-processing in NRI. Each raw simulated trajectory has length of 5000 and we sample with frequency of 100 so that each sample has length of 50 in our dataset. Correspondingly, the value of dynamic period/inference period matches the length of sample in our dataset. For instance, dynamic period = 10 means that the in the raw trajectory, the state of a node changes every 1000 time steps. In addition, The value of trajectories are all normalized to range of [0, 1] and the evaluation is done on the same range as well.
Basketball dataset details The basketball dataset consists of trajectory from 30 teams. The raw trajectory is captured with frequency of 25 ms. For our experiment, we sample the trajectory with frequency of 50 ms for more evident player movements. We use a inference period that matches the length of sample. For instance, inference period = 10 means that our model produce prediction every 500 ms. The resulting dataset include 50,000 training samples, 10,000 validations samples and 10,000 test samples.
We normalize the values of the trajectories to range [0,1] and train all the models in an auto-regressive fashion. We use the same training set up as in physics simulation experiments with a batch size of 64.

heading: C ADDITIONAL EXPERIMENTS

text:
Stochastic dynamics In order to make the problem even harder and to unify all the previous settings, we generate a dataset where the edge types are flipped randomly with a probability p after each dynamic period of 4 timesteps. The static data generation corresponds to p = 0 and the periodic dynamics corresponds to p = 1. Table 5 shows the MSE and inference accuracy of NRI, DYARI and Interaction Networks on the stochastic dataset for flipping probabilities p = 0.8 and p = 0.9.
The Effect of Average Pooling We perform an ablation study where we remove the average pooling corresponding to the inference period in the interpolation module to study the effect of this average pooling on the results. We find that without average pooling, inference accuracy decreases from 0.92 to 0.59 (as shown in Table 6) for inference period at 20. Here we drop the average pooling corresponding to the inference periods and directly interpolate to the sequence length. This shows that intermediate average pooling is critical for the relational inference performance.
Additional Inferred Relations in Basketball Trajectories We set the number of relations in Basketball dataset as two. In Sec 4.2, we visualized one of the inferred relations. Table 8 visualizes the second relations. Notice that the first relation captures focus on the rightmost red player while here the relation captures focus on the leftmost red player.

title: Neural Relational Inference for Interacting Systems