# Optimal transport distances for directed, weighted graphs: a case study with
cell-cell communication networks

###### Abstract

Comparing graphs by means of optimal transport has recently gained significant
attention, as the distances induced by optimal transport provide both a
principled metric between graphs as well as an interpretable description of
the associated changes between graphs in terms of a transport plan. As the
lack of symmetry introduces challenges in the typically considered
formulations, optimal transport distances for graphs have mostly been
developed for undirected graphs. Here, we propose two distance measures to
compare directed graphs based on variants of optimal transport: (i) an earth
movers distance (Wasserstein) and (ii) a Gromov-Wasserstein (GW) distance. We
evaluate these two distances and discuss their relative performance for both
simulated graph data and real-world directed cell-cell communication graphs,
inferred from single-cell RNA-seq data.

Index Terms—  Directed graphs, graph distances, optimal transport, cell-cell
communication networks

##  1 Introduction

Exploring the similarities between graphs is a crucial primitive for comparing
patterns in complex networks. A large variety of distance measures between
graphs exist, often based on comparing features derived from (algebraic
representations) of the graph structures. Examples include distance measures
based on spectral features, the computation of certain subgraph statistics
such as graphlets [1] or graph kernels [2]. While the comparison of such graph
features is powerful, it often does not provide a notion of where precisely
one graph differs from another, or an insight about how two graphs align,
respectively.

Optimal transport based graph distances [3, 4], which have risen to prominence
recently, and address these challenges. In a nutshell, OT-based graph
distances associate with each graph a certain probability distribution. Two
graphs can then be compared by finding a transport plan (a mapping) between
those two probability distributions with the minimal transport cost [5]. The
transport plan associated with the minimal cost can then be used to provide an
interpretable and robust alignment of the two graphs considered, highlighting
the changes between the graphs relevant to the computed distance.

To date, most OT-based methods for measuring network similarities have been
proposed for undirected graphs. In many applications, however, we are
interested in comparing directed graphs. Yet, extending OT-based distances to
directed graphs is not simple, as a _symmetric_ distance metric, typically
derived from the distances between nodes in the graph, is required within the
cost function(s) typically employed within OT. To address this problem, here
we consider two node-to-node distances, which have been developed for directed
graphs, namely, the Generalized Effective Resistance (GRD) [6] and Markov
chain hitting time (HTD) [7]. Employing these distance measures enables us to
compute OT-based graph distances even for directed graphs. Specifically, we
explore the use of these metrics for both Wasserstein (Earth Mover) and
Gromov-Wasserstein based OT distances for graphs [5].

Having established our OT-based distances framework for directed graphs, we
evaluate the relative performance of the proposed distance measures in the
context of clustering cell-cell communication networks which arise in the
study of single-cell sequencing data. These networks are intrinsically
directional and provide a challenging test case, as technical artifacts such
as data dropouts (e.g., missing connections and entities), outliers, and noise
are often present in those [8].

Contributions (i) We present and evaluate two OT formulations (Wasserstein and
Gromov Wasserstein) to compare directed graphs based on two node-to-node
distances for directed graphs, namely, the Markov chain hitting time [7] and
the Generalized Effective Resistance [6] (ii) We evaluate proposed approaches
with simulated directed stochastic block models and on a case study of patient
cell-cell communication networks.

Outline The remainder of the paper is structured as follows. We briefly
outline some related work in Section 2. In Section 3, we then discuss two
node-to-node distance measures for directed graphs, that we employ to
formulate two optimal transport distances between directed graphs. We
illustrate the utility of these different formulations in Section 4, in which
we provide some numerical illustrations of these distances for synthetic and
real world data. We close with a short discussion outlining future work.

##  2 Related work

Optimal transport distances between graphs. One of the earliest OT-based
distances for comparing undirected graphs considers vectorial embeddings of
the graph adjacency matrices and then computes graph similarities using a
Wasserstein metric (earth movers’ distance) between the embeddings [9]. A
different perspective is taken by Graph Optimal Transport (GOT) [3]. Here, the
pseudoinverse of the graph Laplacian is assumed to correspond to the
covariance of a multivariate Gaussian distribution, and a multivariate
Gaussian OT problem [10] is then solved to define the distance between two
graphs.

In the context of directed graph, far fewer distances between graphs exists.
Recently, Silva and collaborators [11] have explored the use of Wasserstein
distances between distributions of directed graphlets to compare directed
graphs. Other OT formulations for the comparison of directed graphs are based
on Gromov-Wasserstein formulations (GWOT) [12, 13], where the node-to-node
distances within the graph are transported instead of the node embeddings.

Node-to-node distance metrics for directed graphs When considering undirected
graphs, the most commonly adopted node distance measures are the shortest-path
distance, or the resistance distance [14]. For directed graphs, defining a
distance measure between nodes becomes a nontrivial task, however, due to the
non-symmetric nature of the graph. In the following, we leverage two
formulations for a directed distance measure between nodes in a graph to
define an optimal transport distance between graphs. By considering the Markov
Chain associated with a directed weighted graph, Young and collaborators [6]
extended the resistance distance to directed and weighted graphs. A related
formulation has been provided by [7], that introduced a node-to-node pseudo-
metric based on Markov Chain Hitting times.

##  3 Methods

In this section, we define two distance measures between _directed, weighted
graphs_ based on optimal transport theory. We consider a setup in which we are
confronted with a set of directed weighted graphs
$\\{\mathcal{G}^{1},...,\mathcal{G}^{p}\\}$ where each $\mathcal{G}^{i}$
denotes a digraph $\mathcal{G}^{i}=(\mathcal{V}^{i},\mathcal{E}^{i},w^{i})$
consisting of a node set $\mathcal{V}$ a set of directed edges
$\mathcal{E}^{i}\subset\mathcal{V}\times\mathcal{V}$ and an associated non-
negative weight function $w^{i}:\mathcal{E}\rightarrow\mathbb{R}_{\geq}0$.

Our task is now to defined a distance function
$d(\mathcal{G}^{k},\mathcal{G}^{l})$ between any two those graphs by means of
optimal transport. To obtain a well-defined optimal transport problem we to
define a geometry according to which the transport cost can be computed. In
the following, we describe two ways to obtain such a geometry from directed
weighted graphs, specifically from node-to-node distance metrics defined for
directed graphs. We then employ these two node-to-node distances within two
different optimal transport formulations to compare directed weighted graphs,
yielding in total 4 possible distance measures.

###  3.1 Node-to-Node distances for directed graphs

####  3.1.1 Generalized Effective Resistance Distance (GRD)

The effective resistance or resistance distance is a well known distance
metric for nodes within undirected networks [15, 16]. To derive the resistance
distance for undirected graphs, we consider a graph as resistor network, where
the weight of each edge corresponds to a conductance. The resistance distance
between two nodes $i$ and $j$ in the graph is then equal to the potential
difference that is induced by injecting a unit current between two nodes [15,
16].

Formally, let $A\in\mathbb{R}^{N\times N}$ be the adjacency matrix of a graph
with $N$ nodes, with entries $A_{ij}=w_{ij}$ equal to the weight $w_{ij}$ of
the edge from node $i$ to $j$, and $A_{ij}=0$ otherwise. The Laplacian of the
graph is then given as $L=D-A$, where $D=\text{diag}(A\mathbf{1})$ is the
diagonal matrix of (weighted) node degrees. The (square root of the)
resistance distance between node $i$ and $j$ can then be computed as [15, 16]:

$r_{ij}=\sqrt{(e_{i}-e_{j})^{\top}L^{\dagger}(e_{i}-e_{j})},$ (1)

where $L^{\dagger}$ denotes the Moore-Penrose pseudoinverse of the Laplacian,
and $e_{i},e_{j}$ are the $N$ dimensional indicator vectors associated to node
$i$ and node $j$, respectively.

To generalize this notion of effective resistance to directed graphs, we now
consider the following formulation, due to Young et al. [17, 6]. Let
$Q\in\mathbb{R}^{N-1\times N}$ be a (grounding) matrix that satisfies:

$\displaystyle Q\mathbf{1}_{N}=0\qquad QQ^{\top}=I_{N-1}\qquad
Q^{\top}Q=I-\mathbf{11}^{\top}/N.$ (2)

A _grounded_ Laplacian matrix for the graph can now be computed via $Q$ as
follows:

$\displaystyle\widetilde{L}=QLQ^{\top}.$ (3)

Using the grounded Laplacian, the (square root of) the resistance distance can
now be alternatively written as
$r_{ij}=[(e_{i}-e_{j})^{\top}\widetilde{L}^{-1}(e_{i}-e_{j})]^{-1/2}$, where
the inverse of the grounded Laplacian is used in lieu of the pseudoinverse of
the standard Laplacian matrix. Indeed, the action of the matrix $Q$ can be
understood in terms of removing the null-space of $L$ by effectively
“grounding” the resistor network, i.e., fixing a reference potential [18, 16].

Young et al. [17] now extended the notion of resistance distance by using an
alternative characterization of the inverse $\widetilde{L}^{-1}$ that appears
in the definition of the effective resistance. Specifically, they define the
_generalized effective resistance distance_ between node $k$ and node $j$ by:

$\displaystyle d_{\text{GRD}}(k,j)=\sqrt{(e_{k}-e_{j})^{\top}X(e_{k}-e_{j})}.$
(4)

Here the matrix $X$ is defined via

$\displaystyle X=2Q^{\top}\Sigma Q,$ (5)

where $\Sigma$ is the solution of the Lyapunov equation:

$\displaystyle\widetilde{L}\Sigma+\Sigma\widetilde{L}^{\top}=I_{N-1}.$ (6)

This solution is unique under the assumption that there exists a globally
reachable node within the graph. Note that this formulation reduces to the
classical resistance distance in the case of undirected graphs. For more
details, we refer to [17, 6].

####  3.1.2 Hitting Time Based Distance (HTD)

A second type of node-to-node distance metric for directed graphs is the class
of hitting time metrics developed by Boyd et al. [7].

Consider a discrete-time Markov chain $(X_{t})_{t\geq 0}$ on the space of the
vertices $\mathcal{V}=\\{1,...,N\\}$ of a strongly connected graph, with
initial distribution $\lambda$ and a irreducible transition matrix $P=D^{-1}A$
such that:

$\displaystyle P(X_{0}=i)=\lambda_{i}\qquad\text{and}\qquad
P(X_{t+1}=j|X_{t}=i)=P_{i,j}.$ (7)

Let $\pi\in\mathbb{R}^{N}$ be the invariant distribution of the chain, i.e.,
$\pi P=\pi$. For a starting point distributed according to $\lambda$, the
_hitting time_ from a starting vertex $i\in\mathcal{V}$ is a random variable

$\displaystyle\tau_{i}=\inf\\{t\geq 1:X_{t}=i\\}.$ (8)

Following [7], we denote the probability that starting in a node $i$ the
hitting time of $j$ is less than the time it takes to return back to $i$ by

