# Sampling for network function learning

_Li-Chun Zhang_

Given a _valued graph_ , where both the nodes and the edges of the graph are
associated with one or several values, any network function for a given node
must be defined in terms of that node _and_ its connected nodes in the graph.
Generally, applying the same definition to the whole graph or any given
subgraph of it would result in systematically different network functions. In
this paper we consider the feasibility of graph sampling approach to network
function learning, as well as the corresponding learning methods based on the
sample graphs. This can be useful either when the edges are unknown to start
with or the graph is too large (or dynamic) to be processed entirely.

Key words: graph, supervised learning, graph sampling, estimating equation

##  1 Network function

Let $G=(U,A)$ be a simple graph with $U$ as the set of nodes, $N=|U|$, and $A$
as the adjacency matrix, where $a_{ij}=1$ if an edge from $i$ to $j$ exists
and 0 otherwise. By definition, an undirected graph is such that $a_{ij}\equiv
a_{ji}$ for any $i,j\in U$ and, as a convention for this paper, we assume
$a_{ii}\equiv 0$ for any $i\in U$, i.e. there are no loops in the graph. Let
$v_{G}$ contain the values associated with the graph, which are
$y_{U}=\\{y_{i}:i\in U\\}$, $x_{U}=\\{x_{i}:i\in U\\}$ and
$\omega_{A}=\\{\omega_{ij}:i,j\in U,a_{ij}=1\\}$. Whereas $y_{i}$ is a scalar
_outcome_ value the function targets, $x_{i}$ and $\omega_{ij}$ are (possibly
vectors of) _feature_ values that can be used to form the arguments of the
function.

Given the _valued graph_ $(G,v_{G})$, a _network function (NF)_ for any $i$ in
$U$ must be defined in terms of $i$ _and_ its _(graph) neighbours_ , which are
given by

$\nu_{i}=\\{j\in U:a_{ij}+a_{ji}>0\\}$

For any $i\in U$, let its degree, out-degree and in-degree be

$d_{i}=|\nu_{i}|\qquad d_{i+}=\sum_{j\in\nu_{i}}a_{ij}\quad\text{and}\quad
d_{+i}=\sum_{j\in\nu_{i}}a_{ji}$

where $d_{i}=d_{i+}=d_{+i}$ in undirected graphs by definition.

###  1.1 Contextual network function (CNF)

For any $i\in U$, let $x_{\nu_{i}}=\\{x_{j}:j\in\nu_{i}\\}$ and
$\omega_{\nu_{i}}=\\{\omega_{ij},\omega_{ji}:j\in\nu_{i}\\}$. A _contextual
NF_ explicates a mapping
$(x_{i},x_{\nu_{i}},\omega_{\nu_{i}})\mapsto\mu_{i}\in\mathbb{R}$, defined by

$\mu_{i}=f(x_{i},\dot{x}_{i};\theta_{0})\quad\text{and}\quad\theta_{0}=\arg\min_{\theta}D\big{(}\mu_{U}(\theta),y_{U}\big{)}$
(1)

given _contextual features_

$\dot{x}_{i}=\eta(x_{\nu_{i}},\omega_{\nu_{i}})$ (2)

and the _parameter_ value $\theta_{0}$ that minimises a metric $D$ of the
distance between $y_{U}$ and $\mu_{U}(\theta)=\\{\mu_{i}(\theta):i\in U\\}$.

For instance, a simple model of a random outcome $y_{i}$ can be given as

$\displaystyle y_{i}$
$\displaystyle=x_{i}^{\top}\beta+z_{i}^{\top}\gamma+e_{i}$ $\displaystyle
z_{i}$ $\displaystyle=d_{+i}^{-1}\sum_{j\in\nu_{i}}a_{ji}x_{j}$

where $z_{i}$ is the average feature of those neighbours with $a_{ji}=1$, and
$e_{i}$ is an independent mean-0 random error, and $(\beta,\gamma)$ are
unknown constants. The corresponding contextual NF with
$\theta=(\beta,\gamma)$ is

$\mu_{i}=E(y_{i}\mid
x_{i},x_{\nu_{i}},\omega_{\nu_{i}};\beta,\gamma)=x_{i}^{\top}\beta+z_{i}^{\top}\gamma$

As Friedkin (1990) comments, a group average effect via $z_{i}$ may be
unrealistic in many social settings, where the nodes represent a finite
population of persons and the edges the existent influences among them.

Potentially more realistic contextual features can be engineered in terms of
the _neighbour function_ (2), which must be invariant over permutations of the
adjacent nodes. For instance, varying strength of network influence can be
achieved via $\omega_{ji}$ associated with $(ji)\in A$. Finally, note that the
definition (1) does not require any distributional assumptions about $y_{U}$,
which are treated as unknown constants and the targets of $\mu_{U}$.

###  1.2 Recursive network function (RNF)

A _recursive NF_ defines a mapping $(x_{i},\mu_{\nu_{i}})\mapsto\mu_{i}$,
where $\mu_{\nu_{i}}=\\{\mu_{j}:j\in\nu_{i}\\}$, such that $\mu_{i}$ may
depend on some $\mu_{j}$ for $j\in\nu_{i}$, and $\mu_{j}$ itself may depend on
some $\mu_{k}$ for $k\in\nu_{j}$, and so on recursively. We consider any
recursive NF defined by

$\mu_{i}=\lambda_{0}\dot{\mu}_{i}+c_{i}\quad\text{and}\quad\theta_{0}=\arg\min_{\theta}D\big{(}\mu_{U}(\theta),y_{U}\big{)}$
(3)

where $\theta=(\beta,\lambda)$, given $c_{i}=c(x_{i};\beta_{0})$ and any
_linear_ neighbour function

$\dot{\mu}_{i}=\sum_{j\in\nu_{i}}m_{ij}\mu_{j}$ (4)

where $m_{ij}$ depends on $\omega_{\nu_{i}}$, and $\lambda_{0}$ is subject to
the restriction

$\|\lambda_{0}M\|<1$

where the matrix $M$ has $m_{ij}$ as its $(i,j)$th element if $j\in\nu_{i}$
and 0 otherwise.

Given linear neighbour function (4), we can rewrite (3) in matrix notation as

$\mu=\lambda_{0}M\mu+c$

The restriction $\|\lambda_{0}M\|<1$ ensures that $Q$ exists for

$\mu=Qc\coloneqq(I-\lambda_{0}M)^{-1}c$

where $I$ is the $N\times N$ identity matrix. Thus, the recursive NF defines a
mapping $(x_{U},\omega_{A})\mapsto\mu_{i}$, which generally depends on the
entire adjacent matrix $A$.

Meanwhile, let the $\tau$th order approximation to the matrix $Q$ be given as

$Q_{\tau}\coloneqq
I+\lambda_{0}M+\lambda_{0}^{2}M^{2}+\cdots+\lambda_{0}^{\tau}M^{\tau}$

Since $M$ has the same non-zero elements as $A^{\top}$, the $(i,j)$th element
of $M^{t}$ depends on all the possible paths of length $t$ from some node $j$
to $i$. Let $\alpha_{i}^{t}$ contain the nodes that can reach $i$ in exactly
$t$ steps, which correspond to the non-zero elements in the $i$th column of
$A^{t}$. Then, by the approximation $\mu\doteq Q_{\tau}c$, $\mu_{i}$ would
only depend on $c_{j}$ if $j$ belongs to the $\tau$th-order neighbourhood

$\nu_{i}^{\tau}=\bigcup_{t=1}^{\tau}\alpha_{i}^{t}$ (5)

This shows how the recursive NF can represent a power series of contextual
effects (or influences) over any number of steps.

######  Example 1.

Take the digraph in Figure 1 for an illustration.

${i_{3}~}$${i_{1}~}$${i_{2}}$${i_{4}}$ Figure 1: A digraph with 4 nodes

Arrange the rows of the adjacency matrix $A$ in the order
$i_{1},i_{2},i_{3},i_{4}$. We have

$A=\left[\begin{array}[]{cccc}0&1&0&0\\\ 0&0&1&1\\\ 0&0&0&1\\\
0&0&0&0\end{array}~\right]\qquad A^{2}=\left[\begin{array}[]{cccc}0&0&1&1\\\
0&0&0&1\\\ 0&0&0&0\\\ 0&0&0&0\end{array}~\right]\qquad
A^{3}=\left[\begin{array}[]{cccc}0&0&0&1\\\ 0&0&0&0\\\ 0&0&0&0\\\
0&0&0&0\end{array}~\right]$

For the 2nd-order approximation to the RNF, $\mu_{i_{1}}$ does not depend on
any other $c_{j}$ since $d_{+i_{1}}=0$, and $\mu_{i_{2}}$ depends on
$c_{i_{1}}$ where $\nu_{i_{2}}^{2}=\alpha_{i_{2}}^{1}=\\{i_{1}\\}$, and
$\mu_{i_{3}}$ depends on $c_{j}$ for $j\in\nu_{i_{3}}^{2}=\\{i_{1},i_{2}\\}$
where $\alpha_{i_{3}}^{1}=\\{i_{2}\\}$ and $\alpha_{i_{3}}^{2}=\\{i_{1}\\}$,
and $\mu_{i_{4}}$ depends on all the other $c_{j}$ since
$\nu_{i_{4}}^{2}=\\{i_{1},i_{2},i_{3}\\}$. Note that $c_{i_{2}}$ affects
$\mu_{i_{4}}$ via both $M$ and $M^{2}$, due to the edge $(i_{2}i_{4})$ and the
2-path $(i_{2},i_{3},i_{4})$, respectively. Since $A^{t}=0$ for $t\geq 4$, we
have $Q=Q_{\tau}$ for any $\tau\geq 3$ given $\|\lambda_{0}M\|<1$.

###  1.3 Remarks

Ord (1975) considers maximum likelihood estimation of the model

$y_{i}=\rho\sum_{j\in\nu_{i}}m_{ij}y_{j}+c_{i}+\epsilon_{i}\quad\text{and}\quad
c_{i}=x_{i}^{\top}\beta\quad\text{and}\quad\sum_{j\in\nu_{i}}m_{ij}=1$

that allow interactions among locations $U$. This corresponds to the RNF

$\mu_{i}=E(y_{i}\mid
G,x_{U},\omega_{A};\beta,\rho)=\rho\sum_{j\in\nu_{i}}m_{ij}\mu_{j}+c_{i}$

However, there are several obstacles to applying Ord’s approach to recursive
NF learning generally. First, it requires known $\nu_{i}$ and
$\\{m_{ij}:j\in\nu_{i}\\}$ for all $i\in U$, not just a sample of them. Next,
an assumption of normally distributed $\epsilon_{i}$ is needed, given which
the log-likelihood requires one to compute

$\mbox{det}(I-\rho M)=\prod_{i=1}^{N}(1-\rho\lambda_{i})$

where $\lambda_{1},...,\lambda_{N}$ are the eigenvalues of $W$, which can be
too demanding if $N$ is very large even when $M$ is known. Finally, the
assumption of independent $\epsilon_{i}$ with constant variance may be
unrealistic. For instance, suppose $a_{ij}=a_{ji}=1$ and $i,j$ are not
connected to any other nodes. Then, we would have

$\begin{cases}\mu_{i}=\rho\mu_{j}+c_{i}\\\
\mu_{j}=\rho\mu_{i}+c_{j}\end{cases}\&~{}~{}\begin{cases}y_{i}=\mu_{i}+e_{i}\\\
y_{j}=\mu_{j}+e_{j}\end{cases}\Rightarrow~{}~{}\begin{cases}y_{i}=\rho
y_{j}+c_{i}+(e_{i}-\rho e_{j})\\\ y_{j}=\rho y_{i}+c_{j}+(e_{j}-\rho
e_{i})\end{cases}$

An alternative network disturbance model is sometimes adopted to account for
node interdependencies (e.g. Ord, 1975; Leenders, 2002), where

$y_{i}=x_{i}^{\top}\beta+e_{i}\quad\text{and}\quad
e_{i}=\rho\sum_{j\in\nu_{i}}m_{ij}e_{j}+\epsilon_{i}$

or

$y=X\beta+(I-\rho M)^{-1}\epsilon\quad\text{and}\quad e=\rho Me+\epsilon$

in matrix notation, which however corresponds to the non-network function
$\mu_{i}=E(y_{i}|x_{i})=x_{i}^{\top}\beta$ that is not our concern in this
paper.

##  2 Learning

Let $e_{U}=\\{e_{i}:i\in U\\}$ be the discrepancies between $\mu_{U}(\theta)$
and $y_{U}$, where $e_{i}=y_{i}-\mu_{i}$. Let
$e_{\nu_{i}}=\\{e_{j}:j\in\nu_{i}\\}$. We consider in this paper metrics $D$
of the form

$D(\mu_{U},y_{U})=\sum_{i\in U}D(e_{i},e_{\nu_{i}})$

such that given the population graph $G$ and all the associated values
$v_{G}$, the parameter $\theta_{0}$ by definition (1) or (3) must be a
solution to

$\frac{\partial}{\partial\theta}D(\mu_{U},y_{U})=H(\theta;G)=\sum_{i\in
U}H_{i}(\theta)=\sum_{i\in
U}\frac{\partial}{\partial\theta}D(e_{i},e_{\nu_{i}})=0$

