# Dynamic Vertex Replacement Grammars

Daniel Gonzalez Cedre
University of Notre Dame
Notre Dame, USA Justus Isaiah Hibshman
University of Notre Dame
Notre Dame, USA Timothy La Fond
Lawrence-Livermore Nat’l Lab.
Livermore, USA
Grant Boquet
Lawrence-Livermore Nat’l Lab.
Livermore, USA Tim Weninger
University of Notre Dame
Notre Dame, USA

###### Abstract

Context-free graph grammars have shown a remarkable ability to model
structures in real-world relational data. However, graph grammars lack the
ability to capture time-changing phenomena since the left-to-right transitions
of a production rule do not represent temporal change. In the present work, we
describe dynamic vertex-replacement grammars (DyVeRG), which generalize vertex
replacement grammars in the time domain by providing a formal framework for
updating a learned graph grammar in accordance with modifications to its
underlying data. We show that DyVeRG grammars can be learned from, and used to
generate, real-world dynamic graphs faithfully while remaining human-
interpretable. We also demonstrate their ability to forecast by computing
dyvergence scores, a novel graph similarity measurement exposed by this
framework.111https://github.com/daniel-gonzalez-cedre/DyVeRG.

##  1 Introduction

Like the string grammars upon which they are based, graph grammars usually
deal with static data. Although it might be attractive to think of LHS
$\rightarrow$ RHS replacement schemes as indicative of change, growth, or
evolution over time, this is rarely the case in grammar-based formalisms.
Instead, grammars are typically used to represent hierarchical refinements of
a static structure. The replacements that occur by applying production rules
rarely have anything to do with time.

However, modeling time-varying data for real-life processes is fundamentally
important for many scholars and scientists. Because graphs are capable of
expressing immensely-complicated discrete topological relationships, they are
widely used to model real world phenomena. In particular, temporal graph
models have come to prominence to account for the time-varying nature of many
real phenomena. For example, the Temporal Exponential Random Graph Model
(TERGM) [18], Dynamic Stochastic Block Model (ARSBM) [27], and certain
versions of newer Graph Neural Network models (GraphRNN, GRAN) [41, 26] are
able to fit sequential graph data and make predictions about future
relationships, but these models are difficult to inspect and tend to break
down.

Graph grammars have seen a recent increase in popularity, with applications in
molecular synthesis [23, 15, 39], software engineering [24, 25], and robotics
[43]. Related models focusing on subgraph-to-subgraph transitions are readily
interpretable, but need to be hand-tuned to model subgraphs of a predetermined
(usually very small) size, usually for computational complexity reasons [20,
5]. These transition models tend to set out a schema for the set of permitted
transitions and perform modeling by simply counting transition frequencies.
Despite their simplicity, these transition models are effective tools for
understanding changes in dynamic systems. However, these models struggle with
larger changes outside of 3-or-4-node (or similarly small) subgraph sizes
[30].

More recently, researchers have found data-driven ways to learn representative
hyperedge replacement grammars (HRG) [2, 38] and vertex replacement grammars
(VRG) [32, 33]. These models permit the extraction of production rules from a
graph and the resulting grammar can be used to reconstruct the graph or
generate similar graphs. However, as discussed earlier, these models are still
limited by the inherent static nature of the formalism. The lack of a dynamic,
interpretable, learnable model presents a clear challenge to modeling real-
world relational data.

Figure 1: An example of a rule transition comprised of two production rules:
the left-rule extracted from a graph at time $t$ and the right-rule updated at
time $t+1$. Here we see evidence of triadic closure, the disappearance of a
node with its incident edge, and resulting changes to the LHS symbol.

In the present work, we tackle this challenge by introducing the Dynamic
Vertex Replacement Grammars (DyVeRG). As the name implies, this model extends
the VRG framework, which typically begins with a hierarchical clustering of
the graph and then extracts graph rules in a bottom-up fashion from the
resulting dendrogram. In order to adapt VRGs to the dynamic setting, the
DyVeRG model finds stable mappings between filtrations of the nodes in the
dynamic graph across time. The filtration mappings provide a transparent a way
to inspect the changes in the graph without significant performance
degradation.

This dynamic graph grammar takes the form of a sequence of production rules we
call rule transitions that are interpretable and inspectable. An example of
such a rule transition is illustrated in Fig. 1: the rule on the left is
extracted from a graph $G_{t}$ at time $t$; the rule on the right covers the
same nodes, but corresponds to time $t+1$ and incorporates changes from
$G_{t+1}$. In this example, the nonterminal node on the LHS of the left
production rule signifies that the RHS has two boundary edges (used to connect
elsewhere in the graph). The RHS also has four terminal nodes and three
terminal edges. However, as the graph changes between times $t$ and $t+1$, the
topology of the rule on the right of Fig. 1 changes correspondingly. The blue
dotted edges illustrate the addition of one terminal edge and one new boundary
edge, which is why the nonterminal label on the LHS increased from 2 to 3. The
red nodes and wavy dotted lines represent the deletion of a node and edge
respectively across this temporal chasm.

The paper is organized as follows. We first introduce some basic concepts and
terminology. Then, we describe the DyVeRG model with the help of illustrations
and examples. We then introduce the dyvergence score, a byproduct of DyVeRG,
and explain how rudimentary forecasting can be done as well as the more-
traditional graph generation. Finally, we provide a quantitative and
qualitative analysis of the model on real-world dynamic graphs and compare its
predictive performance against other generative models.

##  2 Preliminaries

A graph $G=(V,E)$ is a set of nodes $V$ with a relation $E\subseteq V\times V$
defining edges between the nodes. We say that $G$ is connected if there is a
path within $G$ between any two nodes. If $E$ is symmetric, then we say $G$ is
undirected; otherwise, $G$ is directed. We say that $G$ is node-labeled if we
have a function $\lambda:V\to L$ that assigns a label from $L$ to each node in
$G$. If we have two such node-labeling functions, we call the graph doubly-
node-labeled. We say that $G$ is edge-weighted if we have a function
$\omega:E\to W$ assigning each edge in the graph some weight from $W$. If
these weights are natural numbers, then we say $G$ is a multigraph, whose edge
multiplicities are given by $\omega$.

There are two common ways to model temporality for graphs: as continuous
streams of (hyper-)edges, and as discrete sequences of graph snapshots [22].
In the present work, we consider the latter form of dynamic graph, which we
represent as a (finite) sequence $\left\langle
G_{t}\right\rangle_{t=0}^{T}=\left\langle G_{0},\dots G_{T}\right\rangle$ of
graphs $G_{t}=(V_{t},E_{t})$.

###  2.1 Context-Free Grammars.

A context-free grammar (CFG) on strings is determined by a finite set of
nonterminal symbols $N$ with a distinguished starting symbol $S\in N$ and
finite a set of terminal symbols $T$, along with a finite set of production
rules $R\subseteq N\times(N\cup T)^{*}$. Each rule $P_{i}\in R$ represents a
transition from a left-hand side (LHS) nonterminal to a finite sequence of
symbols on the right-hand side (RHS), each of which is either terminal or
nonterminal. We say $P_{i}$ is terminal if it only contains terminal symbols;
otherwise, $P_{i}$ is nonterminal.

Given a string $\Sigma=\sigma_{1}\dots\sigma_{i}\dots\sigma_{n}\in(N\cup
T)^{*}$, the application of a production rule $P_{i}$ to a particular
nonterminal symbol $\sigma_{i}\in N$ from $\Sigma$ involves replacing the
symbol $\sigma_{i}$ with the string on the RHS of $P_{i}$. Formally, the
result of applying $P_{i}=(\sigma_{i},\pi_{P_{i}})$ to $\sigma_{i}$ in
$\Sigma$ is a new string
$\tilde{\Sigma}=\left(\sigma_{1}\dots\sigma_{i-1}\right)\cdot\pi_{P_{i}}\cdot\left(\sigma_{i+1}\dots\sigma_{n}\right)$,
where $\cdot$ represents the string-concatenation operation.

###  2.2 Vertex-Replacement Graph Grammars.

A natural way to generalize CFGs would be to think of the characters in a
string like nodes in a graph. We can then think of CFG rules as producing
graphs whose nodes are arranged in a path, with attributes given by the
different characters in the language and boundary conditions specifying
whether or not additional characters can be added at the beginning or end of
the string. Clearly, changing the connectivity structure and boundary
conditions will lead to rules with more expressive RHS structures.

There are many specific formalisms and nuances, but generally a vertex-
replacement grammar (VRG) is given by a finite set of nonterminal symbols
$N\subseteq\mathbb{N}$ with the distinguished starting symbol $0\in N$ along
with a set of terminal symbols $T\subseteq V_{G}$ representing nodes in a
graph. The production rules $P_{i}$ for a VRG then look like transitions from
a nonterminal symbol $n\in N$ to a doubly-node-labeled multigraph
$\left(H,\lambda_{H},\delta_{H}\right)$ whose first node-labeling function
$\lambda_{H}:V_{H}\to N\cup T$ distinguishes between terminal and nonterminal
symbols, and whose second node-labeling function
$\delta_{H}:V_{H}\to\mathbb{N}$ assigns a natural number _boundary degree_ to
each node of $G$.

As was the case with CFGs, we apply rules at nonterminals by replacing those
symbols with the structure on the RHS of a suitable production rule, while
accounting for VRG rules’ nontrivial boundary conditions (i.e., the boundary
degrees). Given a connected, node-labeled multigraph
$G=(V_{G},E_{G},\lambda_{G})$ with a node $v\in V_{G}$ having nonterminal
label $\lambda_{G}(v)\in N$, the application of a rule
$P_{i}=(\lambda_{G}(v),(H,\lambda_{H},\delta_{H}))$ at $v$ consists of
replacing $v$ with the graph $H$ and rewiring the _broken edges_ —those edges
previously connected to $v$—to those nodes in $H$ such that the number of
broken edges incident on a node $v_{H}$ of $H$ does not exceed its boundary
degree $\delta(v_{H})$.

Random rewiring is the most rudimentary way to address the boundary condition.
If our data were augmented with node labels, we could guide the rewiring
process using an estimated assortativity mixing matrix, or by minimizing a
loss function computed over the nodes [33]. Even without node labels, we could
consider greedy rewiring strategies that try to reduce discrepancy along some
measured statistic of the data—e.g., modularity, average local clustering
coefficient, graphlet distribution. For simplicity, we consider only the
random approach in the present work.

Formally, we will say that a production rule
$P_{i}=(s,(H,\lambda_{H},\delta_{H}))$ is suitable for a node $v\in V_{G}$ if
$\lambda_{G}(v)=s$ and $\deg(v)=\sum_{v_{H}\in V_{H}}\delta_{H}(v_{H})$. This
means that the label associated with $v$ is the same as the nonterminal symbol
$P_{i}$ is expecting, and that the number of broken edges $v$ will leave
behind is the same as the total number of boundary edge slots $H$ has
available. With these conditions, the application of a suitable $P_{i}$ at a
node $v$ results in a well-defined, though not necessarily deterministic,
vertex-to-subgraph substitution.