$\displaystyle Q_{i,j}:=P_{i}[\tau_{j}\leq\tau_{i}].$ (9)

Based on the matrix $Q$ a normalized hitting time matrix $T^{(\beta)}$ can be
defined in terms of its entries

$T^{(\beta)}_{i,j}=\begin{cases}\frac{\pi^{\beta}_{i}}{\pi^{1-\beta}_{i}}Q_{i,j}&\text{$i\neq
j$},\\\ 1&\text{otherwise},\end{cases}$ (10)

where $\beta$ is a scalar parameter that can be used to adjust the measure If
$P$ is an irreducible stochastic matrix (i.e., the underlying graph is
strongly connected, the Hitting Time Distance Matrix for $\beta=(0.5,1]$ can
be obtained by:

$d_{\text{HTD}}^{(\beta)}(i,j)=HTD_{i,j}^{(\beta)}\quad\text{where}\quad
HTD^{(\beta)}=-\log(T^{(\beta)})$ (11)

Remark. (Not strongly connected graphs). Note that both distance functions
discussed above make assumptions about the global reachability of (all) nodes
in the graph. To make the above distance measures well defined in case these
assumptions are not fulfilled, one option is to add a low-rank regularization
term, as popularized within the context of the well-known PageRank algorithm
[19, 20].

###  3.2 Optimal Transport distances for Directed Weighted Graphs

In the following, will exploit the geometries defined by the above defined
node-to-node distances measures $d_{\text{GRD}}$ $d_{\text{HTD}}^{(\beta)}$,
to derive two optimal transport distances between directed graphs: 1) a
Gromov-Wasserstein distance and 2) a Wasserstein distance.

####  3.2.1 Gromov-Wasserstein distance for directed graphs

The intuitive idea underpinning Gromov-Wasserstein distances is to
probabilistically map one geometric configuration (metric-space) onto another,
while distorting the distances as weakly as possible. In the context of graphs
these ideas have been explored, e.g., in [12, 13]. To define a Gromow-
Wasserstein distance for graphs, we thus need to consider the graph as a
collection of points (corresdponding to the nodes), with a (symmetric) metric
distance defined between them. This is precisely for what we will use the
above introduced node-to-node distance metrics.

Formally, consider two graphs $\mathcal{G}^{k}$ and $\mathcal{G}^{l}$. To each
graph, we associated the tuple ($\mathcal{C}^{k}$, $\mathbf{p}^{k}$)
consisting of a node-to-node distance matrix $\mathcal{C}^{k}$ and a
probability vector $p_{k}\in\mathbb{R}^{N}$ which describes the relative
“mass” we associate to each node in that graph. Without further available
information, we will typically use the uniform distribution
$\mathbf{p}^{k}=\mathbf{1}/N$ as an agnostic choice.

The Gromov-Wasserstein distance between two graphs $\mathcal{G}^{k}$ and
$\mathcal{G}^{l}$ can then be obtained as the solution to the following
minimization problem:

$d_{\text{GW}}(\mathcal{G}^{k},\mathcal{G}^{l})=\min_{\mathbf{\Gamma}\in\prod(p_{k},p_{l})}\quad\sum_{x_{1},x_{2},y_{1},y_{2}}\mathcal{L}(\mathcal{C}_{x_{1},x_{2}}^{k},\mathcal{C}_{y_{1},y_{2}}^{l})\Gamma_{x_{1},y_{1}}\Gamma_{x_{2},y_{2}}$
(12)

where $\prod(p_{k},p_{l})=\\{\Gamma\in\mathbb{R}^{N\times N}:\Gamma_{ij}\leq
0,\Gamma\mathbf{1}=\mathbf{p}^{k},\Gamma^{\top}\mathbf{1}=\mathbf{p}^{l}\\}$
is the set of all possible transport plans with marginal distributions
$\mathbf{p}^{k}$, $\mathbf{p}^{l}$, and $\mathcal{L}$ is a loss function
defined over the distance matrices $\mathcal{C}^{k}$. Commonly, the loss
function $\mathcal{L}(.,.)$ is simply an (elementwise) $L_{2}$ norm.

####  3.2.2 Wasserstein Distance for directed graphs

To derive a Wasserstein distance for directed graphs, we switch our
interpretation of the observed data. Instead of considering the geometry
defined by each graph in our observation set
$\\{\mathcal{G}^{1},...,\mathcal{G}^{p}\\}$ separately, and transporting these
geometries such that the distortion is minimized, we now interpret the edge-
weights of each weighted graph as a specific realization of a signal supported
on the _same underlying space_. Stated differently, we consider the edge-
weights as a distribution supported on the same set of latent edges, and we
aim to transport these edge distributions on top of each other optimally.

To this end, we allocate the observed edge weights in a matrix
$\varmathbb{P}\in\mathbb{R}^{E\times p}$, whose rows are indexed by the
(directed) edges and whose columns by the respective graph, i.e., the column
$\varmathbb{P}_{:,k}$ describes the weights of the $k$th graph
$\mathcal{G}^{k}$.

Using this definition, we build a _directed linegraph_
$\varmathbb{L}=(\varmathbb{V},\varmathbb{E},\varmathbb{W})$. The vertex set
$\varmathbb{V}$ of the linegraph contains each possible edge $(j,k)$ contained
in one of the graphs $\mathcal{G}^{i}$. The edge set $\varmathbb{E}$ of the
linegraph is defined as follows: an edge
$e^{\prime}=(u^{\prime},v^{\prime})\in\varmathbb{E}$ exists if the target of
$u^{\prime}$ is the source of $v^{\prime}$, i.e., the target node of edge
$u^{\prime}$ in the original graph, is the source node of edge $v^{\prime}$ in
the original graph. Note that, to build the line graph, the weights of the
interactions are not considered (but are considered as distribution supported
on the line-graph). Finally, the weight $w_{u^{\prime}v^{\prime}}$ of edge
$(u^{\prime},v^{\prime})$ in the line graph is simply the proportion of graphs
containing both edges $u^{\prime}$ to $v^{\prime}$.

Once we have a weighted, directed linegraph $\varmathbb{L}$, we can again
associate a distance matrix based on the generalized effective resistance or
the hitting time with $\varmathbb{L}$. The Wasserstein distance between two
graphs $\mathcal{G}^{k}$ and $\mathcal{G}^{l}$ can then be computed as follow:

$\displaystyle
d_{W}(\mathcal{G}^{k},\mathcal{G}^{l})=\mathop{\arg\min}_{\Gamma\in\Pi(\varmathbb{L})}\quad\langle\Gamma,\mathcal{C}_{\varmathbb{L}}\rangle_{F}$
(13)

$\mathcal{C}_{\varmathbb{L}}$ is one of the distance matrices (generalized
effective resistance, hitting time distance) defined for directed graphs, as
discussed above. Here
$\Pi(\varmathbb{L})=\\{\Gamma\in\mathbb{R}^{|\varmathbb{V}|\times|\varmathbb{V}|}:\Gamma_{ij}\leq
0,\Gamma\mathbf{1}=\varmathbb^{P}_{:,k},\Gamma^{\top}\mathbf{1}=\varmathbb^{P}_{:,l}\\}$
is again the set of all admissible transport matrices, whose marginal
distribution is now, however, defined by the respective distribution of edge
weights as encoded in the columns of the matrix $\varmathbb{P}$.

##  4 Numerical Experiments

Fig. 1: Optimal Transport distance between directed graphs. We consider an
illustrative example network, consisting of four directed “local” cycles
(indicated by node color), who are again connected “globally” in a cyclic way.
Left: original reference network (note that the network is strongly
connected). Middle: We perturb the network by swapping the direction of one of
the “local” edges within one of the four cycles. Right: We perturb the network
by swapping the direction of one of the “global” edges connecting the four
cycles. The table below displays the obtained distances considering the
following three baselines: the Frobenius norm of the difference between the
adjacency matrices; the optimal transport-based GOT distance [3], when
considering the graph as undirected, and the optimal transport-based GWOT
distance [13] (again considering the graph as undirected). We contrast these
with the results obtained via our Gromow-Wasserstein and Wasserstein (earth
movers distance) formulation based on both generalized effective resistance
and hitting time distance. Note that only our distance metrics that account
for the directionality of the graph edges can distinguish these different
cases. Table 1: Adjusted Rand (AR) measuring the accuracy of DWG clustering.
Values in bold indicate the outperforming method.

Dataset | PCA(P) | correlation(P) | $GW_{HTD^{0}.5}$ | $GW_{GRD}$ | $GW_{HTD^{1}}$ | $Wasserstein_{GRD}$ | $Wasserstein_{HTD^{1}}$ | $Wasserstein_{HTD^{0}.5}$
---|---|---|---|---|---|---|---|---
Pancreas Cancer | 0.037006 | 0.109974 | 0.109974 | -0.033237 | 0.138969 | 0.884777 | 0.884777 | 0.884777
Heart Myocardial Infarction | -0.055866 | 0.320291 | 0.312917 | 0.312917 | 0.455679 | 0.455679 | 0.455679 | 0.455679

###  4.1 Experiments on synthetic graphs: an illustrative example

To illustrate the behavior of our distance measures for directed weighted
graphs, we consider a synthetic example in which we connected four cyclic
graphs with four nodes each in a cyclic fashion — see Figure 1 for an
illustration. We now consider two different perturbations of these graphs and
assess how far these changes can be detected. Both of these perturbations
consist merely of a flip of the orientation of one of the edges, meaning that
when the graph is considered undirected there is no apparent change in the
graph structure. The first perturbation we consider is a flip in orientation
in one of the “local” edges within one of the cyclic four-node-graphs (cf.
Figure 1). The second perturbation we consider is a flip in the orientation of
one of the “global” edges that connect two of the cyclic graphs (cf. Figure
1).

The distances between these perturbed graphs, relative to the original graph,
are displayed in the table shown in Figure 1. We see that both of our distance
metrics for directed graphs capture a difference between the two scenarios,
irrespective of what directed node-to-node metric we use for them. In fact, in
most cases, the “global” edge flip leads to a larger distance. If we consider
the directed graph as a flow circulation pattern, it can be argued that,
indeed, this single “global” flip leads to a larger overall perturbation in
the overall flow pattern, in contrast to flipping a “local” edge which leads
only to a reversal of the flow within one of the cycles.

We also compare our distances, to standard distance metrics for undirected
graphs as baselines, i.e., the Frobenius norm, GOT [3]. Furthermore, a
previously proposed method for comparing directed graphs, GWOT [13], was also
considered in our benchmark. Interestingly, this approach also fails to
distinguish the graph with the global edge flip from the original graph. From
the evaluated distances, the Frobenius norm identifies the two perturbed
graphs to be equally far apart from our original graph. As there is no
difference in the undirected graph structure, the GOT distance assigns a zero
distance between all graphs.

Overall, we see that accounting for directions in the edges is thus important
to obtain meaningful distances between the graphs.

