# Temporal Egonet Subgraph Transitions

Daniel Gonzalez Cedre
University of Notre Dame
Notre Dame, USA Sophia Abraham
University of Notre Dame
Notre Dame, USA Lucas Parzianello
University of Notre Dame
Notre Dame, USA Eric Tsai
University of Notre Dame
Notre Dame, USA

###### Abstract

How do we summarize dynamic behavioral interactions? We introduce a possible
node-embedding-based solution to this question: temporal egonet subgraph
transitions.111Source code at https://github.com/lucaspar/cbm-project.

##  1 Introduction

The problem of anomaly detection in graphs has a multitude of real-world
applications in many fields. An anomaly may be a rare item, event, or entity
that does not fit with the more ‘typical’ trends in a set of data - i.e. an
outlier. Examples include bank fraud in a set of financial transactions, typos
in a text, intrusions in networks, ‘bot’ users in social media, or a sudden
drop in sales caused by a global pandemic. In this paper, we propose Temporal
Egonet Subgraph Transitions (TEST): a comprehensive way of summarizing the
behavioral patterns of nodes in a network.

We represent interactions between users over time as a sequence of graphs,
representing the evolution of interactions between a set of nodes over time.
In this framework, we are interested in modeling the behavior individual nodes
exhibit in order to distinguish different patterns of interaction. To that
end, TEST creates a vector representation of each node using the changes in
its neighborhood—or _egonet_ —over time. These vector representations can then
be used for traditional tasks, such as clustering and classification,
depending on the application and data quality.

TEST is flexible enough to lend itself to a variety of standard tasks and
application domains because it does not depend on labeled data or any kind of
iterative learning procedure. Nodes’ vector representations are computed
purely based on how their egonets change over time. Once in the embedding
space, the data can be analyzed from various perspectives. For example, given
labeled data, the latent representations can be used for classification tasks
such as bot-detection on social networks. However, in the absence of ground
truth regarding nodes, the latent representations can still be analyzed to
find _communities_ : clusters of points in the embedding space signalling
nodes with similar temporal behavior.

Despite its flexibility, TEST makes some important assumptions about the data.
Not only should the data be graphical, it should be a discrete sequence
$G_{1},G_{2},\dots G_{T}$, where the events described by $G_{t}$ precede those
in $G_{t+1}$. This means that datasets presented as streams of timestamped
edges must be _discretized_. If the discretization process is too coarse,
signals in the data will be lost; however, if the discretization is too fine,
the model will not significantly compress the data. While some datasets and
application domains are concerned with clustering or classifying edges—as is
the case in, for example, detecting fraudulent transactions on financial
networks—our focus in this paper is on characterizing nodes’ behavior.

##  2 Related Work

Diverse techniques exists for anomaly detection in literature. Approaches
include density-based techniques like k-nearest neighbor [10], local outlier
factor [1], isolation forests [14] and other variations [23]. For higher
dimensional data - subspace [11], correlation [12], single class support
vector machines [20] and tensor based methods [6] have been proposed. Neural
network approaches include replicators [8], Bayesian Networks [20], hidden
markov models [20]. Additionally, cluster analysis based [2], fuzzy logic and
ensemble techniques with feature bagging [18] and score normalization [22]
have been applied.

Although these methodologies have minimal systematic advantages across data
sets and parameters, many are applied in the realm of static graphs. To narrow
the scope in relation to our proposed method regarding anomaly detection
algorithms for dynamic graph networks a deeper exploration will be applied to
network embedding and streaming anomaly approaches.

###  2.1 Streaming Anomaly Detection

Streaming anomaly detection attempts to detect suspicious or uncharacteristic
behavior in continuous-time streams of relational data.

####  2.1.1 Streaming Graphs

Streaming graphs can be applied to anomalous node detection like dynamic
tensor analysis (DTA) [25] which approximates an adjacency matrix for a graph
at time t with incremental matrix factorization and utilizes a high
reconstruction error to. Anomalous subgraph detection is illustrated in
methods like [24] which uses k-core which is the maximal subgraph in which all
vertices have degree at least k and use patterns related to k-core to find
anomalous subgraphs. Streaming graphs can also be utilized for anomalous event
detection such as changes in first and second derivatives in PageRank [28].

####  2.1.2 Streaming Edges

Streaming anomaly detection can also be applied to streaming edges. Anomalous
nodes can be detected using methods like [29] which uses an incremental
eigenvector update algorithm based in von Mises interations and discover
hotspots of local changes in dynamics streams. SedanSpot [5] utilizes
streaming edges to detect anomalous edges by exploiting edges that connect
part of the graph that are sparsely connected and finding where bursts of
activity indicative of anomalous behavior.

###  2.2 Network Embedding

Network embedding approaches consist of learning low-dimensional feature
representation of the nodes or links within a network. Many advances [3, 13,
27, 31] in the network embedding space present new ways to learn
representations for networks which can be used to detect anomalies. Feature
learning strategies for extracting network embedding have been widely used in
language models such as Skip-gram [17] in which the the defining neighborhood
attributes for words in a sentence are preserved. In a similar manner, many
popular methodologies such as DeepWalk [19] and Node2vec [7] use sequences of
vertices from the graphs and learn the representation of these vertices by
maximizing the preservation of the structure inherent to a neighborhood of
vertices in the network. A large portion of work has also been dedicated to
representation learning in other manners for graph network architectures [26,
27, 32] and compact representations of the graph have been used to find
anomalies within the network [16].

These methods have also been specifically applied for anomaly detection in
dynamic temporal graphs. Specifically, NetWalk [30] learns network
representations which are dynamically updated as the network evolves. This is
done by by learning the latent network representations by extracted sequences
of vertices from the graph, otherwise termed as ”walks” from the initial
network and then extract deep representations by minimizing the pairwise
distance of the vertices when encoding the vector representations and adding
global regularization by using a deep autoencoder reconstruction error.
NetWalk is updated over dynamic changes with reservoir sampling strategy and a
dynamic clustering model is used to find anomalies.

In [9], dynamic graph evolution is modeled with subgraph to subgraph
transitions (SST) by fitting linear SVM models to SST count vectors. This can
be used for link prediction of static, temporal, directed and undirected
graphs while providing interpretable results. The idea of counting SSTs
inspires our proposed methodology, however, instead of utilizing an edge based
approach as this paper did, we propose a neighborhood based approach for
detecting anomalies based on clusters (cf. Sec. 4).

##  3 Data Sources

We are focused on modeling behavior over time from graph-structured data, so
we need datasets with the following attributes:

  1. 1.

Nodes with persistent IDs.

  2. 2.

Interactions (directed or undirected) between nodes.

  3. 3.

Timestamps for the interactions.

###  3.1 Available Datasets

Although we initially wanted to tackle node classification problems using TET,
we ran into problems finding datasets which had both timestamped edges and
ground-truth labels for the nodes. Most of the datasets with ground-truth we
found had labels for the edges instead. Therefore, we are considering
unsupervised tasks like clustering for testing the quality of our node
embeddings. We describe some of the datasets we found below.

####  3.1.1 Enron Emails222http://odds.cs.stonybrook.edu/enroninc-dataset/

The nodes of this dataset represent email addresses and directed edges depict
sent/received relations. Enron email network dataset contains a total of 80,
884 nodes and 700 timestamp in total.

####  3.1.2 College Messages444https://snap.stanford.edu/data/CollegeMsg.html

This is a dataset containing private messages at an online social network at
the University of California, Irvine. Here an edge (u, v, t) means that during
time t, an user u sent a message to an user v.

####  3.1.3 EU Emails666https://snap.stanford.edu/data/email-Eu-core-
temporal.html

This dataset contains 986 nodes and 332,334 temporal edges, with the timestamp
of 803 in total.

###  3.2 Synthetic Dataset

In order to test our model’s ability to properly distinguish between nodes
with different temporal behavior in the embedding space, we need a dataset
which:

  1. 1.

represents interactions between different objects,

  2. 2.

is temporal (i.e., interactions occur at known points in time, which may
repeat),

  3. 3.

has ground truth labels on the _nodes_ indicating whether those nodes are
anomalous or not.

There are many public temporal graph datasets that immediately satisfy the
first two requirements.

Among those, there are a few that also include some ground truth information
regarding authentic/suspicious/anomalous edges in the graph. However, since we
are attempting to characterize _nodes_ as anomalous or not, edge-centric
ground truth labels are unhelpful. Since a dataset satisfying all three
criteria is unavailable to us, we could go out into the world and collect,
mine, or survey a sufficiently high-quality dataset on our own.