Typically, we only distinguish between the rules in a grammar _up to
isomorphism_ once an appropriate notion of isomorphism for production rules is
specified. We say two rules
$\dot{P}=\left(\dot{s},(\dot{H},\dot{\lambda},\dot{\delta})\right)$ and
$\ddot{P}=\left(\ddot{s},(\ddot{H},\ddot{\lambda},\ddot{\delta})\right)$ from
a VRG are rule-isomorphic if and only if $\dot{s}=\ddot{s}$ and there is a
graph isomorphism $\dot{H}\cong\ddot{H}$ that preserves the labels from
$\dot{\lambda}$ and $\ddot{\lambda}$ (but not necessarily $\dot{\delta}$ and
$\ddot{\delta}$).

###  2.3 Filtrations.

A filtration of a graph $G=(V,E)$ is a sequence of node partitions
$\mathcal{F}=\langle F_{i}\rangle_{i=1}^{n}$, where each $F_{i}$ partitions
the node set $V$ into mutually-disjoint subsets—called _covers_ —so that each
$F_{i}$ is a refinement of $F_{i+1}$. When mining real-world networks,
filtrations are often the result of hierarchical node clusterings [13, 4],
$k$-core decompositions [11, 31], and, more recently, methods [28, 34]
inspired by persistent homology [10] and topological data analysis [7]. The
aforementioned methods usually produce filtrations as an intermediate result
for an analysis of a network involving, for example, community detection [42],
representation learning [40], or visualization [9]. Filtrations lend
themselves well to generative approaches to network structures since they can
highlight salient hierarchical and recursive patterns. Vertex-replacement
graph grammars can induce filtrations (cf. Sec. 3.1) suitable for dynamic
graph modeling.

##  3 Dynamic Vertex-Replacement Grammars

Incredible advances in theory and application have enabled researchers to
parse real-world networks by learning an appropriate graph grammar—including
vertex replacement schemes [32, 33, 15], hyperedge replacement schemes [38,
2], and Kemp-Tennenbaum [19] grammars. An important limitation of these
established formalisms is their semantic inability to express temporality in
terms of change to their underlying data. This presents a serious problem for
practitioners: time does not stand still, and new data may lead to changes in
prior beliefs. By associating the grammar extracted from a dataset with a
filtration on the data, and describing how filtrations on graphs produce
compatible grammars, we construct temporal transitions between grammars by
defining transitions between their associated filtrations, which are driven by
changes in the data. In the proceeding sections, we detail the Dynamic Vertex-
Replacement Grammar (DyVeRG) framework for generalizing VRGs in the time
domain.

###  3.1 Extracting Rules.

We describe in this section how to parse a graph with a VRG and how its
associated filtration is computed. For simplicity, we focus on just two
temporally-sequential graphs $G_{t}=(V_{t},E_{t})$ and
$G_{t+1}=(V_{t+1},E_{t+1})$ at a time, though the idea generalizes to an
arbitrarily-long finite sequence of graphs. First, an initial filtration
$\mathcal{F}_{t}^{\text{clust}}$ on $G_{t}$ is produced using the Leiden
hierarchical clustering algorithm [35]. We choose to use Leiden for our
analyses as opposed to the myriad alternatives—the Louvain algorithm [6],
smart local moving [36], hierarchical Markov clustering [37], recursive
spectral bi-partitioning [17]—because its iterative modularity-maximization
approach is intuitively appealing, and it realizes better performance [35]
than Louvain and smart local mover (on which Leiden is based) while remaining
efficient on larger graphs.

Taking inspiration from clustering-based node replacement grammars [32], we
use the filtration $\mathcal{F}_{t}^{\text{clust}}$ derived from the
hierarchical clustering to recursively extract rules for the grammar. Starting
from the bottom, we consider subfiltrations covering at most $\mu$ nodes
(terminal or nonterminal) total, where $\mu\in\mathbb{N}_{+}$ is set a priori
to limit the maximum size of any rule’s RHS. Among all subfiltrations of size
at-most $\mu$, we then select a subfiltration $\mathcal{F}^{*}$ that minimizes
the overall description length of the grammar. $\mathcal{F}^{*}$ then
determines a rule $P^{*}$ that gets added to our grammar and
$\mathcal{F}_{t}^{\text{clust}}$ is compressed until every node is in the same
cover, as described by Sikdar  _et al._ [32].

(a) Graph $G_{t}$.

(b) Clustering $\mathcal{F}_{t}^{\text{clust}}$.

(c) Grammar $\mathcal{F}_{t}^{\text{gram}}$.

(d) Rule decomposition.

Figure 2: Overview of the extraction process for a VRG on a static graph
$G_{t}$ pictured in (a). A filtration induced by a hierarchical clustering is
shown in (b), from which the rules in (d) are extracted bottom-up. At the same
time, the filtration in (c) is derived from the node coverings the extracted
rules produce.

Concurrently, we also construct a filtration $\mathcal{F}_{t}^{\text{gram}}$
whose node covers are determined by the right-hand sides of the rules in the
grammar as they are extracted. The filtration $\mathcal{F}_{t}^{\text{gram}}$
acts as a rule-based hierarchical decomposition of $G_{t}$, keeping track of
the parallel hierarchical structure shared by the rules in the grammar and the
nodes in the graph. This naturally produces a one-to-one correspondence
between the rules $R_{t}=\left\\{P_{t,1},\dots P_{t,r}\right\\}$ in our
(unweighted) grammar and their corresponding covers in
$\mathcal{F}_{t}^{\text{gram}}$, allowing us to construct a surjective
association $f_{t}:V_{t}\twoheadrightarrow R_{t}$ between each node $v\in
V_{t}$ and the unique rule $f_{t}(v)\in R_{t}$ that was extracted with $v$ as
a terminal node. Further, we keep track of the particular terminal symbol node
on the right-hand side of $f_{t}(v)$ corresponding to $v$ when $f_{t}(v)$ was
extracted. We call this $\alpha_{t}(v)$, the _alias_ of $v$, where
$\alpha_{t}:V_{t}\hookrightarrow T$. An illustration of this process on a
small example network is shown in Fig. 2. The two filtrations are highlighted
along with a hierarchical decomposition of the graph induced by the grammar’s
rules.

The _root_ of a grammar is defined to be the rule whose left-hand side is the
distinguished starting symbol $S$. Clearly, this rule covers every node in
$G_{t}$. Given two rules $\dot{P}_{t},\ddot{P}_{t}\in R_{t}$, we say
$\dot{P}_{t}$ is an _ancestor_ of $\ddot{P}_{t}$ _iff_ every node covered by
$\ddot{P}_{t}$ in the filtration is also covered by $\ddot{P}_{t}$. If
additionally $\dot{P}_{t}\neq\ddot{P}_{t}$, then it is a _proper ancestor_. We
define one rule to be a _descendant_ of another conversely to how ancestors
are defined. Finally, a _common ancestor_ of a set of rules
$\tilde{R}_{t}\subseteq R_{t}$ is rule $\tilde{P}_{t}$ that is an ancestor of
rule in $\tilde{R}_{t}$, and the _least common ancestor_ is the one having no
common ancestor of $\tilde{R}$ as a proper descendant. Note that the least
common ancestor of a nonempty subset of $R_{t}$ always exists since the root
rule is an ancestor of every rule in $\mathcal{G}_{t}$.

###  3.2 Updating the Filtration

(a) Graph $G_{t+1}$.

(b) Updated filtration $\mathcal{F}_{t+1}^{\text{gram}}$.

(c) Updated grammar.

Figure 3: The graph from 2(a), the filtration from 2(c), and the grammar from
2(d) are shown here with changes from time $t+1$. The changes to $G_{t+1}$ in
(a) stimulate changes to the filtration in (b), modifying the corresponding
rules in the grammar (c). Following Fig. 1, the node and edge addition is
shown in blue, while node and edge removal is indicated in red. Nonterminal
nodes’ borders are colored blue or red if they increased or decreased in value
respectively.

We will refer interchangeably to the covers in the filtration
$\mathcal{F}_{t}^{\text{gram}}$ and the rules $P_{t,i}\in R_{t}$ in the
grammar $\mathcal{G}_{t}$. For a visual summary of the proceeding description,
please refer to Fig. 3. First, we categorize the edges $(u,v)\in E_{t}\cup
E_{t+1}$:

  1. i.

_persistent_ : $u\in V_{t}$, $v\in V_{t}$, $u\in V_{t+1}$, $v\in V_{t+1}$,
and $(u,v)\in E_{t}\cap E_{t+1}$

  2. ii.

_internal additions_ : $u\in V_{t}$, $v\in V_{t}$, $u\in V_{t+1}$,
$v\in V_{t+1}$, and $(u,v)\in E_{t+1}\setminus E_{t}$

  3. iii.

_frontier additions_ : $u\in V_{t}$, $v\not\in V_{t}$, $u\in V_{t+1}$,
$v\in V_{t+1}$, and $(u,v)\in E_{t+1}\setminus E_{t}$

  4. iv.

_external additions_ : $u\not\in V_{t}$, $v\not\in V_{t}$, $u\in V_{t+1}$,
$v\in V_{t+1}$, and $(u,v)\in E_{t+1}\setminus E_{t}$

  5. v.

_edge deletions_ : $u\in V_{t}$, $v\in V_{t}$, and $(u,v)\in E_{t}\setminus
E_{t+1}$

Examples of edges from each category are demonstrated in Fig. 4. These classes
determine how each edge induces a change in the filtration: class i. edges do
not influence the filtration, class ii. edges add new connections between
already-existing nodes (thus altering the induced subgraph covers of the
filtration) class iii. edges introduce a new neighbor for an already-existing
node, class iv. edges produce two entirely-new neighboring nodes, and class v.
edges account for the removal of connections from the graph, which may or may
not be associated with nodes’ exodus from the network. Of these, only classes
iii., iv., and v. are capable of causing structural changes to the hierarchy
of the filtration, but all except for class i. edges will affect the grammar’s
rules.

(a) A graph with temporal updates.

(b) A filtration mirroring the updates.

Figure 4: A dynamic graph with three well-defined communities (a) and an
associated filtration (b) are shown with temporal updates. Class i. edges are
shown in solid black. The blue dotted edges incident to $v$ in (a) are class
ii. edges; the blue dotted edges between $u$ and the black nodes are class
iii. edges; all other blue dotted edges are class iv. edges. The wavy edges in
red belong to class v.

####  3.2.1 Internal Additions.

If an edge $(u,v)$ corresponds to an _internal addition_ , we first find the
covering rules $f_{t}(u)=P_{u}$ and $f_{t}(v)=P_{v}$ of the nodes incident on
that edge and let $G_{u}$ and $G_{v}$ be their respective RHS graphs. If
$G_{u}=G_{v}$, then we simply add an edge between $\alpha_{t}(u)$ and
$\alpha_{t}(v)$. However, if $G_{u}\neq G_{v}$, then we find their least
common ancestor and add an edge between the appropriate nodes on its right-
hand side. Note that if a nonterminal symbol is incident on the edge added,
then this will necessarily change the symbol—recall that the nonterminal
symbols are defined to be the sum of their degree with their boundary degree.
This change in the symbol must be propagated _down_ through the hierarchy by
commensurately increasing LHS’s of rules and adding boundary degrees.

####  3.2.2 Frontier & External Additions.

We handle frontier and external edge additions jointly by cases. Given an edge
$(u,v)$ of class iii. or iv., let $H_{(u,v)}\triangleleft G_{t+1}$ be the
maximally connected induced subgraph of $G_{t+1}$ containing $(u,v)$.