###  4.2 Case Study: single-cell RNAseq derived cell-cell interactions disease
clustering

To illustrate the utility of our graph distances, we further consider a real-
world analysis task, namely the comparison of cell-cell communication
networks. Specifically, we consider a scenario in which we are given a patient
cohort with $p$ patients, from which we generate a set of cell-cell
communication networks
$\mathcal{\textbf{G}}=\\{\mathcal{G}^{1},...,\mathcal{G}^{p}\\}$ using the
ligand-receptor analysis method CrossTalkeR [8]. Our question here is whether
the comparison of cell-cell networks can be used to delineate the disease
stage or sub-types in these patients. To construct our set of graphs, we
retrieved two single-cell RNA sequencing datasets publicly available. These
data have 20-35 samples, which are annotated regarding the health status of
patients. Next, we compute the graph-to-graph distances using our introduced
distance measures.

To reveal how far we can find a partition of the patient cohorts, we perform
$k$-means with the estimated distance matrix as input. For simplicity, we set
$k$ to the (true) number of classes in the data, and use the Adjusted Rand
index (ARI) [21] between the true label and clustering result to evaluate the
performance of the clustering result. We also include a few baseline methods.
In the first baseline, we would like to compare our methods with a simplistic
way of obtaining a distance using the graph set $\mathbf{G}$. Here, the matrix
$\varmathbb{P}$ is used as an input for a Principal Component Analysis, which
can be obtained by computing an SVD of the centered $\varmathbb{P}$ matrix
$\tilde{\varmathbb{P}}=U\Sigma V^{\top}$ Next, the principal components matrix
$U_{p\times(p-1)}$ are used to compute the pairwise Euclidean distance between
the samples.

In the second baseline, we attempt to compare our method(directed) with an
undirected cost function. For that, we compute the correlation distance
$dCor(u,v)$, between the pair of rows from $\varmathbb{P}$.

$dCor(u,v)=1-\frac{\langle(u-\bar{u}),(v-\bar{v})\rangle}{{\|(u-\bar{u})\|}_{2}{\|(v-\bar{v})\|}_{2}},$
(14)

where $\bar{u}$ and $\bar{v}$ denote the average of the vectors $u$ and $v$,
respectively. The distance matrix resulting from that process is then used as
a cost function for the Wasserstein approach described above.

We display the results of these experiments in Table 1. As can be seen, our
optimal transport-based distances outperform the baseline methods (correlation
and PCA), disregarding edge directions. Interestingly, we find that in this
task, the Wasserstein-based construction outperforms the Gromow-Wasserstein
formulation. In contrast, the node-to-node distance metric used to induce a
geometry for the directed graphs appears to play a far less significant role.
These results indicate that the Wasserstein formulation might be better suited
for sparse and noisy DWG obtained from cell-cell communication networks from
single-cell RNA sequencing. A potential explanation may be that the
Wasserstein formulation is adaptive with respect to the whole ensemble of
graphs considered, due to the specific construction of the linegraph.

##  5 Conclusions

We presented two OT-based distance measures to compare directed graphs, based
upon node-to-node distance metric for directed graphs. Our results highlight
the importance of considering edge directions when comparing graphs. Indeed,
as our example in Figure 1 shows our approach can capture essential features
related to the direction of each interaction in opposition to our baseline
models.

We further provided a case study of cell-cell communication networks as a real
word application of the proposed methods. Here our methods enabled the
identification of latent disease stages and potentially disease-related
interaction groups.

In future work, we intend to improve the robustness of our structural
comparison, e.g., by adding other synthetic directed weighted graph models. We
will also aim to characterize in more detail the effects of noise and
sparseness in our methods as well as explore approaches using the computed
transport maps for explainability. For instance, in the context of our example
application we may want to highlight which cell-cell pairs provide the core
contributions to the observed differences between healthy and disease states.

## References

  * [1] Noël Malod-Dognin and Nataša Pržulj,  “L-graal: Lagrangian graphlet-based network aligner,”  Bioinformatics, vol. 31, no. 13, pp. 2182–2189, 2015.
  * [2] S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt,  “Graph kernels,”  Journal of Machine Learning Research, vol. 11, pp. 1201–1242, 2010\.
  * [3] Hermina Petric Maretic, Mireille EL Gheche, Giovanni Chierchia, and Pascal Frossard,  “Got: An optimal transport framework for graph comparison,”  arXiv preprint arXiv:1906.02085, 2019.
  * [4] Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin Duke,  “Gromov-wasserstein learning for graph matching and node embedding,”  in International conference on machine learning. PMLR, 2019, pp. 6932–6941.
  * [5] Gabriel Peyré, Marco Cuturi, et al.,  “Computational optimal transport: With applications to data science,”  Foundations and Trends® in Machine Learning, vol. 11, no. 5-6, pp. 355–607, 2019.
  * [6] George Forrest Young, Luca Scardovi, and Naomi Ehrich Leonard,  “A new notion of effective resistance for directed graphs—part ii: Computing resistances,”  IEEE Transactions on Automatic Control, vol. 61, no. 7, pp. 1737–1752, 2015.
  * [7] Zachary M Boyd, Nicolas Fraiman, Jeremy Marzuola, Peter J Mucha, Braxton Osting, and Jonathan Weare,  “A metric on directed graphs and markov chains based on hitting probabilities,”  SIAM Journal on Mathematics of Data Science, vol. 3, no. 2, pp. 467–493, 2021.
  * [8] James S Nagai, Nils B Leimkühler, Michael T Schaub, Rebekka K Schneider, and Ivan G Costa,  “CrossTalkeR: analysis and visualization of ligand–receptorne tworks,”  Bioinformatics, vol. 37, no. 22, pp. 4263–4265, 05 2021.
  * [9] Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis,  “Matching node embeddings for graph similarity,”  in Proceedings of the AAAI Conference on Artificial Intelligence, 2017, vol. 31,1.
  * [10] Asuka Takatsu,  “On wasserstein geometry of gaussian measures,”  in Probabilistic approach to geometry, pp. 463–472. Mathematical Society of Japan, 2010.
  * [11] Miguel EP Silva, Robert E Gaunt, Luis Ospina-Forero, Caroline Jay, and Thomas House,  “Comparing directed networks via denoising graphlet distributions,”  Journal of Complex Networks, vol. 11, no. 2, pp. cnad006, 2023.
  * [12] Facundo Mémoli,  “Gromov–wasserstein distances and the metric approach to object matching,”  Foundations of computational mathematics, vol. 11, no. 4, pp. 417–487, 2011.
  * [13] Samir Chowdhury and Facundo Mémoli,  “The gromov–wasserstein distance between networks and stable network invariants,”  Information and Inference: A Journal of the IMA, vol. 8, no. 4, pp. 757–787, 2019.
  * [14] M Randić and DJ Klein,  “Resistance distance,”  J. Math. Chem, vol. 12, pp. 81–95, 1993.
  * [15] Douglas J Klein and Milan Randić,  “Resistance distance,”  Journal of mathematical chemistry, vol. 12, pp. 81–95, 1993.
  * [16] Arpita Ghosh, Stephen Boyd, and Amin Saberi,  “Minimizing effective resistance of a graph,”  SIAM review, vol. 50, no. 1, pp. 37–66, 2008.
  * [17] George Forrest Young, Luca Scardovi, and Naomi Ehrich Leonard,  “A new notion of effective resistance for directed graphs—part i: Definition and properties,”  IEEE Transactions on Automatic Control, vol. 61, no. 7, pp. 1727–1736, 2015.
  * [18] Ali Jadbabaie, Nader Motee, and Mauricio Barahona,  “On the stability of the kuramoto model of coupled nonlinear oscillators,”  in Proceedings of the 2004 American Control Conference. IEEE, 2004, vol. 5, pp. 4296–4301.
  * [19] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd,  “The pagerank citation ranking: Bring order to the web,”  Tech. Rep., Technical report, Stanford University, 1998.
  * [20] David F Gleich,  “Pagerank beyond the web,”  siam REVIEW, vol. 57, no. 3, pp. 321–363, 2015.
  * [21] Lawrence Hubert and Phipps Arabie,  “Comparing partitions,”  Journal of classification, vol. 2, pp. 193–218, 1985.


# Towards Arbitrary-View Face Alignment by Recommendation Trees††thanks: This
is our original submission to ICCV 2015.

Shizhan Zhu1 Cheng Li2 Chen Change Loy1,3 Xiaoou Tang1,3
1Department of Information Engineering, The Chinese University of Hong Kong
2SenseTime Group
3Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Learning to simultaneously handle face alignment of arbitrary views, _e.g_.
frontal and profile views, appears to be more challenging than we thought. The
difficulties lay in i) accommodating the complex appearance-shape relations
exhibited in different views, and ii) encompassing the varying landmark point
sets due to self-occlusion and different landmark protocols. Most existing
studies approach this problem via training multiple viewpoint-specific models,
and conduct head pose estimation for model selection. This solution is
intuitive but the performance is highly susceptible to inaccurate head pose
estimation. In this study, we address this shortcoming through learning an
Ensemble of Model Recommendation Trees (EMRT), which is capable of selecting
optimal model configuration without prior head pose estimation. The unified
framework seamlessly handles different viewpoints and landmark protocols, and
it is trained by optimising directly on landmark locations, thus yielding
superior results on arbitrary-view face alignment. This is the first study
that performs face alignment on the full AFLW dataset with faces of different
views including profile view. State-of-the-art performances are also reported
on MultiPIE and AFW datasets containing both frontal- and profile-view faces.

##  1 Introduction

Face alignment is essential for many facial analysis tasks such as facial
expression detection [11, 28], attribute recognition [9], face image
processing [25], face recognition and verification [22, 5, 21, 10, 12].
Significant improvements have been achieved in face alignment with the
emergence of discriminative regression methods [24, 17, 13]. Nevertheless,
most of these methods tend to confine their solutions on faces with limited
view range, in which at least both two eyes are visible and all landmarks can
be explicitly annotated. Some studies [31, 23] can handle multi-view face
alignment, but they only reported results on faces with $\sim\pm$45$\degree$
viewpoint variation. When view changes dramatically, these models often
produce erroneous shape estimation (Fig. 1). However, non-frontal face
constitutes a considerable fraction of faces found in various sources, such as
web images, social network photos, and surveillance videos. Considering
alignment only for near-frontal view severely limits the scalability of many
subsequent facial analyses in real-world environment. In this paper, we wish
to study the limitations of using a single discriminative regression model
[24, 17, 13], and formulate a unified model recommendation framework to handle
arbitrary view poses up to profile view $\sim\pm$90$\degree$.

Figure 1: Results on four methods (from left to right): [32] models facial
structure by mixture of trees; SDM [24] is a representative discriminative
regression method that achieves state-of-the-art performance on frontal-face-
biased datasets [1, 15]; CoR [27] is specially proposed to handle external-
object occlusion; and our proposed method based on model recommendation.

