S}_{{\mathcal{P}}}\right)^{n}\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Definition}\right\\}}\end{array}$

Next, we define a bound on ${\tt
DRuns}\left(\gamma\right)\left(\mathsf{l}\right)\left(n\right)$. We
characterize the set of runs that visit the set of small configurations “many
times” before visiting $\mathsf{l}$. For sets of configurations
$G_{1},G_{2}\subseteq\Gamma_{{\mathcal{P}}}$, a run $\rho$, and
$m\in\mathbb{N}$, we write $\rho\models G_{1}\,{\tt Before}^{m}\,G_{2}$ to
denote that $\rho=\pi\boldsymbol{\cdot}\rho^{\prime}$ for some path $\pi$ and
run $\rho^{\prime}$, $\pi$ is of the form
$\pi_{1}\boldsymbol{\cdot}\gamma_{1}\boldsymbol{\cdot}\cdots\boldsymbol{\cdot}\pi_{m}\boldsymbol{\cdot}\gamma_{m}$,
and the following conditions are satisfied

  * $\triangleright$

$\gamma_{i}\in G_{1}$ for all $i:1\leq i\leq m$.

  * $\triangleright$

$\pi[i]\not\in G_{2}$ for all $i:0\leq i\leq\left|{\pi}\right|$.

In other words $\rho$ visits the set $G_{1}$ at least $m$ times before
visiting $G_{2}$ for the first time. We usually write ${\tt Before}$ instead
of $\,{\tt Before}^{1}\,$, and write $\gamma\,{\tt Before}^{k}\,G$ instead of
$\left\\{\gamma\right\\}\,{\tt Before}^{k}\,G$. Define the set ${\mathcal{A}}$
of small configurations from which $\mathsf{l}$ is reachable.

${\mathcal{A}}:=\Gamma^{\tt
small}_{{\mathcal{P}}}\cap(\gamma\models_{{\mathcal{P}}}\exists\Diamond\mathsf{l}))$

Consider a $\mu$ satisfying (well defined since ${\mathcal{A}}$ is finite),

$0<\mu\leq\min_{\gamma\in{\mathcal{A}}}{\it
Prob}_{{\mathcal{P}}}\left(\gamma\models\bigcirc(\mathsf{l}\,{\tt
Before}\,\gamma)\right).$

This means that $\mu$ is a lower bound on the measure of runs that start from
some configuration in $\gamma\in{\mathcal{A}}$ and visit $\mathsf{l}$ before
visiting $\gamma$.

###### Lemma 0.D.12

${\it Prob}_{{\mathcal{P}}}\left(\gamma\models\gamma\,{\tt
Before}^{m}\,\mathsf{l}\right)\leq(1-\mu)^{m-1}$ for each
$\gamma\in{\mathcal{A}}$.

###### Proof

By induction on $m$. The base case, when $m=1$ is trivial.

For the induction step, we observe that, by definition, we have

$\begin{array}[]{l}{\it Prob}_{{\mathcal{P}}}\left(\gamma\models\gamma\,{\tt
Before}^{2}\,\mathsf{l}\right)={\it
Prob}_{{\mathcal{P}}}\left(\gamma\models\bigcirc(\gamma\,{\tt
Before}\,\mathsf{l})\right)\leq(1-\mu)\end{array}$

By the induction hypothesis we know that

$\begin{array}[]{l}{\it Prob}_{{\mathcal{P}}}\left(\gamma\models\gamma\,{\tt
Before}^{m-1}\,\mathsf{l}\right)\leq(1-\mu)^{m-2}\end{array}$

We obtain

$\begin{array}[]{rl}{\it Prob}_{{\mathcal{P}}}\left(\gamma\models\gamma\,{\tt
Before}^{m}\,\mathsf{l}\right)&={\it
Prob}_{{\mathcal{P}}}\left(\gamma\models\gamma\,{\tt
Before}^{2}\,\mathsf{l}\right)\cdot{\it
Prob}_{{\mathcal{P}}}\left(\gamma\models\gamma\,{\tt
Before}^{m-2}\,\mathsf{l}\right)\\\
&\leq(1-\mu)\cdot(1-\mu)^{m-2}=(1-\mu)^{m-1}\end{array}$

We now recall and give the proof of Lemma 10. See 10

###### Proof

There are two possible cases: (i) $\gamma\in\Gamma^{\tt
small}_{{\mathcal{P}}}-{\mathcal{A}}$. From the definitions, it follows that
$\sum_{m=\lfloor\frac{n}{\nu}\rfloor+1}^{n}{\it
Prob}_{{\mathcal{P}}}\left(\gamma\models_{{\mathcal{P}}}\Diamond^{\\!\\!=n}\mathsf{l}\land{\tt
Visit}_{{\mathcal{P}}}\left(n,m\right)\right)=0$. (ii)
$\gamma\in{\mathcal{A}}$. We analyze this case below.

For any $m$ we have that

$\begin{array}[]{l}{\it Prob}_{{\mathcal{P}}}\left({\tt
DRuns}\left(\gamma\right)\left(\mathsf{l}\right)\left(n\right)\right)\\\
=\sum_{m=\lfloor\frac{n}{\nu}\rfloor+1}^{n}{\it
Prob}_{{\mathcal{P}}}\left(\gamma\models_{{\mathcal{P}}}\Diamond^{\\!\\!=n}\mathsf{l}\land{\tt
Visit}_{{\mathcal{P}}}\left(n,m\right)\right)\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Definition
of F-Runs}\right\\}}\\\ \leq\sum_{m=\lfloor\frac{n}{\nu}\rfloor+1}^{n}{\it
Prob}_{{\mathcal{P}}}\left(\gamma\models{\mathcal{A}}\,{\tt
Before}^{m}\,\mathsf{l}\right)\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Definitions
of $\Diamond^{\\!\\!m}$, ${\tt Visit}$, and ${\tt Before}$}\right\\}\par}\\\
\leq\sum_{m=\lfloor\frac{n}{\nu}\rfloor+1}^{n}\sum_{\gamma^{\prime}\in{\mathcal{A}}}{\it
Prob}_{{\mathcal{P}}}\left(\gamma\models\gamma^{\prime}\,{\tt
Before}^{\left\lceil\frac{m}{\left|{{\mathcal{A}}}\right|}\right\rceil}\,\mathsf{l}\right)\\\
\qquad\qquad\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Finiteness
of ${\mathcal{A}}$ and pigeonhole principle}\right\\}}\\\
\leq\sum_{m=\lfloor\frac{n}{\nu}\rfloor+1}^{n}\sum_{\gamma^{\prime}\in{\mathcal{A}}}{\it
Prob}_{{\mathcal{P}}}\left(\gamma\models\gamma^{\prime}\,{\tt
Before}\,\mathsf{l}\right)\cdot{\it
Prob}_{{\mathcal{P}}}\left(\gamma^{\prime}\models\gamma^{\prime}\,{\tt
Before}^{\left\lceil\frac{m}{\left|{{\mathcal{A}}}\right|}\right\rceil}\,\mathsf{l}\right)\\\
\qquad\qquad\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Definition
of ${\tt Before}$}\right\\}}\\\
\leq\sum_{m=\lfloor\frac{n}{\nu}\rfloor+1}^{n}\sum_{\gamma^{\prime}\in{\mathcal{A}}}{\it
Prob}_{{\mathcal{P}}}\left(\gamma^{\prime}\models\gamma^{\prime}\,{\tt
Before}^{\left\lceil\frac{m}{\left|{{\mathcal{A}}}\right|}\right\rceil}\,\mathsf{l}\right)\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{${\it
Prob}_{{\mathcal{P}}}\left(\cdot\right)\leq 1$}\right\\}\par}\\\
\leq\sum_{m=\lfloor\frac{n}{\nu}\rfloor+1}^{n}\sum_{\gamma^{\prime}\in{\mathcal{A}}}(1-\mu)^{\left\lceil\frac{m}{\left|{{\mathcal{A}}}\right|}\right\rceil-1}\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Lemma~{}\ref{aaset:measure:lemma}}\right\\}\par}\\\
\leq\sum_{m=\lfloor\frac{n}{\nu}\rfloor+1}^{n}\sum_{\gamma^{\prime}\in{\mathcal{A}}}(1-\mu)^{\frac{m}{\left|{{\mathcal{A}}}\right|}}\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Algebra}\right\\}}\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{=}\;\left\\{\mbox{Algebra}\right\\}}\\\
\leq\frac{\left|{{\mathcal{A}}}\right|}{1-\mu}\cdot\sum_{m=\lfloor\frac{n}{\nu}\rfloor+1}^{n}(1-\mu)^{\frac{m}{\left|{{\mathcal{A}}}\right|}}\\\
=\frac{\left|{{\mathcal{A}}}\right|}{1-\mu}\cdot\frac{(1-\mu)^{\frac{\left\lfloor\frac{n}{\nu}\right\rfloor+1}{\left|{{\mathcal{A}}}\right|}}-(1-\mu)^{\frac{n+1}{\left|{{\mathcal{A}}}\right|}}}{1-(1-\mu)^{\frac{1}{\left|{{\mathcal{A}}}\right|}}}\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Algebra}\right\\}}\\\
\leq\frac{\left|{{\mathcal{A}}}\right|}{1-\mu}\cdot\frac{(1-\mu)^{\frac{n}{\nu\cdot\left|{{\mathcal{A}}}\right|}}-(1-\mu)^{\frac{n+1}{\left|{{\mathcal{A}}}\right|}}}{1-(1-\mu)^{\frac{1}{\left|{{\mathcal{A}}}\right|}}}\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Algebra}\right\\}}\\\
=\frac{\left|{{\mathcal{A}}}\right|}{1-\mu}\cdot\frac{(1-\mu)^{\frac{n}{\nu\cdot\left|{{\mathcal{A}}}\right|}}}{1-(1-\mu)^{\frac{1}{\left|{{\mathcal{A}}}\right|}}}\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Algebra}\right\\}\par}\\\
=\frac{\left|{{\mathcal{A}}}\right|}{(1-\mu)\cdot\left(1-(1-\mu)^{\frac{1}{\left|{{\mathcal{A}}}\right|}}\right)}\cdot\left((1-\mu)^{\frac{1}{\nu\cdot\left|{{\mathcal{A}}}\right|}}\right)^{n}\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Algebra}\right\\}}\\\
=\left({\mathcal{E}}^{\tt
D}_{{\mathcal{P}}}\right)^{n}\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Definition}\right\\}}\end{array}$

