# An Explainer for Temporal Graph Neural Networks

1st Wenchong He  University of Florida
Gainesville, USA.
<EMAIL_ADDRESS>1st Minh N. Vu *Authors contribute equally University of Florida
Gainesville, USA.
<EMAIL_ADDRESS>3rd Zhe Jiang  University of Florida
Gainesville, USA.
<EMAIL_ADDRESS>4th My T. Thai  University of Florida
Gainesville, USA.
<EMAIL_ADDRESS>
###### Abstract

Temporal graph neural networks (TGNNs) have been widely used for modeling
time-evolving graph-related tasks due to their ability to capture both graph
topology dependency and non-linear temporal dynamic. The explanation of TGNNs
is of vital importance for a transparent and trustworthy model. However, the
complex topology structure and temporal dependency make explaining TGNN models
very challenging. In this paper, we propose a novel explainer framework for
TGNN models. Given a time series on a graph to be explained, the framework can
identify dominant explanations in the form of a probabilistic graphical model
in a time period. Case studies on the transportation domain demonstrate that
the proposed approach can discover dynamic dependency structures in a road
network for a time period.

###### Index Terms:

TGNN, graph explanations, interpretable DL

††publicationid: pubid:  978-1-6654-3540-6/22/$31.00 © 2022 IEEE

##  I Introduction

In the last several years, Graph Neural Networks (GNNs) have been increasingly
popular due to their ability to capture the complex relationship and
interactions in a system[1, 2, 3, 4, 5, 6, 7, 8, 9]. GNNs assume static graph
data and operate by aggregating information in the local neighborhood of a
node. However, many real-world systems are dynamic and evolving over time. For
example, in the transportation domain, accurate traffic forecasting requires
both temporal features (periodicity and trend) and spatial dependency modeling
(the topology of a road network). A Temporal Graph Neural Network (TGNN)
combines both a GNN and a recurrent neural network (RNN) to capture both the
spatial dependency and temporal dynamics in a system[10, 11, 12].

Although TGNNs have achieved wide success in modeling spatial networks with
temporal dynamics, it is unclear why a model makes certain predictions. Such
explanation is crucial because: (1) It improves the transparency and
consequently the trust of a TGNN model in a growing number of safety-related
applications when being deployed into the real world; (2) It allows end-users
to identify interesting dynamic dependency structures in the system. For
example, for traffic forecasting, the spatial dependency structure can change
due to the evolving characteristics of the traffic flow. In a non-congestion
period, the traffic status at upstream roads impacts the traffic status at
downstream roads through the transfer effect, and in a congestion period, the
traffic status at downstream roads impacts the traffic status at upstream
roads through the feedback effect[13, 10]. Such dependency dynamics are
crucial for a transportation domain expert to identify the influential
neighboring roads at different time periods when predicting the traffic flow
or speed for one road segment.

The problem of explaining TGNNs is challenging for several reasons. First, to
generate an accurate explanation for the temporal predictions, we need to
consider the network structural and temporal dependency simultaneously, which
increases the problem complexity compared with the static GNN explanations.
Second, the explanations identified in some time steps may be insignificant or
redundant, it is non-trivial to discover the dominant interesting dependency
structure in a time period and eliminate the redundant pattern. Third, the
computation complexity is high considering the high complexity of the
interpretable domain and quadratic potential temporal windows for
explanations.

We propose a novel explainer framework for the temporal graph neural network
interpretations based on the static graph explainer. Specifically, the main
contributions are:

$\bullet$ To reduce the interpretation complexity, we reformulate the temporal
graph neural network model such that the explanations at different temporal
snapshots can be done independently to leverage the static graph explainer.

$\bullet$ We propose a pruning approach to discover the temporal dominant
interesting explanations from the independent explanations at each time step
and eliminate the insignificant and redundant explanations. The proposed
pruning algorithms can reduce the temporal search space and improve
efficiency.

$\bullet$ The case studies of the TGNN explanations on the transportation
domain show that our proposed explainer framework can provide interpretable
explanations and discover the dynamic dependency structure of the spatial
network.

##  II Background on Graph Neural Network Explanation

This section provides some related background and preliminaries of our paper.
The following provides some highlights on GNN and TGNN, the current landscape
of explaining predictions made by GNNs, and the PGM-Explainer, which serves as
an important component of our method.

GNNs and TGNNs: With the increasing availability of modern graph data and the
popularity of graph-related tasks, many Graph-based Neural Networks have been
introduced in recent years, such as ChebNets [1], Graph Convolutional Networks
[2], GraphSage [3], Graph Attention Networks [4], among others [5, 6, 7, 8, 9,
14]. At a high level, these models exploit the non-linear transformation in
conventional neural networks to transform input features and aggregate (or
propagate) those features via a graph’s connectivity. To consider the time-
varying features of graph-related tasks, TGNNs combine GNN and RNN models
together, e.g., Temporal Graph Convolutional Neural Network (T-GCN)[10],
Spatial-Temporal Graph Social Network (STGSN)[12]. A TGNN integrates the GNN
architecture (to model the structural topology dependency) and an RNN model
(to capture the non-linear temporal dependency for time series). Recent
studies have put significant attention into the TGNN model, such as
applications in traffic forecasting, social network analysis, and human
trajectory prediction [10, 12, 15].

Explanation methods for GNNs: Similar to some previously studied deep neural
network architectures, the GNNs are known to be black-boxes, i.e. it is
unclear how they generate predictions. To address this issue, several
explanation methods, called explainers, for GNNs have been introduced recently
[16, 17, 18]. The main objective of the explainers is to identify some network
components such as nodes, edges, or sub-graphs, that explain, clarify or
contribute the most to the model’s predictions. The scope of explanations can
also vary: some methods focus on explaining the overall behaviors of the
model, while others aim to explain the model’s prediction on a specific input
instance. In this work, we focus on the latter, which is known as the “local
explanation” method. Local explanation methods can also be classified based on
their methodology: gradients or features-based, perturbation-based,
decomposition, and surrogate methods.

Explaining the GNN using PGM-Explainer: This paper aims to extend PGM-
Explainer [17], a local explanation method based on a probabilistic graphical
model, from GNN explanation to TGNN explanation. The main reason why we choose
PGM-Explainer as a base framework is that it can capture the graph
dependencies within TGNN’s variables. This makes the explainer a strong
candidate to explain models with high temporal-spatial dependencies as TGNNs.
In the next paragraphs, we provide a more formal description of how PGM-
Explainer explains the static GNNs.

We consider the forwarding of a GNN or TGNN to be explained as a function
$\Phi$. In practice, since the output of $\Phi$ can contain many predictions
(for example as in node classification), we denote $o$ the target prediction
to be explained. As such, the prediction to be explained can be written as the
function $\Phi_{o}:\mathcal{G}\rightarrow\mathcal{K}$, where $\mathcal{G}$ is
the set of input graphs and $\mathcal{K}$ is the set of prediction’s outputs
on that target.

PGM-Explainer represents the GNN’s variables via a directed acyclic
probabilistic graph, i.e. a Bayesian network [19]. Given a target prediction
to be explained $o$, PGM-Explainer solves the optimal Bayesian network
$\mathcal{B}^{*}$:

$\displaystyle\arg\max_{\mathcal{B}\in\mathcal{E}}R_{\Phi,o}(\mathcal{B}),\quad\textup{s.t.
}|\mathcal{V}(\mathcal{B})|\leq M,\boldsymbol{o}\in\mathcal{V}(\mathcal{B}),$
(1)

where $\mathcal{E}$ is the set of all Bayesian networks and $\boldsymbol{o}$
is the random variable corresponding to the target prediction $o$. The set of
random variables in Bayesian network $\mathcal{V}(\mathcal{B})$ represents the
set of explanatory features in the input graph of the model, which is
typically a subset of nodes in the input graph. The objective
$R_{\Phi,o}(\mathcal{B})$ measure the fitness of the Bayesian network
$\mathcal{B}$ with a set of perturbation data generated from the function
$\Phi_{o}$. The constraints in the optimization is to encourage compact
solutions and guarantee the target prediction is included in the explanations.
One choice of the objective $R_{\Phi,o}(\mathcal{B})$ is the BIC score, which
is given as follows:

$\displaystyle
R_{\Phi,o}(\mathcal{B})=\textup{score}_{BIC}(\mathcal{B}:\mathcal{D}_{o})=l(\hat{{\theta}}_{\mathcal{B}}:\mathcal{D}_{o})-\frac{\textup{log}n}{2}\textup{Dim}[\mathcal{B}]$

where $\mathcal{D}_{o}$ is the perturbation data generated from $\Phi_{o}$ and
$\textup{Dim}[\mathcal{B}]$ is the dimension of model $\mathcal{B}$.
${\theta}_{\mathcal{B}}$ are the parameters of $\mathcal{B}$ and function
$l({\theta}_{\mathcal{B}}:\mathcal{D}_{o})$ is the log-likelihood between the
data $\mathcal{D}_{o}$ and ${\theta}_{\mathcal{B}}$.
$\hat{{\theta}}_{\mathcal{B}}$ in the score is parameters’ value that
maximizes the log-likelihood, which is called the maximum likelihood
estimator. This choice of objective has been proven to be consistent with the
data [20].

##  III Problem Statement

This section provides a problem formulation for TGNN explanation. Based on our
previous introduction of PGM-Explainer in case of static GNNs, we describe the
formulation for TGNN and highlight some key properties and challenges of the
problem compared to the static case.

The function learnt by a TGNN can be considered as a mapping from a graph $G$
and a sequence of feature matrices to the predictions:

$\displaystyle Y=\Phi(G;[X_{t},\cdots,X_{t+T-1}]),$ (2)