Simultaneously considering face alignment for arbitrary view poses is non-
trivial: i) For large view variation some landmarks such as those on half of
the face might become invisible due to self-occlusion. Solving this problem
requires not only the capability to infer the visibility of occluded points,
but also the ability to handle varying landmark point sets. For instance,
MultiPIE has 39 points for profile-view and 68 points for frontal-view. ii)
Importantly, due to the inherently multimodal and complex appearance-shape
relations exhibited in multi-view faces, a single model would easily fail to
fit the landmarks (Fig. 1). The aforementioned challenges demand multiple face
alignment models specially trained on different view poses, so as to handle
different landmark protocols and multimodal appearance-shape relations. How to
jointly and seamlessly consider all models for aligning an arbitrary face pose
remains an understudied problem.

There are a few attempts [8, 30] to address the arbitrary-view face alignment.
These methods first estimate the head pose and subsequently choose the
corresponding alignment model from a model pool for landmark estimation.
Nonetheless, head pose estimation in unconstrained settings itself is a
challenging task. Existing methods mostly rely on global features for
estimation, which can be susceptible to illumination, occlusion, and
background clutter. Error in head pose estimation inevitably affects the
performance of subsequent face alignment. Approaches have also been proposed
to handle occlusion caused by external objects such as hands, hairs, or
sunglasses [3, 27]. Nonetheless, there are intrinsic differences between the
handling of external occlusion and self-occlusion caused by view variation. In
particular, given a specific pose, the underlying shape constraint remains
unchanged in the presence of external occlusion. Even if some facial parts are
occluded, accurate landmarks can still be inferred using a single model. On
the contrary, self-occlusion caused by view changes is a more challenging
problem. Our experiments show that a direct application of face alignment
specifically designed for handling external occlusion fails to cope with
profile-view poses (CoR [27] in Fig. 1).

Handling face alignment with different view poses requires a framework that
can seamlessly handle different face models and landmark protocols from
frontal view to profile view, and select optimal model configuration given an
arbitrary pose. To this end, we cast the problem as a model recommendation
problem and propose a framework called Ensemble of Model Recommendation Trees
(EMRT). Decision forests [2] have been extensively used in many applications
including facial alignment due to its effectiveness and efficiency. In this
study, we reformulate it for the purpose of model recommendation. In the
proposed framework, we first prepare a model pool by training a set of
alignment models, each of which concentrates on processing specific cluster of
face samples with similar face angles and landmark protocols111Note that our
framework can naturally handle models encompassing different in-plane and out-
of-plane rotations. In addition, the framework flexibly handles varying number
of models depending on the complexity of the application scenarios, and it can
be used along with different existing discriminative regression methods [24,
17, 13].. Given a face image with unknown pose, the EMRT takes features based
on the shape responses from different models as input, and produces a model
rating vector that encodes the preference on different models. Face alignment
is then accomplished by aggregating the consensus of different models based on
the rating.

The main contributions of this study are as follows:

(1) We propose a novel approach that is capable of handling arbitrary pose
face alignment, up to profile view. To our knowledge, this is the first study
that is capable of training and evaluating on the challenging full Annotated
Facial Landmarks in the Wild (AFLW) dataset [14] 222The full AFLW dataset
contains 25,993 images. Existing studies [7, 19, 26, 29] only select $\leq$25%
images with near-to-frontal views for evaluations.. State-of-the-art
performances are also achieved on MultiPIE [20] and AFW [32], which contain
challenging profile-view faces.

(2) We formulate a new forest-based recommendation framework with appealing
properties. Firstly, it has a new splitting function that jointly optimises
the partitions of features and the learning of model rating vector. The
splitting function is formulated such that it optimises directly the landmark
locations, thus leading to accurate alignment given arbitrary poses. Secondly,
the objective function is optimised to produce a model rating vector that
captures the unique correlation between models so that semantically nearer
models (_e.g_. those trained with faces in nearby face angle range) share
closer values in the model rating vector, than those further away in the model
space. Thanks to these properties, the proposed model recommendation approach
is more robust than other model selection alternatives in our task.

Although we mainly focus on face alignment of arbitrary views, our framework
also naturally deals with partial occlusion and capable of inferring the
visibility of landmarks.

##  2 Related Work

Many approaches have been proposed for solving the face alignment problem. The
classic methods include the Active Appearance Model (AAM) [6] and its
variants. AAM models faces by both appearance and shape information and
optimises them in a holistic manner. Facial parts detection based method [1],
also known as Constrained Local Model, aim to detect facial parts with several
part detectors, and use global constraints to estimate reasonable shapes.
Discriminative regression methods [4, 24, 17, 13] regress expected shape
update based on local appearance information extracted from all current
estimated landmarks. Such methods have achieved state-of-the-art accuracy. Our
framework allows these state-of-the-art approaches to be applicable to non-
frontal cases via recommendation over multiple models. A number of existing
studies propose to solve the multi-view face alignment problem [31, 23]. These
studies differ significantly from our work since they confine the yaw angle of
faces within the range of $\sim\pm$45$\degree$ [31]. In [23], the dataset is
chosen from the 300-W dataset [18] with an approximate range of
$\sim\pm$45$\degree$, which is far smaller than the head pose range considered
in this study.

Our work is closer to a few alignment studies that address the face alignment
problem in a multimodal manner:

Conditional Regression Forest [8]. In this work, the facial points are
estimated after a rough estimation of head pose. The head pose is estimated
according to the global appearance of the face image and regarded as the prior
probability of each alignment model. This method works quite well and gains
improvement on traditional face alignment benchmarks, _e.g_. LFPW [1] or LFW
[8]. When this method is extended to dataset with extremely large pose
variations, _e.g_. AFLW, the method fails due to erroneous head pose
estimation, no matter how well each face alignment model is trained.

Iterative Multi-Output Random Forests [30]. This study extends [8] by
iteratively re-estimating the head pose and facial expression based on the
current estimated shape, and then re-estimating the facial landmarks with the
updated prior model probability. Further improvement is achieved in this work
compared to [8]. Similar to [8], the algorithm begins with head pose
estimation based on global appearance. When applied to faces with large pose
variation, if the initial head pose estimation is incorrect, the error is
rather hard to be rectified during iterative optimisation since the initial
shape is estimated with the wrong prior probability.

Consensus of Regressors [27]. The study applies a mixture of models to handle
different types of occluded faces. The method works well on occlusion
benchmarks like COFW [3]. However, the method yields poor performance on
profile-view cases because all regression models assume a limited pose
variation. From our experiments, we observe that even if models are provided
to handle large pose variations, suboptimal results may be still generated due
to the failure in drawing consensus amongst recommended landmarks with large
spatial variations.

Model Recommendation. Model recommendation has been proposed for action
recognition [16]. The study shows that a recommendation system is important
for choosing one model out of a large set of possibilities. Their method
follows the conventional collaborative filtering scheme, where user’s rating
is required on a small subset of models, and the goal is to use that subset of
ratings to predict the ratings of remaining models. This is in contrast to our
task where user rating is not available.

##  3 Arbitrary-View Face Alignment

Figure 2:  There are three steps to align a face image with arbitrary pose:
(a) extracting shape responses from model pool (note that the model pool could
cover the modeling of various in-plane or out-plane face rotation and
external-object occlusion), (b) forming recommendation feature vector based on
model shape responses, and (c) model recommendation using the proposed
Ensemble of Model Recommendation Trees.

Our aim is to predict the $N$ facial landmark locations given a face image
with arbitrary view up to profile view, with potentially in-plane rotation,
self- or external-object occlusion. In addition to landmark locations, we also
want to estimate a confidence value that indicates the visibility of each
landmark. Figure 2 provides an overview of using the proposed framework for
aligning a face with arbitrary pose. We explain the training process involved
in each step as follows. Table 1 summarises the notations we used in this
study.

Category | Notation | Meaning
---|---|---
Index | $c=1,...,C$ | Index of model
$m=1,...,M$ | Index of sample
$n=1,...,N$ | Index of facial landmark
$f=1,...,F$ | Index of feature
$j$ | Index of node in a tree
Training Set | $\boldsymbol{x}^{m}_{c,n}\in\mathcal{X},\mathbb{R}^{2}$ | Model shape responses
$\boldsymbol{y}^{m}_{n}\in\mathcal{Y},\mathbb{R}^{2}$ | Shape ground truth
$\\{m,n\\}\in\mathcal{V}$ | Visibility ground truth
$\phi^{m}_{f}\in\mathcal{F}$ | Feature
$l^{m}_{n}\in\mathcal{L}$ | Label for classification
Model | $\boldsymbol{b}_{c}\in\\{0,1\\}^{N}$ | Model visibility protocol
Rating | $\boldsymbol{w}_{j}\in\mathbb{R}^{C}$ | Rating
Table 1: Mathematical notations used in this study.

a) Model pool construction. We construct a model pool of discriminative
regression alignment models as depicted in Fig. 2(a). We assume there are $C$
models in the pool and $M$ training samples. Each model $c$ is trained to
accept a facial image and output the predicted landmarks
$\\{\boldsymbol{x}_{c,n}\\}^{N}_{n=1}$, where
$c\in\left\\{1,\dots,C\right\\}$, and $N$ is the number of landmarks. Here
$\boldsymbol{x}$ is the $(x,y)$ coordinate of one landmark. The landmarks
predicted by all models over all samples collectively form the model shapes
responses
$\mathcal{X}=\\{\boldsymbol{x}^{m}_{c,n}\\}^{C,~{}~{}~{}N,~{}~{}~{}M}_{c=1,n=1,m=1}$.

Each alignment model is trained to handle only a specific cluster of faces
with specific view range and landmark visibility protocol333Variations in
landmark visibility are caused by both self-occlusion due to extreme view
pose, and external-object occlusion.. Models are different from each other,
_e.g_. there can be a model specific to left-profile, or a model specific to
45$\degree$ out-of-plane rotated with mouth occluded. We denote landmark
protocol of model $c$ by a binary mask vector
$\boldsymbol{b}_{c}\in\\{0,1\\}^{N}$, 1 for visible and 0 for invisible
(derived from ground truth visibility $\mathcal{V}$). To train each model, we
provide it with the labelled facial landmark locations
$\mathcal{Y}=\\{\boldsymbol{y}^{m}_{n}\\}_{\\{m,n\\}\in\mathcal{V}}$ and
visibility $\mathcal{V}$. Here $\\{m,n\\}\in\mathcal{V}$ only when the $n$-th
landmarks in the $m$-th face is visible. In other words, the training samples
for a model must contain all visible landmarks defined by the associated model
landmark protocol. Note that we still force all the models to output the full
set of landmarks, including those defined as invisible by the model, so as to
facilitate the following recommendation process, _i.e_.
$\boldsymbol{x}^{m}_{c,n}\in\mathcal{X}$ even if $(\boldsymbol{b}_{c})_{n}=0$.