We elected to not pursue this idea not only because of time constraints, but
also because building a real-world dataset satisfying those three criteria by
hand would require a level of description, analysis, and methodological detail
that might be more appropriate for its own paper.

Therefore, we elected to generate a synthetic temporal graph with ground truth
node labels.

The data consists of a discrete sequence of five graphs $G_{1},G_{2},\dots
G_{5}$ on a shared set of $500$ nodes $V$, representing five snapshots of
interactions between the nodes in $V$.

The nodes are split between _authentic_ and _anomalous_ nodes, labels which
persist through the different graphs in the sequence. For each time
$t\in{0,\dots 4}$ authentic nodes’ edges are generated by an Erdos-Renyi
random process [4];

specifically, between any two authentic nodes $u$ and $v$, an edge
$e=\left\\{u,v\right\\}$ exists with probability $p\in[0,1]$. The anomalous
nodes are connected together in the following way: for
$t\in\left\\{0,2,4\right\\}$, all of the anomalous nodes form the empty
subgraph; for $t\in\left\\{1,3,5\right\\}$, the anomalous nodes form a clique.

The free parameters for generating this dataset are the connection probability
$p$ for the authentic nodes, the total number of nodes $n$, and the percentage
of the total nodes that is designated as anomalous. In the future, we can
experiment with different ways of connecting the anomalous nodes together to
create more-varied temporal patterns.

##  4 Description of the Model

Synthetic dataset: $p=0.0025$, $a=0.05$
---
| Egonet | Node2Vec | Spectral Clustering | Deepwalk |
| Prec. | Recall | F1-Score | Prec. | Recall | F1-Score | Prec. | Recall | F1-Score | Prec. | Recall | F1-Score | Data Points
Anomaly | 1.00 | 1.00 | 1.00 | 0.00 | 0.00 | 0.00 | 0.01 | 0.04 | 0.02 | 0.27 | 0.56 | 0.36 | 25
Normal | 1.00 | 1.00 | 1.00 | 0.95 | 0.95 | 0.95 | 0.94 | 0.82 | 0.88 | 0.98 | 0.92 | 0.95 | 475
Accuracy |  |  | 1.00 |  |  | 0.90 |  |  | 0.78 |  |  | 0.90 | 500

Table 1: Where $p$ is is the connection probability for the authentic nodes,
and a is the percentage of the anomalous nodes.

The basic idea behind TET is that changes in a node’s egonet can be summarized
by counting _subgraph transitions_. A subgraph transition for a node $v$ at a
given time transition $(t,t+1)$ is defined as a pair of graphs
$(H_{t},H_{t+1})$ on a shared node set $V$ such that:

  * $\cdot$

$H_{t}$ is a subgraph of the adjacency neighborhood of $v$ at time $t$ if any
missing nodes from the neighborhood at time $t+1$ are included

  * $\cdot$

$H_{t+1}$ is a subgraph of the adjacency neighborhood of $v$ at time $t+1$ if
any missing nodes from the neighborhood at time $t$ are included

  * $\cdot$

$H_{t}$ and $H_{t+1}$ are not isomorphic.

In the interest of computational tractability, we only consider subgraph
transitions up to a certain number of vertices—for this paper, we only
consider subgraph transitions on at most $N=3$ nodes.

By enumerating and canonically ordering all of the subgraph transitions in
question, we can construct a vector of _subgraph transition counts_ for the
node $v$ during the time hop from $t$ to $t+1$. This subgraph transition count
vector summarizes the change in $v$’s behavior from the previous time step to
the next time step.

Performing this for each time transition results in a sequence of count
vectors $\vec{v}_{1},\vec{v}_{2},\dots\vec{v}_{T-1}\in\mathbb{R}^{d}$, where
$d$ is the number of subgraph transitions enumerated (note: $d$ may be _very_
large, even for small $N$). We can then condense these counts into a single
vector representation for $v$ by applying some element-wise _aggregation
function_ (e.g., mean, sum, min, max). In this paper, we aggregate the count
vectors by averaging each of the transition counts over all of the time steps,
producing $\vec{v}=\frac{1}{T-1}\sum_{t=1}^{T-1}\vec{v}_{t}\in\mathbb{R}^{d}$
as the embedding vector for the node in question. The model is described in
detail in Alg. 1.

Input: List of subgraph transitions $\mathcal{T}$

eeeeeii Temporal graph sequence, $G_{1},\dots G_{T}$

eeeeeii Set of nodes $V$

Output: Set of embeddings $\left\\{\vec{c}_{v}~{}|~{}v\in V\right\\}$

for  _$v$ in $V$_ do

for  _$t\in\left\\{1,\dots T-1\right\\}$_ do

Initialize $\vec{c}_{v,t}=(0,\dots 0)\in\mathbb{R}^{|\mathcal{T}|}$;

Let $G_{t}(v)$ be the egonet of $v$ at time $t$;

Let $G_{t+1}(v)$ be the egonet of $v$ at time $t+1$;

Union the vertex sets of $G_{t}(v)$ and $G_{t+1}(v)$;

for  _$(L,R)_{i}\in\mathcal{T}$_ do

for  _$G\lhd G_{t}(v)$ isomorphic to $L$_ do

for  _$H\lhd G_{t+1}(v)$ isomorphic to $R$_ do

if  _$G$ and $H$ share the same nodes_ then

Increment index $i$ of $\vec{c}_{v,t}$;

else

Continue;

end if

end for

end for

end for

end for

Compute $\vec{c}_{v}=\frac{1}{T-1}\sum_{t=1}^{T-1}\vec{c}_{v,t}$;

yield $\vec{c}_{v}$;

end for

Algorithm 1 how to embed temporal egonets

##  5 Evaluation

###  5.1 Experiments Setup

In the case that we find a properly labeled dataset to evaluate TET, we can
use more commonly found metrics to compare our results in an anomaly-detection
problem. We probably will not use accuracy of classification directly,
however. That is because anomaly datasets in general are heavily skewed
towards the normal behavior, thus, any classifier that labeled them all as
normal would achieve an accuracy close to 100%. Thus, we focus our report in
the F1-score, precision, and recall achieved in the baseline executions and
compare them against Egonet. The experiments shown in Table 1 shown here were
carried out on the synthetic dataset described in Sec. 3.2.

###  5.2 Baselines

In order to assess the quality of our method, we will compare against
competing methods and apply the same unsupervised learning methods later on.

  * $\cdot$

Spectral Clustering [15]: is closely related to nonlinear dimension reduction,
and dimension reduction techniques such as locally-linear embedding can be
used to reduce errors from noise. By calculating the Laplacian of the graph
and obtaining the first eigenvectors and corresponding eigenvalues of the
Laplacian, this method output embedding nodes. Spectral Clustering has no
assumption on the shapes of the clusters and can thus model complex scenarios.

  * $\cdot$

DeepWalk [19]: generalizes on language modeling from sequences of words to
graphs by using local information from sequences of vertices(Random Walk and
SkipGram) in the graph and learning representations by treating them
equivalently to sentences. Here the input is an edge list file and the output
of DeepWalk is 64 dimensions by default. In order to visualize it, the output
is manually set to 2 dimensions.

  * $\cdot$

Node2Vec [7]: is a useful method for extracting the continuous-feature
representations for nodes in graph networks. By using a biased random walk
procedure, Node2Vec maps of nodes to a lower-dimensional space of features
while preserving their locality.

The baselines mentioned above do not take dynamic graphs into account without
a remodeling of the input data and multiple executions, making it a
challenging task to represent the evolution of the graph over time. In our
case temporal graphs into account, which significantly lowers to their
implementation complexity. All of the output of embedding methods (including
the output of Egonet) are later fed forward to the same pipeline of DBSCAN for
outlier detection. The results are displayed in Figures 1, 2, and 3. The
images also point the frequency distribution among the classes found by
DBSCAN. As opposed to k-means, DBSCAN attempts to find the optimal number of
classes, so the number of clusters is highly dependent on the embedding
dataset.

Figure 1: Results of the clustering after DeepWalk node embedding on the
synthetically generated dataset. Figure 2: Results of the clustering after
Node2Vec node embedding on the synthetically generated dataset. Figure 3:
Results of the clustering after Spectral Clustering node embedding on the
synthetically generated dataset.

###  5.3 Future Work

