# Generating Master Faces for Dictionary Attacks with
a Network-Assisted Latent Space Evolution

Ron Shmelkin1∗, Tomer Friedlander2∗ and Lior Wolf1
1The Blavatnik School of Computer Science, Tel Aviv University 2The School of
Electrical Engineering, Tel Aviv University *Equal contribution

###### Abstract

A master face is a face image that passes face-based identity-authentication
for a large portion of the population. These faces can be used to impersonate,
with a high probability of success, any user, without having access to any
user-information. We optimize these faces, by using an evolutionary algorithm
in the latent embedding space of the StyleGAN face generator. Multiple
evolutionary strategies are compared, and we propose a novel approach that
employs a neural network in order to direct the search in the direction of
promising samples, without adding fitness evaluations. The results we present
demonstrate that it is possible to obtain a high coverage of the LFW
identities (over 40%) with less than 10 master faces, for three leading deep
face recognition systems.

##  I INTRODUCTION

In dictionary attacks, one attempts to pass an authentication system by
sequentially trying multiple inputs. In real-world biometric systems, one can
typically attempt only a handful of inputs before being blocked. However, the
matching in biometrics is not exact, and the space of biometric data is not
uniformly distributed. This may suggest that with a handful of samples, one
can cover a larger portion of the population.

Indeed, as we show for the case of face recognition, there are face images
that would be authenticated successfully, using state of the art face
recognition systems and acceptable match thresholds, of a large portion of
users in a given dataset. In some cases, a single face can cover more than 20%
of the identities in LFW. Following previous work on fingerprints [33], we
term such faces “master faces”, due to the analogy to master keys.

The process of master face generation employs a realistic face generator
network, in our case StyleGAN [15]. Since the objective function, i.e., the
number of identities that are similar enough to the face image we optimize, is
non-differentiable, black box optimization methods are utilized.
Unsurprisingly, we find that optimization methods that are tailored for high
dimensional data outperform other methods. We then propose a novel method, in
which a trained neural network is used to predict the competitiveness of a
given sample.

When attempting to cover an even larger number of faces, we advocate for a
greedy method in which one repeats the master face generation process
sequentially, each time to cover the identities that were not covered by the
previously generated faces. Using such a greedy process, we obtain coverage of
40%-60% with nine images (the focus on nine images arises from a different
experiment, in which the samples in the latent space are clustered).

The experiments are conducted using three different deep face recognition
systems, each with its own processing pipeline, training dataset, objective,
and similarity measure. The similarity threshold used is a conservative one
that is based on obtaining a standard FAR value of 0.001, or, when available,
is the one prescribed by the method itself.

Overall, our results indicate that performing a dictionary attack of face
authentication systems is feasible at high success rates. This is demonstrated
for multiple face representations and explored with multiple, state-of-the-art
optimization methods.

##  II Related work

#### Face Verification

Face Verification is the task of comparing two face thumbnail images and
determining whether or not they belong to the same subject. In the past few
years, deep neural network (DNN) approaches have dominated the field, e.g.
[18, 35, 42, 39]. These DNNs learn embedding face representations, such that
the distance under a certain similarity metric (e.g. cosine distance,
euclidean distance etc.), corresponds to the face similarity. Different loss
functions have been presented for the purpose of achieving such a behavior,
e.g., the triplet loss [35], angular loss [41] and contrastive loss [2].

Face verification is often assessed by considering the False Acceptance Rate
(FAR) and the False Rejection Rate (FRR). FAR is the percentage of embedding
representations in which different subjects were incorrectly authorized as the
same person, FRR is the percentage of embedding representations in which
embedding representations that belong to the same subject were incorrectly
rejected. There is a trade-off between these two metrics, which is balanced by
a matching distance threshold $\theta$.

#### Face Image Generation using GAN

The Generative Adversarial Network (GAN) [5] is a machine learning framework
in which two neural networks, the generator $G$ and the discriminator $D$, are
trained in the form of min-max game. Given the dataset distribution $X$ and
$z\sim Z$ latent input vector, the goal of $G$ is to generate samples
$G(z)\sim X$. Given a data sample $x$, $D$ is trained to determine whether
$x\sim X$ or $x\sim G(z)$, where $z\sim Z$. On the other hand, $G$ is trained
to create samples for which $D$ fails to discriminate between the two. The
quality and resolution of data samples generated using GANs have been
constantly improving. One of the most notable lines of work is that of the
StyleGAN Face Image Generation (FG) [15, 16].

StyleGan [15] applies a mapping neural network $f:Z\rightarrow W$ to convert
the latent vector $z$ into a more disentangled latent representation $w$ that
separates content and style. It is then fed to each convolutional layer of
generator through the adaptive instance normalization (AdaIN) [12]. This
allows better control of the image synthesis process and results in the
generation of quality and more detailed images.

#### Master sample attacks

A parallel work that we became aware of post-publication [27] attempts to
generates faces that are similar to a large portion of the faces in a given
dataset using StyleGAN but with a different evolutionary strategy, which is
one of our baselines (CMA-ES). In the field of finger print verification, Roy
et al. [33] have suggested to exploiting the lower quality of partial
fingerprint systems to generate fingerprint templates that can be matched to a
large number of users’ fingerprints, without any knowledge of the actual user.
This generation does not produce an actual image, which is required for the
actual match.

To produce such an image, Bontrager et al. [1] used a deep neural network. Our
work performs a similar task for faces. In comparison to fingerprints, faces
are characterized by a larger latent space, and we develop an optimizer that
is better suitable for large dimensions. In a very extensive set of
experiments, we explore various state of the art solutions and demonstrate the
effectiveness of our method.

#### Evolution Strategies

Covariance Matrix Adaptation Evolution Strategy (CMA-ES) [9] is a type of an
iterative evolutionary algorithm extensively used for solving non-convex
continuous optimization problems with no usage of gradient information. It is
considered one of the most powerful stochastic numerical optimizers used for
solving difficult black-box problems [40].

At each iteration, CMA-ES generates a population of $\lambda$ candidate
solutions, by sampling a multivariate Gaussian distribution, whose mean vector
and covariance matrix were estimated in the previous iterations. The $\mu$
fittest candidates in terms of the objective function are selected out of the
current population and are used to adapt the last estimate of the model’s
learnable parameters.

The quadratic time and space-complexity of CMA-ES limit its applicability for
high-dimensional problems [40] and its performance degrades significantly [28]
in larger dimensions. Limited-Memory Matrix Adaptation Evolution Strategy (LM-
MA-ES) [22] reduces the time and storage complexity to
$\mathcal{O}(n\log{n})$. This algorithm is reported to perform well on high-
dimensional variants of well established benchmark problems. This makes LM-MA-
ES an appropriate choice for solving the high-dimensional black-box
optimization problem in the current work.

Evolutionary algorithms assisted by an additional machine learning model have
been presented in the literature, e.g., surrogate-assisted CMA-ES algorithms
[30]. Some models train a regression model online with the evolutionary
algorithm in order to learn the fitness function of the black-box problem [7].
Instead of computing the expensive fitness function itself for all candidates,
the fitness scores of some candidates are predicted by this regression model,
and as a result, the number of evaluation calls is decreased. Models can be
assisted by the surrogate for another purpose of predicting if a given
candidate is going to be competitive in terms of its fitness score and
evaluate only such candidates. ACM-ES [23] is an example of such a model,
which uses a comparison-based surrogate, instead of a regression model.

In our work, we train a neural classifier coupled with the evolutionary
algorithm in order to predict a given candidate’s probability to be fitter
(lower fitness) relative to candidates generated in the few last iterations,
without evaluating its fitness score explicitly.

##  III METHODOLOGY

Given a dataset $D=\\{x\in\mathbbm{R}^{w\times h\times c}\\}$ which contains
face images (each of size $w\times h$ and with $c$ channels) with a single
image per subject, a deep convolutional face embedding model
${\mathcal{M}}(x)\in\mathbbm{R}^{d}$ and a matching threshold $\theta$, we
define the Master Face $\mathbf{x_{mf}}$ as following:

$\mathbf{x_{mf}}=\operatorname*{arg\,max}_{x_{mf}}\sum_{x\in
D}f({\mathcal{M}}(x_{mf}),{\mathcal{M}}(x)),\theta)$ (1)

The binary function $f:\mathbbm{R}^{2d+1}\rightarrow\\{0,1\\}$ compares two
embedding vectors and assigns a value of $1$, if the embeddings are similar by
some similarity by the amount determined by the threshold $\theta$. We note
that our method searches for an optimal face image $x_{mf}$ and for an optimal
embedding

$c=\operatorname*{arg\,max}_{c}\sum_{x\in D}f(c,{\mathcal{M}}(x),\theta)$ (2)

.

As we show in Sec. IV-A, it is not possible to invert ${\mathcal{M}}$
effectively and obtain ${\mathcal{M}}^{-1}(c)\in\mathbbm{R}^{w\times h\times
c}$ which achieves both high visual quality and a high coverage.

Instead, we suggest to optimize the Face Generator’s latent vector $z$ based
on its matching score, in order to find a better representation in the image
space.

$\mathbf{z_{opt}}=\operatorname*{arg\,max}_{z}\sum_{x\in
D}f({\mathcal{M}}({\mathcal{G}}(z)),{\mathcal{M}}(x)),\theta)$ (3)

Since, by convention, evolutionary algorithms minimize the score instead of
maximizing it, the above matching score is altered by subtracting it from the
total number of face images in the training set $n=|D|$. Moreover, the score
is normalized to be in $[0,1]$.

$\mathbf{z_{opt}}=\operatorname*{arg\,min}_{z}\frac{1}{n}(n-\sum_{x\in
D}f({\mathcal{M}}({\mathcal{G}}(z)),{\mathcal{M}}(x),\theta))$ (4)

Figure 1: An overview of the generation flow for finding a master face.

An overview of the method is given in Fig. 1. Initially, the dataset $D$ is
transformed to the embedding space. Denote the embedded dataset by
$\widehat{D}=\\{{\mathcal{M}}(x):~{}\forall x\in D\\}$. An evolutionary
algorithm is used to find the optimal latent vector $\mathbf{z_{opt}}$, which
solves the optimization problem defined in Eq. 4. At each iteration of the
optimization algorithm, a set of candidate solutions is generated and
evaluated by the fitness function. Given a candidate latent vector $z$, an
image corresponding to $z$ is generated by applying the face generator
${\mathcal{G}}$ on $z$. The face is then extracted from the generated image
${\mathcal{G}}(z)$ and is embedded using the face description model
${\mathcal{M}}$.

###  III-A The evolutionary algorithm

(a)

(b)

Figure 2: (a) Training the success predictor using samples stored in memory
$H$. (b) Filtering generated candidates by the success predictor and updating
$H$.

We present an evolutionary algorithm that is coupled with a neural predictor.
The latter estimates the probability of a given candidate to be fitter (lower
fitness score) than the p-percentile of candidates generated during the few
last iterations. These estimated probabilities are used to obtain a set of
promising candidates for the purpose of enhancing the latent space
optimization.

The LM-MA-ES evolutionary algorithm, which is known to perform well on high-
dimensional black box optimization problems, is selected as the baseline
method for the optimization problem in Eq. 4. At each iteration, the original
variant of LM-MA-ES generates a population of $\lambda$ candidate solutions
and the $\mu$ fittest candidates are selected for adjusting the parameters of
the model. Since the candidates are generated randomly by sampling the
probability density learned by the LM-MA-ES model, some of the candidates may
be unsuccessful in terms of their fitness score. In order to obtain a set of
successful candidates in a higher probability, we suggest training a neural
classifier for predicting the probability of a given candidate to be fitter
than the p-percentile of stored samples from the few last iterations. We use
this classifier, named the Success Predictor, to filter the more probable
candidates to be promising out of a larger generated set, without the need to
explicitly evaluate their fitness scores.

Let $h$ be a neural classifier, which gets a vector $z$ as an input. The
training process of classifier $h$ is described in Fig 2(a) and is performed
online in the end of each iteration of the evolutionary algorithm. The
training samples are candidates generated during the last few iterations of
the evolutionary algorithm, which are stored in a finite memory $H$ with a
capacity of $C$ samples. Each new evaluated candidate and its fitness score
are added to the memory $H$. When the memory $H$ becomes over-occupied,
excessive samples are removed out of it randomly, without removing the best
candidate. After each update of the memory $H$, each sample $z_{i}$ in $H$ is
defined to be a successful candidate (labeled +1), if its fitness score is
better than the p-percentile of the fitness scores of all samples stored in
the memory. Otherwise, it is defined as an unsuccessful candidate (labeled 0).
Let $(z_{i},y_{i})\in H$ be the i-th sample in the memory and its
corresponding label. The classifier is trained to successfully classify the
class of the training samples, by minimizing the binary cross entropy loss
between the predicted class and the the true class:

$\mathcal{L}_{BCE}=-\frac{1}{|H|}\sum_{(z_{i},y_{i})\in
H}[y_{i}log(h(z_{i}))+(1-y_{i})log(1-h(z_{i}))]$ (5)

The classifier $h$ is used in the inference mode during the generation step of
the evolutionary algorithm, as described in Fig. 2(b). Instead of generating
only $\lambda$ candidates, $\lambda^{\prime}>\lambda$ candidates are
generated. Prior to evaluating the candidates’ fitness values, each candidate
is forwarded through the classifier $h$ in order to obtain a score
representing its probability of belonging to the successful class of samples.
The scores of all $\lambda^{\prime}$ candidates are concatenated to a single
vector, which is afterwards converted to a probability vector by applying the
Softmax operator. Then, only $\lambda$ candidates are selected to be
evaluated, by sampling them out of the total $\lambda^{\prime}$ candidates
according to the obtained probability scores. The rest of the evolutionary
algorithm steps remain unchanged and are performed on these $\lambda$
candidates, in particular, the fittest $\mu$ candidates are chosen out of this
already filtered set.

After evaluating the fitness scores of the new filtered candidates, we can
retrospectively determine if these candidates were correctly classified by the
classifier $h$ earlier. In particular, if a candidate which obtained a
prediction score higher (lower) than 0.5 by $h$, is indeed (less) fitter than
the p-percentile of the samples in the memory $H$. Correspondingly, the
performance of $h$ is tested, by calculating the averaged prediction accuracy
on these new candidates. If this averaged accuracy becomes lower than a
predefined threshold, $\tau_{acc}$, for a predefined number of $T$ iterations,
the learnable parameters of $h$ are re-initialized randomly. Moreover, we use
a predefined warm-up period of iterations at the first generations of the
evolutionary algorithm for which the classifier is only trained, but is not
used for filtering new candidates.

###  III-B Dataset coverage

Given a set of face images $D$, we strive to find a minimal set of master face
images $S=\\{x\in\mathbbm{R}^{w\times h\times x}\\}$ such that for as many
subjects $x\in D$ as possible, there is a least one $x^{\prime}\in S$ such
that $f({\mathcal{M}}(x),{\mathcal{M}}(x^{\prime}),\theta)$ is one.

A natural choice is to divide the embedding space into clusters, e.g., by
using KMeans [24], and optimize each member of $S$ to cover a different
cluster, e.g., by considering the center of each cluster. However, as shown in
IV-A it is difficult to invert the cluster centroid point to the image space.
Thus, we propose a greedy approach Alg. 1 to find such set of master face
images. After each iteration, the dataset $D$ is reduced by already covered
face images, namely, images that were already incorrectly authorized with the
generated master face of the current iteration, are removed from the dataset
and the next search iteration is performed on the updated dataset. Therefore,
the current generated master face might cover some face images, which were
already covered by previously generated master faces, while the opposite
direction cannot occur. However, such an intersection does not result in
counting covered face images twice in the total coverage percentage
calculation, since the current coverage iteration is performed on the reduced
dataset.