Now, for NF learning we would estimate $\theta_{0}$ based on a sample of nodes
and edges from $G$, to be referred to as the _sample graph_ and denoted by
$G_{s}=(U_{s},A_{s})$, where $U_{s}$ contains the observed nodes of $U$ and
$A_{s}$ the observed elements of the adjacency matrix $A$. Specifically, we
shall estimate $\theta_{0}$ by solving the _sample estimating equation (SEE)_

$H(\theta;G_{s})=\sum_{i\in U_{s}}w_{i}H_{i}(\theta)=0$ (6)

where $w_{i}$ is an appropriately chosen weight for each $i\in U_{s}$,
depending on the sampling method by which $(G_{s},v_{G_{S}})$ are observed
from $(G,v_{G})$, such that the SEE is _unbiased_ under hypothetically
repeated sampling, denoted by

$E\big{[}H(\theta;G_{s})\big{]}=\sum_{i\in U}H_{i}(\theta)=H(\theta;G)$

Note that it is inappropriate generally to let $w_{i}\equiv 1$ given we
observe all the values from $v_{G}$ which are required for $H_{i}(\theta)$ and
0 otherwise, since

$E\big{[}\sum_{i\in U_{s}:w_{i}=1}H_{i}(\theta)\big{]}=E\big{[}\sum_{i\in
U}\mathbb{I}(w_{i}=1)H_{i}(\theta)\big{]}\neq\sum_{i\in U}H_{i}(\theta)$

Below we first propose the choices of $D$ and the corresponding SEEs (6) for
CNF and RNF, respectively. We then explain how the weights in (6) can be
obtained for two basic graph sampling methods, which yield either depth-first
or breadth-first observation in graphs.

###  2.1 SEE

First, a natural choice of $D$ for the CNF (1) is

$D(\mu_{U},y_{U})=\sum_{i\in U}\frac{e_{i}^{2}}{2\sigma_{i}^{2}}$ (7)

where $\sigma_{i}^{2}$ is a chosen constant that may depend on $x_{i}$. The
SEE follows as

$H(\theta;G_{s})=\sum_{i\in
U_{s}}\frac{w_{i}}{\sigma_{i}^{2}}\big{(}\frac{\partial\mu_{i}}{\partial\theta}\big{)}(\mu_{i}-y_{i})=0$

The similarity to weighted least squares for standard linear regression
becomes clear given $\mu_{i}=u_{i}^{\top}\theta$, where
$\theta^{\top}=(\beta^{\top},\gamma^{\top})$ and
$u_{i}^{\top}=(x_{i}^{\top},z_{i}^{\top})$, such that

$\theta_{0}=\big{(}\sum_{i\in
U}\sigma_{i}^{-2}u_{i}u_{i}^{\top}\big{)}^{-1}\sum_{i\in
U}\sigma_{i}^{-2}u_{i}y_{i}$

and the SEE yields

$\hat{\theta}_{0}=\big{(}\sum_{i\in
U_{s}}\frac{w_{i}}{\sigma_{i}^{2}}~u_{i}u_{i}^{\top}\big{)}^{-1}\sum_{i\in
U_{s}}\frac{w_{i}}{\sigma_{i}^{2}}u_{i}y_{i}$

Next, for an innovative approach to the RNF (3), we propose

$D(\mu_{U},y_{U})=\sum_{i\in U}\frac{\tilde{e}_{i}^{2}}{2\sigma_{i+}^{2}}$ (8)

where $\tilde{e}_{i}$ is given via the same neighbour function (4) for
$\dot{\mu}_{i}$ as

$\tilde{e}_{i}=e_{i}-\lambda\dot{e}_{i}=e_{i}-\lambda\sum_{j\in\nu_{i}}m_{ij}e_{j}=\tilde{y}_{i}-c_{i}\quad\text{with}\quad\tilde{y}_{i}=y_{i}-\lambda\dot{y}_{i}$

and

$\sigma_{i+}^{2}=\sigma_{i}^{2}+\lambda^{2}\sum_{j\in\nu_{i}}m_{ij}^{2}\sigma_{j}^{2}$

Note that $\sigma_{i+}^{2}$ would be the variance of $\tilde{e}_{i}$ if
$e_{i}$ is a random variable with variance $\sigma_{i}^{2}$ and is independent
across the nodes. The SEE (6) follows, where

$\begin{cases}H_{i}(\lambda)=-\sigma_{i+}^{-2}\tilde{e}_{i}\dot{y}_{i}-\lambda\sigma_{i+}^{-4}\tilde{e}_{i}^{2}\sum_{j\in\nu_{i}}m_{ij}^{2}\sigma_{j}^{2}\\\
H_{i}(\beta)=\sigma_{i+}^{-2}c^{\prime}(x_{i};\beta)(c_{i}-\tilde{y}_{i})\quad\text{with}\quad
c^{\prime}(x_{i};\beta)=\partial c(x_{i};\beta)/\partial\beta\end{cases}$

As a practical alternative, one could choose a grid of values $\lambda$
subject to the range restriction of $\lambda_{0}$, find the corresponding
$\beta_{\lambda}$ for each $\lambda$ by solving

$H(\beta;G_{s}\mid\lambda)=\sum_{i\in
s}\frac{w_{i}}{\sigma_{i+}^{2}}c^{\prime}(x_{i};\beta)(c_{i}-\tilde{y}_{i})=0$

and choose as $\hat{\theta}_{0}$ the pair of $(\lambda,\beta_{\lambda})$ that
minimise the estimate of (8) given by

$\hat{D}(\mu_{U},y_{U})=\sum_{i\in
s}\frac{w_{i}\tilde{e}_{i}^{2}}{2\sigma_{i+}^{2}}$

###  2.2 Graph sampling and weighting

The way by which the edges drive graph sampling is called the _observation
procedure (OP)_ ; see Zhang (2022), Zhang and Patone (2017). In particular, we
assume in this paper that the OP is _reciprocal incident_ such that, given an
initial sample of nodes $s_{0}$, both $a_{ij}$ and $a_{ji}$ are observed for
any $i\in s_{0}$. For instance, if $s_{0}=\\{i_{4}\\}$ in Figure 1, then
$\\{i_{2},i_{3}\\}$ are observed as well as $a_{i_{2}i_{4}}$ and
$a_{i_{3}i_{4}}$, i.e. the direction of an edge (in digraphs) does not matter
under the reciprocal incident OP. Moreover, the values in $v_{G}$ are assumed
to be observed together with the associated nodes and edges. Finally, an OP
may be applied repeatedly, i.e. to the observed nodes outside the initial
$s_{0}$, and the set of nodes to which the OP is applied is called the _seed
sample_ , denoted by $s$. Let $A_{s}$ contain all the elements of $A$ which
are observed from the seed sample. Zhang (2022) defines sample graph to be
$G_{s}=(U_{s},A_{s})$, where $U_{s}=s\cup\\{i,j:a_{ij}\in A_{s}\\}$.

For any $i\in U_{s}$, denote by $\delta_{i}=1$ or 0 whether all the values
required for $H_{i}(\theta)$ are observed. Given (7), we have $\delta_{i}=1$
for the CNF iff $(x_{\nu_{i}},\omega_{\nu_{i}})$ are observed; given (8), we
have $\delta_{i}=1$ for the RNF iff
$(y_{\nu_{i}},x_{\nu_{i}},\omega_{\nu_{i}})$ are observed. Thus, although the
RNF $\mu=Qc$ depends on the whole graph, we only need to observe the
neighbourhood of $i$ and all the associated values, in order to be able to use
it for learning, as long as we adopt the proposed metric (8) for RNF. In
contrast, for the $Q_{\tau}$-approximation $\mu=Q_{\tau}c$, we have
$\delta_{i}=1$ iff
$(y_{\nu_{i}^{\tau}},x_{\nu_{i}^{\tau}},\omega_{\nu_{i}^{\tau}})$ are
observed, where $\nu_{i}^{\tau}$ is defined by (5) and
$\omega_{\nu_{i}^{\tau}}$ are associated with all the paths starting from $i$
and consisting of at most $\tau$ edges (regardless their directions). The
observation requirement is actually more demanding than for the RNF.

Below we describe the details of sampling and weighting for NF learning. By
virtue of the reciprocal incident OP, the description given below in terms of
undirected graphs applies equally to digraphs.

####  2.2.1 Targeted random walk (TRW)

There are many types of random walk on graphs; see e.g. Masuda et al. (2017).
We consider the following. Starting from any node, denoted by $O_{0}=i\in U$,
we either move randomly over one of the edges incident to $i$ or jump randomly
to any node by the following transition probabilities (Avrachenkov, et al.,
2010)

$p_{ij}=\begin{cases}\frac{1}{d_{i}+r}\big{(}1+\frac{r}{N}\big{)}&\text{if
}a_{ij}=1\\\ \frac{r}{d_{i}+r}\big{(}\frac{1}{N}\big{)}&\text{if
}a_{ij}=0\text{ including }i=j\end{cases}$

where $r$ is a chosen tuning constant. This yields $O_{1}=j$, and so on. By
virtue of random jump, the Markov process $\\{O_{t}:t\geq 0\\}$ is
irreducible. On reaching its equilibrium, the stationary probability is given
by

$\pi_{i}=\Pr(O_{t}=i)\propto d_{i}+r$ (9)

The same stationary probabilities $\\{\pi_{i}:i\in U\\}$ can as well be
obtained by faster-mixing lagged random walk (Zhang, 2021).

Applying the OP to the current state $O_{t}=i$ enables one to observe
$\nu_{i}$ and the associated $(x_{\nu_{i}},y_{\nu_{i}},\omega_{\nu_{i}})$.
Hence, for both the CNF (1) and RNF (3), we have $\delta_{i}=1$ iff $i$ is in
the seed sample of TRW. Given an extraction of $n$ states at equilibrium,
denoted by $s_{n}=\\{t_{1},...,t_{n}\\}$, the SEE (6) can be written as

$H(\theta;G_{s})=\sum_{k=1}^{n}\sum_{i\in
U}\mathbb{I}(O_{t_{k}}=i)w_{i}H_{i}(\theta)$

For each $i\in U$, setting

$w_{i}^{-1}=n(d_{i}+r)$

makes the SEE is unbiased, since

$E\big{[}H(\theta;G_{s})\big{]}=\frac{1}{n}~\sum_{k=1}^{n}\sum_{i\in
U}\frac{\pi_{i}}{d_{i}+r}H_{i}(\theta)\propto\sum_{i\in U}H_{i}(\theta)=0$

Under TRW, the states are correlated in the seed sample
$s_{n}=\\{t_{1},...,t_{n}\\}$. The simplest approach to unbiased variance
estimation is to run multiple TRWs independently and obtain, say,
$\hat{\theta}_{l}$ for $l=1,...,L$. The combined estimator and variance
estimator are then given by

$\hat{\theta}=\frac{1}{L}~\sum_{l=1}^{L}\hat{\theta}_{l}\qquad\text{and}\qquad\hat{V}(\hat{\theta})=\frac{1}{L(L-1)}\sum_{l=1}^{L}(\hat{\theta}_{l}-\hat{\theta})^{2}$

####  2.2.2 Snowball sampling (SBS)

Let $s_{0}\sim p(s_{0})$ for the initial sample $s_{0}\subset U$. For
$t=1,...,T$, let

$s_{t}=\nu(s_{t-1})\setminus\bigcup_{r=0}^{t-1}s_{r}$

be the $t$-th wave sample of nodes, which are outside of $s_{t-1}$ but
adjacent to some nodes in $s_{t-1}$. The sampling is terminated if
$s_{t}=\emptyset$ for some $t<T$, in which case $s_{r}=\emptyset$ for
$r=t,...,T$. The seed sample of _$T$ -wave snowball sampling ($T$SBS_) is

$s=\bigcup_{t=0}^{T-1}s_{t}$

(Zhang, 2022; Frank and Snijders, 1994; Goodman, 1961). By the reciprocal
incident OP, the elements of $A_{s}$ are $s\times U\cup U\times s$.

Clearly, 1SBS is feasible for the learning of CNF (1) or RNF (3), where
$\delta_{i}=1$ iff $i\in s_{0}$. The number of nodes with $\delta_{i}=1$ can
be increased by $T$SBS, if $T>1$. For example, suppose $s_{0}=\\{i_{2}\\}$ in
Figure 1. By 1SBS, we observe all the other nodes,
$s_{1}=\\{i_{1},i_{3},i_{4}\\}$, but not yet _all_ the neighbours of these
nodes because it is unclear whether there are any edges among $s_{1}$. After
the 2nd wave, all the neighbours of $s_{1}$ are also observed, so that
$\delta_{i}=1$ for $s_{0}\cup s_{1}$. Thus, by $T$SBS generally, we have
$\delta_{i}=1$ iff $i$ is in the seed sample $s$.

To define the weights, we use the _sample-dependent_ strategy (Zhang, 2022).
Given the sample graph $G_{s}=(U_{s},A_{s})$, let $F_{i,s}$ contain all the
nodes (including itself) that can lead to $i\in s$ (i.e. $\delta_{i}=1$) by
$T$-wave OP _in_ $G_{s}$, in contrast to $F_{i}$ that contains all such nodes
in $G$. Notice that $F_{i,s}$ is generally not equal to $F_{i}$ because
$G_{s}\neq G$. For the SEE (6), let $w_{i}=0$ if $i\in U_{s}\setminus s$ and,
for any $i\in s$, let

$w_{i}^{-1}=\Pr(s_{0}\cap F_{i,s}\neq\emptyset)=1-\Pr(s_{0}\cap
F_{i,s}=\emptyset)$ (10)