In addition to the clustering techniques mentioned above, the Extreme Value
Machine (EVM) [21] could be used to classify extracted embeddings.

The EVM is a scalable nonlinear classifier which supports open-set
classification, where the models are assumed to have incomplete knowledge of
their operating context and can reject inputs that are beyond the support of
the training set. The EVM relies on a strong feature representation and every
represented sample in the feature representation becomes a point. EVM utilizes
bins which groups all the points in their feature representation by their
correspondent label. These bins are utilized to create a 1 vs. rest EVM
classifier for each known class or in our case each of the known clusters. The
EVM generates a classifier where a Weibull distribution is fit on the data for
each known class and is made to avoid the negative data points (unknown
classes) or outliers for our application. This is repeated for all the known
classes/clusters. When a coordinate point which is a sample encoded by its
feature representation as a vector is provided to the EVM, the points are
mapped to the feature space as a probability of belonging to a representative
class, or if it falls below a threshold of inclusion, labeled as an outlier.

The analysis of our approach for extracting embeddings and clustering with
DBSCAN proved to be successful on the synthetically generated data, however,
real world data may be more complex and difficult to detect outliers in. Thus,
using an approach like the EVM and forming distributions that take into
account the input space distance distributions may provide strong
understanding of the nature of the data and prove to be an effective means of
capturing anomalous nodes based off the embeddings.

## References

  * [1] Markus M Breunig, Hans-Peter Kriegel, Raymond T Ng, and Jörg Sander.  Lof: identifying density-based local outliers.  In Proceedings of the 2000 ACM SIGMOD international conference on Management of data, pages 93–104, 2000.
  * [2] Ricardo JGB Campello, Davoud Moulavi, Arthur Zimek, and Jörg Sander.  Hierarchical density estimates for data clustering, visualization, and outlier detection.  ACM Transactions on Knowledge Discovery from Data (TKDD), 10(1):1–51, 2015.
  * [3] Shiyu Chang, Wei Han, Jiliang Tang, Guo-Jun Qi, Charu C Aggarwal, and Thomas S Huang.  Heterogeneous network embedding via deep architectures.  In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 119–128, 2015.
  * [4] Paul Erdős and Alfréd Rényi.  On Random Graphs. I.  Publicationes Mathematicae, 6:290–297, 1959.
  * [5] Dhivya Eswaran and Christos Faloutsos.  Sedanspot: Detecting anomalies in edge streams.  In 2018 IEEE International Conference on Data Mining (ICDM), pages 953–958. IEEE, 2018.
  * [6] Hadi Fanaee-T and Joao Gama.  Tensor-based anomaly detection: An interdisciplinary survey.  Knowledge-Based Systems, 98:130–147, 2016.
  * [7] Aditya Grover and Jure Leskovec.  node2vec: Scalable feature learning for networks.  In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855–864, 2016.
  * [8] Simon Hawkins, Hongxing He, Graham Williams, and Rohan Baxter.  Outlier detection using replicator neural networks.  In International Conference on Data Warehousing and Knowledge Discovery, pages 170–180. Springer, 2002.
  * [9] Justus Isaiah Hibshman, Daniel Gonzalez, Satyaki Sikdar, and Tim Weninger.  Joint subgraph-to-subgraph transitions: Generalizing triadic closure for powerful and interpretable graph modeling.  Proceedings of the 14th ACM International Conference on Web Search and Data Mining, 2021.
  * [10] Edwin M Knorr, Raymond T Ng, and Vladimir Tucakov.  Distance-based outliers: algorithms and applications.  The VLDB Journal, 8(3):237–253, 2000.
  * [11] Hans-Peter Kriegel, Peer Kröger, Erich Schubert, and Arthur Zimek.  Outlier detection in axis-parallel subspaces of high dimensional data.  In Pacific-asia conference on knowledge discovery and data mining, pages 831–838. Springer, 2009.
  * [12] Hans-Peter Kriegel, Peer Kröger, Erich Schubert, and Arthur Zimek.  Outlier detection in arbitrarily oriented subspaces.  In 2012 IEEE 12th international conference on data mining, pages 379–388. IEEE, 2012.
  * [13] Omer Levy and Yoav Goldberg.  Neural word embedding as implicit matrix factorization.  Advances in neural information processing systems, 27:2177–2185, 2014.
  * [14] Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou.  Isolation-based anomaly detection.  ACM Transactions on Knowledge Discovery from Data (TKDD), 6(1):1–39, 2012.
  * [15] Jialu Liu, Jiawei Han, C Aggarwal, and C Reddy.  Spectral clustering., 2013.
  * [16] Emaad Manzoor, Sadegh M Milajerdi, and Leman Akoglu.  Fast memory-efficient anomaly detection in streaming heterogeneous graphs.  In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1035–1044, 2016.
  * [17] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean.  Distributed representations of words and phrases and their compositionality.  arXiv preprint arXiv:1310.4546, 2013.
  * [18] Hoang Vu Nguyen, Hock Hee Ang, and Vivekanand Gopalkrishnan.  Mining outliers with ensemble of heterogeneous detectors on random subspaces.  In International Conference on Database Systems for Advanced Applications, pages 368–383. Springer, 2010.
  * [19] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena.  Deepwalk: Online learning of social representations.  In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701–710, 2014.
  * [20] John C Platt, John Shawe-Taylor, Alex J Smola, Robert C Williamson, et al.  Estimating the support of a high-dimensional distribution.  Technical Report MSR-T R-99–87, Microsoft Research (MSR), 1999\.
  * [21] Ethan M Rudd, Lalit P Jain, Walter J Scheirer, and Terrance E Boult.  The extreme value machine.  IEEE transactions on pattern analysis and machine intelligence, 40(3):762–768, 2017.
  * [22] Erich Schubert, Remigius Wojdanowski, Arthur Zimek, and Hans-Peter Kriegel.  On evaluation of outlier rankings and outlier scores.  In Proceedings of the 2012 SIAM International Conference on Data Mining, pages 1047–1058. SIAM, 2012.
  * [23] Erich Schubert, Arthur Zimek, and Hans-Peter Kriegel.  Local outlier detection reconsidered: a generalized view on locality with applications to spatial, video, and network outlier detection.  Data mining and knowledge discovery, 28(1):190–237, 2014.
  * [24] Kijung Shin, Tina Eliassi-Rad, and Christos Faloutsos.  Patterns and anomalies in k-cores of real-world graphs with applications.  Knowledge and Information Systems, 54(3):677–710, 2018.
  * [25] Jimeng Sun, Dacheng Tao, and Christos Faloutsos.  Beyond streams and graphs: dynamic tensor analysis.  In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 374–383, 2006.
  * [26] Fei Tian, Bin Gao, Qing Cui, Enhong Chen, and Tie-Yan Liu.  Learning deep representations for graph clustering.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
  * [27] Daixin Wang, Peng Cui, and Wenwu Zhu.  Structural deep network embedding.  In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1225–1234, 2016.
  * [28] Minji Yoon, Bryan Hooi, Kijung Shin, and Christos Faloutsos.  Fast and accurate anomaly detection in dynamic graphs with a two-pronged approach.  In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 647–657, 2019.
  * [29] Weiren Yu, Charu C Aggarwal, Shuai Ma, and Haixun Wang.  On anomalous hotspot discovery in graph streams.  In 2013 IEEE 13th International Conference on Data Mining, pages 1271–1276. IEEE, 2013.
  * [30] Wenchao Yu, Wei Cheng, Charu C Aggarwal, Kai Zhang, Haifeng Chen, and Wei Wang.  Netwalk: A flexible deep embedding approach for anomaly detection in dynamic networks.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2672–2681, 2018.
  * [31] Wenchao Yu, Guangxiang Zeng, Ping Luo, Fuzhen Zhuang, Qing He, and Zhongzhi Shi.  Embedding with autoencoder regularization.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 208–223. Springer, 2013.
  * [32] Lekui Zhou, Yang Yang, Xiang Ren, Fei Wu, and Yueting Zhuang.  Dynamic network embedding by modeling triadic closure process.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.


# Hybrid Traffic Control and Coordination from Pixels

Michael Villarreal, Bibek Poudel, Jia Pan, Weizi Li

###### Abstract