In the first case, suppose none of the vertices of $H_{(u,v)}$ coincide with
$G_{t}$. We begin by independently extracting a grammar $\mathcal{H}_{(u,v)}$
on $H_{(u,v)}$ with its own induced filtration. We then _merge_ this grammar
with $\mathcal{G}_{t}$ by combining the two filtrations under one larger
cover. Specifically, this takes the form of a new root rule whose LHS is $S$
and RHS consists of two disconnected nonterminal symbols—one for $G_{t}$ and
one for $H_{(u,v)}$—incorporating the rules of $\mathcal{G}_{t}$ and
$\mathcal{H}_{(u,v)}$ as descendants. To disambiguate, the LHS’s for the root
rules $\mathcal{G}_{t}$ and $\mathcal{H}_{(u,v)}$ are updated accordingly.

In the second case, there is at least one node in common between $H_{(u,v)}$
and $G_{t}$. Define the _frontier_ $F(G_{t},H_{(u,v)})$ between $G_{t}$ and
$H_{(u,v)}$ to be the collection of all such class iii. edges. Then, for each
edge $(u_{G},v_{H})\in F(G_{t},H_{(u,v)})$, we find the rules
$f_{t}(u_{G})=P_{u_{G}}$ and $P_{v_{H}}$ from $\mathcal{G}_{t}$ and
$\mathcal{H}_{(u,v)}$ that cover $u_{G}$ and $v_{H}$ respectively, and
increase their boundary degrees by $1$ to indicate that this node should
expect to receive a new edge. This increase in boundary degree necessitates a
change to the LHS symbols of the two rules, which in turn induces more changes
to their ancestor rules; these changes propagate _up_ to the roots of their
respective hierarchies. Finally, once these changes have been made for each
frontier edge, a new rule is created (cf. the prior case) with two nonterminal
symbols connected by as many edges as there are in $F(G_{t},H_{(u,v)})$,
concluding the subgrammar-merging process. This accounts for all of the class
iii. and iv. edges that participated in the connected component $H_{(u,v)}$.

####  3.2.3 Deletions.

An edge deletion $(u,v)$ must have both of its incident nodes existing in
$G_{t}$, but they need not exist in $G_{t+1}$. As a result, we handle class v.
edges by first finding the covering rules $f_{t}(u)$ and $f_{t}(v)$ and
removing the edge between the nodes corresponding to $\alpha_{t}(u)$ and
$\alpha_{t}(v)$ from their common ancestor. Note that if this edge was
incident on a nonterminal symbol, its removal will cause a cascade of changes
that must be propagated _down_ the hierarchy. Then, if $u$ is not present in
$G_{t+1}$, we also remove the node $\alpha_{t}(u)$ from the RHS of $f_{t}(u)$;
similarly with $v$ and the removal of $\alpha_{t}(v)$ from $f_{t}(v)$.

###  3.3 Measuring Deviation

Now that we know how to take a grammar $\mathcal{G}_{t}$ and temporally modify
it into $\mathcal{G}_{t+1}$, we can analyze what the specific changes were
between the two grammars. From the process delineated in Sec. 3.1, we obtain a
natural correspondence $\pi_{t}:R_{t}\to R_{t+1}$ between every rule $P_{t}\in
R_{t}$ from $\mathcal{G}_{t}$ and its updated version $\pi_{t}(P_{t})\in
R_{t+1}$ in $\mathcal{G}_{t+1}$. We can use this mapping to quantify the
difference between the two grammars in terms of the number of changes
introduced by the temporal update process. Given a rule $P_{t+1}\in R_{t+1}$,
we define the change introduced by this rule by computing the graph edit
distance (GED) [1] between the RHS’s of $P_{t+1}$ and
$\pi_{t}^{-1}(\\{P_{t+1}\\})$ (with a small penalty to any modifications that
need to be made to make the LHS’s the same)222The notation
$\pi_{t}^{-1}(\\{P_{t+1}\\})$ denotes the _preimage_ of $P_{t+1}$ under
$\pi_{t}$.. If $P_{t+1}$ is a rule introduced as part of the subgrammar-
merging process for class iii. and iv. edges, then we let
$\pi_{t}^{-1}(\\{P_{t+1}\\})$ be the empty graph by definition. By aggregating
these edit distances across the rules of $\mathcal{G}_{t+1}$, we get an
indication of how much $\mathcal{G}_{t}$ had to be perturbed to accommodate
the data seen in $G_{t+1}$. Specifically, we compute

$\Delta=-\ln\frac{1}{1+~{}~{}\displaystyle\smashoperator[]{\sum_{P_{t+1}\in
R_{t+1}}^{}}~{}~{}\text{GED}\Big{(}\pi^{\scriptscriptstyle-1}_{t}\left(\big{\\{}P_{t+1}\big{\\}}\right),P_{t+1}\Big{)}}.$
(1)

###  3.4 Generating Graphs

Finally, we can use the rules from the updated grammar $\mathcal{G}_{t+1}$ to
generate graphs. First, we post-process the rules of the unweighted grammar
$\mathcal{G}_{t+1}$ into the rules of a weighted grammar by combining all
isomorphic rules and weighting them by how frequently (up to isomorphism) each
rule occurred in $\mathcal{G}_{t+1}$. The idea now is identical to the
approach traditionally taken by weighted VRGs. We start with the root rule,
which has LHS symbol $S$, and use the structure on its RHS as our initial
graph $\hat{G}_{t+1}$. We then iteratively grow the graph by randomly
selecting a nonterminal symbol in $\hat{G}_{t+1}$ and randomly sampling a
compatible rule to apply at that symbol, with the sampling probability for the
rules determined by the frequencies of the possible candidate rules for that
nonterminal symbol. Once no nonterminal symbols remain in $\hat{G}_{t+1}$, we
stop and obtain our resulting graph.

##  4 Evaluation

We perform three types of analysis to better understand the quantitative and
qualitative characteristics of the DyVeRG model. In the first quantitative
benchmark, we task the model with distinguishing genuine temporal dynamics
from realistic imposter data created by other generative models. The second
quantitative analysis asks all of the models, including DyVeRG, to generate a
graph corresponding to a slice of time from the data; the generated graphs are
then compared to the ground truth. We conclude with a short qualitative
analysis and interpretation of the temporal transitions DyVeRG induces between
grammar rules.

###  4.1 Datasets

Table 1: Summary of the datasets used in the evaluation.

|  node count |  edge count |  # timestamps |  # interactions |  # snapshots
---|---|---|---|---|---
DNC Emails | 1 891 | 4 465 | 19 389 | 32 878 | 11
EU Emails | 986 | 16 064 | 207 880 | 327 333 | 19
DBLP | 95 391 | 164 479 | 21 | 200 792 | 21
Facebook | 61 096 | 614 797 | 736 674 | 788 135 | 29

In this evaluation, we consider four dynamic datasets, listed in Tab. 1. DNC
Emails and EU Emails are email networks where user email accounts are nodes
and an email from one user to another at a given time is represented by an
undirected edge labeled with a UNIX time. Both of these datasets are
aggregated by month; DNC Emails contains a number of self-edge loops, while EU
Emails contains none. The DBLP dataset is an undirected academic coauthorship
graph where nodes correspond to researchers and an edge is drawn between two
researchers during a particular year _iff_ they coauthor a paper during that
year. Finally, the Facebook dataset is an undirected graph tracking
friendships on a monthly basis, with two users sharing an edge if they were
friends during that month.

$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$10^{1}$$10^{3}$$10^{5}$$t$Number of
Nodes$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$10^{1}$$10^{3}$$10^{5}$$t$Number of
EdgesDNC Emails EU Emails DBLP Facebook Figure 5: Number of nodes and edges in
the datasets over time.

We take snapshots $0$ through $10$ for each dataset. Because these datasets
are dynamic, we summarize their orders and sizes in Fig. 5, noting they tend
to grow over time.

###  4.2 Baselines

We compare the DyVeRG model against 5 baselines. The Erdős-Renyi model
generates random graphs of a fixed size $n$ with probability $p$ of an edge
between any two nodes [12]; for evaluation we set $n$ and
$p=\nicefrac{{2m}}{{n(n-1)}}$ to the ground-truth values within each timestep.
The configuration model of Chung and Lu generates a random graph approximating
a given degree distribution [8, 16]; for this baseline, we use the degree
distribution from the dataset.

The Erdős-Renyi and Configuration models learn very rudimentary features from
an input graph. The following three graph models are different in that they
take a whole graph as input and use their own inductive biases to learn
features. The Stochastic Block Model (SBM) uses matrix reductions to represent
graphs with structured communities [21, 29]. Likewise, the more advanced graph
recurrent neural network (GraphRNN) [41] is able to learn a generative model
from an input collection of graphs by adapting walks over nodes as sequential
data. We also provide a static implementation of DyVeRG based on CNRG [32],
which we call VeRG, as a final point of comparison.

An important note should be made here that some of the data for GraphRNN is
missing from the figures. This is because, when training and testing the model
on the two NVIDIA GeForce RTX 2080 Ti cards available to us, with 10 GB of RAM
each, we regularly ran out of memory on the larger datasets.

###  4.3 Inference

$0$$1$$2$DyvergenceDNC Emails$0$$0.5$$1$EU
Emails$0$$0.2$$0.4$$0.6$$0.8$DyvergenceDBLP$0$$0.1$$0.2$FacebookErdos-Renyí
Chung-Lu SBM GraphRNN VeRG Ground
Truth$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$1$$3$$5$Ranking$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$1$$3$$5$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$1$$3$$5$$t$Ranking$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$1$$3$$5$$t$
Figure 6: Dyvergence scores and model rankings. The top subplots show, for
each model, the deviations over time from the mean dyvergence score. The
relative rankings of the models are then shown in the corresponding bottom
subplots. Note that lower is better, so the best-performing model is listed at
the bottom.

The goal of this task, given a temporal sequence of graphs $\langle
G_{t}\rangle_{t=0}^{10}$, is to distinguish the graph that genuinely comes
next from an assortment of impostors.

For each timestep $t\in\\{0,\dots 9\\}$, we extract a VRG from $G_{t}$ and
update it using $G_{t+1}$, yielding DyVeRG grammars
$\langle\mathcal{G}_{t}\rangle_{t=1}^{10}$. These grammars are used to compute
dyvergence scores (cf. Sec. 3.3) for the ground truth. This is performed $10$
times independently for each $(G_{t},G_{t+1})$ pair, and we let $D_{t}$ denote
the mean.

We use the average ground-truth dyvergences $\\{D_{0},\dots D_{t-1}\\}$ to
compute an estimate $\hat{D}_{t}$ for the expected dyvergence of the next
graph pair $(G_{t},G_{t+1})$—i.e., an estimate for $D_{t}$. Specifically, we
let $A_{t}=\nicefrac{{(\sum_{i=0}^{t}D_{i})}}{{(t+1)}}$ and compute

$\hat{D}_{t}=A_{t-1}+(D_{t-1}-A_{t-2}).$ (2)

Separately, each impostor model $\mathcal{M}$ is trained on $G_{t+1}$ and $10$
graphs $\langle M_{t+1,i}\rangle_{i=1}^{10}$ are sampled from its
distribution. Dyvergence scores are calculated for these graphs by extracting
a VRG from $G_{t}$ and then updating it with each of the $M_{t+1,i}$;
aggregate edits are then computed as in Eq. 1. Average dyvergences
$D_{\mathcal{M},t}$ are then found for the $(G_{t},M_{t+1,i})$. We define the
_dyvergence_ of $\mathcal{M}_{t}$ by