###  0.D.4 Eagerness: Existence and Computability

The results from 0.D.3 give us all the ingredients that were necessary to
proof Lemma 7. We briefly discussed the proof idea for this lemma in the main
paper. We give here the proof with full details.

See 7

##### Existence

We start off by showing the existence of ${\mathcal{E}}_{{\mathcal{P}}}$ and
$\eta_{{\mathcal{P}}}$.

###### Proof

For values ${\mathcal{E}}^{\tt S}_{{\mathcal{P}}},{\mathcal{E}}^{\tt
D}_{{\mathcal{P}}}<1$, we have,

$\begin{array}[]{rl}&\text{For }~{}n\geq
300:~{}~{}\sum\limits_{m=1}^{\left\lfloor\frac{n}{\nu}\right\rfloor}{\it
Prob}_{{\mathcal{P}}}\left(\gamma\models_{{\mathcal{P}}}\Diamond^{\\!\\!=n}\mathsf{l}\land{\tt
Visit}_{{\mathcal{P}}}\left(n,m\right)\right)\leq({\mathcal{E}}^{\tt
S}_{{\mathcal{P}}})^{n}\qquad\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Lemma
\ref{sruns:lemma}}\right\\}}\\\\[5.69046pt] &\text{For }~{}n\geq\eta^{\tt
D}_{{\mathcal{P}}}:~{}~{}\sum\limits_{m=\left\lfloor\frac{n}{\nu}\right\rfloor}^{n}{\it
Prob}_{{\mathcal{P}}}\left(\gamma\models_{{\mathcal{P}}}\Diamond^{\\!\\!=n}\mathsf{l}\land{\tt
Visit}_{{\mathcal{P}}}\left(n,m\right)\right)\leq({\mathcal{E}}^{\tt
D}_{{\mathcal{P}}})^{n}\qquad\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Lemma
\ref{druns:lemma}}\right\\}}\end{array}$

Choose (exists since ${\mathcal{E}}^{\tt S}_{{\mathcal{P}}},{\mathcal{E}}^{\tt
D}_{{\mathcal{P}}}<1$) a value ${\mathcal{E}}^{\tt SD}_{{\mathcal{P}}}$ such
that, $\max({\mathcal{E}}^{\tt S}_{{\mathcal{P}}},{\mathcal{E}}^{\tt
D}_{{\mathcal{P}}})<{\mathcal{E}}^{\tt SD}_{{\mathcal{P}}}<1$. It follows that
for some value $\eta^{1}$, ${\it
Prob}_{{\mathcal{P}}}\left(\gamma\models_{{\mathcal{P}}}\Diamond^{\\!\\!=n}\mathsf{l}\right)\leq({\mathcal{E}}^{\tt
SD}_{{\mathcal{P}}})^{n}$ for all $n\geq\eta^{1}$. Define $\eta^{\tt
SD}_{{\mathcal{P}}}=\max(\eta^{\tt D}_{{\mathcal{P}}},300,\eta^{1})$. From the
earlier two results, we get the following,

$\text{For }~{}n\geq\eta^{\tt SD}_{{\mathcal{P}}}:~{}~{}{\it
Prob}_{{\mathcal{P}}}\left(\gamma\models_{{\mathcal{P}}}\Diamond^{\\!\\!=n}\mathsf{l}\right)\leq\left({\mathcal{E}}^{\tt
SD}_{{\mathcal{P}}}\right)^{n}$

The final step is to extend the argument to the set of $\gamma$-runs that
reach $\mathsf{l}$ in $n$ or more steps (as required by Lemma 7).

$\begin{array}[]{l}{\it
Prob}_{{\mathcal{P}}}\left(\gamma\models_{{\mathcal{P}}}\Diamond^{\\!\\!\geq
n}\mathsf{l}\right)=\sum_{k=n}^{\infty}{\it
Prob}_{{\mathcal{P}}}\left(\gamma\models_{{\mathcal{P}}}\Diamond^{\\!\\!=n}\mathsf{l}\right)\leq\sum_{k=n}^{\infty}\left({\mathcal{E}}^{\tt
SD}_{{\mathcal{P}}}\right)^{k}=\frac{\left({\mathcal{E}}^{\tt
SD}_{{\mathcal{P}}}\right)^{n}}{1-{\mathcal{E}}^{\tt
SD}_{{\mathcal{P}}}}\end{array}$

Choose (exists since ${\mathcal{E}}^{\tt SD}_{{\mathcal{P}}}<1$)
${\mathcal{E}}^{\tt SD}_{{\mathcal{P}}}<{\mathcal{E}}_{{\mathcal{P}}}<1$.
There exists an $\eta_{{\mathcal{P}}}\geq\eta^{\tt SD}_{{\mathcal{P}}}$ such
that $\frac{\left({\mathcal{E}}^{\tt
SD}_{{\mathcal{P}}}\right)^{n}}{1-{\mathcal{E}}^{\tt
SD}_{{\mathcal{P}}}}\leq\left({\mathcal{E}}_{{\mathcal{P}}}\right)^{n}$ for
all $n\geq\eta_{{\mathcal{P}}}$, and hence we have,

$\text{For }~{}n\geq\eta_{{\mathcal{P}}}:~{}~{}{\it
Prob}_{{\mathcal{P}}}\left(\gamma\models_{{\mathcal{P}}}\Diamond^{\\!\\!\geq
n}\mathsf{l}\right)\geq\left({\mathcal{E}}_{{\mathcal{P}}}\right)^{n}$

This gives us the result.

##### Computability

Now we show that computatbility of these terms. We proceed systematically
along the dependencies and illustrate how each term can be computed, not just
for our model but for arbitrary models.

###### Proof

  * $\triangleright$

$\hat{q}:=\min_{\gamma\in\Gamma_{{\mathcal{P}}}^{=5}}\sum\limits_{\gamma^{\prime}\in\Gamma^{\tt
small}_{{\mathcal{P}}}}{\tt
M}_{{\mathcal{P}}}\left(\gamma,\gamma^{\prime}\right)$. Computable since the
sets $\Gamma_{{\mathcal{P}}}^{=4}$ and $\Gamma_{{\mathcal{P}}}^{\leq 3}$ are
finite, and for any two configurations $\gamma,\gamma^{\prime}\in\Gamma$, we
can compute ${\tt M}_{{\mathcal{P}}}\left(\gamma,\gamma^{\prime}\right)$. In
fact, for us, this has the constant value of $2/3$.

  * $\triangleright$

$\hat{p}:=1-\hat{q}$. Computable since $\hat{q}$ is computable.

  * $\triangleright$

${\mathcal{E}}_{{\mathcal{P}}}:=2\sqrt{\hat{p}\cdot\hat{q}}$. Computable since
$\hat{q}$ and $\hat{p}$ are computable.

  * $\triangleright$

${\mathcal{A}}$ is computable since ${\mathcal{A}}=\Gamma^{\tt
small}_{{\mathcal{P}}}\cap\\{\rho\in{\tt
Runs}\left(\gamma\right)~{}|~{}\rho\models_{{\mathcal{P}}}\exists\Diamond\mathsf{l}))$,
the set $\Gamma^{\tt small}_{{\mathcal{P}}}$ is finite (and explicitly given),
and the property $\gamma\models_{{\mathcal{P}}}\exists\Diamond\mathsf{l}$ is
decidable by Lemma 4.

  * $\triangleright$

Compute $\nu$ such that

$\left(\frac{\nu}{\nu-1}\right)(2\cdot\nu)^{\frac{1}{\nu}}\cdot\left(\frac{1}{\nu}+\frac{1}{{\mathcal{G}}_{{\mathcal{P}}}}\right)^{\lfloor\frac{1}{\nu}\rfloor}\cdot{\mathcal{G}}_{{\mathcal{P}}}\leq
1$

This is possible since the function is monotone and its limit approaches
${\mathcal{G}}_{{\mathcal{P}}}<1$, i.e.,

$\lim_{\nu\rightarrow\infty}\left(\frac{\nu}{\nu-1}\right)(2\cdot\nu)^{\frac{1}{\nu}}\cdot\left(\frac{1}{\nu}+\frac{1}{{\mathcal{G}}_{{\mathcal{P}}}}\right)^{\lfloor\frac{1}{\nu}\rfloor}\cdot{\mathcal{G}}_{{\mathcal{P}}}={\mathcal{G}}_{{\mathcal{P}}}<1$

  * $\triangleright$