Traffic congestion is a persistent problem in our society. Existing methods
for traffic control have proven futile in alleviating current congestion
levels leading researchers to explore ideas with robot vehicles given the
increased emergence of vehicles with different levels of autonomy on our
roads. This gives rise to hybrid traffic control, where robot vehicles
regulate human-driven vehicles, through reinforcement learning (RL). However,
most existing studies use precise observations that involve global
information, such as network throughput, as well as local information, such as
vehicle positions and velocities. Obtaining this information requires updating
existing road infrastructure with vast sensor networks and communication to
potentially unwilling human drivers. We consider image observations as the
alternative for hybrid traffic control via RL: 1) images are readily available
through satellite imagery, in-car camera systems, and traffic monitoring
systems; 2) Images do not require a complete re-imagination of the observation
space from network to network; and 3) images only require communication to
equipment. In this work, we show that robot vehicles using image observations
can achieve similar performance to using precise information on networks,
including ring, figure eight, merge, bottleneck, and intersections. We also
demonstrate increased performance (up to $26$%) in certain cases on tested
networks, despite only using local traffic information as opposed to global
traffic information.

##  I Introduction

Traffic congestion is a prevalent challenge in modern society that causes
delays, gridlocks, and substantial economic losses. Traditional traffic
management methods such as traffic lights, stop signs, and ramp meters have
proven insufficient in alleviating the current level of congestion [1, 2]. As
more vehicles with varying degrees of autonomy are introduced into our
transportation system, the idea of hybrid traffic control, which involves the
use of robot vehicles (RVs) to regulate human-driven vehicles (HVs), is
gaining popularity as a solution. Studies have shown the effectiveness of this
approach in stabilizing traffic on roads of different configurations,
including ring and figure-eight roads [3], merge and bottleneck roads [4], and
intersections [4, 5, 6]. Among various control methods for hybrid traffic,
reinforcement learning (RL) has emerged as a promising tool, as it can handle
the complexity of hybrid traffic behaviors without the need for predefined
models or heuristics [7].

Recent research on hybrid traffic control via RL all uses precise information
on traffic conditions as input. This means the RV receives both exact global
information such as network throughput and travel time as well as exact local
information such as surrounding vehicles’ positions and velocities. For the RV
to receive precise global information, sensor infrastructure to collect this
information is required. This involves updating or completely upending
existing road networks, which can incur significant costs. To receive precise
local information, the RV needs to establish vehicle-to-vehicle (V2V) and
vehicle-to-infrastructure (V2I) communications (where the infrastructure
tracks individual vehicles). While V2I also needs augmented infrastructure
with proper sensors installed, V2V additionally requires HVs to have the
capabilities to send precise information and opt-in to the communication with
neither of these being guaranteed. To avoid these pitfalls of using precise
observations as input to RL policies, we consider image observations as the
alternative. Imagery about traffic conditions is readily available. To start
with, satellite imagery can capture traffic conditions in both cities and
rural areas where communication is sparse. In addition, our road
infrastructure is equipped with ubiquitous camera systems. Examples include
Performance Measurement System (PeMS) [8] which monitors city-scale traffic
and Advanced Traffic Management System (ATMS) [9] which provides real-time
images of traffic conditions. Lastly, many modern cars are installed with
cameras that can capture $360^{\circ}$ view of the surroundings.

There are also benefits of using image observations to train RL policies for
hybrid traffic control. First, using pixels as inputs allows for end-to-end
training thus avoiding the need for the manual design of the global and local
traffic information. Designing the observation space has been a hurdle for
hybrid traffic control via RL: different scenarios need a complete rethinking
of what information to extract and how to effectively combine the information.
For example, the figure-eight network uses all vehicles’ positions and
velocities while the bottleneck network uses mean position and velocity of HVs
and RVs on user-defined segments combined with network outflow as the
observation. Using pixels can further enable RVs to generalize to new
situations as the V2I support could vary significantly in different parts of a
road network.

This project focuses on exploring the use of image observations as an
alternative to precise observations for training RL policies in hybrid traffic
control. The image observations, which are centered on RVs, have generic
resolutions and provide only local information about the surroundings of RVs
and not global information about the entire network. While we still require
V2V communication as images are shared amongst the RVs, the use of image
observations eliminates the need for HVs to participate in the communication
process. This overcomes the uncertainty of having HVs collect and send
information and opt-in to share their information. In summary, our
contributions are as follows.

  * •

Image observations are used instead of precise observations for training RVs
in hybrid traffic control. These images are both generic and only need to
record the local surroundings of the RVs. In contrast, global information is
needed when using precise observations.

  * •

Demonstration of the same-level performance to using precise observations on
ring roads, figure-eight networks, and merge networks.

  * •

Improved performance in certain cases as compared to using precise
observations, such as a $26\%$ increase in average vehicle velocity in the
merge network and a $6\%$ increase in network outflow in the bottleneck
network.

To the best of our knowledge, we are the first in conducting thorough
experiments to demonstrate the feasibility of utilizing image observations in
hybrid traffic control through RL.

Figure 1: We experiment on five road networks: ring, figure eight,
intersection, merge, and bottleneck. The image observations used for each road
network are presented on the right. The car shapes in the color figures are
for visualization-purpose only. Human-driven vehicles (HVs) are white,
observed HVs (when using precise observations) are blue, and robot vehicles
(RVs) are red. All HVs are blue when using image observations to provide
contrast from a white background as seen in the image observations. No HV is
blue in the bottleneck network as specific HVs are not observed, but rather
information about the entire network. We use static, grayscale, $84\times 84$
images centered over RVs (or intersection for the intersection network) that
provide only local information to RVs. Ring, figure eight, and intersection
use a single image, while merge and bottleneck use five and $15$,
respectively.

##  II Related Work

There are numerous studies demonstrating the use of images or pixel values in
reinforcement learning (RL). These applications range from playing Atari games
[10, 11, 12] to improving ultrasound images and diagnoses [13, 14]. A series
of image trajectories have also been adopted for training RL agents [15, 16,
17]. While these studies highlight the potential of images in RL, the
applications differ and our focus is hybrid traffic control via robot
vehicles, a multi-agent setting.

A significant portion of training RVs via RL focuses on individual vehicle
driving but not controlling the entire traffic [18, 19]. To list some
examples, images are used with vision transformers to learn an effective
driving policy [20], to train RVs to drive in simulation [21, 22, 23, 24], or
to prevent crashes by capturing the RVs’ surroundings [25]. In the work by Pan
et al. [26], simulated images are transformed into realistic-looking images to
train RVs via RL. While these studies apply RL and images to RVs, they do not
concentrate on traffic control.

The work by Wu et al. [3] pioneers hybrid traffic control using RL. They show
the effectiveness of training an RV on smoothing out stop-and-go waves on a
ring road. Further tests are conducted by Vinitsky et al. [4] on additional
networks, including merge, bottleneck, and intersection scenarios. Recently,
Wang et al. [6] manage to scale up hybrid traffic control to real-world,
complex intersections while controlling and coordinating hundreds of vehicles.
While significant advancements have been made in hybrid traffic control, all
these studies use precise observations as inputs to the RL policy. These
precise observations include both global and local traffic conditions, such as
network throughput and vehicle position and velocity.

Our work replaces these precise observations with image observations in the
training of RL policies for hybrid traffic control. This shift to image
observations has several benefits. First, it eliminates the requirement for
manual design of the observation space for different traffic scenarios, making
it a more flexible solution. Second, it can leverage existing traffic
infrastructure as image data is readily available from sources such as
satellite imagery, traffic monitoring systems, and vehicle surround-view
cameras.

There are several studies exploring hybrid traffic control with images.
However, there are key differences between their efforts and ours. To start
with, the work by Maske et al. [27] presents a decentralized method for
training RVs using images, but the test is only done on the ring network and
the focus is not to prevent stop-and-go waves. The work by Wu and Bayen [28]
shows that human driving can be positively augmented using an RL controller
trained on local image observations. Their approach is tested on the ring and
figure-eight networks. However, again, the focus is not to prevent stop-and-go
traffic. To the best of our knowledge, our work is the first to perform
extensive experimentation on various road networks to prove the viability of
using image observations for RL-based hybrid traffic control in alleviating
traffic congestion.

##  III Methodology

In this section, we first introduce our problem formulation and then outline
the details (observation, action, and reward) for the five road networks in
which we conduct experiments. We also provide details on precise observations
[3, 4] and compare their differences to image observations.

###  III-A Preliminaries

