# Self-Growing Spatial Graph Network for
Context-Aware Pedestrian Trajectory Prediction

Sirin Haddad, Siew-Kei Lam S. Haddad was with the School of Computer Science
and Engineering, Nanyang Technological University (NTU), Singapore, 639798.
E-mail: see<EMAIL_ADDRESS>S.K. Lam is an Assistant Professor in
NTU.Manuscript received Dec 19, 2020.

###### Abstract

Pedestrian trajectory prediction is an active research area with recent works
undertaken to embed accurate models of pedestrians social interactions and
their contextual compliance into dynamic spatial graphs. However, existing
works rely on spatial assumptions about the scene and dynamics, which entails
a significant challenge to adapt the graph structure in unknown environments
for an online system. In addition, there is a lack of assessment approach for
the relational modeling impact on prediction performance. To fill this gap, we
propose Social Trajectory Recommender-Gated Graph Recurrent Neighborhood
Network (STR-GGRNN), which uses data-driven adaptive online neighborhood
recommendation based on the contextual scene features and pedestrian visual
cues. The neighborhood recommendation is achieved by online Nonnegative Matrix
Factorization (NMF) to construct the graph adjacency matrices for predicting
the pedestrians’ trajectories. Experiments based on widely-used datasets show
that our method outperforms the state-of-the-art. Our best performing model
achieves 12 cm ADE and $\sim$15 cm FDE on ETH-UCY dataset. The proposed method
takes only 0.49 seconds when sampling a total of 20K future trajectories per
frame.

###### Index Terms:

Machine learning, Tracking, Vision and Scene Understanding.

## Introduction

111This research was accomplished while being a PhD student at NTU.
Code and Data are available on Github: here.
Additional Materials and Training files: here.

Pedestrian trajectory prediction plays an essential role in Advanced Driver-
Assistance Systems (ADAS), autonomous driving, and robotic navigation to
maintain pedestrians safety. Modern trajectory prediction approaches [1, 2, 3]
model social interactions locally, where the neighborhood boundaries are
defined by a specific metric (i.e., short distance). An exception to this is
Social Attention [4] and Social GAN [5], which model all pedestrians
interactions to create a global context. The local methods observe dynamics
within the nearby pedestrian whereabouts and use a tabulated format to model
the environment.

Earlier research defined local pedestrian neighborhoods based on fixed spatial
distances as in [6, 7, 8]. Forming neighborhoods neurally is already explained
in [9, 10]. There are few works that developed the social modeling on spatio-
temporal graphs considering the spatial relations between pedestrians [11, 12,
13] using fixed parameters to determine the neighborhood boundaries. Such
local capture considers related pedestrians, but with limited understanding of
the social interaction temporal evolution.

Research in crowd behavioral modeling has reported a self-organizing
cooperative tendency among individuals in the crowd [14, 15, 16, 17]. Starting
with this intuition, we theorize a data-driven self-growing mechanism that
learns the interaction between pedestrians.

Figure 1: An illustration of the real-world scenario of pedestrians in an
urban environment. Anticipating whether pedestrians are influencing each other
is depicted by the $<$?$>$, and the dashed links connecting pedestrians
indicate whether a potential relationship exists. Each pedestrian has a
walking trajectory and looking span indicated by the light cones at the head.

Figure 1 visualizes the case where this mechanism is required for developing
associations between pedestrians. By considering their visual span, one can be
more certain about how pedestrians consider each others when moving.
Accordingly, a learning mechanism can learn to estimate their impact and
interactions. However, using a data-driven self-growing approach introduces
additional challenges to model the social interaction on spatio-temporal
graphs. There is a need to evaluate the generated neighborhoods plausibility
as the graph grows neighborhoods dynamically. To overcome this problem, we
employ pedestrians’ visual cues as a means to capture their spatial awareness
for constraining their neighbourhood. We propose an approach that combines
tabulated modeling with graph-structured modeling of interactions. Then it
examines the impact of associating pedestrians on the effectiveness of social
modeling, such that related pedestrians become pooled into adaptively-shaped
neighborhoods. Moreover, we propose a self-learned relational inference that
plays a significant role in growing the graph edges. At the same time, we
dedicate a tabulated structuring for modeling the static context into local
neighborhoods. This hybrid approach aims to improve the modeling of
pedestrians social influence and their awareness of static surroundings,
thereby reducing trajectory prediction errors. Our framework employs GridLSTM
[18], which is a more advanced LSTM cell that is capable of structuring its
memory gate over multimodal streams of features simultaneously. GridLSTM
passes memory states between data modalities horizontally and vertically,
which enables it to learn faster and more effectively than LSTM-based models.
In summary, the contributions of our work are as follow:

  * •

We introduce STR-GGRNN, an edge-centric online framework for mapping crowd
dynamics onto spatio-temporal graph networks and automatically infer the
social interactions by completing the graph edges with minimal engineering
effort.

  * •

Proposing a novel kernel to maps the STR-GGRNN features gradients and
accordingly, generates the future trajectories as an effect of the
interactions change relative to the static scene over time.

  * •

To the best of our knowledge, our work is the first to integrate Nonnegative
Matrix Factorization (NMF) as an efficient self-learned social neighborhood
recommendation system. It neurally evaluates the importance of the edges with
a compact version of nodes and edges features. The system generates
variational neighborhood proposals and examines them against the prediction
accuracy. It yields a locally optimal solution for modeling the social
interactions in spatio-temporal graphs.

  * •

The proposed model outperforms state-of-the-art methods in the ETH-UCY dataset
using TrajNet++ challenge data [19].

## Related Works

### Pedestrian Trajectory Prediction

Trajectory prediction approaches can be categorized into classical engineered
models [20, 21, 22] and learning-based models. Encoder-Decoder architecture
has achieved notable success in real crowd surveillance and driving datasets
[23]. Examples include GAN-based network [24, 5, 25, 26], LSTM-based [27, 3,
28, 12], Gated Graph-structured networks [29, 30, 7, 4, 11, 31, 32, 33, 34,
35, 36, 37]. In several occurrences, LSTM was combined with CNN in an end-to-
end pipeline. This has shown to be effective in generating contextually
compliant paths. The LSTM-based and other methods used prior knowledge and
empirical practices of modeling pedestrian trajectory and hence, they are
tailored to specific scenes and datasets that contains fewer pedestrians and
homogeneous scenarios captured by ETH-UCY dataset[38].

### Evolutionary Graph-based Systems Modeling

Fundamental research proposed biologically-inspired techniques to model
complex dynamic systems on a graph as a set of nodes connected by a set of
edges. Graph-based modeling had a plethora of successful applications, and
with numerous advancements this modeling evolved to adopt biological evolution
processes into dynamically adaptive graphs that encode features and make
decisions about structural growth. Neural Gas [39] and self-Organizing Maps
[40] introduced the fuzzy self-learned growth into graph theory.

Recently, in the field of crowd motion modeling, there are several attempts to
model crowd holistic motion as a simulation of a physically-inspired system
[41, 42, 10, 17, 43]. However, in such proposals the underlying graph/temporal
function was resembling a pre-engineered natural model and the growth decision
was determined or predicted a-priori.

Self-organization and hierarchical networks in artificial intelligence root
back to Self-Organizing Maps [40] and Graph Neural Networks (GNN) [44, 14, 45,
46, 47]. These promoted the growth of network hierarchy from its own learning
and inference process. The uncertainty of the association between two nodes
creates a necessity for an adaptively-formed edge set. Such a proposal entails
more flexible modeling of complex variable-sized environment and dynamic
behaviors. This idea was theorized over a more general context in [48] as an
evolutionary fuzzy graph clustering by assigning degrees to indicate
relationships between similar nodes.

This work adopts the self-learning graph concept and introduces it into graph-
based pedestrians modeling to propose more powerful graphs that can adaptively
change, and create its structure throughout a physics kernel that computes the
higher order of interactions features to stem their evolution. The kernel
accurately and efficiently model context-aware interactive pedestrians.
Considering that graph growing is a fuzzy process and graph completion is a
NP-hard problem, the objective here is introduce a variational graph growth to
choose the local optimum solution with minimum modeling of mechanical
functions for pedestrians motions and intents.

### Efficient Graph-based Modeling

With predefined-neighborhood settings, [7, 8, 13, 49] predictors surmised that
pedestrian neighborhoods cast on a fixed grid. Moreover, they used hardcoded
proxemic distance for outlining neighborhood boundaries. The family of global
graph Structural-RNN [30], Social Attention [4], SpAGNN [33], and Fuzzy Graph
Attention [50] grow fully-connected graphs with degree-based relationships to
cluster pedestrians. They assume neighborhoods to be the global context of the
scene and start with non-fuzzy edge set but end with relational estimation
that assign different degrees to the edges, creating neurally-evaluated fuzzy
edge sets to recognize related pedestrians. Similarly, interaction graphs [17,
35, 32, 26, 28] make neural relational inference (NRI [51]) given the
heterogeneous agent dynamics. In light of these methods, we allow a greater
degree of freedom in the pedestrians social-spatial modeling by instantiating
self-learned proxemic-free criteria for saving the additional parameter tuning
and engineering effort. Contrary to interaction graphs, our approach stores
compact features in the graph. It performs neural restructuring of
neighborhoods without attributing the edges. It just encodes past and present
motion sequences for each pedestrian and replaces the initial edge-set with
sparse adjacency matrix. That is, the objective is to re-generate more
efficient graphs by means of minimizing edges without the need for an
exhaustive search through all the possible solutions.