Define

${\mathcal{E}}^{1}_{{\mathcal{P}}}:=\left(\frac{\nu}{\nu-1}\right)(2\cdot\nu)^{\frac{1}{\nu}}\cdot\left(\frac{1}{\nu}+\frac{1}{{\mathcal{G}}_{{\mathcal{P}}}}\right)^{\lfloor\frac{1}{\nu}\rfloor}\cdot{\mathcal{G}}_{{\mathcal{P}}}$

This is possible since both ${\mathcal{G}}_{{\mathcal{P}}}$ and $\nu$ are
computable. In fact for our model, the constant value of $\nu=150$ suffices.

  * $\triangleright$

We can find a $\mu$ such that $0<\mu\leq\min_{\gamma\in{\mathcal{A}}}{\it
Prob}_{{\mathcal{P}}}\left(\gamma\models\bigcirc(\mathsf{l}\,{\tt
Before}\,\gamma)\right)$, using the following procedure. We explore the paths
that start from $\gamma$ in a breadth-first manner, until we find a path $\pi$
that end with $\mathsf{l}$. Such a $\pi$ exists since
$\gamma\models\exists\Diamond\mathsf{l}$ holds by assumption. We define $\mu$
to be the probability of $\pi$.

  * $\triangleright$

Define ${\mathcal{E}}^{2}_{{\mathcal{P}}}$ such that
$(1-\mu)^{\frac{1}{\nu\cdot\left|{{\mathcal{A}}}\right|}}<{\mathcal{E}}^{2}_{{\mathcal{P}}}<1$.
We can compute ${\mathcal{E}}^{2}_{{\mathcal{P}}}$ since $\nu$,
${\mathcal{A}}$, $\mu$ are computable. Since
$(1-\mu)^{\frac{1}{\nu\cdot\left|{{\mathcal{A}}}\right|}}<{\mathcal{E}}^{{\mathcal{P}}}_{2}$
it follows that there is a natural number, which we denote by
$\eta_{{\mathcal{P}}}^{2}$ such that
$({\mathcal{E}}^{2}_{{\mathcal{P}}})^{n}\leq\frac{\left|{{\mathcal{A}}}\right|}{(1-\mu)\cdot
1-(1-\mu)^{\frac{1}{\left|{{\mathcal{A}}}\right|}}}\cdot\left((1-\mu)^{\frac{1}{\nu\cdot\left|{{\mathcal{A}}}\right|}}\right)^{n}$
for all $n\geq\eta_{{\mathcal{P}}}^{2}$.

  * $\triangleright$

Define ${\mathcal{E}}_{{\mathcal{P}}}$ such that
$\max({\mathcal{E}}^{1}_{{\mathcal{P}}},{\mathcal{E}}^{2}_{{\mathcal{P}}})<{\mathcal{E}}_{{\mathcal{P}}}<1$.
It follows that there is a natural number, which we denote by
$\eta_{{\mathcal{P}}}$ such that
$({\mathcal{E}}_{{\mathcal{P}}})^{n}<\left(\max({\mathcal{E}}^{1}_{{\mathcal{P}}},{\mathcal{E}}^{2}_{{\mathcal{P}}})\right)^{n}$
, for all $n\geq\eta_{{\mathcal{P}}}$.

This concludes the proof of computatbility and hence gives us Lemma 7.

###  0.D.5 Proving the invariants

We now prove Lemma 11 that states the validity of the invariants.

See 11

The invariants (1), (2), (5), and (6) follow directly from the definitions.
Below, we show Invariant (3) and (4).

Invariant (3): Let
${\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}k}=\tt
MaxCost\left({\tt Cost}\right)$.

$\begin{array}[]{l}E\left(X_{\gamma,\mathsf{l},{\tt
Cost}}\right)-{\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}{\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}\tt
CostApprx}^{(n)}}\\\ =\sum_{i=0}^{\infty}\sum\limits_{\rho\in\\{\rho\in{\tt
Runs}\left(\gamma_{\it
init}\right)|\rho\models\Diamond^{\\!\\!=i}\mathsf{l}\\}}{\tt
Cost}\left(\rho\right)\cdot{\it
Prob}_{{\mathcal{P}}}\left(\rho\right)-{\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}{\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}\tt
CostApprx}^{(n)}}\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Definition}\right\\}}\\\
=\sum_{i=0}^{\infty}\sum\limits_{\rho\in\\{\rho\in{\tt Runs}\left(\gamma_{\it
init}\right)|\rho\models\Diamond^{\\!\\!=i}\mathsf{l}\\}}{\tt
Cost}\left(\rho\right)\cdot{\it
Prob}_{{\mathcal{P}}}\left(\rho\right)-\sum_{i=0}^{n}\sum\limits_{\rho\in\\{\rho\in{\tt
Runs}\left(\gamma_{\it
init}\right)|\rho\models\Diamond^{\\!\\!=i}\mathsf{l}\\}}{\tt
Cost}\left(\rho\right)\cdot{\it Prob}_{{\mathcal{P}}}\left(\rho\right)\\\
\qquad\qquad\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Invariant~{}\ref{costapprx:invariant}}\right\\}}\\\
\leq{\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}k}\cdot\sum\limits_{i=0}^{\infty}i\cdot\sum\limits_{\rho\in\\{\rho\in{\tt
Runs}\left(\gamma_{\it
init}\right)|\rho\models\Diamond^{\\!\\!=i}\mathsf{l}\\}}{\it
Prob}_{{\mathcal{P}}}\left(\rho\right)-{\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}k}\cdot\sum\limits_{i=0}^{n}i\cdot\sum\limits_{\rho\in\\{\rho\in{\tt
Runs}\left(\gamma_{\it
init}\right)|\rho\models\Diamond^{\\!\\!=i}\mathsf{l}\\}}{\it
Prob}_{{\mathcal{P}}}\left(\gamma_{\it
init}\models\Diamond^{\\!\\!=i}\mathsf{l}\right)\\\
\qquad\qquad\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\rho\models\Diamond^{\\!\\!=i}\implies{\tt
Cost}\left(\rho\right)\leq{\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}k}\cdot
i\right\\}}\\\
\leq{\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}k}\cdot\sum\limits_{i=n}^{\infty}i\cdot{\it
Prob}_{{\mathcal{P}}}\left(\gamma_{\it
init}\models\Diamond^{\\!\\!=i}\mathsf{l}\right)\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Algebra}\right\\}}\\\
\leq{\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}k}\cdot\sum\limits_{i=n}^{\infty}i\cdot{\mathcal{E}}_{{\mathcal{P}}}^{i}\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Lemma~{}\ref{eagerness:lemma}
and $n\geq\eta_{{\mathcal{P}}}$}\right\\}}\\\
\leq{\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}k}\cdot\frac{{\mathcal{E}}_{{\mathcal{P}}}^{n}}{(1-{\mathcal{E}}_{{\mathcal{P}}})^{2}}\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{{\mathcal{E}}_{{\mathcal{P}}}<1\right\\}}\\\
={\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}{\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}\tt
CostError}^{(n)}}\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Invariant~{}\ref{cerror:invariant}}\right\\}}\end{array}$

Invariant (4):