according to the sampling design of $s_{0}$. The SEE is then unbiased
_conditional_ on the chosen $F_{i,s}$, which means that we let $\delta_{i}=1$
_only if_ at least one node in $F_{i,s}$ is selected in the initial sample but
not otherwise, i.e.

$E\big{[}H(\theta;G_{s})\big{]}=\sum_{i\in
U}E(\delta_{i})w_{i}H_{i}(\theta)=\sum_{i\in U}\Pr(s_{0}\cap
F_{i,s}\neq\emptyset)w_{i}H_{i}(\theta)=\sum_{i\in U}H_{i}(\theta)$

That is, under hypothetically repeated sampling, we would set $\delta_{i}=0$
despite $i\in s$, whenever $i\in s$ happens only because $(F_{i}\setminus
F_{i,s})\cap s_{0}\neq\emptyset$. Take the digraph in Figure 2. Suppose 3SBS
yields $s_{0}=\\{i_{1}\\}$, $s_{1}=\\{2\\}$, $s_{2}=\\{i_{3}\\}$ and
$s_{3}=\\{i_{4}\\}$, such that $F_{i_{3},s}=\\{i_{1},i_{2},i_{3},i_{4}\\}$ for
$i_{3}\in s$, although $i_{5}\in F_{i_{3}}$ as well. By the strategy (10), we
would set $\delta_{i_{3}}=0$ whenever 3SBS starts with $s_{0}=\\{i_{5}\\}$
under repeated sammpling, even though $i_{3}$ is included in the seed sample
$s$ then.

${i_{1}~}$${i_{2}}$${i_{3}}$${i_{4}}$${i_{5}}$ Figure 2: A digraph with 5
nodes

Let $\hat{\theta}$ be the solution to SEE. By expansion around $\theta_{0}$,
we have

$0=\sum_{i\in U_{s}}w_{i}H_{i}(\hat{\theta})\approx\sum_{i\in
U}\delta_{i}w_{i}H_{i}(\theta_{0})+\Big{[}\sum_{i\in
U}H_{i}^{\prime}(\theta_{0})\Big{]}(\hat{\theta}-\theta_{0})$

where $H_{i}^{\prime}(\theta_{0})=\partial
H_{i}(\theta_{0})/\partial\theta_{0}$. The sampling variance of $\hat{\theta}$
follows as

$V(\hat{\theta})\approx\Big{[}\sum_{i\in
U}H_{i}^{\prime}(\theta_{0})\Big{]}^{-1}\Big{[}\sum_{i,j\in
U}\Delta_{ij}H_{i}(\theta_{0})H_{j}(\theta_{0})^{\top}\Big{]}\Big{[}\sum_{i\in
U}H_{i}^{\prime}(\theta_{0})\Big{]}^{-1}$ (11)

where

$\Delta_{ij}=w_{i}w_{j}\Pr(\delta_{i}\delta_{j}=1)-1$

and

$\Pr(\delta_{i}\delta_{j}=1)=1-\Pr(s_{0}\cap F_{i,s}=\emptyset)-\Pr(s_{0}\cap
F_{j,s}=\emptyset)+\Pr\big{(}s_{0}\cap(F_{i,s}\cup F_{j,s})=\emptyset\big{)}$

##### Remark

The strategy consisting of $T$SBS and (10) is also applicable to the learning
of $\mu=Q_{\tau}c$. Let $s_{\tau}$ be the subset of seed sample $s$,
containing all the nodes for which $\nu_{i}^{\tau}$ defined by (5) is observed
under $T$SBS. Note that $s_{0}\subseteq s_{\tau}$ provided $T\geq\tau$, since
$\nu_{i}^{\tau}$ is always observed for any $i$ in $s_{0}$ under $\tau$SBS.
Let $F_{i,s}$ and the weight (10) be as defined above for any node $i\in
s_{\tau}$.

For an illustration, suppose $(T,\tau)=(3,2)$, where 3SBS starts from
$s_{0}=\\{i_{1}\\}$ in Figure 2. We have $i_{3}\not\in
s_{\tau}=\\{i_{1},i_{2}\\}$ because it is unclear if $\nu_{i_{3}}^{2}$ is
observed, now that $i_{4}$ is observed on the last wave and it is possible
that $i_{4}$ is adjacent to other yet unobserved nodes, which indeed is the
case here. The weight (10) can be calculated for
$F_{i_{1},s}=\\{i_{1},i_{2},i_{3}\\}$ and
$F_{i_{2},s}=\\{i_{1},i_{2},i_{3},i_{4}\\}$.

Clearly, the graph computation required for the learning of $\mu=Q_{\tau}c$ is
more complicated without ready-made software.

## References

  * [1] Avrachenkov, K., Ribeiro, B. and Towsley, D. (2010). Improving Random Walk Estimation Accuracy with Uniform Restarts. _Research report_ , RR-7394, INRIA. inria-00520350
  * [2] Frank O. and Snijders T. (1994). Estimating the size of hidden populations using snowball sampling. Journal of Official Statistics, 10:53-53.
  * [3] Friedkin, N.E. (1990). Social Networks in Structural Equation Models. Social Psychology Quarterly, 53:316-328.
  * [4] Goodman, L.A. (1961). Snowball sampling. Annals of Mathematical Statistics, 32:148-170.
  * [5] Leenders, R. (2002). Modeling social influence through network autocorrelation: constructing the weight matrix. Social Networks, 24:21-47.
  * [6] Masuda, N., Porter, M.A. and Lambiotte, R. (2017) Random walks and diffusion on networks. _Physics Reports_ , 716-717: 1-58.
  * [7] Ord, K. (1975). Estimation Methods for Models of Spatial Interaction. Journal of the American Statistical Association, 70:120-126.
  * [8] Zhang, L.-C. (2022). _Graph sampling._ CRC Press.
  * [9] Zhang, L.-C. (2021a). Graph sampling by lagged random walks. Stat, https://onlinelibrary.wiley.com/doi/abs/10.1002/sta4.444
  * [10] Zhang, L.-C. and Patone, M. (2017). Graph sampling. _Metron_ , 75:277-299.


Pierre-Antoine Bernard, Nicolas Crampé, Rafael Nepomechie, Gilles Parez, Luc
Vinet 11institutetext: Centre de Recherches Mathématiques and Département de
Physique,
Université de Montréal, P.O. Box 6128,
Centre-ville Station, Montréal (Québec), H3C 3J7, Canada.
11email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>22institutetext: Institut Denis-Poisson CNRS/UMR 7013
\- Université de Tours - Université d’Orléans,
Parc de Grandmont, 37200 Tours, France
22email<EMAIL_ADDRESS>33institutetext: Physics Department, PO Box
248046
University of Miami, Coral Gables, FL 33124 USA
33email<EMAIL_ADDRESS>44institutetext: IVADO, Montréal (Québec), H2S
3H1, Canada

# Entanglement of free-fermion systems, signal processing and algebraic
combinatorics

Pierre-Antoine Bernard 11 Nicolas Crampé 22 Rafael I. Nepomechie 33
Gilles Parez 11 Luc Vinet 1144

###### Abstract

This paper offers a review of recent studies on the entanglement of free-
fermion systems on graphs that take advantage of methods pertaining to signal
processing and algebraic combinatorics. On the one hand, a parallel with time
and band limiting problems is used to obtain a tridiagonal matrix commuting
with the chopped correlation matrix in bispectral situations and on the other,
the irreducible decomposition of the Terwilliger algebra arising in the
context of $P$-polynomial association schemes is seen to yield a simplifying
framework.

###### keywords:

Free fermions, graphs, entanglement, Heun operators, association scheme,
Terwilliger algebra

Dedicated to Gordon Semenoff on the occasion of his 70th birthday

##  1 Introduction

Quantifying the entanglement of quantum many-body problems is a meaningful
issue and free-fermion systems provide fertile ground for such studies.
Roughly speaking, the model is taken in its ground state, split in two parts
and the entanglement of one part relative to the other is explored. This
review offers a survey of some papers written on the subject by the authors
and collaborators over the recent years [1, 2, 3, 4, 5, 6, 7, 8].

##  2 Free fermions on weighted paths

We first consider fermionic chains with dynamics described as follows.

###  2.1 The Hamiltonian and its eigenstates

The system is an open chain of length $N+1$ described by the Hamiltonian

$H=\sum_{n=0}^{N-1}J_{n}(c_{n+1}^{\dagger}c_{n}+c_{n}^{\dagger}c_{n+1})-\sum_{n=0}^{N}B_{n}c_{n}^{\dagger}c_{n},\quad
J_{-1}=0,$ (1)

with the constants $J_{n}$ and $B_{n}$ real and positive and $c_{n}$,
$c_{n}^{\dagger}$ the fermionic operators obeying the anticommutation
relations:

$\\{c_{m},c_{n}^{\dagger}\\}=\delta_{m,n},\qquad\\{c_{m},c_{n}\\}=0,\qquad
m,n=0,\dots N.$ (2)

Let $\\{|n\rangle,\ n=0,\dots,N\\}$ be the orthonormal position basis made out
of the characteristic vectors $|n\rangle$ of $\mathbb{C}^{N+1}$. Introducing
the matrix $\Lambda$ defined by

$\Lambda|n\rangle=J_{n-1}|n-1\rangle-B_{n}|n\rangle+J_{n}|n+1\rangle,$ (3)

the Hamiltonian $H$ can be written in the form:
$H=\sum_{m,n=0}^{N}\Lambda_{mn}c_{m}^{\dagger}c_{n}$ with
$\Lambda_{mn}=\langle m|\Lambda|n\rangle$. Note that $\Lambda$ can be viewed
as the adjacency matrix of a weighted path with self-loops.

The eigenstates of $H$ are obtained by diagonalizing $\Lambda$. This brings
the orthonormal energy basis of $\mathbb{C}^{N+1}$:

$\\{|\omega_{k}\rangle,\
k=0,\dots,N\quad|\quad\Lambda|\omega_{k}\rangle=\omega_{k}|\omega_{k}\rangle\\}.$
(4)

We order the energies as $\omega_{k}\leqslant\omega_{k+1}$. Owing to (3) and
(4), the wavefunctions $\phi_{n}(k)=\langle n|\omega_{k}\rangle$ are expressed
in terms of orthogonal polynomials of a discrete variable. Under the canonical
transformation $\tilde{c}_{k}=\sum_{n=0}^{N}\phi_{n}(k)c_{n}$, the Hamiltonian
is brought in the form
$H=\sum_{k=0}^{N}\omega_{k}\tilde{c}_{k}^{\dagger}\tilde{c}_{k}$. With
$|0\rangle\\!\rangle$ the vacuum state defined by the property
$c_{n}|0\rangle\\!\rangle=0$ for $n=0,\dots,N$, we readily have

$H\tilde{c}_{k_{1}}^{\dagger}\dots\tilde{c}_{k_{m}}^{\dagger}|0\rangle\\!\rangle=\Big{(}\sum_{i=1}^{m}\omega_{k_{i}}\Big{)}\tilde{c}_{k_{1}}^{\dagger}\dots\tilde{c}_{k_{m}}^{\dagger}|0\rangle\\!\rangle.\
$ (5)

###  2.2 Correlations and entanglement

The ground state $|\Psi_{0}\rangle\\!\rangle$ is obtained by filling the Fermi
sea, that is by populating the vacuum with the excitations of energies up to
$\omega_{K}<\omega_{N}$ :
$|\Psi_{0}\rangle\\!\rangle=\tilde{c}_{0}^{\dagger}\dots\tilde{c}_{K}^{\dagger}|0\rangle\\!\rangle$.

The correlation matrix has elements

$\bar{C}_{mn}=\langle\\!\langle\Psi_{0}|c_{m}^{\dagger}c_{n}|\Psi_{0}\rangle\\!\rangle=\sum_{k=0}^{K}\phi_{m}(\omega_{k})\phi_{n}(\omega_{k}),\quad
m,n=0,\dots,N,$ (6)

thus showing that
$\bar{C}=\sum_{k=0}^{K}|\omega_{k}\rangle\langle\omega_{k}|$, in other words
that the correlation matrix $\bar{C}$ is the projector $\Pi_{E}$ on the
subspace of energy states in the Fermi sea.

In the following, we discuss entanglement between two complementary parts of
the chain. Part 1 consists of the sites $\\{0,1,\dots,\ell\\}$, and part 2,
the complement of part 1, is formed of the sites $\\{\ell+1,\dots,N\\}$. With
the full system in the ground state and thus described by the density matrix
$\rho=|\Psi_{0}\rangle\\!\rangle\langle\\!\langle\Psi_{0}|$, the entanglement
of part 1 with part 2 is completely accounted for by the reduced density
matrix
$\rho_{1}=\text{Tr}_{2}|\Psi_{0}\rangle\\!\rangle\langle\\!\langle\Psi_{0}|$,
where the trace is over the subspace of the Fock space generated by the
creation operators $c^{\dagger}_{i}$ associated to part 2, i.e., with
$i\in\\{\ell+1,\dots,N\\}$.