### Graph-Structured Data Streams

Recently, Adaptive Online Learning has emerged as a new trend in pedestrian
trajectory prediction. [52] reports prediction results on portions of the ETH-
UCY datasets. We aim to advance the application of online learning over
multiple modalities of data. Unlike offline training, online learning can be
more sensitive to the catastrophic interference problem and requires a large
memory space. Data streaming application requires immediate processing and
mapping in lightweight structures. Graph kernels are useful techniques for
critical online prediction systems that model and generate predictions with
continuous evaluation of pedestrian dynamics and relationships to the
environment objects [43].

This work shows how mapping the graph to kernel can be a valid technique for
achieving online continuous learning of the scene and pedestrians motion
features in order to track their and stem future pedestrian motion relevant to
the scene structure.

### Link Prediction through Graph Recommender Systems

Link Prediction techniques estimate the relations that tie graph nodes to each
other [53, 54, 55, 56, 57]. Link prediction is eminent in recommender systems,
social networks, and biologic-ally-inspired growth networks [58, 59, 60, 61].
The link prediction quality can vary based on the goodness of nodes and edges
features. In the worst-case scenario, the Breadth-First Search (BFS), takes up
to quadratic time $\mathcal{O}(n^{2})$ time to traverse an offline graph with
$n$ nodes and complete the missing edges. This time complexity is even more
challenging in online graph streams to estimate relational heuristic over an
incomplete graph. Theoretically, there is a lack of a globally optimal
solution to the right neighborhood discretization, and there is no prior-
stated universal edge set. As explained previously, the current online
application [62, 52, 63] is limited to few pedestrians due to the large memory
consumption.

Our work is the first to combine online paradigm with social interaction
inference on incomplete spatio-temporal graphs. We coin this approach as Self-
Growing Online Graph. The pedestrian social inference problem is tackled as an
online matrix completion problem that employs variational unsupervised
technique called Nonnegative Matrix Factorization (NMF). This factorization
carries out a compact representation of nodes relationships through the online
graph. We postulate that a Self-Growing model can flexibly encode any mixture
of social and contextual features besides facilitating a scalable network
growth that we will show in our experimental results.

## Proposed Approach

### Problem Formulation

Given a set of pedestrians $\mathcal{N}$, we represent their trajectories over
time $T^{i}_{t}$ using a spatio-temporal graph $G_{t}$ at each time step $t$,
containing $\mathcal{N}$ nodes. $T^{i}_{t}$ comprises the 2D positional
trajectories $X^{i}_{t}=(x^{i}_{t},y^{i}_{t})$ and 2D head pose sequence
$V^{i}_{t}=(v^{i}_{x_{t}},v^{i}_{y_{t}})$. The i-th pedestrian is assigned a
node $n^{i}_{t}$ to store the ground-truth trajectory $x^{i}$, the 2D head
pose $v^{i}$, and temporal edge $e_{t}$ that links the node $n^{i}_{t-1}$ to
$n^{i}_{t}$. We propose $P$ adjacency matrices $A$ for all pedestrians at each
time-step and predict i-th future trajectory
$\widetilde{X}={\widetilde{x}^{iA^{1}}_{t+1},\widetilde{x}^{iA^{2}}_{t+2},...,\widetilde{x}^{iA^{P}}_{t+l}}$
per each matrix $A^{p}$. The best adjacency matrix that produces the minimum
prediction errors is then selected. $A^{P}={A^{1},A^{2},...,A^{p}}$ and
$\widetilde{x}^{iA^{p}}_{t+l}$ is the future trajectory of length t+l steps in
the future, for i-th pedestrian in the p-th Adjacency matrix proposal, given
the past observed trajectory between $x^{i}_{t}$ to $x^{i}_{t-obs}$, where
$obs$ is the observation length, including the current step.

### STR-GGRNN Framework

STR-GGRNN is a framework for processing pedestrians interactions and
trajectories as graph data streams. It includes crowd data mapping into
spatio-temporal graph $G_{t}$, and then models their spatial relationships by
completing the graph spatial edges $e_{t}$ at time-step $t$.

The framework takes pedestrians positional trajectories $X$ and encodes them
using a nested linear transformation function $\phi$, such that $W_{X}$ is [8
x 10] and $W_{\hat{X}}$ is [10 x 8]. Eventually the trajectories are encoded
as [10 x 10] as a lightweight version:

$\hat{X}=\phi(X)$ (1) $\phi(X)=W_{\hat{X}}*(W_{X}*X)$ (2)

It also encodes the 2D head pose annotations, called Vislets, $V$ using a
single transformation function $\phi$. The lightweight encoding size is [2 x
10], where $W_{V}$ is [2 x 8]:

$\hat{V}=\phi(V)$ (3) $\phi(V)=W_{V}*V$ (4)

The head pose is annotated in the ETH-UCY datasets in roll-yaw format. This is
to represent the head rotation at the back-forth axis and along the vertical
axis. The 2D poses were annotated in the radian system which describes the
angular change in head direction, such that it would be more relevant to
modeling pedestrians attention and easier for training the network compared to
the angular degree system.

Our framework then concatenates the embedded cues $\hat{V}$ and $\hat{X}$ at
the vertical axis and feed T into GGRNN:

$T=(\hat{X},\hat{V})$ (5)

The proposed spatial-temporal graph network adopts an edge-centric task, as
the graph analytics focus on predicting associations (edges) between
pedestrians. It is a central model since a single GridLSTM cell is used as the
encoder of the social pedestrians interactions. It takes graph $G_{t}$ of
$\mathcal{N}$ nodes and $\mathcal{E}$ edges, and maps it into a kernel of
fixed dimension, $K$, such that the kernel generates predicted trajectories
$\widetilde{X}$ and adjacency states between the pedestrian nodes. The
adjacency models the social interactions.

$\widetilde{X},J_{\theta}=K(G_{t}{(\mathcal{N},\mathcal{E})},H_{t}^{*})$ (6)

The Social Trajectory Recommender (STR) component is a recommender system that
performs matrix factorization to complete the Adjacency matrix.The framework
encodes the contextual influence of static features onto pedestrian trajectory
by segmenting the scene into a grid of local regions which comprises the Gated
Graph Recurrent Neighborhoods Networks (GGRNN). These regions hold the
potential contextual interactions between pedestrians and the scene structure.
They are assigned continuously over time, creating a sequence of graphs
encoded by gated Recurrent Neural Networks. Overall, the framework ends up
combining the contextual model features from GGRNN and the pedestrians social
interaction features from STR.

We will first discuss in depth the GGRNN and explain its formalization and
task. Later, we will present the formulation of the Social Trajectory
Recommender component (STR) and illustrate how the different components are
integrated into the GGRNN pipeline.

### Gated Graph Recurrent Neighborhood Network (GGRNN)

Figure 2: The full online pipeline of STR-GGRNN. The STR network encodes
Vislets $\hat{V}$ and positional trajectories $\hat{X}$ for each pedestrian
trajectory. Then maps them into social grid $f_{S}$ using $GLSTM_{nu}$. The
GGRNN network discretizes static context using $GLSTM_{O}$ into ’Visuospatial’
neighborhoods and stores pedestrian contextual awareness in $f_{O}$. At the
consequent step, STR takes $f_{O}$ and $f_{S}$ and maps them into the weighted
adjacency matrix using the NMF technique. It will generate the edge set
$\mathcal{E}$ as means of completing graph $G_{t}$ spatial edge-set while the
temporal edge-set {$G_{t+1}$, $G_{t+2}$, $G_{t+3}$} connect the spatial
instances over time. The concept of Gated Graph is depicted to the right-side
such that set of temporal graphs has a gated edge completion process according
to GridLSTM gating mechanism.

The Gated Graph Recurrent Neighborhood Network takes the static scene and
encodes it as a fixed local neighborhoods grid. It models the contextual
interactions between pedestrians and their context surrounding. This
contextual model contributes to generating future trajectories that account
for pedestrians ”context-awareness” to make plausible predictions.

Firstly, it takes the transformed Vislets $\hat{V}$ and trajectories $\hat{X}$
from the transformation functions. It assumes that motion happens over an
initially uniformly-divided square grid containing $v$ static neighborhoods.
The STR∗ variants run single GridLSTM cell $GLSTM_{\nu}$ on each graph $G_{t}$
which is encoding features $T$ and initial hidden states $h_{0}$, to generate
relative social features $f_{S}$:

$f_{S},h_{S}=GLSTM_{nu}(T,h_{0})$ (7)

In Figure 2, $CNN$ is a 2D convolutional layer used for encoding the human-
space interaction that takes a static scene image as input. A grid mask $M$ is
applied to the convoluted features. The filter depicts static space
neighborhoods that are discretized as a square grid and is uniformly-
initialized.

$C_{map}=CNN(f_{S},h_{S})*M$ (8)

In our work we encode head pose $V$ with static features $C_{map}$ to
formulate the ”Visuospatial” neighborhood representation using single GridLSTM
cell $GLSTM_{O}$:

$f_{\mathcal{O}},h_{\mathcal{O}}=GLSTM_{O}(C_{map},\hat{V},h_{O})$ (9)

The usage of GridLSTM as a multimodal feature encoder is clarified in (9). It
combines visual awareness state $V$, the scene spatial feature map $C$, and
the normally-initialized hidden states $h_{O}$, for stemming pedestrians
attention to the physical context. It stores pedestrians contextual
interaction in $f_{\mathcal{O}}$.

Eventually, GGRNN produces a final neighborhood representation, $F$, combines
the outputs of GLSTMν with

GLSTMO, which are static features grid with social features grid, static scene
map and Vislets again:

$F=f_{S}*f_{\mathcal{O}}^{\prime}$ (10)

### Social Trajectory Recommender (STR)

In this section, we formalize the proposed model for recommending social
trajectories given a band of estimated neighborhood proposals. We coin
variational modeling as Social Trajectory Recommender. The proposals suggest
several unique edge sets to connect pedestrian nodes. Then it selects the best
neighborhood proposal, which generates minimum prediction errors, among other
proposals.

Figure 2 shows the detail steps for the recommendation mechanism to achieve
deep relational inference between pedestrians. The proposed mechanism has a
customized design relevant to the features set included in our model versions.
The kernel $K$ generates the social interaction states $H_{t+1}$ and future
positional predictions $\widetilde{X}$. Based on STR-GGRNN and ST-V model
variants, the kernel uses $f_{\mathcal{O}}$ and $f_{S}$ to calculate each
pedestrian adjacency state. As such, Eq. (6) becomes:

$\widetilde{X},H_{t+1}=K(f_{S},V,H_{t}^{*})$ (11)

Here, $K$ calculates the soft attention over social and contextual interaction
features at one hand, and calculate their gradient in relevance to the static
map at the other hand:

$\displaystyle\hat{F}=\phi(F)=C_{map}*((W_{v}*[f_{S},\hat{V}]+b_{v})*(W_{r}*F))$
(12) $\displaystyle
J_{\theta}=(\frac{d(f_{S}*W_{v}||f_{\mathcal{O}})}{df_{\mathcal{O}}})$ (13)
$\displaystyle J_{\theta}=ReLU(J_{\theta})$ (14)
$\displaystyle\widetilde{X}=MLP(J_{\theta})=W_{o}*(W_{c}*J_{\theta})$ (15)

$\hat{F}$ holds a final neighborhood representation. It combines the outputs
of GLSTMnu with GLSTMO, which are static features grid with social features
grid, static scene map and Vislets again. This ensures a rich multi-modal
feature representation and strengthens the intertwining between contextual and
social interactions. But according to our basic model $LSTM_{O}$ and ST-GGRNN,
the kernel $K$ in Eq. (6) has a limited formulation that only generates future
trajectories without the social recommendation or contextual features, hence
this kernel version takes parameters as follows:

$\widetilde{X},H_{t+1}=K(f_{S},H_{t}^{*})$ (16)

In the variants that exclude social inference, $K$ calculates the soft
attention over social and contextual features at one hand in the same way as
previous variants,however, it extrapolates future trajectories from
convoluting static map with social neighborhoods to create a relevance effect
between pedestrians social interactions and their interactions with the scene
features:

$\displaystyle\hat{F}=\phi(F)=C_{map}*((W_{v}*[f_{S},\hat{V}]+b_{v})*(W_{r}*F))$
(17) $\displaystyle J_{\theta}=(W_{v}*F+b_{v})*C_{map}$ (18) $\displaystyle
J_{\theta}=ReLU(J_{\theta})$ (19)
$\displaystyle\widetilde{X}=MLP(J_{\theta})=W_{o}*(W_{c}*J_{\theta})$ (20)