$\begin{array}[]{l}{\it
Prob}_{{\mathcal{P}}}\left(\pi\right)-{\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}{\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}\tt
ProbApprx}^{(n)}}\\\ =\sum_{i=0}^{\infty}\sum\limits_{\rho\in\\{\rho\in{\tt
Runs}\left(\gamma_{\it
init}\right)|\rho\models\Diamond^{\\!\\!=i}\mathsf{l}\\}}{\it
Prob}_{{\mathcal{P}}}\left(\rho\right)-{\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}{\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}\tt
ProbApprx}^{(n)}}\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{By
definition}\right\\}}\\\ =\sum_{i=0}^{\infty}{\it
Prob}_{{\mathcal{P}}}\left(\gamma_{\it
init}\models\Diamond^{\\!\\!=i}\mathsf{l}\right)-\sum_{i=0}^{n}{\it
Prob}_{{\mathcal{P}}}\left(\gamma_{\it
init}\models\Diamond^{\\!\\!=i}\mathsf{l}\right)\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Invariant~{}\ref{probapprx:invariant}}\right\\}}\\\
=\sum_{i=n}^{\infty}{\it Prob}_{{\mathcal{P}}}\left(\gamma_{\it
init}\models\Diamond^{\\!\\!=i}\mathsf{l}\right)\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Algebra}\right\\}}\\\
\leq\sum_{i=n}^{\infty}{\mathcal{E}}_{{\mathcal{P}}}^{i}\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Lemma~{}\ref{eagerness:lemma}}\right\\}}\\\
\leq\frac{{\mathcal{E}}_{{\mathcal{P}}}^{n}}{1-{\mathcal{E}}_{{\mathcal{P}}}}\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{{\mathcal{E}}_{{\mathcal{P}}}<1\right\\}}\\\
={\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}{\color[rgb]{0.140625,0.109375,0.890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.140625,0.109375,0.890625}\tt
ProbError}^{(n)}}\;{\color[rgb]{0.6640625,0.359375,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{0.6640625,0.359375,0.40625}{}\;\left\\{\mbox{Invariant~{}\ref{perror:invariant}}\right\\}}\end{array}$


# Magnitude and Topological Entropy of Digraphs

Steve Huntsman STR
Arlington, Virginia<EMAIL_ADDRESS>
###### Abstract

Magnitude and (co)weightings are quite general constructions in enriched
categories, yet they have been developed almost exclusively in the context of
Lawvere metric spaces. We construct a meaningful notion of magnitude for flow
graphs based on the observation that topological entropy provides a suitable
map into the max-plus semiring, and we outline its utility. Subsequently, we
identify a separate point of contact between magnitude and topological entropy
in digraphs that yields an analogue of volume entropy for geodesic flows.
Finally, we sketch the utility of this construction for feature engineering in
downstream applications with generic digraphs.

##  1 Introduction

Let $\mathbf{M}=(\mathbf{M},\otimes,1)$ be a monoidal category (for
background, see [27, 11]) and $\mathbf{C}$ a (small) $\mathbf{M}$-category,
i.e., a (small) category enriched over $\mathbf{M}$. Recall that this means
that $\mathbf{C}$ is specified by a set $\text{Ob}(\mathbf{C})$; hom-objects
$\mathbf{C}(j,k)\in\mathbf{M}$ for all $j,k\in\text{Ob}(\mathbf{C})$; identity
morphisms $1\rightarrow\mathbf{C}(j,j)$ for all $j\in\text{Ob}(\mathbf{C})$;
and composition morphisms
$\mathbf{C}(j,k)\otimes\mathbf{C}(k,\ell)\rightarrow\mathbf{C}(j,\ell)$ for
all $j,k,\ell\in\text{Ob}(\mathbf{C})$; moreover, these hom-objects and
morphisms are required to satisfy associativity and unitality properties [20,
11].

The theory of magnitude [25, 24] incorporates a $\mathbf{M}$-category
$\mathbf{C}$ and a semiring $S$ via a “size” map
$\sigma:\text{Ob}(\mathbf{M})\rightarrow S$ that is constant on isomorphism
classes and that satisfies $\sigma(1)=1$ and $\sigma(X\otimes
Y)=\sigma(X)\cdot\sigma(Y)$, where the semiring unit and multiplication are
indicated on the right-hand sides. If $n:=|\text{Ob}(\mathbf{C})|<\infty$ then
its _similarity matrix_ $Z\in M(n,S)$ has entries
$Z_{\\_}{jk}:=\sigma(\mathbf{C}(j,k))$. Introducing the (common) notation

$(f[X])_{\\_}{jk}:=f(X_{\\_}{jk})$

as a shorthand where $X$ is a matrix over the semiring $S$ and $f$ is a
function on $S$, we have $Z:=\sigma[\mathbf{C}]$.

A _weighting_ is a column vector $w$ satisfying $Zw=1$, where the semiring
matrix multiplication and column vector of ones are indicated. A _coweighting_
is the transpose of a weighting for $Z^{T}$. If $Z$ has a weighting and a
coweighting, its _magnitude_ is the sum of the components of either one of
these: a line of algebra shows these sums necessarily coincide.

The notion of magnitude has been the subject of increasing attention over the
past 15 years, and over the last year or so applications have begun to emerge
based on boundary-detecting properties of (co)weightings in the setting of
metric spaces [3, 17], which is virtually the only case that has been explored
to date. 111 The only exception of which we are aware is [7], which details a
nontrivial example of magnitude for a certain Vect-category; see also Example
6.4.5 of [24].  This setting emerges from the choice
$\mathbf{M}=(([0,\infty],\geq),+,0)$, which with only a very mild continuity
assumption requires $\sigma(x)=\exp(-tx)$ for some constant $t$; varying this
constant leads to the notion of a _magnitude function_. The corresponding
enriched categories are precisely the _Lawvere metric spaces_ , also known as
_extended quasipseudometric spaces_ since they generalize metric spaces by
allowing distances that are infinite (extended), asymmetric (quasi-), or zero
(pseudo-). In §2 we will show that seemingly adjacent monoidal structures on
$([0,\infty],\geq)$ in fact lead to the same construction, so to move away
from the generalized metric space setting at all, it is necessary to move
quite far indeed.

However, there are other interesting monoidal categories that yield applicable
instantiations of magnitude, though §2 shows that these must necessarily give
rise to something quite different from metric spaces. In §3, we introduce such
a construction via a monoidal category $\mathbf{Flow}$ of _flow graphs_ that
informs the analysis of computer programs (and also, e.g., business
processes), encompassing constructs that represent the transfer of control and
data [8, 32] as in Figure 1. This category has two monoidal products that
model “series” and “conditional” (versus “parallel” _per se_) execution of
programs as well as the structure of an operad in $\mathbf{Set}$ [16] that
dovetails with a hierarchical representation of input/output structure [18].

For each generic flow graph $D$, there is a $\mathbf{Flow}$-category described
in Lemma 1. The _topological entropy_ of hom-objects in this category provides
a suitable map $\sigma$ into the max-plus semiring, and the resulting
weighting (resp., coweighting) indicate sub-flow graphs of maximal entropy in
the “forward direction” (resp., “reverse direction”). These constructions are
attractive from the point of view of feature engineering for graph matching
[10] and machine learning problems involving flow graphs.

Meanwhile, once we consider interactions between magnitude and topological
entropy in the setting of digraphs, another point of contact is readily
discernible, and we discuss it in §4. The magnitude function of a ball in the
universal cover of a strong loopless digraph is closely related to the
topological entropy of the digraph. In §5 we provide evidence of the utility
for feature engineering based on this observation in problems involving
generic digraphs.

##  2 Rigidity of similarity matrix arithmetic

Here we show that there is even less choice in how the theory of magnitude can
be applied to metric spaces and their ilk than §2.3 of [25] suggests, wherein
the usual addition operation on $([0,\infty],\geq)$ is chosen for the monoidal
structure. This rigidity illustrates that meaningful notions of magnitude
outside its usual arena are likely to involve very different monoidal
structures and/or categories.

######  Proposition 1.

Let $f$ be a strictly increasing bijection from $[0,\infty]$ to a subset of
$[-\infty,\infty]$ containing $0$. Then $x\otimes y:=f^{-1}(f(x)+f(y))$ gives
rise to a strict symmetric monoidal structure on $([0,\infty],\geq)$ with
monoidal (additive) unit $f^{-1}(0)$. ∎

A category $\mathbf{C}$ enriched over the strict symmetric monoidal category
above has, for every $j,k\in\text{Ob}(\mathbf{C})$, some
$\eta_{\\_}{jk}:=\mathbf{C}(j,k)\in[0,\infty]$ such that
$\eta_{\\_}{jj}=f^{-1}(0)$ and
$\eta_{\\_}{jk}\otimes\eta_{\\_}{k\ell}\geq\eta_{\\_}{j\ell}$. That is, we
have the triangle inequality $f(\eta_{\\_}{jk})+f(\eta_{\\_}{k\ell})\geq
f(\eta_{\\_}{j\ell})$. Let us therefore assume $f[\eta]=d$, and furthermore
stipulate that we want our similarity matrix $Z$ to take values in the
semiring $\mathbb{R}$ with the usual structure, as opposed to some more exotic
choice. Then we require a function $\sigma:[0,\infty]\rightarrow\mathbb{R}$
such that $\sigma(x\otimes y)=\sigma(x)\cdot\sigma(y)$ in order to define
$Z:=\sigma[\eta]$. If we require continuity, then this generalized Cauchy
equation has the unique family of solutions $\sigma(x)=\exp(-\tau f(x))$ for
$\tau\in\mathbb{R}$. Now $Z=\sigma[\eta]=\sigma[f^{-1}[d]]=\exp[-\tau d]$,
just as usual: i.e., this attempted generalization actually has no material
effect.

What about a more exotic semiring structure on $\mathbb{R}$? The proposition
above has a close analogue:

######  Proposition 2.

Let $g$ be a strictly increasing function from $[-\infty,\infty]$ to itself,
and taking on the value $0$ (and also $1$ for the final part of the
statement). Then $x\oplus y:=g^{-1}(g(x)+g(y))$ gives rise to a strict
symmetric monoidal structure on $([-\infty,\infty],\geq)$ with monoidal
(additive) unit $g^{-1}(0)$. Moreover, additionally taking $x\odot
y:=g^{-1}(g(x)\cdot g(y))$ gives a semiring with multiplicative unit
$g^{-1}(1)$. 222 We thank S. Tringali for this observation. If
$g(x):=\text{sgn}(x)\cdot|x|^{p}$ for $p>0$, we get the semiring
$([-\infty,\infty],\oplus,0,\cdot,1)$. If $g(x):=\exp(-\tau x)$ for $\tau<0$,
then we get the semiring $([-\infty,\infty],\oplus,-\infty,+,0)$.  ∎

Now the equation for a weighting is $\bigoplus_{\\_}k(Z_{\\_}{jk}\odot
w_{\\_}k)=g^{-1}(1)$, which unpacks to the matrix equation $g[Z]g[w]=1$ in
ordinary arithmetic. Recalling that $Z=\sigma[\eta]$ and $f[\eta]=d$, we have
$Z=\sigma[f^{-1}[d]]$. Meanwhile, we have the generalized Cauchy equation
$\sigma(x\otimes y)=\sigma(x)\odot\sigma(y)$, which unpacks to

$\sigma(f^{-1}(f(x)+f(y)))=g^{-1}(g(\sigma(x))\cdot g(\sigma(y))).$ (1)

Defining $h:=g\circ\sigma\circ f^{-1}$, this becomes
$h(f(x)+f(y))=h(f(x))\cdot h(f(y))$, i.e., $h$ satisfies the usual Cauchy
equation; assuming continuity, we have $h[d]=\exp[-\tau d]$. Since
$g[Z]=h[d]$, the weighting equation is $h[d]g[w]=1$, which apart from the
transformation of $w$ is the same as in ordinary arithmetic.

In short, it appears to be at least difficult–perhaps impossible–to get
substantially different arithmetic of similarity matrices than the “default”
while still working over the extended real numbers, regardless of which
underlying arithmetic we use. The thin silver lining is that we can
legitimately apply a very broad class of componentwise transformations to a
(co)weighting and still interpret the result as a (co)weighting also, albeit
with respect to a different underlying semiring structure.

Nevertheless, the notion of magnitude still affords useful application to
quite different monoidal categories; in the sequel, we give an example.

##  3 Max-plus magnitude for flow graphs

Throughout this paper, by _digraph_ we mean the usual notion in combinatorics.
In particular, we do not allow multiple edges between vertices (i.e., a quiver
is generally not a digraph _per se_). See footnote 3.

Consider the specific notion of _flow graph_ discussed in [16], viz. a digraph
$D$ with exactly one source and exactly one target, such that there is a
unique (entry) edge from the source and a unique (exit) edge to the target,
and such that identifying the source of the entry edge with the target of the
exit edge yields a strong digraph (i.e., a digraph in which every two vertices
are connected by some path). An example is the digraph in the right panel of
Figure 1.

[0 ] START repeat repeat repeat if b goto 7 if b repeat S until b endif until
b do while b do while b repeat S until b enddo enddo until b until b HALT

Figure 1:  (L) A simple imperative program. S denotes a generic statement (or
subroutine); b denotes a generic Boolean predicate. (R) The corresponding
control flow graph: branches are shaded black (resp., gray) if the
corresponding b evaluates to
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\top}$
or
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
Let ${\bf Flow}$ be the full subcategory of reflexive digraphs 333 An object
in the category $\mathbf{Dgph}$ of reflexive digraphs is
$G=(U,\alpha,\omega)$, where $U$ is a set and $\alpha,\omega:U\rightarrow U$
are _head_ and _tail_ functions that satisfy $\alpha\circ\omega=\omega$ and
$\omega\circ\alpha=\alpha$. For
$G^{\prime}=(U^{\prime},\alpha^{\prime},\omega^{\prime})$, a morphism
$f\in{\bf Dgph}(G,G^{\prime})$ is a function $f:U\rightarrow U^{\prime}$ such
that $f\circ\alpha=\alpha^{\prime}\circ f$ and
$f\circ\omega=\omega^{\prime}\circ f$. The _vertices_ of $G=(U,\alpha,\omega)$
are the (mutual) image $V\equiv V(G)$ of $\alpha$ and $\omega$; the _loops_
are the set $L\equiv L(G):=\\{u\in U:\alpha(u)=\omega(u)\\}$ (so that
$V\subseteq L$), and the _edges_ are the set $E\equiv E(G):=U\backslash L$. We
recover the usual notion of a digraph by considering $\alpha\times\omega$ and
its appropriate restrictions on $U^{2}$, $L^{2}$, and $E^{2}$: e.g., we can
abusively write $E=(\alpha\times\omega)(E^{2})$, where the LHS and RHS
respectively refer to usual and reflexive notions of digraph edges. Thus a
morphism $f:U\rightarrow U^{\prime}$ restricts to $f|_{\\_}V:V\rightarrow
V^{\prime}$, $f|_{\\_}L:L\rightarrow L^{\prime}$, and $f|_{\\_}E:E\rightarrow
U^{\prime}$. Since morphisms are only partially specified by their actions on
vertices, defining ${\bf Flow}$ as a full subcategory of $\mathbf{Dgph}$ is
essentially a convention about vertex identification.  whose objects are
(combinatorially realized as) flow graphs. It turns out that there are both
“series” and “parallel” tensor products on ${\bf Flow}$, as well as the
structure of an operad in $\mathbf{Set}$ which has a conceptually and
algorithmically attractive instantiation. We are presently interested in the
“series” tensor product, denoted $\boxtimes$. The idea of $\boxtimes$ is just
to identify the exit edge of its first argument with the entry edge of its
second argument (so unlike the “parallel” tensor product, this does not give
rise to a symmetric monoidal structure). It turns out that this yields (the
monoidal base of) an enriched category, viz. the ${\bf Flow}$-category ${\bf
SubFlow}_{\\_}D$ of sub-flow graphs of a flow graph $D$ (these correspond to
subroutines in the context of program control flow).