where $T$ is the time window of the model. In practice, the total time
interval $[t_{1},t_{2}]$ is normally larger than the window $T$. In that case,
the interval $[t_{1},t_{2}]$ is processed into $t_{2}-t_{1}-T+1$ sequences of
length $T$ and feed into the TGNN. We consequentially have $t_{2}-t_{1}-T+1$
predictions.

Therefore, the problem of explaining the TGNN’s predictions is not only about
explaining the function $\Phi$ at some specific input sequence
$[X_{t},\cdots,X_{t+T-1}]$ but also about explaining all predictions during
the time interval $[t_{1},t_{2}]$, which includes $t_{2}-t_{1}-T+1$
predictions.

Formally, given a trained TGNN model $\Phi$ and the predictions at the
temporal interval to be explained, we define our problems as discovering the
crucial dependency structures for the model making predictions on the
interval. In the followings, we will first address how prediction of each
sequence of length $T$ is explained. Then, we describe how all explanations
can be combined to explain all predictions on the interval.

##  IV Approach

Our framework consists of two modules as shown in Figure 1. The first module
leverages PGM-explainer to explain TGNN model independently for each time
step. Then the second module aims to discovery the dominant interesting
explanations from the explanations identified in the first module. In the
following we will discuss the two modules and use T-GCN [10] as an example of
TGNN model.

Figure 1: Our proposed temporal graph neural network explainer framework

###  IV-A T-GCN Explanation

A naive way to explain the TGNN $\Phi$ on its input $[X_{t},\cdots,X_{t+T-1}]$
is to treat the sequence as a single feature matrix and explain the model as
in the case of non-temporal models. One drawback of this approach is the
temporal information and dependencies among model’s variables are not
considered and included in the explanations. Furthermore, the number of
input’s features would be scaled up with a factor of the window $T$. This
introduces significant computation complexity on the explaining process.

To overcome challenges in explaining the TGNN discussed in Sect. III , we
reformulate the TGNN equations based on its sequential implementation [10] as
follow:

$\displaystyle Y$ $\displaystyle=\bar{\Phi}(G;X_{t+T-1};H_{t+T-1}),$ (3)
$\displaystyle H_{i+1}$
$\displaystyle=\bar{\Phi}(G;X_{i};H_{i}),i=t,\cdots,t+T-2.$ (4)

Here, $H_{i}$ is the hidden features or configurations that the TGNN computes
during the sequential forwarding computation. With this formulation, we can
consider the problem of explaining the TGNN $\Phi$ as the problem of
explaining $\bar{\Phi}$ at its last computation with argument $H_{t+T-1}$. On
one hand, the argument $H_{t+T-1}$ is the result of the aggregation of the
input features from the past time steps. On the other hand, it can be
considered as the configuration of the last computation where the model makes
the final prediction. That configuration dictates how the graph’s components
work together to generate the model’s prediction. Thus, we rewrite (Eq. 3) as
$Y=\bar{\Phi}_{H_{t+T-1}}(G;X_{t+T-1})$. Then, for each sequence
$[X_{t},\cdots,X_{t+T-1}]$ the function $\bar{\Phi}_{H_{t+T-1}}$ can be
explained by PGM-Explainer as described in Eq. 1.

Specifically, for each time sequence starting with index $t$, we generate a
perturbation data $\mathcal{D}_{t}$ of $\bar{\Phi}_{H_{t+T-1}}$. Similar to
that in PGM-Explainer, $\mathcal{D}_{t}$ contains two components. First is a
set of random seeds determining which nodes of the input graph $G$ is
perturbed. Second is an indicator whether the predictions on each nodes is
changed by the perturbation on the nodes. The predictions on the perturbations
are computed based on the function $\bar{\Phi}_{H_{t+T-1}}$, in which the
value of $H_{t+T-1}$ is computed based on the original input data by
forwarding the model using Eq. 4. For each $\mathcal{D}_{t}$, we use PGM-
Explainer to solve for an optimal Bayesian network $\mathcal{B}_{t}$
explaining the model at that snapshot.

Note that the explanation Bayesian network $\mathcal{B}_{t}$ can be different
among different snapshots. In analyzing temporal predictions of TGNN, the
network structures that can represent many snapshots are much more favorable.
Thus, we propose a Temporal Bayesian Information Criterion (TBIC) score
measuring the fitness of a given Bayesian network $\mathcal{B}$ with a
temporal data $\mathbf{D}=\\{\mathcal{D}_{t}\\}_{t=t_{s}}^{t_{e}}$:

$\displaystyle\textup{score}_{TBIC}(\mathcal{B}:\mathbf{D}):=\frac{1}{t_{e}-t_{s}+1}\sum_{t=t_{s}}^{t_{e}}\textup{score}_{BIC}(\mathcal{B}:\mathcal{D}_{t}).$

To mitigate the impact of variations in the data $\mathcal{D}_{t}$ at each
snapshot and grasp a better intuition on how much the edges in the Bayesian
network $\mathcal{B}$ help capture the data, we use a normalized version of
the TBIC score, called $F_{\mathbf{D}}(\mathcal{B})$. The normalized TBIC is
the different between the TBIC score of $\mathcal{B}$ and the Bayesian network
with no edge $\mathcal{B}_{0}$:

$\displaystyle
F_{\mathbf{D}}(\mathcal{B}):=\textup{score}_{TBIC}(\mathcal{B}:\mathbf{D})-\textup{score}_{TBIC}(\mathcal{B}_{0}:\mathbf{D})$
(5) $\displaystyle=$
$\displaystyle\frac{1}{t_{e}-t_{s}+1}\sum_{t=t_{s}}^{t_{e}}\left(\textup{score}_{BIC}(\mathcal{B}:\mathcal{D}_{t})-\textup{score}_{BIC}(\mathcal{B}_{0}:\mathcal{D}_{t})\right).$

We can see that each term in the sum of Eq. 5 captures the gain of including
the edges in $\mathcal{B}_{t}$ to fit each data $\mathcal{D}_{t}$.

With the normalized TBIC score $F_{\mathbf{D}}$, we now can define the
interesting Bayesian network and the temporal dominant interesting Bayesian
network. Specifically, the Bayesian network $\mathcal{B}$ is an _interesting_
Bayesian network on a given temporal window $[t_{s},t_{e}]$ if
$F_{\mathbf{D}}(\mathcal{B})>B_{threshold}$, where $B_{threshold}$ is a hyper-
parameter as a threshold for selecting the interesting Bayesian network.
Furthermore, if the temporal window $[t_{s},t_{e}]$ is not a subset of any
other interesting Bayesian network temporal window, then $\mathcal{B}$ is a
temporal _dominant interesting_ Bayesian network on that temporal window. The
definition of “dominance” provides a compact explanation.

###  IV-B Discover dominant interesting Bayesian networks

In this section, given the independent explanation from PGM-explainer
$\\{\mathcal{B}_{i}\\}_{i=t_{s}}^{t_{e}}$, and the data in each time step
$\\{\mathcal{D}_{i}\\}_{i=t_{s}}^{t_{e}}$, we aim to discover interesting
dominant Bayesian graph in the temporal window. We first described a brute-
force approach for temporal pattern discovery. Then we described our proposed
pruning approach based on the antimonocity property of dominant interesting
Bayesian network.

####  IV-B1 Brute-force approach

The brute-force approach has two phases, namely interesting Bayesian network
discovery and dominant interesting Bayesian network discovery. In the first
phase, for each candidate network, the algorithm scans every possible temporal
window and computes the interest score on the window. There are $n^{2}$
possible temporal windows and $n$ candidate Bayesian networks. The computation
cost is $O(n^{3})$ for the first phase. Then in the second phase, the
algorithm aims to find dominant interesting Bayesian network whose temporal
window is not a subset of that of any other interesting Bayesian network. It
scans every pair of interesting Bayesian network’s temporal window and
eliminates the one that is not dominant. Due to the space limit, we omit the
algorithm of the brute-force approach.

####  IV-B2 Proposed pruning approach

The brute-force approach does an exhaustive search on all temporal windows for
all Bayesian networks. There are lots of redundant computations in this step
and requires the second phase to eliminate the redundant Bayesian network
explanation. We propose to optimize the brute-force search by a top-down
traversal search[21] to leverage the temporal dominant relationship .

Specifically, given a temporal dominant Bayesian network over the temporal
window $[t_{1},t_{2}]$, we can conclude that no other temporal dominant
Bayesian graph exists in the sub-temporal window
$[t^{\prime}_{1},t^{\prime}_{2}]\subset[t_{1},t_{2}]$. Such property inspires
a top-down traversal search. We start to calculate the interest measure of
each Bayesian graph over the longest temporal window $[t_{1},t_{2}]$. The
algorithm recursively reduces the temporal window size if there is no temporal
dominant Bayesian network in the temporal window $[t_{1},t_{2}]$. Otherwise,
if it finds temporal dominant Bayesian network over $[t_{1},t_{2}]$, the
subset of the temporal window of $[t_{1},t_{2}]$ can be pruned out for other
Bayesian networks. The computation of interest measures for all Bayesian
network over the subset is eliminated.

Then we introduce the detailed implementation of the algorithm. We first
construct a directed acyclic graph (DAG) to represent the dominant
relationship between temporal windows. Each node represents one temporal
window $[t_{i},t_{j}]$ and has two child nodes that are sub-temporal windows
and cover one time step less, $[t_{i}+1,t_{j}]$ and $[t_{i},t_{j}-1]$. The
algorithm uses a queue to do breadth first search on the temporal window. For
each node, we evaluate the interest measure for all Bayesian networks over the
temporal window. If the node identifies at least one temporal dominant
Bayesian network, all the successors of the node will be pruned, otherwise,
the algorithm continues evaluating the successors of the node.