After generating future trajectories, $\hat{F}$ now is used to compute scaled
soft-attention weights. STR model will tune the influence of each region to
update contextual features and evaluates the social relationships strength. It
deploys the scaled self-attention mechanism [64] (as illustrated in Eq. (21).
Attention coefficient $a$ considers the human-human interaction features and
the human-space interaction features:

$a=\frac{Softmax(\exp{(\hat{F})})}{\Sigma\exp{(\hat{F})}}$ (21)

Given the $i$th pedestrian trajectory features, neighborhood $nu^{i}_{t}$ of
i-th pedestrian has 1 or more j pedestrians considered as neighbors to i:

$nu^{i}_{t}=\\{(i,j)\\}^{+};\quad|nu^{i}_{t}|<=|\mathcal{N}|$ (22)

Moreover, neighborhood boundaries at pedestrian $i$ are defined by the set of
edge pairs that connect pedestrian nodes to other nodes in the graph. Online
graph completion is an NP-hard problem, so we rely on a stochastic adjacency
matrix generation mechanism that generates one adjacency proposal at a time-
step. During back-propagation, it evaluates the estimated adjacency proposal
with all the possible permutations for that crowd. It optimizes the objective
function responsible for selecting neighbors based on minimizing the L2-Norms
resulted from the best adjacency matrix. All the proposals yielded from Eq. 22
for adjacency matrix belongs to the solution space $\Omega$:

$\Omega_{nu_{t}}=\\{nu^{i}_{1},nu^{i}_{2},...,nu^{i}_{nxn}\\}$ (23)

Selecting the best adjacency will lead to a local optimum solution for the
neighborhood construction, as the best optimum is not known, and a brute-force
approach towards testing all the possible permutation is of exponential cost
to the deployment. So our method considers $\Omega$ a partially-observed
variable and resorts to the non-exhaustive graph search mentality.

The static features $f_{\mathcal{O}}$ are weighted by soft-attention
coefficient $a$ using the soft-attention mechanism in [65]:

$f_{\mathcal{O}_{t+1}}=a*f_{\mathcal{O}_{t+1}}$ (24)

The attention weightage manifests pedestrian relationships have various
degrees of strength. Inspired by the neural factorization technique [66] to
factorize spatio-temporal graph edges, we establish a deep mechanism for
neighborhoods that is aware of the static and the social constraints. Again,
the best setting for neighborhoods is not fully-observable. We estimate
pedestrian relationships weight based on relative visual attention and
relative spatial motion features to define their neighborhoods. We introduce
the Nonnegative Matrix Factorization (NMF) into our pipeline for a proper
approximation of social relations from the neural attention features and
static map. The reconstruction yields a more compact and efficient adjacency
representation to be carried to the next time-step, such that $A_{0}$ is the
initial $A$ matrix (all ones) of size [10 x 10] for 10 pedestrians in the
scene, $W_{a}$ is assigned attention $a$, $H_{t}$ is assigned the weighted
hidden states:

$W_{a},H_{t}=\textit{NMF}(a,C_{map}C_{map}^{\top})$ (25)

$A^{P}=W_{a}/max(W_{a})$ (26)

$W_{a}$ is a square matrix of the frame max-size (i.e.max number of
pedestrians). We select $W_{a}$ as it approximates the motion features in its
weighted version and normalizes it to 1. $W_{a}$ maps directly to adjacency
states of range [0,1], as the edge weights are nonnegative values.

The NMF reconstructs a compact version of the input features to approximate
the social interaction patterns between pedestrians. Using the downscaled
features enhances the scalability within an online pipeline.

Finally, within STR∗ recommender models we apply Softmax function to node
hidden states. This will transform nodes states into continuous space under
the interval [0,1]:

$A_{t};\quad min(||\quad X_{i}-\widetilde{X}^{iA^{P}}\quad||_{2})$ (27)

We display in (28) the formal definitions of the proposed mechanisms for
autonomous relational modeling, including ours (i.e.STR∗):

$A_{t}=\begin{cases}1/(||x_{i}^{t}-x_{j}^{t}||_{2});\quad M_{SGTV}\\\
Softmax(W*H_{t});\quad MCR^{*}\\\ min(||\quad
X_{i}-\widetilde{X}^{iA^{P}}\quad||_{2});\quad STR^{*}\\\ \end{cases}$ (28)

The Self-Growing model (SGTV) [36], which was the first proposed method for
growing the edge set $SGTV$, relied on hard-attention weights to express the
importance of relationships. The weights were calculated using pedestrian-wise
Euclidean distances. However, their relational inference outcomes are
unexpected, and the neighborhood modeling would change for each run. The
ultimate degree of freedom found in such data-driven modeling makes it
difficult to evaluate their modeling effectiveness.

Pedestrian states are updated with the selected best adjacency state to
reflect upon the STR adjacency outcomes, $H^{*}_{t}$ gets passed to the
following time-step:

$H^{*}_{t}=A_{t}*H_{t}$ (29)

## Experiments

### Training Setup

The learning objective is formulated as minimization of Euclidean errors
between the p-th predicted trajectory $\widetilde{X}$ and the ground-truth
trajectory $X$, given the locally-optimal adjacency proposal (edge set)
$A^{p}_{t}$, such that there are P proposals:

$\mathcal{L}=\underset{A^{p}_{t}}{argmin}||\quad\widetilde{X_{t}}-X_{t}^{p}\quad||_{2}$
(30)

We empirically set the number of samples for variational trajectory and
adjacency samples (P) to 10/20/100/200. We did not observe a change in the
prediction accuracy. As an acceleration of our code, we deploy the variational
parts over multi-threads to simultaneously sample future trajectories.
Eventually, the code selects the minimum global Euclidean error based on the
least erroneous predicted trajectories. Accordingly, the proposal with minimum
Euclidean errors is the sub-optimal Adjacency matrix $A$, which sets the
neighborhood boundaries for each pedestrian at time-step $t$ and produces the
least prediction errors.

The prediction errors are reported in meters over interpolated real-world
coordinates in ETH-UCY dataset. We run experiments over two settings for
observation/prediction lengths. In the first part, we observe 8 frames (3.2
seconds) and predict 12 steps (4.8) seconds. In the second part, we observed 4
frames (1.6 seconds) and predicted the next 8 frames (3.2 seconds). We
implement all model variants using TensorFlow (1.13) [67]. The experiments are
deployed in a leave-one-out on desktop Intel® Xeon(R) CPU of frequency
3.50-GHz using Ubuntu 16.04 at a learning rate of 5e-3, decay rate of 0.95 and
a dropout of 0.80. The maximum size variable (maxSize) of pedestrians is also
set to 20 per frame. We repeated the testing experiments 10 times over each
set to verify the errors stability. $GLSTM_{o}$ and $GLSTM_{nu}$ (outputSize)
is 8 and embedding size is 128. Size of $h_{S}$ and $h_{O}$ is [20 x 128]. CNN
encodes the static scene at compressed size [8x8] for compactness.

### Evaluation Metrics and Baselines

Similar to [68, 7], we use the following Euclidean average errors:

  * •

Average Displacement Error (ADE): measures prediction errors along the time-
steps between the predicted trajectory and the ground-truth trajectory as
follows:

$\frac{\sum_{i=1}^{N}\sum_{j=1}^{l}||(\widetilde{X_{i}^{j}}-X_{i}^{j})||_{2}}{N*|T|},$
(31)

  * •

Final Displacement Error (FDE): measures prediction errors at the final time-
step between the predicted trajectory and the ground-truth trajectory as
follows:

$\frac{\sum_{i=1}^{N}||(\widetilde{X_{i}}-X_{i})||_{2}}{N}\quad$ (32)

#### Deterministic Models

  1. 1.

Trajectron++ [69]: An edge-centric spatio-temporal LS-TM graph. We refer to
their deterministic version. The model encodes contextual map and social
interactions for heterogeneous dynamic agents of variably-sized environments.
Therefore, its comparison with ST-GGRNN variant is considered valid.

  2. 2.

S-LSTM [7]: Dedicates LSTM for every pedestrian, and pool them given an
empirical setting for the neighborhood.

  3. 3.

$LSTM_{O}$: Online GridLSTM model that only takes the positional trajectories
$X$ with a fixed temporal window of 8 time-steps.

  4. 4.

GGRNN-V: This variant withdraws the social recommender section and includes
only the static context neighborhoods. It highlights scenarios wherein
pedestrians are not necessarily socialising (i.e.posing direct impact on each
other) or there is a decreased crowding. At its best, this variant models
trajectories as an effect of reaching the target place and considering
pedestrians visual awareness of the static surroundings.

  5. 5.

ST: This is the fully-connected graph model. It does not incorporate Vislets,
static context neighborhood components or social recommendation

  6. 6.

ST-GGRNN: This follows the same pipeline of ST variant, with incorporation of
the static context neighborhoods component (GGRNN).

  7. 7.

ST-V: This is the fully-connected graph model with Vislet being incorporated
for each node. However, it does not incorporate either of the static context
neighborhood components and social recommendation.

#### Stochastic Models

  1. 1.

S-GAN [5]: Social GAN, a variational Encoder-Decoder architecture for
generating future predictions using GAN network.

  2. 2.

MX-LSTM [68]: deployed 2D head poses in the model to encode the Visual Field
of Attention (VFOA) in a cone-shaped looking span, such that the latter
determines pedestrians visual attention scope and can substitute the looking
angle feature.

  3. 3.

Trajectron [31]: A spatio-temporal graph for social modeling of variably-sized
environments. The model predicts a band of trajectories and selects the best
future trajectories the same as in the S-GAN model.

  4. 4.

Social-STGCNN [37]: A Graph Convolutional Network (GCN) that estimates
relationships using a pedestrian clustering technique to assign weights given
the euclidean proximity between pedestrians pairwise.

  5. 5.

STR-V: a model variation that applies social neighborhood selection knowing
pedestrians location and their visual angle, $VS$ (i.e.Vislets). This is to
assess the plausibility of neighborhoods generated by the recommender
technique.

  6. 6.

STR-GGRNN-V: By incorporating the Vislets, the model enriches the feature
representation and forms a prior knowledge for the recommender technique so to
assess the neighborhood selection with respect to the static context that draw
its influence on pedestrians trajectory and social interaction.

TABLE I: Analysis of the reported ADE/FDE errors across state-of-the-art
models on ETH & UCY video datasets. $\downarrow$ denotes decrease % and
$\uparrow$ denotes the increase % in our models prediction ADE/FDE over
Trajectron++. Respectively, STR-GGRNN-V
achieves($\downarrow$84%)/($\downarrow$85%) while ST-GGRNN
achieves($\downarrow$51.1%)/($\uparrow$24%). ST-GGRNN is the fully-connected
graph, while STR-GGRNN-V is the recommender-based graph.

| Stochastic models
---|---
Dataset | S-GAN | MX-LSTM | Trajectron | Trajectron++ | Social-STGCNN | ST-GGRNN | STR-GGRNN | ST-GGRNN-V | STR-GGRNN-V
ETH-Univ | 0.81/1.5 | – | 0.59/1.14 | 0.39/0.83 | 0.64/1.11 |  0.29/1.192 | 0.35/0.80 | – | –
Hotel | 0.72/1.61 | – | 0.35/0.66 | 0.12/0.21 | 0.49/0.85 | 0.32/1.150 | 0.39/0.88 | – | –
Zara1 | 0.34/0.69 | 0.59/1.31 | 0.43/0.83 | 0.15/0.33 | 0.34/0.53 | 0.31/1.154 | 0.47/0.95 |  0.10/0.84 | 0.12/0.14
Zara2 | 0.42/0.84 | 0.35/0.79 | 0.43/0.85 | 0.11/0.25 | 0.30/0.48 | 0.30/1.160 | 0.40/0.91 |  0.10/0.84 | 0.12/0.143
Zara3 | 0.45/1.12 | – | – | – | – |  0.31/1.175 | 0.41/0.90 | – | –
UCY-Univ | 0.66/1.44 | 0.49/1.12 | 0.54/1.13 | 0.20/0.44 | 0.44 / 0.79 | 0.27/1.630 | 0.40/0.92 |  0.10/0.86 | 0.13/0.15
AVG | 0.47/1.02 | 0.48/1.07 | 0.47/0.92 | 0.18/0.40 | 0.44/0.75 | 0.23/1.165 | 0.40/0.89 |  0.10/0.85 | 0.123/0.144

Deterministic models
---
Dataset | LSTMO | Trajectron++ | S-LSTM | GGRNN-V
ETH-Univ | 1.76/3.87 | 0.71/1.68 | 0.50/1.19 |  0.46/1.55
Hotel | 0.81/1.78 | 0.22/0.46 | 0.24/0.56 | 0.45/1.56
Zara1 | 1.20/2.86 | 0.33/0.77 | 0.29/0.72 | 0.45/1.54
Zara2 | 2.25/5.14 | 0.23/0.59 | 0.27/0.67 | 0.47/1.51
Zara3 | 0.96/2.38 | – | 0.84/1.80 | 0.48/1.24
UCY-Univ | 0.22/0.53 | 0.41/1.07 | 1.30/2.38 | 0.47/1.56
AVG | 1.06/2.44 | 0.38/0.92 | 0.66/1.36 | 0.47/1.50

### Quantitative Analysis

Table I lists existing state-of-the-art models ADE/FDE errors. We observed a
general tendency across all models (Deterministic and Stochastic) to have the
lowest ZARA subsets’ errors and approximate errors over Hotel and ETH subsets.
This tendency indicates that these models customize performance during the
offline training to specific dynamic crowds patterns. GGRNN-V was used where
Vislets $V$ annotation was available, i.e.UCY and Zara. It performs similarly
to GGRNN , with slightly higher ADE by 14%. ST-GGRNN shows improvements over
the former variants as it generates fully-connected spatial graphs.

Fully-connected graphs are not be suitable for less interactive crowds, yet
ST-GGRNN ADE outperforms Trajectron under ETH and Hotel. In contrast, it
becomes comparable with the spatio-temporal baselines for the rest of the
datasets. By observation, ETH and Hotel show crowds that conduct motion
according to individual targets without persistent social interactions.
Instead, such crowds are influenced by the static context. Noticeably, under
Zara sets and UCY, the social and contextual factors impact pedestrians, so
STR-GGRNN has a comparable performance with MX-LSTM given that the social
relational inference does not take Vislets in this variant. That comparison
leads us to verify the NMF-based relational inference, which designated a true
capability of modeling interactions between pedestrians. Similar to ST-GGRNN,
STR-GGRNN generates dense spatial graph with the visual cue and slightly
improve ADE, however, the ADE/FDE discrepancy remains considerably large. STR-
GGRNN-V achieves better improvements than STR-GGRNN, as the former reduces the
metric discrepancy by lowering FDE significantly. The selective social
inference procedure has better impact on the overall performance when there
are additional cues that model pedestrian intention (i.e.Vislets & static
map), and thereby STR-GGRNN-V delivers the best predictions over other spatio-
temporal state-of-the-art.

Tables II and III compare STR-GGRNN best and overall performance errors along
with the most recent state-of-the-art. Table II lists the methods in
chronological order and illustrate pixels resolution. The most recent
baselines such as Social-WaGDAT and Evolve-Graph reported their results on
1/5th resolution order, while STR-GGRNN was tested on SDD data with full pixel
resolution and yielded comparable accuracy. Additionally, to compare with
STGAT and DAG-NET, STR-GGRNN is trained on SDD meter annotations. Under the
pixels annotation STR-GGRNN shows fair improvements and under the meters
annotation, it shows an outperforming improvements.

TABLE II: Comparing best results achieved in recent graph-based models with the proposed models at full resolution. The observation/prediction length in $M_{SGTV}$ is 1.67/3.2 seconds, while in the rest of methods it is reported at 3.2/4.8 seconds. Model | Best | AVG
---|---|---
S-LSTM [7] | 9.85 | 33.2/56.4
Desire-SI-IT4 [70] | – | 35.4/57.6
S-Attn [4] | – | 33.3/55.9
CAR-NET [71] | – | 25.72/51.80
GRE-MC-10 [72] | 22.35 | 27.0/43.9
$M_{SGTV}$ [36] | 9.81 | 24.46/59.53
NRI[51] | – | 25.6/43.7
Trajectron++ [69] | – | 24.3/40.1
Social-WaGDAT [26] | – | 22.52/38.27
Evolve-Graph [35] | – |  15.3/27.9
STR-GGRNN | 9.67 | 17.23/24.24
ConvLSTM[73] | – | 14.35/26.85
TABLE III: Comparing ADE/FDE results achieved in STR-GGRNN with the recent spatio-temporal graphs, the models are trained on Stanford Drone Dataset meters annotation [19].  Model | Best | AVG
---|---|---
STGAT[74] | – | 0.58/1.11
Social-Ways[75] | – | 0.62/1.16
DAG-NET[76] | – | 0.53/1.04
STR-GGRNN | 0.04 |  0.05/0.07

### Qualitative Analysis

(a)

(b)

(c)

(d)

(e)

(f)

Figure 3: (a) Prediction Bands: 100 sampled trajectories per pedestrian in
frame (7961). (b). Frame 8177 of Zara1 scene. (c) Adjacency proposal 2D
histogram for frame in (a). (d) Adjacency proposal heatmap for frame in (b).
(e) Maximum values in the adjacency matrix heatmap of (d), out of 6
pedestrians in (b), 4 pedestrians were taken as highly influential to each
other. Those were in the proximity to Zara shop entrance. (f) Variations in
weight estimation density for 38 pedestrians over 4 frames. The variations
indicated that adjacency weights increased over time due to the increase in
relational estimation confidence as the STR consequently modeled and mapped
the social interactions to the adjacency matrix.

We visualize the same experiment several times to see the extent of
variational bands. For clarity, Figure 3a displays one band of 10 variational
predicted trajectories for pedestrian (ID:128), in Zara1, frame (7961). The
variational bands are compact and closer to the ground-truth trajectory than
the variational prediction of S-GAN, which are more divergent. Figure 3c
visualizes the 2D histograms of the best-proposed adjacency under the same
frame, containing only a single pedestrian. The selected proposal is shown in
the figure. However, there are 10 2D histogram plots, each corresponds to [10
x 10] adjacency matrix $A^{p}_{t}$. As discussed before, the edges are
assigned weights between [0,1] inclusively. The lighter shades represent
higher weights, which means a higher degree of association strength. The
yellowish squares at the line indicate a high density of connections.

## Time and Space Complexity

We observed a log-polynomial growth rate in both time and memory online
training curves. This was the general pattern under both models. Figure 4
visualizes the pattern in sampling time over different rates ranging from 1000
to 20K trajectories per single frame of 20 pedestrians. While Trajectron
starts high, it yields a steadily linear running time. STR-GGRNN sustains
logarithmic curve for sampling sizes up to 10K samples. Thereafter, the
sampling time increases in a step-wise polynomial pattern such that it is
asymptotic to Trajectron curve.

Figure 4: Sampling time curves of Trajectron [31] vs. Our Kernel. The graph
plot visualizes an approximate time complexity functions. The X-axis is the
number of sampled trajectories and Y-axis is the sampling time in seconds.

The internal stages of training, such as generating adjacency proposals, takes
$\sim$100 ms for STR (including the kernel $K$ sampling) to make 10
recommendations for a neighborhood of 10 pedestrians. It takes $\sim$360ms to
choose the best proposal.

TABLE IV: Mean sampling time in our model Vs. Baselines best performing model
over different sampling counts per frame, given that future trajectories are
sampled at 12 steps ahead on Intel® Xeon(R) CPU E5-1650 v2 @ 3.50GHz with 16GB
memory. Baseline models: Social GAN [5], Social LSTM [7] and Trajectron [31]
were re-evaluated on our CPU to make fair comparisons.

No. Sample | 1K | 2K | 10K | 20K
---|---|---|---|---
S-GAN | 7.10s | 10.70s | 16.69s | 33.87s
Trajectron | 0.22s | 0.23s | 0.36s | 0.52s
S-LSTM | 8.07s | 15.67s | 78.37s | 155.67s
S-Attn | 17.30s | 34.04s | 173.89s | 342.55s
STR-GGRNN | 0.03s (86x) | 0.10s (56x) | 0.15s (58x) | 0.49s (5.7x)

Table IV lists the sampling time required at the sampling stage. At 20K
trajectories per frame, the kernel sampling time in addition to recommending
the best adjacency, become comparable to Trajectron, which means that our
method can scale up by 100x more trajectories per entire frame. During
initialization, our algorithm takes $\sim$3.54 seconds to start with the 1st
batch.

TABLE V: Time and Memory space consumption summary for 8/12 steps
(i.e.observation/prediction lengths) and at sampling rate of 10K trajectories
per frame on CPU.

Model | Memory (MB) | Train Time (sec.) | Val. Time
---|---|---|---
LSTMO | 422 | 2.30$\pm$[0.16, 1.00] |  $\sim$2.26
STR-GGRNN | 500 | 2.90$\pm$1.00 |  $\sim$2.30

Table V summarizes the average statistics of time & space occupied for a
single run of the algorithm. The total time required to complete the social
recommendation and evaluating the trajectories band for all pedestrians is
$\sim$0.37 seconds with an interval of $\pm$ 0.10 seconds difference for
several runs and 0.30-second increase from one batch to another while
training.

## Ablation Study

TABLE VI: Ablation Study. Performance of various model components for 20 pedestrians in the scene. Dataset | ST | STR | ST-V | STR-V
---|---|---|---|---
ETH | 0.38/1.26 | 0.40/1.23 | – | –
Hotel | 0.38/1.29 | 0.38/1.22 | – | –
Zara1 | 0.37/1.15 | 0.35/1.23 | 0.86/2.02 | 0.88/2.02
Zara2 | 0.36/1.24 | 0.37/1.29 | 0.89/2.02 | 0.88/2.02
Zara3 | 0.38/1.23 | 0.37/1.29 | – | –
UNIV | 0.41/1.29 | 0.36/1.23 | 0.86/2.02 | 0.88/2.02
AVG | 0.38/1.24 | 0.37/1.25 | 0.87/2.02 | 0.88/ 2.02

To verify the components impact on the overall performance, ablative
experiments were performed to observe different features impact on the social
modeling effectiveness. Noticeably, running STR component performs better
given only the positional trajectories as in STR and ST than it does when
combined with head poses. STR-V model performed much worse than model STR-
GGRNN which combines static context. This illustrates that the head poses
alone were not sufficient feature composition for generating effective social
recommendation, unless it is combined with the static context map. This means
that STR was more capable of modeling individuals social interactions given
their visual awareness to the static context. The head pose was more
beneficial when being used as an indicator of the static environment impact
than when used as pedestrians influence indicator. In fact, visual span
represents pedestrian observability of other pedestrians, yet, it does not
form a robust basis for estimating pedestrians attention to each other unless
this observability is combined with motion features.

## Graph Efficiency Analysis

A thorough statistical analysis has been conducted to visualize STR algorithm
behavior compared to fully-connected graph (fullGT) and Trajectron approach.

Observing the whiskers boxplot in Figure 5b, STR produces much lesser dense
graphs than $SGTV$ [36] which yields a fully-connected (complete) graph. The
y-axis represents edge counts (graph cardinality degrees). For a graph
consisting 50 nodes at once, STR generates variational edge sets that range
between 180 and 260 non-zero edges. Even though $SGTV$ generates weighted
adjacency matrix, it only generates non-zero edges and therefore induces 2500
weighted edges.

Figure 5c shows the density of the 75th percentiles of STR to fullGT graph
cardinality. The highest density was found under 44% and 52% percentiles,
which means that the STR graph cardinality is smaller in size by almost half
of the fully-connected graph case for a maximum of 20 pedestrians. Figure 5d
shows that NMF construction of non-zero weighted edges was more efficient for
higher pedestrian contexts. While the visualization is based on crowd size of
20 pedestrians, assuming a fully-connected graph is an inefficient design
approach as in a big crowd pedestrian influence gets hindered by several
factors such as crowdedness impact and limited visual awareness to immediate
approaching pedestrians. Hence a fully-connected ground-truth graph is a
partially applicable option as it can work for smaller crowd size. Over a
crowd size of 9 pedestrians, STR assumes connectivity over 20 pedestrians. It
ends up training a model with larger graph size than the ground-truth crowd.
However, NMF generates sparse matrix that produces lesser falsely-assigned
edges.

For 9 pedestrians, STR to fullGT cardinality ratio was $\sim$ 2.50x. This
means that STR generated 2.5x more edges. For 10 pedestrians, STR generated 1x
less edges, while for exactly 20 pedestrians, STR to fullGT cardinality ratio
was down to 0.65x. For 50 pedestrians, STR ended up generating sparser graphs
as it assumed that connectivity covers up to 20 pedestrians at one time-
instance. The resultant graph ended up with $\sim$ 0.92x fewer edges compared
to fullGT graph. In percentage terms, at the first place, the reduction in
graph cardinality was up to 86% fewer edges over 200 STR proposal. At the
second place, the reduction was up to 100% fewer edges and this reduction was
scored over nearly 150 STR proposals.

Figure 5b measures the cardinality degree in Trajectron graph [31]. It yields
the least cardinality, given that it pools pedestrians based on the spatial
proximity. This shows that Trajectron is more conservative in assigning edges
between pedestrians, generating a minimal graph to model the social
interactions. For a scene containing 15 pedestrians, Trajectron generates edge
sets of size ranging between 6 and 20 edges, while STR generates a size
ranging between 200 and 260 edges.

(a) 25th/75th Whiskers Box Plot SGTV vs. STR

(b) 25th/75th Whiskers Box Plot Trajectron vs. STR

(c) 75th percentiles density figure. x-axis displays percentage of non-zero
edges out of 400 edges

(d) The ratio of edge cardinality under STR to cardinality under fully-
connected Ground-truth graph.

Figure 5: Graph Cardinality. Statistical visualization of Self-Growing STR
mechanism.

## STR Stability and Integrity

The proposed framework deploys the Nonnegative Matrix Factorization to be the
edges construction mechanism. It works as a recommender system for completing
the online Adjacency matrix, which is realized by taking the downscaled
approximated features $W$ (assigned an initial attention matrix), and the
components part $H$ (assigned the hidden states of pedestrians). Since this
neural reconstruction is a divergent process and that the optimal adjacency
matrix $A^{*}$ is not observable, the Nonnegative Matrix Factorization of the
best adjacency is an NP-Hard problem that yields local optimal adjacency
modeling. Similar case demonstrating the graph-structured NP-hard problems
appears in [77] which exploits graph neural traversal given a complete set of
edges that is weighted as a local optimum adjacency matrix. In our graph case,
the output will be the reconstructed attention weights $W^{\prime}$ and hidden
states $H^{\prime}$. $W^{\prime}$ is scaled to 1 and used as the weighted
adjacency matrix $A_{0}$ to represent the weighted social interaction.

In the following lemma, the adjacency matrix (A) is the latent variable since
it is not fully-observable. The priors, features matrix W (represents the
edges attention weight) is assigned ($\hat{F}$), and the components matrix H
is assigned ($C_{map}$) are fully-observable and set a-priori, so the
reconstruction of $A$ is conditioned by $H$, $W$ and a nonnegative $A_{0}$
that is initialized to ones. The adjacency at any index and at any instance in
time remains conditioned by the priors.

The Null hypothesis $h_{0}$ indicates that bounding matrix $A$ by a
distribution-free distribution $H$ leads at the end to a Normal distribution:

$h_{0}:\quad A_{(i,j)}\in P(W_{(i,j)}|H_{(i.j)},A_{0})\sim G(\mu=0,\sigma=1)$
(33)

The Null hypothesis $h_{0}$ also indicates that matrix $A$ always obey some
parametric distribution which can be conveyed as a Gaussian distribution
$G(\mu=0,\sigma=1)$.

On the other hand, the alternative hypothesis $h_{1}$ says that NMF generates
variational results which cannot be conveyed by the normality assumption.
Therefore, the distribution-free assumption represents a wider set of
distribution that can better model the social interaction.

$h_{1}$ represents a more generic modeling of pedestrians adjacency
(occupancy) states, of which the Gaussian distribution bounding conveys a
limited part of the social interaction modeling:

$h_{1}:\quad A_{(i,j)}\in P(W_{(i,j)}|H_{(i.j)},A_{0})\sim H$ (34)

By visually observing the Density function in Figure 6, a plot of Adjacency
matrices over 400 runs of NMF algorithm, the density values indicate mostly
sparse matrices with the highest density of 0s and a narrow span of nonzero
weights that have $\leq 2000$ occurrences, which gives the impression of
normally-based adjacency and supports the Null hypothesis $h_{0}$.

Figure 6: Density histogram of Adjacency weights, designates graph edges
density and weight concentration values.

This designates that all estimated adjacencies by NMF will always obey the
normality condition, such that the estimated values will always be small and
the density function is concentrated around zero. The probability of any
reconstructed features using NMF obey a univariate Gaussian distribution.

On the other hand, observing the loss curves reveals what can be a more
convenient distribution of pedestrian trajectory data at its entirety. As the
loss function is set as L2-Norm, the ADE curves in Figures 7,9,8 can be
considered for analyzing the predictor models performance on one side, and on
the other side, they can be used to analyze the regression pattern.

The STR-GGRNN ADE curves regressions are normally distributed, while the
GGRNN-V curves regression pattern designates a levy-stable distribution. The
latter distribution is clearly designated by GGRNN and ST-GGRNN model under
the SDD training curves.

This variation in predictive model regressions, shows that the normality
assumption cannot apply to all the tested contexts. Under SDD, the pattern
shows a range of step-like, stable, and normal regressions, while under ETH-
UCY, there were consistent appearance of normal regressive curves.

(a) Average Displacement curves under GGRNN model over the 1st epoch round of
online training. Errors are reported in meters.

(b) Average Displacement curves under GGRNN-V model over the 1st epoch round
of online training. Errors are reported in meters.

Figure 7: ADE curves under GGRNN and GGRNN-V models shows the step-wise
function pattern over ETH-UCY dataset. The step-wise pattern implies that
Gaussian-based assumption may not be the best and generic distribution to fit
the predictive model patterns. Therefore, distribution-free hypothesis is a
more proper assumption for trajectory predictions generated by our models.

(a) STR-GGRNN curves

(b) GGRNN curves

(c) STR-GGRNN curves

(d) GGRNN curves

Figure 8: ADE curves reflect the step-wise and stable patterns over SDD. These
suggest that the proposed predictor model behavior cannot be fit under
Gaussian distribution and is best described as a model-free method.
Distribution-Free assumption for such a predictor system is a more generic
hypothesis to describe the model performance.

Overall, the proposed model was trained as a model-free method by taking
updates immediately. There are no assumptions made before training and
estimation about the distribution parameters/type that convey the adjacency
modeling, nor there was any parametric mapping of hidden states onto a
parameters vector [7, 4], therefore, the proposed predictive models
performance is better understood under distribution-free hypothesis. In this
case, the alternative hypothesis $h_{1}$ can provide a more generic
probabilistic perception of the predictive model.

While STR-GGRNN-V performance obeys the normal distribution pattern, other
model variants represented different patterns that are outside the normal
distribution category. As indicated by the predictor model performance in
Figures 7a – 8d. These figures show stable function and step-wise function
curves in STR-GGRNN and GGRNN models. In the literature, the normality
assumption was always set as the prior knowledge to eliminate the prediction
problem and ensure the predictions integrity. That is to simplify the
probabilistic modeling under dynamic interactive systems. Now, it is safe to
conclude that the normality assumption (Null hypothesis $h_{0}$) is partially
applicable to the predictor systems application. It is proper to assume
distribution-free prediction patterns on pedestrian trajectory to perceive the
predictors performance. Considering that STR-GGRNN and STR-GGRNN-V models
includes an unsupervised adjacency estimation using NMF and it follows the
Null hypothesis, the STR-GGRNN model yields a prediction behavior that is non-
Gaussian. This means the model-free techniques can be modeled using a
probability distribution that is not necessarily Gaussian over the human
trajectory all the time. So to have a general perspective, the trajectory
prediction model can be formulated without a specific distribution assumption
assumption and generate useful predictions.

(a) STR-GGRNN curves

(b) GGRNN curves

Figure 9: Average Displacement curves under ST-GGRNN model over the 1st epoch
round of online training. Euclidean errors are reported in Pixels. The ADE
curves are generated at frames of full resolution for Death Circle 4 sets.

## Conclusion

In this work, we presented STR-GGRNN, a framework for adaptive social
relational inference, through online nonnegative matrix factorization as a
data-driven graph-completion task. Our model mixes local contextual modeling
with the global social modeling of crowd interactions without relying on a
predefined proxemics threshold. NMF is an NP-hard problem, so theoretically,
it is proven to reach a sub-optimal solution of the best neighboring
recommendation. Currently, the approach selects best adjacency with log-
polynomial time-complexity. Integrating social inference given rich enhanced
interactions and neighborhoods representation, constitutes for prediction
accuracy outcomes and withdraws the exhaustive search of optimal neighborhood
problem. Experimental results showed significant improvement in future
trajectories prediction. It reduced errors down to 10cm on average. Although
the adjacency matrix assumes a fixed scene size, the model is proxemic-free
and the adjacency size is fitting for a moderately-crowded environment. As
future work, we plan to model adjacency directly on the graph without mapping
to fixed-size matrices. We also plan to extend the testing to heterogeneous
crowd graph given the learned knowledge from homogeneous crowds, wherein the
adaptive online learning has higher potential.

## References

  * [1] S. van Steenkiste, M. Chang, K. Greff, and J. Schmidhuber, “Relational Neural Expectation Maximization: Unsupervised Discovery of Objects and their Interactions,” in _International Conference on Learning Representations_ , 2018. [Online]. Available: https://openreview.net/forum?id=ryH20GbRW
  * [2] F. Bartoli, G. Lisanti, L. Ballan, and A. Del Bimbo, “Context-aware trajectory prediction,” _arXiv preprint arXiv:1705.02503_ , 2017.
  * [3] T. Fernando, S. Denman, S. Sridharan, and C. Fookes, “Soft+ hardwired attention: An lstm framework for human trajectory prediction and abnormal event detection,” _Neural networks_ , vol. 108, pp. 466–478, 2018.
  * [4] A. Vemula, K. Muelling, and J. Oh, “Social attention: Modeling attention in human crowds,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2018, pp. 1–7.
  * [5] A. Gupta, J. Johnson, L. Fei-Fei, S. Savarese, and A. Alahi, “Social gan: Socially acceptable trajectories with generative adversarial networks,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 2255–2264.
  * [6] D. Helbing and P. Molnar, “Social force model for pedestrian dynamics,” _Physical review E_ , vol. 51, no. 5, p. 4282, 1995.
  * [7] A. Alahi, K. Goel, V. Ramanathan, A. Robicquet, L. Fei-Fei, and S. Savarese, “Social lstm: Human trajectory prediction in crowded spaces,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2016, pp. 961–971.
  * [8] B. Cheng, X. Xu, Y. Zeng, J. Ren, and S. Jung, “Pedestrian trajectory prediction via the Social-Grid LSTM model,” _The Journal of Engineering_ , vol. 2018, no. 16, pp. 1468–1474, 2018.
  * [9] F. Yang, H. Saikia, and C. Peters, “Who are my neighbors?: A perception model for selecting neighbors of pedestrians in crowds,” in _Proceedings of the 18th International Conference on Intelligent Virtual Agents_. ACM, 2018, pp. 269–274.
  * [10] P. Battaglia, R. Pascanu, M. Lai, D. J. Rezende, and others, “Interaction networks for learning about objects, relations and physics,” in _Advances in neural information processing systems_ , 2016, pp. 4502–4510.
  * [11] S. Haddad, M. Wu, H. Wei, and S. K. Lam, “Situation-Aware Pedestrian Trajectory Prediction with Spatio-Temporal Attention Model,” _Computer Vision Winter Workshop (CVWW)_ , pp. 4–13, 2019.
  * [12] P. Zhang, W. Ouyang, P. Zhang, J. Xue, and N. Zheng, “SR-LSTM: State Refinement for LSTM towards Pedestrian Trajectory Prediction,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 12 085–12 094.
  * [13] H. Xue, D. Q. Huynh, and M. Reynolds, “SS-LSTM: A hierarchical LSTM model for pedestrian trajectory prediction,” in _2018 IEEE Winter Conference on Applications of Computer Vision (WACV)_. IEEE, 2018, pp. 1186–1194.
  * [14] D. Helbing, L. Buzna, A. Johansson, and T. Werner, “Self-organized pedestrian crowd dynamics: Experiments, simulations, and design solutions,” _Transportation science_ , vol. 39, no. 1, pp. 1–24, 2005.
  * [15] C. Schiermeyer, F. Pascucci, N. Rinke, V. Berkhahn, and B. Friedrich, “A genetic algorithm approach for the calibration of a social force based model for shared spaces,” in _Proceedings of the 8th international conference on pedestrian and evacuation dynamics (PED)_ , 2016.
  * [16] F. T. Johora and J. P. Müller, “Modeling interactions of multimodal road users in shared spaces,” in _2018 21st International Conference on Intelligent Transportation Systems (ITSC)_. IEEE, 2018, pp. 3568–3574.
  * [17] P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez, V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, and others, “Relational inductive biases, deep learning, and graph networks,” _arXiv preprint arXiv:1806.01261_ , 2018.
  * [18] N. Kalchbrenner, I. Danihelka, and A. Graves, “Grid long short-term memory,” _arXiv preprint arXiv:1507.01526_ , 2015.
  * [19] A. Sadeghian, V. Kosaraju, A. Gupta, S. Savarese, and A. Alahi, “TrajNet: Towards a Benchmark for Human Trajectory Prediction,” _arXiv preprint_ , 2018.
  * [20] P. Trautman and A. Krause, “Unfreezing the robot: Navigation in dense, interacting crowds,” in _Intelligent Robots and Systems (IROS), 2010 IEEE/RSJ International Conference on_. IEEE, 2010, pp. 797–803.
  * [21] A. Robicquet, A. Alahi, A. Sadeghian, B. Anenberg, J. Doherty, E. Wu, and S. Savarese, “Forecasting social navigation in crowded complex scenes,” _arXiv preprint arXiv:1601.00998_ , 2016.
  * [22] I. Hasan, F. Setti, T. Tsesmelis, A. Del Bue, M. Cristani, and F. Galasso, “” Seeing is Believing”: Pedestrian Trajectory Forecasting Using Visual Frustum of Attention,” in _2018 IEEE Winter Conference on Applications of Computer Vision (WACV)_. IEEE, 2018, pp. 1178–1185.
  * [23] J. Liang, L. Jiang, K. Murphy, T. Yu, and A. Hauptmann, “The garden of forking paths: Towards multi-future trajectory prediction,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 10 508–10 518.
  * [24] A. Sadeghian, V. Kosaraju, A. Sadeghian, N. Hirose, and S. Savarese, “SoPhie: An Attentive GAN for Predicting Paths Compliant to Social and Physical Constraints,” _arXiv preprint arXiv:1806.01482_ , 2018.
  * [25] I. Hasan, F. Setti, T. Tsesmelis, V. Belagiannis, S. Amin, A. Del Bue, M. Cristani, and F. Galasso, “Forecasting people trajectories and head poses by jointly reasoning on tracklets and vislets,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2019.
  * [26] J. Li, H. Ma, Z. Zhang, and M. Tomizuka, “Social-WaGDAT: Interaction-aware Trajectory Prediction via Wasserstein Graph Double-Attention Network,” _arXiv preprint arXiv:2002.06241_ , 2020.
  * [27] A. Robicquet, A. Sadeghian, A. Alahi, and S. Savarese, “Learning social etiquette: Human trajectory understanding in crowded scenes,” in _European conference on computer vision_. Springer, 2016, pp. 549–565.
  * [28] Y. Ma, X. Zhu, S. Zhang, R. Yang, W. Wang, and D. Manocha, “Trafficpredict: Trajectory prediction for heterogeneous traffic-agents,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 33, 2019, pp. 6120–6127.
  * [29] A. Jain, H. S. Koppula, B. Raghavan, S. Soh, and A. Saxena, “Car that knows before you do: Anticipating maneuvers via learning temporal driving models,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2015, pp. 3182–3190.
  * [30] A. Jain, A. R. Zamir, S. Savarese, and A. Saxena, “Structural-RNN: Deep learning on spatio-temporal graphs,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2016, pp. 5308–5317.
  * [31] B. Ivanovic and M. Pavone, “The Trajectron: Probabilistic multi-agent trajectory modeling with dynamic spatiotemporal graphs,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2019, pp. 2375–2384.
  * [32] V. Kosaraju, R. Sadeghian, Amir, I. Reid, H. Rezatofighi, and S. Savarese, “Social-bigat: Multimodal trajectory forecasting using bicycle-gan and graph attention networks,” in _Advances in Neural Information Processing Systems_ , 2019, pp. 137–146.
  * [33] S. Casas, C. Gulino, R. Liao, and R. Urtasun, “Spatially-aware graph neural networks for relational behavior forecasting from sensor data,” _arXiv preprint arXiv:1910.08233_ , 2019.
  * [34] R. Chandra, T. Guan, S. Panuganti, T. Mittal, U. Bhattacharya, A. Bera, and D. Manocha, “Forecasting Trajectory and Behavior of Road-Agents Using Spectral Clustering in Graph-LSTMs,” _arXiv preprint arXiv:1912.01118_ , 2019.
  * [35] J. Li, Y. Fang, M. Tomizuka, and C. Choi, “EvolveGraph: Heterogeneous Multi-AgentMulti-Modal Trajectory Prediction withEvolving Interaction Graphs,” _arXiv preprint arXiv:2003.13924_ , 2020.
  * [36] S. Haddad and S.-K. K. Lam, “Self-Growing Spatial Graph Networks for Pedestrian Trajectory Prediction,” in _The IEEE Winter Conference on Applications of Computer Vision_ , 2020, pp. 1151–1159.
  * [37] A. Mohamed, K. Qian, M. Elhoseiny, and C. Claudel, “Social-STGCNN: A Social Spatio-Temporal Graph Convolutional Neural Network for Human Trajectory Prediction,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 14 424–14 432.
  * [38] A. Lerner, Y. Chrysanthou, and D. Lischinski, “Crowds by example,” in _Computer Graphics Forum_ , vol. 26, no. 3. Wiley Online Library, 2007, pp. 655–664.
  * [39] B. Fritzke, “A growing neural gas network learns topologies,” in _Advances in neural information processing systems_ , 1995, pp. 625–632.
  * [40] T. Kohonen, “The self-organizing map,” _Proceedings of the IEEE_ , vol. 78, no. 9, pp. 1464–1480, 1990.
  * [41] D. Xie, T. Shu, S. Todorovic, and S.-C. Zhu, “Learning and inferring “dark matter” and predicting human intents and trajectories in videos,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 40, no. 7, pp. 1639–1652, 2017.
  * [42] V. Karasev, A. Ayvaci, B. Heisele, and S. Soatto, “Intent-aware long-term prediction of pedestrian motion,” in _Robotics and Automation (ICRA), 2016 IEEE International Conference on_. IEEE, 2016, pp. 2543–2549.
  * [43] T. Yau, S. Malekmohammadi, A. Rasouli, P. Lakner, M. Rohani, and J. Luo, “Graph-SIM: A Graph-based Spatiotemporal Interaction Modelling for Pedestrian Action Prediction,” 12 2020. [Online]. Available: http://arxiv.org/abs/2012.02148
  * [44] A. Ranganathan and Z. Kira, “Self-organization in artificial intelligence and the brain,” _College of Computing, Georgia Institute of Technology_ , 2003\.
  * [45] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, “The graph neural network model,” _IEEE Transactions on Neural Networks_ , vol. 20, no. 1, pp. 61–80, 2008.
  * [46] B. Pérez-Sánchez, O. Fontenla-Romero, and B. Guijarro-Berdiñas, “Self-adaptive topology neural network for online incremental learning,” in _Proceedings of the 6th International Conference on Agents and Artificial Intelligence-Volume 1_. SCITEPRESS-Science and Technology Publications, Lda, 2014, pp. 94–101.
  * [47] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip, “A comprehensive survey on graph neural networks,” _IEEE Transactions on Neural Networks and Learning Systems_ , 2020.
  * [48] T. Smith and D. Alahakoon, “Growing self-organizing map for online continuous clustering,” in _Foundations of Computational Intelligence Volume 4_. Springer, 2009, pp. 49–83.
  * [49] X. Li, X. Ying, and M. C. Chuah, “Grip: Graph-based interaction-aware trajectory prediction,” in _2019 IEEE Intelligent Transportation Systems Conference (ITSC)_. IEEE, 2019, pp. 3960–3966.
  * [50] N. Kamra, H. Zhu, D. Trivedi, M. Zhang, and Y. Liu, “Multi-agent Trajectory Prediction with Fuzzy Query Attention,” _arXiv preprint arXiv:2010.15891_ , 2020.
  * [51] T. Kipf, E. Fetaya, K. C. Wang, M. Welling, and R. Zemel, “Neural Relational Inference for Interacting Systems,” in _arXiv_ , 2018.
  * [52] M. Huynh and G. Alaghband, “AOL: Adaptive Online Learning for Human Trajectory Prediction in Dynamic Video Scenes,” _arXiv preprint arXiv:2002.06666_ , 2020.
  * [53] Y. Feng, B. Hu, F. Lv, Q. Liu, Z. Zhang, and W. Ou, “ATBRG: Adaptive Target-Behavior Relational Graph Network for Effective Recommendation,” _arXiv preprint arXiv:2005.12002_ , 2020.
  * [54] X. Li and H. Chen, “Recommendation as link prediction in bipartite graphs: A graph kernel-based machine learning approach,” _Decision Support Systems_ , vol. 54, no. 2, pp. 880–890, 2013.
  * [55] F. Mutinda, A. Nakashima, K. Takeuchi, Y. Sasaki, and M. Onizuka, “Time series link prediction using NMF,” _Journal of Information Processing_ , vol. 27, pp. 752–761, 2019.
  * [56] J. Shi, H. Ji, C. Shi, X. Wang, Z. Zhang, and J. Zhou, “Heterogeneous Graph Neural Network for Recommendation,” 2020.
  * [57] W. Fan, Y. Ma, Q. Li, Y. He, E. Zhao, J. Tang, and D. Yin, “Graph Neural Networks for Social Recommendation,” in _The World Wide Web Conference_. ACM, 2019, pp. 417–426.
  * [58] H. Chen, X. Li, and Z. Huang, “Link prediction approach to collaborative filtering,” in _Proceedings of the 5th ACM/IEEE-CS Joint Conference on Digital Libraries (JCDL ’05)_ , 6 2005, pp. 141–142.
  * [59] C. Tran, W.-Y. Shin, and A. Spitz, “Community detection in partially observable social networks,” _arXiv preprint arXiv:1801.00132_ , 2017.
  * [60] D. Liben-Nowell and J. Kleinberg, “The link-prediction problem for social networks,” _Journal of the American society for information science and technology_ , vol. 58, no. 7, pp. 1019–1031, 2007.
  * [61] C. Lei and J. Ruan, “A novel link prediction algorithm for reconstructing protein–protein interaction networks by topological similarity,” _Bioinformatics_ , vol. 29, no. 3, pp. 355–364, 2012. [Online]. Available: https://doi.org/10.1093/bioinformatics/bts688
  * [62] F. Hua, R. Nassif, C. Richard, H. Wang, and A. H. Sayed, “Online Distributed Learning Over Graphs With Multitask Graph-Filter Models,” _IEEE Transactions on Signal and Information Processing over Networks_ , vol. 6, pp. 63–77, 2020.
  * [63] A. Bera, N. Galoppo, D. Sharlet, A. Lake, and D. Manocha, “Adapt: real-time adaptive pedestrian tracking for crowded scenes,” in _2014 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2014, pp. 1801–1808.
  * [64] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, “Graph Attention Networks,” _stat_ , vol. 1050, p. 20, 2017.
  * [65] D. Bahdanau, K. Cho, and Y. Bengio, “Neural machine translation by jointly learning to align and translate,” _arXiv preprint arXiv:1409.0473_ , 2014\.
  * [66] E. Webb, B. Day, H. Andres-Terre, and P. Lió, “Factorised Neural Relational Inference for Multi-Interaction Systems,” _arXiv preprint arXiv:1905.08721_ , 2019.
  * [67] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, and others, “Tensorflow: A system for large-scale machine learning,” in _12th ${$USENIX$}$ Symposium on Operating Systems Design and Implementation (${$OSDI$}$ 16)_, 2016, pp. 265–283.
  * [68] I. Hasan, F. Setti, T. Tsesmelis, A. Del Bue, F. Galasso, and M. Cristani, “MX-LSTM: mixing tracklets and vislets to jointly forecast trajectories and head poses,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 6067–6076.
  * [69] T. Salzmann, B. Ivanovic, P. Chakravarty, and M. Pavone, “Trajectron++: Multi-Agent Generative Trajectory Forecasting With Heterogeneous Data for Control,” _arXiv preprint arXiv:2001.03093_ , 2020.
  * [70] N. Lee, W. Choi, P. Vernaza, C. B. Choy, P. H. S. Torr, and M. Chandraker, “Desire: Distant future prediction in dynamic scenes with interacting agents,” 2017.
  * [71] A. Sadeghian, F. Legros, M. Voisin, R. Vesel, A. Alahi, and S. Savarese, “Car-net: Clairvoyant attentive recurrent network,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2018, pp. 151–167.
  * [72] C. Choi and B. Dariush, “Looking to relations for future trajectory forecast,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2019, pp. 921–930.
  * [73] D. Ridel, N. Deo, D. Wolf, and M. Trivedi, “Scene compliant trajectory forecast with agent-centric spatio-temporal grids,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 2, pp. 2816–2823, 2020.
  * [74] Y. Huang, H. Bi, Z. Li, T. Mao, and Z. Wang, “STGAT: Modeling Spatial-Temporal Interactions for Human Trajectory Prediction,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2019, pp. 6272–6281.
  * [75] J. Amirian, J.-B. Hayet, and J. Pettré, “Social ways: Learning multi-modal distributions of pedestrian trajectories with GANs,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops_ , 2019, p. 0.
  * [76] A. Monti, A. Bertugli, S. Calderara, and R. Cucchiara, “DAG-Net: Double Attentive Graph Neural Network for Trajectory Forecasting,” _arXiv preprint arXiv:2005.12661_ , 2020.
  * [77] C. K. Joshi, T. Laurent, and X. Bresson, “An efficient graph convolutional network technique for the travelling salesman problem,” _arXiv preprint arXiv:1906.01227_ , 2019.