Consequently, each alignment model is capable of handling its specific type of
faces easily; the hard part lies in the way to infer the optimal model
configuration given a face with potentially arbitrary pose and landmarks
visibility.

b) Recommendation features extraction. All alignment models in the pool
collectively produce the model shape responses $\mathcal{X}$ given a face
image, as depicted in Fig. 2(a). From the given model shape responses we
extract recommendation features as input to the EMRT. Formally, we represent
the recommendation feature of the $m$-th face image as
$\boldsymbol{\phi}^{m}={(\phi_{1}^{m},\dots,\phi_{F}^{m})}^{\mathsf{T}}$,
where each dimension a facial part detection score of a visible landmark, and
the dimension is denoted by $F=\sum_{c=1}^{C}\|\boldsymbol{b}_{c}\|_{1}$. To
obtain the part detection score, we apply a facial part detector (SIFT+SVM) on
all visible landmarks defined in all models in the pool, and use the resulting
detection scores to form the recommendation feature of a face. Such feature is
more discriminative than global appearance features used in the prior-head-
pose-estimation method. We collectively denote all features of $M$ training
images as $\mathcal{F}=\\{\phi^{m}_{f}\\}^{M,~{}~{}~{}F}_{m=1,f=1}$.

c) Model Recommendation by ensemble of recommendation trees. The core purpose
of a recommendation system is to estimate a rating that describe the fitness
of a model on a given task. We denote a model rating vector as
$\boldsymbol{w}\in\mathbb{R}^{C}$. In our problem, the rating vector is used
as a weight vector to combine the shape responses of different models in the
pool to estimate the final landmark positions. Similarly, the rating vector is
also used to obtain the final visibility estimation. The training details of
the ensemble of recommendation trees are provided in Sec. 3.2. Before we
detail the training steps, we first review the conventional classification
forest and discuss its limitations as a recommendation framework.

###  3.1 Classification Forest for Model Recommendation

A classification forest can be adapted for model recommendation by training it
to pick up the most suitable model given the model shape responses obtained
from the model pool. The rating may be approximated by using the posterior
classification probability. Alternatively, a hard model selection can be done
by finding the maximum votes from all trees. In this section, we first give a
brief review of classification forest and discuss its limitation as a model
recommendation method.

Learning a conventional decision tree, _e.g_. the classification tree,
typically starts from splitting the training set with optimal binary split
function $h_{\Theta}(\boldsymbol{\phi})\in\\{0,1\\}$, and repeats such process
recursively until some criteria are reached. Typically the form of $h$ is pre-
defined, and for conventional classification tree, it could be represented by