We model the RL problem as a Partially Observable Markov Decision Process
(POMDP) represented by a tuple ($\mathcal{S}$, $\mathcal{A}$, $\mathcal{P}$,
$\mathcal{R}$, $p_{0}$, $\gamma$, $T$, $\Omega$, $\mathcal{O}$) where:
$\mathcal{S}$ is the state space; $\mathcal{A}$ is the action space;
$\mathcal{P}(s^{\prime}|s,a)$ is the transition probability function;
$\mathcal{R}$ is the reward function; $p_{0}$ is the initial state
distribution; $\gamma\in(0,1]$ is the discount factor; $T$ is the episode
length (horizon); $\Omega$ is the observation space; and $\mathcal{O}$ is the
probability distribution of retrieving an observation $\omega\in\Omega$ from a
state $s\in\mathcal{S}$.

At each timestep $t\in[1,T]$, a robot vehicle (RV) uses its policy
$\pi_{\theta}(a_{t}|s_{t})$ to take an action $a_{t}$ $\in$ $\mathcal{A}$,
given the state $s_{t}$ $\in$ $\mathcal{S}$. The RV’s environment provides
feedback on action $a_{t}$ by calculating a reward $r_{t}$ and transitioning
the agent into the next state $s_{t+1}$. The RV’s goal is to learn a policy
$\pi_{\theta}$ that maximizes the discounted sum of rewards, i.e., return,
$R_{t}=\sum^{T}_{i=t}\gamma^{i-t}r_{i}$. We use Proximal Policy Optimization
[29], a model-free, on-policy algorithm, to learn the optimal policy.

###  III-B Road Network MDPs

We train RVs using RL on five road networks (ring, figure eight, intersection,
bottleneck, and merge) shown in Fig. 1 using image observations. We give a
brief environment description and outline MDP details, such as observation
space, action space, and reward function, for each network and compare the
differences between precise observations and image observations. Further
details related to these networks are provided in Section IV.

####  III-B1 Ring Network

The ring network is a widely used benchmark in traffic control. A single-lane
circular road network consisting of $22$ vehicles with $21$ human-driven
vehicles (HVs) and one RV is considered. It simulates how subtle perturbations
due to imperfections in human driving behavior can amplify and propagate,
leading to an eventual standstill for some vehicles. This situation is known
as ‘stop-and-go traffic’ which acts as a wave that propagates continually
through the ring, opposite the direction of travel. The RV’s goal is to dampen
these waves, thus increasing the average velocity of all vehicles.

Observation Space. Every timestep, our observation is a gray-scale image of
dimensions $84\times 84$ pixels, centered on a single RV as shown in Fig. 1,
right A. To simulate limited visibility, the image is masked by a circle with
a radius corresponding to $28.75$ meters in real world.

Precise observations are a vector of the RV’s velocity, the difference between
the leading vehicle’s velocity and the RV’s velocity, and the difference
between the leading vehicle’s position and the RV’s position. The positions of
the vehicles are defined relative to the ring network, and all three values
are normalized. These observations have been used previously [3] to produce
state-of-the-art performance.

Action Space. The action is defined as a continuous distribution space of
acceleration bound by $[-1,1]$ m/s2.

Reward. The reward function encourages high average velocity of all vehicles
while penalizing accelerations (control action) above a threshold:

$r=\begin{cases}0,&\text{if collision,}\\\
\lambda_{1}*v/20+A,&\text{otherwise,}\end{cases}$ (1)

where $\lambda_{1}$ is empirically set to 4, $v$ is the average velocity of
all vehicles, and $A$ is

$A=\begin{cases}0,&\text{if}\ a>\phi,\\\
\lambda_{2}*(\phi-a),&\text{otherwise.}\end{cases}$ (2)

In $A$, $\lambda_{2}$ is empirically set to 3, $a$ is the average of
accelerations, and $\phi$ is a threshold value set to 0. The RV is punished
for accelerating when $a$ is positive.

####  III-B2 Figure Eight Network

The figure-eight network simulates an intersection in a closed loop with $14$
vehicles—$13$ HVs and one RV. As a result of its shape and the fixed number of
vehicles in the network, queues form among cars that try to cross the
intersection. This causes a network-wide decrease in average vehicle velocity.
The RV’s goal is then to increase the average velocity of all vehicles in the
network.

Observation Space. Our observation is the same as of the ring network (see
Sec. III-B1). An example is given in Fig. 1, right B. The dimension of the
masked circle corresponds to a $21.25$ m radius. Precise observations are a
vector of the velocities and positions of all vehicles within the figure-eight
network, including RV and HVs [3]. This complete information reflects that the
state space is used. As our observations are local, i.e., images centered on
the RV, learning an optimal policy includes extra steps of perception and
representation learning, making it much more challenging than with precise
observations.

Action Space. The action is defined in a continuous distribution of
accelerations bound by $[-3,3]$ m/s2.

Reward. The objective of the RV is to increase the velocities of all vehicles
in the network:

$r=\frac{max({\parallel}v_{des}*1^{k}\parallel_{2}-{\parallel}v_{des}-v\parallel_{2},0)}{{\parallel}v_{des}*1^{k}{\parallel}_{2}},$
(3)

where $v_{des}$ (desired velocity) is $10$ m/s, $v$ is a vector of all
vehicles’ velocities, and $k$ is the total number of vehicles in the network.

####  III-B3 Intersection Network

This network represents an unsignalized intersection where east/westbound
traffic flow is less than north/southbound traffic flow. The difference in
flows is significant enough such that east/westbound traffic forms queues as
it would otherwise be unsafe to cross the intersection. This intersection
functions similarly to an idealized two-way stop for the east/west traffic.
RVs are placed in the north/south directions with a penetration rate of
$20\%$. The RVs’ objective is the minimization of queues forming and increased
average vehicle velocity along the east/west directions. This environment
allows for studying hybrid traffic control in directions absent of RVs since
RVs control only the north/south directions.

Observation Space. Our observation is an $84\times 84$, grayscale image (shown
in Fig. 1, right C) taken at the intersection’s center. The image observations
focus on the intersection. No circle mask is applied to the images. The image
dimensions correspond to a square with a side length of $50$ m in real world.

Precise observations include global traffic information as well as local
traffic information. Vehicles closest to the intersection up to a user-defined
number are considered [3, 4]. Specifically, the observation space has the
following information: the velocities of each vehicle, the position distance
to the intersection of each vehicle, the edge number of each vehicle (this
identifies if the vehicle is in east/west traffic or in north/south traffic),
the density of the edges, and the average vehicle velocity of the edges. Our
RVs cannot infer network-wide information from the limited radius observations
making learning more difficult.

Action Space. The actions are defined in a continuous distribution of
accelerations in the range $[-7,7]$ m/s2 where each RV receives an
acceleration value. At most five RVs take actions, although more or less RVs
can be present in the network. If there are less, the remaining acceleration
values are not used. If there are more, extra RVs act as HVs.

Reward. As the RVs’ objective is to reduce queue length and increase average
vehicle velocity in east/west bound traffic, the reward function penalizes
both vehicle delay and vehicle standstills in traffic:

$r=-(D+SS),$ (4)

where $D$ is

$\frac{t*{\sum}((sl-v)/sl)}{k+eps},$ (5)

and $t$ is the current timestep, $sl$ is a vector of speed limits for each
edge of the network, $v$ is a vector of velocities for each vehicle in the
network, $k$ is the number of vehicles in the network, and $eps$ prevents
division by zero. The function $SS$ is

$SS=gain*num_{ss},$ (6)

where $gain$ is 0.2 and $num_{ss}$ is the number of standstill vehicles. Given
the reward is negative, the RVs’ goal is to minimize delay and standstill of
the vehicles.

####  III-B4 Merge Network

The merge network contains a highway and an on-ramp. The highway and on-ramp
respective flows can create stop-and-go waves along the highway and congest
the on-ramp, reducing the average velocity and outflow. The RVs’ goal is to
minimize the formation of such waves and increase average vehicle velocity.
RVs are only placed on the highway at a penetration rate of 10%

Observation Space. Our observation is a stack of five images, each of size
$84\times 84$ (shown in Fig 1, right D), centered on the RV. There can be
multiple RVs present at any given time. However, we observe that five is the
maximum. If there are less than five RVs present, the remaining stack is
padded with black images; if more, the extra RVs are treated as HVs. The image
dimensions correspond to $41.25$ m in real world.

Precise observations are a vector of the following [3, 4]: the velocities of
the following and leading vehicle for each RV; the difference in positions
between the RV and the following and leading vehicles; and the velocity of
each RV. HVs on the on-ramp are observed only if they are following vehicles
or have merged onto the highway.