In the case of free-fermion chains, a considerable simplification [9] known as
the Peschel trick occurs; namely the reduced density matrix, here a
$2^{\ell+1}\times 2^{\ell+1}$ matrix, can be obtained from the chopped
correlation matrix $C$. This matrix is the restriction of the full correlation
matrix $\bar{C}$ to the subspace $S\subset\mathbb{C}^{N+1}$ spanned by the
vectors $\\{|0\rangle,\dots,|\ell\rangle\\}$ and thus, a
$(\ell+1)\times(\ell+1)$ matrix. If we denote by $\Pi_{S}$ the space projector
on $S$, in view of the observation made before about $\bar{C}$, we arrive at
the conclusion that the chopped correlation matrix $C$ is the key entity and
that it is given by the product of three projectors:
$C=\Pi_{S}\Pi_{E}\Pi_{S}$. Indeed, the (von Neuman) entanglement entropy
$\mathfrak{S}=-{\rm\text{Tr}}\,\rho_{1}\log\,\rho_{1}$ is given by [9]

$\mathfrak{S}=-{\rm Tr}\big{[}C\,\log\,C+(1-C)\,\log\,(1-C)\big{]}.$ (7)

###  2.3 A commuting (Heun) operator

To compute the entanglement entropy $\mathfrak{S}$ we hence need to
diagonalize the chopped correlation matrix $C=\Pi_{S}\Pi_{E}\Pi_{S}$. As a
rule, this is a full matrix with eigenvalues near 0, a feature that does not
facilitate a numerical treatment. We here wish to stress a useful observation,
namely that for a class of fermionic chains, there exists a tridiagonal matrix
$T$ with a well-behaved spectrum and such that $[T,C]=0$, see [10, 1, 2].

Such occurrences are particularly opportune because $T$ shares its
eigenvectors with $C$ and is easier to diagonalize (numerically). We shall now
discuss situations when such a commuting operator is present and indicate how
it can be obtained.

The key is bispectrality. If the constants $J_{n}$ and $B_{n}$ in the
Hamiltonian $H$ are such that the orthogonal polynomials arising in the
wavefunctions $\phi_{n}(k)$ belong to the Askey scheme [11], these
wavefunctions are bispectral. (Note that there are many such choices.) In
these cases, there is an operator $X$ on $\mathbb{C}^{N+1}$ that is diagonal
in the position basis and tridiagonal in the energy basis; that is, there is
an $X$ such that

$X|n\rangle=\lambda_{n}|n\rangle,\qquad
X|\omega_{k}\rangle=\bar{J}_{k-1}|\omega_{k-1}\rangle-\bar{B}_{k}|\omega_{k}\rangle+\bar{J}_{k}|\omega_{k+1}\rangle.$
(8)

This follows from the fact that $\phi_{n}(k)=\langle n|\omega_{k}\rangle$,
being bispectral, obeys a difference equation of the form

$\lambda_{n}\phi_{n}(k)=\bar{J}_{n-1}\phi_{n}(k-1)-\bar{B}_{k}\phi_{n}(k)+\bar{J}_{k}\phi_{n}(k+1),$
(9)

in addition to the three term recurrence relation that is implied by the
reciprocal action of the operator $\Lambda$ in the two bases:

$\Lambda|\omega_{k}\rangle=\omega_{k}|\omega_{k}\rangle,\qquad\Lambda|n\rangle=J_{n-1}|n-1\rangle-
B_{n}|n\rangle+J_{n}|n+1\rangle.$ (10)

Under such circumstances, the commuting operator can be obtained as follows.
To all bispectral problems, one may associate a so-called algebraic Heun
operator defined as the most general bilinear expression in the two bispectral
operators [12]. For simplicity, we shall here consider a special case and the
operator

$\bar{T}=\\{X,\Lambda\\}+\mu X+\nu\Lambda,$ (11)

where the scalars $\mu$ and $\nu$ are for the moment unspecified. Clearly,
$\bar{T}$ is tridiagonal in both the position and the energy bases. From the
specific action of $\bar{T}$ in these bases, it is not difficult to see that
by choosing for $\mu$ and $\nu$ the values

$\mu=-(\omega_{K}+\omega_{K+1}),\quad\quad\nu=-(\lambda_{\ell}+\lambda_{\ell+1}),$
(12)

$\bar{T}$ preserves the subspace S and the one spanned by the energy
eigenvectors belonging to the Fermi sea. With T the restriction to $S$ of
$\bar{T}$, it follows that $[T,\Pi_{S}]=[T,\Pi_{E}]=0$ and hence that
$[T,C]=0$ since $C=\Pi_{S}\Pi_{E}\Pi_{S}$.

This result stems from a striking parallel [13, 14] with the celebrated
treatment [15] by Slepian et al. of the time and band limiting problem in
signal processing. This deserves a short digression. The central and
prototypical question is: how to best concentrate in a time interval $-T\leq
t\leq T$ a signal $f(t)$ which is limited to a frequency band $[-W,W]$? This
is in principle answered by looking for the eigenfunctions of the integral
operator $G$ with the sinc kernel, namely by solving

$GF(p)=\int_{-W}^{W}dp^{\prime}\frac{\sin(p-p^{\prime})T}{\pi(p-p^{\prime})}F(p^{\prime})=\lambda
F(p).$ (13)

Note that $G$ can also be written as the product of three projector:
$G=\Pi_{W}^{p}\widetilde{\Pi}_{T}^{p}\Pi_{W}^{p}$ with
$\Pi_{L}^{x}g(x)=[\Theta(x+L)-\Theta(x-L)]g(x)$, $\widetilde{\Pi}_{T}^{p}$ the
Fourier transform of $\Pi_{T}^{t}$ and $\Theta(x)$ the Heavyside function.

This should be the end of the story but G, a non-local operator, proves also
intractable numerically. The way out came from the remarkable discovery [15]
that the spheroidal wave operator

$D=\frac{1}{2}\Big{\\{}\frac{d^{2}}{dp^{2}},p^{2}\Big{\\}}-W^{2}\frac{d^{2}}{dp^{2}}+T^{2}p^{2}\
$ (14)

commutes with G. This result can be obtained [12] from the rather obvious
observation that the Fourier function $e^{ipx}$ are solutions to a simple
bispectral problem with $\frac{d^{2}}{dp^{2}}$ and $p^{2}$ playing the roles
of $\Lambda$ and $X$ in the scenario described before. The parameters of the
Heun operator are here also fixed by demanding that the commutators with the
projectors $\Pi_{W}^{p}$ and $\widetilde{\Pi}_{T}^{p}$ be equal to 0.

The parallel between the entanglement analysis of free-fermion chains and the
band and time limiting problem is thus quite clear. The filling of the Fermi
sea in the construction of the ground state corresponds to the band limiting.
Splitting space in two parts and restricting to one is akin to time limiting.
The main problem regarding the fermionic chain is to diagonalize the chopped
correlation matrix $C=\Pi_{S}\Pi_{E}\Pi_{S}$ while in the band and time
limiting case, it is to diagonalize the integral operator
$G=\Pi_{W}^{p}\widetilde{\Pi}_{T}^{p}\Pi_{W}^{p}$. The understanding that the
existence of a commuting operator is rooted in underlying bispectral problems
leads then in both contexts, to a simple identification of this operator from
the respective algebraic Heun operators.

###  2.4 A non-homogeneous example: the Krawtchouk chain

A nice example of a chain with bispectral features arises for the following
choice of parameters:

$J_{n}=\sqrt{(N-n)(n+1)p(1-p)},\quad B_{n}=-(Np-n(1-2p)),\quad p\in[0,1].$
(15)

In this case $\omega_{k}=\lambda_{k}=k$ and the wavefunctions are given as
follows in terms of Krawtchouk polynomials (the ${{}_{2}}F_{1}$ part in the
formula below) [11]:

$\phi_{n}(k)=(-1)^{n}\sqrt{p^{n+k}(1-p)^{N-n-k}\binom{N}{n}\binom{N}{k}}\;{{}_{2}}F_{1}\;\left({-n,-k\atop-N};\frac{1}{p}\right).$
(16)

Note that $B_{n}$ is a constant for $p=1/2$. In this case, the non-zero matrix
elements $T_{mn}=T_{nm}$ of the symmetric commuting operator are given by [1]:

$T_{n,n}=\frac{N}{2}(2n-2\ell-1)-n(2K+1),\quad
T_{n-1,n}=(n-\ell-1)\sqrt{n(N-n+1)}.$ (17)

As for the entanglement entropy for the half chain and at half filling it is
well approximated by111Note that in (18) we fixed a small sign typo from the
original publication [6]. [6]:

$\mathfrak{S}=\frac{1}{6}\log\frac{N+1}{2}+a(p)-\frac{1}{2(N+1)}\frac{\cos(\frac{\pi}{2}\frac{N+1}{m(p)})}{\sin(\frac{\pi}{2m(p)})}+\dots$
(18)

where

$m(p)=\frac{1}{2}\left(1-\log p+\frac{1-\log 2}{2p}\right)\,,$ (19)

and $a(p)$ is a non-universal constant with respect to $N$.

##  3 Free fermions on graphs

We now consider free fermions on higher dimensional non-oriented graphs. Let
$V=\\{v_{0},\dots,v_{D}\\}$ be the set of vertices and $E\subset V\times V$,
the set of edges. The orthonormal canonical basis
$\\{|v_{0}\rangle,\dots,|v_{D}\rangle\\}$ will be referred to as the position
basis with the vector $|v_{i}\rangle$ associated to the vertex $v_{i}$. The
$(D+1)\times(D+1)$ symmetric adjacency matrix $A$ has entries given by

$A_{ij}=\langle
v_{i}|A|v_{j}\rangle=\begin{cases}1\quad\text{if}\quad(v_{i},v_{j})\in E\\\
0\quad\text{otherwise}.\end{cases}$ (20)

The Hamiltonian $\mathcal{H}$ is taken to be
$\mathcal{H}=\sum_{m,n=0}^{D}A_{m,n}c_{m}^{\dagger}c_{n}$ where $c_{n}$ and
$c_{n}^{\dagger}$ are the usual fermionic operators at $v_{n}$. Thus the
adjacency matrix (made out of only $0$s and ${1}$s) plays a role similar to
the matrix $\Lambda$ introduced in the description of fermionic chains. We
shall focus below on a natural family of graphs.

###  3.1 The hypercube and the Krawtchouk chain

In the case of the hypercube $Q_{N}$ in $N$ dimensions, $V=\\{0,1\\}^{\otimes
N}$; that is, the vertices are strings of $N$ bits. Two vertices
$v_{i},v_{j}\in V$ are linked if they differ by only one entry, i.e., if they
are at Hamming distance $d(v_{i},v_{j})=1$. The case $N=1$ corresponds to the
complete graph (where all vertices are connected to one another) with two
vertices $K_{2}$. In general, $Q_{N}$ is the $N$-fold Cartesian product of
$K_{2}$, i.e. $Q_{N}=(K_{2})^{\square N}$.

Let us now establish a connection between the system consisting of fermions on
the hypercube and the Krawtchouk chain. Pick $0=(0,\dots,0)$ as a reference
point on $Q_{N}$. Organize $V$ in columns $V_{n}=\\{x\in V\;|\;d(0,x)=n\\}$
made out of all vertices at distance $n=0,\dots,N$ of $0$. It is easy to see
that $k_{n}=\text{Card}(V_{n})=\binom{N}{n}$. Let us label the vertices in the
column $V_{n}$ by $V_{nm},m=1,\dots,k_{n}$ and form the $n$-qbit Dicke or
column vector states:

$|col\;n\rangle=\frac{1}{\sqrt{k_{n}}}\sum_{m=1}^{k_{n}}|V_{nm}\rangle.$ (21)

It is easy to see [16, 17] that $\langle
col\;n+1|\;A\>|col\;n\rangle=\sqrt{(n+1)(N-n)}$ which is equal to twice the
expression of $J_{n}$ for the Krawtchouk chain when $p=\frac{1}{2}$ as per
(15). In other words, for $\Lambda$ corresponding to the Krawtchouk chain with
$p=\frac{1}{2}$, we have $\langle col\;n+1|\>A\;|col\>n\rangle=2\;\langle
n+1|\;\Lambda\>|n\rangle$. When $p=\frac{1}{2}$, the diagonal term in the
Hamiltonian of the Krawtchouk chain does not depend on $n$ and thus yields a
global constant that can be subtracted; we hence find that up to an overall
multiplicative factor the hypercube system projects to the $p=\frac{1}{2}$
Krawtchouk chain. The reason for this is that $Q_{N}$ is a distance-regular
graph, implying that each vertex in column $V_{n}$ is connected to the same
number of vertices in the column $V_{n+1}$ and vice versa. This observation
suggests that the entanglement properties of free fermions on the hypercube
bear a relation with those of the Krawtchouk chain. This connection can
further be understood in terms of association schemes. The hypercube $Q_{N}$
is part of the family of graphs on $V$ consisting of those where it is the
vertices at Hamming distance $0$, $1$, or $2$, up to $N$ that are connected by
an edge. These are the graphs of the (binary) Hamming association scheme that
have adjacency matrices whose action is closed on the space spanned by the
column vector states. We discuss these constructs more generally next.

###  3.2 Association schemes

An important concept in algebraic combinatorics is that of (symmetric)
$d$-class association schemes [18] which can be considered as ensembles of
$d+1$ undirected graphs on a set of vertices $V$ with cardinality $|V|$
satisfying certain axioms. Such an ensemble of graphs may be seen as colorings
of the edges of the complete graph with $d$ colors. In terms of the
corresponding adjacency matrices $A_{i},\ i=0,\dots,d$, the axioms are
equivalent to

$\sum_{i=0}^{d}A_{i}=J,\quad A_{0}=I,\quad A_{i}=A_{i}^{T},\quad
A_{i}A_{j}=\sum_{k=0}^{d}p_{ij}^{k}A_{k},$ (22)