Computational complexity analysis:  The top-down search approach can
potentially eliminate redundant temporal search. In the best case, the
algorithm identifies the longest temporal window $[t_{s},t_{e}]$ as the
temporal dominant Bayesian network. The computation for one Bayesian network
is $O(n)$ for all Bayesian networks. In the worst case, no dominant Bayesian
graph is identified and the algorithm needs to evaluate all $n^{2}$ temporal
windows. The computational cost for $n$ candidate Bayesian networks is
$O(n^{3})$.

noend 1 The pruning approach

$\bullet$ Candidate Bayesian graph $\\{\mathcal{B}_{i}\\}_{i=t_{s}}^{t_{e}}$

$\bullet$ Perturbed dataset from the model $\mathbf{D}$

$\bullet$ Interest measure function $F_{\mathbf{D}}$

$\bullet$ All the Interesting dominant Bayesian graph and its dominant time
window

Candset $\leftarrow\emptyset$, Create a empty queue Q

Q.enque($[t_{s},t_{e}]$)

while Q not empty do $\mathcal{W}=[t_{1},t_{2}]\leftarrow Q.deque()$

for each $\mathcal{B}_{i}$ do

Scan the temporal window $\mathcal{W}$ and compute

the interest measure of Bayesian network $\mathcal{B}$

if $F_{\mathbf{D}}(\mathcal{B}_{i})>B_{threshold}$ then

Add $\\{\mathcal{B}_{i}:[t_{1},t_{2}]\\}$ to the CandSet

Prune all subtemporal window of $\mathcal{W}$ Break

if $\mathcal{W}$ has sub-temporal window then

$\mathcal{W}_{1}=[t_{1}+1,t_{2}],\mathcal{W}_{2}=[t_{1},t_{2}-1]$

Q.enque($\mathcal{W}_{1}$), Q.enque($\mathcal{W}_{2}$) return CandSet

##  V Experiment Results

In this section, we aim to evaluate our proposed approach on the temporal
graph neural network model and present the interpretation results on the
transportation domain dataset.

###  V-A Dataset Description

We use the datasets from transportation domain, which contains the traffic
speed information on the road network. The dataset SZ-taxi contains the taxi
trajectories of Shenzhen from Jan.1, 2015 to Jan.30, 2015. Following the
experiments setup, we select 156 major roads of Lanzhou districts as the study
area. Each road segment is represented with one node. The adjacency matrix
describes the spatial relationship between roads. The feature matrix describes
the speed dynamics overtime on each road. The traffic speed was aggregated
every 15 minutes. The dataset was split into $60\%$ for training, $20\%$ for
validation and $20\%$ for testing. We selected one day (discretize into 96
temporal steps) to do the interpretation of the prediction on the test
dataset.

###  V-B Experiment setup

We train T-GCN model[10] using Adam optimizer and set the learning rate to
$0.001$, batch size to 64 and training epoch to 3000. The accuracy of T-GCN on
the test dataset is $0.71$. Then we generate the perturbation dataset using
$1000$ samples. The perturbation threshold is set to $0.01$, and perturbation
probability is $0.2$. For dominant Bayesian network discovery, the Bayesian
score threshold is $1400$ based on the validation dataset. All experiments are
done on the high performance cluster using 1 NVIDIA A100 GPU with 80 GB GPU
memory.

###  V-C Interpretation of results

We present the interpretation results on some representative nodes to
visualize the results. The chosen target nodes have around ten two-hop
neighbors. The time series of the target node contains both congestion (low
speed) and non-congestion (high speed) time slots in one day to be
representative for the traffic condition.

Figure 2(a) shows one target node speed ground-truth and the prediction of
T-GCN, as well as that of one neighbor node. From the prediction trend, we can
observe, the T-GCN model predicts worse at the peak, because the GCN model
uses a smooth filter in the spatial network and capture the spatial
relationship by constantly moving the filter. Before applying our method to
explain the prediction of T-GCN model, we inspect the dependency dynamic of
the model in each snapshot. We first construct a standard Bayesian network,
which contains all neighborhood nodes within 2-hop and no edges. The Bayesian
score of standard network on each temporal snapshot data is shown in Figure
2(b). We can observe in the time $3$ to $4$ and $11$ to $12$, the standard
Bayesian score is higher, it implies that the target node and neighbors have a
higher probability to be independent of each other. On the contrary, around
$20$ to $22$ the standard Bayesian score is lower, meaning there exists an
interesting dependency between the target nodes and neighbors.

Secondly, we apply our approach to explain the predictions of T-GCN on each
temporal snapshot during a day and obtain the Bayesian network
$\\{\mathcal{B}_{i}\\}_{i=t_{s}}^{t_{n}}$. Then, we measure the fitness of the
identified Bayesian network to the data in other time slots using
$\textup{score}(\mathcal{B}:D_{i})$. To evaluate the relative improvement of
adding the dependency edges, we use the difference of the Bayesian score
between each network $\mathcal{B}_{i}$ and the standard Bayesian network
$\mathcal{B}_{0}$. Figure 3 shows the score results of three dominant
interesting Bayesian network. We can observe around the time window $3$ to
$4$, $6$ to $8$ and $19$ to $23$, the average score is higher. We show the
explanation results of the target node in Figure 4. Three dominant Bayesian
network were discovered in the time window [3, 4], [6, 8] and [19, 23]. We can
observe that in the early morning period, the influential nodes to the target
node is nodes $12,126,145$, while in the evening period, more dependency
structure is observed. Almost all neighbor nodes within 2-hop have high
influence on the target node in the evening. Based on the discovery, it is
reasonable to hypothesize that the early morning period traffic in this target
node is less rush than in the evening.

(a)  (b)

Figure 2: Ground-truth and prediction of one target node and neighbor (a),
standard Bayesian score of the target node (b) (The x axis represents the hour
in one day). Figure 3: The Bayesian score evaluated at the day for three
candidate Bayesian graph

(a)

(b)

(c)

(d)

Figure 4: (a). Original two-hop neighbors of the target node (TN) , (b-d).
Interesting dominant Bayesian discovered in temporal window: (b). [3, 4], (c).
[6, 8], (d). [19, 23]

(a)

(b)

(c)

Figure 5: (a). Original two-hop neighbors of the target node (TN). Interesting
dominant Bayesian network discovered in temporal window: (b). [8, 10], (c).
[21, 23].

As a comparison we provide the explanation results for another target node in
Figure 5. We can observe for this target node, the dominant Bayesian network
discovered around $[8,10]$ (Figure 5 (b)) has much more dependency structure
than the dominant Bayesian network in $[21,23]$ (Figure 5 (c)), so we
hypothesize that for this target node, the time window $[8,10]$ maybe rush-
hour period.

Analysis of Bayesian score threshold: The selection of interesting Bayesian
network depends on the Bayesian score threshold. A higher threshold can find
more critical patterns of the network dependency structure, but the related
dominant windows are shorter. On the other hand, a lower threshold can find
dominant Bayesian network with a longer time window but there may be
redundancy. The selection of the threshold can be based on the above trade-off
and domain knowledge.

###  V-D Analysis of Computational costs

Then we analyze the computational costs for brute-force and pruning approach.
As Figure 6 shows, the PGM-explainer module requires the same time for two
approaches ($22$ mins). For dominant explanation discovery module, our pruning
approach improve significantly than the brute-force approach.

Figure 6: Computational cost analysis

##  VI Conclusion

In this paper, we propose a novel explainer framework for TGNN model. The
framework consists of two modules that first explain each time slot prediction
independently and then discovery the dominant interesting explanations in a
time period. Case studies show that the proposed approach can discover the
dynamic structure depenency in TGNN model.

## Acknowledgement

This material is based upon work supported by the National Science Foundation
(NSF) under Grant No. FAI-1939725, SCH-2123809, IIS-2147908, IIS-2207072, and
OAC-2152085.