Action Space. The actions are defined in a continuous distribution of
accelerations bounded by $[-1.5,1.5]$ m/s2. If there are more than five RVs,
the additional RVs act as HVs. If there are less, then the leftover RL actions
are not used.

Reward. The objective of the RVs is to improve the overall vehicle velocity
and increase the outflow of the network:

$r=\frac{\max({\parallel}v_{des}*1^{k}\parallel_{2}-{\parallel}v_{des}-v\parallel_{2},0)}{{\parallel}v_{des}*1^{k}{\parallel}_{2}}-H,$
(7)

where

$H=\alpha\sum_{i\epsilon RVs}\max[h_{\max}-h_{i}(t),0],$ (8)

and $h_{max}$ is emprically set to 1 and $h_{i}(t)$ is the headway of an RV at
$t$. The first term is Eq. 3, which is trying to improve the overall vehicle
velocity. The objective of $H$ is to penalize small headways between an RV and
an HV to discourage traffic bunching up and potentially causing stop-and-go
waves.

####  III-B5 Bottleneck Network

The bottleneck network simulates vehicles experiencing capacity drop [30]
where a network’s outflow significantly decreases after the network inflow
surpasses a threshold. The goal of the RVs is to improve outflow. The
bottleneck network represents a bridge with lanes decreasing from $4\times l$
to $2\times l$ to $l$ (where $l$ is a scaling factor and is one for our work).
The penetration rate of the RV is $10\%$.

Observation Space. Our observation consists of $15$ stacked images, each of
size $84\times 84$ (shown in Fig. 1 right E), as a maximum of $15$ RVs are
placed in the network. If there are less than 15 RVs, the remaining stack is
filled with black images; if more than 15 RVs, additional RVs are treated as
HVs. The image dimensions correspond to a circle with a radius of $25$ m in
real world.

Precise observations are a vector comprised of the following [3, 4]: the mean
positions and velocities of all human drivers for each lane for each user-
defined segment of the road network; the mean positions and velocities of the
RVs for each user-defined segment of the road network (unlike HVs, the lanes
RVs are present on are not tracked); and the outflow of the network (veh/hr)
over the last five seconds. This observation is difficult to design as it
consists of both microscopic and macroscopic traffic statistics. In addition,
since it focuses on segments of the bottleneck rather than individual
vehicles, it can be considered as global information. In contrast, our
observations only need to contain local information.

Action Space. Unlike the previously defined environments where the action is
acceleration, here the action is defined as velocity in the range $[0.01,23]$
m/s. If there are less than $15$ RVs, the outstanding RL actions are not used;
if more, the extra RVs assume the role of HVs.

Reward. The objective is to increase the outflow of the network and reduce the
frequency of capacity drops:

$r_{t}=\sum^{i=t}_{i=t-\frac{5}{{\Delta}t}}\frac{N_{exit}(i)}{5({\Delta}t*N_{lanes}*500)},$
(9)

where $N_{exit}(i)$ is the number of vehicles that left the network at
timestep i over the last five seconds, ${\Delta}t$ is the simulation timestep,
and $N_{lanes}$ is number of lanes.

##  IV Experiments and Results

In this section, we present our experimental setup and detail the training and
evaluation results obtained for each tested road network using both image and
precise observations.

Figure 2: Results for the ring, figure eight, merge, and bottleneck networks.
TOP-LEFT: An RV with image observations achieves the same performance as an RV
with precise observations. Stop-and-go waves are prevented at all densities.
TOP-RIGHT: Similar to the ring network, an RV with image observations achieves
hybrid traffic control comparable to an RV with precise observations. BOTTOM-
LEFT: In a majority of scenarios, RVs with image observations achieve similar
performance as RVs with precise observations. In the $2000/100$ inflows
scenario, the RVs using image observations even surpass the performance of the
RVs using precise observations by 26%. BOTTOM-RIGHT: RVs with image
observations outperform the performance of RVs with precise observations at
$2000$ inflow by $6$%, but in general, the performance is lower, which is
likely due to the absence of global information in the image observations.

###  IV-A Experiment Setup

We train RVs using the Proximal Policy Optimization (PPO) [29], with
hyperparameters given in Table I. The HVs are operated by Intelligent Driver
Model (IDM) [31] with stochastic noise in the range $[-0.2,0.2]$ added to
account for heterogeneous driving behaviors. RVs are trained for $200$
episodes. Table II provides further simulation details. Warmup refers to the
number of timesteps before the activation of RL policies. Horizon refers to
the episode length and ${\Delta}t$ is the simulation timestep.

TABLE I: Hyperparameters of PPO [29] used in our experiments. Hyperparameter | Value
---|---
Minibatch Size | 128
Clipping | 0.3
$\gamma$ | 0.999
$\lambda$ | 0.97
KL Initialization | 0.2
KL Target | 0.02
Value Function Coefficient | 1.0
Entropy Coefficient | 0.0
Learning Rate | 5e-05

Trained policies in each network are evaluated for $10$ rollouts, and results
are presented as averages. Convolutional Neural Networks with filters
(formatted as [out channels, kernel size, stride]) of $[16,8,4]$, $[32,4,2]$,
and $[256,11,1]$ are adopted. Experiments are conducted using i7-$12700$k CPU
with $32$G RAM.

TABLE II: Simulation settings for the different road networks. ${\Delta}t$ is the simulation timestep. Warmup is the timestep duration where RVs act as HVs, and horizon is the timestep duration where RVs transition to new states and take actions used for learning.  Network | ${\Delta}t$ | Warmup | Horizon
---|---|---|---
Ring | $0.1$ | $3000$ | $3000$
Figure Eight | $0.1$ | $0$ | $1500$
Intersection | $0.1$ | $0$ | $400$
Bottleneck | $0.5$ | $40$ | $1000$
Merge | $0.5$ | $0$ | $750$

###  IV-B Results

####  IV-B1 Ring Network

The ring network hosts $21$ HVs and one RV where the RV’s objective is to
remove stop-and-go waves. At initialization, the $22$ vehicles are uniformly
placed from each other and act as HVs for $3000$ warmup timesteps. During this
period, stop-and-go waves will form and persist. Afterwards, the RV is
activated for $3000$ timesteps. During training, the RV is trained on rings
with circumference sampled uniformly from $[220,270]$. For testing, this range
is extended to $[210,290]$.

The results are shown in Fig. 2 TOP-LEFT. Our approach using image
observations is represented in blue, while the result of using precise
observations is represented in orange. The vertical lines represent the bounds
for what densities (converted from the ring length) are seen during training.
Our results show, at all densities tested, the RV with image observations is
able to prevent stop-and-go waves and achieve the same-level performance as of
using precise observations.

Fig. 3 shows the time-space diagram of all vehicles over an episode. The
shockwaves from $200$ to $300$ seconds (one second equals $10$ timesteps)
reflect stop-and-go traffic. After $300$ seconds, the image-trained RV starts
taking action. With an initial period of acceleration, the RV then stabilizes
the traffic. For this demonstration, the horizon is set to $5000$ timesteps
($500$ seconds) to illustrate the generalizability of our approach beyond the
training horizon.

Figure 3: Time-space diagrams showing stop-and-go waves being prevented after
RVs start taking action. The experiments are conducted on the ring network
with a length of $260$ m. Stop-and-go waves form around $200$ to $300$ seconds
($10$ timesteps equals one second). LEFT: An RV trained on image observations
is able to prevent stop-and-go waves once it begins taking actions similar to
an RV trained on precise observations; RIGHT: An RV trained with only position
information (without velocity information) can also prevent stop-and-go waves.

####  IV-B2 Figure Eight Network

The figure-eight network is comprised of $13$ HVs and one RV driving with no
warmup and a horizon of $1500$ timesteps. The efficacy of a trained RV is
measured by the average vehicle velocity in the network. Previously, the RV is
trained only on a single, inner-loop radius [3] (inner-loop radius is used to
calculate the overall network length), but we expand the scenario by training
on the range $[20,30]$ m and expand this range to $[18,32]$ m during
evaluation.

Our results are shown in Fig. 2 TOP-RIGHT. We evaluate on average vehicle
velocity at different network densities. The ability to perform hybrid traffic
control of an RV with image observations is the same as an RV with precise
observations, despite that the image-trained RV only receives local
information while the counterpart receives complete global information.

####  IV-B3 Intersection Network