where $J$ is the all $1$ matrix, $I$ the identity and $p_{ij}^{k}$ integers
referred to as the intersection numbers. The commutative $d+1$ algebra thus
generated by the adjacency matrices is called the Bose-Mesner algebra. Since
the symmetric adjacency matrices all commute, they can be diagonalized
simultaneously and admit the spectral decomposition

$A_{i}=\sum_{j=0}^{d}\theta_{i}(j)E_{j},\qquad
E_{i}=\frac{1}{|V|}\sum_{j=0}^{d}\theta_{i}^{*}(j)A_{j},$ (23)

with $E_{j}$ the idempotents projecting on the eigenspaces
($E_{i}E_{j}=\delta_{ij}E_{i}$ and $\sum_{i=0}^{d}E_{i}=I).$ Finally, it is
known that the distance matrices of distance regular graphs lead in a one-to-
one way to association schemes that are $P$-polynomial in that
$A_{i}=p_{i}(A_{1})$ for $p_{i}$ a polynomial of degree $i$. We shall often
assume this situation to hold in the following. Dually, an association scheme
is called $Q$-polynomial if there is an ordering such that its primitive
idempotents $E_{i}$ are given as polynomials of degree $i$ of $E_{1}$ (under
the entry-wise product).

###  3.3 The Terwilliger algebra and the correlation matrices

An algebra introduced by Terwilliger [19] and extending the Bose-Mesner one
can be attached to an association scheme and is relevant to our entanglement
studies. Its definition requires picking a reference vertex $v_{0}$ and
introducing the dual matrices $A_{i}^{*}$ and $E_{i}^{*}$ as the diagonal
matrices with entries:

$[A_{i}^{*}(v_{0})]_{vv}=|V|[E_{i}]_{v_{0}v},\qquad[E_{i}^{*}(v_{0})]=[A_{i}]_{v_{0}v}.$
(24)

Note that $E_{i}^{*}E_{j}^{*}=\delta_{ij}E_{i}^{*}$ and that $E_{i}^{*}$
projects on the position subspace spanned by the vectors $|v\rangle$
corresponding to vertices connected to $v_{0}$ in the graph with adjacency
matrix $A_{i}$, i.e., the column space at distance $i$ from $v_{0}$. Recall
that $E_{i}$ projects on the energy eigenspaces of the adjacency matrices that
intervene in the Hamiltonians. The Terwilliger algebra $\mathfrak{T}$ is
generated by the adjacency matrices $\\{A_{0},\dots,A_{d}\\}$ and their duals
$\\{A_{0}^{*},\dots,A_{d}^{*}\\}$ or equivalently by the sets of projectors
$\\{E_{0},\dots,E_{d}\\}$ and $\\{E_{0}^{*},\dots.E_{d}^{*}\\}$.

It is appropriate to remark at this point that the entanglement analysis of
fermions on graphs proceeds much as for fermion chains. The ground state is
defined by filling the vacuum state $|0\rangle\\!\rangle$ with the excitations
corresponding to a subset $SE$ of the eigenvalues $\theta(j)$ of the adjacency
matrix A (or of combination) chosen for Hamiltonian. The correlation matrix
$\bar{C}$ is given by

$\bar{C}=\sum_{j}E_{j}=\Pi_{SE}\quad\text{for}\quad\theta(j)\in SE.$ (25)

The bipartition of the vertices (or positions) $V$ into $SV$ (part 1) and its
complement (part 2) is typically be done by picking columns at the successive
distances from $0$ to $\ell<d$ with respect to a vertex $v_{0}$. Since
$E_{i}^{*}=\sum_{v|d(v_{0},v)=i}|v\rangle\langle v|$, the projector on the
position vectors of part 1 is $\Pi_{SV}=\sum_{i=0}^{\ell}E_{i}^{*}$ and the
chopped correlation matrix thus reads $C=\Pi_{SV}\Pi_{SE}\Pi_{SV}$. It follows
that this matrix $C$ that needs to be diagonalized actually represents an
element of the Terwilliger algebra $\mathfrak{T}$, a point worth underscoring.

A natural strategy to carry out the entanglement analysis of fermions on
graphs of ($P$\- and $Q$\- polynomial) association schemes thus presents
itself: (i) Identify the Terwilliger algebra $\mathfrak{T}$ for the scheme;
(ii) Decompose the regular representation of $\mathfrak{T}$ on
$\mathbb{C}^{|V|}$ into its irreducible components and as a result; (iii)
Simplify the diagonalization of $C$ by working on irreducible subspaces. This
last step can further be aided by the presence of a commuting operator
belonging also to $\mathfrak{T}$. For $P$\- and $Q$\- polynomial schemes,
$\mathfrak{T}$ is generated by $A_{1}=A$ and $A_{1}^{*}=A^{*}$ solely as all
the others matrices are polynomials of one or the other. The energy and
position bases are respectively the eigenbases of $A$ and $A^{*}$. The action
of each of these elements in the eigenbasis of the other is block tridiagonal.
This implies that the overlaps between the two bases (the wavefunctions) are
solutions of bispectral problems. Considering therefore the (generalized)
algebraic Heun operator $\bar{T}=\\{A,A^{*}\\}+\mu A^{*}+\nu A$, it is
possible to find $\mu$ and $\nu$ so that
$[\bar{T},\Pi_{SV}]=[\bar{T},\Pi_{SE}]=0$ and hence $[\bar{T},C]=0$.

###  3.4 Entanglement on graphs of the (binary) Hamming scheme

Let us bring as an example the celebrated Hamming scheme which was referred to
at the end of the subsection on the hypercube. It is known to be $P$\- and
$Q$\- polynomial with the self-dual Krawtchouk polynomials arising in the
expression of the (dual) adjacency matrices in terms of $A$ and $A^{*}$. These
two matrices hence generate $\mathfrak{T}$ which we easily recognize to be the
Lie algebra $\mathfrak{su}(2)$. By applying the definitions of the adjacency
matrix and its dual for $K_{2}$, it is seen that:

$A=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}=\sigma_{x},\qquad
A^{*}=\begin{pmatrix}1&0\\\ 0&-1\end{pmatrix}=\sigma_{z},$ (26)

where $\sigma_{x}$ and $\sigma_{z}$ are the usual notation for the Pauli
matrices. Since as already noted, the hypercube $Q_{d}=(K_{2})^{\square d}$ it
follows that in this case:

$A=\sum_{i=0}^{d-1}\underbrace{I\otimes\dots\otimes
I}_{i}\otimes\>\sigma_{x}\otimes I\dots\otimes I,\quad
A^{*}=\sum_{i=0}^{d-1}\underbrace{I\otimes\dots\otimes
I}_{i}\otimes\>\sigma_{z}\otimes I\dots\otimes I.$ (27)

This corresponds to the diagonal embedding of $\mathfrak{su}(2)$ into
$\mathfrak{su}(2)^{\otimes d}$ with $A$ and $A^{*}$ resulting from the
repeated application of the coproduct. The underlying representation is of
course very well known. As anticipated, when part 1 is made out of columms the
irreducible decomposition reduces the entanglement characterization problem on
the graph to a combination of Krawtchouk chains, one of which being the chain
discussed in Section 3.1.

##  4 Conclusion

The connections that have been highlighted between the entanglement analysis
of fermionic systems, signal processing and algebraic combinatorics have been
put to use in a variety of contexts but many avenues still remain to be
explored. The entanglement of free fermions on the Hamming, Johnson, Hadamard
and folded cube graphs have been examined [3, 4, 5, 8]. It would certainly be
worth determining what other schemes [20] such as the dual polar [21] or
Grassmann ones entail. In some cases the irreducible decompositions of the
regular representation of the Terwilliger algebras have not yet been spelled
out. $P$-multivariate association schemes and their graph descriptions are
currently generating much interest [22, 23, 24, 25]. Examining beyond the
initial studies [6] the entanglement of fermionic systems built upon those
structures should warrant attention. Finally, the bearing of graph symmetries
on the entanglement properties of free fermions on these graphs is certainly a
question that we plan to study in the future.

## Acknowledgments

LV is grateful to the organizers of the conference at the CRM in honour of
Gordon Semenoff for having invited him to be part of this celebration.

PAB holds an Alexander-Graham-Bell scholarship from the Natural Sciences and
Engineering Research Council of Canada (NSERC). NC is partially supported by
the IRP AAPT of CNRS. RN enjoys funding from the National Science Foundation
under Grant No. PHY 2310594. GP holds a FRQNT and a CRM–ISM postdoctoral
fellowship, and acknowledges support from the Mathematical Physics Laboratory
of the CRM. The research of LV is funded in part by a Discovery Grant from
NSERC.

## References

  * [1] Crampé, N. Nepomechie, R., Vinet, L.: Free-Fermion entanglement and orthogonal polynomials. Journal of Statistical Mechanics 093101 (2019)
  * [2] Crampé, N., Nepomechie, R., Vinet, L.: Entanglement in Fermionic Chains and Bispectrality. Reviews in Mathematical Physics 33(7) (2021)
  * [3] Bernard, P.-A., Crampé, N., Vinet, L.: Entanglement of free fermions on Hamming graphs. Nuclear Physics B986 116061 (2023)
  * [4] Bernard, P.-A., Crampé, N., Vinet, L.: Entanglement of free fermions on Johnson graphs. Journal of Mathematical Physics 64 061903 (2023)
  * [5] Crampé, N., Guo, K., Vinet, L.: Entanglement of Free Fermions on Hadamard Graphs. Nuclear Physics B 360 115176 (2020)
  * [6] Bernard, P.-A., Crampé, N., Nepomechie, R., Parez, G., Poulain d’Andecy, L., Vinet, L.: Entanglement of inhomogeneous free fermions on hyperplane lattices. Nuclear Physics B 984 115975 (2022)
  * [7] Parez, G., Bernard, P.-A., Crampé, N., Vinet, L.: Multipartite information of free fermions on Hamming graphs. Nuclear Physics B 990 116157 (2023)
  * [8] Bernard, P.-A., Mann, Z., Parez, G., Vinet, L.: Absence of logarithmic enhancement in the entanglement scaling of free fermions on folded cubes. Journal of Physics A: Math. Theor. 57 015002 (2024)
  * [9] Peschel, I.: Calculation of reduced density matrices from correlation functions. Journal of Physics A: Math. Gen. 36 L205 (2003)
  * [10] Eisler, V., Peschel, I.: Properties of the entanglement Hamiltonian for free-fermion chains. Journal of Statistical Mechanics 104001 (2018)
  * [11] Koekoek, R. Lesky, P.A., Swarttouw, R.F.: Hypergeometric Orthogonal Polynomials and Their q-Analogues. Springer (2010)
  * [12] Grünbaum, F. A., Vinet, L., Zhedanov, A.: Algebraic Heun Operator and Band-Time Limiting. Communications in Mathematical Physics 364 1041 (2018)
  * [13] Gioev, D., Klich, I.: Entanglement Entropy of Fermions in Any Dimension and the Widom Conjecture. Physical Review Letters 96 100503 (2006)
  * [14] Eisler, V., Peschel, I.: Free-fermion entanglement and spheroidal functions. Journal of Statistical Mechanics 04028 (2013)
  * [15] Slepian, D.: Some comments on Fourier analysis, uncertainty and modeling. SIAM Review 25 379 (1983)
  * [16] Christandl, M., Datta, N., Ekert, A., Landahl, A. J.: Perfect state transfer in quantum spin networks. Physical Review Letters 92 187902 (2004)
  * [17] Bernard, P.-A., Chan, A., Loranger, E., Tamon, C., Vinet, L.: A graph with fractional revival. Physics Letters A 382 259 (2018)
  * [18] Bannai, E., Bannai, E., Ito, T., Tanaka, R.: Algebraic Combinatorics. De Gruyter (2021)
  * [19] Terwilliger, P.: The subconstituent algebra of an association scheme. Journal of Algebraic Combinatorics (Part I) 1 363 (1992), (Part II) 2 73 (1993), (Part III) 2 177 (1993)
  * [20] Brouwer, A. E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Springer (1989)
  * [21] Bernard, P.A., Crampé, N., Vinet, L.: The Terwilliger of symplectic dual polar graphs, the subspace lattices and $\mathcal{U}_{q}(sl_{2})$. Discrete Mathematics 12 113169 (2023)
  * [22] Bernard, P.A., Crampé, N., Poulain d’Andecy, L. Vinet, L., Zaimi, M.: Bivariate $P$-polynomial association schemes. arXiv:2212.10824 (2022)
  * [23] Bannai, E., Kurihara, H., Zhao, D., Zhu, Y.: Multivariate $P$ and/or $Q$-polynomial association schemes. arXiv:2305.00707v2 (2023)
  * [24] Crampé, N., Vinet, L. Zaimi, M., Zhang, X.: A bivariate $Q$-polynomial structure for the non-binary Johnson scheme. arXiv:2306.01882 (2023)
  * [25] Bernard, P.-A., Crampé, N., Vinet, L., Zaimi, M., Zhang, X.: $m$-distance-regular graphs and their relation to multivariate $P$-polynomial association schemes. arXiv:2309.16016


[table]capposition=top

# GSVNet: Guided Spatially-Varying Convolution for Fast Semantic Segmentation
on Video

###### Abstract