## References

  * [1] M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” in _Proceedings of the 30th International Conference on Neural Information Processing Systems_ , 2016, p. 3844–3852.
  * [2] T. N. Kipf and M. Welling, “Semi-Supervised Classification with Graph Convolutional Networks,” in _Proceedings of the 5th International Conference on Learning Representations_ , 2017.
  * [3] W. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in _Advances in Neural Information Processing Systems 30_ , 2017, pp. 1024–1034.
  * [4] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph Attention Networks,” _International Conference on Learning Representations_ , 2018.
  * [5] R. Levie, F. Monti, X. Bresson, and M. M. Bronstein, “Cayleynets: Graph convolutional neural networks with complex rational spectral filters,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 1, pp. 97–109, Jan 2019.
  * [6] F. Monti, K. Otness, and M. M. Bronstein, “Motifnet: A motif-based graph convolutional network for directed graphs,” _2018 IEEE Data Science Workshop (DSW)_ , pp. 225–228, 2018.
  * [7] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?” in _International Conference on Learning Representations_ , 2019\.
  * [8] Z. Ying, J. You, C. Morris, X. Ren, W. Hamilton, and J. Leskovec, “Hierarchical graph representation learning with differentiable pooling,” in _Advances in Neural Information Processing Systems 31_ , 2018, pp. 4800–4810.
  * [9] Z. Xinyi and L. Chen, “Capsule graph neural network,” in _International Conference on Learning Representations_ , 2019.
  * [10] L. Zhao, Y. Song, C. Zhang, Y. Liu, P. Wang, T. Lin, M. Deng, and H. Li, “T-gcn: A temporal graph convolutional network for traffic prediction,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 21, no. 9, pp. 3848–3858, 2019.
  * [11] X. Wang, Y. Ma, Y. Wang, W. Jin, X. Wang, J. Tang, C. Jia, and J. Yu, “Traffic flow prediction via spatial temporal graph neural network,” in _Proceedings of The Web Conference 2020_ , 2020, pp. 1082–1092.
  * [12] S. Min, Z. Gao, J. Peng, L. Wang, K. Qin, and B. Fang, “Stgsn—a spatial–temporal graph neural network framework for time-evolving social networks,” _Knowledge-Based Systems_ , vol. 214, p. 106746, 2021.
  * [13] C. J. Dong, C. F. Shao, C.-X. Zhuge, and M. Meng, “Spatial and temporal characteristics for congested traffic on urban expressway,” _Journal of Beijing University of Technology_ , vol. 38, no. 8, pp. 1242–1246, 2012.
  * [14] J. Lee, I. Lee, and J. Kang, “Self-attention graph pooling,” in _36th International Conference on Machine Learning, ICML 2019_ , 2019, pp. 6661–6670.
  * [15] A. Mohamed, K. Qian, M. Elhoseiny, and C. Claudel, “Social-stgcnn: A social spatio-temporal graph convolutional neural network for human trajectory prediction,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 14 424–14 432.
  * [16] Z. Ying, D. Bourgeois, J. You, M. Zitnik, and J. Leskovec, “GNNexplainer: Generating explanations for graph neural networks,” in _Advances in Neural Information Processing Systems 32_ , 2019, pp. 9244–9255.
  * [17] M. Vu and M. T. Thai, “Pgm-explainer: Probabilistic graphical model explanations for graph neural networks,” in _Advances in Neural Information Processing Systems_ , H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, Eds., vol. 33. Curran Associates, Inc., 2020, pp. 12 225–12 235.
  * [18] T. Schnake, O. Eberle, J. Lederer, S. Nakajima, K. Schütt, K.-R. Mueller, and G. Montavon, “Higher-order explanations of graph neural networks via relevant walks,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. PP, pp. 1–1, 09 2021.
  * [19] J. Pearl, “Chapter 3 - markov and bayesian networks: Two graphical representations of probabilistic knowledge,” in _Probabilistic Reasoning in Intelligent Systems_ , 1988, pp. 77 – 141.
  * [20] D. Koller and N. Friedman, _Probabilistic Graphical Models: Principles and Techniques - Adaptive Computation and Machine Learning_. The MIT Press, 2009.
  * [21] X. Zhou, S. Shekhar, and D. Oliver, “Discovering persistent change windows in spatiotemporal datasets: A summary of results,” in _Proceedings of the 2nd ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data_ , 2013, pp. 37–46.


Generalities sec:axes-definitions Graphs and trees

A graph $\Gamma$ is defined by $(V(\Gamma),E(\Gamma),\bar{\cdot},o,t)$ where

  * •

$V(\Gamma)$ is a set of _vertices_

  * •

$E(\Gamma)$ is a set of _edges_

  * •

the map $\bar{\cdot}$ is an involution $E(\Gamma)\to E(\Gamma)$ without fixed
point; for $e\in E(\Gamma)$ the edge $\bar{e}$ is called the _opposite edge_

  * •

the maps $o,t:E(\Gamma)\to V(\Gamma)$ are the _initial vertex_ and _terminal
vertex_ maps, with the property that every $e\in E(\Gamma)$ satisfies
$o(e)=t(\bar{e})$.

It is finite if $V(\Gamma),E(\Gamma)$ are finite. See [SerreArbresAmalgames]
for more details on graphs. An edge path in $\Gamma$ is a sequence
$e_{1},\dots,e_{k}$ with $e_{i}\in E(\Gamma)$ for $i\in\\{1,\dots,k\\}$ and
$t(e_{i})=o(e_{i+1})$ for $i\leq k-1$. It is _non-backtracking_ if for all
$i\in\\{1,\dots,k-1\\}$, $\bar{e}_{i}\neq e_{i+1}$. It is a _loop_ if
$o(e_{1})=t(e_{k})$. A _tree_ is a graph without non-backtracking loops. Let
$E^{+}(\Gamma)$ be an orientation of the edges, i.e. a subset of $E(\Gamma)$
such that $E^{+}(\Gamma)\sqcup\overline{E^{+}(\Gamma)}$ is a partition of
$E(\Gamma)$. A _metric_ on a graph $\Gamma$ is a map
$\len_{\Gamma}:E(\Gamma)\to\R_{+}$ such that for all $e\in E(\Gamma)$,
$\len_{\Gamma}(\bar{e})=\len_{\Gamma}(e)$. The _geometric realization_ of a
graph $\Gamma$ is the union of points $(x_{v})_{v\in V(\Gamma)}$ and segments
$(\sigma_{e})_{e\in E^{+}(\Gamma)}$ where $\sigma_{e}$ is isometric to
$[0,\len_{\Gamma}(e)]$ for every $e\in E(\Gamma)$, where for every $e\in
E^{+}(\Gamma)$ we identify the first point of $\sigma_{e}$ with $x_{o(e)}$ and
its last point with $x_{t(e)}$. It is endowed with the associated path metric.
It does not depend on the choice of $E^{+}(\Gamma)$. In the rest of the paper
we will identify trees and other graphs with their geometric realizations. A
_path_ in a tree $T$ is the image of a Lipschitz map from an interval to $T$.
It is _non-backtracking_ if the map is an immersion, and equivalently if it is
a the image of a geodesic. In the context of geometric realizations an _edge
path_ is a path which is the image of an edge path in the graph. For two
points $x,y\in T$, the segment $[x,y]$ is the unique geodesic from $x$ to $y$.

A _graph of groups_ is a graph $\Gamma$ together with collections of vertex
groups $(G_{v})_{v\in V(\Gamma)}$ and edge groups $(G_{e})_{e\in E(\Gamma)}$
and monomorphisms $\iota_{e}:G_{e}\to G_{t(e)}$. Let $\tau$ be a maximal
subtree in the graph $\Gamma$. The fundamental group $\pi_{1}(\Gamma,\tau)$ of
the graph of groups $\Gamma$ is defined as follows:

$\pi_{1}(\Gamma,\tau)=\left\langle\bigcup_{v\in
V(\Gamma)}G_{v}\cup(t_{e})_{e\in E(\Gamma)}|\bigcup_{v\in
V(\Gamma)}R_{v},\bigcup_{e\in E(\Gamma)}R_{e},R_{\tau}\right\rangle$

where

  * •

for $v\in V(\Gamma)$, $R_{v}$ is the set of relations of $G_{v}$

  * •

for $e\in E(\Gamma)$,
$R_{e}=\\{t_{e}\phi_{e}(h)t_{\bar{e}}\phi_{\bar{e}}(h)^{-1}/h\in G_{e}\\}$

  * •

$R_{\tau}:=\\{t_{e},e\in\tau\\}$

Note that for $h=1$ we obtain the relation $t_{\bar{e}}=t_{e}^{-1}$. Up to
isomorphism the fundamental group does not depend on the choice of $\tau$. If
the vertex groups and edge groups are finitely generated then
$\pi_{1}(\Gamma)$ is finitely presented. Let $G$ be a group. A _marked graph
of groups_ for $G$ is a graph of groups $\Gamma$ together with a _marking_
(i.e. an identification) $\Psi:G\to\pi_{1}(\Gamma)$. The automorphism group of
$G$ acts as follows on the set of marked graphs of groups: if $\phi\in\Aut(G)$
and $(\Gamma,\Psi)$ is a marked graph of groups then
$(\Gamma,\Psi)\cdot\phi:=(\Gamma,\Psi\circ\phi)$. A _$G$ -tree_ $T$ is a
metric simplicial tree with an action of $G$ by isometries. The tree $T$ is
_minimal_ if there is no proper $G$-invariant subtree. The _universal cover_
of a graph of groups $\Gamma$ is a minimal $\pi_{1}(\Gamma)$-tree $T$ such
that $T/G$ is isomorphic to $\Gamma$ as a graph and for every $v\in V(\Gamma)$
and every lift $\bar{v}\in T$, the stabilizer of $\bar{v}$ is isomorphic to
$G_{v}$. By Bass-Serre theory in [SerreArbresAmalgames], universal covers
exist and are unique up to $\pi_{1}(\Gamma)$-equivariant isomorphism. Moreover
Bass-Serre theory gives a correspondance between marked graphs of groups for
$G$ and $G$-trees. If $\Gamma$ is a metric graph then the metric naturally
lifts to its universal cover. In a $G$-tree $T$ we denote the pointwise
stabilizer of a vertex $v$ (resp. an edge $e$) by $G_{v}$ (resp. $G_{e}$).