$\text{dyvergence}(G_{t},\mathcal{M}_{t}=|\hat{D}_{t}-D_{\mathcal{M},t}|)$ (3)

Dyvergence for the ground truth is similarly defined by
$\text{dyvergence}(G_{t},G_{t+1})=|\hat{D}_{t}-D_{t}|$. The lower this score
is, the higher our confidence would be that the scored graph comes from the
same generating distribution as the data.

We illustrate our results in Fig. 6. Here, we determine success by assigning
the ground truth a lower dyvergence score than the impostor graphs. We
outperform the competing baselines on the EU Emails and Facebook datasets.

Our model is also largely successful on the DNC email graph, ranking the
ground truth as least-dyvergent the majority of the time, shown clearly by the
ranking subfigures in Fig. 6. The model performs poorly only on the DBLP
graph. We conjecture that the amount of dyvergance in DBLP from one time step
to another fluctuates more drastically due to the longer timescale for data
aggregation in this dataset; whereas the other three datasets were grouped
into monthly snapshots, DBLP snapshots are taken annually. This might lead to
inaccuracies in $\hat{D}_{t}$, negatively impacting the dyvergence scores for
the real graph while boosting performance on imposters that are not as
temporally turbulent.

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$0$$0.5$$1$Portrait DivergenceDNC
Emails$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$0$$0.5$$1$EU
Emails$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$0$$0.5$$1$$t$Portrait
DivergenceDBLP$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$0$$0.5$$1$$t$FacebookErdos-Renyí
Chung-Lu SBM GraphRNN VeRG DyVeRG Figure 7: Portrait Divergence comparing a
generated graph from each model and timestep against a corresponding ground
truth graph. Lower is better.

###  4.4 Generation

A natural way to interrogate a generative graph model—like a graph grammar—is
to generate graphs with it. Generative graph models are widely used in modern
AI systems for contrastive and adversarial learning. Here, we use these models
in the more traditional way they might be used for a task like hypothesis-
testing; we fit the models, generate a graph at a particular time, and then
compare the generated graph with the ground truth. For each baseline model, we
train on the ground truth at time $t$ and then generate at this same time. If
the two graphs are similar according to some empirical measure of graph
similarity, then we would say that the model performed well. For DyVeRG, we
train on time $t-1$, update with time $t$, and then generate at time $t$.

Comparing two (or more) graphs is a nontrivial task since the distributions
from which graphs can be sampled can behave erratically and are often very
high-dimensional. The most natural way to determine similarity between two
graphs is by an isomorphism test; however, in addition to being
computationally intractable, this provides a far-too-narrow view of graph
similarity. We instead take two alternative views to graph similarity. Graph
portrait divergence [3] provides a holistic view of a graph based on a matrix
of random-walk counts sorted by length; these results will be averaged across
10 independent trials. Maximum mean discrepancy (MMD) [14] is a kernel-based
sampling test—which will thus not require any averaging—with desirable
stability and computational efficiency characteristics. For both of these,
lower is better.

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$0$$1$$2$Spectrum MMDDNC
Emails$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$0$$1$$2$EU
Emails$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$0$$1$$2$$t$Spectrum
MMDDBLP$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$0$$1$$2$$t$FacebookErdos-Renyí Chung-Lu
SBM GraphRNN VeRG DyVeRG Figure 8: The MMD of the eigenvalues (Spectrum) of a
generated graph from each model and timestep compared a corresponding ground
truth graph. Lower is better.

We begin with the Portrait Divergence results, shown in Fig. 7. In general, we
can see that the DyVeRG-generated graphs tend to have lower portrait
divergence compared to the other models, thus outperforming them.

Next, we analyse the MMD of the eigenvalue spectra of the graphs’ Laplacian
matrices. MMD values are bounded between 0 and 2, with a value of 0 indicating
belief that the spectrum of the ground truth and the sample spectra of the
generated graphs were certainly sampled from the same underlying distribution.
These results are shown in Fig. 8. Here, we find that DyVeRG performs no worse
than VeRG, its static counterpart, on three of the datasets. However, on the
DBLP dataset, DyVeRG performs worse than almost all of the other models,
despite is static analogue VeRG outperforming every model.

There are, of course, many additional metrics by which to compare these
models, but the main power of DyVeRG comes from its ability to express graph
dynamics in a human-interpretable way.

###  4.5 Interpretability

To illustrate how the DyVeRG model can help a practitioner understand a
complex temporal dataset, we illustrate some specific examples of frequent
_rule transitions_ —analogous to subgraph-to-subgraph transitions—learned by
the model.

Figure 9: A sample of the top rule transitions from the EU Emails dataset.
$\times 61$ denotes that the first rule transition was repeated 61 times.
These rule transitions describe various changes in graph structure over time.

We focus our analysis here on the first $10$ timesteps of the EU Emails
dataset. For each $t\in\\{0,\dots 9\\}$, we extract a grammar on $G_{t}$ and
then update it according to the procedure described in Section 3, giving us a
list of DyVeRG grammars $\langle\mathcal{G}_{t}\rangle_{t=1}^{10}$. Then,
given two rules $\dot{P}$ and $\ddot{P}$, each of which could be a rule from
any of the grammars $\mathcal{G}_{t}$ for $t\in\\{1,\dots 10\\}$, we say that
a transition of _type_ $\dot{P}\Rightarrow\ddot{P}$ has occurred _iff_ there
is a grammar $\mathcal{G}_{i}$ such that, during the temporal updating
procedure, a rule isomorphic to $\dot{P}$ was modified into a rule isomorphic
to $\ddot{P}$. We then go through our list of grammars and tally up the
frequency with which every possible rule transition occurs with the idea in
mind that the most frequent rule transitions might provide some salient
insight into the dynamics of the dataset. In Fig. 9, we have a sample of four
of the most frequent rule transitions learned from EU Emails, which we will
refer to as $\dot{P}_{1}\Rightarrow\ddot{P}_{1}$, $\dots$
$\dot{P}_{4}\Rightarrow\ddot{P}_{4}$ respectively.

Both $\dot{P}_{1}\Rightarrow\ddot{P}_{1}$ and
$\dot{P}_{2}\Rightarrow\ddot{P}_{2}$ illustrate that a new structure emerged
at time $t+1$ among nodes that did not already exist in $G_{t}$. In the first
case, we have the introduction of a new user participating in a email exchange
with two other people, and this occurs $61$ times throughout the whole
dataset. In the second, we can see a pair of new users emailing each other,
one of whom has sent two emails elsewhere in the network and the other of whom
has sent out one additional email, a structure that occurs $5$ times in the
data. In either case, because there was no rule at time $t$ that
$\ddot{P}_{1}$ and $\ddot{P}_{2}$ are updated versions of, we can be certain
they were additions that participated in a larger connected component that was
introduced wholly at time $t+1$. This reveals a temporal property of the EU
Email network: it is much more frequent for users to send out emails following
periods of inactivity when other previously-inactive users are also sending
out emails to new people, than it would be for them to suddenly begin sending
emails to active users.

The next transition, $\dot{P}_{3}\Rightarrow\ddot{P}_{3}$, shows us that three
times throughout the data, a heterophilous dyad—a communicating pair of users
where one is involved in many emails and the other is not—will see a reduction
in the number of emails in which the less popular user participates. By
contrast, the final transition $\dot{P}_{4}\Rightarrow\ddot{P}_{4}$
exemplifies a more extreme version of the _opposite_ phenomenon: twice in the
data, when a heterophilous wedge consisting of two unpopular users is bridged
by a high-volume email-sender, the bridging user will experience a reduction
in email output while the unpopular users become more popular.

The insights obtained by this analysis are over-specific due largely to the
precise nature of rule isomorphism. However, if a more relaxed view of rule
isomorphism is adopted, and the definition of rule transition is broadened,
then our model could describe even more general temporal trends. Even so, our
model has shown its ability to provide significant insight into network
dynamics.

##  5 Conclusion

We introduced the Dynamic Vertex Replacement Grammar (DyVeRG) formalism, which
is a graph grammar model that learns rule transitions from a dynamic graph.
Unlike typical graph grammars, these rule transitions encode the dynamics of a
graph’s evolution over time. Further, unlike subgraph-to-subgraph transition
models, which learn transitions between small configurations of nodes, DyVeRG
encodes rule transitions across multiple levels of granularity.

We show through our quantitative analysis across two tasks and three metrics
that the fidelity of the DyVeRG model is comparable or better than many
existing graph models, even a highly-parameterized, uninterpretable graph
neural network. Finally, we presented a short case study demonstrating how the
induced rule transitions can provide insight into a temporal dataset.