This paper addresses fast semantic segmentation on video. Video segmentation
often calls for real-time, or even faster than real-time, processing. One
common recipe for conserving computation arising from feature extraction is to
propagate features of few selected keyframes. However, recent advances in fast
image segmentation make these solutions less attractive. To leverage fast
image segmentation for furthering video segmentation, we propose a simple yet
efficient propagation framework. Specifically, we perform lightweight flow
estimation in 1/8-downscaled image space for temporal warping in segmentation
outpace space. Moreover, we introduce a guided spatially-varying convolution
for fusing segmentations derived from the previous and current frames, to
mitigate propagation error and enable lightweight feature extraction on non-
keyframes. Experimental results on Cityscapes and CamVid show that our scheme
achieves the state-of-the-art accuracy-throughput trade-off on video
segmentation.

##  1 INTRODUCTION

Video semantic segmentation is a compute-intensive vision task. It aims at
classifying pixels in video frames into semantic classes. This task often has
real-time or even faster than real-time requirements in data-center
applications, in order to process hours-long videos in a much shorter time.
The ever increasing video resolution in both spatial and temporal dimensions
makes real-time processing even more challenging.

A simple approach to video segmentation is to adopt image-based processing;
that is, to process individual video frames independently using an off-the-
shelf image segmentation network. This approach was once considered
prohibitively expensive, given that most image segmentation networks, like
DeepLabv3+ [1], usually optimized the feature extraction for segmentation
accuracy rather than throughput.

To address the prolonged feature extraction, several fast video segmentation
frameworks are proposed. One common recipe is to propagate features of few
selected keyframes, in order to conserve computation for feature extraction on
subsequent non-keyframes [2, 3]. This is motivated by the high correlation
between consecutive video frames. Due to the evolution of video content in the
temporal dimension, some [4, 5] additionally introduce lightweight feature
extraction, followed by fusion of spatio-temporal features [4, 5], for non-
keyframes to cope with scene changes or dis-occlusion. Others propose adaptive
keyframe selection [6, 5] or bi-directional feature propagation [7] for
alleviating error propagation. Meanwhile, Xu et al.[6] perform adaptive
inference for cropped regions with scene changes.

However, recent advances in fast image segmentation [8, 9, 10] make video-
based solutions less attractive. For example, BiSeNet [8] and SwiftNet [9] can
now process high-definition ($2048\times 1024$) videos at 40 to 60 frames per
second on modern graphics processing units (GPU) while achieving reasonably
good segmentation accuracy. A question that arises is whether video-based
approaches can benefit from these advanced image segmentation networks. The
answer relies crucially on how to address the following challenges. First, the
increasing spatial resolution of videos may render optical flow estimation too
expensive. Second, the excessive amount of channels in feature space may make
the propagation of features time-consuming. Third, the feature extraction for
non-keyframes has to be even more lightweight. Lastly, errors resulting from
imperfect flow estimation and feature extraction may be propagated along the
temporal dimension.

To tackle these issues, we propose a simple yet efficient propagation
framework, termed GSVNet, for fast semantic segmentation on video. Our
contributions include: (1) to conserve computation for temporal propagation,
we perform lightweight flow estimation in 1/8-downscaled image space for
warping in segmentation outpace space; and (2) to mitigate propagation error
and enable lightweight feature extraction on non-keyframes, we introduce a
guided spatially-varying convolution for fusing segmentations derived from the
previous and current frames.

Experimental results on Cityscapes [11] show that when working with BiSeNet
[8] and SwiftNet [9], our scheme can process up to 142 high-definition
($2048\times 1024$) video frames per second on GTX 1080Ti with $71.8\%$
accuracy in terms of Mean Intersection over Union (mIoU). It achieves the
state-of-the-art accuracy-throughput trade-off on video segmentation and can
readily work with any off-the-shelf fast image segmentation network.

##  2 RELATED WORK

Image Semantic Segmentation: Image semantic segmentation models [1, 12] have
achieved great success in segmentation accuracy by incorporating sophisticated
feature extractors and task decoders [1, 12]. To achieve better accuracy-
throughput trade-offs, recent research [13, 8, 10] has been focused on making
feature extractors lightweight and less sensitive to the adaptation of input
resolution. To this end, Yu et al. [8] introduce a cost-effective feature
extractor by including a spatial path for preserving spatial details and a
context path for capturing contextual information in a wide receptive field.
In another attempt, Orsic et al. [9] take the advantage of transfer learning
by using pre-trained encoder on ImageNet and adopting a simple upsampling
decoder with lateral connections.

Video Semantic Segmentation: Efficient video segmentation is another active
research area. Unlike images, consecutive video frames usually have a high
correlation or similarity. To conserve computation for feature extraction,
several works leverage the temporal correlation between video frames to reuse
features of selected keyframes on non-keyframes. Shelhamer et al. [2] employ
features at different stages of the network from previous frames. For feature
propagation, Zhu et al. [3] use optical flow estimated by a flow network,
while Li et al. [5] adopt spatially variant convolution. [4, 5] additionally
introduce lightweight feature extraction for non-keyframes together with
spatio-temporal feature fusion, to reduce error propagation arising from scene
changes or warping errors. However, the emergence of lightweight image
segmentation calls for a careful rethink of these strategies. Specifically,
the feature extraction on non-keyframes must be even more lightweight and the
extracted features must be used to their fullest potential to mitigate error
propagation.

Fig. 1: Illustration of our proposed propagation framework, where $m_{i}$ is
the optical flow map, $N$ denotes the image-based segmentation network and
$\mathcal{PF}$ indicates our propagation network. Fig. 2: Architecture diagram
of the proposed propagation network $\mathcal{PF}$.

##  3 METHOD

This work addresses the problem of efficient semantic segmentation on video.
Given an input video consisting of a set $\\{I_{t}\\}_{t=0}^{N-1}$ of video
frames, each being of dimension $3\times H\times W$, our task is to predict
for every video frame $I_{t}$ its downscaled, semantic segmentation
$\hat{S}_{t}\in\mathbb{R}^{C\times H/8\times W/8}$ with $C$ classes, aiming to
strike a good balance between accuracy and throughput. Following common
practice, the final segmentation is obtained by upsampling $\hat{S}_{t}$ to
the full resolution, where the segmentation accuracy is measured.

###  3.1 System Overview

Fig. 1 illustrates our proposed method for efficient semantic segmentation on
video. The process begins by segmenting the first keyframe to obtain its
semantic segmentation $\hat{S}_{0}$ with an image-based segmentation network
$\mathcal{N}$. Our propagation framework $\mathcal{PF}$ then propagates
temporally the segmentation $\hat{S}_{0}$ (respectively, $\hat{S}_{t-1}$) of
the previous step to assist in predicting the segmentation $\hat{S}_{1}$
(respectively, $\hat{S}_{t}$) for the current non-keyframe $I_{1}$
(respectively, $I_{t}$). The process repeats until the next keyframe is
reached.

###  3.2 Spatiotemporal Propagation Framework

Fig. 2 shows the pipeline of our segmentation propagation framework
$\mathcal{PF}$. Starting with the downscaled segmentation
$\hat{S}_{t-1}\in\mathbb{R}^{C\times H/8\times W/8}$ for the previous frame
$I_{t-1}$, we (1) perform temporal (backward) warping of $\hat{S}_{t-1}$ based
on the optical flow $m_{t}\in\mathbb{R}^{2\times H/8\times W/8}$ to arrive at
an initial estimate $\hat{S}_{t}^{-}\in\mathbb{R}^{C\times H/8\times W/8}$ of
the downscaled segmentation for the current frame $I_{t}$. It is obvious that
not every semantic prediction in $\hat{S}_{t}^{-}$ is reliable. The errors can
propagate along the temporal dimension through the warping process. Moreover,
the optical flow $m_{t}$ may be error-prone due to dis-occlusion or imperfect
flow estimation. We thus (2) refine the warped segmentation $\hat{S}_{t}^{-}$
by applying a guided spatially-varying convolution. This is achieved in three
sequential steps. The first convolves the $\hat{S}_{t}^{-}$ with several
ideal-delay kernels $\theta_{1},\theta_{2},\ldots,\theta_{D}$, yielding
$\\{f_{t,d}^{s}\\}_{d=1}^{D},f_{t,d}^{s}\in\mathbb{R}^{C\times H/8\times
W/8}$. The second arranges $\\{f_{t,d}^{s}\\}_{d=1}^{D}$ together with a crude
estimate $f_{t}^{i}\in\mathbb{R}^{C\times H/8\times W/8}$ of the current
frame’s segmentation from a lightweight network into $C$ chunks, each
concatenating the channels of the same index from
$\\{f_{t,d}^{s}\\}_{d=1}^{D}$ and $f_{t}^{i}$. The last applies a spatially-
varying $1\times 1$ convolution across the channels of each of these $C$
chunks, with their results concatenated together to form our downscaled
estimate $\hat{S}_{t}\in\mathbb{R}^{C\times H/8\times W/8}$ of the current
frame’s segmentation.

###  3.3 Temporal Segmentation Warping

This very first step performs temporal warping of $\hat{S}_{t-1}$ to arrive at
an initial estimate $\hat{S}_{t}^{-}$ of the current frame’s segmentation. In
symbols, we have

$\hat{S}_{t}^{-}(c,x,y)=\hat{S}_{t-1}(c,x+m_{t}^{(x)}(x,y),y+m_{t}^{(y)}(x,y)),\forall
c\in C\vspace{0.25em}$ (1)

where $(x,y),1\leq x\leq W/8,1\leq y\leq H/8$ denotes pixel locations in the
downscaled segmentation and $m_{t}=(m_{t}^{(x)},m_{t}^{(y)})$ is the optical
flow describing the backward motion from $I_{t}$ to $I_{t-1}$ also in the
downscaled domain, and is estimated by a lightweight optical flow network $O$
based on the hierarchical feature fusion block. More details of this flow
network can be found in the supplementary document. Performing temporal
warping in the 1/8-downscaled domain is motivated by two observations. First,
lowering the spatial resolution can significantly reduce the runtime costs of
both optical flow estimation and temporal warping. Second, the 1/8 downscaling
factor is chosen empirically to match common practice in most segmentation
network design that the final high-resolution segmentation is usually
recovered by interpolating the network output by a factor of 8.

###  3.4 Guided Spatially-Varying Convolution

To correct unreliable segmentation predictions in $\hat{S}_{t}^{-}$, we resort
to a guided spatially-varying filtering. This operation serves as a means to
propagate spatially within $\hat{S}_{t}^{-}$ the segmentation predictions from
reliable regions to unreliable ones. Apparently, in what direction the
propagation should be performed to correct the erroneous prediction at a pixel
depends on the error pattern in its local neighborhood. As such, our filtering
kernel is designed to be both context- and pixel-adaptive.

####  3.4.1 Spatial Propagation with Ideal-delay Kernels

Such spatial propagation starts by convolving the temporally warped
segmentation $\hat{S}_{t}^{-}$ with several ideal-delay kernels
$\theta_{1},\theta_{2},\ldots,\theta_{D}$. As a result of the convolution,
each of these kernels shifts the $\hat{S}_{t}^{-}$ channel-wise by one pixel
or more in a certain direction. When viewed from each pixel’s perspective,
these shifting operations line up its surrounding semantic predictions as
potential candidates for propagation. For implementation, we consider each
ideal-delay kernel as a 3-D tensor of size $1\times K\times K$, where $K$
indicates the propagation range measured in the maximum horizontal or vertical
displacement of the unit impulse from the origin. It is then convolved with
$\hat{S}_{t}^{-}$, also regarded as a 3-D tensor, using 3-D convolution
$\otimes$ to get $f_{t,d}^{s}=\hat{S}_{t}^{-}\otimes\theta_{d}$, where
$f_{t,d}^{s}\in\mathbb{R}^{C\times H/8\times W/8}$, $d=1,2,\ldots,D$.

####  3.4.2 Lightweight Intra-frame Segmentation

Recognizing that there may be areas in a video frame where new image contents
emerge or our spatial propagation may not work well, we further develop a
lightweight network $\varphi$ for segmentation in these areas. The former is
also known as the dis-occluded areas; the latter is because our spatial
propagation is susceptible to the errors of the previous frame’s segmentation
and the optical flow estimation. The module is showed in the upper branch of
Fig. 2. Since these areas normally represent only a small percentage of pixels
in a video frame, we design $\varphi$ for low complexity, with its prediction
accuracy focused on those error-prone areas. Our current implementation
comprises only 3 convolutional layers with kernel size $3\times 3$ without
resolution downscaling. As shown in Fig. 2, it takes as input the
1/8-downscaled current video frame and outputs the segmentation
$f_{t}^{i}=\varphi(\hat{S}_{t}^{-}),f_{t}^{i}\in\mathbb{R}^{C\times H/8\times
W/8}$.

####  3.4.3 Guided Dynamic Filtering

Given $\\{f_{t,d}^{s}\\}_{d=1}^{D}$ and $f_{t}^{i}$ from the previous two
steps, the guided dynamic filtering forms a semantic prediction of every pixel
by spatially-varying $1\times 1$ filtering. To proceed, we first organize
$\\{f_{t,d}^{s}\\}_{d=1}^{D}$ and $f_{t}^{i}$ into $C$ chunks. Each chunk
concatenates the channels of the same semantic class from
$\\{f_{t,d}^{s}\\}_{d=1}^{D}$ and $f_{t}^{i}$; that is, the resulting channels
of a chunk correspond to semantic predictions of the same class yet shifted
spatially from $\hat{S}_{t}^{-}$ in different directions. We then use a
guiding network $G$ to produce the $1\times 1$ kernel for every pixel. In
particular, this kernel varies from one pixel location to another, determining
dynamically how the spatial propagation is conducted at every pixel location
or whether the intra-frame segmentation should be weighted more heavily.