In the intersection network, north/south traffic inflow is set to $1333$
vehicles per hour (veh/hr) and east/west inflow is set to $500$ veh/hr. The
RVs’ objective is to minimize queue length and increase the average velocity
of traffic along the east/west directions, where queues form.

Results are shown in Table III where we examine the average velocity of all
vehicles and queue lengths along the east/west directions. RVs with image
observations can provide similar performance to RVs with precise observations
in regard to queue length. The average vehicle velocity of RVs with image
observations is less than RVs with precise observations. We believe this
performance difference is due to precise global observations knowing exactly
what edges vehicles are on and their corresponding velocities, which allow the
RVs to know when HVs are at standstill in the east/west directions. Both RV
types outperform HVs in both evaluation metrics.

Fig. 4 illustrates the development of queues with only HVs versus RVs with
image observations. The southbound RV in the right image is slowing down
momentarily, which allows east/westbound HVs to safely cross the intersection.
With only HVs, they travel at velocities that cause queues in the east/west
directions to develop.

TABLE III: Results for intersection network. Average velocity is the mean velocity of vehicles traveling east/westbound, and queue length is the number of cars waiting to cross the intersection in the east or west directions. | Average Velocity (m/s) | Queue Length
---|---|---
Human Drivers |  $3.70$ $\pm$ $0.00$ |  $5$ vehicles
Precise Obs. |  $5.90$ $\pm$ $0.23$ |  $3$ vehicles
Image Obs. | 4.75 $\pm$ $0.02$ |  $3$ vehicles
Figure 4: Queue length comparison between all HVs and hybrid traffic on the
intersection network. LEFT: With only HVs, the queue length is five (in both
east/west directions) by episode termination. North/southbound HVs travel at
speeds that allow safe crossing infrequently causing queue growth over time.
RIGHT: With RVs, the queue length is only three by episode termination. This
shows that RVs can assist traffic on lanes where they are not present. Note
that HVs are blue, instead of white.

####  IV-B4 Merge Network

The merge network simulates vehicles entering a highway from an on-ramp. This
experiment evaluates on a set of five combinations of highway/merge inflow
rates: $\\{2000/100,1800/300,1500/500,1500/300,1000/500\\}$. The different
inflow combinations result in varying levels of congestion due to vehicles
merging onto the highway. In either case, stop-and-go waves form on the
highway, resulting in decreased average velocity of all vehicles. This
combination of inflows has not been previously studied, except for the
$2000/100$ inflow rates [3, 4].

Fig. 2 BOTTOM-LEFT presents our results. HVs’ performance is provided for
comparison. RVs with image observations have similar performance to RVs with
precise observations at $1500/300$ and $1000/500$ inflows rates. The latter
outperforms the former in the $1800/300$ inflows scenario, but the former (our
approach) outperforms the latter in the $1500/500$ and $2000/100$ inflows
scenarios. RVs with image observations provide the largest performance
improvement with a $3.79$ m/s—a $26\%$ increase—over using precise
observations in the $2000/100$ scenario. The $1500/500$ scenario is difficult
to learn on, evidenced by both RV types not being able to outperform HVs. In
fact, RVs with precise observations slightly underperform compared to HVs.

####  IV-B5 Bottleneck Network

The bottleneck network investigates hybrid traffic control on a bridge with
decreasing lane capacity forming a bottleneck at the end. The RVs’ objective
is to improve outflow (vehicles exiting the network per hour) at the
bottleneck. A set of four inflows is tested, i.e.,
$\\{2000,2100,2300,2500\\}$, with the goal to capture moderate to severe
congestion levels. The range is chosen to demonstrate the congestion effects
on the system, while still allowing for potential improvement through hybrid
traffic control.

Results for bottleneck are presented in Fig. 2 BOTTOM-RIGHT. At $2000$ inflow,
image-trained RVs significantly outperform RVs with precise observations by
$6\%$. At $2300$ and $2500$ inflow rates, RVs with precise observations
outperform our approach. A crossover point occurs around $2100$, where HVs
start to perform worse than RVs. At lower inflows, HVs’ performance is higher
than RVs suggesting that RVs may hinder network performance by attempting to
alleviate congestion that is not present. The bottleneck scenario experiences
high levels of congestion throughout the network. We hypothesize this is the
reason that causes our approach to underperform precise-trained RVs, since the
image observations do not contain network-wide traffic information.

####  IV-B6 Position-only Observation Space

We conduct additional experiments to test position-only observations in
training RVs under precision information. The purpose of this experiment is to
analyze whether RVs can still be leveraged to alleviate traffic congestion
given only static positional information, which is similar to positional
inference using image observations. This experiment is conducted on the ring
network. The observation space changes to a vector of the difference between
the RV’s position and the leading vehicle’s position. Fig. 3 RIGHT shows the
time-space diagram for this experiment. As a result, an RV with only position
information can achieve the same level of performance as of using complete
information (i.e., both position and velocity). This result further solidifies
our approach to using image observations without explicitly including the
velocity information.

##  V Conclusion

In this work, we demonstrate the ability of robot vehicles (RVs) to perform
hybrid traffic control using reinforcement learning (RL) policies trained on
image observations. We examine RVs trained on image observations in five
different scenarios: ring, figure eight, intersection, bottleneck, and merge.
Additionally, we expand on the figure eight network by training the RL
policies on a range of network lengths, and we expand the bottleneck and merge
networks by training and testing on inflow rates previously untested. We show
that RVs trained on image observations have competitive performances to RVs
trained on precise observations.

The use of image observations enables the adoption of existing infrastructure
rather than developing a complex, interconnected sensor network that incurs
significant costs for our road networks. In addition, our approach allows for
end-to-end training of hybrid traffic control. This overcomes the challenge of
manually designing the observation space for incorporating various global and
local traffic information, which has been an obstacle to training hybrid
traffic on heterogeneous road networks.

###  V-A Assumptions About RVs

Note that we do not assume our RVs to be fully autonomous vehicles with
equipment and sensors to allow for complete control. Our RVs control only
their acceleration (or velocity), which can be achieved by controlling the
throttle signal through a control mechanism, using images that do not require
significant computational resources to process and receive actions from.

###  V-B Future Work

In the future, we aim to advance this study in several directions. First, we
are interested in testing our approach in more complex and larger scenarios
[32, 33], which can be calibrated using mobile data to reflect real-world
traffic conditions [34, 35, 36]. Second, we would like to incorporate
additional generic information such as traffic state predictions [37, 38] and
vehicle trajectories [39, 40] into our observation space for potential
improvement. Third, we want to improve the resilience of our approach by
taking adversarial attacks [41, 42, 43] into account. Lastly, we are
interested in studying hybrid traffic control under other mobility-related
topics such as traffic safety [44] and micromobility [45].