######  Lemma 1.

[16] For a flow graph $D$, we can form a category ${\bf SubFlow}_{\\_}D$
enriched over ${\bf Flow}$ as follows:

  * •

$\textnormal{Ob}({\bf SubFlow}_{\\_}D):=E(D)$ (i.e., the objects of ${\bf
SubFlow}_{\\_}D$ are the edges of the digraph $D$); 444Loops and reflexive
self-edges are not included here, though the former may be accommodated
without substantial changes.

  * •

for $e_{\\_}s,e_{\\_}t\in{\bf SubFlow}_{\\_}D$, the hom object ${\bf
SubFlow}_{\\_}D(e_{\\_}s,e_{\\_}t)\in{\bf Flow}$ is the (possibly empty)
induced sub-flow graph of $D$ with entry edge $e_{\\_}s$ and exit edge
$e_{\\_}t$: we denote this by $D\langle e_{\\_}s,e_{\\_}t\rangle$;

  * •

the composition morphism is induced by $\boxtimes$;

  * •

the identity element is determined by the flow graph $e$ with one edge. ∎

A digraph $D$ determines a _(sub)shift of finite type_ , i.e., a dynamical
system on the space of paths in $D$ with an evolution operator that simply
shifts path indices. The corresponding _topological entropy_
$h(D):=\lim_{\\_}{N\uparrow\infty}N^{-1}\log W(D,N)$ measures the growth of
the number $W(D,N)$ of paths in $D$ of length $N$ [21]. A basic result in
symbolic dynamics is that $h(D)$ is given by the logarithm of the spectral
radius of the adjacency matrix of $D$. (If $D$ is strong, the spectral radius
is the Perron eigenvalue $\geq 1$.)

######  Lemma 2.

For $D_{\\_}j\in{\bf Flow}$,

$h(\boxtimes_{\\_}jD_{\\_}j)=\max_{\\_}jh(D_{\\_}j).$ (2)

###### Proof.

To see the $\geq$ direction, consider paths that are confined to whichever
$D_{\\_}j$ has highest topological entropy. For the $\leq$ direction, note
that the number of paths that are not so confined cannot grow at a faster
rate. ∎

######  Remark 1.

In fact more is true: writing $A(D)$ for the adjacency matrix of $D$, we have
via standard Perron-Frobenius theory that (as multisets)

$\textnormal{spec
}A(\boxtimes_{\\_}jD_{\\_}j)=\\{0\\}\cup\bigcup_{\\_}j\textnormal{spec
}A(D_{\\_}j).$

(The zero is due to the first column/last row [using the obvious indexing] of
$A(\boxtimes_{\\_}jD_{\\_}j)$ being identically zero.) Defining the zeta
function $\zeta_{\\_}D(t):=1/\det(I-tA(D))$ [31], we furthermore have that

$\zeta_{\\_}{\boxtimes_{\\_}jD_{\\_}j}=\prod_{\\_}j\zeta_{\\_}{D_{\\_}j}.$

For examples, see Figures 2 and 3.

Figure 2:  Left:
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}D_{\\_}1}\boxtimes{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}D_{\\_}2}$
for two flow graphs
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}D_{\\_}1}$
and
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}D_{\\_}2}$
on 10 vertices. Upper right: spectra $\text{spec}_{\\_}x\subset\mathbb{C}$ of
the adjacency matrices $A(D_{\\_}x)$ for
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}x=1}$,
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}x=2}$, and
$x=12$ with
$D_{\\_}{12}:={\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}D_{\\_}1}\boxtimes{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}D_{\\_}2}$.
Lower right: zeta functions $\zeta_{\\_}{12}$ and
$\zeta_{\\_}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}\cdot\zeta_{\\_}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2}$
with $\zeta_{\\_}x\equiv\zeta_{\\_}{D_{\\_}x}$.

Figure 3:  As in Figure 2, but for two flow graphs
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}D_{\\_}1}$
and
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}D_{\\_}2}$
on 20 vertices.

Recall that $\max$ furnishes a monoidal structure on the poset
$([0,\infty],\geq)$ of extended nonnegative real numbers, and that categories
enriched over this are Lawvere ultrametric spaces [33]. Similarly,
$([-\infty,\infty),\leq,-\infty,\max)$ is a monoidal poset. This is sufficient
data for us to define (following [25]) the _magnitude_ of ${\bf
SubFlow}_{\\_}D$ over the _max-plus or tropical semiring_ [15, 34]. 555 It is
important to distinguish between the magnitude of ${\bf SubFlow}_{\\_}D$ as an
enriched category and the magnitude of $D$ as a digraph with the usual
(asymmetric) notion of distance. Here we are concerned only with the former.

Unpacking the details, we have the similarity matrix

$(Z^{\boxtimes}_{\\_}D)_{\\_}{st}\equiv
Z^{\boxtimes}_{\\_}D(e_{\\_}s,e_{\\_}t):=h(D\langle
e_{\\_}s,e_{\\_}t\rangle).$ (3)