The method uses the function $find\\_matched$, which given a face image
$x_{mf}^{i}$ and the dataset $D$ $find\\_matched$ returns the set of faces
from $D$ that are incorrectly authorized with $x_{mf}^{i}$. We set the limit
of the number of iterations in Alg. 1 to be the number of clusters that cover
most of the $\widehat{D}$, as presented in Sec. IV-A.

1:function find coverage(${\mathcal{G}},D,{\mathcal{M}},\theta,max\\_iter$)

2: $center\\_imgs\leftarrow[]$

3: for $i=1..{max\\_iter}$ do

4: $x_{mf}^{i}\leftarrow\textrm{master face
generation}({\mathcal{G}},D,{\mathcal{M}},\theta)$

5: $center\\_imgs\leftarrow center\\_imgs\bigcup x_{mf}^{i}$

6: $D\leftarrow D\backslash\ find\\_matched(D,x_{mf}^{i})$

7: end for

8: return $center\\_imgs$

9:end function

Algorithm 1 $greedy$-Coverage Search

##  IV Experiments

We evaluated our method with three different CNN based, face descriptors:
FaceNet [35], SphereFace [42], and Dlib [18]. Each face descriptor is equipped
with its own combination of an architecture, a similarity metric and a loss
function, thus providing additional validation of our method.

The FaceNet implementation employs an Inception-ResNetV1 [38]. It obtains a
$0.9905$ accuracy on the LFW face verification benchmark. The SphereFace face
descriptor is implemented as a deep neural network with 20 convolutional
layers. An accuracy of $0.9922$ is measured on the LFW face verification
benchmark. In both cases, the face regions are extracted and aligned using
MTCNN [14], the embeddings similarity is measured by cosine distance, training
takes place on the CasiaWebface [43] dataset. The embedding dimension is 512.
The thresholds for the FaceNet and SphereFace were chosen to preserve $FAR\sim
0.001$.

We also use the Dlib face descriptor implementation [18], which employs a
ResNet with 29 convolutional layers. This architecture is ResNet-34 [10] with
a reduced number of layers, in which the number of filters per layers is
reduced by half. The LFW accuracy reported is $0.9938$. The model trained on
the face scrub [26], VGG [29] and additional face images scraped from the
internet. The model embeds the face images in $\mathbbm{R}^{128}$ and employs
the euclidean distance with a predefined recommended threshold $\theta=0.6$.
The face detection and alignment processes use Dlib’s detector [17].

As a face image generator ${\mathcal{G}}$ StyleGAN [15] is used, in which
${\mathcal{G}}:\mathbbm{R}^{512}\rightarrow\mathbbm{R}^{1024\times 1024\times
3}$. We use the pre-trained StyleGAN model, trained with FFHQ [15] dataset.

The architecture of Success Predictor $h$ is a feed-forward neural network
with three fully connected layers, whose output dimensions are 256, 128 and 1
neurons respectively. The first two hidden layers and the output layer are
followed by the ELU [3] activation function and a Sigmoid respectively. The
first hidden layer uses the BatchNorm regularization layer [13], prior to the
activation function. The network is trained using the ADAM [19] optimizer with
a learning rate of $0.001$ on mini-batches of size 32. The population size
$\lambda$ is set to $22$ according to the calculation in [22] and
$\lambda^{\prime}$ is set to 1,000 candidates. The threshold defining the
promising class is set to the 5-th percentile. The capacity $C$ of the memory
$H$ is set to 5000 samples. The parameters $\tau_{acc}$ and $T$ are set to 0.6
and 20 respectively. The warm-up period of $h$ is set to the first 5% of the
evolutionary algorithm iterations.

The method is evaluated on the LFW [11] dataset. One image per subject is
used. In Sec. IV-B, we evaluated our approach on the predefined split
$|D_{train}|/|D_{test}|=4038/1711$ while in Sec. IV-C and Sec. IV-A we perform
a coverage search on the whole dataset $|D|=5749$.

Note that, since we compare a new generated face to the set of different
subjects, we measure the matching score as Mean Set Coverage (MSC).