## References

  * [1] Zeina Abu-Aisheh., Romain Raveaux., Jean-Yves Ramel., and Patrick Martineau.  An exact graph edit distance algorithm for solving pattern recognition problems.  In Proceedings of the International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM,, pages 271–278. INSTICC, SciTePress, 2015.
  * [2] Salvador Aguinaga, David Chiang, and Tim Weninger.  Learning hyperedge replacement grammars for graph generation.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 41(3):625–638, 2019.
  * [3] James P. Bagrow and Erik M. Bollt.  An information-theoretic, all-scales approach to comparing networks.  Applied Network Science, 4(1):45, Jul 2019.
  * [4] Mohammadhossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Raimondas Kiveris, Silvio Lattanzi, and Vahab Mirrokni.  Affinity clustering: Hierarchical clustering at scale.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
  * [5] Austin R. Benson, Rediet Abebe, Michael T. Schaub, Ali Jadbabaie, and Jon Kleinberg.  Simplicial closure and higher-order link prediction.  Proceedings of the National Academy of Sciences, 115(48):E11221–E11230, 2018.
  * [6] Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre.  Fast unfolding of communities in large networks.  Journal of Statistical Mechanics: Theory and Experiment, 2008(10):P10008, oct 2008.
  * [7] Peter Bubenik.  Statistical topological data analysis using persistence landscapes.  J. Mach. Learn. Res., 16(1):77–102, jan 2015.
  * [8] Fan Chung and Linyuan Lu.  Complex Graphs and Networks (Cbms Regional Conference Series in Mathematics).  American Mathematical Society, USA, 2006.
  * [9] Stéphan Clémençon, Hector De Arazoza, Fabrice Rossi, and Viet Chi Tran.  Hierarchical clustering for graph visualization.  2012\.
  * [10] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer.  Stability of persistence diagrams.  In Proceedings of the Twenty-First Annual Symposium on Computational Geometry, SCG ’05, page 263–271, New York, NY, USA, 2005. Association for Computing Machinery.
  * [11] Sergey N. Dorogovtsev, Alexander V. Goltsev, and José F.F. Mendes.  k-core organization of complex networks.  Phys Rev Lett, 96(4):040601, February 2006.
  * [12] Paul Erdös and Alfréd Rényi.  On random graphs i.  Publicationes Mathematicae Debrecen, 6:290, 1959.
  * [13] Yitian Gao, Hongwei Fang, and Ke Ni.  A hierarchical clustering method of hydrogen bond networks in liquid water undergoing shear flow.  Scientific Reports, 11(1):9542, May 2021.
  * [14] Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola.  A kernel two-sample test.  Journal of Machine Learning Research, 13(25):723–773, 2012.
  * [15] Minghao Guo, Veronika Thost, Beichen Li, Payel Das, Jie Chen, and Wojciech Matusik.  Data-efficient graph grammar learning for molecular generation.  In International Conference on Learning Representations, 2022.
  * [16] Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart.  Exploring network structure, dynamics, and function using networkx.  In Gaël Varoquaux, Travis Vaught, and Jarrod Millman, editors, Proceedings of the 7th Python in Science Conference, pages 11 – 15, Pasadena, CA USA, 2008.
  * [17] Lars Hagen and Andrew B. Kahng.  New spectral methods for ratio cut partitioning and clustering.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 11(9):1074–1085, 1992.
  * [18] Steve Hanneke, Wenjie Fu, and Eric P. Xing.  Discrete temporal models of social networks.  Electronic Journal of Statistics, 4(none):585 – 605, 2010.
  * [19] Justus Hibshman, Satyaki Sikdar, and Tim Weninger.  Towards interpretable graph modeling with vertex replacement grammars.  In 2019 IEEE International Conference on Big Data (Big Data), pages 770–779, 2019.
  * [20] Justus Isaiah Hibshman, Daniel Gonzalez, Satyaki Sikdar, and Tim Weninger.  Joint subgraph-to-subgraph transitions: Generalizing triadic closure for powerful and interpretable graph modeling.  In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, WSDM ’21, page 815–823, New York, NY, USA, 2021. Association for Computing Machinery.
  * [21] Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt.  Stochastic blockmodels: First steps.  Social Networks, 5(2):109–137, 1983.
  * [22] Petter Holme and Jari Saramäki.  Temporal networks.  Physics Reports, 519(3):97–125, 2012.
  * [23] Hiroshi Kajino.  Molecular hypergraph grammar with its application to molecular optimization.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3183–3191. PMLR, 09–15 Jun 2019.
  * [24] Daniel Le Métayer.  Software architecture styles as graph grammars.  In Proceedings of the 4th ACM SIGSOFT Symposium on Foundations of Software Engineering, SIGSOFT ’96, page 15–23, New York, NY, USA, 1996. Association for Computing Machinery.
  * [25] Erhan Leblebici, Anthony Anjorin, and Andy Schürr.  Inter-model consistency checking using triple graph grammars and linear optimization techniques.  In Marieke Huisman and Julia Rubin, editors, Fundamental Approaches to Software Engineering, pages 191–207, Berlin, Heidelberg, 2017\. Springer Berlin Heidelberg.
  * [26] Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Will Hamilton, David K Duvenaud, Raquel Urtasun, and Richard Zemel.  Efficient graph generation with graph recurrent attention networks.  Advances in neural information processing systems, 32, 2019.
  * [27] Catherine Matias and Vincent Miele.  Statistical clustering of temporal networks through a dynamic stochastic block model.  Journal of the Royal Statistical Society. Series B (Statistical Methodology), 79(4):1119–1141, 2017.
  * [28] Leslie O’Bray, Bastian Rieck, and Karsten Borgwardt.  Filtration curves for graph representation.  In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, KDD ’21, page 1267–1275, New York, NY, USA, 2021\. Association for Computing Machinery.
  * [29] Tiago P. Peixoto.  The graph-tool python library.  figshare, 2014.
  * [30] Corey Pennycuff, Satyaki Sikdar, Catalina Vajiac, David Chiang, and Tim Weninger.  Synchronous hyperedge replacement graph grammars.  In Leen Lambers and Jens Weber, editors, Graph Transformation, pages 20–36, Cham, 2018. Springer International Publishing.
  * [31] Kijung Shin, Tina Eliassi-Rad, and Christos Faloutsos.  Corescope: Graph mining using k-core analysis — patterns, anomalies and algorithms.  In 2016 IEEE 16th International Conference on Data Mining (ICDM), pages 469–478, 2016.
  * [32] Satyaki Sikdar, Justus Hibshman, and Tim Weninger.  Modeling graphs with vertex replacement grammars.  In 2019 IEEE International Conference on Data Mining (ICDM), pages 558–567, 2019.
  * [33] Satyaki Sikdar, Neil Shah, and Tim Weninger.  Attributed graph modeling with vertex replacement grammars.  In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, WSDM ’22, page 928–936, New York, NY, USA, 2022\. Association for Computing Machinery.
  * [34] Joshua Southern, Jeremy Wayland, Michael Bronstein, and Bastian Rieck.  Curvature filtrations for graph generative model evaluation, 2023.
  * [35] V. A. Traag, L. Waltman, and N. J. van Eck.  From louvain to leiden: guaranteeing well-connected communities.  Scientific Reports, 9(1):5233, Mar 2019.
  * [36] Ludo Waltman and Nees Jan van Eck.  A smart local moving algorithm for large-scale modularity-based community detection.  The European Physical Journal B, 86(11):471, Nov 2013.
  * [37] Zhenyi Wang, Yanjie Zhong, Zhaofeng Ye, Lang Zeng, Yang Chen, Minglei Shi, Zhiyuan Yuan, Qiming Zhou, Minping Qian, and Michael Q Zhang.  MarkovHC: Markov hierarchical clustering for the topological structure of high-dimensional single-cell omics data with transition pathway and critical point detection.  Nucleic Acids Research, 50(1):46–56, 12 2021.
  * [38] Tim Weninger Xinyi Wang, Salvador Aguinaga and David Chiang.  Growing better graphs with latent-variable probabilistic graph grammars.  In Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG), 2018.
  * [39] Chencheng Xu, Qiao Liu, Minlie Huang, and Tao Jiang.  Reinforced molecular optimization with neighborhood-controlled grammars.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 8366–8377. Curran Associates, Inc., 2020.
  * [40] Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec.  Hierarchical graph representation learning with differentiable pooling.  In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, page 4805–4815, Red Hook, NY, USA, 2018. Curran Associates Inc.
  * [41] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec.  Graphrnn: Generating realistic graphs with deep auto-regressive models.  In International conference on machine learning, pages 5708–5717. PMLR, 2018.
  * [42] Shihua. Zhang, Xue-Mei Ning, and Xiang-Sun Zhang.  Graph kernels, hierarchical clustering, and network community structure: experiments and comparative analysis.  The European Physical Journal B, 57(1):67–74, May 2007.
  * [43] Allan Zhao, Jie Xu, Mina Konaković-Luković, Josephine Hughes, Andrew Spielberg, Daniela Rus, and Wojciech Matusik.  Robogrammar: Graph grammar for terrain-optimized robot design.  ACM Trans. Graph., 39(6), nov 2020.


# Gesture2Path: Imitation Learning for
Gesture-aware Navigation

Catie Cuan1,2, Edward Lee3, Emre Fisher2, Anthony Francis3,
Leila Takayama3, Tingnan Zhang3, Alexander Toshev4,†, and Sören Pirk5,†
1Department of Mechanical Engineering, Stanford University, Stanford, 94305,
United States2Everyday Robots, 100 Mayfield Ave, Palo Alto, CA 94043,
USA3Robotics at Google, 1600 Amphitheatre Parkway, Mountain View, CA 94304,
USA4Apple ML Research, Apple Park 1, Cupertino, CA 95014, USA5Adobe Research,
345 Park Avenue, San Jose, CA 95110-2704, USA$\dagger$ Work done while at
Robotics at Google.

###### Abstract

As robots increasingly enter human-centered environments, they must not only
be able to navigate safely around humans, but also adhere to complex social
norms. Humans often rely on non-verbal communication through gestures and
facial expressions when navigating around other people, especially in densely
occupied spaces. Consequently, robots also need to be able to interpret
gestures as part of solving social navigation tasks. To this end, we present
Gesture2Path, a novel social navigation approach that combines image-based
imitation learning with model-predictive control. Gestures are interpreted
based on a neural network that operates on streams of images, while we use a
state-of-the-art model predictive control algorithm to solve point-to-point
navigation tasks. We deploy our method on real robots and showcase the
effectiveness of our approach for the four gestures-navigation scenarios:
left/right, follow me, and make a circle. Our experiments indicate that our
method is able to successfully interpret complex human gestures and to use
them as a signal to generate socially compliant trajectories for navigation
tasks. We validated our method based on in-situ ratings of participants
interacting with the robots.

##  I INTRODUCTION

Situated agents should not only navigate safely around people, but should also
abide by social norms and respond to the full gamut of human behavior –
including nonverbal communication such as body language, gestures, and facial
expressions. A robot solving a navigation task must be able to interpret human
behavior and to carefully adjust its actions to be socially compliant. We
refer to this form of navigation task as Nonverbal Social Navigation. For
defining and generating social behavior, robotics research has recently
expanded efforts toward understanding the importance of respecting personal
space [1] and social dynamics [37, 21], socially-acceptable behavior for
approaching humans [18], navigation among groups of people [22], the
validation of socially acceptable policies [31], and curating large datasets
[20]. The breadth of these research directions is a testament of the
complexity of generating socially compliant agent behavior.

Figure 1: Gesture2Path is a novel social navigation policy that combines
image-based imitation learning with model-predictive control to enable
gesture-aware navigation. In this example we show our right gesture policy: A
robot at its start location begins navigating toward its goal (a). On its way,
it encounters a person that indicates to the robot with a right gesture to
pass on their right (b). The robot interprets this gesture and drives around
the person in the intended manner (c) to then continue its path towards its
goal (d). The robot in use is from Everyday Robots.  Figure 2:  Overview of
Gesture2Path: A sequential neural network trained via imitation learning acts
as a high-level planner to predict waypoint deltas from image sequences. The
predicted waypoint deltas are used to compute a world space waypoint that
serves as intermediate target position. MPC uses these intermediate target
positions to compute linear and angular velocities to drive the robot.

To solve navigation tasks, many existing approaches rely on point cloud data
obtained from LiDAR scanners that provide real-time information about the
environment, including dynamic objects such as humans. The captured point
clouds are projected to 2-D occupancy maps. With these maps existing policy
algorithms – such as model predictive control (MPC) – can efficiently solve
complex navigation tasks with remarkable success. However, while point cloud
data is a powerful sensor modality for generating navigation trajectories in
the environment, it rarely provides the accuracy needed to interpret intricate
human behavior. Conversely, while RGB sensors do not provide the depth
information needed to solve navigation tasks, they produce high-resolution
images that allow the capture of nuanced gestures and facial expressions.

In this paper, we propose a novel gesture-aware navigation policy based on
imitation learning and MPC. We train a sequential neural network that enables
us to generate waypoints of navigation trajectories from a sequence of
consecutive images. Our goal is to train this network so that it predicts
waypoints that are socially compliant and adherent to the gestures of humans
interacting with the robot. Once the network is trained, the predicted
waypoints are sent to an MPC algorithm to control the robot. The sequential
neural network serves as a high-level planner, while the MPC algorithm
provides low-level control. This setup provides the benefits of both
approaches: the sequential neural network allows us to obtain nuanced
information of human gestures from sequences of images, while the MPC
algorithm allows us to safely navigate the robot based on laser-scanned point
clouds.

To explore the effectiveness of our gesture-aware social navigation policy, we
define the four gesture scenarios: Left/Right, Follow Me, and Make a Circle.
For each scenario we define the gesture (e.g. pointing with the hand to the
left) and the robot behavior (e.g. drive left) so each gesture maps to a
specific robot behavior – an example is shown in Fig. 1. We then collected a
dataset of expert examples for each scenario by driving the robot with a human
operator. A collected trajectory is defined by a sequence of images and a
sequence of robot waypoints. We then train the sequential neural network on
subsequences of images to predict subsequences of future waypoints. The MPC
algorithm then computes the linear and angular velocities to drive from
robots’ current position to the predicted position of the sequential model.