Now if there exist $v$, $w$ satisfying the max-plus matrix (co)weighting
equations

$\max_{\\_}s[v_{\\_}s+(Z^{\boxtimes}_{\\_}D)_{\\_}{st}]=0=\max_{\\_}t[(Z^{\boxtimes}_{\\_}D)_{\\_}{st}+w_{\\_}t],$

then the maxima of $v$ and $w$ coincide and also equal the magnitude of
$Z^{\boxtimes}_{\\_}D$. Such linear equations can be solved via methods
described in [15], and we simply report the result here: the unique “principal
solutions” (which may not be _bona fide_ solutions in general) are
$\hat{v}_{\\_}s:=-\max_{\\_}t(Z^{\boxtimes}_{\\_}D)_{\\_}{st}$;
$\hat{w}_{\\_}t:=-\max_{\\_}s(Z^{\boxtimes}_{\\_}D)_{\\_}{st}$. We therefore
obtain the following

######  Lemma 3.

$Z^{\boxtimes}_{\\_}D$, and hence ${\bf SubFlow}_{\\_}D$, has well-defined
magnitude $z$ over the max-plus semiring iff

$\max_{\\_}s[-\max_{\\_}t(Z^{\boxtimes}_{\\_}D)_{\\_}{st}]=z=\max_{\\_}t[-\max_{\\_}s(Z^{\boxtimes}_{\\_}D)_{\\_}{st}].\qed$
(4)

It is not obvious when such a $z$ can exist. However, by Lemma 5 of [16], any
nontrivial $D\langle e_{\\_}s,e_{\\_}t\rangle$ must be of the form
$\boxtimes_{\\_}jD\langle e_{\\_}{j-1},e_{\\_}j\rangle$ where the $D\langle
e_{\\_}{j-1},e_{\\_}j\rangle$ are minimal. Appealing to Lemma 2, we therefore
obtain the following

######  Theorem 1.

$Z^{\boxtimes}_{\\_}D$, and hence ${\bf SubFlow}_{\\_}D$, has well-defined
magnitude over the max-plus semiring. ∎

######  Example 1.

Consider a flow graph of the form
$D:=\otimes_{\\_}{k=1}^{K}\boxtimes_{\\_}{j=1}^{J_{\\_}k}D\langle
e_{\\_}{(j-1,k)},e_{\\_}{(j,k)}\rangle$, where $\otimes$ denotes the parallel
tensor/composition on ${\bf Flow}$ described in [16]. For an example, see
Figure 4. For convenience, further assume that the program structure trees of
$D\langle e_{\\_}{(j-1,k)},e_{\\_}{(j,k)}\rangle$ are all trivial, i.e., there
are no nontrivial sub-flow graphs. Then
$(Z^{\boxtimes}_{\\_}D)_{\\_}{(j_{\\_}0,k),(j_{\\_}1,k)}=\max_{\\_}{j_{\\_}0<j\leq
j_{\\_}1}h(D\langle e_{\\_}{(j-1,k)},e_{\\_}{(j,k)}\rangle)$,
$(Z^{\boxtimes}_{\\_}D)_{\\_}{-\infty,\infty}=h(D)$, where $\mp\infty$
indicate the entry and exit edges of $D$, and all other entries of
$Z^{\boxtimes}_{\\_}D$ are trivial.

$e_{\\_}-$$e_{\\_}{(0,1)}$$e_{\\_}{(1,1)}$$e_{\\_}{(2,1)}$$e_{\\_}{(0,2)}$$e_{\\_}{(1,2)}$$e_{\\_}{(2,2)}$$e_{\\_}{(0,3)}$$e_{\\_}{(1,3)}$$e_{\\_}{(2,3)}$$e_{\\_}+$
Figure 4:  Flow graph of the form
$D:=\otimes_{\\_}{k=1}^{K}\boxtimes_{\\_}{j=1}^{J_{\\_}k}D\langle
e_{\\_}{(j-1,k)},e_{\\_}{(j,k)}\rangle$ for $J_{\\_}k\equiv 2$ and $K=3$. The
large nodes indicate nontrivial interiors of sub-flow graphs.

The nontrivial weighting components are therefore

$w_{\\_}{(j,k)}=-\max_{\\_}{j_{\\_}0<j}h(D\langle
e_{\\_}{(j_{\\_}0,k)},e_{\\_}{(j,k)}\rangle)=-\max_{\\_}{j_{\\_}0<j}h(D\langle
e_{\\_}{(j_{\\_}0,k)},e_{\\_}{(j_{\\_}0+1,k)}\rangle),$

while the nontrivial coweighting components are

$v_{\\_}{(j,k)}=-\max_{\\_}{j_{\\_}1>j}h(D\langle
e_{\\_}{(j,k)},e_{\\_}{(j_{\\_}1,k)}\rangle)=-\max_{\\_}{j_{\\_}1>j}h(D\langle
e_{\\_}{(j_{\\_}1-1,k)},e_{\\_}{(j_{\\_}1,k)}\rangle).$

That is, the weighting and coweighting respectively encode the cumulative
forward and reverse maxima of the topological entropy along the $K$
“backbones” $\boxtimes_{\\_}{j=1}^{J_{\\_}k}D\langle
e_{\\_}{(j-1,k)},e_{\\_}{(j,k)}\rangle$ of $D$. In particular,
$v_{\\_}{(j_{\\_}*-1,k)}=w_{\\_}{(j_{\\_}*,k)}$ when
$j_{\\_}*=\arg\max_{\\_}jh(D\langle e_{\\_}{(j-1,k)},e_{\\_}{(j,k)}\rangle)$.

Finally, it is evident that similar behavior to that detailed in Example 1
should occur when each $D\langle e_{\\_}{(j-1,k)},e_{\\_}{(j,k)}\rangle$ is
itself of the form $\otimes_{\\_}m\boxtimes_{\\_}\ell D^{\prime}\langle
e^{\prime}_{\\_}{(\ell-1,m)},e^{\prime}_{\\_}{(\ell,m)}\rangle$, and so on.
That is, (co)weightings reliably encode salient features for “series-parallel”
flow graphs. It seems likely that the same is true for flow graphs that
correspond to “structured” control flow, which can always be obtained from
“unstructured” control flow [42] in the event that it makes any practical
difference.

Operationally, the (co)weighting identifies regions of high topological
entropy. 666 NB. Both $Z^{\boxtimes}_{\\_}D$ and its (co)weighting are
efficiently computable, as is any necessary preprocessing/restructuring of
$D$.  This echoes the observations of [3] that (co)weightings pick out salient
features of Euclidean point clouds (e.g., “strata” of sampled
psuedomanifolds). In turn, this suggests a strategy for “anchoring” graph
matching methods for related flow graphs (e.g., for different versions of the
same program or business process). Namely, iteratively coarsen suitably
(re)structured flow graphs using the technique of [16], attempting to match
regions of high topological entropy at each stage of the process. Recalling
Example 1, suppose that
$D^{\prime}:=\otimes_{\\_}{k=1}^{K}\boxtimes_{\\_}{j=1}^{J_{\\_}k}D^{\prime}\langle
e^{\prime}_{\\_}{(j-1,k)},e^{\prime}_{\\_}{(j,k)}\rangle$ is somehow related
to $D$. We can hope to leverage the respective (co)weightings for graph
matching between $D$ and $D^{\prime}$.

##  4 Magnitudes of balls in the universal cover of a digraph

For a finite strong digraph, a ball around any vertex (defined by, e.g.
distance to or from that vertex) eventually saturates. It is helpful to shift
perspectives to the _universal cover_ [9] to avoid this saturation while using
a notion of the size of these balls to characterize the digraph. 777 For the
conventional notion of a universal cover in topology, see [14, 12].  This
perspective shift is motivated by the context of a (compact connected)
Riemannian manifold, for which the _volume entropy_ [28] is defined via
$\lim_{\\_}{r\uparrow\infty}r^{-1}\log\text{vol}(B_{\\_}x(r))$, where
$B_{\\_}x(r)$ is the ball of radius $r$ around a point $x$ in the universal
cover of the manifold. It turns out that the volume entropy is independent of
the point $x$. Also, the volume entropy is bounded above by the topological
entropy of the geodesic flow, with equality in the case of nonpositive
sectional curvature. Proposition 5 is a very close analogue of this result.
888 There is a kind of volume entropy for metric graphs [26, 22] (see also
[19]), but we are unaware of a digraph analogue.

Returning to the context of digraphs, the universal cover of a digraph is a
_polytree_ , (i.e., an acyclic digraph whose corresponding undirected graph is
a tree) that “locally looks like the digraph everywhere.” A telling advantage
of this construction is that (at the cost of implicitly encoding structure) it
renders the calculation of magnitude functions trivial:

######  Lemma 4.

Let $F$ be a _polyforest_ , i.e., an acyclic digraph whose corresponding
undirected graph is a forest. Then the magnitude function of $F$ (i.e., the
magnitude of $\exp[-td]$ where $d$ is the usual Lawvere metric on $F$) is
$|V(F)|-|E(F)|e^{-t}$. 999Note that if $F$ is a polytree, then
$|V(F)|=|E(F)|+1$.

###### Proof (sketch)..

The proof can be adapted almost wholesale from an analogous result for
undirected trees (or for that matter, forests) in §4 of [23]: apart from
checking and slightly adjusting definitions, the key observation is that the
magnitude function of a digraph with a single (directed) edge is $2-e^{-t}$
(by comparison, the magnitude function of a graph with a single edge is
$2(1+e^{-t})^{-1}$). ∎