A _generalized Baumslag-Solitar_ (GBS) group is a group which is isomorphic to
the fundamental group of a finite graph of groups where all vertex and edge
groups are infinite cyclic. If a generator is chosen for every vertex and edge
group then the monomorphisms $\phi_{e}$ are defined by the multiplication by
an integer $\lambda(\bar{e})\in\Z\setminus\\{0\\}$. Let $G$ be a GBS group. In
the general case there exist infinitely many marked graphs of cyclic groups
for $G$. Making $\Aut(G)$ act on a marked graph of groups often yields
infinitely many other markings, besides in general cases there are infinitely
many possible underlying graphs of groups. Let $T$ be a $G$-tree. A subgroup
$H<G$ is _elliptic_ in $T$ if it fixes a point in $T$. Suppose all elliptic
groups in $T$ are also elliptic in $S$. Then there exists a $G$-equivariant
map $T\to S$ (see by example [GuirardelLevitt07]). Let $T,T^{\prime}$ be
$G$-trees. We say that they lie in the same _deformation space_ if they have
the same sets of elliptic subgroups. Equivalently they are in the same
deformation space if there exist $G$-equivariant maps $T\to T^{\prime}$ and
$T^{\prime}\to T$. Now let us define the _cyclic deformation space_ $\D$
associated to a group $G$, as the set of minimal simplicial $G$-trees with
cyclic vertex and edge stabilizers, where we identify $T$ and $T^{\prime}$ if
there is a $G$-equivariant isometry or homothety $T\to T^{\prime}$.
Equivalently we could define $\D$ with marked graphs of groups. If $G$ is not
isomorphic to $\Z^{2}$ or the fundamental group of a Klein bottle $\langle
a,b|a^{2}=b^{2}\rangle\simeq\langle a,t|tat^{-1}=a^{-1}\rangle$, then $\D$ is
a deformation space, i.e. all trees in $\D$ have the same elliptic subgroups.
Let $T\in\D$ and let $e$ be an edge in $T$. Define the equivalence relation
$\sim_{e}$ as the minimal $G$-invariant equivalence relation such that
$x\sim_{e}y$ if $x,y\in e$. The _collapse_ of the edge $e$ is the quotient map
$T\to T/\sim_{e}$. The edge $e$ in $T$ is _collapsible_ if $T/\sim_{e}\in\D$.
Equivalently an edge is collapsible if its image in the quotient is not a loop
and one of its two labels is $\pm 1$. A tree of $\D$ is _reduced_ if none of
its edges is collapsible. GBS trees in the same deformation space share some
properties. Let $\Gamma$ be a finite connected graph. Then the first Betti
number $b_{1}(\Gamma)$ is defined by
$b_{1}(\Gamma)=\\#E(\Gamma)-\\#V(\Gamma)+1$. By [GuirardelLevitt07, Section 4]
the first Betti number is an invariant of the deformation space. Let $G$ be a
GBS group with cyclic deformation space $\D$. We say that an elliptic subgroup
$H<G$ is _big_ if there exists a tree $T\in\D$ such that $H$ fixes no edge in
$T$. From [GuirardelLevitt07] we deduce: Let $T\in\D$. The number of vertices
$v\in T$ such that for all edge $e$ with origin $v$, $G_{e}\neq G_{v}$ is
bounded by the number of conjugacy classes of big subgroups of $G$. If $T$ is
reduced then these numbers are equal. The notion of big subgroups is defined
in [GuirardelLevitt07], though it depends on a family $\A$ of subgroups of
$G$: a subgroup $H<G$ is big if it is elliptic and is not conjugate into a
subgroup of an element of $\A$. Here the corresponding choice for $\A$ is the
family of subgroups which fix an edge in a reduced tree of $\D$, or
equivalently in every reduced tree of $\D$. Thus an elliptic subgroup is big
if fixes a single point in some (equivalently any) tree in $\D$. Solvable GBS
groups are GBS groups isomorphic to $\Z$ and $\BS(1,n)$ for $n\in\N$ (which
include $\Z^{2}$ and the fundamental group of a Klein bottle).

##  Cyclic factors, irreducible automorphisms

From now on we assume $G$ is a non-solvable GBS group. The automorphism group
of $G$ is $\Aut(G)$. The outer automorphism group is
$\Out(G):=\Aut(G)/\Inn(G)$ where $\Inn(G)$ is the subgroup of inner
automorphisms $\\{c_{g}:x\mapsto gxg^{-1},g\in G\\}$. Cyclic factors are the
GBS analogue of free factors for free groups. A _cyclic factor_ of $G$ is a
subgroup $H$ such that there exists a graph of cyclic groups $\Gamma$ and an
identification $G\simeq\pi_{1}(\Gamma)$, with a subgraph $\Gamma_{H}$ such
that $H$ is conjugate to $\pi_{1}(\Gamma_{H})$. The family of cyclic factors
of $G$ is stable by conjugacy and by automorphisms.

  1. 1.

If $G:=\BS(2,4)=\langle a,t|ta^{2}t^{-1}=a^{4}\rangle$, the first graph of
groups of Figure • represents $G$. The red subgraph represents the subgroup
$H:=\langle a,t^{-1}a^{2}t\rangle$ which is a cyclic factor.

  2. 2.

The second and third graphs of Figure • represents $G:=\langle
u,r,s,t|tu^{n}t^{-1}=su^{n}s^{-1}=ru^{n}r^{-1}=u\rangle$. The subgroup
$\langle u,r\rangle\simeq\BS(1,n)$ is a cyclic factor, it can be seen in the
graph on the left. The subgroup $\langle
u,rur^{-1},rsus^{-1}r^{-1},rst\rangle\simeq\BS(1,n^{3})$ is a cyclic factor
which can be seen in the graph on the right.

Figure : Examples of cyclic factors

An automorphism $\phi\in\Aut(G)$ is _fully irreducible_ if no power of $\phi$
preserves the conjugacy class of a cyclic factor. Since inner automorphisms
preserve conjugacy classes, the full irreducibility can be defined for outer
automorphisms. A _representative_ for $\phi$ is a map $f:T\to T$ with $T\in\D$
which is $\phi$-equivariant, i.e. $\forall t\in T$, $\forall g\in G$,
$f(gt)=\phi(g)\cdot f(t)$. A representative for an outer automorphism class
$\psi\in\Out(G)$ is a representative for some automorphism in the class
$\psi$. Let $\phi\in\Out(G)$. A _pseudo-periodic_ conjugacy class for $\phi$
is the conjugacy class of an element $g\in G$ such that
$\|\phi^{n}(g)\|_{n\in\N}$ is bounded. An automorphism $\phi\in\Out(G)$ is
_pseudo-atoroidal_ if $\phi$ has no pseudo-periodic conjugacy class. Train
track representatives for automorphisms of $\Out(F_{N})$ were introduced in
[BestvinaHandelTrainTracks]. They are a main tool for studying these
automorphisms. One can define likewise train tracks for other families of
groups acting on trees. Let $T$ be a $G$-tree. A _gate structure_ on $T$ is a
$G$-invariant family of equivalence relations $(\sim_{v})_{v\in V(T)}$ on the
sets $E_{v}$ of edges with origin $v$. Equivalence classes for these relations
are called gates. Let $\tau:T\to T^{\prime}$ be a $G$-equivariant map sending
edges to non-degenerate non-backtracking paths. The gate structure _induced by
$\tau$_ is the minimal gate structure such that for $v\in V(T)$,
$e,e^{\prime}\in E_{v}$, if $\tau(e)\cap\tau(e^{\prime})$ has non-zero length
then $e\sim_{v}e^{\prime}$. Let $T$ be a $G$-tree with a gate structure. A
_turn_ in $T$ is a pair of edges with same origin. The turn
$\\{e,e^{\prime}\\}$ is _illegal_ if $e$ and $e^{\prime}$ belong to the same
gate. Otherwise the turn is _legal_. Let $\phi\in\Out(G)$. Let $f:T\to T$ be a
representative for $\phi$ sending vertex to vertex.. Then $f$ is _train track_
if for every $e\in E(T)$:

  * •

$\len(f(e))>0$

  * •

at every vertex $v\in V(T)$ there are at least two gates for the gate
structure induced by $f$.

  * •

for every $k\in\N$, $f^{k}(e)$ crosses only legal turns for the gate structure
induced by $f$.

The _train track structure_ is the gate structure such that $e\sim e^{\prime}$
if there exists $k\in\N$ such that $f^{k}(e)\cap f^{k}(e^{\prime})$ is not a
single point. Suppose $f:T\to T$ is a train track representative for a fully
irreducible automorphism $\phi\in\Out(G)$. Up to precomposing $f$ with a map
$T\to T$ whose restriction to edges is a homeomorphism, we may assume that $f$
stretches the edges uniformly. Let $e_{1},\dots,e_{n}$ be the edges of $T/G$.
Let $A(f)$ be the transition matrix for $f$ where $A(f)_{ij}$ is the number of
occurences of edges in the orbit $e_{i}$ in $f(e_{j})$, for $1\leq i,j\leq n$.
Irreducibility of $\phi$ implies that up to collapsing edges in $T$ the matrix
$A(f)$ is primitive, i.e. there exists $k\in\N$ such that $A(f)^{k}>0$ (see
[PapinDetection, Lemma 1.9]). The theorem of Perron-Frobenius below then
applies to $A(f)$: [Perron-Frobenius] Let $A$ be a non-negative primitive
matrix with size $n\times n$. There exists a real eigenvalue $\lambda>0$ (the
_Perron-Frobenius eigenvalue_) such that for every other eigenvalue
$\mu\neq\lambda$ we have $|\mu|<\lambda$. The eigenvectors for $\lambda$ are
unique up to scalar multiplication and there exists an eigenvector $v$ for
$\lambda$ such that $v>0$. A proof of the theorem can be found in [Seneta,
Theorem 1.1]. Let $\lambda$ be the Perron-Frobenius eigenvalue and
$(l_{1},\dots,l_{n})$ be the left Perron-Frobenius eigenvector. Define a
metric on $T$ by $\len(e_{n}):=l_{n}$. Then for every $e\in E(T)$ we have
$\len(f(e))=\lambda\len(e)$, and the Lipschitz constant $\Lip(f)$ is
$\lambda$. From now on we assume train track maps are linear on edges and have
the same Lipschitz constant on all edges.

Recall that it is not known whether all fully irreducible automorphisms admit
train track maps. However some do exist: Example • is an example of fully
irreducible automorphism with a train track representative. Let $G:=\langle
r,s,t|ru^{n}r^{-1}=su^{n}s^{-1}=atu^{n}t^{-1}=u\rangle$. Define
$\phi\in\Aut(G)$ by

$\phi:\cases{u}\mapsto u\\\ r\mapsto s\\\ s\mapsto t\\\ t\mapsto
rsts^{-1}t^{-1}$

Define the tree $T$ (whose quotient $T/G$ is represented on Figure •) by a
fundamental domain with vertices $v,x$ and edges e_a & = [ v, rv]
e_b = [v, t x ]
e_e = [v, x]
e_f = [v, s^-1x]