We validate our gesture-aware social navigation policy based on in-situ
experience ratings of humans interacting with the robots. To obtain these
ratings we follow a protocol for social navigation policies [31]. Each of our
scenarios is defined by a gesture as well as the start and end positions of
the trajectory that the robot is supposed to drive along, mirroring the
training setup. Additionally, we define a questionnaire based on a five-level
Likert scale for each scenario. Once a scenario is completed a participant is
asked to provide their ratings for a specific scenario. We use this setup to
compare our Gesture2Path policy with a MPC policy as the baseline.

In summary, our contributions are: (1) we introduce Gesture2Path, a novel
gesture-aware social navigation policy that combines a sequential neural
network with MPC; (2) we show that our policy is able to interpret gestures to
generate socially-compliant behavior in gesture-navigation scenarios; (3) we
define a canonical set of social navigation scenarios with gestures that can
be replicated and tested; (4) we employ a novel validation protocol for social
navigation scenarios to compare our gesture-aware policy with a standard MPC
policy.

##  II PRIOR WORK

Due to its importance to robotics, research on social navigation has recently
garnered considerable attention, spanning a breadth of methods which we cannot
comprehensively discuss. For a general overview, interested readers are
referred to recent survey papers by Gao and Huang [14], Charalampous et al.
[6], Mavrogiannis et al. [27], Kruse et al. [25], Rios-Martinez [32], and
Mirsky et al. [28]. The following discussion focuses on approaches to social
navigation and human robot interaction with methods closely related to our
work.

A variety of researchers have explored gestures for robotic control. For
teleoperation, researchers used hand tracking with a Microsoft Kinect device
[39] [10], a Leap motion [38], or a camera to direct a robot’s end effector.
For robot navigation, [33], [34] extracted gestures from a Kinect sensor to
generate navigation commands for a teleoperated robot in a non-social setting.
[19] used hidden Markov models to detect six gestures with a Kinect sensor and
mapped them to hand-crafted robot navigation behaviors. [5] used a wearable
gesture detector to control a mobile robot. Finally, [3], [2] and [26] used
imitation learning to replicate human gestures on a robot platform.

Researchers have also examined gestures for social communication. [17] modeled
musical improvisation as a series of gestures so a robot marimba player could
improvise with a human. In [29], researchers designed a gesture framework for
humans to collaborate with a co-worker robot on an assembly task; [11]
approached a different collaborative task between humans and robots using a
gesture framework. Other gesture-based human-robot communication systems have
been developed for settings where verbal communication may be challenging,
such as emergency settings [8] or underwater [7].

##  III METHOD

Our main goal is to develop a gesture-aware navigation policy which can guide
robots around humans in a socially compliant manner while responding to
provided gestures. We define our Gesture2Path policy by combining a sequential
neural network as a high-level planner with MPC for low level control (Fig.
2). The high-level planner identifies humans and the gestures they perform
from images, while the low-level controller safely navigates the robot from
one waypoint to another. The advantage of this setup is that the high-level
planner and the low-level controller complement each other. MPC performs well
for navigating from one waypoint to another, even around dynamic obstacles,
based on point cloud data obtained from the environment. However, MPC fails to
detect humans and their gestures as it does not use RGB data. Conversely, the
high-level planning neural network is able to detect humans and their gestures
from sequences of images, but fails to reliably predict waypoints for the
navigation task.

###  III-A Gesture-aware Social Navigation

To control a robot in response to a human and their gestures, we employ a
sequential neural network [35] that, given a history of observations, outputs
a sequence of future positions. We learn this model from demonstrations of
successful navigation trajectories of human-robot interactions and show that
the network is able to learn to interpret human gestures.

In more detail, we denote by $s=(I,O,p)$ the robot state consisting of an RGB
image $I$ from a headmounted camera, an occupancy grid $O$ from a LiDAR
sensor, and a robot position $p$ in the world coordinate frame. A
demonstration trajectory of length $n$ can be described as a sequence of
states: $(s_{1},\dots,s_{n})$. An occupancy map is defined as the 2D
projection of a point cloud obtained from a LiDAR scanner.

Given a history of states, we aim to compute controls that would result in the
future robot positions as encoded by the demonstrations. In particular, at
step $n$ we utilize a history of $k$ states from the demonstration to predict
$l$ future positions:

$(p_{n+1},...,p_{n+l})=\textrm{Gesture2Path}(s_{n},\dots,s_{n-k},g),$ (1)

where $g$ is the goal position of the robot.

In theory, we could use a neural network to directly learn robot control
commands. Several approaches do learn direct mappings from pixels to motor
controls [23, 24, 30]. However, learning an end-to-end robot control policy
remains challenging, as methods tend to require large training datasets and
easily overfit to the underlying robot dynamics.

Therefore, we employ MPC as a low level controller that, given an intermediate
goal position, drives the robot to this position while avoiding collisions.
The MPC algorithm takes care of converting target positions to low level
torque controls.

To navigate a robot a MPC controller requires the intermediate next position
encoded in the robot frame. Thus, we need to convert the demonstrated robot
positions from world frame to a sequence of egocentric positions, each in the
frame of the previous position. This can be done by calculating the deltas
between subsequent positions: $\delta_{i}=p_{i}-p_{i-1}$ for $i=1,\dots,l$,
which leads to the final model formulation:

$(\delta_{n+1},\dots,\delta_{n+l})=\textrm{Gesture2Path}(s_{n},\dots,s_{n-k},g).$
(2)

####  III-A1 Sequential Model Architecture

We train the sequential model by simultaneously embedding subsequences of RGB
images $I$, the occupancy maps $O$, and the target deltas $\tau=g-p_{n}$ into
a joined latent space. Specifically, our neural network architecture uses 3D
convolutional layers to obtain two 64-dimensional embeddings from RGB images
and occupancy maps of the input subsequence with a resolution of 256x256
pixels. To combine the target deltas ($\tau$) with the image embeddings we
also project them into a 64-dimensional latent space. We then add the
embeddings and pass them to three dense layers to obtain a sequence of $l$
position deltas ($\delta$). For the last dense layer we use a linear
activation for regression. Fig. 3 shows this network architecture. Compared to
other approaches for action recognition (e.g. [15]), the goal for defining a
lightweight multi-modal architecture for detecting gestures is to ensure small
inference times ($<$ 30ms).

While our policy is agnostic to the choice of the sequential model, we found a
common 3D-convolutional neural network similar to [4] provided the best
performance for our experiments. We train the network via imitation learning
using expert sequences of human-robot interactions captured by manually
driving the robot with a human operator (see Section IV-B).

Fig. 4 illustrates the parameters of our learning setup. We train our
sequential neural network on subsequences of the collected expert trajectories
(full sequence). The training objective is to predict a sequence of position
deltas (with $l$ steps into the future) based on a history of $k$ previous
states. The goal is to use the predicted position deltas to compute an
intermediate target position ($p_{t}$) from the current position ($p_{n}$). To
train the model we sample all possible subsequences from our dataset of expert
trajectories.

Figure 3: We use a 3D CovNet neural network architecture that joinly embeds
sequences of RGB images $I$, occupancy maps $O$, and target deltas $\tau$ into
a fused embedding space. The network is trained so as to predict sequences of
position deltas that we use to generate an intermediate goal position for an
MPC algorithm. Figure 4: Our sequential neural network predicts a subsequence
of position deltas ($\delta$) from a history of past states $s$. We use the
predicted position deltas to compute an intermediate target position
($p_{t}$).

####  III-A2 Action Parameterization

We use MPC for low-level robot control. Specifically, we formulate the goal
following as an optimization problem and use an iterative linear quadratic
regulator (iLQR) solver, Trajax [13], that minimizes a hand-engineered cost
function, similar to [36, 16, 9]. The optimization problem was solved at each
control step and the predicted action at the first step (i.e. velocity
command) is sent to the robot. The inputs to MPC include the occupancy grid
and relative goal position; its cost function combines time-weighted goal
penalties, margin-offset collision penalties, and a weighted control penalty;
and its action space is linear and angular velocities. This MPC policy
provides smooth navigation and fast reaction times for differential drive
robots and is superior in our tests to a re-implementation of the well-
performing reinforcement learning policy in [12].

We use MPC in two ways: first we establish a baseline, where we use the
algorithm to navigate from a start to a goal position without additional
visual inputs. Second, we use MPC for our gesture-aware policy by tracking
waypoints that are generated by the sequential neural network. In both cases,
the action space are linear and angular velocities.

Figure 5: Once the intermediate target position $p_{t}$ has been computed from
the predicted position deltas, we use MPC to compute an optimal trajectory
from the current position $p_{n}$ to the target position. Note that the
trajectory represented by the predicted position deltas and the computed MPC
trajectory may diverge – we do not want to over-constrain the MPC algorithm to
find an optimal trajectory.

Figure 6: We test Gesture2Path with three policies to respond to four
gestures: circle (a), follow (b), right (c), and left (d). For each scenario
we only define the gesture (e.g. pointing with the hand to the left), the
corresponding expected robot behavior (e.g. drive left), and the start and end
positions of the robot trajectory. The robot is tasked to navigate from its
start position to a goal area (blue circle). A person is standing in the
center of the room and interacts with the robot by performing different
gestures to initiate the robots’ response.

For gesture-aware navigation, we use the sequential neural network described
in Section III-A1 to predict position deltas from a sequence of previous
states. From the position deltas ($\delta$) we compute an intermediate target
position $p_{t}=p_{n}+\sum_{i=n+1}^{i=n+l}\delta_{i}$ for MPC based on the
current position $p_{n}$. The MPC algorithm then computes an optimal path from
the current position $p_{n}$ to the intermediate target position $p_{t}$.

At every time step we collect the robot state $s_{n}$. To generate gesture-
aware trajectories we use the neural network to make predictions every $k$
time steps (Fig. 2, Planning Loop), while the MPC algorithm runs at a
frequency of 10 Hz (Fig. 2, Control Loop). With $k=10$, this means that the
neural network is used to predict a new intermediate target position every 10
time steps, while the MPC algorithm continuously generates control commands to
drive toward the intermediate target position. Note that the number of
previous states (defined by $k$) used to make predictions with the neural
network need not be the same as the number of predicted position deltas
(defined by $l$). The neural network may be triggered to predict a new
intermediate target position before the robot reaches the previously computed
one. This ensures that the gesture-aware policy is susceptible to chances in
the observed gestures.

Moreover, as illustrated in Fig. 6, the trajectory represented by the
predicted position deltas of the sequential neural network and the MPC-
computed trajectory may diverge. While we want the robot to closely follow the
predicted position deltas to implement gesture-aware behavior, we do not want
to over-constrain MPC to find an optimal trajectory from the current position
to the intermediate target position. The planning loop based on the sequential
neural network provides general direction while considering observed gestures,
and the control loop based on MPC ensures safe navigation.

##  IV EXPERIMENT SETUP

The robots we use are 7 DOF mobile manipulators with a single arm and a
rectangular base. Each robot is equipped with a head-mounted camera and a
LiDAR sensor. Robots also have access to an existing static map of their
environment to assist with localization and point-to-point navigation.