## References

  * [1] Phil Goodwin.  The economic costs of road traffic congestion.  2004\.
  * [2] Richard Arnott and Kenneth Small.  The economics of traffic congestion.  American scientist, 82(5):446–455, 1994.
  * [3] Cathy Wu, Aboudy Kreidieh, Kanaad Parvate, Eugene Vinitsky, and Alexandre M Bayen.  Flow: Architecture and benchmarking for reinforcement learning in traffic control.  arXiv preprint arXiv:1710.05465, 10, 2017.
  * [4] Eugene Vinitsky, Aboudy Kreidieh, Luc Le Flem, Nishant Kheterpal, Kathy Jang, Cathy Wu, Fangyu Wu, Richard Liaw, Eric Liang, and Alexandre M Bayen.  Benchmarks for reinforcement learning in mixed-autonomy traffic.  In Conference on robot learning, pages 399–409. PMLR, 2018.
  * [5] Zhongxia Yan and Cathy Wu.  Reinforcement learning for mixed autonomy intersections.  In 2021 IEEE International Intelligent Transportation Systems Conference (ITSC), pages 2089–2094. IEEE, 2021.
  * [6] Dawei Wang, Weizi Li, Lei Zhu, and Jia Pan.  Learning to control and coordinate hybrid traffic through robot vehicles at complex and unsignalized intersections.  arXiv preprint arXiv:2301.05294, 2023.
  * [7] Fang-Chieh Chou, Alben Rome Bagabaldo, and Alexandre M Bayen.  The lord of the ring road: a review and evaluation of autonomous control policies for traffic in a ring road.  ACM Transactions on Cyber-Physical Systems (TCPS), 6(1):1–25, 2022\.
  * [8] State of California Department of Transportation.  Caltrans pems.  http://pems.dot.ca.gov/, 2022.
  * [9] Colorado Springs ATMS.  Advanced traffic management system.  https://coloradosprings.gov/traffic-and-transportation-engineering/page/traffic-management/, 2022\.
  * [10] Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling.  The arcade learning environment: An evaluation platform for general agents.  Journal of Artificial Intelligence Research, 47:253–279, 2013.
  * [11] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller.  Playing atari with deep reinforcement learning.  arXiv preprint arXiv:1312.5602, 2013.
  * [12] Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, et al.  Model-based reinforcement learning for atari.  arXiv preprint arXiv:1903.00374, 2019.
  * [13] Farhang Sahba, Hamid R Tizhoosh, and Magdy MA Salama.  A reinforcement learning framework for medical image segmentation.  In The 2006 IEEE international joint conference on neural network proceedings, pages 511–517. IEEE, 2006.
  * [14] Hanane Allioui, Mazin Abed Mohammed, Narjes Benameur, Belal Al-Khateeb, Karrar Hameed Abdulkareem, Begonya Garcia-Zapirain, Robertas Damaševičius, and Rytis Maskeliūnas.  A multi-agent deep reinforcement learning approach for enhancement of covid-19 ct image segmentation.  Journal of personalized medicine, 12(2):309, 2022.
  * [15] Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi.  Dream to control: Learning behaviors by latent imagination.  arXiv preprint arXiv:1912.01603, 2019.
  * [16] Danijar Hafner, Timothy Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson.  Learning latent dynamics for planning from pixels.  In International conference on machine learning, pages 2555–2565. PMLR, 2019.
  * [17] Manuel Watter, Jost Springenberg, Joschka Boedecker, and Martin Riedmiller.  Embed to control: A locally linear latent dynamics model for control from raw images.  Advances in neural information processing systems, 28, 2015.
  * [18] Yu Shen, Weizi Li, and Ming C. Lin.  Inverse reinforcement learning with hybrid-weight trust-region optimization and curriculum learning for autonomous maneuvering.  In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 7421–7428, 2022.
  * [19] Bibek Poudel, Thomas Watson, and Weizi Li.  Learning to control dc motor for micromobility in real time with reinforcement learning.  In IEEE International Conference on Intelligent Transportation Systems (ITSC), pages 1248–1254, 2022.
  * [20] Eshagh Kargar and Ville Kyrki.  Vision transformer for learning driving policies in complex multi-agent environments.  arXiv preprint arXiv:2109.06514, 2021.
  * [21] Alexey Dosovitskiy, German Ros, Felipe Codevilla, Antonio Lopez, and Vladlen Koltun.  Carla: An open urban driving simulator.  In Conference on robot learning, pages 1–16. PMLR, 2017.
  * [22] Peide Cai, Sukai Wang, Hengli Wang, and Ming Liu.  Carl-lead: Lidar-based end-to-end autonomous driving with contrastive deep reinforcement learning.  arXiv preprint arXiv:2109.08473, 2021.
  * [23] Óscar Pérez-Gil, Rafael Barea, Elena López-Guillén, Luis M Bergasa, Carlos Gomez-Huelamo, Rodrigo Gutiérrez, and Alejandro Diaz-Diaz.  Deep reinforcement learning based control for autonomous vehicles in carla.  Multimedia Tools and Applications, 81(3):3553–3576, 2022.
  * [24] Zhejun Zhang, Alexander Liniger, Dengxin Dai, Fisher Yu, and Luc Van Gool.  End-to-end urban driving by imitating a reinforcement learning coach.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 15222–15232, 2021.
  * [25] Zhangjie Cao, Erdem Bıyık, Woodrow Z Wang, Allan Raventos, Adrien Gaidon, Guy Rosman, and Dorsa Sadigh.  Reinforcement learning based control of imitative policies for near-accident driving.  arXiv preprint arXiv:2007.00178, 2020.
  * [26] Xinlei Pan, Yurong You, Ziyan Wang, and Cewu Lu.  Virtual to real reinforcement learning for autonomous driving.  arXiv preprint arXiv:1704.03952, 2017.
  * [27] Harshal Maske, Tianshu Chu, and Uroš Kalabić.  Large-scale traffic control using autonomous vehicles and decentralized deep reinforcement learning.  In 2019 IEEE Intelligent Transportation Systems Conference (ITSC), pages 3816–3821. IEEE, 2019.
  * [28] Fangyu Wu and Alexandre M. Bayen.  Cscrs road safety fellowship report: A human-machine collaborative acceleration controller attained from pixel learning and evolution strategies.
  * [29] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  arXiv preprint arXiv:1707.06347, 2017.
  * [30] Meead Saberi and Hani S Mahmassani.  Empirical characterization and interpretation of hysteresis and capacity drop phenomena in freeway networks.  Transportation Research Record: Journal of the Transportation Research Board, Transportation Research Board of the National Academies, Washington, DC, 2013.
  * [31] Martin Treiber, Ansgar Hennecke, and Dirk Helbing.  Congested traffic states in empirical observations and microscopic simulations.  Physical review E, 62(2):1805, 2000.
  * [32] David Wilkie, Jason Sewall, Weizi Li, and Ming C. Lin.  Virtualized traffic at metropolitan scales.  Frontiers in Robotics and AI, 2:11, 2015.
  * [33] Qianwen Chao, Huikun Bi, Weizi Li, Tianlu Mao, Zhaoqi Wang, Ming C. Lin, and Zhigang Deng.  A survey on visual traffic simulation: Models, evaluations, and applications in autonomous driving.  Computer Graphics Forum, 39(1):287–308, 2020.
  * [34] Weizi Li, Dong Nie, David Wilkie, and Ming C. Lin.  Citywide estimation of traffic dynamics via sparse GPS traces.  IEEE Intelligent Transportation Systems Magazine, 9(3):100–113, 2017.
  * [35] Weizi Li, David Wolinski, and Ming C. Lin.  City-scale traffic animation using statistical learning and metamodel-based optimization.  ACM Trans. Graph., 36(6):200:1–200:12, 2017.
  * [36] Weizi Li, Meilei Jiang, Yaoyu Chen, and Ming C. Lin.  Estimating urban traffic states using iterative refinement and wardrop equilibria.  IET Intelligent Transport Systems, 12(8):875–883, 2018.
  * [37] Lei Lin, Weizi Li, and Srinivas Peeta.  Efficient data collection and accurate travel time estimation in a connected vehicle environment via real-time compressive sensing.  Journal of Big Data Analytics in Transportation, 1(2):95–107, 2019\.
  * [38] Lei Lin, Weizi Li, and Lei Zhu.  Data-driven graph filter based graph convolutional neural network approach for network-level multi-step traffic prediction.  Sustainability, 14(24):16701, 2022.
  * [39] Weizi Li, David Wolinski, and Ming C. Lin.  ADAPS: Autonomous driving via principled simulations.  In IEEE International Conference on Robotics and Automation (ICRA), pages 7625–7631, 2019.
  * [40] Lei Lin, Weizi Li, Huikun Bi, and Lingqiao Qin.  Vehicle trajectory prediction using LSTMs with spatial-temporal attention mechanisms.  IEEE Intelligent Transportation Systems Magazine, 14(2):197–208, 2022.
  * [41] Bibek Poudel and Weizi Li.  Black-box adversarial attacks on network-wide multi-step traffic state prediction models.  In IEEE International Conference on Intelligent Transportation Systems (ITSC), pages 3652–3658, 2021.
  * [42] Yu Shen, Laura Zheng, Manli Shu, Weizi Li, Tom Goldstein, and Ming C. Lin.  Gradient-free adversarial training against image corruption for learning-based steering.  In Advances in Neural Information Processing Systems (NeurIPS), pages 26250–26263, 2021.
  * [43] Michael Villarreal, Bibek Poudel, Ryan Wickman, Yu Shen, and Weizi Li.  Autojoin: Efficient adversarial training for robust maneuvering via denoising autoencoder and joint learning.  2022\.
  * [44] Lei Lin, Feng Shi, and Weizi Li.  Assessing inequality, irregularity, and severity regarding road traffic safety during covid-19.  Scientific Reports, 11(13147), 2021.
  * [45] Lei Lin, Weizi Li, and Srinivas Peeta.  Predicting station-level bike-sharing demands using graph convolutional neural network.  In Transportation Research Board 98th Annual Meeting (TRB), 2019\.