The process is illustrated in the lower and right parts of Fig. 2. For
implementation, the guiding network $\Gamma_{t}=G(f_{t}^{i},E_{t})$ takes as
inputs $f_{t}^{i}$ and $E_{t}$, where $E_{t}=\sigma(\hat{S}_{t}^{-}\otimes M)$
is an edge map derived from convolving $\hat{S}_{t}^{-}$ with a Laplacian
kernel $M$. In particular, before the convolution, we take the argmax
operation with respect to $\hat{S}_{t}^{-}$ to keep only the structure
information inherent in the segmentation map. The output of the convolution is
further passed through a Sigmoid function $\sigma$ to clip the edge response.
This design is inspired by the observation that $\hat{S}_{t}^{-}$ tends to be
erroneous at the object boundaries and in regions where the structure contour
of $\hat{S}_{t}^{-}$ is inconsistent with that of $f_{t}^{i}$, which captures
rough semantic predictions. Finally, the network output
$\Gamma_{t}\in\mathbb{R}^{(D+1)\times H/8\times W/8}$ is the $1\times 1$
kernel for every pixel location $(x,y),1\leq x\leq W/8,1\leq y\leq H/8$. The
filtering of every chunk then follows by evaluating

$\hat{S}_{t,c}(x,y)=\hat{\Gamma}_{t}(x,y)\odot chunk_{t,c}(x,y),\forall
c,x,y\vspace{0.25em}$ (2)

where $\hat{\Gamma}_{t}(x,y)$ denotes the normalized kernel at $(x,y)$ that
has a unity gain across channels and $\odot$ is the inner product. The
filtered results, when pooled together, form the final segmentation output
$\hat{S}_{t}$.

We train the propagation framework $\mathcal{PF}$ end-to-end. The training
objective involves an ordinary cross-entropy loss imposed on the final
segmentation output.

##  4 EXPERIMENTS

###  4.1 Setup

Datasets: We validate our method on Cityscapes [11] and CamVid [14], the
datasets for scene understanding. Cityscapes includes video snippets of urban
scenes, of which 2975/500/1525 are for training/validation/test. Each snippet
of resolution $2048\times 1024$ is 30 frames long, with only the 20th frame
annotated. CamVid has 4 video sequences. In each video, only one frame in
every 30 frames is annotated, leading to a total of 701 labeled video frames
of size $960\times 720$. Among these video frames, 367/101/233 are for
training/validation/test.

Accuracy Metrics: For evaluating the segmentation accuracy, we follow the
protocol in [3, 4] to measure the Mean Intersection over Union (mIoU) over $l$
image pairs $(20-i,20)$ in every snippet with $i=0,1,\ldots,l-1$. For each
image pair $(a,b)$, we propagate the segmentation for frame $a$ (keyframe)
recursively to frame $b$ (non-keyframe). The mIoU measured this way is known
as the average mIoU. We also report the minimum mIoU measured with respect to
the non-keyframe farthest away from the keyframe in every snippet, i.e. the
non-keyframe that is expected to be impacted the most by error propagation in
the temporal dimension. Unless otherwise stated, the keyframe interval $l$ is
defaulted to 5. Note that all the mIoU numbers reported are measured at full
resolution.

Complexity Metrics: For complexity assessment, we report the throughput in
frames per second (FPS) on GTX 1080Ti, the number of network parameters in
bytes, and the average number of floating-point operations per second (FLOPS)
over a keyframe interval.

Implementation Details: We implement our network on Pytorch, and use pre-
trained SwiftNet-R18 [9], termed SN-R18 or BiSeNet-R18, termed BN-R18, as the
segmentation model for keyframes. Both SN-R18 and BN-R18 adopt the ResNet-18
backbone. At inference time, the size of the keyframe is downscaled for the
best accuracy-throughput trade-off. By the same token, our propagation module
operates at one-eighth the resolution of the input video frame, followed by an
interpolation of the segmentation output to the full resolution for mIoU
measurement. Similar to [3, 4], we train our network for keyframe intervals
ranging from 1 to 5. We use stochastic gradient descent (SGD) with momentum
0.9 and a learning rate of 0.002, which is decreased by a factor of 0.992
every 100 iterations. We set the batch size to 8 and the weight decay to
0.0005.  Our model, exclusive of the pre-trained SwiftNet-R18 or BiSeNet-R18
for keyframe segmentation, is then trained end-to-end over image patches
cropped from the input image. Each patch is three quarters of the input size.

###  4.2 Results

Accuracy-throughput Trade-off: Table 1 compares the accuracy-throughput trade-
offs of the competing methods. As shown, at FPS around 130, Ours-BN-R18
($l=4$) outperforms BiSeNet-R18 with input size 0.5 by 2.3% mIoU. Likewise,
Ours-SN-R18 ($l=4$) surpasses SwiftNet-R18 with input size 0.5 by 3.1% mIoU.
Comparing with the video-based methods like [2, 4, 6], our scheme achieves
much higher FPS and mIoU. In particular, Ours-SN-R18 ($l=2$) outpaces
considerably [5, 15], which target also high throughput, in FPS at the cost of
a modest drop in mIoU. Results on Camvid [14] (Table 3) show that our method
runs faster than the image-based schemes [8] while achieving higher or
comparable mIoU. It is to be noted that the other video-based schemes can
hardly compete with ours in FPS, although [15] has higher mIoU due to the use
of better backbones.

Network Parameters and FLOPS: Table 2 compares the number of network
parameters and FLOPS. As can be seen, our scheme introduces 1.6M additional
network parameters for segmenting non-keyframes, representing less than
$3.3\%$ additional overhead relative to image-based segmentation with
SwiftNet-R18 or BiSeNet-R18. It achieves the least number of FLOPS, with a FPS
of 142 and 71.8$\%$ average mIoU. In particular, the FLOPS of our scheme is
variable depending on the keyframe interval. On average, a non-keyframe
requires 2.8G FLOPS, as compared to 58.5G FLOPS for processing a keyframe with
SwiftNet-R18 (0.75). As such, the higher the keyframe interval, the lower the
FLOPS.

Method | Input | Avg. | FPS
---|---|---|---
| size | mIoU |
CLK [2] | 1.0 | 64.4 | 6.3
LVS-LLS [5] | 1.0 | 75.9 | 8.4
Accel-R18 [4] | 1.0 | 72.1 | 2.2
DVSNet [6] | 1.0 | 63.2 | 30.3
TD-BN-R18 [15] | 1.0 | 75.0 | 47
Fast-SCNN [10] | 0.5 | 68.6 | 123.5
BiSeNet-R18 [8] | 0.75 | 73.7 | 62
BiSeNet-R18 [8] | 0.5 | 68.9 | 131
SwiftNet-R18 [9] | 0.75 | 74.4 | 63.2
SwiftNet-R18 [9] | 0.5 | 68.7 | 134
Ours-BN-R18 (l=2) | 0.75 | 72.9 | 98.5
Ours-BN-R18 (l=3) | 0.75 | 72.0 | 123.4
Ours-BN-R18 (l=4) | 0.75 | 71.2 | 140
Ours-SN-R18 (l=2) | 0.75 | 73.6 | 100
Ours-SN-R18 (l=3) | 0.75 | 72.6 | 125
Ours-SN-R18 (l=4) | 0.75 | 71.8 | 142
Table 1: Accuracy and throughput comparison on Cityscapes dataset. The l specifies the keyframe interval. The input size indicates the downscaling factor for keyframes in the video-based schemes or for input images in the image-based schemes. Method | Input | FPS | Key | Non-key | FLOPS
---|---|---|---|---|---
| size |  | params | params |
BiSeNet-R18 | 0.75 | 62.0 | 49.0M | - | 58.0G
SwiftNet-R18 | 0.75 | 63.2 | 47.2M | - | 58.5G
SwiftNet-R18 | 0.5 | 134 | 47.2M | - | 26.0G
Ours-SN-R18 (l=4) | 0.75 | 142 | 47.2M | 1.6M | 16.7G
Table 2: Complexity comparison in terms of network parameters, FLOPS and FPS. Table 3: Accuracy and FPS comparison on CamVid test set. Method | Input | Avg. | FPS
---|---|---|---
| size | mIoU |
Accel [4] | 1.0 | 66.7 | 7.58
TD-PSP18 [15] | 1.0 | 71.0 | 25
TD-PSP50 [15] | 1.0 | 74.7 | 10
BiSeNet-R18 [8] | 0.75 | 66.6 | 142
BiSeNet-R18 [8] | 0.5 | 60.7 | 232
Ours-BN-R18 (l=2) | 0.75 | 65.9 | 210
Ours-BN-R18 (l=3) | 0.75 | 64.8 | 250
$80$$90$$100$$110$$120$$130$$140$$150$$62$$64$$66$$68$$70$$72$$74$Throughput (FPS)Avg. mIoU ($\%$)OursOurs-FlowNetA-Lite Fig. 3: Comparison of accuracy-throughput curves. A-Lite adopts the same flow network and feature extractor as ours. Ours-FlowNet uses FlowNet2s for flow estimation. |  | Keyframe interval
---|---|---
Metric | Intra Feature | 1 | 2 | 3 | 4 | 5
Min. | with | 74.4 | 72.9 | 70.7 | 69.6 | 67.7
mIoU | without | 74.4 | 72.1 | 69.1 | 67.4 | 65.1
Table 4: Accuracy comparison between models with and without the use of the current frame’s features (intra features). The accuracy is measured in minimum mIoU over a keyframe interval to emphasize the worst case. GT |  |  |
---|---|---|---
(a) |  |  |
(b) |  |  |
(c) |  |  |
| k+1 | k+2 | k+3
Fig. 4: Qualitative evaluation: (a) Ours-SN-R18 (0.75), (b) A-Lite, and (c)
SwiftNet-R18 (0.5). From left to right, each column with index k + n shows the
segmentation results for a video frame that is n steps after the keyframe k.
Note that only the last frame (k+3) has the ground-truth segmentation.

###  4.3 Ablation Experiments

This section aims at dissecting our design to understand better the
contributions of each component.

Using Lightweight Flow Estimation and Feature Extraction in A-R18: Fig. 3
shows that Accel-R18, when trained end-to-end with our lightweight flow
estimation network and feature extractor (a scheme termed A-Lite), suffers
from a significant mIoU drop, although its throughput is much improved (red
vs. cyan curves). This stresses the novelty of our guided dynamic filtering.
Also shown in Fig. 3 is that using FlowNet2s [16] in our framework has little
impact on mIoU (blue vs. green curves). This however causes the throughput to
reduce considerably, due to the prolonged runtime for flow estimation.

Discarding Intra Features: Intra features refer to the features extracted from
the current frame. They serve the purposes of guiding the $1\times 1$ dynamic
filtering and refining the semantic predictions propagated from the previous
frame. Table 4 shows that discarding these intra features causes the minimum
mIoU to drop much faster along with the increasing keyframe interval,
highlighting their necessity for mitigating error propagation.

###  4.4 Qualitative Evaluation

Fig. 4 presents qualitative evaluation. For a fair comparison, all the
competing models are configured to have a similar throughput (120 to 140 FPS).
Because of lightweight temporal propagation, video-based methods can afford
higher-accuracy keyframe segmentation, e.g. SwiftNet-R18 (0.75) in our method
and BiSeNet-R18 (0.75) in A-Lite.y We adopt A-Lite instead of A-X39 for
comparison as it is the only version of Accel that achieves a similar
throughput to the others. It is seen that our method produces consistently
better segmentations across video frames (see the poles especially in the top-
left area) than SwiftNet-R18 (0.5). In addition, A-Lite suffers from seriously
distorted object boundaries. More qualitative results can be found in our
supplementary document.

##  5 CONCLUSION

This paper presents a simple propagation framework for efficient video
segmentation. We show that it is more cost-effective to perform warping in
segmentation output space than in feature space. This also allows the
propagation error to be minimized at each time step by our guided spatially-
varying convolution. Our scheme has the striking feature of being able to work
with any off-the-shelf fast image segmentation network to further video
segmentation.

##  6 ACKNOWLEDGEMENT

We are grateful to the National Center for High performance Computing for GPU
resources. This project is supported by MOST 108-2634-F-009-007 through
Pervasive AL Research (PAIR) Labs, National Chiao Tung University, Taiwan.