$\displaystyle h_{\Theta}(\boldsymbol{\phi})=$
$\displaystyle\left\\{\begin{array}[]{lr}0&\phi_{k}\leq\tau\\\
1&\phi_{k}>\tau\end{array}\right..$ (1)

A sample is channeled to the left child if $h_{\Theta}(\boldsymbol{\phi})=0$,
and to the right if otherwise.

To choose the best split function parameters $\Theta_{j}=\\{k_{j},\tau_{j}\\}$
for node $j$, a set of candidate features and thresholds are randomly selected
and evaluated. The optimal one that maximises the information gain is chosen
as the node parameters. Concretely, let denote the set of class labels as
$\mathcal{L}=\\{l^{m}\\}^{M}_{m=1}$, where $l\in\\{1,\dots,C\\}$ is the model
label. Given the current split node $j$ and its related sub training set
$\mathcal{S}_{j}=\mathcal{F}_{j}\times\mathcal{L}_{j}\subset\mathcal{F}\times\mathcal{L}$,
and let denote the two child nodes’ sub training set by
$\\{\mathcal{S}_{j}^{(L)},\mathcal{S}_{j}^{(R)}\\}$, the information gain is
defined as

$I_{j}(\Theta_{j})=H(\mathcal{S}_{j})-\sum_{\theta\in\\{L,R\\}}\frac{|\mathcal{S}_{j}^{(\theta)}|}{|\mathcal{S}_{j}|}H(\mathcal{S}_{j}^{(\theta)})$
(2)

In a classification setting, $H(\mathcal{S}_{j})$ denotes the cross entropy of
sub training set $\mathcal{S}_{j}$, represented as

$H(\mathcal{S}_{j})=\sum_{c=1}^{C}-(p_{j})_{c}\log(p_{j})_{c},$ (3)

where $p_{j}$ is the probability distribution calculated on $\mathcal{L}_{j}$.

Inference of classification forest can be achieved by feeding the feature
$\boldsymbol{\phi}$ to all the trees and pass it downward according to the
binary split function in each split node. Each tree would output a predicted
label proposed by the resulted leaf node. We simply aggregate the decisions
from all trees using a majority voting.

Despite that the classification forest is effective in handling high-
dimensional features of shape responses, it is not well-suited as a model
recommendation framework for our problem, for the following reasons:

(1) The rating generated using the posterior class probability of a
classification forest tends to simultaneously recommend non-related models far
away from each other in the model space (_e.g_. left-profile and right-profile
models), as depicted in Fig. 3(a). Such a poor recommendation will lead to
erroneous landmark estimation. The poor recommendation is mainly caused by the
splitting function of classification forest, in which the cross entropy
formulation (Eq. (3)) does not naturally distinguish the different models.
This drawback is resolved with our new splitting function. Fig. 3 shows an
illustration that highlights the difference between the ratings generated by
the classification tree and a recommendation tree. The rating vector generated
by the recommendation tree tends to recommend models close in the shape space.
We show in Sec. 4 that the proposed recommendation trees outperform the
classification trees.

(2) The classification forest does not fully exploit the available supervision
signal, namely landmark positions $\mathcal{Y}$ and visibility $\mathcal{V}$
in the training process.

###  3.2 Learning Ensemble of Model Recommendation Trees

We wish to address the shortcomings of classification forest through
clustering similar faces naturally with a specially designed split mechanism.
There are three main differences between the learning of a recommendation tree
and a classification tree: (1) In a recommendation tree, the splitting of
samples are directly related to their facial landmark locations instead of the
expected model index as classification target. (2) To learn a recommendation
tree, we need to provide the full supervision signal
$\\{\mathcal{F},\mathcal{X},\mathcal{Y},\mathcal{V}\\}$ rather than just
$\mathcal{F}\times\mathcal{L}$, as in the classification forest. (3) A
recommendation tree incorporates the rating vector
$\boldsymbol{w}_{j}\in\mathbb{R}^{C}$ into the optimisation of each node $j$.
All these differences are introduced aiming to cluster training samples with
similar rating to the same tree node, and the similarity of rating is computed
purely based on $\mathcal{X}$ and $\mathcal{Y}$.

More precisely, given current split node $j$ and its related sub training set
$\mathcal{S}_{j}=\\{\mathcal{F}_{j},\mathcal{X}_{j},\mathcal{Y}_{j},\mathcal{V}\\}$,
we define a new training objective as follows

$I_{j}(\Theta_{j},\boldsymbol{w}_{j}^{(\theta)})=H(\mathcal{S}_{j},\boldsymbol{w}_{j})-\sum_{\theta\in\\{L,R\\}}\frac{|\mathcal{S}_{j}^{(\theta)}|}{|\mathcal{S}_{j}|}H(\mathcal{S}_{j}^{(\theta)},\boldsymbol{w}_{j}^{(\theta)}),$
(4)

where $H(\mathcal{S}_{j},\boldsymbol{w}_{j})$ is defined as

$H(\mathcal{S}_{j},\boldsymbol{w}_{j})=\sum_{\begin{subarray}{c}m,n:\\\
\boldsymbol{x}^{m}\in\mathcal{S}_{j},\\\
\\{m,n\\}\in\mathcal{V}\end{subarray}}\|\boldsymbol{y}^{m}_{n}-\sum_{c=1}^{C}w_{jc}\boldsymbol{x}^{m}_{c,n}\|_{2}^{2}.$
(5)

Note that both $\mathcal{Y}$ and $\mathcal{V}$ are directly involved in the
optimisation function, in contrast to the conventional classification forest.
Importantly, the information gain is maximised not only based on $\Theta_{j}$,
but also the rating vectors in the parent and child nodes
$\\{\boldsymbol{w}_{j},\boldsymbol{w}_{j}^{(L)},\boldsymbol{w}_{j}^{(R)}\\}$.

Figure 3: An illustration that highlights the differences between a
conventional classification tree and a recommendation tree. To simplify the
discussion, we assume the models in a pool are only yaw-specific without
considering in-plane rotation or external-object occlusion. In each rating
vector, the indices of rating are sorted based on the models’ yaw angle. As
can be observed, a classification tree neglects the potential relations
between models, and may thus propose erroneous rating that advocates both
left-profile-view and right-profile-view models. In contrast, the learning of
a recommendation tree is directly supervised by facial landmark positions.
Hence samples with similar facial shapes are naturally clustered, and hence
similar models tend to share similar ratings. As a result, more robust and
reasonable rating can be obtained.

Optimisation with Eq. (4) is more complex than Eq. 2, which is used in the
conventional classification forest. In the classification forest, optimisation
is only performed over the split parameters $\Theta_{j}$, where we just
enumerate several candidate features and thresholds to find the optimal
$\Theta_{j}$. On the contrary, the optimisation in the recommendation forest
needs to account for both the split parameters $\Theta_{j}$ and rating
$\boldsymbol{w}_{j}^{(\theta)}(\Theta_{j}),\theta\in\\{L,R\\}$. In particular,
for each candidate feature-threshold pair, we need to find the optimal
$\boldsymbol{w}_{j}^{(\theta)}(\Theta_{j}),\theta\in\\{L,R\\}$. Assume that
the $\Theta_{j}$ is given, the partition of $\mathcal{S}_{j}$ is determined,
the optimal $\boldsymbol{w}_{j}^{(\theta)}(\Theta_{j})$ can be obtained by

$\displaystyle\boldsymbol{w}_{j}^{(\theta)}(\Theta_{j})=\operatorname*{argmin}_{\boldsymbol{w}}$
$\displaystyle\sum_{\begin{subarray}{c}m,n:\\\
\boldsymbol{x}^{m}\in\mathcal{S}_{j}^{(\theta)},\\\
\\{m,n\\}\in\mathcal{V}\end{subarray}}\|\boldsymbol{y}^{m}_{n}-\sum_{c=1}^{C}w_{c}\boldsymbol{x}^{m}_{c,n}\|_{2}^{2}$
(6) $\displaystyle s.t.~{}~{}~{}~{}\boldsymbol{w}$ $\displaystyle\geq
0,\|\boldsymbol{w}\|_{1}=1,$

which can be efficiently solved by Quadratic Programming packages. Note that
the regularity constraints over $\boldsymbol{w}$ in Eq. 6 is important to
avoid unreasonable recommendation results and to enforce facial shape
constraints.

###  3.3 Landmark Inference with EMRT

Despite the learning procedure of the proposed recommendation tree is more
sophisticated than a traditional tree, the inference efficiency is identical
to the conventional tree. Specifically, given an image in the testing stage,
we first extract the shape responses $\tilde{\boldsymbol{x}}_{c,n}$ and
subsequently compute the recommendation feature $\tilde{\boldsymbol{\phi}}$.
The feature is fed to a recommendation tree and passed down from the root node
to the leaf node according to the binary split function
$h_{\Theta_{j}}(\tilde{\boldsymbol{\phi}})$ stored in each node. For each
tree, rating $\boldsymbol{w}$ stored in the reached leaf node is used to
estimate the predicted landmark locations $\tilde{\boldsymbol{y}}_{n}$ and
visibility confidence $\tilde{v}_{n}$,

$\displaystyle\tilde{\boldsymbol{y}}_{n}=\sum_{c=1}^{C}w_{c}\tilde{\boldsymbol{x}}_{c,n},~{}~{}~{}~{}~{}~{}\tilde{v}_{n}=\sum_{c:(\boldsymbol{b}_{c})_{n}=1}w_{c}\tilde{\phi}_{c,n},$
(7)

where $\tilde{\phi}_{c,n}$ is retrieved from the $F$-dimensional
$\tilde{\boldsymbol{\phi}}$.

To obtain the final estimation from different trees, we average all the
predictions (landmark locations and visibility confidence) weighted by the
number of training samples in the reached leaf node of each tree. Visibility
of a landmark is obtained via comparing the estimated confidence with a
threshold $\gamma$.

##  4 Experiments

#### Datasets.

Following the objective of this study of aligning arbitrary-view face up to
profile view, we choose the following datasets with extremely large pose
variations.

AFLW dataset [14]: This dataset was collected from Flickr hence exhibits in-
the-wild setting. The original dataset contains 25,993 images, of which 27.48%
have yaw angle larger than 45$\degree$ and 3.83% larger than 90$\degree$. The
large angle range and in-the-wild setting is challenging for common methods
without specifically designed mechanism. Each face is annotated with at most
21 landmarks. Similar to [26, 1], we discard two ear landmarks to enforce more
stable face shape. Non-visible landmark annotation, including both self-
occlusion and external-object-occlusion, is not provided. To our knowledge,
our study is the first attempt to train and evaluate on this challenging
dataset without removing non-frontal faces.

MultiPIE dataset [20]: This dataset was originally collected in a constrained
lab environment with a setting of multiple poses, illuminance and facial
expressions. A subset of 6152 faces are defined [20] and labelled with either
39 (profile-view) or 68 (frontal-view) facial landmarks. Zhu  _et al_. [32]
further annotate another 400 profile-view faces with 39 landmarks. In our
experiments, these two subsets of data are merged and cleaned to form a
6547-image dataset.

AFW dataset [32]: This original dataset contains 468 faces with in-the-wild
setting. Each face is annotated with at most 6 landmarks. Non-visible landmark
annotation is not provided similar to AFLW. We note that a subset of AFW,
totally 337 faces, were selected and re-annotated with 68 landmarks by [18].
These 337 faces are frontally biased, hence we still employ the original 468
faces and the associated annotations.

Evaluation metric. We apply percentage of mean squared error normalised by the
upright distance between the highest eyebrow landmark and the chin landmark as
the evaluation metric. Errors are calculated on all annotated landmarks,
excluding non-annotated or invisible landmarks, since no ground truths are
available. We do not normalise error by inter-ocular distance because one of
the two eyes is invisible for many profile view cases.

###  4.1 Comparison with Existing Methods

#### Comparison with [32].

To our knowledge, [32] is one of the most recent works that is capable of
handling profile-view and frontal-view faces simultaneously. Model of [32] is
trained on only 900 images of MultiPIE dataset, which is a rather small
fraction of the original dataset. Since the training of a discriminative
regression model requires more training samples, we employ the full MultiPIE
dataset and perform evaluations by averaging performance on 5-fold cross
validation. For a fair comparison, we re-train the model of [32] in the same
way using their released codes. Note that each person might contribute
multiple facial images. We ensure that the images from the same person only
appear within the same fold.

Similar to [32], we further evaluate the models trained on the full MultiPIE
set on the full AFW dataset. As in [32], we use a trained linear mapping to
obtain the 6-point estimate by each method. Since [32] predefines the mixture
of trees, it is infeasible to train the model of [32] with AFLW landmarks
protocol. Hence we do not compare with [32] on the AFLW dataset.

Approach | MultiPIE | AFW
---|---|---
[32] | 2.74 | 4.68
Ours | 2.12 | 3.55
Table 2: Mean error comparison with [32] on two datasets (also applied in
[32]).

Results of the comparison are reported in Table 2. We also compare the
relative cumulative error distribution (CED) curve for the two methods on
MultiPIE and AFW datasets in Fig. 4. Based on the results, it is observed that
our framework outperforms [32] on both the datasets applied in their work.
More significant improvement is observed on AFW dataset with in-the-wild
setting. The results suggest the effectiveness of using the discriminative
method along with the proposed recommendation framework for handling
unconstrained settings. We provide qualitative examples in Fig .5 comparing
against [32].

(a) Results from MultiPIE.

(b) Results from AFW.

Figure 4: CED curve compared with [32] on MultiPIE and AFW.

Comparison with [24, 17, 13]. The methods proposed in these three studies are
representative discriminative regression approaches. They have achieved state-
of-the-art results on commonly used frontal-view-biased datasets. In this part
we compare our proposed recommendation framework with these regression methods
to show the benefits of adopting a model recommendation framework. Since the
training codes of [24, 17] are not publicly available, we evaluate all these
methods based on our re-implementation. Our re-implementation achieves
comparable performance on common benchmarks (_e.g_. LFPW [1], Helen [15]) with
theirs reported in the literature.

We evaluate our approach and the three baseline methods on the full AFLW
dataset since it is more challenging than the MultiPIE dataset. Since AFLW
also does not provide a train-test set partition, we perform a 5-fold cross-
validation and report the averaged performance across all the folds.

Approach | Mean error over AFLW dataset
---|---
SDM [24] | 6.98
LBF [17] | 7.47
ERT [13] | 7.70
Ours | 4.01
Table 3: Mean error comparison with [24, 17, 13] on the full AFLW dataset.

Note that we only train the discriminative regression methods with the frontal
face subset. Training the baseline methods using the full training set is
infeasible since AFLW contains varying point sets and these methods cannot
handle this issue. Simply filling the missing points with transformed mean
shape is possible, but training the baseline methods with this augmented point
sets lead to worse performance than using only the frontal face subset.

The comparative results are summarised in Table 3. The results suggest the
importance of deploying multiple models together with a model recommendation
framework to handle arbitrary views. Qualitative results by our method are
shown in Fig. 6.

Figure 5: Comparison of representative results between our method (first row)
and [32] (second row).
Figure 6: Illustrative results by our method on AFLW dataset. It is worth
pointing that all faces have extreme view pose (up to profile view or with in-
plane rotation).

###  4.2 Further Analysis

To validate the effectiveness of the proposed model recommendation trees, we
further compare our approach with some variants derived from our framework and
alternative strategies:

  1. (a)

No recommendation at all, _i.e_. always choosing the frontal model as
recommended model. This variant is equivalent to SDM [24];

  2. (b)

Prior head pose estimation before face alignment. This method is conceptually
similar to the conditional regression forest [8];

  3. (c)

Optimising landmarks locations based on multi-response map. This method is
conceptually similar to the study on consensus by regressors [27];

  4. (d)

Classification forest choosing the model with top voting;

  5. (e)

Classification forest using posterior class probability as rating.

Note that all the baselines exploits the same SDM models as those used in our
approach to ensure a fair comparison in the model recommendation process. We
compare all the methods on the challenging full AFLW dataset and the training
setting is similar to that described in Sec. 4.1. We adopt three evaluation
metrics, namely mean normalised error, visibility detection accuracy, and the
corresponding average precision. Visibility detection accuracy refers to the
percentage of landmarks predicted with correct visibility.

Results are provided in Table 4. Precision-Recall curve of visibility
evaluation is depicted in Fig. 7. Following [3], we treat invisible landmarks
as ‘positive’. The results suggest the effectiveness of the the proposed model
recommendation trees. It can be observed that an application of approaches
with prior head pose estimation [8] or occlusion handling [27] only gains
marginal improvement compared with the frontal-face SDM on the challenging
arbitrary-view face alignment task. Moreover, a naive application of
classification forest (both choosing top voted model or using posterior class
probability as rating) cannot achieve the desired results.

|  | Mean error
---
on AFLW
| Visibility detection
---
accuracy (%)
| Visibility
---
AP (%)
(a) | 6.98 | 83.20 | 42.35
(b) | 6.61 | 83.33 | 41.78
(c) | 6.65 | 87.89 | 47.08
(d) | 9.24 | 65.26 | 25.75
(e) | 7.62 | 87.65 | 45.79
Ours | 4.01 | 91.18 | 49.35
Table 4: Comparison of model recommendation between the proposed
recommendation trees and various baseline methods.
Figure 7: Visibility detection Precision-Recall curve compared to various
baseline methods, with representative samples. The black dot on the curve
denotes the visibility threshold. Threshold for each method is chosen to
maximise visibility detection accuracy on the validation set. Colors of the
annotated landmarks indicate our estimate of visibility (yellow for visible
and red for invisible). Best viewed in color.

##  5 Conclusion

We have presented a novel model recommendation framework to simultaneously
handle face alignment of arbitrary-view faces up to profile view. The
framework can flexibly work with different existing discriminative regression
based methods. It is capable of accommodating different landmark protocols
with varying point sets and inferring visibility of landmarks. Extensive
experiments on the full set of AFLW, MultiPIE, and AFW demonstrate the
effectiveness of our approach over existing multimodal face alignment methods.

## References

  * [1] P. N. Belhumeur, D. W. Jacobs, D. Kriegman, and N. Kumar.  Localizing parts of faces using a consensus of exemplars.  In CVPR, pages 545–552, 2011.
  * [2] L. Breiman.  Random forests.  Machine learning, 45(1):5–32, 2001.
  * [3] X. P. Burgos-Artizzu, P. Perona, and P. Dollár.  Robust face landmark estimation under occlusion.  In ICCV, pages 1513–1520, 2013.
  * [4] X. Cao, Y. Wei, F. Wen, and J. Sun.  Face alignment by explicit shape regression.  IJCV, 107(2):177–190, 2014.
  * [5] C. Chen, A. Dantcheva, and A. Ross.  Automatic facial makeup detection with application in face recognition.  In ICB, pages 1–8, 2013.
  * [6] T. F. Cootes, G. J. Edwards, and C. J. Taylor.  Active appearance models.  TPAMI, 23(6):681–685, 2001.
  * [7] T. F. Cootes, M. C. Ionita, C. Lindner, and P. Sauer.  Robust and accurate shape model fitting using random forest regression voting.  In Computer Vision–ECCV 2012, pages 278–291. Springer, 2012.
  * [8] M. Dantone, J. Gall, G. Fanelli, and L. Van Gool.  Real-time facial feature detection using conditional regression forests.  In CVPR, pages 2578–2585, 2012.
  * [9] A. Datta, R. Feris, and D. Vaquero.  Hierarchical ranking of facial attributes.  In AFGR, pages 36–42. IEEE, 2011.
  * [10] P. Dou, Y. Wu, S. K. Shah, and I. A. Kakadiaris.  Benchmarking 3d pose estimation for face recognition.  In Pattern Recognition (ICPR), 2014 22nd International Conference on, pages 190–195. IEEE, 2014.
  * [11] S. Du, Y. Tao, and A. M. Martinez.  Compound facial expressions of emotion.  Proceedings of the National Academy of Sciences, 111(15):E1454–E1462, 2014.
  * [12] G. Hermosilla, P. Loncomilla, and J. Ruiz-del Solar.  Thermal face recognition using local interest points and descriptors for hri applications.  In RoboCup 2010: Robot Soccer World Cup XIV, pages 25–35. Springer, 2011.
  * [13] V. Kazemi and S. Josephine.  One millisecond face alignment with an ensemble of regression trees.  In CVPR, 2014.
  * [14] M. Kostinger, P. Wohlhart, P. M. Roth, and H. Bischof.  Annotated facial landmarks in the wild: A large-scale, real-world database for facial landmark localization.  In ICCVW, pages 2144–2151, 2011.
  * [15] V. Le, J. Brandt, Z. Lin, L. Bourdev, and T. S. Huang.  Interactive facial feature localization.  In ECCV, pages 679–692, 2012.
  * [16] P. Matikainen, R. Sukthankar, and M. Hebert.  Model recommendation for action recognition.  In CVPR, pages 2256–2263, 2012.
  * [17] S. Ren, X. Cao, Y. Wei, and J. Sun.  Face alignment at 3000 fps via regressing local binary features.  In CVPR, 2014.
  * [18] C. Sagonas, G. Tzimiropoulos, S. Zafeiriou, and M. Pantic.  300 faces in-the-wild challenge: The first facial landmark localization challenge.  In ICCVW, pages 397–403, 2013.
  * [19] X. Shen, Z. Lin, J. Brandt, and Y. Wu.  Detecting and aligning faces by image retrieval.  In Computer Vision and Pattern Recognition (CVPR), 2013 IEEE Conference on, pages 3460–3467. IEEE, 2013.
  * [20] T. Sim, S. Baker, and M. Bsat.  The cmu pose, illumination, and expression database.  TPAMI, 25(12):1615–1618, 2003.
  * [21] Y. Sun, Y. Chen, X. Wang, and X. Tang.  Deep learning face representation by joint identification-verification.  In Advances in Neural Information Processing Systems, pages 1988–1996, 2014.
  * [22] Y. Taigman, M. Yang, M. Ranzato, and L. Wolf.  DeepFace: Closing the gap to human-level performance in face verification.  In CVPR, 2014.
  * [23] J. Xing, Z. Niu, J. Huang, W. Hu, and S. Yan.  Towards multi-view and partially-occluded face alignment.  In CVPR, pages 1829–1836, 2014.
  * [24] X. Xiong and F. De la Torre.  Supervised descent method and its applications to face alignment.  In CVPR, pages 532–539, 2013.
  * [25] C.-Y. Yang, S. Liu, and M.-H. Yang.  Structured face hallucination.  In Computer Vision and Pattern Recognition (CVPR), 2013 IEEE Conference on, pages 1099–1106. IEEE, 2013.
  * [26] H. Yang and I. Patras.  Sieving regression forest votes for facial feature detection in the wild.  In Computer Vision (ICCV), 2013 IEEE International Conference on, pages 1936–1943. IEEE, 2013.
  * [27] X. Yu, Z. Lin, J. Brandt, and D. N. Metaxas.  Consensus of regression for occlusion-robust facial feature localization.  In ECCV, pages 105–118, 2014.
  * [28] G. Zen, E. Sangineto, E. Ricci, and N. Sebe.  Unsupervised domain adaptation for personalized facial emotion recognition.  In Proceedings of the 16th International Conference on Multimodal Interaction, pages 128–135. ACM, 2014.
  * [29] Z. Zhang, P. Luo, C. C. Loy, and X. Tang.  Facial landmark detection by deep multi-task learning.  In ECCV, pages 94–108, 2014.
  * [30] X. Zhao, T.-K. Kim, and W. Luo.  Unified face analysis by iterative multi-output random forests.  In CVPR, pages 1765–1772, 2014.
  * [31] Y. Zhou, W. Zhang, X. Tang, and H. Shum.  A Bayesian mixture model for multi-view face alignment.  In CVPR, volume 2, pages 741–746. IEEE, 2005.
  * [32] X. Zhu and D. Ramanan.  Face detection, pose estimation, and landmark localization in the wild.  In CVPR, pages 2879–2886, 2012.


# Second-order Rate Analysis of a Two-user Gaussian Interference Channel with
Heterogeneous Blocklength Constraints

Kailun Dong, Pin-Hsun Lin, Marcel Mross and Eduard A. Jorswieck  Institute for
Communications Technology, Technische Universität Braunschweig, Germany
{k.dong, p.lin, m.mross<EMAIL_ADDRESS>

###### Abstract

We consider a two-user Gaussian interference channel with heterogeneous
blocklength constraints (HB-GIC), strong interference, and two private
messages. We propose to apply the successive interference cancellation with
early decoding, i.e., decoding a message with a number of received symbols
less than the blocklength at the receiver. We determine the necessary number
of received symbols to achieve successful decoding of the longer codeword that
satisfies the input power constraints and target average error probability
constraints. To attain the results, we investigate the dependence testing
bound analysis over an independent and identically distributed (i.i.d.)
Gaussian input. Besides, we derive the second-order achievable rate region of
the considered HB-GIC. By numerical results based on the rate-profile
approach, we compare the derived second-order rate region to the first-order
one, which shows the rate back-off of the considered model due to the impact
of finite blocklength.

##  I Introduction

Ultra-reliable and low-latency communication (URLLC) aims on providing high
reliability and low latency for 5G and related technologies, crucial in
applications like intelligent transportation, remote healthcare, and
industrial automation [01]. Extensive research supports its aim to achieve
sub-millisecond wireless communication, enabling real-time decision-making for
scenarios like autonomous vehicles and remote surgery. To achieve URLLC,
various technologies like forward error correction coding [03], adaptive
modulation, and interference management are essential. In practical
communication scenarios that involve large-scale and high communication rate
demands, such as live streaming of World Cup matches or mobile communication
networks during sudden natural disasters, the allocation of network resources
among users with limited bandwidth needs to be considered.

The diverse user requirements for latency and service quality have led to
research in heterogeneous blocklength-constrained networks. This idea was
first studied as static broadcasting in [shulman_static_2000], where a
broadcast channel with heterogeneous decoding deadlines was considered in a
first-order asymptotic setting with only a common message. Later, this concept
was extended to a network setting [langberg_beyond_2021], where each node owns
some messages and requires other messages with different decoding deadlines.
The concept of joint time-rate region therein was introduced to characterize
the tradeoff between achievable rates and decoding times. In
[nikbakht_dirty_2022], authors consider the case where the transmitter sends
two messages at different time points, and the receiver also has different
decoding time constraints for the two messages, for a point-to-point setting.
The second-order rate analysis of Gaussian broadcast channel (GBC) with
heterogeneous blocklength constraints has been studied in [24, Marcel,
Pin_lin]. The combination of superposition coding and early decoding (ED) with
successive interference cancellation (SIC) has been applied in this case with
i.i.d Gaussian input [06] and composite shell input [Marcel], respectively. As
a fundamental building block in multi-user information theory, the second-
order rate region of the Gaussian interference channel (GIC) was investigated
in [Le2015], where it was shown that not only the capacity but also the
dispersion is unaffected by the interference for both users. However, the
generalization to heterogeneous blocklength constraints is not
straightforward, since one user has to perform SIC with an incompletely
received interference codeword. This motivates the application of ED in the
setting of a GIC with heterogeneous blocklength constraints (HB-GIC). In
contrast to [24], in HB-GIC, messages from two users are transmitted through
their own channels, respectively, and also, messages of different transmitters
are independent and do not require superposition coding. Besides, interference
signals on the two cross-links are both received by each receiver.

The key idea of ED is that when the channel conditions are favorable, users
with higher output SNR can successfully decode with fewer received symbols
than the designed blocklength. Therefore, early decoding techniques can
improve the latency performance of communication systems. ED has been applied
with traditional first-order asymptotic analysis, for example, in finite-state
Markov channel [8] and half-duplex cooperative channels [Azarian]. In addition
to [8] and [Azarian], the concept of ED has also been used in several wireless
scenarios scenarios, such as cognitive radio (CR) [Jovicic], binary input
channels under a finite blocklength assumption [Sahin] and short message noisy
network [HouJie]. Note that these examples in the above references are only
based on the first-order analysis, but not the second-order analysis (in the
finite blocklength regime), which motivates our work.

Our main contribution is as follows. We investigate a two-user Gaussian
interference channel with heterogeneous blocklength and very strong
interference constraints. We propose an SIC scheme combined with ED and
analyze the errors in the first step of SIC at the stronger user 2 by using
the dependence testing (DT) bound [5]. We derive the minimum number of
received symbols at the receiver required for a successful ED and the
corresponding second-order rate region. By numerical results, we show and
discuss the impact of channel gains of the cross-link and the blocklength
constraints on the rate region in the second order.

This paper is organized as follows. In Section II, we introduce the system
model and some preliminaries. Section LABEL:sec:main-results introduces our
main results, and in Section LABEL:sec:numerical we show the numerical
simulation. We conclude in Section LABEL:sec:conclusion and sketch the proof
of our main result in Appendix LABEL:sec:proof.

_Notation_ $\colon$ Upper/lower case normal letters denote
random/deterministic variables. Upper-case calligraphic letters denote sets.
The notation $a_{i}^{j}$ denotes a row vector
$[a_{i},\,a_{i+1},\,\ldots,\,a_{j}]$, while $a_{1}^{j}$ is simplified to
$a^{j}$. We denote the inner product of two vectors $a^{j}$ and $b^{j}$ by
$\langle a^{j},b^{j}\rangle$. The probability of event $\mathcal{A}$ is
denoted by Pr$(\mathcal{A})$. The expectation and variance are denoted by
$\mathds{E}[\cdot]$ and $\mbox{Var}[\cdot]$, respectively. We denote the
probability density function (PDF) and cumulative distribution function (CDF)
of a random variable $X$ by $f_{X}$ and $F_{X}$, respectively. The random
variable $X$ following the distribution with CDF $F$ is denoted by
$\,X\sim\,F$. $\mathrm{Unif}(a,b)$ denotes the uniform distribution between
$a\in\mathds{R}$ and $b\in\mathds{R}$. We use
$X\mathbin{\rotatebox[origin={c}]{90.0}{$\vDash$}}Y$ to denote that $X$ and
$Y$ are stochastically independent. The logarithms used in the paper are all
with respect to base 2. We define
${\textsf{C}}(x)\triangleq\frac{1}{2}\log(1+x)$. Real additive white Gaussian
noise (AWGN) with zero mean and variance $\sigma^{2}$ is denoted by
$\mathcal{N}(0,\sigma^{2})$. We denote the indicator function by $\mathds{1}$.
We denote the inverse $Q$-function by $Q^{-1}(.)$ and the big-$\mathcal{O}$
notation by $\mathcal{O}(.)$.

##  II System Model and Preliminaries

###  II-A System Model

We consider a two-user HB-GIC with very strong interference, where each user
receives only private messages, and there is no common message shared between
them. Without loss of generality, we assume that $n_{1}>n_{2}$ and the channel
gain $a_{21}$ of the cross-link "$X_{1}\rightarrow Y_{2}$" is greater than the
channel gain $a_{12}$ of the cross-link "$X_{2}\rightarrow Y_{1}$", i.e.,
$a_{21}>a_{12}$. Based on the assumption, we define user 1 as the weaker user
and user 2 as the stronger user. The blocklengths of user 1 and user 2 are
denoted by $n_{1}$ and $n_{2}$, respectively. In addition, we consider the
very strong interference constraint: $a_{21}\geq 1+{\textsf{P}}_{2}$ and
$a_{12}\geq 1+{\textsf{P}}_{1}$[Moser_adv, Ch. 21], which is a sufficient
condition, where ${\textsf{P}}_{1}$ and ${\textsf{P}}_{2}$ are used in the
coming up definition of the power constraints. The received signals at users 1
and 2 at time $j$ can be equivalently expressed respectively as the following
standard form [Moser_adv]:

$\displaystyle\begin{cases}Y_{1,j}=X_{1,j}+\sqrt{a_{12}}X_{2,j}+Z_{1,j},\\\
Y_{2,j}=X_{2,j}+\sqrt{a_{21}}X_{1,j}+Z_{2,j},\quad\forall
j\in\left\\{1,\ldots,n_{2}\right\\},\end{cases}$ (1)

and

$\displaystyle\begin{cases}Y_{1,j}=X_{1,j}+Z_{1,j},\\\
Y_{2,j}=\sqrt{a_{21}}X_{1,j}+Z_{2,j},\quad\>\>\forall
j\in\left\\{n_{2}+1,\ldots,n_{1}\right\\},\end{cases}$ (2)

where $Z_{1,j}$ and $Z_{2,j}$ are two mutually independent additive white
Gaussian noises, denoted by
$Z_{1,j}\mathbin{\rotatebox[origin={c}]{90.0}{$\vDash$}}Z_{2,j}$, and both are
independent and identically distributed (i.i.d.), following a standard normal
distribution $Z_{1,j}\sim\mathcal{N}(0,1),\,Z_{2,j}\sim\mathcal{N}(0,1)$, for
all $j\in\\{1,\ldots,n_{1}\\}$.

The transmitters, as well as the receivers, have perfect knowledge of the
channel gains $a_{12}$ and $a_{21}$. The goal of the receiver $k$ is to decode
message $m_{k}\in\mathcal{M}_{k}$ within at most $n_{k}$ channel uses
($k=1,2$). Here the channel inputs
$X_{1}^{n_{1}}\in\mathcal{F}^{n_{1}}\subseteq\mathbb{R}^{n_{1}}$ and
$X_{2}^{n_{2}}\in\mathcal{F}^{n_{2}}\subseteq\mathbb{R}^{n_{2}}$, while
$\mathcal{F}^{n_{1}}$ and $\mathcal{F}^{n_{2}}$ are sets of feasible codewords
satisfying the upcoming power constraints in (4) and (5). The considered code
is formally defined as follows:

###### Definition 1

An
$(n_{1},n_{2},{\textsf{M}}_{1},{\textsf{M}}_{2},\epsilon,\mathcal{F}^{n_{1}},\mathcal{F}^{n_{2}})$-code
for an HB-GIC ${\textsf{P}}_{Y_{1},Y_{2}|X_{1},X_{2}}$ consists of:

  * •

Two message sets $\mathcal{M}_{1}=\\{1,2,\dots,{\textsf{M}}_{1}\\}$,
$\mathcal{M}_{2}=\\{1,2,\dots,{\textsf{M}}_{2}\\}$,

  * •

Two encoders $\phi_{1}:\mathcal{M}_{1}\rightarrow\mathcal{F}^{n_{1}}$,
$\phi_{2}:\mathcal{M}_{2}\rightarrow\mathcal{F}^{n_{2}}$,

  * •

Two decoders $\psi_{1}:\mathbb{R}^{n_{1}}\to\mathcal{M}_{1}$,
$y_{1}^{n_{1}}\mapsto\hat{m}_{1}$;
$\psi_{2}:\mathbb{R}^{n_{2}}\to\mathcal{M}_{2}$,
$y_{2}^{n_{2}}\mapsto\hat{m}_{2}$.

Assume the message tuple $(m_{1},m_{2})$ is uniformly selected from
$\mathcal{M}_{1}\times\mathcal{M}_{2}$, and the average system error
probability satisfies

$\displaystyle{\textsf{P}}_{e}$
$\displaystyle:=\\!\frac{1}{{\textsf{M}}_{1}{\textsf{M}}_{2}}\\!\sum_{m_{1}=1}^{{\textsf{M}}_{1}}\sum_{m_{2}=1}^{{\textsf{M}}_{2}}\Pr(\hat{m}_{1}\\!\neq\\!m_{1}\hskip
2.84544pt\text{or}\hskip
2.84544pt\hat{m}_{2}\\!\neq\\!m_{2}\mid\text{($m_{1}$, $m_{2}$) is sent})$
$\displaystyle\leq\epsilon,$ (3)

where $\epsilon$ is the target decoding error probability.

We consider the maximal power constraints on the channel inputs, which
correspond to the following feasible sets:

$\displaystyle\mathcal{F}^{n_{1}}$
$\displaystyle=\mathcal{F}_{\mathrm{max}}^{n_{1}}({\textsf{P}}_{1}):=\\{x_{1}^{n_{1}}:||x_{1}^{n_{1}}||^{2}\leq
n_{1}{\textsf{P}}_{1}\\},$ (4) $\displaystyle\mathcal{F}^{n_{2}}$
$\displaystyle=\mathcal{F}_{\mathrm{max}}^{n_{2}}(\mathsf{{\textsf{P}}_{2}}):=\\{x_{2}^{n_{2}}:||x_{2}^{n_{2}}||^{2}\leq
n_{2}{\textsf{P}}_{2}\\},$ (5)

where ${\textsf{P}}_{1}$ and ${\textsf{P}}_{2}$ are constants, and an encoding
error is detected when the generated codeword $x_{1}^{n_{1}}$ does not belong
to $\mathcal{F}^{n_{1}}$, or $x_{2}^{n_{2}}$ does not belong to
$\mathcal{F}^{n_{2}}$.

Figure 1: System model of a two-user HB-GIC

We consider that two mutually independent codewords
$\\{x_{1}^{n_{1}}(m_{1}):m_{1}\in\mathcal{M}_{1}\\}$ and
$\\{x_{2}^{n_{2}}(m_{2}):m_{2}\in\mathcal{M}_{2}\\}$ are both i.i.d. Gaussian
generated:

$\displaystyle\begin{cases}X_{1,j}\sim\mathcal{N}(0,{\textsf{P}}_{1}),\qquad\forall
j\in\left\\{1,\cdots,n_{1}\right\\},\\\
X_{2,j}\sim\mathcal{N}(0,{\textsf{P}}_{2}),\qquad\forall
j\in\left\\{1,\cdots,n_{2}\right\\}.\end{cases}$

Similar to [Pin_lin], we consider an SIC decoding scheme based on threshold
decoding. At the stronger user, i.e., user 2, the decoder in the first step of
SIC finds the smallest [5] $m\in\mathcal{M}_{1}$, such that
$i(x_{1}^{n_{2}}(m);y_{2}^{n_{2}})>\log{\textsf{M}}_{1}$, where
$i(\cdot;\cdot)$ is the information density. If a unique index $m$ is found,
set $\hat{m}_{1}=m$. Otherwise, it declares an error. Based on $\hat{m}_{1}$,
the decoder 2 in the next step finds the smallest $m\in\mathcal{M}_{2}$, such
that $i(x_{2}^{n_{2}}(m);\tilde{y}_{2}^{n_{2}})>\log{\textsf{M}}_{2}$, where
$\tilde{y}_{2}^{n_{2}}$ is the received signal subtracting the signal
$x_{1}^{n_{2}}(\hat{m}_{1})$, i.e.,
$\tilde{y}_{2}^{n_{2}}=y_{2}^{n_{2}}-x_{1}^{n_{2}}(\hat{m}_{1})$. If a unique
index $m$ is found, set $\hat{m}_{2}=m$. Otherwise, it declares an error. At
the weaker user, i.e., user 1, the decoder in the first step finds the
smallest $m\in\mathcal{M}_{2}$, such that
$i(x_{2}^{n_{1}}(m);y_{1}^{n_{1}})>\log{\textsf{M}}_{2}$. If a unique index m
is found, set $\hat{m}_{2}=m$. Otherwise, it declares an error. Based on
$\hat{m}_{2}$, the decoder 1 in the next step finds the smallest
$m\in\mathcal{M}_{1}$, such that
$i(x_{1}^{n_{1}}(m);\tilde{y}_{1}^{n_{1}})>\log{\textsf{M}}_{1}$, where
$\tilde{y}_{1}^{n_{1}}$ is the received signal subtracting the signal
$x_{2}^{n_{1}}(\hat{m}_{2})$, i.e.,
$\tilde{y}_{1}^{n_{1}}=y_{1}^{n_{1}}-x_{2}^{n_{1}}(\hat{m}_{2})$. If a unique
index $m$ is found, set $\hat{m}_{1}=m$. Otherwise, it declares an error.

###  II-B Preliminaries

We define the successful ED as follows:

###### Definition 2

[Pin_lin, Def.1] A successful ED means that the stronger user (user 2) with a
shorter blocklength constraint can decode messages of the weaker user (user
1), who has a longer blocklength constraint, from the first $\tilde{n}_{1}$
received symbols: [$Y_{2,1},Y_{2,2},\cdots,Y_{2,\tilde{n}_{1}}$], where
$\tilde{n}_{1}\leq n_{2}<n_{1}$, while the resulting error probability
fulfills the target error probability constraint.

###### Remark 1

Please note that without ED, the stronger user (user 2) must wait for $n_{1}$
received symbols to start the SIC. In contrast, by ED, the SIC can be finished
earlier, which reduces the latency.