Figure : The quotient $T/G$ in Example •

Define $f$ on $T$ by f : & v ↦v, x ↦tx
e_a ↦e_e- s ⋅¯e_f
e_b ↦e_a- r⋅e_e - rs ⋅¯e_f - rs ⋅e_b - rst ⋅¯e_e - rst ⋅e_f
e_e ↦e_b
e_f ↦e_e The map $f$ is a train track representative for $\phi$. To see this
we can compute the successive images of the turns taken by $f$. Consider the
turn $\\{\bar{e}_{a},re_{e}\\}$ at vertex $rv$ which is taken by $f(e_{b})$:

[scale =0.95] (0) at (0,0) $r\\{r^{-1}\bar{e}_{a},e_{e}\\}$; (1) at (3,0)
$\phi(r)\\{e_{f},e_{b}\\}$; (2) at (6,0) $\phi^{2}(r)\\{e_{e},e_{a}\\}$; (3)
at (9,0) $\phi^{3}(r)\\{e_{b},e_{e}\\}$; (4) at (12,0)
$\phi^{4}(r)\\{e_{a},e_{b}\\}$; [-latex] (0) – (1) node [midway, above] $f$;
[-latex] (1) – (2) node [midway, above] $f$; [-latex] (2) – (3) node [midway,
above] $f$; [-latex] (3) – (4) node [midway, above] $f$; [-latex, dashed] (4)
.. controls (12, -2) and (6,-2) .. (2)node [midway, above] $f$ ;

When applying $f$ to $\phi^{4}(r)\\{e_{a},e_{b}\\}$ we find a turn in the
orbit of $\phi^{2}(r)\\{e_{e},e_{a}\\}$ which we had already found. Thus
$\\{\bar{e}_{a},re_{e}\\}$ is a legal turn. The proof for the other turns goes
the same way.

The inverse of $\phi$ is

$\phi^{-1}:\cases{u}\mapsto u\\\ r\mapsto tsrs^{-1}r^{-1}\\\ s\mapsto r\\\
t\mapsto s$

which is the same automorphism as $\phi$, but with swapped roles for $r$ and
$t$. Thus it admits a train track map.

Let $f:T\to S$ be a $G$-equivariant map between trees of $\D$, sending vertex
to vertex and edge to edge path. By [ForesterDeformation] it is a quasi-
isometry, i.e. a map such that for all $x,y\in T$, $K^{-1}d_{T}(x,y)-C\leq
d_{T^{\prime}}(h(x),h(y))\leq Kd_{T}(x,y)+C$. Thus the map has bounded
backtracking property (see [GJLL]) and there exists a constant $\BBT(f)\leq
K^{2}C+C$ such that for every $x,y\in T$ the image $f([x,y])$ lies in a
$\BBT(f)$-neighbourhood of $[f(x),f(y)]$. In [BestvinaFeighnHandelLaminations]
and [AlgomKfirStrongly], a similar constant $\BCC(f)$ is used. Let us clarify
the link between these constants. Suppose $\alpha\cdot\beta$ is a geodesic
concatenation of paths with $\alpha$ $f$-legal. When applying $f$ to
$\alpha\cdot\beta$, there is a subsegment $\tau\subset\alpha$ such that
$f(\tau)\subset f(\beta)$. Let $\tau^{\prime}\subset\beta$ be a minimal prefix
such that $f(\tau)\subset f(\tau^{\prime})$. The first point of $\tau$ and
last point of $\tau^{\prime}$ are mapped to the same point. Then because $f$
is a quasi-isometry there is a constant $K$ depending only on $f$ such that
the length of $\tau\cdot\tau^{\prime}$ is bounded by $K$. This gives a bound
$\BCC(f)$ (from _bounded cancellation constant_ , introduced by Cooper in
[CooperAutomorphisms]) on $f(\tau)$: the simplification which occurs at an
illegal turn is bounded by $\BCC(f)$. By applying the previous paragraph to
$\tau\cdot\tau^{\prime}$ we have $\BCC(f)\leq\BBT(f)$. In order to keep a
reduced number of constants, we will use the $\BBT$ constant instead of $\BCC$
where it could be used. For a path $\eta$ in a tree $T$, we denote by $[\eta]$
the unique non-backtracking path which has the same endpoints as $\eta$. We
can extend this notation to infinite paths which converge to a point in the
boundary of $T$: for example, this is well-defined for a bi-infinite quasi-
geodesic such as the image of a line by a quasi-isometry. Let $\phi\in\Out(G)$
be a fully irreducible automorphism with a train track representative $f:T\to
T$. The _critical constant_ is $C_{f}:=\frac{2\BBT(f)}{\lambda-1}$. The
critical constant has the following property: for any geodesic concatenation
$\alpha\cdot\beta\cdot\gamma\subset T$ such that $\beta$ is legal and
$\len(\beta)\geq C_{f}$ then let
$\alpha^{\prime}\subset\alpha,\beta^{\prime}\subset\beta,\gamma^{\prime}\subset\gamma$
such that the path $[f(\alpha\cdot\beta\cdot\gamma)]$ can be written as the
concatenation
$[f(\alpha^{\prime})]\cdot[f(\beta^{\prime})]\cdot[f(\gamma^{\prime})]$. Then
$\len(f(\beta^{\prime}))\geq C_{f}$. More specifically we have: Let
$\phi\in\Out(G)$ be fully irreducible. Let $f:T\to T$ be a train track
representative. Let $\alpha$ be any path in $T$. Let $\beta\subset\alpha$ be a
legal subpath with length at least $2C_{f}$. Define $\beta^{\prime}$ as the
legal subpath of $\beta$ obtained by cutting out the
$\frac{C_{f}}{2}$-neighbourhood of the endpoints. Then $\beta^{\prime}$
satisfies the following condition: for all $n\in\N$

$f^{n}(\alpha\setminus\beta^{\prime})\cap
f^{n}(\beta^{\prime})=\varnothing\text{and}f^{n}(\beta^{\prime})\subset[f^{n}(\alpha)]$

In particular $\len([f^{n}(\alpha)])\geq\lambda^{n}\len(\beta^{\prime})$. Let
$\alpha,\beta$ be as above. We actually prove a slightly stronger statement by
induction on $n$. Define $\beta^{\prime}_{n}$ as the segment obtained by
cutting out a $\BBT(f)\displaystyle\sum_{k=1}^{n}\lambda^{-k}$-neighbourhood
from the endpoints of $\beta$. Observe that
$\beta^{\prime}=\bigcap_{n\in\N}\beta^{\prime}_{n}$ since
$\BBT(f)\displaystyle\sum_{k=1}^{\infty}\lambda^{-k}=\frac{\BBT(f)}{\lambda-1}=\frac{C_{f}}{2}$.
We will prove that for all $n\in\N$ we have

$f^{n}(\alpha\setminus\beta^{\prime}_{n})\cap
f^{n}(\beta^{\prime}_{n})=\varnothing\text{and}f^{n}(\beta^{\prime}_{n})\subset[f^{n}(\alpha)]$

and since $\beta^{\prime}\subset\beta^{\prime}_{n}$ is a subsegment of the
legal segment $\beta^{\prime}_{n}$, the same holds for $\beta^{\prime}$. The
condition is true for $n=0$ since $\beta^{\prime}_{0}=\beta$. Suppose the
lemma holds for some $n\in\N$. Since $\beta^{\prime}_{n}$ is legal we have
$\len(f^{n}(\beta^{\prime}_{n}))=\lambda^{n}\len(\beta^{\prime}_{n})$. Besides
$f^{n}(\beta^{\prime}_{n})\subset[f^{n}(\alpha)]$. Apply $f$ to the path
$f^{n}(\alpha)$. There may be cancellation at the endpoints of the legal
segment $f^{n}(\beta^{\prime}_{n})$ but this cancellation does not exceed
$\BBT(f)$ when measured in $f^{n+1}(\beta^{\prime}_{n})$, since
$\beta^{\prime}_{n}$ is legal. This neighbourhood in
$f^{n+1}(\beta^{\prime}_{n})$ corresponds to a
$\lambda^{-n-1}\BBT(f)$-neighbourhood of the endpoints of
$\beta^{\prime}_{n}$: as a result $f^{n+1}(\beta^{\prime}_{n+1})$ does not
intersect $f(f^{n}(\alpha)\setminus f^{n}(\beta^{\prime}_{n}))$ since it is
contained in $\beta^{\prime}_{n}$. It does not intersect
$f(f^{n}(\beta^{\prime}_{n})\setminus f^{n}(\beta^{\prime}_{n+1}))$ either.
Finally note that $f(f^{n}(\alpha)\setminus f^{n}(\beta^{\prime}_{n}))\cap
f^{n+1}(\beta^{\prime}_{n})=f^{n+1}(\alpha\setminus\beta^{\prime}_{n})\cap
f^{n+1}(\beta^{\prime}_{n})$. Since $f^{n+1}(\beta^{\prime}_{n+1})$ does not
meet $f^{n+1}(\alpha\setminus\beta^{\prime}_{n+1})$, is is contained in
$[f^{n+1}(\alpha)]$. A consequence of Lemma  is: Let $\phi\in\Out(G)$ be fully
irreducible. Let $f:T\to T$ be a train track representative. For any path
$\alpha$ in $T$, for any legal subpath $\beta\subset\alpha$ such that
$\len(\beta)>2C_{f}$, we have for every $n\in\N$:

$\len(f^{n}(\beta)\cap[f^{n}(\alpha)])\geq\frac{1}{2}\lambda^{n}\len(\beta)$