## References

  * [1] Liang-Chieh Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam,  “Encoder-decoder with atrous separable convolution for semantic image segmentation,”  in ECCV, 2018.
  * [2] Evan Shelhamer, Kate Rakelly, Judy Hoffman, and Trevor Darrell,  “Clockwork convnets for video semantic segmentation,”  in ECCV, 2016.
  * [3] Xizhou Zhu, Yuwen Xiong, Jifeng Dai, Lu Yuan, and Yichen Wei,  “Deep feature flow for video recognition,”  in CVPR, 2017.
  * [4] Samvit Jain, Xin Wang, and Joseph E. Gonzalez,  “Accel: A corrective fusion network for efficient semantic segmentation on video,”  in CVPR, 2019.
  * [5] Yule Li, Jianping Shi, and Dahua Lin,  “Low-latency video semantic segmentation,”  in CVPR, 2018.
  * [6] Yu-Syuan Xu, Tsu-Jui Fu, Hsuan-Kung Yang, and Chun-Yi Lee,  “Dynamic video segmentation network,”  in CVPR, 2018.
  * [7] Samvit Jain and Joseph E Gonzalez,  “Fast semantic segmentation on video using block motion-based feature interpolation,”  in ECCV Workshops, 2018.
  * [8] Changqian Yu, Jingbo Wang, Chao Peng, Changxin Gao, Gang Yu, and Nong Sang,  “Bisenet: Bilateral segmentation network for real-time semantic segmentation,”  in ECCV, 2018.
  * [9] Marin Orsic, Ivan Kreso, Petra Bevandic, and Sinisa Segvic,  “In defense of pre-trained imagenet architectures for real-time semantic segmentation of road-driving images,”  in CVPR, 2019.
  * [10] Rudra P K Poudel, Stephan Liwicki, and Roberto Cipolla,  “Fast-scnn: Fast semantic segmentation network,”  in BMVC, 2019.
  * [11] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele,  “The cityscapes dataset for semantic urban scene understanding,”  in CVPR, 2016.
  * [12] Hengshuang Zhao, Jianping Shi, Xiaojuan Qi, Xiaogang Wang, and Jiaya Jia,  “Pyramid scene parsing network,”  in CVPR, 2017.
  * [13] Sachin Mehta, Mohammad Rastegari, Anat Caspi, Linda Shapiro, and Hannaneh Hajishirzi,  “Espnet: Efficient spatial pyramid of dilated convolutions for semantic segmentation,”  in ECCV, 2018.
  * [14] Gabriel J. Brostow, Jamie Shotton, Julien Fauqueur, and Roberto Cipolla,  “Segmentation and recognition using structure from motion point clouds,”  in ECCV, 2008.
  * [15] Ping Hu, Fabian Caba, Oliver Wang, Zhe Lin, Stan Sclaroff, and Federico Perazzi,  “Temporally distributed networks for fast video semantic segmentation,”  in CVPR, 2020.
  * [16] Eddy Ilg, Nikolaus Mayer, Tonmoy Saikia, Margret Keuper, Alexey Dosovitskiy, and Thomas Brox,  “Flownet 2.0: Evolution of optical flow estimation with deep networks,”  in CVPR, 2017.

##  Appendix A Accuracy-throughput Trade-off

Fig. A5 compares the accuracy-throughput curves of the competing methods. To
trade lower accuracy for higher throughput, the keyframe interval is altered
from 1 to 5 for A-X39 and the two variants of our scheme111The keyframe
interval 1 corresponds to image-based segmentation., while for the image-based
methods, the input image is downscaled by a factor of 1, 0.75, 0.6, and 0.5,
followed by an interpolation of the segmentation output to the full
resolution.

Fig. A6 presents more accuracy-throughput curves by choosing BiSeNet (1.0) and
SwiftNet (1.0) for keyframe segmentation. This shows that our scheme can work
with these image segmentation networks under different settings to offer a
wide variety of accuracy-throughput trade-offs. As mentioned in the main
paper, it can readily work with any off-the-shelf image segmentation network.

##  Appendix B More Ablation Experiments

###  B.1 Replacing Ideal-delay Kernels with Learned Kernels.

Table A5 indicates that little gain can be achieved by replacing the $3\times
3$ ideal-delay kernels with learned kernels. Our reasoning is that the same
net effect may be obtained by adapting the following $1\times 1$ dynamic
convolution kernels.

###  B.2 Enlarging Ideal-delay Kernels.

Table A6 further shows that enlarging the size of the ideal-delay kernels,
equivalently allowing longer-distance spatial propagation, brings modest mIoU
gain at the cost of lower throughput. For this experiment, we learn the
kernels end-to-end since for the $5\times 5$ case, only 17 out of 25 possible
ideal-delay patterns are used for initialization and for maintaining high FPS.
We attribute the result to the fact that our flow propagation network operates
in the 1/8-downscaled domain (cp. Fig. 6 in the main paper). The $3\times 3$
kernel size covers already a large enough receptive field in the full-
resolution image space.

###  B.3 Edge Map Analysis

In the main paper (Section 3.4.3 Guided Dynamic Filtering), we conjecture that
the warped segmentation $\hat{S}_{t}^{-}$ tends to be erroneous at the object
boundaries and propose to provide the edge map $E_{t}$ derived from
$\hat{S}_{t}^{-}$ as the guiding signal for dynamic filtering. Fig. A7
validates our conjecture by showing the high correlation between the edge map
and the error map (indicating the segmentation errors on $\hat{S}_{t}^{-}$).

$30$$40$$50$$60$$70$$80$$90$$100$$110$$120$$130$$140$$150$$160$$66$$68$$70$$72$$74$$76$Throughput (FPS)Avg. mIoU ($\%$)Ours-BiSeNet-R18A-X39BiSeNet-X39Ours-SwiftNet-R18BiSeNet-R18SwiftNet-R18EDANetFast-SCNN$30$$40$$50$$60$$70$$80$$90$$100$$110$$120$$130$$140$$150$$160$$66$$68$$70$$72$$74$$76$Throughput (FPS)Min. mIoU ($\%$)(A6)(A6) Fig. A5: Comparison of accuracy-throughput curves evaluated on Cityscapes validation set. The dashed lines correspond to image-based methods, where different accuracy-throughput trade-offs are achieved by adapting the input resolution with factors {1, 0.75, 0.6, 0.5}. EDANet, Fast-SCNN, and BiSeNet-X39 have an input scaling factor of 0.5, 1, and 0.75, respectively. The solid lines are video-based methods with a variable keyframe interval ranging from 1 to 5. For keyframe segmentation, ours-BiSeNet-R18 and ours-SwiftNet-R19 adopt BiSeNet-R18 (0.75) and SwiftNet-R18 (0.75), respectively. Likewise, A-X39 uses BiSeNet-R18 (0.75). The mIoU is evaluated at full resolution without regard to the input scaling factor. $30$$40$$50$$60$$70$$80$$90$$100$$110$$120$$130$$140$$150$$160$$68$$70$$72$$74$$76$Throughput (FPS)Avg. mIoU ($\%$)Ours-BN-R18 (0.75)Ours-BN-R18 (1.0)Ours-SN-R18 (0.75)Ours-SN-R18 (1.0)$30$$40$$50$$60$$70$$80$$90$$100$$110$$120$$130$$140$$150$$160$$66$$68$$70$$72$$74$$76$Throughput (FPS)Min. mIoU ($\%$)(A6)(A6) Fig. A6: Comparison of accuracy-throughput curves. |  | Keyframe interval
---|---|---
Metric |  Scheme | 1 | 2 | 3 | 4 | 5
Avg. |  IDK | 74.4 | 73.7 | 72.6 | 71.8 | 70.9
mIoU ($\%$) |  IDK+Finetune | 74.4 | 73.6 | 72.6 | 71.8 | 70.9
Table A5: Accuracy comparison between models with ideal-delay kernels and fine-tuned kernels for various keyframe intervals. IDK: Ideal-delay Kernel. Kernel |  $\\#$ of | Avg. | Min. | FPS
---|---|---|---|---
size |  filters | mIoU ($\%$) | mIoU ($\%$) |
3 $\times$ 3 |  9 | 70.9 | 67.7 | 155
5 $\times$ 5 |  17 | 71.1 | 67.9 | 144
Table A6: Impact of the size of the ideal-delay kernels on accuracy and throughput. The mIoU is measured at the keyframe interval of 5. |
---|---
(a) Edge map | (b) Error map
Fig. A7: Comparison between the edge map $E_{t}$ and the error map, which
indicates the errors on the temporally warped segmentation $\hat{S}_{t}^{-}$.
Fig. A8: The architecture of our lightweight optical flow network. The red,
blue, and green blocks each output 64, 32, and 2 channels, respectively.
Except for the gray and green blocks, the other blocks all include $3\times 3$
convolutional layers followed by batch normalization and LeakyReLU with a
slope factor of 0.1.

##  Appendix C Lightweight Optical Flow Network

Fig. A8 details the architecture of our lightweight optical flow network $O$.
It is built based on the hierarchical feature fusion block (HFFB), initially
proposed for image super resolution. It first concatenates two input frames,
$I_{t-1}$ and $I_{t}$, followed by passing them through two $3\times 3$
convolutional layers with stride 2. The resulting feature maps are then input
to HFFB, which consists of 4 convolutional layers with dilation 1, 2, 4, and
8. The outputs of these convolutional layers are added and pooled
hierarchically as illustrated in the figure. Finally, a $3\times 3$
convolution is applied to get a downscaled flow map $m_{t}$, which is
interpolated bilinearly to the resolution of one-eighth of the resolution of
input image.

##  Appendix D Inference Runtime

We apply a breakdown analysis of inference runtime on non-keyframe
segmentation for A-X39 and our scheme in Fig. A9. The operation of non-
keyframe segmentation is divided into four major parts: (1) optical flow
estimation, (2) temporal warping in the feature or segmentation output space,
(3) feature extraction from the current video frame, and (4) fusion of
features or segmentation predictions. The runtimes of the three image-based
methods (i.e. BiSeNet-X39, BiSeNet-R18, and SwiftNet-R18), which turn non-
keyframes into keyframes for processing, are provided as monolithic quantities
for comparison.

Several observations can be made from Fig. A9. First, A-X39 runs slower than
all the image-based schemes, including BiSeNet-R18, i.e. the network used for
keyframe segmentation in A-X39. Careful examination of A-X39 suggests that the
additional operations needed for flow estimation and temporal warping outweigh
its runtime reduction from the use of the lightweight feature extractor in
BiSeNet-X39. This explains our earlier finding that increasing non-keyframes
in A-X39 leads to a slight decrease in throughput. Second, the runtime of
A-X39 is still dominated by the feature extraction from the current frame. In
contrast, our lightweight flow estimation network consumes only about one-
third of the runtime of FlowNet2s [16] in A-X39. Moreover, performing temporal
warping in the segmentation output space (ours) consumes much less time than
in the feature space (A-X39). This is because temporal warping is a memory-
intensive operation. Although the feature space in the present case has a
spatial resolution (of $64\times 128$) that is 4 times smaller than the
segmentation output space (of size $128\times 256$), it has 256/19=13.4 times
more channels, thereby leading to a 3.3 times increase in data to be moved
around. Third, our feature extraction from the current frame represents only a
small portion of the entire inference runtime, and is much simpler than that
of A-X39. The improvement comes from downscaling the input image by a factor
of 1/8 and using only 3 convolutional layers for feature extraction (cp. Fig.
2 in the main paper). Our ablation study, however, shows that without the
guided dynamic filtering (Section 3.4 in the main paper), A-X39 cannot benefit
from such a lightweight feature extractor. This also explains why the fusion
of segmentation predictions through guided dynamic filtering constitutes a
major source of complexity in our scheme.

Last but not least, the runtime distribution of our propagation framework
justifies the aim of conserving computation for feature extraction from the
current frame through exploiting temporal correlation between video frames.

$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$Ours-SwiftNet-R18A-X39SwiftNet-R18
(0.75)BiSeNet-R18 (0.75)BiSeNet-X39Time (ms)Flow estimationTemporal
warpingFeature extractionFeature/Segmentation fusion Fig. A9: A breakdown
analysis of inference runtime.
---
(a)
(b)
Fig. A10:  Qualitative evaluation on Cityscapes demo video ($k$ = 77) for
keyframe interval 4. (a) and (b) correspond to index $k$ and $k+1$
respectively, where $k+n$ denotes the $n$th non-keyframe following keyframe
$k$
---
(a)
(b)
Fig. A11:  Qualitative evaluation on Cityscapes demo video ($k$ = 77) for
keyframe interval 4. (a) and (b) correspond to index $k+2$ and $k+3$
respectively, where $k+n$ denotes the $n$th non-keyframe following keyframe
$k$
---
(a)
(b)
Fig. A12:  Qualitative evaluation on Cityscapes demo video ($k$ = 121) for
keyframe interval 4. (a) and (b) correspond to index $k$ and $k+1$
respectively, where $k+n$ denotes the $n$th non-keyframe following keyframe
$k$
---
(a)
(b)
Fig. A13:  Qualitative evaluation on Cityscapes demo video ($k$ = 121) for
keyframe interval 4. (a) and (b) correspond to index $k+2$ and $k+3$
respectively, where $k+n$ denotes the $n$th non-keyframe following keyframe
$k$
---
(a)
(b)
Fig. A14:  Qualitative evaluation on Cityscapes demo video ($k$ = 261) for
keyframe interval 4. (a) and (b) correspond to index $k$ and $k+1$
respectively, where $k+n$ denotes the $n$th non-keyframe following keyframe
$k$
---
(a)
(b)
Fig. A15:  Qualitative evaluation on Cityscapes demo video ($k$ = 261) for
keyframe interval 4. (a) and (b) correspond to index $k+2$ and $k+3$
respectively, where $k+n$ denotes the $n$th non-keyframe following keyframe
$k$
---
(a)
(b)
Fig. A16:  Qualitative evaluation on Cityscapes demo video ($k$ = 481) for
keyframe interval 4. (a) and (b) correspond to index $k$ and $k+1$
respectively, where $k+n$ denotes the $n$th non-keyframe following keyframe
$k$
---
(a)
(b)
Fig. A17:  Qualitative evaluation on Cityscapes demo video ($k$ = 481) for
keyframe interval 4. (a) and (b) correspond to index $k+2$ and $k+3$
respectively, where $k+n$ denotes the $n$th non-keyframe following keyframe
$k$