The universal cover $U_{\\_}D:=(V_{\\_}U,E_{\\_}U)$ of a weak digraph
$D=(V,E)$ is a polytree defined as follows [9]: pick $v_{\\_}0\in V$ and set

$V_{\\_}U:=\\{(v_{\\_}0,v_{\\_}1,\dots,v_{\\_}L):(v_{\\_}{j-1},v_{\\_}j)\in
E;v_{\\_}{j-1}\neq
v_{\\_}j\\}\cup\\{(v_{\\_}L,v_{\\_}{L-1},\dots,v_{\\_}0):(v_{\\_}j,v_{\\_}{j-1})\in
E;v_{\\_}j\neq v_{\\_}{j-1}\\}$

where $v_{\\_}j\in V$ and $e_{\\_}j\in E$ identically; and set

$\displaystyle E_{\\_}U:=\ $
$\displaystyle\\{((v_{\\_}0,v_{\\_}1,\dots,v_{\\_}{L-1}),(v_{\\_}0,v_{\\_}1,\dots,v_{\\_}L)):(v_{\\_}{L-1},v_{\\_}L)\in
E\\}$
$\displaystyle\cup\\{((v_{\\_}0,v_{\\_}1,\dots,v_{\\_}L),(v_{\\_}0,v_{\\_}1,\dots,v_{\\_}{L-1})):(v_{\\_}L,v_{\\_}{L-1})\in
E\\}.$

######  Example 2.

Consider the digraph $D$ in the left panel of Figure 5. Its universal cover
has local structure shown in the right panel of Figure 5, and the covering map
is depicted in Figure 6 (which also shows a larger local region of the
universal cover).

Figure 5:  (L) A strong loopless digraph $D$ with basepoint $v_{\\_}0=1$
highlighted in red. (R) The portion of $U_{\\_}D$ with vertices at distance
$\leq 3$ to or from $v_{\\_}0$. Vertices of $U_{\\_}D$ are labeled by the
corresponding sequence of $D$-vertices, with $0$ explicitly indicating the
basepoint. The ball $B_{\\_}0(3)$ is formed by taking the arborescence of
depth $3$ rooted at $0$, i.e., the right-hand part.

Figure 6:  (Cf. Figure 5.) (L) The portion of $U_{\\_}D$ with vertices at
distance $\leq 3$ to or from $v_{\\_}0$ with covering of $D$ (at bottom)
indicated. (R) The portion of $U_{\\_}D$ with vertices at distance $\leq 10$
to or from $v_{\\_}0$.

######  Proposition 3.

Let $\gamma\in V_{\\_}U$. Then there is either a unique path in $U_{\\_}D$
from $v_{\\_}0$ to $\gamma$ or _vice versa_. ∎

The number of paths from $v_{\\_}0$ of length $L$ in $U_{\\_}D$ equals the
number of loopless paths from $v_{\\_}0$ of length $L$ in $D$. Define
$B_{\\_}{v_{\\_}0}(L)$ to be the sub-polytree of $U_{\\_}D$ (defined with
basepoint $v_{\\_}0$) induced by its vertices at (the usual notion of digraph)
distance $\leq L$ from (versus to) $v_{\\_}0$. We can compute the magnitude
function of $B_{\\_}{v_{\\_}0}(L)$ very easily using the following
proposition.

######  Proposition 4.

If $D$ is loopless, then $B_{\\_}{v_{\\_}0}(L)$ is an arboresence with
$|V(B_{\\_}{v_{\\_}0}(L))|=\sum_{\\_}{\ell=0}^{L}\sum_{\\_}k(A^{\ell})_{\\_}{jk}$,
where $A$ is the adjacency matrix of $D$ and $j$ is the matrix index
corresponding to $v_{\\_}0$. ∎

######  Remark 2.

By comparison, the _Katz centrality_ is
$\sum_{\\_}{\ell=1}^{\infty}\alpha^{\ell}\sum_{\\_}i(A^{\ell})_{\\_}{ij}$,
where $\alpha$ is restricted to ensure convergence [13]. The Katz centrality
of the graph with all edges reversed is therefore
$\sum_{\\_}{\ell=1}^{\infty}\alpha^{\ell}\sum_{\\_}k(A^{\ell})_{\\_}{jk}$.

Since an arborescence (or more generally a polytree) has one more vertex than
it has edges, Lemma 4 yields that for $D$ loopless, the magnitude function of
$B_{\\_}{v_{\\_}0}(L)$ is

$\operatorname{Mag}(B_{\\_}{v_{\\_}0}(L),t)=|V(B_{\\_}{v_{\\_}0}(L))|-(|V(B_{\\_}{v_{\\_}0}(L))|-1)e^{-t},$
(5)

and the most recent proposition gives an elementary algorithm for computing
$|V(B_{\\_}{v_{\\_}0}(L))|$. If $D$ is loopless and strong, we have
$h(D)=h(U_{\\_}D)=:\lim_{\\_}{L\uparrow\infty}L^{-1}\log|V(B_{\\_}{v_{\\_}0}(L))|$
independent of the basepoint $v_{\\_}0$.

######  Proposition 5.

Let $D$ be a strong loopless digraph and $v_{\\_}0\in V(D)$. Then

$\lim_{\\_}{L\uparrow\infty}L^{-1}\log\operatorname{Mag}(B_{\\_}{v_{\\_}0}(L),t)\leq
h(D)$ (6)

with equality at $t=\infty$, and the left hand side is independent of
$v_{\\_}0$ for any $t$. Here $\operatorname{Mag}(\cdot,t)$ denotes the
magnitude function of the first argument. ∎

######  Example 3.

Continuing Example 2, $h(D)\approx 0.2812$ is the logarithm of the so-called
_plastic number_ , i.e., the unique real solution of $x^{3}-x-1=0$. Numerics
suggest that $|V(B_{\\_}1(L))|$ is given by [2]. Assuming this to obtain
values for large $L$, we show the convergence of
$L^{-1}\log\operatorname{Mag}(B_{\\_}{v_{\\_}0}(L),t)$ in Figure 7.

Figure 7:  $L^{-1}\log\operatorname{Mag}(B_{\\_}{v_{\\_}0}(L),t)\rightarrow
h(D)$ for $t>0$, but depends strongly on $t$ even for fairly large $L$.

##  5 Example: correlated features for digraph matching

In this section we detail how log-magnitudes of small balls associated to the
Lawvere metric structure on a digraph are both interesting and useful from the
perspective of feature engineering; for completeness and comparison, we start
by considering the ambient (co)weighting. In keeping with the general theme of
providing tools for graph matching, we focus on the import graph of the Flare
software hierarchy, accessed from https://observablehq.com/@d3/hierarchical-
edge-bundling/2 in November 2020 and depicted in Figure 8.

Figure 8: Import graph of the Flare software hierarchy, displayed using the
divided edge bundling approach of [36]. Edge sources and targets are
respectively colored red and blue; the hierarchy is depicted along the figure
periphery (and without any material loss of information from occlusions).

As an experiment, we considered $N=100$ realizations of a pair of random
subgraphs of the “ambient” digraph of Figure 8 obtained by removing edges with
probability $3/4$ and then retaining the largest weak component. We then
computed the (co)weightings at scale 0, the log-magnitudes of balls of radius
$\leq 3$ at scale $t=100$ (which is virtually equivalent to $t=\infty$), and
various common vertex centrality measures. For each of these quantities and
$N$ realizations, we then computed the correlation coefficients on vertices
shared by the pair of subgraphs. The results are shown in Figure 9, which
shows that the coweighting and log-magnitudes of balls in the universal cover
of the digraph with edges reversed are very strongly correlated. This suggests
the utility of such features for graph comparison [39] and matching [10].
101010 For a naive approach of matching nodes based on rankings derived from
centralities, see Figure 7 of [35].

Figure 9: Distribution of correlations for various centralities between two
random subgraphs of the digraph in Figure 8. * indicates a ball in the digraph
with all edges reversed. As $L$ increases, boundary effects cause the log-
magnitudes of balls in the universal cover to become (slightly) more
correlated to each other than the log-magnitudes of balls in the digraph
itself. Note that the three best-performing centralities are computing almost
exactly the same thing.

The strong correlations of log-magnitudes of balls are more robust than those
of (co)weightings, as an experiment along the same lines as above but using
different realizations of an Erdős-Renyí digraph ($n=100$ vertices; edge
probability $q=4/n$) as the ambient digraph for each of $N=100$ trials shows.
We formed two subgraphs by removing edges with probability $1/2$, then
retaining the largest weak component. Figure 10 shows the results, which are
qualitatively echoed for different parameters.

Figure 10: Distribution of correlations for various centralities between two
random subgraphs of distinct Erdős-Renyí digraphs with $n=100$ vertices and
edge probability $q=4/n$; cf. Figure 9.