Suppose $\alpha$ contains a legal subsegment $\beta$ of length greater than
$2C_{f}$. Let $\beta^{\prime}$ be the subsegment of $\beta$ at distance
$\frac{C_{f}}{2}$ from the endpoints of $\beta$. By Lemma , for every
$n\in\N$, $f^{n}(\beta^{\prime})\subset[f^{n}(\alpha)]$ so we have: (f^n(β’))
&= λ^n (β’)
= λ^n ( (β) - 2 (f)λ\- 1 )
≥λ^n (β) (1- 12 ) Therefore
$\len(f^{n}(\beta)\cap[f^{n}(\alpha)])\geq\frac{1}{2}\lambda^{n}\len(\beta)$.
Let $f:T\to T$ be a train track representative for $\phi\in\Out(G)$. A non-
backtracking segment $\eta\subset T$ is a _periodic Nielsen path_ if there
exists $g\in G$ and $n\geq 1$ such that $g[f^{n}(\eta)]=\eta$. We call it
simply a Nielsen path if we can choose $n=1$. A periodic Nielsen path is
_indivisible_ if it cannot be written as the non-backtracking concatenation
$\alpha\cdot\beta$ of two periodic Nielsen paths. A result about periodic
indivisible Nielsen paths (or _pINPs_) from [PapinDetection] is: Let $f:T\to
T$ be a train track representative for an automorphism $\phi\in\Out(G)$. There
are only finitely many orbits of periodic indivisible Nielsen paths. Periodic
Nielsen paths give a characterization of pseudo-periodic conjugacy classes for
$\phi\in\Out(G)$, proved in [PapinDetection, Section 3]: Let $f:T\to T$ be a
train track representative for $\phi\in\Out(G)$. The conjugacy class of an
element $g\in G$ is pseudo-periodic for $\phi$ if and only if the axis of $g$
in $T$ is a geodesic concatenation of periodic indivisible Nielsen paths.
Suppose that $\phi$ is fully irreducible, pseudo-atoroidal and has a train
track representative $f:T\to T$. Then there exists $m\in\N$ such that it is
impossible to concatenate more than $m$ periodic Nielsen paths for $f$
together in $T$, and more than $m$ periodic Nielsen paths for $f_{-}$ in
$T_{-}$. There are finitely many orbits of periodic INPs; let $l$ be the
number of orbits of periodic INPs. By contradiction, suppose $L$ is a path in
$T$ which contains a concatenation of more than $2l$ pINPs. Then there exists
$\eta,g\eta\subset L$ with $g\in G$ loxodromic such that there is a
fundamental domain for $g$ which is a concatenation of pINPs. By Lemma , this
implies that $g$ is a loxodromic pseudo-periodic element for $\phi$, which is
impossible since $\phi$ is pseudo-atoroidal, so we can set $m:=2l$.

##  The Lipschitz metric on $\D$

The space $\D$ can be endowed with a pseudo-metric called the _Lipschitz
metric_. For $T,T^{\prime}\in\D$ define

$\Lip(T,T^{\prime})=\inf_{f:T\to T^{\prime}}\Lip(f)$

where the infimum is taken over all $G$-equivariant Lipschitz functions
$f:T\to T^{\prime}$. In [MeinertTheLipschitzMetric] the following is proved:
For $T,T^{\prime}\in\D$ there exists a $G$-equivariant map $f:T\to
T^{\prime}$, sending vertex to vertex and edge to edge path, linear on the
edges, such that $\Lip(f)=\Lip(T,T^{\prime})$. The Lipschitz metric is defined
as follows: for $T,T^{\prime}\in\D$

$d_{\Lip}(T,T^{\prime})=\log\left[\Lip(T,T^{\prime})\frac{\vol(T/G)}{\vol(T^{\prime}/G)}\right]$

The distance $d_{\Lip}(T,T^{\prime})$ is unchanged by rescaling $T$ or
$T^{\prime}$: it only depends on their projective classes. If $T,T^{\prime}$
are normalized so that $\vol(T)=\vol(T^{\prime})=1$ then
$d_{\Lip}(T,T^{\prime})=\log\Lip(T,T^{\prime})$. Sometimes it is more
practical to work with $1$-Lipschitz maps, for example when $T\to T^{\prime}$
is a collapse or a fold. When $\Lip(T,T^{\prime})=1$ then
$d_{\Lip}(T,T^{\prime})=\log\frac{\vol(T)}{\vol(T^{\prime})}$. The Lipschitz
metric is not a metric in the actual sense. The Lipschitz metric has the
following properties:

  1. [label=()]

  2. 1.

for $T,T^{\prime}\in\D$, $d_{\Lip}(T,T^{\prime})\geq 0$

  3. 2.

for $T,T^{\prime},T^{\prime\prime}\in\D$, $d_{\Lip}(T,T^{\prime\prime})\leq
d_{\Lip}(T,T^{\prime})+d_{\Lip}(T^{\prime},T^{\prime\prime})$

(i) Let $T,T^{\prime}\in\D$ scaled such that $\Lip(T,T^{\prime})=1$. Then $f$
induces a $1$-Lipschitz map on the quotients. By minimality $f$ is surjective
so $\vol(T^{\prime}/G)\leq\vol(T/G)$. Thus

$\log\Lip(T,T^{\prime})\frac{\vol(T/G)}{\vol(T^{\prime}/G)}\geq 1$

(ii) Let $T,T^{\prime},T^{\prime\prime}\in\D$. Let $f:T\to
T^{\prime},f^{\prime}:T^{\prime}\to T^{\prime\prime}$ be Lipschitz maps. Then
$\Lip(T,T^{\prime\prime})\leq\Lip(f^{\prime}\circ
f)\leq\Lip(f)\Lip(f^{\prime})$. By taking the lower bound we get
$\Lip(T,T^{\prime\prime})\leq\Lip(T,T^{\prime})\Lip(T^{\prime},T^{\prime\prime})$.
By taking the logarithm we obtain what we want. The other properties of
metrics fail for $\D$:

  * •

like in $\CV_{N}$ the Lipschitz metric is not symmetric. A common counter
example is drawn on Figure •: if $T,T^{\prime}$ are the same tree with a
different metric on edges such that $T^{\prime}/G$ has a very short loop,
$d_{\Lip}(T^{\prime},T)$ is very big.

  * •

unlike in $\CV_{N}$ there exist $T,T^{\prime}$ in $\D$ such that
$d_{\Lip}(T,T^{\prime})=0$ and $d_{\Lip}(T^{\prime},T)\neq 0$. More precisely,
$d_{\Lip}(T^{\prime},T)$ can be chosen arbitrarily big. See Figure •.

  * •

If $\phi\in\Out(G)$ and $T\in\D$ then $d_{\Lip}(T,T\cdot\phi)=0$ implies that
$T=T\cdot\phi$. This is a consequence of the fact that the actions are minimal
so maps are surjective. A $1$-Lipschitz $G$-equivariant surjective map from
$T$ to itself is an isometry, unless $G$ is solvable.

Figure : Counter examples for symmetry of the Lipschitz metric

The Lipschitz metric and its computation have been explored before in
[BestvinaBersLike] for free groups, [FrancavigliaMartino] for free products,
and [MeinertTheLipschitzMetric] for more general deformation spaces. The facts
presented below can be found in these papers. Let $T,T^{\prime}\in\D$. Let
$f:T\to T^{\prime}$ be a piecewise linear $G$-equivariant map. The _tension
graph_ $\Delta(f)$ is the subforest of $T$ spanned by edges $e\in E(T)$ such
that the stretch factor on $e$ is $\Lip(f)$. The map $f$ is _optimal_ if it
realizes the infimum of $\Lip(T,T^{\prime})$ and if at every vertex
$v\in\Delta(f)$, there are at least two gates at $v$ for the gate structure
induced by $f$ which contain edges in $\Delta(f)$. In
[MeinertTheLipschitzMetric] Meinert proves that optimal maps exist. The
distance between two points in $\D$ can be effectively computed by comparing
translation lengths of some elements of $G$ in both trees. Suppose $f:T\to
T^{\prime}$ is a $G$-equivariant map between trees of $\D$. For every $g\in G$
we have, by applying $f$ to a fundamental domain,

$\frac{\|g\|_{T^{\prime}}}{\|g\|_{T}}\leq\Lip(f)$

thus by taking the lower bound we have $\Lip(T,T^{\prime})\geq\max_{g\in
G}\frac{\|g\|_{T^{\prime}}}{\|g\|_{T}}$. It is actually an equality, as this
result from [MeinertTheLipschitzMetric] states: Let $T,T^{\prime}\in\D$. Let
$f:T\to T^{\prime}$ be an optimal map. There exists $g\in G$ such that
$\axe_{T}(g)$ is $f$-legal and contained in the tension graph for $f$. In
particular

$\Lip(T,T^{\prime})=\frac{\|g\|_{T}^{\prime}}{\|g\|_{T}}=\max_{h\in
G}\frac{\|h\|_{T}^{\prime}}{\|h\|_{T}}$

Let $T\in\D$. A _candidate_ of $T$ is an element $g\in G$ such that the map
$\pi:\axe_{T}(g)/\langle g\rangle\to T/G$ has one of the following forms (see
Figure •):

  * •

a loop: the map $\pi$ is an embedding

  * •

a figure eight: there are two embedded circles $u,v$ in $T$ which intersect in
exactly one point. The map $\pi$ maps the circle $\axe_{T}(g)/\langle
g\rangle$ to the tight loop which crosses $u$ and $v$ successfully.

  * •

a barbell: there are two disjoint embedded circles $u,v$ in $T/G$, and a
segment $s$ which connects $u$ to $v$; $\pi$ maps the circle to the tight loop
which crosses $u,s$, then $v$, and then $s$ backwards.

  * •

an embedded singly degenerate barbell : it is the degenerate case of the
barbell where $v$ is a single vertex. In that case, the vertex group at $v$
must be greater than the edge group of the last edge of $s$.

  * •