###  IV-A Gesture Scenarios

To test the capabilities of Gesture2Path, we use the protocol proposed in [31]
to define the four gesture scenarios (illustrated in Fig. 6): Circle, Follow,
and Left/Right

  * •

Circle: In the make a circle scenario, the demonstrator would stand in the
center of the room and raise their right hand straight up to the ceiling. The
robot operator then drives the robot to make a counterclockwise circle before
passing the human on their left (Fig. 6 a).

  * •

Follow: In the follow me scenario, the demonstrator would lift both hands out
to the side while keeping their feet together, making a “T” shape. After
holding this shape for 2 seconds, they would turn over their left shoulder and
walk along a wide arc prior to passing through the end position region. Once
the gesture has been observed the robot operator would then drive the robot so
as to follow the demonstrator (Fig. 6 b).

  * •

Left/Right: In the left/right scenario, the demonstrator would stand in the
center of the room and put their arm out to the left or right while leaning in
that direction. The robot operator would then drive the robot to pass along
the side of the human’s outstretched arm (Fig. 6 c, d).

We selected these gestures based on the following criteria for the human and
the robot: (1) the robot solves a navigation tast beginning at one side of the
room and ending at the other; (2) the robot would move continuously from
beginning to end without pausing or stopping; (3) the gesture instructions
would be simple and easy to teach the experiment participants; (4) the
gestures would correspond to clear changes in robot behavior; (5) the gestures
require the robot to react to a single participant. While the gestures used
for the Circle and Follow scenarios are distinct, the Left and Right gestures
represent more subtle variations for the sequential model to disentangle.

###  IV-B Data Collection and Training

To train our Gesture2Path policy we collected a dataset of 277 trajectories
(40 for follow, 30 for circle, 207 left and right). Each trajectory represents
a 20-40 second sequence that includes a human-robot interaction. The human
performs one of the four defined gestures, while the robot solves a point-to-
point navigation task from a start to a goal position. All training data was
collected in the real world in a large, open atrium space over several
different days and times (Fig. 7).

To collect our dataset we used the following procedure: an expert robot
operator would connect to the real robot using a Logitech F710 gamepad. The
robot operator would stand behind the robot and follow it while driving it
forward. The gesture demonstrator would begin by standing in the middle of the
room. Once the teleoperated robot started to move, the gesture demonstrator
would perform the gesture for 2-3 seconds. Depending on the gesture scenario,
the demonstrator would either stay in place or move appropriately.

We split the collected trajectories into 90% training and 10% validation data.
We then trained our sequential neural network on subsequences ($k=10$, $l=10$,
for most of our experiments) of RGB images and occupancy maps. We used the
Adam optimizer with a standard $l2$ loss and selected checkpoints of the
network for our policies based on the lowest $l2$ error measured on the
validation dataset. The training of our network usually converges after 120
epochs, which usually takes 6 hours of training on a single V100 GPU.

Figure 7: For data collection the robot is controlled by a joystick handled by
an experienced teleoperator. The human demonstrator stands in the center of
the room and performs the gesture as well as the next sequence of human
motions (if in the follow condition). The teleoperator moves the robot from
the beginning position to the ending position with the correct response.

###  IV-C Experiment Design

To validate the effectiveness of our gesture-aware policies we conducted a
user-study to obtain in-situ experience ratings. In the following, we discuss
the setup of our experiment for our Gesture2Path polices as well as for the
MPC baseline.

####  IV-C1 User Study Design

We designed a within-subjects experiment where participants performed the four
gestures while the robot was running either Gesture2Path or a baseline of the
unmodified MPC policy. Note this baseline MPC policy is itself a highly
performant navigation policy, exceeding in our internal tests a
reimplementation of [12]. The study occurred in the same location where the
training data was collected.

Participants arrived at the location and filled out an introductory survey
asking about their dominant hand and number of months they had been working
near these robots. The participants then performed each of the four gestures a
total of 70 different times in the center of the room. Each the trials
consisted of the robot crossing from one side of the room to the other; the
human participants would perform the gesture in the center of the room (and
during the follow scenario, walking to the edge of the room). Once the trial
was completed the participant would immediately answer four questions about
the robot’s performance. The questionnaire was defined based on a 5-level
Likert scale. Each of the four questions were rated on a scale of 1-5, 1 being
Strongly Disagree and 5 being Strongly Agree. Participants had the option to
answer 0 if the question did not apply. The questions were:

  1. 1.

The robot maintained a safe distance at all times. (Safe)

  2. 2.

It was clear what the robot wanted to do. (Clarity)

  3. 3.

The robot responded correctly to my gesture. (Correct)

  4. 4.

The robot paid attention to what I was doing. (Trust)

We ran the gesture trials 10 times for each of our Gesture2path policies
(Follow, Circle, Left/Right). For the MPC baseline we ran 10 trials for the
Follow and Circle scenarios and 5 trials for the Left and Right scenarios.

We randomized policy ordering for each participant. For example, one
participant may have completed MPC Left/Right, Gesture2Path Left/Right, MPC
Follow, Policy Follow, MPC Circle, Follow Circle. After the gesture trials,
the participants filled out a closing survey asking about their age, gender,
cultural group, height, highest degree of education received, primary field of
work or study, as well as their experience with STEM, robotics in general, and
specifically the used robot. The experiment took approx. 90 minutes to
complete.

####  IV-C2 Participants

12 individuals volunteered to participate in the user study, including 2 women
and 10 men. 8 participants identified as Asian, 2 as White, 1 as
Hispanic/Latino, and 1 Middle Eastern. 3 participants were ages 18-24, 8 were
ages 25-34, and 1 declined to state. All participants listed their right hand
as the dominant hand and all participants had previously used the robot in
their work.

Figure 8: The means and standard errors for all four questions for policy and
gesture condition. The MPC conditions are in grey and Gesture2Path policy in
blue. Participants rated the question on a scale of 1 Strongly Disagree to 5
Strongly Agree. Zero was reserved for Not Applicable. The policy rated overall
more highly for each of the four questions when compared to MPC. A paired
t-test was performed on each MPC/policy bar for each gesture (i.e. comparing
circle MPC to circle policy). All of these tests were statistically
significant with a p-value $<$ .01. We can conclude that the policy performs
overall better than MPC for each of these gesture scenarios.

##  V RESULTS

All participant ratings for each gesture were grouped together by Gesture2Path
and MPC (i.e. questions 1-4 for Circle gesture, Gesture2Path, were all
grouped). These grouped responses were averaged, as shown in Fig. 9. A paired
t-test was performed for each gesture vs policy group (i.e. Questions 1-4 for
Circle Gesture2Path vs Questions 1-4 for Circle MPC) and all differences are
statistically significant with a p-value $<.01$. Therefore, we conclude that
the Gesture2Path policy overall performs better than MPC for all four gesture
scenarios.

To determine which questions had the strongest effect on Gesture2Path’s
improvement over MPC, we ran a repeated measures ANOVA on each question. The
repeated measures ANOVA comparing the effect of Gesture2Path vs MPC on
Question 3 (Correctness) showed a statistically significant difference:
F(within groups df) = 115.563, p-value = .059.

Separate repeated measures ANOVAs were performed to compare the effect of
Gesture2Path vs MPC on Question 1 (Safety), Question 2 (Clarity) and Questions
4 (Trustworthiness). Fig. 8 shows that Gesture2Path (blue bars) is higher in
all cases for Question 2 (Clarity) and Question 4 (Trustworthiness), while MPC
(grey bars) is higher for Question 1 (Safety). However, for Questions 1, 2,
and 4, the ANOVA did not show statistical significance. Therefore, the
critical improvement that elevated Gesture2Path over MPC was the policy’s
correct response to the human gesture (Question 3).

Figure 9: All averages and standard errors for each question for each gesture,
Gesture2Path is in blue, MPC is in grey. Question 3 (Correctness) shows the
largest difference between Gesture2Path and MPC. A repeated measures ANOVA on
Question 3 showed a statistically significant difference.

The Gesture2Path policies took longer than MPC in all cases, as summarized in
Table I. For Circle and Follow, this was likely due to the gesture response
trajectory requiring a longer distance for the robot to travel. For the
Left/Right Policy, the additional time was likely due to the wider distance
needed by the gesture, as well as how quickly the human operator drove the
robot during data collection. A paired t-test was performed on each
Gesture2Path and MPC pairing for each gesture and the results were
statistically significant.

In Fig. 11 we show 2-dimensional plots of the robot navigating from the start
to end positions. The positive participant ratings (4 or 5 out of 5) for
Question 3 (Correctness) are shown in solid magenta. The neutral rating (3 out
of 5) is show in dotted black. The negative ratings (1 or 2 out of 5) are
shown in dotted red. These plots demonstrate that the participants have a
clear understanding of the robot’s correct response as the higher ratings
correspond with the robot’s correct behavior.

Finally, in Fig. 12, we show examples for the four scenarios. For each policy
the image sequences show (from left to right) the robot at its start location,
the human performing the gesture, the gesture response of the robot, and the
navigation to the goal location. As shown, our Gesture2Path policy is able to
generate socially compliant trajectories in response to the performed
gestures. In contrast, as the MPC policy is not using image sequences as input
to detect gestures, it is not able to generate trajectories based on the
performed gestures – an example is shown in Fig. 10.

Figure 10: Example of the MPC policy: As no image sequences are used, the
policy is not able to generate trajectories in response to gestures. While the
performed gesture is supposed to make the robot drive a circle, it only passes
the human participant on their right side. TABLE I: p-values for gesture, MPC
vs. policy, and relevant question using a paired t-test

Gesture | Gesture2Path, MPC | Avg duration (sec) | p-value
---|---|---|---
Circle | Gesture2Path, MPC | 56, 35 | $<.001$
Follow | Gesture2Path, MPC | 45, 38 | $<.01$
Left | Gesture2Path, MPC | 45, 38 | $<.01$
Right | Gesture2Path, MPC | 46, 33 | $<.01$

__The Gesture2Path policy took significantly longer than MPC in all cases,
likely due to the increased distance requirements of the correct response path
or the speed of the demonstrations.

###  V-A Discussion and Limitations

Our MPC baseline can reliably navigate around obstacles with success
comparable to published state of the art [12]. In this work we show that using
imitation learning in tandem with MPC simultaneously allows us to maintain
this performance level while enabling gesture-aware navigation. The aim of the
study was to show that robots can respond correctly to human gestures and we
observe this in the results.

The trained Gesture2Path policies perform better than baseline MPC policy for
all gestures in the participant ratings (Fig. 9). Question 3 (Correctness) was
statistically significant, showing that Gesture2Path is able to correctly
identify and respond to human gestures. The difference in ratings between
baseline MPC and Gesture2Path was larger for the Circle and Follow policy than
for the Right and Left policy, meaning that either participants were more
certain of the robot’s correct response or that Gesture2Path’s behavior was
more distinctive than baseline MPC. Baseline MPC performed better than
Gesture2Path for all four gestures on Question 1 (Safety). The higher safety
rating follows from baseline MPC’s tendency to give humans a large amount of
space to avoid collisions.