One theoretical advantage of using log-magnitudes of balls is that unlike
(co)weightings, these are nonnegative by construction. 111111 NB. It is
possible using elementary bounds to efficiently determine the minimal $t$ such
that a [co]weighting of $Z=\exp[-td]$ is nonnegative [17].  121212 Note that
from the point of view of correlation analyses, log-magnitudes are more
interesting than the magnitudes themselves: because the correlation
coefficient is invariant under affine transformations of either argument, we
have that
$\rho(\operatorname{Mag}(B_{\\_}{v_{\\_}0}(L),t),\operatorname{Mag}(B^{\prime}_{\\_}{v_{\\_}0}(L),t^{\prime}))=\rho(|V(B_{\\_}{v_{\\_}0}(L))|,|V(B^{\prime}_{\\_}{v_{\\_}0}(L))|)$.
In any event,
$\lim_{\\_}{t\uparrow\infty}\operatorname{Mag}(B_{\\_}{v_{\\_}0}(L),t)=|V(B_{\\_}{v_{\\_}0}(L))|$.
This may be advantageous in the context of graph matching via optimal
transport techniques that require a sensible distribution on vertices. In
particular, the recently developed _Gromov-Wasserstein distance_ [29, 30] is
useful for analyzing weighted digraphs endowed with measures [4] and has been
applied to (mostly but not exclusively undirected) graph matching with state
of the art performance [37, 41, 40, 6, 5, 38]. For instance, although [40] did
not consider digraphs, it used a distribution proportional to $(\deg+a)^{b}$,
where $a$ and $b$ are hyperparameters, and remarked that “the node
distributions have a huge influence on the stability and the performance of
our learning algorithms.” Meanwhile, this particular sort of distribution is
rather similar to the log-magnitude of a unit ball for $a=1$ and $b=0$. In
short, we can plausibly expect to improve upon the approach of [40] in the
context of digraphs by using weightings rather than a more _ad hoc_
distribution.

## Acknowledgement

This research was developed with funding from the Defense Advanced Research
Projects Agency (DARPA). The views, opinions and/or findings expressed are
those of the author and should not be interpreted as representing the official
views or policies of the Department of Defense or the U.S. Government.
Distribution Statement “A” (Approved for Public Release, Distribution
Unlimited)

## References

  * [1]
  * [2] Roger L. Bagula (2009): _Online Encyclopedia of Integer Sequences: sequence A167385_.  Available at http://oeis.org/A167385.
  * [3] Eric Bunch et al. (2020): _Practical applications of metric space magnitude and weighting vectors_ , 10.48550/arXiv.2006.14063.
  * [4] Samir Chowdhury & Facundo Mémoli (2019): _The Gromov–Wasserstein distance between networks and stable network invariants_.  Information and Inference 8(4), pp. 757–787, 10.1093/imaiai/iaz026.
  * [5] Samir Chowdhury & Tom Needham (2020): _Gromov-Wasserstein averaging in a Riemannian framework_.  In: CVPR Workshops, 10.1109/CVPRW50498.2020.00429.
  * [6] Samir Chowdhury & Tom Needham (2021): _Generalized spectral clustering via Gromov-Wasserstein learning_.  In: AISTATS.  Available at http://proceedings.mlr.press/v130/chowdhury21a.html.
  * [7] Joseph Chuang, Alastair King & Tom Leinster (2016): _On the magnitude of a finite dimensional algebra_.  Theory and Applications of Categories 31(3), pp. 63–72.  Available at http://www.tac.mta.ca/tac/volumes/31/3/31-03abs.html.
  * [8] Keith Cooper & Linda Torczon (2011): _Engineering a Compiler_.  Elsevier, 10.1016/C2009-0-27982-7.
  * [9] Willibald Dörfler, Frank Harary & Günther Malle (1980): _Covers of digraphs_.  Mathematica Slovaca 30(3), pp. 269–280.  Available at https://eudml.org/doc/34089.
  * [10] Frank Emmert-Streib, Matthias Dehmer & Yongtang Shi (2016): _Fifty years of graph matching, network alignment and network comparison_.  Information Sciences 346, pp. 180–197, 10.1016/j.ins.2016.01.074.
  * [11] Brendan Fong & David I Spivak (2019): _An Invitation to Applied Category Theory: Seven Sketches in Compositionality_.  Cambridge, 10.1017/9781108668804
  * [12] Robert W Ghrist (2014): _Elementary Applied Topology_.  Createspace.  Available at https://www2.math.upenn.edu/~ghrist/notes.html.
  * [13] Peter Grindrod & Desmond J Higham (2013): _A matrix iteration for dynamic network summaries_.  SIAM Review 55(1), pp. 118–128, 10.1137/110855715.
  * [14] Allen Hatcher (2002): _Algebraic Topology_.  Cambridge.  Available at https://pi.math.cornell.edu/~hatcher/AT/ATpage.html.
  * [15] Bernd Heidergott, Geert Jan Olsder & Jacob Van Der Woude (2014): _Max Plus at Work_.  Princeton, 10.1515/9781400865239.
  * [16] Steve Huntsman (2019): _The multiresolution analysis of flow graphs_.  In: WoLLIC, 10.1007/978-3-662-59533-620.
  * [17] Steve Huntsman (2022): _Diversity enhancement via magnitude_ , 10.48550/arXiv.2201.10037.
  * [18] Richard Johnson, David Pearson & Keshav Pingali (1994): _The program structure tree: computing control regions in linear time_.  In: PLDI, 10.1145/178243.178258.
  * [19] Steve Karam (2015): _Growth of balls in the universal cover of surfaces and graphs_.  Transactions of the American Mathematical Society 367(8), pp. 5355–5373, 10.1090/S0002-9947-2015-06189-3.
  * [20] Gregory Maxwell Kelly (1982): _Basic Concepts of Enriched Category Theory_.  Cambridge.
  * [21] Bruce P Kitchens (2012): _Symbolic Dynamics_.  Springer, 10.1007/978-3-642-58822-8.
  * [22] Hyekyoung Lee et al. (2019): _Volume entropy for modeling information flow in a brain graph_.  Scientific Reports 9(1), pp. 1–13, 10.1038/s41598-018-36339-7.
  * [23] Tom Leinster (2019): _The magnitude of a graph_.  Mathematical Proceedings of the Cambridge Philosophical Society 166(2), pp. 247–264, 10.1017/S0305004117000810.
  * [24] Tom Leinster (2021): _Entropy and Diversity: the Axiomatic Approach_.  Cambridge, 10.1017/9781108963558.
  * [25] Tom Leinster & Mark W Meckes (2017): _The magnitude of a metric space: from category theory to geometric measure theory_.  In Nicola Gigli, editor: Measure Theory in Non-Smooth Spaces, De Gruyter, 10.1515/9783110550832-005.
  * [26] Seonhee Lim (2008): _Minimal volume entropy for graphs_.  Transactions of the American Mathematical Society 360(10), pp. 5089–5100, 10.1090/S0002-9947-08-04227-X.
  * [27] Saunders Mac Lane (1978): _Categories for the working mathematician_.  Springer, 10.1007/978-1-4757-4721-8.
  * [28] Anthony Manning (1979): _Topological entropy for geodesic flows_.  Annals of Mathematics 110(3), pp. 567–573, 10.2307/1971239.
  * [29] Facundo Mémoli (2011): _Gromov–Wasserstein distances and the metric approach to object matching_.  Foundations of Computational Mathematics 11(4), pp. 417–487, 10.1007/s10208-011-9093-5.
  * [30] Facundo Mémoli (2014): _The Gromov–Wasserstein distance: a brief overview_.  Axioms 3(3), pp. 335–341, 10.3390/axioms3030335.
  * [31] Hirobumi Mizuno & Iwao Sato (2001): _Zeta functions of digraphs_.  Linear Algebra and its Applications 336(1-3), pp. 181–190, 10.1016/S0024-3795(01)00318-4.
  * [32] Flemming Nielson, Hanne R Nielson & Chris Hankin (2004): _Principles of Program Analysis_.  Springer, 10.1007/978-3-662-03811-6.
  * [33] nLab authors (2020): http://ncatlab.org/nlab/show/enriched%20category.  Revision 94.
  * [34] nLab authors (2020): http://ncatlab.org/nlab/show/max-plus%20algebra.  Revision 2.
  * [35] Ryoma Sato et al. (2020): _Fast and robust comparison of probability measures in heterogeneous spaces_ , 10.48550/arXiv.2002.01615.
  * [36] David Selassie, Brandon Heller & Jeffrey Heer (2011): _Divided edge bundling for directional network data_.  IEEE Transactions on Visualization and Computer Graphics 17(12), pp. 2354–2363, 10.1109/TVCG.2011.190.
  * [37] Titouan Vayer et al. (2019): _Optimal transport for structured data with application on graphs_.  In: ICML.  Available at http://proceedings.mlr.press/v97/titouan19a.html.
  * [38] Titouan Vayer et al. (2020): _Fused Gromov-Wasserstein distance for structured objects_.  Algorithms 13(9), p. 212, 10.3390/a13090212.
  * [39] Peter Wills & François G Meyer (2020): _Metrics for graph comparison: a practitioner’s guide_.  PLoS ONE 15(2), p. e0228728, 10.1371/journal.pone.0228728.
  * [40] Hongteng Xu, Dixin Luo & Lawrence Carin (2019): _Scalable Gromov-Wasserstein learning for graph partitioning and matching_.  In: NeurIPS.  Available at https://papers.nips.cc/paper/2019/hash/6e62a992c676f611616097dbea8ea030-Abstract.html.
  * [41] Hongteng Xu et al. (2019): _Gromov-Wasserstein learning for graph matching and node embedding_.  In: ICML.  Available at http://proceedings.mlr.press/v97/xu19b.html.
  * [42] Fubo Zhang & Erik H D’Hollander (2004): _Using hammock graphs to structure programs_.  IEEE Transactions on Software Engineering 30(4), pp. 231–245, 10.1109/TSE.2004.1274043.