an embedded doubly degenerate barbell : degenerate case of the barbell where
both circles are single vertices. The vertex group at $u$ must also be greater
than the edge group of the first edge of $g$.

In particular a candidate crosses each orbit of edge at most twice.

Figure : The five possible shapes for a candidate in the quotient graph

In [FrancavigliaMartino, Theorem 9.10] the following theorem is proved for the
case of free products: Let $T\in\D$. For every $T^{\prime}\in\D$, there exists
a candidate $g$ of $T$ such that

$\Lip(T,T^{\prime})=\frac{\|g\|_{T}^{\prime}}{\|g\|_{T}}$

For the proof we refer to [FrancavigliaMartino]. Note that the context differs
a little since the deformation space and the group are different. The relevant
point is that contrary to elements of $\CV_{N}$, trees in the outer space for
a free product may have non-free vertex stabilizers, which account for the
degenerate barbells. In the case of GBS products we also have vertices whose
stabilizer is greater than the stabilizers of incident edges, hence the
presence of degenerate barbell candidates.

##  The axis of an irreducible automorphism

For an automorphism $\phi\in\Out(G)$ with a primitive train track map $f:T\to
T$, then

$\Lip(f)=\Lip(T,T\cdot\phi)=\min_{S\in\D}\Lip(S,S\cdot\phi)$

Since $f$ is a train track map, at each vertex of $T$ there are at least two
gates. Consequently there exists $h\in G$ such that $\axe_{T}(g)$ is legal.
Let $n\in\N$. Since $h$ is $f^{n}$-legal for all $n\in\N$ we have
$\frac{\|\phi^{n}(h)\|_{T}}{\|h\|_{T}}=\Lip(f^{n})=\Lip(f)^{n}$. Then we have
$\Lip(T,T\cdot\phi^{n})=\sup_{g\in
G}\frac{\|\phi^{n}(g)\|_{T}}{\|g\|_{T}}=\frac{\|\phi^{n}(h)\|_{T}}{\|h\|_{T}}=\Lip(f)^{n}$.
Let $\lambda:=\Lip(f)$. Let $S\in\D$. Let $f^{\prime}:S\to S\cdot\phi$ be such
that $\Lip(S,S\cdot\phi)=\Lip(f^{\prime})=:\lambda^{\prime}$. By triangular
inequality, for $n\in\N$ we have $\Lip(S,S\cdot\phi^{n})\leq\lambda^{\prime
n}$. By triangular inequality we have

$\lambda^{n}=\Lip(T,T\cdot\phi^{n})\leq\Lip(T,S)\Lip(S,S\cdot\phi^{n})\Lip(S,T)\leq\lambda^{\prime
n}\Lip(T,S)\Lip(S,T)$

If $\lambda^{\prime}<\lambda$ this inequality becomes false when $n$ is big
enough, hence the minimality of $\lambda=\Lip(T,T\cdot\phi)$. A map
$\gamma:\R\to\D$ is a _geodesic_ for the Lipschitz distance if for any
$t,s\in\R$, $t<s\Rightarrow d_{\Lip}(\gamma(t),\gamma(s))=s-t$. Since the
metric is not symmetric, the distance $d_{\Lip}(\gamma(s),\gamma(t))$ needs
not be $|s-t|$: in fact it can even be zero. Let $f:T\to T$ be a train track
representative for $\phi$. There exists a geodesic $\L_{f}:\R\to\D$ such that
for every $n\in\Z$, $T\cdot\phi^{n}\in\L_{f}$, and such that the map $\L_{f}$
is continuous for the axes topology. For a construction see
[MeinertTheLipschitzMetric, Section 4.4]. The _axes topology_ on $\D$ is the
coarsest topology such that the functions $T\mapsto\|g\|_{T}$ for $g\in G$ are
continuous; for more information on the topologies of $\D$ see
[GuirardelLevitt07]. If $f:T\to T$ is a train track representative we choose
an arbitrary axis $\L_{f}$ crossing $T$ and denote by $T_{t}$ the unique point
of the axis such that $d_{\Lip}(T,T_{t})=t$ if $t\geq 0$ and
$d_{\Lip}(T_{t},T)=-t$ if $t\leq 0$. Similarly there is an axis $\L_{f_{-}}$
for $\phi^{-1}$ defined from $f_{-}:T_{-}\to T_{-}$. Since $d_{\Lip}$ is
$\Out(G)$-invariant the axes stay within a bidirectional bounded neighbourhood
of each other.

We already stated that between any two trees in $\D$, there exists a
$G$-equivariant quasi-isometry. The quasi-isometry constants can be chosen
uniformly if the trees lie in a subsegment of $\L_{f}$: For any $T,S\in\D$ and
$D\geq 1$ such that $\max\\{\Lip(T,S),\Lip(S,T)\\}\leq D$, any optimal map
$T\to S$ is an equivariant $(D,4D)$-quasi-isometry. Let $T,S\in\D$. Scale
$T,S$ such that $\vol(T/G)=\vol(S/G)=1$. There exists $X\subset T$ such that
$G\cdot X=T$ and $\diam(X)\leq 1$. For every oriented edges
$\overrightarrow{e},\overrightarrow{e^{\prime}}\in E(T)$, there exists an edge
path with length at most $2$ with first edge $\overrightarrow{e}$ and last
edge $h\overrightarrow{e^{\prime}}$ for some $h\in G$. This fails if $G$ is
solvable, but we assumed that it is not the case. Let us prove this fact.
First we will prove that for any edge $e$ there exists a path
$\overrightarrow{e}\dots\overleftarrow{he}$ for some $h\in G$. Since $G$ is
not solvable, then the action of $G$ on $T$ is irreducible. Since $T$ is not a
line, there exist translates $h_{1}e,h_{2}e$ such that for any line containing
both edges, the orientations of the edges along the line differ. There exists
$h\in G$ such that $\axe_{T}(h)$ crosses both $h_{1}e$ and $h_{2}e$. Either
$h_{1}e$ and $h_{2}e$ point towards each other, or they may point away from
each other, but in that case there exists $k\in\Z$ such that $h^{k}h_{1}e$ and
$h_{2}e$ point towards each other. Then we get a path
$\overrightarrow{h_{1}e}\dots\overleftarrow{h_{2}e}$. Now let $e,e^{\prime}$
be edges in the tree. There is a path which connects both edges, but the path
may fail to contain a translate of
$\overrightarrow{e}\dots\overrightarrow{he^{\prime}}$ for some $h\in G$. By
concatenating paths which reverse the orientation on one or both sides we
obtain a path satisfying the condition. As for the bound on the length of the
path, observe that if an edge appears in the path twice with same orientation,
then subpath can be deleted to obtain a shorter path.

Let $\tau:T\to S$ be an optimal map. Let $x,y\in T$. Let $e$ be the first edge
of $[x,y]$. Let $e^{\prime}$ be an edge with origin $y$ and not in $[x,y]$:
such an edge exists since $T$ is minimal. By the fact above, there exists
$g\in G$ and a path containing
$\overrightarrow{e^{\prime}},g\overrightarrow{e^{\prime}}$ with these
orientations and length at most $2$. Thus $d_{T}(gx,y)\leq 2$ and
$[x,y]\subset\axe_{T}(g)$. We have $d_{T}(x,y)+2\leq\|g\|_{T}$. Then by Lemma
we have $\Lip(S,T)\leq D,\Lip(T,S)\leq D$ so

$d_{S}(\tau(x),\tau(y))\leq Dd_{T}(x,y)$

and d_S(τ(x), τ(y)) &≥d_S(τ(x), τ(gx)) - d_S(τ(gx), τ(y))
≥∥g∥_S - 2(τ)
≥∥g∥TD -2(τ)
≥dT(x,y)D - 2D -2D Then the optimal map $\tau:T\to T_{t^{\prime}}$ is a
$(D,4D)$-quasi-isometry. We have the following result about the axes $\L_{f}$
and $\L_{f_{-}}$: Let $\phi\in\Out(G)$ be a fully irreducible automorphism.
Let $f:T\to T$ be a train track representative for $\phi$ and $f_{-}:T_{-}\to
T_{-}$ be a train track representative for $\phi^{-1}$. Let
$\L_{f},\L_{f_{-}}$ be axes in $\D$ for $\phi$ and $\phi^{-1}$. Let $a<b$,
$c,d$ be real numbers. There exists a constant $D_{a,b,c,d}>1$ such that for
every $X,Y\in\\{T_{t}/a\leq t\leq b\\}\cup\\{(T_{-})_{t}/c\leq t\leq d\\}$,
$\Lip(X,Y)\leq D_{c,d}$. Let $n,m\in\N$ be such that

$n\log(\lambda)\leq a,m\log(\lambda)\geq b,n\log(\lambda_{-})\leq
c,m\log(\lambda_{-})\geq d$

There is a quadrilateron which crosses
$T\cdot\phi^{n},T\cdot\phi^{m},T_{-}\cdot\phi^{m},T_{-}\cdot\phi^{n}$, which
contains $\\{T_{t}/a\leq t\leq b\\}$ and $\\{(T_{-})_{t}/c\leq t\leq d\\}$.
Its length is

$d:=d_{\Lip}(T\cdot\phi^{n},T\cdot\phi^{m})+d_{\Lip}(T,T_{-})+d_{\Lip}(T_{-}\cdot\phi^{m},T_{-}\cdot\phi^{n})+d_{\Lip}(T_{-},T)$

Therefore, for every $X,Y$ as above we have $L(X,Y)\leq D:=e^{d}$. Lemmas •
and  imply that for every $S\in\D$, there exist $(K,C)$ such that for every
$t\in[0,\log(\lambda)]$, there exist equivariant $(K,C)$-quasi-isometries
$T_{t}\to S$ and $S\to T_{t}$.