Figure 11: 2D plots of the robot trajectories and corresponding participant
ratings (Question 3 only) for all four gestures with Gesture2Path (Ours) and
MPC. The robot starts in the red circle and is tasked to navigate to the blue
dot. The human is the black circle in the center. For the Follow plots, there
is an additional black alternating dot-dash line to indicate the rough path
that the human walks after they make the gesture in the center of the room.
Favorable participant ratings (4 or 5 on a 5 point scale) are solid lines in
magenta. Neutral participant ratings (3 on a 5 point scale) are the dashed
line in blue. Negative participant ratings (1 or 2 on a 5 point scale) are the
dotted lines in red. The MPC trajectories in the first row are all similar
regardless of the gesture. The Gesture2Path policy robot trajectories in b)
Circle and d) Follow are distinctive, correct, and consistent, with
participant ratings capturing this effect. The Gesture2Path policy does not
perform as well for Right and Left sides, also reflected in the participant
ratings.

Recall we trained three policies: 1) Circle only, 2) Follow only, and 3) Left
and Right. The third policy must generate different paths for two gestures. As
baseline MPC tends to go right when it encounters obstacles, it appears
correct to participants half the time (high clarity rating, Question 2).

We limited the number of questions to four due to practicality reasons;
running the study became quite lengthy. The study ran for a minimum of 90
minutes, so participants may have been fatigued towards the end. One
participant elected not to complete the study halfway through due to the time
commitment. To mitigate this fatigue effect in the data, conditions were
randomized for each participant.

Furthermore, not all participants perform the gesture the same way. Despite
watching the same video in order to learn the gesture, each human has
different timings, range of motion, and qualitative emphasis. Therefore, it is
promising that Gesture2Path can generalize to these performance variations.

##  VI CONCLUSION AND FUTURE WORK

We have introduced Gesture2Path, a novel social navigation policy, to enable
gesture-aware point-to-point navigation. Our approach combines a novel
sequential neural network which can predict position deltas from images with
MPC for generating linear and angular velocities to control a robot. As the
sequential neural network is trained on images of the observed gestures it can
generate positions as waypoints which implement socially-acceptable and
gesture-aware navigation behavior. On the other hand, MPC allows us to safely
navigate from the current position of the robot to an intermediate goal
position. Based on four scenarios we have shown that our Gesture2Path policy
is able to respond correctly, clearly, and legibly to a range of human
gestures, while it also outperforms the baseline MPC algorithm devoid of
visual inputs.

In future work, we plan to train our policy so as to handle multiple gestures
simultaneously. This step is important for deploying Gesture2Path in a working
robot environment, where the aim is to maximize the number of gestures with
the smallest number of concurrently running policies. We will also explore
multiple humans gesturing simultaneously. As another direction for future work
we are interested in exploring a closer connection of the introduced
sequential neural network and MPC. While keeping both algorithms separate has
intriguing advantages from an engineering point of view, it seems likely that
a closer integration of understanding gestures and low-level control would
lead to better performance. Finally, we want to use our Gesture2Path policy
for learning even more complex and diverse sets of gestures to enable even
more advanced robot navigation behavior.

Figure 12: The Gesture2Path policy employed for the four gesture-aware
navigation scenarios: circle (a), follow (b), left (c), and right (d). For all
scenarios the robots starts on the right side of the room. The robot in the
photo is from Everyday Robots.

## References

  * [1] P. Althaus, H. Ishiguro, T. Kanda, T. Miyashita, and H.I. Christensen.  Navigation for human-robot interaction tasks.  In IEEE International Conference on Robotics and Automation, 2004\. Proceedings. ICRA ’04. 2004, volume 2, pages 1894–1900 Vol.2, 2004.
  * [2] J.P. et. al Bandera-Rubio.  Vision-based gesture recognition in a robot learning by imitation framework.  2010\.
  * [3] S. Calinon and A. Billard.  Learning of gestures by imitation in a humanoid robot.  Technical report, Cambridge University Press, 2007.
  * [4] J. Carreira and A. Zisserman.  Quo vadis, action recognition? a new model and the kinetics dataset.  pages 4724–4733, 07 2017.
  * [5] D.J. Chaithanya, D. Gowda, D. Balakrishna, D. M. Gowda, and MS Divyashree.  A survey on hand gesture controlled rover.  2022\.
  * [6] K. Charalampous, I. Kostavelis, and A. Gasteratos.  Recent trends in social aware robot navigation: A survey.  Robotics and Autonomous Systems, 93:85–104, 2017.
  * [7] D. Chiarella, M. Bibuli, G. Bruzzone, M. Caccia, A. Ranieri, E. Zereik, L. Marconi, and P. Cutugno.  A novel gesture-based language for underwater human–robot interaction.  Journal of Marine Science and Engineering, 6(3):91, 2018.
  * [8] F. De Cillis, G. Oliva, F. Pascucci, R. Setola, and M. Tesei.  On field gesture-based human-robot interface for emergency responders.  In 2013 IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR), pages 1–6. IEEE, 2013.
  * [9] J. Di Carlo, P. M. Wensing, B. Katz, G. Bledt, and S. Kim.  Dynamic locomotion in the mit cheetah 3 through convex model-predictive control.  In IROS, pages 1–9, 2018.
  * [10] G. Du, P. Zhang, J. Mai, and Z. Li.  Markerless kinect-based hand tracking for robot teleoperation.  International Journal of Advanced Robotic Systems, 9(2):36, 2012\.
  * [11] T. Ende, S. Haddadin, S. Parusel, T. Wüsthoff, M. Hassenzahl, and A. Albu-Schäffer.  A human-centered approach to robot gesture based communication within collaborative working processes.  In 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 3367–3374. IEEE, 2011.
  * [12] A. Francis, A. Faust, L. Chiang, J. Hsu, J. C. Kew, M. Fiser, and E. Lee.  Long-range indoor navigation with prm-rl.  IEEE Transactions on Robotics, 36(4):1115–1134, 2020.
  * [13] R. Frostig, V. Sindhwani, S.T. Singh, and S.N. Tu.  trajax: differentiable optimal control on accelerators.  2021\.
  * [14] Y. Gao and C.-M. Huang.  Evaluation of socially-aware robot navigation.  Frontiers in Robotics and AI, 8, 2022.
  * [15] R. Girdhar, M. Singh, N. Ravi, L. van der Maaten, A. Joulin, and I. Misra.  Omnivore: A single model for many visual modalities.  2022\.
  * [16] M. Hertneck, J. Köhler, S. Trimpe, and F. Allgöwer.  Learning an approximate model predictive controller with guarantees.  IEEE Control Systems Letters, 2(3):543–548, 2018.
  * [17] G. Hoffman and G. Weinberg.  Gesture-based human-robot jazz improvisation.  In ICRA, pages 582–587. IEEE, 2010.
  * [18] C.-M. Huang, T. Iio, S. Satake, and T. Kanda.  Modeling and controlling friendliness for an interactive museum robot.  07 2014.
  * [19] L. Iocchi and M.T. Bonanni.  Person-tracking and gesture-driven interaction with a mobile robot using the kinect sensor.  2011\.
  * [20] H. Karnan, A. Nair, X. Xiao, G. Warnell, S. Pirk, A. Toshev, J. Hart, J. Biswas, and P. Stone.  Socially compliant navigation dataset (scand): A large-scale dataset of demonstrations for social navigation.  IEEE Robotics and Automation Letters, pages 1–8, 01 2022.
  * [21] Y. Kato, T. Kanda, and H. Ishiguro.  May i help you? design of human-like polite approaching behavior.  In Proceedings of the Tenth Annual ACM/IEEE International Conference on Human-Robot Interaction, HRI ’15, page 35–42, New York, NY, USA, 2015. Association for Computing Machinery.
  * [22] K. D. Katyal, K. Popek, G. D. Hager, I.-J. Wang, and C.-M. Huang.  Prediction-based uncertainty estimation for adaptive crowd navigation.  In Artificial Intelligence in HCI (AI-HCI), page 353–368, Berlin, Heidelberg, 2020. Springer-Verlag.
  * [23] H. Kim, M. Jordan, S. Sastry, and A. Ng.  Autonomous helicopter flight via reinforcement learning.  In S. Thrun, L. Saul, and B. Schölkopf, editors, Advances in Neural Information Processing Systems, volume 16. MIT Press, 2003.
  * [24] N. Kohl and P. Stone.  Policy gradient reinforcement learning for fast quadrupedal locomotion.  In IEEE International Conference on Robotics and Automation, 2004\. Proceedings. ICRA ’04. 2004, volume 3, pages 2619–2624 Vol.3, 2004.
  * [25] T. Kruse, A. K. Pandey, R. Alami, and A. Kirsch.  Human-aware robot navigation: A survey.  Robotics and Autonomous Systems, 61(12):1726–1743, 2013.
  * [26] Y. Kuniyoshi.  Learning from examples: Imitation learning and emerging cognition.  Humanoid robotics and neuroscience: science, engineering and society, pages 234–249, 2015.
  * [27] C. Mavrogiannis, F. Baldini, A. Wang, D. Zhao, P. Trautman, A. Steinfeld, and J. Oh.  Core challenges of social robot navigation: A survey, 2021.
  * [28] R. Mirsky, X. Xiao, J. Hart, and P. Stone.  Prevention and resolution of conflicts in social navigation–a survey.  arXiv preprint arXiv:2106.12113, 2021.
  * [29] P. Neto, M. Simão, N. Mendes, and M. Safeea.  Gesture-based human-robot interaction for human assistance in manufacturing.  The International Journal of Advanced Manufacturing Technology, 101(1):119–135, 2019.
  * [30] J. Peters and S. Schaal.  Reinforcement learning of motor skills with policy gradients.  Neural Networks, 21(4):682–697, 2008.  Robotics and Neuroscience.
  * [31] S. Pirk, E. Lee, X. Xiao, L. Takayama, A. Francis, and A. Toshev.  A protocol for validating social navigation policies.  ICRA, Workshop: Social Robot Navigation: Advances and Evaluation, 2022.
  * [32] J. Rios-Martinez, A. Spalanzani, and C. Laugier.  From proxemics theory to socially-aware navigation: A survey.  International Journal of Social Robotics, 7(2):137–153, Apr 2015\.
  * [33] S. Saha, R. Lahiri, A. Konar, A. Lekova, and A.K. Nagar.  A novel approach to tsk model based gesture driven robot movement.  In 2017 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE), pages 1–6. IEEE, 2017.
  * [34] S. Saha, R. Lahiri, A. Konar, and A.K. Nagar.  Gesture driven remote robot manoeuvre for unstructured environment.  In 2018 IEEE Symposium Series on Computational Intelligence (SSCI), pages 1793–1800. IEEE, 2018.
  * [35] I. Sutskever, O. Vinyals, and Q. V. Le.  Sequence to sequence learning with neural networks.  NIPS, 27, 2014.
  * [36] Y. Tassa, N. Mansard, and E. Todorov.  Control-limited differential dynamic programming.  In ICRA, pages 1168–1175, 2014.
  * [37] X.-T. Truong and T.-D. Ngo.  “to approach humans?”: A unified framework for approaching pose prediction and socially aware robot navigation.  IEEE Transactions on Cognitive and Developmental Systems, 10(3):557–572, 2018.
  * [38] W. Zhang, H. Cheng, L. Zhao, L. Hao, M. Tao, and C. Xiang.  A gesture-based teleoperation system for compliant robot motion.  Applied Sciences, 9(24):5290, 2019.
  * [39] Z. Zhang.  Microsoft kinect sensor and its effect.  IEEE multimedia, 19(2):4–10, 2012.