$MSC=\frac{\\#\textrm{of incorrect authorization }}{|D|}*100$

###  IV-A Cluster centroid inversion

We first explore the alternative method of clustering the data in the
embedding space and then trying to convert the prototypes found to images.
This also provides an estimate of the number of target master faces that one
can use, in an ideal case in which one can use a dictionary attack with
embeddings and not with real-world faces.

In this experiment, we focus on the Dlib face descriptor. An embedding dataset
$\widehat{D}$ is created and then clustered using KMeans [24]. With nine
clusters $\sim 91.63\%$ of $\widehat{D}$ was covered, i.e. in the embedding
space we were able to find nine center points (cluster centroids) such that
over 90% of the samples in $\widehat{D}$ were in the euclidean distance of
less than $\theta=0.6$ away from at least one of these centroids.

Since the actual master-based dictionary attack requires using images, we
trained a neural network to generate a face image from the Dlib’s embedding
representation. Specifically, we trained a neural network face generator
$G:\mathbbm{R}^{128}\rightarrow\mathbbm{R}^{64x64x3}$ with five layers. The
layers consist of one linear layer and four de-convolutional, similar to the
generator’s architecture presented in the DC-GAN [31]. The generator $G$ was
trained on the Dlib’s embedding representation of the FFHQ[15] dataset. It is
trained to minimize MSE loss between the generated image and the original one.

$\mathcal{L}_{MSE}=\frac{1}{|D_{FFHQ}|}\sum_{x\in
D_{FFHQ}}(x-G({\mathcal{M}}(x)))^{2}$ (6)

While $G$ performs well on embeddings of the real image, the visual quality in
the case of cluster centroids is unsatisfactory, see Fig. 3. Moreover, only
two out of the nine generated faces are detected as faces by the Dlib
detector. These generated faces are also ineffective as master faces and the
highest MSC score of any of the nine is only $\sim 2\%$.

|  |  |  |
---|---|---|---|---
|  |  |  |
Figure 3: Clusters center in latent space, converted to image space

###  IV-B Experiments for one Master Face image

The generic scheme we present for optimizing a single image, as depicted in
Fig. 1, is employed for recovering a single Master Face image. For each face
descriptor, each black box optimization method was trained on $D_{train}$ for
five runs. Each run differs in its initial random seed. Out of the face images
obtained from all five runs, the one which achieved the highest MSC score on
the training dataset, was chosen to be reported as the master face obtained
for this face descriptor on the training dataset. This way, we eliminate some
of the sensitivity of such optimization methods to the random seed, without
using any test data.

For the sake of making a fair comparison, all algorithms were trained for an
equal number of fitness function calls (26400) with the same set of five
seeds. The number of fitness function calls was chosen based on the
observation that longer training processes resulted in a negligible
improvement. After this selection process, each master face was then evaluated
on the test dataset, $D_{test}$.

We compare the performance of our method, which is denoted by LM-MA-ES (LME) +
Success Predictor to the following baselines: (i) A random Search algorithm
was used to set the baseline results. We used the version implemented in the
Nevergrad package [32]. (ii) LM-MA-ES [22] is the high-dimensional variant of
CMA-ES [9], which our method is based on. (iii) For completeness, the original
CMA-ES algorithm is compared, although despite not being suitable for high
dimensions. We use the implementation from the pycma package [8].

Differential Evolution (DE) is another very successful family of evolutionary
algorithms. In addition to original (iv) DE [37], we compare to the newer
variants (v) LSHADE-RSP [36] and (vi) IMODE [34], which achieved the second
place in the IEEE CEC’2018 competition and the first place in the IEEE
CEC’2020 competition respectively.

(vii) NGOpt [21] is an algorithm which automatically selects the right
evolutionary algorithm to be trained out of a set of several algorithms,
according to the properties of the optimization problem. NGOpt is implemented
in the Nevergrad package. (viii) ACM-ES [23] is a surrogate-assisted CMA-ES
variant with a comparison-based surrogate (ranking SVM). Similar to our
approach, it selects to evaluate only a subset of candidates predicted to be
promising according to the surrogate model. The initial larger population and
the warm-up period is set like the model assisted by the Success Predictor. We
use the implementation from the BOLeRo package [4]. (ix) lq-CMA-ES [7] is a
surrogate-assisted CMA-ES variant, which is assisted by a linear-quadratic
regression model (LQ) It uses the surrogate for decreasing the number of
evaluations and not for predicting promising candidates. We use the
implementation from pycma [8]. (x) For the purpose of comparing our model more
directly to another surrogate-assisted model, we add this LQ regression model
to the LM-MA-ES algorithm and train it online as done in lq-CMA-ES. This
variant is named LME + LQ-Filter. Similar to our method, a larger set of
$\lambda^{\prime}>\lambda$ candidates is generated by the LM-MA-ES. Their
fitness score is then predicted by the LQ model and their success probability
is estimated by applying the Softmax function on the negated predicted fitness
scores. The estimated probabilities are used for sampling a smaller set of
$\lambda$ candidates. For the purpose of adjusting the LM-MA-ES’s parameters
fairly, the actual fitness values of all selected candidates are evaluated,
instead of using the predicted values by the LQ model.

Table I presents a comparison between the different optimization algorithms
for the master face generation task, in terms of the MSC score. It can be
observed that our LM-MA-ES+Success Predictor achieved the highest result among
all compared algorithms on the train set for two out of three face
descriptors, when considering either the train set or the test set. When not
leading, our LM-MA-ES assisted by the Success Predictor achieved the second
best result. In comparison to the the original LM-MA-ES, LM-MA-ES assisted by
the Success Predictor achieved better results on all three training sets and
on two out of three test sets. Moreover, the Success Predictor seems to better
improve the LM-MA-ES baseline algorithm than the LQ regression model in all
experiments, except for the training set of SphereFace. In addition, LM-MA-ES
assisted by the Success Predictor outperforms the comparison-based surrogate-
assisted ACM-ES in all experiments. An additional observation is that the high
MSC results on the training set, are often preserved on the test set.

In general, algorithms from the CMA-ES family perform better than other
algorithms, like the DE family. In particular, the original implementation of
the LM-MA-ES[22] performs better than the CMA-ES as expected on a high-
dimensional optimization problem. In fact, LM-MA-ES performs the best among
the original variants with no additional assisting models. It is worth
mentioning that even though the lq-CMA-ES achieved worse results than the
original CMA-ES, as might be expected from its usage of predicted fitness
values instead of the actual ones, its training process is faster. In Fig. 4,
we present the generated master face images with the highest MSC score for
each of the face descriptors.

TABLE I: Generated master faces MSC score (%) for different optimization methods. | Dlib | FaceNet | SphereFace
---|---|---|---
Optimization Algorithm | Train | Test | Train | Test | Train | Test
RandomSearch | $5.78$ | $4.73$ | $9.69$ | $9.94$ | $7.60$ | $6.78$
DE | $7.08$ | $5.67$ | $12.29$ | $11.87$ | $14.12$ | $13.68$
LSHADE-RSP | $10.09$ | $8.30$ | $15.90$ | $15.20$ | $15.73$ | $11.52$
IMODE | $7.70$ | $6.06$ | $12.36$ | $12.04$ | $11.64$ | $11.52$
CMA-ES | $18.17$ | $16.32$ | $16.75$ | $16.43$ | $16.84$ | $15.49$
NGOpt | $14.04$ | $12.71$ | $16.62$ | $15.20$ | $17.24$ | $16.37$
lq-CMA-ES | $7.38$ | $6.12$ | $13.10$ | $12.57$ | $9.31$ | $9.82$
ACM-ES | $18.09$ | $17.61$ | $16.00$ | $14.50$ | $16.67$ | $16.84$
LM-MA-ES (LME) | $18.27$ | $17.97$ | $17.12$ | $\mathbf{16.96}$ | $17.39$ | $16.96$
LME + LQ-Filter | $18.87$ | $16.67$ | $16.60$ | $14.91$ | $\mathbf{17.79}$ | $17.42$
LME + Success Pred. | $\mathbf{22.43}$ | $\mathbf{21.56}$ | $\mathbf{17.36}$ | $16.60$ | $17.51$ | $\mathbf{17.60}$
| Dlib | FaceNet | SphereFace
---|---|---|---
(a) |  |  |
(b) |  |  |
(c) |  |  |
(d) |  |  |
(e) |  |  |
(f) |  |  |
(g) |  |  |
(h) |  |  |
(i) |  |  |
(j) |  |  |
(k) |  |  |
Figure 4: Master face images with the highest MSC score, generated by (a) Random Search. (b) DE. (c) LSHADE-RSP. (d) IMODE. (e) CMA-ESA. (f) NGOpt. (g) lq-CMA-ES. (h) ACM-ES. (i) LM-MA-ES. (j) LM-MA-ES + LQ-Filter. (k) LM-MA-ES + Success Predictor. TABLE II: Percentage of dataset covered by nine generated images FD | Dlib | FaceNet | SphereFace
---|---|---|---
Coverage Search LM-MA-ES on clustered data | $51.43\%$ | $40.17\%$ | $39.78\%$
$greedy$-Coverage Search LM-MA-ES | $63.22\%$ | $42.08\%$ | $43.14\%$
$greedy$-Coverage Search LM-MA-ES+Success Predictor | $\mathbf{63.92}\%$ | $\mathbf{43.82}\%$ | $\mathbf{44.15}\%$
(a) |  |  |  |  |  |  |  |  |
---|---|---|---|---|---|---|---|---|---
| $9.39\%$ | $7.00\%$ | $5.53\%$ | $4.94\%$ | $4.71\%$ | $3.62\%$ | $2.04\%$ | $1.70\%$ | $0.85\%$
(b) |  |  |  |  |  |  |  |  |
| $11.39\%$ | $6.45\%$ | $4.84\%$ | $4.82\%$ | $3.81\%$ | $3.32\%$ | $2.89\%$ | $1.67\%$ | $0.97\%$
(c) |  |  |  |  |  |  |  |  |
| $9.22\%$ | $6.98\%$ | $6.94\%$ | $6.60\%$ | $6.57\%$ | $6.14\%$ | $3.88\%$ | $3.25\%$ | $1.84\%$
(d) |  |  |  |  |  |  |  |  |
| $16.81\%$ | $5.50\%$ | $4.83\%$ | $3.42\%$ | $3.40\%$ | $3.09\%$ | $3.00\%$ | $1.60\%$ | $1.49\%$
(e) |  |  |  |  |  |  |  |  |
| $16.28\%$ | $5.70\%$ | $4.40\%$ | $3.56\%$ | $3.30\%$ | $2.90\%$ | $2.61\%$ | $1.91\%$ | $1.39\%$
(f) |  |  |  |  |  |  |  |  |
| $17.30\%$ | $9.84\%$ | $7.70\%$ | $6.39\%$ | $6.11\%$ | $5.29\%$ | $4.85\%$ | $3.45\%$ | $2.29\%$
(g) |  |  |  |  |  |  |  |  |
| $17.17\%$ | $4.75\%$ | $4.63\%$ | $4.45\%$ | $3.65\%$ | $3.23\%$ | $2.20\%$ | $2.10\%$ | $1.97\%$
(h) |  |  |  |  |  |  |  |  |
| $15.85\%$ | $5.05\%$ | $4.85\%$ | $4.00\%$ | $3.84\%$ | $3.67\%$ | $3.35\%$ | $1.61\%$ | $1.58\%$
(i) |  |  |  |  |  |  |  |  |
| $23.92\%$ | $7.60\%$ | $6.60\%$ | $6.00\%$ | $5.53\%$ | $5.34\%$ | $5.06\%$ | $2.80\%$ | $1.59\%$
Figure 5: Set of nine master face images generated with each of the Coverage
Search methods: LM-MA-ES Coverage Search on clustered data (a-c), greedy-
Coverage Search methods (d-f) LM-MA-ES, (g-i) LM-MA-ES+Success Predictor.
Embedded using either (a,d,g) SphereFace, (b,e,h) FaceNet ,or the (c,f,i) Dlib
face descriptors. Below each image, the MSC score for that image is listed.

###  IV-C Dataset Coverage

We run Alg. 1 in order to find a minimal number of images that match the
largest number of faces in the entire dataset $D$, where $|D|=5,749$.

As a baseline, we clustered the embedding faces to nine clusters. Based on
these clusters, we split the dataset into nine disjoint datasets. We run the
single image generation method (Fig 1) on each of the datasets. Our $greedy$
method (Alg. 1) is also run for nine iterations in order to generate a number
of faces that is equal to the number of clusters. We run it twice, once with
the LM-MA-ES optimization method and once with our LM-MA-ES+Success Predictor.

Table II lists the results. Evidently, the greedy method outperforms the per-
cluster solution. The greedy method is able to create nine master face images
that cover 42%-64% of the dataset and by applying the Success Predictor the
results slightly improve for all three face descriptors. The coverage results
for FaceNet and SphereFace models are lower than for the Dlib. The higher
embedding dimension of these two face descriptors allows better separability
between the faces, which in turn makes the coverage task more difficult. In
Fig. 5 nine master face images are presented for each of the face descriptors,
dataset $greedy$-Coverage Search algorithms as well as the MSC score of each
of the master faces.

##  V CONCLUSIONS AND FUTURE WORKS

Our results imply that face-based authentication is extremely vulnerable, even
if there is no information on the target identity. This is true for all three
face recognition methods, with some differences in the obtained success
probability.

Interestingly, the obtained faces are not blurry and their pose is mostly
frontal. There is a tendency to observe older faces in the generated images.
Since the face recognition methods are trained on faces from different ages,
the representation has some age invariance. It is possible that the methods
make use of this fact. However, we do not observe such a tendency toward
facial hair or glasses.

We further note that according to [6], the group of 60+ years-old white males
is the third most common group in the LFW dataset, while younger groups of
white males (40-60, 20-40) are even more common. Nevertheless, the group of
60+ years-old white males is usually less varied in comparison to the younger
groups, so a single older master face can cover a larger portion of its group.
As the iterations of the coverage algorithm proceed, the model covers less
represented groups in the dataset since each iteration is performed on the
reduced dataset. Eventually master faces of several ethnicities and several
ages are generated. The lower number of female faces out of the nine master
faces generated by our method, matches the much lower frequency of female
faces (22%) in the LFW dataset according to [6].

In order to provide a more secure solution for face recognition systems, anti-
spoofing [25] methods are usually applied. Our method might be combined with
additional existing methods to bypass such defenses. For example, DeepFake
methods [20] can be used to animate the generated master faces and overcome
liveness detection methods. We leave this research extension as future work.

It is also interesting to explore the possibility of using master faces faces
in order to help protect the face recognition systems against dictionary
attacks, as well as a way to reduce the overall false positive rate.
Anecdotally, although unreported in publications as far as we can ascertain,
the same set of faces appear multiple times in the false matches.

##  VI ACKNOWLEDGMENTS

This project has received funding from the European Research Council (ERC)
under the European Unions Horizon 2020 research and innovation programme
(grant ERC CoG 725974). This research was partially supported by The Yandex
Initiative for Machine Learning.

## References

  * [1] P. Bontrager, A. Roy, J. Togelius, N. Memon, and A. Ross.  Deepmasterprints: Generating masterprints for dictionary attacks via latent variable evolution, 2018.
  * [2] S. Chopra, R. Hadsell, and Y. LeCun.  Learning a similarity metric discriminatively, with application to face verification.  In CVPR, 2005.
  * [3] D.-A. Clevert, T. Unterthiner, and S. Hochreiter.  Fast and accurate deep network learning by exponential linear units (elus).  arXiv preprint arXiv:1511.07289, 2015.
  * [4] A. Fabisch, M. Langosz, and F. Kirchner.  Bolero: Behavior optimization and learning for robots.  International Journal of Advanced Robotic Systems, 17(3), 2020.
  * [5] I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio.  Generative adversarial nets.  In NIPS, 2014.
  * [6] H. Han and A. K. Jain.  Age, gender and race estimation from unconstrained face images.  Dept. Comput. Sci. Eng., Michigan State Univ., East Lansing, MI, USA, MSU Tech. Rep.(MSU-CSE-14-5), 87:27, 2014.
  * [7] N. Hansen.  A global surrogate assisted cma-es.  In Genetic and Evolutionary Computation Conference, 2019.
  * [8] N. Hansen, Y. Akimoto, and P. Baudis.  CMA-ES/pycma on Github.  Zenodo, DOI:10.5281/zenodo.2559634, Feb. 2019.
  * [9] N. Hansen, S. D. M”uller, and P. Koumoutsakos.  Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation.  Evolutionary computation, 11(1):1–18, 2003.
  * [10] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition, 2015.
  * [11] G. B. Huang, M. Ramesh, T. Berg, and E. Learned-Miller.  Labeled faces in the wild: A database for studying face recognition in unconstrained environments.  Technical report, UMass, Amherst, 2007.
  * [12] X. Huang and S. J. Belongie.  Arbitrary style transfer in real-time with adaptive instance normalization.  CoRR, abs/1703.06868, 2017.
  * [13] S. Ioffe and C. Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In International conference on machine learning, pages 448–456. PMLR, 2015.
  * [14] Z. Kaipeng, Z. Zhanpeng, L. Zhifeng, and Q. Yu.  Joint face detection and alignment using multitask cascaded convolutional networks.  IEEE Signal Processing Letters, 23(10):1499–1503, Oct 2016.
  * [15] T. Karras, S. Laine, and T. Aila.  A style-based generator architecture for generative adversarial networks, 2019.
  * [16] T. Karras, S. Laine, M. Aittala, J. Hellsten, J. Lehtinen, and T. Aila.  Analyzing and improving the image quality of StyleGAN.  In Proc. CVPR, 2020.
  * [17] V. Kazemi and J. Sullivan.  One millisecond face alignment with an ensemble of regression trees.  In CVPR, 2014.
  * [18] D. E. King.  Dlib-ml: A machine learning toolkit.  Journal of Machine Learning Research, 10:1755–1758, 2009.
  * [19] D. P. Kingma and J. Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [20] P. Korshunov and S. Marcel.  Deepfakes: a new threat to face recognition? assessment and detection.  CoRR, abs/1812.08685, 2018.
  * [21] J. Liu, A. Moreau, M. Preuss, J. Rapin, B. Roziere, F. Teytaud, and O. Teytaud.  Versatile black-box optimization.  In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pages 620–628, 2020.
  * [22] I. Loshchilov, T. Glasmachers, and H. Beyer.  Limited-memory matrix adaptation for large scale black-box optimization.  IEEE Transactions on Evolutionary Computation, PP, 05 2017.
  * [23] I. Loshchilov, M. Schoenauer, and M. Sebag.  Comparison-based optimizers need comparison-based surrogates.  In International Conference on Parallel Problem Solving from Nature, pages 364–373. Springer, 2010.
  * [24] J. MacQueen et al.  Some methods for classification and analysis of multivariate observations.  In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, volume 1, pages 281–297. Oakland, CA, USA, 1967\.
  * [25] Z. Ming, M. Visani, M. M. Luqman, and J. Burie.  A survey on anti-spoofing methods for face recognition with RGB cameras of generic consumer devices.  CoRR, abs/2010.04145, 2020.
  * [26] H. Ng and S. Winkler.  A data-driven approach to cleaning large face datasets.  In ICIP, 2014.
  * [27] H. H. Nguyen, J. Yamagishi, I. Echizen, and S. Marcel.  Generating master faces for use in performing wolf attacks on face recognition systems.  In 2020 IEEE International Joint Conference on Biometrics (IJCB), pages 1–10. IEEE, 2020.
  * [28] M. N. Omidvar and X. Li.  A comparative study of cma-es on large scale global optimisation.  In Australasian Joint Conference on Artificial Intelligence, pages 303–312. Springer, 2010.
  * [29] O. M. Parkhi, A. Vedaldi, and A. Zisserman.  Deep face recognition.  In British Machine Vision Conference, 2015.
  * [30] Z. Pitra, L. Bajer, J. Repickỳ, and M. Holeňa.  Overview of surrogate-model versions of covariance matrix adaptation evolution strategy.  In Proc. of the Genetic and Evolutionary Computation Conf., 2017\.
  * [31] A. Radford, L. Metz, and S. Chintala.  Unsupervised representation learning with deep convolutional generative adversarial networks.  arXiv preprint arXiv:1511.06434, 2015.
  * [32] J. Rapin and O. Teytaud.  Nevergrad - A gradient-free optimization platform.  https://GitHub.com/FacebookResearch/Nevergrad, 2018.
  * [33] A. Roy, N. Memon, and A. Ross.  Masterprint: Exploring the vulnerability of partial fingerprint-based authentication systems.  IEEE Trans. on Information Forensics and Security, 2017.
  * [34] K. M. Sallam, S. M. Elsayed, R. K. Chakrabortty, and M. J. Ryan.  Improved multi-operator differential evolution algorithm for solving unconstrained problems.  In 2020 IEEE Congress on Evolutionary Computation (CEC), pages 1–8. IEEE, 2020.
  * [35] F. Schroff, D. Kalenichenko, and J. Philbin.  Facenet: A unified embedding for face recognition and clustering.  2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Jun 2015.
  * [36] V. Stanovov, S. Akhmedova, and E. Semenkin.  LSHADE algorithm with rank-based selective pressure strategy for solving CEC 2017 benchmark problems.  In IEEE congress on evolutionary computation (CEC), 2018.
  * [37] R. Storn and K. Price.  Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces.  Journal of global optimization, 11(4):341–359, 1997.
  * [38] C. Szegedy, S. Ioffe, V. Vanhoucke, and A. Alemi.  Inception-v4, inception-resnet and the impact of residual connections on learning.  In AAAI, 2017.
  * [39] Y. Taigman, Y. Ming, M. Ranzato, and L. Wolf.  Deepface: Closing the gap to human-level performance in face verification.  In CVPR, 2014.
  * [40] K. Varelas, A. Auger, D. Brockhoff, N. Hansen, O. A. ElHara, Y. Semet, R. Kassab, and F. Barbaresco.  A comparative study of large-scale variants of cma-es.  In International Conference on Parallel Problem Solving from Nature, pages 3–15. Springer, 2018.
  * [41] J. Wang, F. Zhou, S. Wen, X. Liu, and Y. Lin.  Deep metric learning with angular loss.  In ICCV, 2017.
  * [42] L. Weiyang, W. Yandong, Y. Zhiding, L. Ming, R. Bhiksha, and S. Le.  Sphereface: Deep hypersphere embedding for face recognition, 2018.
  * [43] D. Yi, Z. Lei, S. Liao, and S. Z. Li.  Learning face representation from scratch.  arXiv preprint arXiv:1411.7923, 2014.


# End-to-end Deformable Attention Graph Neural Network for Single-view Liver
Mesh Reconstruction

###### Abstract

Intensity modulated radiotherapy (IMRT) is one of the most common modalities
for treating cancer patients. One of the biggest challenges is precise
treatment delivery that accounts for varying motion patterns originating from
free-breathing. Currently, image-guided solutions for IMRT is limited to 2D
guidance due to the complexity of 3D tracking solutions. We propose a novel
end-to-end attention graph neural network model that generates in real-time a
triangular shape of the liver based on a reference segmentation obtained at
the preoperative phase and a 2D MRI coronal slice taken during the treatment.
Graph neural networks work directly with graph data and can capture hidden
patterns in non-Euclidean domains. Furthermore, contrary to existing methods,
it produces the shape entirely in a mesh structure and correctly infers mesh
shape and position based on a surrogate image. We define two on-the-fly
approaches to make the correspondence of liver mesh vertices with 2D images
obtained during treatment. Furthermore, we introduce a novel task-specific
identity loss to constrain the deformation of the liver in the graph neural
network to limit phenomenons such as flying vertices or mesh holes. The
proposed method achieves results with an average error of $3.06\pm 0.7$ mm and
Chamfer distance with L2 norm of $63.14\pm 27.28$.

Index Terms—  Motion modeling, 3D mesh inference, Attention Graph Neural
Network, Liver cancer radiotherapy

##  1 Introduction

One of the most commonly used radiotherapy treatment is intensity modulated
radiotherapy (IMRT), which consists in the delivery of tightly targeted
radiation beams from outside the body. However, it faces complex challenges
when experiencing important motion displacements, hence posing a great risk of
dose administration to healthy tissue, such as in the liver [1]. Consequently,
respiratory motion compensation is an important part of radiotherapy and other
non-invasive interventions [2]. To avoid unnecessary damage due to organ
displacement caused by respiratory motion, the treated organ must be located
and imaged at all times. Unfortunately, image acquisition during treatment
with IMRT is limited to 2D cine slices due to time complexity, therefore
resulting in a lack of information in out-of-plane data for tumor targeting.
Real-time 3D motion tracking of organs would provide necessary tools to
accurately follow tumor targets.

Several methods, based on convolutional neural networks (CNNs) have been
proposed to tackle the problem of modeling 3D data based on 2D signals.
Mezheritsky et al. [3] proposed a method that warps the reference volume with
the output of a convolutional autoencoder, thus recovering 3D deformation
fields with only a pre-treatment volume and a single live 2D image. Cerrolaza
et al. [4] proposed a 3D ultrasound fetal skull reconstruction method based on
standard 2D ultrasound views of the head using a reconstructive conditional
variational autoencoder. Girdhar et al. [5] investigated tackling a number of
tasks including voxel prediction from 2D images and 3D model retrieval.
However, methods based on CNNs achieved partial success, since they rely on
fixed-size inputs. The volumes might have different sizes across scans, body
types, and/or machines. The requirement of having volumes reshaped might
result in information loss.

Recent advances in graph neural networks sparked new advances in many domains,
including in medical imaging [6]. Lu et al. [7] leveraged dynamic spatio-
temporal graph neural network for cardiac motion analysis. Graph neural
networks operate on graph objects, which contrasts to representations obtained
by CNN that might lose important surface details. The mesh has more desirable
properties for many applications, because they are lightweight, have more
shape modeling details, and are better suited for simulating deformations [6].

Fig. 1: High-level representation of the DAGNN-SVLR model. The Attention Graph
Neural Network deforms the reference mesh from the preoperative phase based on
features extracted from supplied 2D surrogate images. We proposed two
approaches to feature extraction: without feature pooling and with feature
pooling.

In this work, we propose a Deformable Attention Graph Neural Network - Single
View Liver Reconstruction (DAGNN-SVLR) method, which is an end-to-end
trainable model that infers a 3D liver mesh structure at any time during
treatment, using a reference triangulated mesh obtained from the segmentation
of baseline 3D MRI volume and a single 2D MRI slice captured in real-time.
Moreover, we present a new identity loss tailored for this specific task and
empirically show that the combination with the Chamfer distance favors good
mesh properties and improves the performance of the predictive model. A high-
level representation of the proposed approach is shown in Fig. 1.

##  2 DAGNN-SVLR

The DAGNN-SVLR model leverages a triangulated liver mesh segmented from the
pre-operative T2-w MRI volume and a 2D cine-MR slice taken in real-time during
treatment. The model learns a function $f(.)$ that predicts the deformation of
a reference mesh $M_{r}$ based on the surrogate 2D MRI slice at time $t$,
defined as $I_{t}$, calculating the mesh at time $t$ as
$M_{t}=f(M_{r},I_{t})$.

A major component of the DAGNN-SVLR model is to determine correspondences
between the reference mesh and a surrogate image. Since GNNs work directly on
graphs and we cannot simply merge the image with the graph, we explored two
solutions as illustrated in Fig. 1.

  1. (a)

As a first option - without the feature pooling, we utilize a residual
convolutional network as a feature extractor. The output is a latent
representation of the image represented by a one-dimensional vector of size
$dim=128$. ResNet18 [8] network was selected as a compromise between accuracy
and speed.

  2. (b)

As a second option, we propose a feature pooling approach. We use a ResNet18
network, with added padding, so each consequent layer of the network does not
downsample the shape. Consequently, the feature maps produced by this ResNet
have an identical shape to the input image. In parallel to the feature
extraction, the index coordinates of the reference mesh are calculated, so
that each vertex of the mesh can be associated with its particular position in
the image. Afterward, direct $3\times 3$ neighborhoods are extracted from each
feature map, thereby yielding nine features per feature map for each node in
the reference mesh.

Once the feature extraction module is processed, the concatenated features of
the reference mesh, with the extracted features from the image, are passed
through an attention graph neural network to produce the predicted mesh
surface.

###  2.1 Graph Convolutional Neural Network

A Graph Convolutional Neural Network (GCNN) is a multilayer neural network
that operates directly on graphs. It induces vertex embeddings based on the
properties of their local neighborhood and the vertices.

Let $G=(V,E)$ be a triangulated surface of the liver volume, where
$V=\\{1,2,\dots,N\\}$ and $E\subseteq|V|\times|V|$ represent the set of
vertices and edges, respectively. Let $X\in\mathbb{R}^{Nxm}$ be a matrix
containing the $m$ features of all $N$ vertices. We denote
$\mathcal{N}_{i}=\\{j:(i,j)\in E\\}\cup\\{i\\}$ as the neighbor set of vertex
$i$. Then, $H=\\{\mathbf{h}_{1},\mathbf{h}_{2},...,\mathbf{h}_{N}\\}$ is a set
of input vertex features, where feature vector $\mathbf{h}_{i}$ is associated
with a vertex $i\in V$.

Kipf et al. [9] proposed a Spatial Graph Convolution layer GCN, where the
features from neighboring vertices are aggregated with fixed weights, where
one vertex embedding is calculated as:

$h_{u}=\Phi(\mathbf{x}_{u},\bigoplus_{v\in\mathcal{N}_{u}}c_{uv}\psi(\mathbf{x}_{v}))$
(1)

where $\Phi$ and $\psi$ are learnable functions, $\mathbf{x}_{u}$ and
$\mathbf{x}_{v}$ are vertex representations of vertex $u$ and vertex $v$,
$c_{uv}$ specifies the importance of vertex $v$ to vertex $u$’s
representation, $\mathcal{N}_{u}$ is a local neighborhood and $\bigoplus$ is
an aggregation function, such as a summation or mean.

Graph Attention Layers (GAT) [10] extend this work by incorporating a self-
attention mechanism that computes the importance coefficients $a_{uv}$:

$h_{u}=\Phi(\mathbf{x}_{u},\bigoplus_{v\in\mathcal{N}_{u}}a(\mathbf{x}_{u},\mathbf{x_{v}}\psi(\mathbf{x}_{v}))).$
(2)

The attention mechanism $a$ is a single-layer feed-forward neural network
parameterized by a weight vector $\mathbf{a}\in\mathbb{R}^{2F^{\prime}}$,
where:

$a_{ij}=\exp(LeakyRELU(\mathbf{a}^{T})).$ (3)

We employ a neural network consisting of seven alternating GAT and
normalization layers. Each GAT layer receives as input $128$ features and two
heads, which output is summed afterward. According to the proposal in [11] we
aggregate the features based on a combination of two aggregation functions:
summation and mean.

###  2.2 Loss functions

We define three different loss functions to constrain the properties of output
liver meshes. Amongst the most critical properties of final meshes are
smoothness, closeness, and the absence of so-called flying vertices.

#### Chamfer distance

The Chamfer distance measures the distance of each vertex to the other set and
it serves as a constraint for the location of mesh vertices. The function is
continuous, piecewise smooth and is defined as:

$\mathcal{L}_{CD}(P,Q)=\sum_{p}\min_{q}||p-q||_{2}^{2}+\sum_{q}\min_{p}||p-q||_{2}^{2}.$
(4)

where $P$ and $Q$ are predicted and ground truth liver meshes and $p$ and $q$
are single points. Contrary to its name, based on the mathematical
formulation, it is not a distance function since it does not hold the property
of triangle inequality.

#### Sampled Chamfer Distance

The Chamfer distance, despite its wide usage in the mesh processing domain, is
unable to capture any fine information included in the mesh structure. It
penalizes the point difference directly resulting in the loss of surface mesh
information.

To mitigate this drawback, Smith et al. [12] introduced a training objective
that operates on a local surface defined by vertices sampled by a
differentiable sampling procedure.

Given a facet defined by 3 vertices
$\\{v_{1},v_{2},v_{3}\\}\in\mathbb{R}^{3}$, uniform sampling is achieved by:

$s=(1-\sqrt{r_{1}})v_{1}+(1-r_{2})\sqrt{r_{1}}v_{2}+\sqrt{r_{1}}r_{2}v_{3}$
(5)

where s is a point inside the surface defined by the facet, $r_{1},r_{2}\sim
U[0,1]$

The loss function is defined as:

$\mathcal{L}_{SCD}(P,Q)=\sum_{p\in S}\min_{\hat{f}\in
P}dist(p,\hat{f})+\sum_{q\in\hat{S}}\min_{f\in Q}dist(q,f)$ (6)

where $P$ is the first mesh, $Q$ is the ground truth mesh, $\hat{S}$ and $S$
are the sampled points of the predicted mesh and ground truth mesh $f$ and
$\hat{f}$ are faces and $dist$ is a function computing the distance between a
point and a triangular facet.

#### Identity loss

The identity loss penalizes substantial changes in the vertex positions if the
surrogate image represents the actual state of the mesh. Given a mesh $M_{t}$,
the surrogate signal at time $t$ $I_{t}$, and model that infers current mesh
$\hat{M}_{t}$ based on surrogate image and a reference mesh $M_{r}$,
$\hat{M}_{t}=f(M_{r},I_{t})$ we define identity loss as:

$\mathcal{L}_{I}=\mathcal{L}_{CD}(M,\hat{M})$ (7)

where $L_{CD}$ is a Chamfer loss or a sampled Chamfer loss.

Finally, DAGNN calculates the final loss as
$\mathcal{L}=\mathcal{L_{SCD}}+\alpha\mathcal{L}_{I}$ where $\alpha$ is a
hyperparameter.

##  3 Results

We evaluated the proposed approach using a 4D-MRI liver dataset acquired from
$25$ volunteers [13]. The volume dimensions were $176\times 176\times 32$ with
a pixel spacing of $1.7\times 1.7\textrm{mm}^{2}$ and a slice thickness of
$3.5$ mm. Reference meshes were created as a closed surface of the liver
segmentation from each of the subject’s inhale phases. Ground truth meshes of
other temporal sequences were then acquired by using deformation field
calculated by Elastix deformable registration [14]. Volumes were resized for
the registration to $64\times 64\times 32$ due to computational complexity.
The number of vertices in meshes were from interval $(1300,2000)$. When
sampling loss was used, an empirically determined value of $1000$ was chosen.

As for preprocessing steps, we centered and normalized the scale into the
interval $(-1,1)$. For validation purposes, we performed a 10-fold cross-
validation. The model was trained with a batch size of one with five steps
accumulation gradients and with Adam optimizer with a learning rate $1e^{-5}$.
We set the weight of identity function $L_{I}$ to $0.05$.

Ground Truth Predicted Mesh Signed Distance

Fig. 2: Visualization of a signed distance (in mm) from predicted to ground
mesh for two subjects.

Visualizations of sample predictions and their ground truth can be seen in
Fig. 2. It is clear that the inferred shapes are compliant with important mesh
properties such as complete and smooth surfaces. Additionally, in Fig. 3 we
show ground truth and predicted delineations obtained from inferred mesh in
the axial, sagittal, and coronal planes.

Fig. 3: Comparison of ground truth (green) and predicted (red) segmentations.
Each row depicts different volunteer acquisitions.

The average error and average Chamfer distance over the entire test sequence
is presented in Table 1. We used the Chamfer distance with L2 norm and errors
calculated by unsigned distance of two meshes to measure the performance. The
results of our model are divided into two main categories, with and without
feature pooling.

Method | Chamfer distance with L2 norm | Avg. error (mm)
---|---|---
Node2Vec [15] | $79.45\pm 48.67$ | $5.0\pm 3.7$
FP + $\mathcal{L}_{CD}$ | $62.85\pm 25.18$ | $3.44\pm 0.91$
FP + $\mathcal{L}_{SCD}$ | $82.25\pm 24.40$ | $3.23\pm 0.64$
FP + $\mathcal{L}_{SCD}$ \+ $\mathcal{L}_{I}$ | $63.14\pm 27.28$ | $\mathbf{3.05\pm 0.75}$
No FP + $\mathcal{L}_{CD}$ | $67.226\pm 5.57$ | $3.46\pm 0.70$
No FP + $\mathcal{L}_{SCD}$ | $66.117\pm 26.48$ | $3.26\pm 0.78$
No FP + $\mathcal{L}_{SCD}$ \+ $\mathcal{L}_{I}$ | $\mathbf{61.34\pm 25.63}$ | $3.06\pm 0.7$

Table 1: Prediction results for different loss functions, with and without
feature pooling (FP).

To compare our method with a state-of-the-art approach, we chose the Node2Vec
[15] method that supports working with graph data. Node2Vec was trained for
$100$ epochs and found embeddings were concatenated with extracted features,
similarly to our model.

Feature pooling, as used in this study, slightly outperforms the utilization
of a single feature vector with respect to average error in all cases. This
confirms our hypothesis, that leveraging sampling loss improves performance
for both feature extraction methods. The average error for feature pooling
subsided from $3.44\pm 0.91$mm to $3.23\pm 0.64$mm, and for the approach
without FP from $3.46\pm 0.70$mm to $3.26\pm 0.78$mm. Adding identity loss
during the training improves the results from $3.23\pm 0.91$mm and $3.26\pm
0.78$mm to $3.05\pm 0.75$mm and $3.06\pm 0.7$mm respectively, thus
representing a performance improvement of $5.6$% and $6.2$%.

Interestingly, the test results of Chamfer distance are higher when the
sampling loss was used without identity loss for feature pooling. We
hypothesize that the model was trained using a loss that sampled points on the
surface, but for the testing part conventional Chamfer loss was used. This
error in Chamfer distance diminishes when identity loss is added.

Next, we present the average error in millimeters for three subjects over time
in Fig. 4. The plot of the subject in first row has spikes that introduce
errors yielding more than $5$ mm. The other two subjects have very similar
errors over time oscillating over a value of $2.5$mm without any outliers. The
model repeatedly achieve error as low as $1.8$mm.

Fig. 4: Average error (in mm) over free-breathing sequences for three selected
subjects.

##  4 Conclusion

We presented a novel approach for single-view liver surface reconstruction
from a surrogate 2D signal based on the combination of an attention graph
neural network with a fully convolutional neural network. Our model was
successful in generating full meshes with proper topology, and position and
with an inference time of 0.002 seconds. We have shown that the model benefits
considerably from the proposed identity loss, with a feature pooling process.
Several potential extensions will be addressed in future work, such as liver
motion prediction in the graph domain or using a sequence of surrogate images
for liver reconstruction, instead of using a single view.

##  5 Compliance with Ethical Standards

This study was performed in line with the principles of the Declaration of
Helsinki. Approval was granted by the local Institutional Review Board.

##  6 Acknowledgments

This research has been funded in part by the Natural Sciences and Engineering
Research Council of Canada (NSERC). The authors have no relevant financial or
non-financial interests to disclose.

## References

  * [1] Susanne Stera, Georgia Miebach, Daniel Buergy, Constantin Dreher, Frank Lohr, Stefan Wurster, Claus Rödel, Szücs Marcella, David Krug, Michael Ehmann, et al.,  “Liver sbrt with active motion-compensation results in excellent local control for liver oligometastases: An outcome analysis of a pooled multi-platform patient cohort,”  Radiotherapy and Oncology, vol. 158, pp. 230–236, 2021.
  * [2] Yihuan Lu, Kathryn Fontaine, Tim Mulnix, John A Onofrey, Silin Ren, Vladimir Panin, Judson Jones, Michael E Casey, Robert Barnett, Peter Kench, et al.,  “Respiratory motion compensation for pet/ct with motion information derived from matched attenuation-corrected gated pet data,”  Journal of nuclear Medicine, vol. 59, no. 9, pp. 1480–1486, 2018\.
  * [3] Tal Mezheritsky, Liset Vázquez Romaguera, William Le, and Samuel Kadoury,  “Population-based 3d respiratory motion modelling from convolutional autoencoders for 2d ultrasound-guided radiotherapy,”  Medical Image Analysis, vol. 75, pp. 102260, 2022.
  * [4] Juan J Cerrolaza, Yuanwei Li, Carlo Biffi, Alberto Gomez, Matthew Sinclair, Jacqueline Matthew, Caronline Knight, Bernhard Kainz, and Daniel Rueckert,  “3d fetal skull reconstruction from 2dus via deep conditional generative networks,”  in International Conference on Medical Image Computing and Computer-Assisted Intervention. Springer, 2018, pp. 383–391.
  * [5] Rohit Girdhar, David F Fouhey, Mikel Rodriguez, and Abhinav Gupta,  “Learning a predictable and generative vector representation for objects,”  in European Conference on Computer Vision. Springer, 2016, pp. 484–499.
  * [6] David Ahmedt-Aristizabal, Mohammad Ali Armin, Simon Denman, Clinton Fookes, and Lars Petersson,  “Graph-based deep learning for medical diagnosis and analysis: past, present and future,”  Sensors, vol. 21, no. 14, pp. 4758, 2021.
  * [7] Ping Lu, Wenjia Bai, Daniel Rueckert, and J Alison Noble,  “Dynamic spatio-temporal graph convolutional networks for cardiac motion analysis,”  in 2021 IEEE 18th International Symposium on Biomedical Imaging (ISBI). IEEE, 2021, pp. 122–125.
  * [8] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun,  “Deep residual learning for image recognition,”  in Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778.
  * [9] Thomas N Kipf and Max Welling,  “Semi-supervised classification with graph convolutional networks,”  arXiv preprint arXiv:1609.02907, 2016.
  * [10] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio,  “Graph attention networks,”  arXiv preprint arXiv:1710.10903, 2017.
  * [11] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković,  “Principal neighbourhood aggregation for graph nets,”  Advances in Neural Information Processing Systems, vol. 33, pp. 13260–13271, 2020.
  * [12] Edward J Smith, Scott Fujimoto, Adriana Romero, and David Meger,  “Geometrics: Exploiting geometric structure for graph-encoded objects,”  arXiv preprint arXiv:1901.11461, 2019.
  * [13] Liset Vázquez Romaguera, Tal Mezheritsky, Rihab Mansour, Jean-François Carrier, and Samuel Kadoury,  “Probabilistic 4d predictive model from in-room surrogates using conditional generative networks for image-guided radiotherapy,”  Medical Image Analysis, vol. 74, pp. 102250, 2021.
  * [14] Mariëlle JA Jansen, Hugo J Kuijf, Maarten Niekel, Wouter B Veldhuis, Frank J Wessels, Max A Viergever, and Josien PW Pluim,  “Liver segmentation and metastases detection in mr images using convolutional neural networks,”  Journal of Medical Imaging, vol. 6, no. 4, pp. 044003, 2019.
  * [15] Aditya Grover and Jure Leskovec,  “node2vec: Scalable feature learning for networks,”  in Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, 2016, pp. 855–864.