11institutetext: Department of Computer Science, University of Rochester,
Rochester, USA 11email<EMAIL_ADDRESS>Digital
Technology and Innovation, Siemens Healthineers, Princeton, USA
33institutetext: Tencent X-Lab, Shenzhen, China 44institutetext: Institute of
Computing Technology, Chinese Academy of Sciences, Beijing, China

# Face Completion with Semantic Knowledge
and Collaborative Adversarial Learning

Haofu Liao* 11 Gareth Funka-Lea 22 Yefeng Zheng* 33 Jiebo Luo 11
S. Kevin Zhou* 44

###### Abstract

††*The work was done when the authors were with Siemens Healthineers.

Unlike a conventional background inpainting approach that infers a missing
area from image patches similar to the background, face completion requires
semantic knowledge about the target object for realistic outputs. Current
image inpainting approaches utilize generative adversarial networks (GANs) to
achieve such semantic understanding. However, in adversarial learning, the
semantic knowledge is learned implicitly and hence good semantic understanding
is not always guaranteed. In this work, we propose a collaborative adversarial
learning approach to face completion to explicitly induce the training
process. Our method is formulated under a novel generative framework called
collaborative GAN (collaGAN), which allows better semantic understanding of a
target object through collaborative learning of multiple tasks including face
completion, landmark detection and semantic segmentation. Together with the
collaGAN, we also introduce an inpainting concentrated scheme such that the
model emphasizes more on inpainting instead of autoencoding. Extensive
experiments show that the proposed designs are indeed effective and
collaborative adversarial learning provides better feature representations of
the faces. In comparison with other generative image inpainting models and
single task learning methods, our solution produces superior performances on
all tasks.

###### Keywords:

Face completion Image inpainting Generative Adversarial Networks Multitask
Learning.

##  1 Introduction

Image inpainting is the process of reconstructing a missing region in an image
such that the inpainted area is visually consistent with its neighboring
pixels and the inpainted image overall looks realistic. Traditional approaches
to this problem either require that the filling information is available in
the image [6, 9, 1] or rely on the availability of a large photo database to
retrieve the missing region [37, 5]. These approaches work well for the
background inpainting problem, i.e., filling the missing part with image
patches similar to its background, as inpainting can be performed through
pattern matching. However, when it comes to complete a missing part of an
object where no existing patches can be matched or retrieved, the traditional
approaches may fail. For example, if a mouth is missing, it is not possible to
synthesize the mouth using image patches from other face parts. Instead, image
inpainting in this case requires semantic knowledge about faces, e.g.,
location, shape, color and texture of face parts.

(a)

(b)

(c)

(d)

Figure 1: Inpainting results using our method. (a) original image. (b) masked
image. (c) inpainted image with collaborative learning. (d) inpainted image
without collaborative learning (top) and segmentation mask from our method
superimposed on the inpainted image (bottom).

To address this object completion problem in image inpainting, recent models
[30, 39, 21] propose to use generative adversarial networks (GANs) for more
semantically consistent results. However, for generative models, the semantic
understanding is implicitly learned through adversarial training. There are no
direct constraints on the structure of the target object and hence the
inherent semantic understanding is not always guaranteed. Fortunately, in
recent years, the success of deep learning has made the semantic labels of
objects accessible. In this work, we investigate the possibility of
introducing the semantic knowledge of face labels to the adversarial training
of face completion for better induction of semantic understanding.

We focus on helping the inpainting model better understand the underlying
structure of faces through the collaborative learning of other face related
tasks. We argue that current approaches using generative inpainting models
alone may not be able to produce structurally realistic results in some cases.
For example, when an eye is missing from the image, the inpainting model
should be able to predict the missing eye’s location and shape based on the
facial symmetry. However, as shown in the first row of Figure 1, the
generative image inpainting model trained without using our proposed
collaborative method produces a structurally unrealistic face (Figure 1(d)
top) with the inpainted eye smaller and darker than the eye outside the
corrupted region. In contrast, a collaboratively trained model can keep the
structural consistency between the inpainted region and the nearby context
(Figure 1(c) top). In addition, we also find that models trained in this
manner tend to produce visually consistent results among tasks. As
demonstrated in Figure 1(d) bottom, the segmentation result is closely aligned
with the inpainting result other than the ground truth. This provides a clear
evidence that they are inherently helping each other during training and the
knowledge is shared instead of individually learned.

To this end, we propose an innovative image-to-image generative network for
face completion. The proposed method formulates a collaborative GAN to
facilitate the direct learning of multiple tasks. For the generator, the
network outputs multiple channels for each task and has them share most of the
network parameters for better collaborative learning. We also stand apart from
the existing inpainting models by introducing skip connections between the
encoder and decoder [34, 12]. For the discriminators, we apply conditional GAN
(cGAN) [29] for better transformation quality and have dedicated
discriminators for each task. For the loss function, we introduce an
inpainting concentrated scheme to allow the model focusing on the inpainting
itself instead of autoencoding the context. Our experimental results
demonstrate the effectiveness of the proposed design and better feature
representations can be obtained with the proposed collaborative GAN. Comparing
with other generative models without using collaborative adversarial learning,
our approach consistently produces remarkably more realistic inpainting
results. Comparing with single task adversarial learning, our joint approach
produces better performances on all tasks.

##  2 Related Work

Generative Image to Image Transformation Image inpainting can be seen as a
special case of the image-to-image transformation problem in that image
inpainting tries to transform a cropped image to a reconstructed one. One of
the typical image-to-image transformation problems is autoencoding [8]. In
relation to inpainting, a seminal work in this area is the denoising
autoencoder [36]. It introduces an inpainting-like scheme to autoencoding,
hoping the autoencoder can learn a better feature representation by recovering
the damage to the input image. Another related work is [16]. It incorporates
GANs into a variational autoencoder (VAE) [14] and argues that the network
trained using the adversarial loss and VAE loss can give a more representative
feature vector of the input image.

For other image-to-image transformation problems, [18] proposes to use GANs
for image super-resolution. It has the standard generative image-to-image
model setting: a generator that maps the low resolution input to high
resolution and a discriminator that tells if the input image is a high
resolution one or not. It also includes perceptual loss [18] to further
regularize the realism. [12] proposes a general framework for image-to-image
translation. It improves the generative image-to-image networks by introducing
image-conditional GANs and PatchGAN. Inspired by [12], [20] proposes a
generative image-to-image framework for caricature image generation from face
image. [22] applies generative image-to-image network for medical image
artifact reduction.

Semantic Inpainting The term semantic inpainting is first introduced by
context encoder (CE) [30] to address the challenging inpainting case where a
large region of the image is missing and the inpainting generally requires
semantic understanding of the context. The paper proposes to learn a better
autoencoder by having it recover the missing part of an input image. To our
best knowledge, it is the first work that introduces adversarial loss into the
inpainting problem. Another approach to semantic inpainting is [39]. The
method is based on a pretrained GAN model that maps a noise vector to the
generator manifold. The algorithm finds the noise vector such that the
generated image through the pretrained GAN model minimizes both a contextual
loss and a perceptual loss. This work is an indirect approach to image
inpainting. Due to the limitation of the pretrained GAN model, it may fail to
produce good results when the image resolution is high or the scene is
complex. [38] proposes a multi-scale neural patch synthesis network for high-
resolution image inpainting. Since our work focus on the benefit of
collaborative adversarial training, high-resolution image inpainting is not
within the cope of this study. In fact, our work can be easily extended to
high-resolution settings for better performance.

The closest work to ours is [21]. It advances the state of the art [30] by
introducing a parsing network to further regularize the inpainting through
semantic parsing/segmentation and a local discriminator to ensure the
generated contents are semantically coherent. However, the parsing network is
pretrained and independent of the generator. Thus, the semantic parsing
information is not shared with the generator during training. The semantic
parsing loss is also not applied directly to the generator. As a result, the
accuracy of computing such a loss is limited by the parsing network which
further limits the final performance of the generator. Meanwhile, for the
local discriminator, it requires the mask to be rectangular and hence cannot
be generalized to other inpainting cases such as noise inpainting. [10] also
proposes a similar global and local discriminator design and it suffers from
the same disadvantage as [21]. Semantic inpainting has also been applied to
address medical problems. [24] introduces a 3D inpainting task to improve the
performance of ultrasound image segmentation. [23, 25] convert the metal
artifact reduction problem to the X-ray image inpainting problem and the metal
artifacts are removed by reconstructing from the inpainted X-ray images.

Multi-Task Learning Multi-task learning (MTL) [2] refers to the process of
learning multiple tasks jointly in order to improve the generalization
performance of the model. It has been widely used in deep neural networks
(DNNs) for various tasks, such as object detection [4], action recognition
[35], landmark detection [40], etc. In terms of generative models, many works
have introduced adversarial learning in a multi-task fashion to improve the
learning of the main tasks. [3] uses adversarial learning for better domain
adaption of the main task. [19] proposes a perceptual GAN that learns super-
resolution together with object detection for better performance of small
object detection. [26] leverages GANs to generate shared features that are
independent of different text classification tasks. In this work, we
contribute to the literature with a novel image-to-image generative framework
that collaboratively learns multiple tasks for better semantic understanding
and, ultimately, yields better image inpainting.

Figure 2: The architecture of the proposed method. The network is trained
collaboratively with three tasks: inpainting $i$, segmentation $s$ and
(landmark) detection $d$. The generator $G$ takes a masked image $x$ as input
and outputs the inpainted image $G^{i}(x,z)$, segmentation mask $G^{s}(x,z)$
and detection heatmap $G^{d}(x,z)$ simultaneously. The discriminators $D_{i}$,
$D_{s}$ and $D_{d}$ are used for adversarial learning. In addition,
reconstruction losses $\mathcal{L}_{rec}^{i}$, $\mathcal{L}_{rec}^{s}$ and
$\mathcal{L}_{rec}^{d}$ are also applied to the three tasks, respectively.

##  3 Collaborative Face Completion

The proposed collaborative face completion method is formulated under a novel
GAN framework which we call collaborative GAN (collaGAN). The proposed
framework aims to inductively improve the main generation task (face
completion in our case) by incorporating the additional knowledge embedded in
other tasks. In this section, we give the formal definition of collaGAN and
its connection to face completion.

###  3.1 Collaborative GAN

Let $\Omega$ be a finite set of tasks and $y_{t}$ be a data sample of task
$t\in\Omega$. A collaGAN learns a mapping from an input image $x$ and a random
noise $z$ to a set of outputs $\\{y_{t}|t\in\Omega\\}$, i.e.,
$G:\\{x,z\\}\rightarrow\\{y_{t}|t\in\Omega\\}$. The network is trained in an
adversarial fashion. The generator $G$ tries to generate data samples as
“real” as possible such that, $\forall t\in\Omega$, the adversarially trained
discrimintor $D_{t}$ cannot tell if a sample is generated by $G$ or from the
data domain of task $t$.

Similar to the classic GAN, the objective function of a collaGAN can be given
as follows:

$\begin{split}&\mathcal{L}^{\Omega}_{adv}=\min_{G}\max_{D_{\Omega}}\sum_{t\in\Omega}\mathbb{E}_{x,y_{t}\sim
p_{data}(x,y_{t})}[\log D_{t}(x,y_{t})]\\\
&+\lambda_{adv}^{t}\mathbb{E}_{x\sim p_{data}(x),z\sim p_{z}(z)}[1-\log
D_{t}(x,G^{t}(x,z))],\end{split}$ (1)

Here, $D_{\Omega}=\\{D_{t}|t\in\Omega\\}$. $p_{data}$ and $p_{z}$ denote the
data and noise distribution, respectively. $G(x,z)$ is the channel-wisely
stacked generator outputs of the tasks with $G^{t}(x,z)$ denoting the ouput
generated for task $t$. $\lambda_{adv}^{t}$ balances the importance of the
generator loss for task $t$. $D_{\Omega}$ and $G$ play a minmax game where
$D_{\Omega}$ tries to maximize the objective and $G$ tries to minimize it.

In this work, as shown in Figure 2, $\Omega=\\{i,s,d\\}$, denoting three tasks
of inpainting, segmentation, and (landmark) detection. $x$ is the occluded
image, $y_{i}$ is the original face, $y_{s}$ is the segmentation mask and
$y_{d}$ is the detection heatmap (See Section 4.1).
$D_{\Omega}=\\{D_{i},D_{s},D_{d}\\}$ where $D_{i}$, $D_{s}$ and $D_{d}$ are
the discriminators for the inpainting, segmentation and detection tasks,
respectively. $G(x,z)=[G^{i}(x,z),G^{s}(x,z),G^{d}(x,z)]$ are the generator
outputs for the three tasks.

Note that instead of only applying adversarial loss to the inpainted image, we
have dedicated discriminators for each of the tasks. Our design follows the
observation that GANs can also be helpful in some non-generative tasks [28].
In our case, GANs are used to keep the long-range spatial label contiguity of
the detection heatmap and the segmentation mask. We have also experimented
with an optional setting that feeds the outputs of all the tasks into a single
discriminator and discover that the single discriminator selectively ignores
the inpainting result as the outputs from other tasks are much easier for
judging the realness. Besides, the collaGAN is conditioned on multiple
discriminators, one per task. Such a design, on one hand, ensures the
perceptual quality of the generated image and, on the other hand, keeps the
spatial consistency between the input image and generated image. This choice
was also shown to be effective in [12].

###  3.2 Reconstruction Loss

It has been found by previous approaches [12, 30] that mixing the adversarial
loss with a reconstruction loss is beneficial to generative image-to-image
models. A reconstruction loss gives pixel-level measurement of the errors
which is a direct regularization between the output and the ground truth. It
can capture the overall structure of the target object but is usually unable
to give a sharp output. An adversarial loss, on the other hand, can produce
perceptually better result but the output may not be structurally consistent
with input. Therefore, we combine these two to achieve both realistic and
coherent output.

In our case, the reconstruction loss is computed for the three tasks as
denoted in Figure 2. For the inpainting task, the reconstruction loss
$\mathcal{L}_{rec}^{i}$ measures the L1 distance between the inpainted image
and the unoccluded image. Here, we use the L1 loss instead of the L2 loss due
to the observation that the L2 loss tends to give slightly blurry outputs. For
the segmentation mask, we first convert the label mask to a multi-channel map
with each channel denoting the binary mask of a label. Then, we apply the L2
loss $\mathcal{L}_{rec}^{s}$ to the multi-channel map to measure the
difference between the network output and the ground truth. We use the L2 loss
against the typical cross-entropy loss simply for the ease of implementation
as the generator (See section 3.4) produces outputs with values between
$(-1,1)$ which favors a regression loss. In our experiments, we find the L2
loss gives good enough segmentation map for this study. For the detection
heatmap, we also use the L2 loss $\mathcal{L}_{rec}^{d}$ as the regularizer
adapting the choices from [32, 31]. Let $\Omega=\\{i,s,d\\}$, the total
reconstruction loss can be written as

$\mathcal{L}^{\Omega}_{rec}=\sum_{t\in\Omega}\lambda_{rec}^{t}\mathcal{L}_{rec}^{t},$
(2)

where $\mathcal{L}_{rec}^{t}$ denotes the reconstruction loss of task $t$ and
$\lambda_{rec}^{t}$ denotes the importance of each loss. The final objective
function is then given by

$\mathcal{L}^{\Omega}=\mathcal{L}_{adv}^{\Omega}+\mathcal{L}_{res}^{\Omega}.$
(3)

(a)

(b)

(c)

(d)

Figure 3: Example output of the network trained with the inpainting
concentrated scheme. From (a) to (d): (a) original image, (b) masked image,
(c) output from the generator, and (d) the final inpainting result by
combining (b) and (c).

###  3.3 Inpainting Concentrated Generation

In previous work [21], image inpainting is performed through an autoencoder
and the unoccluded region is reconstructed along with the occluded part. Thus,
the network spends significant portion of its computing power on autoencoding
the already available information while the inpainting itself is not fully
addressed. A direct approach [30] to this problem is having the generator only
outputs the content within the mask. However, this only works for the case
where the masks are rectangular. When random shaped regions are occluded, this
approach fails as convolutional neural networks cannot generate non-
rectangular images. To address this problem for arbitrary shaped masks, we
propose an inpainting concentrated scheme. The scheme consists of two parts:
an adversarial part and a reconstruction part. For the adversarial part, we
modify the adversarial loss for the inpainting such that the discriminator,
instead of judging the realness of the generated image, concentrates on
finding the incoherence between the inpainted region and the context.
Formally, let $M$ be a binary mask where pixels in the occluded region are 0
and anywhere else are 1. The new adversarial loss for inpainting can be
written as

$\begin{split}&\mathcal{L}_{adv}^{i}=\mathbb{E}_{x,y_{i}\sim
p_{data}(x,y_{i})}[\log D_{i}(x,y_{i})]\\\ &+\lambda_{i}\mathbb{E}_{x\sim
p_{data}(x),z\sim p_{z}(z)}[(1-\log D_{i}(x,\hat{y}_{i}))],\end{split}$ (4)

where

$\hat{y}_{i}=G^{i}(x,z)\odot(1-M)+x\odot M.$ (5)

As demonstrated in Figure 2, $\hat{y}_{i}$ is nothing but the inpainting
output from the generator with the unoccluded region replaced by the ground
truth. Such a replacement guarantees that the discriminator does not need to
worry about the unrealness of the context and thus the inpainted region is
concentrated. For the reconstruction part, we introduce an inpainting
concentrated reconstruction loss that only computes the L1 distances within
the occluded region. That is,

$\begin{split}\mathcal{L}^{i}_{rec}=\lVert
y_{i}\odot(1-M)-G^{i}(x,z)\odot(1-M)\rVert_{1}.\end{split}$ (6)

With this scheme, we make sure that no errors outside the occluded region will
be backpropagated to the generator, and therefore the unnecessary autoencoding
is not learned. Figure 3(c) shows an example output of the network trained
with the proposed scheme. The network produces sharp and realistic results
inside the occluded region and produces inferior results for the context
region that contributes little to the inpainting. Figure 3(d) is obtained
using Equation (5). The inpainted region coherently fits with the context and
the image overall looks realistic.

###  3.4 Network Architecture

For the generator and discriminator, we follow the architecture choices in
[33] for stable deep convolutional GANs. Both the generator and discriminator
take an input image of size $128\times 128$. For the generator, its encoder
has $7$ convolution layers with each layer followed by a batch normalization
layer [11] and a LeakyReLU [7] layer. The decoder has a symmetric structure
with the encoder, except that it uses transposed convolution and ReLU [15].
All the convolutional layers have a $4\times 4$ kernel size with a stride of
2. The output layer of the generator is a $\tanh$ function. We also adapt the
design suggestion from [12] by adding skip connections between encoder and
decoder. Skip connections shuttle low level features directly to decoder
without passing through the “bottleneck layers”. Such a circumvention is
critical to some tasks such as semantic segmentation [34] (which is also
included in the collaborative training) and we also find this helpful in
improving the coherence between the context and the inpainted region. The
discriminator has a similar structure to the encoder, except that it only has
$5$ convolutional layers.

##  4 Experimental Results

###  4.1 Datasets

The dataset used in our experiment is the CelebA [27] dataset. It has
$202,599$ face images and we use the official split for training, validating
and testing. Unlike the state-of-the-art works [39, 21], we do not align the
faces according to the eyes. In fact, we find such alignment makes the
inpainting much easier for the models as they do not need to semantically
learn too much about the locations of the eyes and other face parts. Hence, to
avoid overfitting and achieve better generalization, when cropping the faces,
we only guarantee that the eyes, nose and mouth are included and no alignment
is performed. We also augment the dataset by random shift, scaling, rotation
and flipping to further ensure the diversity of the faces during training.

Along with each face image, the CelebA dataset readily provides the locations
of 5 face landmarks (the two eyes, nose and the two corners of mouth). We
create heatmaps from the landmarks according to the method denoted in [32,
31]. The generated heatmaps will be used during collaborative training. For a
fair comparison, we obtain segmentation masks for each of the faces using the
parsing network provided by [21]. The network is trained based on the Helen
[17] dataset and achieves a close to state-of-the-art performance. Hence, it
is considered sufficient for this study, which is supported by our
experimental results. Also, using computer-generated annotations alleviates
the burden of laborious manual annotation effort.

All images in the experiments are resized to $128\times 128$. We use this size
choice for a fair comparison with other approaches. It is straighforward for
the proposed method to use a large image size. Following the mask generation
strategies in previous works, we apply three different masks to the resized
images: 1) random block mask with a $64\times 64$ block [21]; 2) random
pattern mask [30] with roughly 25% of the pixels missing; 3) random noise mask
with 80% of the pixels missing [39]. For 1) and 3) the masked region is filled
with random noise. For 2), the masked region is filled with zeros as the mask
itself is already noisy.

###  4.2 Models

To demonstrate the effectiveness of the proposed method, the performances
under different model settings are investigated. We denote $M_{\Omega}$ as the
model trained using $L^{\Omega}$ and $M_{\Omega}^{*}$ as the model trained in
addition with the inpainting concentrated scheme. Model settings are changed
by varying $\Omega$ and switching between $M_{\Omega}$ and $M_{\Omega}^{*}$.
All the investigated models are trained for 20 epochs. For the optimization,
we use the Adam [13] optimizer with a learning rate of $0.01$. For the weights
of different losses, we emperically find the following settings work well:

  * •

Models with one task: $\lambda_{adv}^{i}=1.0$, $\lambda_{adv}^{s}=1.0$,
$\lambda_{adv}^{d}=1.0$, $\lambda_{res}^{i}=100$, $\lambda_{res}^{s}=1000$,
$\lambda_{res}^{d}=1000$;

  * •

Models with two tasks: $\lambda_{adv}^{i}=0.8$, $\lambda_{adv}^{s}=0.2$,
$\lambda_{adv}^{d}=0.2$, $\lambda_{res}^{i}=100$, $\lambda_{res}^{s}=200$,
$\lambda_{res}^{d}=200$;

  * •

Models with three tasks: $\lambda_{adv}^{i}=0.8$, $\lambda_{adv}^{s}=0.1$,
$\lambda_{adv}^{d}=0.1$, $\lambda_{res}^{i}=100$, $\lambda_{res}^{s}=200$,
$\lambda_{res}^{d}=200$.

For models with one or two tasks, the parameters will be used only when they
are applicable. For example, model $\mathrm{M_{i}}$ will only have
$\lambda_{adv}^{i}=1.0$ and $\lambda_{res}^{i}=100$. Other parameters are not
used as they are for $\mathrm{M_{s}}$ and $\mathrm{M_{d}}$. Note for this
study we are not interested in the best parameter settings for each model.
Hence, the parameters are chosen when they work reasonably well. For the
$\lambda_{adv}^{i}$, we generally find $0.8$ works better in a multi-task
scenario and other adversarial loss paramters are chosen such that they sum up
to 1. For the reconstruction loss parameters, we find minor performance
differences when they are in a reasonable range. In general, setting
$\lambda_{res}^{i}$ around $100$ and $\lambda_{res}^{s}$ and
$\lambda_{res}^{d}$ around $200$ gives good performance when several tasks are
presented. Setting values close to these numbers give similar performances and
the performances are degraded when the values are too large or too small.

###  4.3 Face Completion

(a) original

(b) masked

(c) $\mathrm{M_{i}}$

(d) $\mathrm{M_{i,d}}$

(e) $\mathrm{M_{i,s}}$

(f) $\mathrm{M_{i,s,d}}$

(g) $\mathrm{M_{i,s,d}^{*}}$

Figure 4: Qualitative face completion comparison of our models with different
settings and varying numbers of tasks.

Qualitative Comparison During the experiments, we find in general the models
trained with more collaborative tasks produce more realistic results. Figure 4
shows some example outputs of our models. The first row demonstrates that, for
an easy inpainting task where context coherence is not critical, the models
can all produce relatively good looking faces and the collaboratively trained
models from (d) to (g) tend to emphasis more on landmarks (eyes in this case)
to give even better inpainting outputs. In the second row, we show a
challenging case that only part of the woman’s left eye is present and the
entire right eye is missing. This inpainting task requires the model to both
complete the left eye and reconstruct the entire right eye such that the two
eyes together looking realistic. Without collaborative inpainting, the
$\mathrm{M_{i}}$ model does not consider the coherence between the two eyes
and inpaints the two eyes independently. The other models try to more or less
balance the two eyes so that they have the same shape, size and color. The two
models trained with three tasks in the last two columns give relatively better
inpainting of the eyes. Overall, the $\mathrm{M_{i,s,d}^{*}}$ model trained
using the inpainting concentrated scheme gives the most realistic output.

Figure 5: Qualitative face completion comparison between the proposed method
and the state-of-the-art methods. Different masks are applied. From (a) to
(f): (a) original image, (b) masked image, and results of (c) the proposed
$\mathrm{M_{i,s,d}^{*}}$ model, (d) CE [30], (e) SII [39] and (f) GFC [21].

We then compare the proposed method with other state-of-the-art models: CE
[30], SII [39] and GFC [21]. Since we use a slightly different face cropping
and data augmentation strategy, we retrain those models for a fair comparison.
All retrainings are based on their officially released code with the training
parameters unchanged. For SII [39], all the experiments are performed using
$64\times 64$ images as DCGAN [33] only works well on images with lower
resolution. For all the models, poisson blending is performed. The comparison
results are given in Figure 5. To demonstrate the generalizability of the
models on various shaped masks, the random pattern masked images in columns
4-6 are inpainted using the models trained with random block masks. For the
random noise mask case, since GFC [21] requires square masks for the local
loss, it cannot be used to complete random noise masked images. Hence, the
inpainting results for GFC [21] in columns 7-9 are omitted. Also, for CE [30]
and our method, we train a new model for the random noise mask case due to the
uniqueness of the mask.

From Figure 5, we observe that our model consistently gives better inpainting
results than the state-of-the-art methods. In general, SII [39] gives the
worst results in all the cases. Due to the unaligned faces and the data
augmentation we performed during training, the face scene becomes more
complex. Thus, the DCGAN model used in SII [39] can not learn the face data
distribution very well, which as a result yieds inferior inpainting
performance during the inference step. The CE [30] and GFC [21] models in
general produce reasonably good results, especially when the faces are
aligned. However, as they either train the model without using additional
structural constrains or has an indirect measurement of structural
inconsistency, their synthesized images are less structurally realistic than
ours.

Figure 6 shows the feature maps extracted from the last common layer in the
generator G of the $\mathrm{M_{i,s,d}}$ and $\mathrm{M_{i}}$ models. The
$\mathrm{M_{i,s,d}}$ model is more predictive in the masked region and outputs
better face related features. It is interesting to notice that the
$\mathrm{M_{i,s,d}}$ model tends to treat face parts independently. Some maps
contain features only about nose, mouse or eyes. While the $\mathrm{M_{i}}$
model mostly outputs features about the whole face. This indicates that the
$\mathrm{M_{i,s,d}}$ model is more discriminative about the face than the
$\mathrm{M_{i}}$ model and it learns to distinguish (and generate) each of the
face part due to the training with other tasks.

Quantitative Comparison In addition to the visual comparison, we also
quantitatively compare our models with the state-of-the-art models to
statistically understand their inpainting performances. All the evaluated
models are trained with random block masks. We use two classic metrics, PSNR
and SSIM, to evaluate the similarity between the inpainted image and the
ground truth. PSNR gives the similarity score at pixel-level while SSIM
evaluates the similarity at perceptual level. The ground truth image used in
this evaluation is the original image before the occlusion. However, since
given an occluded image, there could be multiple inpainting results that are
perceptually correct, we realize that neither PSNR or SSIM offers a perfect
evaluation. But due to the symmetric nature and the relatively simple
structure of human faces, as long as the occlusion does not hide significant
portion of the face, all the possible inpainting results should be similar
which gives us an opportunity to roughly evaluate the models’ performance.
Table 1 shows the evaluation results at 6 different mask locations. We adapt
the mask location choices from [21] by masking out left eye (O1), right eye
(O2), upper face (O3), left face (O4), right face (O5), and lower face (O6),
respectively. We intentionally select relatively smaller mask sizes (on
average $40\times 48$) to limit the variation of all possible inpaintings. We
observe from Table 1 that our base model $\mathrm{M_{i}}$ has already obtained
comparable or slightly better performance than the state-of-the-art models
which demonstrates the effectiveness of introducing skip connections into
collaGAN. In general, models trained with more tasks give better numbers in
both PSNR and SSIM. This shows that the knowledge among tasks is indeed
collaborative during training. We also find that $\mathrm{M_{i,s,d}^{*}}$
performs slightly better than $\mathrm{M_{i,s,d}}$ which means the inpainting
concentrated scheme is really helpful in getting better inpainting results.
Overall, we spot a significant performance jump with the proposed method when
compared with the state-of-the-art models.

(a)

(b)

(c)

Figure 6: Feature maps from the last common layer in the generator G. Face
related features are marked with yelow squares. Features from early layers
through the skip connection are omitted. (a) The original and masked images,
(b) Feature maps of the $\mathrm{M_{i,s,d}}$ model, and (c) Feature maps of
the $\mathrm{M_{i}}$ model.

To further understand the collaborative nature of the proposed method, we also
investigate if the inpainting can help other tasks as well. Specifically, we
want to know that, through the learning of inpainting, if the model can
predict better of the semantical labels and landmarks in the occluded region.
We use the Dice coefficient and localization error to evaluate the performance
of semantic segmentation and landmark detection, respectively. The Dice
coefficient measures the similarity of two segmentation masks and the
localization error computes the Euclidean distances between two landmarks.
Table 3 gives the Dice coefficient of different models trained with the
segmentation task. The performances of the facial semantic labels are shown.
It is clear that the collaboratively trained models perform better than single
task models and the models trained with three tasks better than with two
tasks. The $\mathrm{M_{i,s,d}}$ and $\mathrm{M_{i,s,d}^{*}}$ models have very
close performance. This is reasonable as the inpainting concentrated scheme is
designed solely for inpainting and does not introduce additional information
to other tasks during training. Note that, for the segmentation task, the
performance difference of the models is not significant. We speculate that
this is because the “ground truth” is computer-generated from the parsing
network which sometimes may not give perfect prediction. For the landmark
detection task with accurately labeled landmark locations provided by the
CelebA dataset, the performance boost of introducing other tasks is more
significant as shown in Table 3. For example, the average landmark error is
reduced from 2.38 (the $\mathrm{M_{d}}$ model) to 1.72 (the
$\mathrm{M_{i,s,d}^{*}}$ model), a 27.7% decrease.

Table 1: Quantitative face completion comparison of different models evaluated
at 6 different mask locations: left eye (O1), right eye (O2), upper face (O3),
left face (O4), right face (O5), and lower face (O6). The numbers in each cell
are SSIM (%)/PSNR (dB), the higher the better.

|  | O1 |  | O2 |  | O3 |  | O4 |  | O5 |  | O6
---|---|---|---|---|---|---|---|---|---|---|---|---
CE [30] |  | 90.5/26.74 |  | 90.6/27.01 |  | 93.8/27.90 |  | 95.8/30.37 |  | 96.0/30.65 |  | 90.0/27.11
SII [39] |  | 87.5/23.93 |  | 87.7/24.12 |  | 93.0/26.61 |  | 95.6/28.94 |  | 95.9/29.38 |  | 87.8/24.84
GFC [21] |  | 90.6/27.10 |  | 90.9/27.34 |  | 94.0/28.68 |  | 96.3/31.18 |  | 96.3/31.11 |  | 90.0/27.13
$\mathbf{M_{i}}$ |  | 90.8/27.23 |  | 91.1/27.42 |  | 94.0/28.53 |  | 96.0/30.94 |  | 96.1/31.06 |  | 90.1/27.15
$\mathbf{M_{i,d}}$ |  | 91.7/27.57 |  | 91.6/27.81 |  | 94.5/28.76 |  | 96.4/31.33 |  | 96.5/31.36 |  | 90.7/27.37
$\mathbf{M_{i,s}}$ |  | 91.4/27.59 |  | 91.5/27.65 |  | 94.3/28.66 |  | 96.4/31.22 |  | 96.4/31.28 |  | 90.7/27.55
$\mathbf{M_{i,s,d}}$ |  | 91.7/27.66 |  | 91.8/27.87 |  | 94.5/28.77 |  | 96.5/31.31 |  | 96.6/31.39 |  | 90.8/27.57
$\mathbf{M^{*}_{i,s,d}}$ |  | 92.4/27.76 |  | 92.6/27.96 |  | 95.2/28.79 |  | 97.2/31.44 |  | 97.2/31.50 |  | 91.7/27.81

Table 2: Semantic segmentation performance of different models. The numbers are given as Dice coeffient (%). Higher numbers are better. |  | $\mathbf{M_{s}}$ |  | $\mathbf{M_{i,s}}$ |  | $\mathbf{M_{i,s,d}}$ | $\mathbf{M_{i,s,d}^{*}}$
---|---|---|---|---|---|---|---
Face |  | 93.7 |  | 94.1 |  | 94.2 | 94.1
Left eyebrow |  | 74.2 |  | 74.6 |  | 75.0 | 75.2
Right eyebrow |  | 72.3 |  | 72.8 |  | 73.8 | 73.5
Left eye |  | 70.7 |  | 71.9 |  | 72.2 | 72.7
Right eye |  | 70.0 |  | 70.3 |  | 71.2 | 71.2
Nose |  | 90.5 |  | 90.9 |  | 90.9 | 91.0
Upper lip |  | 68.1 |  | 67.2 |  | 68.3 | 67.9
Teeth |  | 64.2 |  | 66.5 |  | 66.8 | 66.7
Lower lip |  | 81.4 |  | 82.1 |  | 82.8 | 82.4
Average |  | 76.1 |  | 76.7 |  | 77.2 | 77.2

Table 3: Landmark detection performance of different models. The numbers are given as localization errors in pixels. Lower numbers are better. |  | $\mathbf{M_{d}}$ |  | $\mathbf{M_{i,d}}$ |  | $\mathbf{M_{i,s,d}}$ | $\mathbf{M_{i,s,d}^{*}}$
---|---|---|---|---|---|---|---
Left eye |  | 2.12 |  | 1.73 |  | 1.61 | 1.60
Right eye |  | 2.29 |  | 1.71 |  | 1.59 | 1.62
Nose |  | 2.53 |  | 2.15 |  | 1.92 | 1.93
Left mouth |  | 2.39 |  | 1.80 |  | 1.74 | 1.73
Right mouth |  | 2.57 |  | 1.86 |  | 1.77 | 1.72
Average |  | 2.38 |  | 1.85 |  | 1.73 | 1.72

##  5 Conclusion

We present a novel collaborative GAN framework for face completion. The
experimental results suggest that training multiple related tasks together
within the proposed framework is beneficial. By infusing more knowledge, the
generative model learns better about the inpainting through the knowledge
sharing of the segmentation and detection tasks, whose performances are
boosted vice versa. We have also found that optimizing directly toward
inpainting other than autoencoding produces better inpainting results in an
image-to-image network. Finally, we have demonstrated that the proposed method
can give superior inpainting performance than the state-of-the-art methods.

Disclaimer: This feature is based on research, and is not commercially
available. Due to regulatory reasons its future availability cannot be
guaranteed.

## References

  * [1] Barnes, C., Shechtman, E., Finkelstein, A., Goldman, D.B.: Patchmatch: A randomized correspondence algorithm for structural image editing. ACM Trans. Graph. 28(3), 24–1 (2009)
  * [2] Caruana, R.: Multitask learning. In: Learning to learn, pp. 95–133. Springer (1998)
  * [3] Ganin, Y., Ustinova, E., Ajakan, H., Germain, P., Larochelle, H., Laviolette, F., Marchand, M., Lempitsky, V.: Domain-adversarial training of neural networks. The Journal of Machine Learning Research 17(1), 2096–2030 (2016)
  * [4] Girshick, R.: Fast r-cnn. arXiv preprint arXiv:1504.08083 (2015)
  * [5] Hays, J., Efros, A.A.: Scene completion using millions of photographs. In: ACM Transactions on Graphics (TOG). vol. 26, p. 4. ACM (2007)
  * [6] He, K., Sun, J.: Statistics of patch offsets for image completion. In: Computer Vision–ECCV 2012, pp. 16–29. Springer (2012)
  * [7] He, K., Zhang, X., Ren, S., Sun, J.: Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In: Proceedings of the IEEE international conference on computer vision. pp. 1026–1034 (2015)
  * [8] Hinton, G.E., Salakhutdinov, R.R.: Reducing the dimensionality of data with neural networks. science 313(5786), 504–507 (2006)
  * [9] Huang, J.B., Kang, S.B., Ahuja, N., Kopf, J.: Image completion using planar structure guidance. ACM Transactions on Graphics (TOG) 33(4), 129 (2014)
  * [10] Iizuka, S., Simo-Serra, E., Ishikawa, H.: Globally and locally consistent image completion. ACM Transactions on Graphics (TOG) 36(4), 107 (2017)
  * [11] Ioffe, S., Szegedy, C.: Batch normalization: Accelerating deep network training by reducing internal covariate shift. In: International Conference on Machine Learning. pp. 448–456 (2015)
  * [12] Isola, P., Zhu, J.Y., Zhou, T., Efros, A.A.: Image-to-image translation with conditional adversarial networks. arXiv preprint arXiv:1611.07004 (2016)
  * [13] Kingma, D., Ba, J.: Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)
  * [14] Kingma, D.P., Welling, M.: Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114 (2013)
  * [15] Krizhevsky, A., Sutskever, I., Hinton, G.E.: Imagenet classification with deep convolutional neural networks. In: Advances in neural information processing systems. pp. 1097–1105 (2012)
  * [16] Larsen, A.B.L., Sønderby, S.K., Larochelle, H., Winther, O.: Autoencoding beyond pixels using a learned similarity metric. arXiv preprint arXiv:1512.09300 (2015)
  * [17] Le, V., Brandt, J., Lin, Z., Bourdev, L., Huang, T.S.: Interactive facial feature localization. In: European Conference on Computer Vision. pp. 679–692. Springer (2012)
  * [18] Ledig, C., Theis, L., Huszár, F., Caballero, J., Cunningham, A., Acosta, A., Aitken, A., Tejani, A., Totz, J., Wang, Z., et al.: Photo-realistic single image super-resolution using a generative adversarial network. arXiv preprint arXiv:1609.04802 (2016)
  * [19] Li, J., Liang, X., Wei, Y., Xu, T., Feng, J., Yan, S.: Perceptual generative adversarial networks for small object detection. In: IEEE CVPR (2017)
  * [20] Li, W., Xiong, W., Liao, H., Huo, J., Gao, Y., Luo, J.: Carigan: Caricature generation through weakly paired adversarial learning. arXiv preprint arXiv:1811.00445 (2018)
  * [21] Li, Y., Liu, S., Yang, J., Yang, M.H.: Generative face completion. arXiv preprint arXiv:1704.05838 (2017)
  * [22] Liao, H., Huo, Z., Sehnert, W.J., Zhou, S.K., Luo, J.: Adversarial sparse-view cbct artifact reduction. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 154–162. Springer (2018)
  * [23] Liao, H., Lin, W.A., Huo, Z., Vogelsang, L., Sehnert, W.J., Zhou, S.K., Luo, J.: Generative mask pyramid network for ct/cbct metal artifact reduction with joint projection-sinogram correction. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 77–85. Springer (2019)
  * [24] Liao, H., Tang, Y., Funka-Lea, G., Luo, J., Zhou, S.K.: More knowledge is better: Cross-modality volume completion and 3d+ 2d segmentation for intracardiac echocardiography contouring. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 535–543. Springer (2018)
  * [25] Lin, W.A., Liao, H., Peng, C., Sun, X., Zhang, J., Luo, J., Chellappa, R., Zhou, S.K.: Dudonet: Dual domain network for ct metal artifact reduction. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. pp. 10512–10521 (2019)
  * [26] Liu, P., Qiu, X., Huang, X.: Adversarial multi-task learning for text classification. arXiv preprint arXiv:1704.05742 (2017)
  * [27] Liu, Z., Luo, P., Wang, X., Tang, X.: Deep learning face attributes in the wild. In: Proceedings of International Conference on Computer Vision (ICCV) (12 2015)
  * [28] Luc, P., Couprie, C., Chintala, S., Verbeek, J.: Semantic segmentation using adversarial networks. arXiv preprint arXiv:1611.08408 (2016)
  * [29] Mirza, M., Osindero, S.: Conditional generative adversarial nets. arXiv preprint arXiv:1411.1784 (2014)
  * [30] Pathak, D., Krahenbuhl, P., Donahue, J., Darrell, T., Efros, A.A.: Context encoders: Feature learning by inpainting. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. pp. 2536–2544 (2016)
  * [31] Payer, C., Štern, D., Bischof, H., Urschler, M.: Regressing heatmaps for multiple landmark localization using cnns. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 230–238. Springer (2016)
  * [32] Pfister, T., Charles, J., Zisserman, A.: Flowing convnets for human pose estimation in videos. In: Proceedings of the IEEE International Conference on Computer Vision. pp. 1913–1921 (2015)
  * [33] Radford, A., Metz, L., Chintala, S.: Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint arXiv:1511.06434 (2015)
  * [34] Ronneberger, O., Fischer, P., Brox, T.: U-net: Convolutional networks for biomedical image segmentation. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 234–241. Springer (2015)
  * [35] Simonyan, K., Zisserman, A.: Two-stream convolutional networks for action recognition in videos. In: Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N.D., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems 27, pp. 568–576. Curran Associates, Inc. (2014), http://papers.nips.cc/paper/5353-two-stream-convolutional-networks-for-action-recognition-in-videos.pdf
  * [36] Vincent, P., Larochelle, H., Bengio, Y., Manzagol, P.A.: Extracting and composing robust features with denoising autoencoders. In: Proceedings of the 25th international conference on Machine learning. pp. 1096–1103. ACM (2008)
  * [37] Whyte, O., Sivic, J., Zisserman, A.: Get out of my picture! internet-based inpainting. In: BMVC. vol. 2, p. 5 (2009)
  * [38] Yang, C., Lu, X., Lin, Z., Shechtman, E., Wang, O., Li, H.: High-resolution image inpainting using multi-scale neural patch synthesis. In: The IEEE Conference on Computer Vision and Pattern Recognition (CVPR). vol. 1, p. 3 (2017)
  * [39] Yeh, R., Chen, C., Lim, T.Y., Hasegawa-Johnson, M., Do, M.N.: Semantic image inpainting with perceptual and contextual losses. arXiv preprint arXiv:1607.07539 (2016)
  * [40] Zhang, Z., Luo, P., Loy, C.C., Tang, X.: Facial landmark detection by deep multi-task learning. In: European Conference on Computer Vision. pp. 94–108. Springer (2014)


# Fast Node Vector Distance Computations using Laplacian Solvers

Michele Coscia
IT University of Copenhagen
Copenhagen, Denmark
<EMAIL_ADDRESS>
&Karel Devriendt
Max Planck Institute for Mathematics in the Sciences
Leipzig, Germany
<EMAIL_ADDRESS>
###### Abstract

Complex networks are a useful tool to investigate various phenomena in social
science, economics, and logistics. Node Vector Distance (NVD) is an emerging
set of techniques allowing us to estimate the distance and correlation between
variables defined on the nodes of a network. One drawback of NVD is its high
computational complexity. Here we show that a subset of NVD techniques, the
ones calculating the Generalized Euclidean measure on networks, can be
efficiently tackled with Laplacian solvers. In experiments, we show that this
provides a significant runtime speedup with negligible approximation errors,
which opens the possibility to scale the techniques to large networks.

##  1 Introduction

Complex networks are useful for a number of tasks. One prominent example is
tracking the propagation of a phenomenon through a complex system. Examples
range from diseases [3, 26, 42], memes/behaviors [19, 47, 16, 14, 22], or
product adoption [28, 45] through a social network; productive knowledge in
international trade [21, 41]; or goods in network modeling problems in
logistics [33].

The Node Vector Distance (NVD) term has been recently used to group these
tasks under a common structure [13]. In NVD, the phenomenon is represented as
a vector recording one value per node. Then two vectors from different
phenomena, or from the same phenomenon at different observation times, can be
compared. Specifically, with NVD one can calculate their distance, network
variance, or correlation.

Most useful NVD techniques share a drawback: they are computationally complex
to calculate. This severely limits their practical applicability to nodes
containing a handful thousands of nodes, a far cry from the (tens or hundreds)
million of nodes of the most interesting complex networks.

In this paper we focus specifically on those NVD techniques based on the
inversion of the graph Laplacian [10]. We do so for two reasons. First, these
measures are among the most intuitive available. Second, because it turns out
that the most computationally intensive part of calculating such measures is
not necessary.

We show how the already existing collection of techniques known as “Laplacian
solvers” [37] can be directly applied to the Generalized Euclidean NVD
technique, greatly reducing its computational complexity and allowing the
analysis of really large complex networks.

In our experiments we show how much runtime we gain in synthetic networks of
growing sizes, showing an empirical estimation of the new computational
complexity. We also do a brief analysis of the memory consumption. Finally, we
show the practical applicability on a number of real world networks. The
latter experiments also shows that, even if Laplacian solvers do not provide
exact solutions, the approximation they induce is negligible for all practical
purposes.

All the experiments we run can be reproduced with the material we
provide111https://www.michelecoscia.com/?page_id=1733#nvdfast.

##  2 Related Works

###  2.1 Node Vector Distance

Node Vector Distance (NVD) is a collection of techniques to estimate the
network distance between node vectors – vectors recording one value per node
[13]. NVD has a number of applications in network science, it can be used to
track disease spreading [3], estimate the complexity of a country’s economy
[21], or quantify ideological polarization on social media [22]. The
techniques at the basis of NVD can also be used to estimate how dispersed a
variable is in a network [15], as well as calculating the correlations between
node vectors on a network [12].

There are a number of different approaches one can take. One can apply graph
signal processing techniques via the graph Fourier transform [35, 36]. Another
popular approach is to compute the optimal way to transport the weights of one
vector to another with respect to the distance in the network, giving rise to
the Earth Mover Distance [33, 50].

In this paper we focus on a different class of solutions, which we label
“Generalized Euclidean”. In this class, one adapts the classical Euclidean
distance to the graph setting. In the case of regular Euclidean distance, the
node vectors are embedded in a space where all dimensions contribute equally –
here, the distance is induced by the inner product represented by the identity
matrix, so there is no distinction between the nodes. In the case of
Generalized Euclidean distance, the node vectors are embedded in a complex
space represented by the graph; more precisely, the distance between node
vectors in this space is given by computing the quadratic product of their
difference with the pseudoinverse Laplacian matrix as in Section 3.1. Note
that using the pseudoinverse Laplacian is not a unique solution, as there are
other ways to take into account the graph structure in the Euclidean formula
[10].

Since the pseudoinverse Laplacian is the technique we focus on in this paper,
we will provide more details about this approach in Section 3. For the purpose
of this section, we only need to mention that pseudoinverting the Laplacian is
computationally complex, but not necessary. One can achieve an approximate
result by using Laplacian solvers, which we discuss now.

###  2.2 Laplacian Solvers

Laplacian solvers are a class of solutions to problems in the form $Lx=b$,
where $L$ is the Laplacian of an undirected graph [43]. These solvers have a
number of applications in graph partitioning and specification.

Laplacian solvers make use of a number of techniques to solve the $Lx=b$
problem in near linear time [37, 38, 39, 40]. Examples include sparse
approximate Gaussian elimination [27], building a chain of progressively
sparser graphs [24, 25], and recursive graph preconditioning [40].

One major drawback of the methods cited so far is that they only work with
undirected graphs. However, there is a collection of techniques that work on
directed graphs as well [8, 7].

##  3 Methods

###  3.1 Generalized Euclidean

Let us assume we are working with a graph $G=(V,E)$, with $V$ being the set of
nodes and $E\subseteq V\times V$ the set of edges – pairs of nodes. For this
paper we assume to work with undirected graphs: if $u,v\in V$ and $(u,v)\in
E$, then $(u,v)=(v,u)$. The graphs can be weighted, i.e. each edge can have a
positive real weight $w>0$ – although, in this paper, we ignore weights
(including them does not change any of our conclusions).

We can define a number of useful matrices. $A$ is the adjacency matrix of $G$,
with $A_{uv}=1$ if $(u,v)\in E$ and $A_{uv}=0$ otherwise. $D$ is the degree
matrix, the degree being the number of connections a node has. $D$ contains
the degree of a node in the main diagonal and zero elsewhere. The Laplacian
matrix is defined as $L=D-A$, i.e. it contains the degree of a node on the
main diagonal and $L_{uv}=-1$ if $(u,v)\in E$.

The Laplacian is useful to solve a number of problems. For instance, it can be
used to solve the discrete heat exchange problem. If $h$ contains the heat
value for each node of the network, we can use the Laplacian to estimate how
heat propagates through the graph. This is done by solving the differential
equation $\dfrac{\partial h}{\partial t}=-Lh$ [9]. It can also be used for
spectral clustering [44].

It follows that the Laplacian is helpful to understand the relationships
between nodes. Previous work has exploited this fact to use the Laplacian as
the matrix defining the space in which a Generalized Euclidean (GE) distance
measure lives. If we are given two vectors $a$ and $b$, each with $|V|$
entries, then their network distance is:

$\delta_{G,a,b}=\sqrt{(a-b)^{T}L^{\dagger}(a-b)}.$

where $L^{\dagger}$ is the (Moore–Penrose) pseudoinverse of $L$. $L$ cannot be
inverted directly, because it is singular. To calculate $L^{\dagger}$ one
needs to perform a singular value decomposition (SVD) of $L$. Herein lies the
main issue with this measure: SVD requires $\mathcal{O}(|V|^{\alpha})$ time to
be solved, with $\alpha$ larger than $2$ and smaller than $3$. This makes GE
intractable for all but trivially sized graphs.

###  3.2 Laplacian Solvers

A Laplacian solver is a technique that is able to solve systems of linear
equations in the form of $Lx=b$ in near linear time. To explain each Laplacian
solver techniques in depth goes beyond the scope of this paper. In Section 2.2
we provide further references. In this section, we briefly mention how some of
these solvers work.

Sparse approximate Gaussian elimination [27] works by performing an
approximate sparse Cholesky decomposition. The Cholesky decomposition is an
efficient algorithm for solving systems of linear equations. The issue is
that, locally, $L$ does not satisfy the sparsity assumption for the Cholesky
decomposition – e.g. in case of large cliques. Thus, cliques need to be
sampled and then the regular Cholesky decomposition can be applied.

Spectral graph sparsification [24, 25] works by taking $G$ and sparsify it to
$G^{\prime}$ in such a way that $G$ and $G^{\prime}$ have very similar
spectra. This is done iteratively via a preconditioning chain. After the first
spectral sparsification, $G^{\prime}$ is then contracted by eliminating nodes
of degree $1$ and $2$. This can be done efficiently, because the spectrum of
the Laplacian is related to the cut problem, and it is possible to sparsify
the graph while preserving its cuts.

Recursive graph preconditioning [40] puts together the previous two approaches
by recursively sparsifying $G$ via a partial Cholesky factorization, ensuring
a low condition number at every step in the recursion.

##  4 Experiments

###  4.1 Setup Details

####  4.1.1 Implementation

We implement the GE function in Julia (version 1.8.0). We use the
Laplacians.jl package222https://danspielman.github.io/Laplacians.jl/dev/ for
Julia to access implementations of the Laplacian solvers (version 1.3.0). We
use the methods’ names provided in the package to refer to the various methods
we use here. We run our code on a Intel Xeon Platinum 8358 at 2.60GHz.

####  4.1.2 Synthetic Data

We test the Laplacian solvers on a number of synthetic networks, which allow
us to vary both the number of nodes $|V|$ and the graph’s density by changing
the average degree. We use different models because each of them can reproduce
some of the common properties we find in real world networks. Specifically, we
use:

  * •

Erdős–Rényi (ER): this is a $G_{n,m}$ model where we create a graph with
$|V|=n$ and $|E|=m$. The edges are assigned uniformly at random by extracting
two random node ids. This network model reproduces well the small world
feature of real networks – the resulting networks have small diameters [11].

  * •

Barabási-Albert (BA): we grow this network by adding one node at a time. Each
node connects to $k$ already existing nodes, with $k$ being a parameter.
Existing nodes receive new connections with a probability directly
proportional to their degree. This network reproduces well both small world
property and broad degree distributions [4].

  * •

Watts-Strogatz (WS): this network starts from a circle graph where nodes are
connected to all of their $k$ closest neighbors. Then, each edge is rewired
randomly with probability $p$, with $k$ and $p$ as parameters. This model
reproduces the high clustering and small world features [46].

  * •

Stochastic Blockmodel (SBM): in this model, as an input, the user partitions
nodes into groups and specifies two probabilities. $p_{in}$ determines the
probability of connecting to a node inside the same group, and $p_{out}$
regulates the connections to nodes outside the group. This model can generate
network communities [23].

For all models, we make sure to directly compare networks with roughly the
same number of edges.

####  4.1.3 Real World Data

For our applications section (Section 5) we also make use of real world data,
to showcase the usefulness of GE – and, as a consequence, the need for
efficient ways to estimate it. Specifically we use:

  * •

Section 5.1 (US Congress): networks from the roll call votes in the House of
Representatives – one network per congress edition –, using data from
Voteview.com [31]. Each node is a representative and they are connected if the
two representatives have co-voted on bills more often than the average same-
party pair. The procedure to build these networks has been used multiple times
in the literature [1, 22].

  * •

Section 5.2 (Various): networks that come from a variety of papers, retrieved
via the network catalogues SNAP [30] and Netzschleuder [32].

We use small networks in Section 5.1 because we want to show how accurate the
Laplacians solvers can be in quantifying the GE values against the exact
result obtained via SVD – thus we need to be able to run SVD. The larger
networks in Section 5.2 are used to showcase the possibilities opened by the
Laplacian solvers that are not available to the exact solutions via the
Laplacian pseudoinverse.

###  4.2 By Network Size

In this section we test the effect of the size of the network on the running
time and memory consumption of the Laplacian solvers against the baseline
using the pseudoinversion via SVD. We split the size test first by increasing
the number of nodes while keeping the density of the network constant, and
then by keeping the number of nodes fixed but increasing the network density.

####  4.2.1 Runtimes ($|V|$)

For the runtimes, we exclude outlier runs which took more than twice the
average runtime. This is done to exclude compilation time from the estimate –
this issue only affects very small input sizes where compilation could take
significantly longer than running time. All plots report average runtimes over
ten independent runs. The exception is Baseline, for which we make a single
run for $|V|=10^{4}$ and we do not run for larger $|V|$ at all, due to its
excessively long runtimes.

(a) Erdős–Rényi

(b) Barabási-Albert

(c) Watts-Strogatz

(d) Stochastic Blockmodel

Figure 1: The running time (y axis) against $|V|$ (x axis) for all the methods
(line color) on different synthetic networks.

We start by analyzing the runtimes for increasing number of nodes. Figure 1
reports the results. The first evident result is that any Laplacian solver has
both a constant running time advantage and a better asymptotic complexity.
Even for tiny networks of $100$ nodes, regardless of the network topology, all
Laplacian solvers are at least one order of magnitude faster than the
baseline. From these plots we can infer that the empirical asymptotic
complexity of the baseline is $\sim\mathcal{O}(|V|^{2.6})$. For the Laplacian
solvers the exact combination of solver and topology matters, but in general
the empirical asymptotic complexity is between $\mathcal{O}(|V|^{1.2})$ and
$\mathcal{O}(|V|^{1.4})$, in all cases decisively below
$\mathcal{O}(|V|^{2})$.

The practical result is that the baseline takes at least one order of
magnitude more time to compute a $|V|=10^{4}$ network than any Laplacian
solver takes for a network two orders of magnitude larger.

(a) Runtime

(b) Memory

Figure 2: Time and memory consumption (y axis) against $|V|$ (x axis) for all
synthetic networks (line color) for the CG Laplacian solver.

Among the Laplacian solvers there is no clear overall winner. CG is the
fastest for the Erdős–Rényi and SBM topologies, but it ties with ApproxChol
for the Barabási-Albert model, while ApproxChol is also fastest for Watts-
Strogatz. The topology in general has different effects on different solvers.
Picking CG as an example, Figure 2(a) shows that indeed CG runs slower for
Watts-Strogatz than it does for all other topologies. Other solvers also
experience different strengths and weaknesses depending on the topology – not
shown here for space issues.

####  4.2.2 Runtimes (Density)

Efficient Laplacian solvers exploit, among other things, the sparseness of a
graph. It is interesting to investigate what happens to the runtime when the
graphs we investigate get denser and denser. In this experiment, we fix
$|V|=10,000$, and we increase the average degree of the network from $1$ to
$64$. The vast majority of real world networks have low average degrees in the
single digit realm [17], thus this domain covers the most realistic scenarios.
Also in this case we report the average of ten runs, taking out outliers and
ignoring compilation time.

(a) Erdős–Rényi

(b) Barabási-Albert

(c) Watts-Strogatz

(d) Stochastic Blockmodel

Figure 3: The running time (y axis) against average degree (x axis) for all
the methods (line color) on different synthetic networks.

Figure 3 shows the results. Since the baseline works with dense matrices
anyway, there is no real effect of density on its running time, which is
roughly constant. Most Laplacian solvers have longer runtimes for denser
networks – as expected. All Laplacian solvers are orders of magnitude faster
than the baseline, and thus represent a significant advantage.

CG shows a peculiar pattern: it takes longer for extremely sparse networks –
with average degree close to one – then gets faster and faster for middle
values of average degree between four and eight. After this, the runtimes
increase with density as expected. This pattern is consistent, independently
from the topology of the network. It seems that, for extremely sparse networks
with average degree lower than four, CG might not be the best choice. For
denser networks, however, CG can be one or two orders of magnitude faster than
the other Laplacian solvers.

####  4.2.3 Memory

For the memory test we show only a single run per method, due to limitations
in memory benchmarking. However, memory consumption should not be variable
across runs and the results of a single run are still indicative of the
overall trends. We also run a single Laplacian solver, CG, because the memory
consumption for all solvers is indistinguishable in all cases.

(a) Erdős–Rényi

(b) Barabási-Albert

(c) Watts-Strogatz

(d) Stochastic Blockmodel

Figure 4: Memory consumption (y axis) against $|V|$ (x axis) for all the
methods (line color) on different synthetic networks.

From Figure 4 we can see that there is a basic memory consumption coming from
simply running the program. For $|V|=10^{4}$, the Laplacian solvers do not add
any memory consumption to this basic rate. However, the baseline needs to
shift from sparse to dense matrix representations to calculate the
pseudoinverse of the Laplacian. This means that its memory consumption is
already between $5$ and $6$GB in our implementation even for these small
networks. If we exclude the warm-up phase for $|V|<10^{3}$, the memory
consumption of the baseline scales exponentially.

This is not true for Laplacian solvers, here represented by CG. The total
memory consumption at $|V|=10^{4}$ is still in the neighborhood of the basic
cost of running the program. Even for $|V|=10^{6}$, the memory required is
below $2$GB in all but one case. Asymptotically, the best function describing
the growth in memory consumption by CG is linear, not exponential. Figure 2(b)
does not show any significant difference in memory consumption for CG
depending on the topology of the network.

##  5 Applications

###  5.1 Polarization

The GE measure can be used to estimate polarization on social media, or any
networked system where we have information about the opinions of the nodes
[22]. This is done by calculating the distance between the vector recording
the opinions of nodes on one side of the spectrum – e.g. Democrats – with the
one recording the opinions of the nodes on the other side of the spectrum –
e.g. Republicans.

Method | 85th | 105th | 113th
---|---|---|---
Baseline | 1.006 | 3.664 | 8.330
ApproxChol | $2.1e^{-14}$ | $2.1e^{-14}$ | $1.3e^{-13}$
Aug Tree | $6.9e^{-9}$ | $1.1e^{-14}$ | $5.0e^{-14}$
KMP | $4.4e^{-16}$ | $2.7e^{-15}$ | $1.1e^{-13}$
CG | $4.9e^{-10}$ | $2.7e^{-15}$ | $2.1e^{-13}$
Table 1: The polarization scores for three US Congress networks (top row) and
the difference between exact and approximate solution using a specific
Laplacian solver (bottom four rows).

For this task we use the Congress networks described in Section 4.1.3.
Specifically, we focus on the 85th, 105th, and 113th Congress, since they show
the lowest, average, and highest value of polarization, respectively. Table 1
shows the result. First, the Baseline method confirms the differences in
scores between the three networks. Then we show how the four Laplacian solvers
estimate the level of polarization to be practically identical to the exact
one we compute via the Baseline. The largest error is in the neighborhood of
$10^{-8}$, which is far below the level of precision required for such an
analysis.

###  5.2 Various

We look at a variety of networks which would all benefit from a GE analysis,
in increasing size to show the speedup of the Laplacian solvers in real world
scenarios. We simplify all networks to an undirected, unweighted, simple graph
version, even if the original network was either directed, weighted, or
multilayer. All runtimes exclude I/O operations and preprocessing, so they
ignore the time it takes to read the graph from disk. Below we briefly explain
what the node vectors are in each case.

  * •

Hiring: we can calculate the distance between the region in which a university
is located, by analyzing the hiring patterns.

  * •

EUAir: we can calculate the distance between airlines depending on which
airports they serve.

  * •

EUCore: we have communities based on email exchange, and GE could tell the
distance between community pairs.

  * •

Open Flights: we can calculate the distance between countries based on how the
airlines connect their airports.

  * •

LastFm: we can calculate the distance between countries – a metadata we have
about the users – based on their friendships on the platform.

  * •

Wiki RFA: we can calculate the distance between admins and non-admins in the
voting network.

  * •

Fly Brain: we can calculate the distance between neuron types in the neural
network.

  * •

Twitter15m: we can measure the distance between two hashtags in the user
network.

  * •

Patents: we can measure the distance between patent categories in the patent
citation patterns.

  * •

DBpedia: we do not have node metadata, so we calculate distances between
random vectors, but this network could be used, e.g., to calculate distances
between different page categories in the encyclopedia, whose pages are
connected by hyperlinks.

Network | $|V|$ | $|E|$ | Dens | ApproxChol (s) | Baseline (s) | Ref
---|---|---|---|---|---|---
Hiring | 145 | 2,266 | 0.2170 | 0.0023 | 0.0040 | [6]
EUAir | 450 | 2,953 | 0.0292 | 0.0011 | 0.0454 | [5]
EUCore | 1,005 | 16,064 | 0.0318 | 0.0068 | 0.4496 | [29]
Open Flights | 3,214 | 18,858 | 0.0036 | 0.0079 | 13.623 | [32]
LastFm | 7,624 | 27,806 | 0.0009 | 0.0149 | 244.20 | [34]
Wiki RFA | 11,381 | 194,592 | 0.0030 | 0.0976 | 853.00 | [48]
Fly Brain | 21,739 | 2,897,925 | 0.0122 | 2.6151 | 6181.3 | [49]
Twitter15m | 87,569 | 4,708,274 | 0.0012 | 4.3299 |  | [18]
Patents | 3,774,768 | 16,518,947 | 2.31$e^{-6}$ | 59.311 |  | [20]
DBpedia | 18,268,992 | 136,537,566 | 8.18$e^{-7}$ | 247.10 |  | [2]
Table 2: The runtimes of the ApproxChol solver against the exact solution in
number of seconds for a collection of networks of different sizes (in number
of nodes $|V|$ and edges $|E|$). We terminate the process after one hour, thus
we do not report runtimes longer than that.

(a) ApproxChol

(b) Baseline

Figure 5: Runtime (y axis) on real networks by number of nodes (x axis).

Table 2 reports the running times. These are also summarized in Figure 5. For
comparison purposes, we estimate the scaling of the two methods with a power
relation with the number of nodes. The best function approximating the runtime
of ApproxChol is $\mathcal{O}(|V|^{1.12})$ (Figure 5(a)). On the other hand,
the best function approximating the runtime of the exact SVD-based solution is
$\mathcal{O}(|V|^{2.91})$ (Figure 5(b)).

However, it would be more appropriate to estimate the scaling of the Laplacian
solver with the number of edges. This is is because their advantage becomes
less and less relevant the more the network is dense. Note the difference in
runtimes, e.g., in Hiring and EUAir. Notwithstanding the fact that Hiring has
fewer nodes and fewer edges, it is much more dense than EUAir (21% dense vs 3%
dense) and thus the Laplacian solvers actually take longer to run on this
smaller network. On the other hand, it is remarkable that the Laplacian solver
can process the DBpedia network (18M nodes) in the same time it takes the
baseline to process LastFm (7.6k nodes).

##  6 Conclusions

In this paper we showed that using Laplacian solvers will bring massive
speedups in the calculation of the Generalized Euclidean measure and other
related measures in the Node Vector Distance class of problems. The speedup is
relative to calculating an exact solution via the pseudoinverse of the
Laplacian. Since Laplacian solvers scale with the number of edges, these
speedups are more noticeable for sparse networks. Besides an improved time
efficiency, these methods also require fewer resources in terms of memory,
since the process to obtain the pseudoinverse of the Laplacian involves using
dense matrices, while all Laplacian solvers work with sparse structures.

We failed to notice significant differences between different Laplacian
solvers in synthetic networks. As the network grows in number of nodes, they
all increase their runtimes approximately at the same rate. The only potential
difference comes when we densify the network. The CG solver is the slowest for
very sparse networks, but it scales better as the network becomes denser and
denser.

This paper can be used as an argument to use Laplacian solvers to efficiently
solve GE and related NVD problems.

## References

  * [1] Clio Andris, David Lee, Marcus J Hamilton, Mauro Martino, Christian E Gunning, and John Armistead Selden.  The rise of partisanship and super-cooperators in the us house of representatives.  PloS one, 10(4):e0123507, 2015.
  * [2] Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives.  Dbpedia: A nucleus for a web of open data.  In The semantic web, pages 722–735. Springer, 2007.
  * [3] Paolo Bajardi, Chiara Poletto, Jose J Ramasco, Michele Tizzoni, Vittoria Colizza, and Alessandro Vespignani.  Human mobility networks, travel restrictions, and the global spread of 2009 h1n1 pandemic.  PloS one, 6(1):e16591, 2011.
  * [4] Albert-László Barabási and Réka Albert.  Emergence of scaling in random networks.  science, 286(5439):509–512, 1999.
  * [5] Alessio Cardillo, Jesús Gómez-Gardenes, Massimiliano Zanin, Miguel Romance, David Papo, Francisco del Pozo, and Stefano Boccaletti.  Emergence of network features from multiplexity.  Scientific reports, 3(1):1–6, 2013.
  * [6] Aaron Clauset, Samuel Arbesman, and Daniel B Larremore.  Systematic inequality and hierarchy in faculty hiring networks.  Science advances, 1(1):e1400005, 2015.
  * [7] Michael B Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B Rao, Aaron Sidford, and Adrian Vladu.  Almost-linear-time algorithms for markov chains and new spectral primitives for directed graphs.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 410–419, 2017.
  * [8] Michael B Cohen, Jonathan Kelner, John Peebles, Richard Peng, Aaron Sidford, and Adrian Vladu.  Faster algorithms for computing the stationary distribution, simulating random walks, and more.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 583–592. IEEE, 2016.
  * [9] Ronald R Coifman and Stéphane Lafon.  Diffusion maps.  Applied and computational harmonic analysis, 21(1):5–30, 2006.
  * [10] Michele Coscia.  Generalized euclidean measure to estimate network distances.  In Proceedings of the International AAAI Conference on Web and Social Media, volume 14, pages 119–129, 2020.
  * [11] Michele Coscia.  The atlas for the aspiring network scientist.  arXiv preprint arXiv:2101.00863, 2021.
  * [12] Michele Coscia.  Pearson correlations on complex networks.  Journal of Complex Networks, 9(6):cnab036, 2021.
  * [13] Michele Coscia, Andres Gomez-Lievano, James Mcnerney, and Frank Neffke.  The node vector distance problem in complex networks.  ACM Computing Surveys (CSUR), 53(6):1–27, 2020.
  * [14] Michele Coscia and Clara Vandeweerdt.  Posts on central websites need less originality to be noticed.  Scientific reports, 12(1):1–10, 2022.
  * [15] Karel Devriendt, Samuel Martin-Gutierrez, and Renaud Lambiotte.  Variance and covariance of distributions on graphs.  SIAM Review, 64(2):343–359, 2022.
  * [16] Adrien Friggeri, Lada Adamic, Dean Eckles, and Justin Cheng.  Rumor cascades.  In proceedings of the international AAAI conference on web and social media, volume 8, pages 101–110, 2014.
  * [17] Amir Ghasemian, Homa Hosseinmardi, Aram Galstyan, Edoardo M Airoldi, and Aaron Clauset.  Stacking models for nearly optimal link prediction in complex networks.  Proceedings of the National Academy of Sciences, 117(38):23393–23400, 2020.
  * [18] Sandra González-Bailón, Javier Borge-Holthoefer, Alejandro Rivero, and Yamir Moreno.  The dynamics of protest recruitment through an online network.  Scientific reports, 1(1):1–7, 2011.
  * [19] Mark Granovetter.  Threshold models of collective behavior.  American journal of sociology, 83(6):1420–1443, 1978.
  * [20] Bronwyn H Hall, Adam B Jaffe, and Manuel Trajtenberg.  The nber patent citation data file: Lessons, insights and methodological tools, 2001.
  * [21] Ricardo Hausmann, César A Hidalgo, Sebastián Bustos, Michele Coscia, and Alexander Simoes.  The atlas of economic complexity: Mapping paths to prosperity.  Mit Press, 2014.
  * [22] Marilena Hohmann, Karel Devriendt, and Michele Coscia.  Quantifying ideological polarization on a network using generalized euclidean distance.  Science Advances, 9(9):eabq2044, 2023.
  * [23] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt.  Stochastic blockmodels: First steps.  Social networks, 5(2):109–137, 1983.
  * [24] Ioannis Koutis, Gary L Miller, and Richard Peng.  A nearly-m log n time solver for sdd linear systems.  In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 590–598. IEEE, 2011.
  * [25] Ioannis Koutis, Gary L Miller, and Richard Peng.  Approaching optimality for solving sdd linear systems.  SIAM Journal on Computing, 43(1):337–354, 2014.
  * [26] Moritz UG Kraemer, Chia-Hung Yang, Bernardo Gutierrez, Chieh-Hsi Wu, Brennan Klein, David M Pigott, Open COVID-19 Data Working Group†, Louis Du Plessis, Nuno R Faria, Ruoran Li, et al.  The effect of human mobility and control measures on the covid-19 epidemic in china.  Science, 368(6490):493–497, 2020.
  * [27] Rasmus Kyng and Sushant Sachdeva.  Approximate gaussian elimination for laplacians-fast, sparse, and simple.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 573–582. IEEE, 2016.
  * [28] Jure Leskovec, Lada A Adamic, and Bernardo A Huberman.  The dynamics of viral marketing.  ACM Transactions on the Web (TWEB), 1(1):5–es, 2007.
  * [29] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos.  Graph evolution: Densification and shrinking diameters.  ACM transactions on Knowledge Discovery from Data (TKDD), 1(1):2–es, 2007.
  * [30] Jure Leskovec and Andrej Krevl.  SNAP Datasets: Stanford large network dataset collection.  http://snap.stanford.edu/data, June 2014.
  * [31] Jeffrey B Lewis, Keith Poole, Howard Rosenthal, Adam Boche, Aaron Rudkin, and Luke Sonnet.  Voteview: Congressional roll-call votes database.  https://voteview. com/ (accessed 25 February 2022), 2019.
  * [32] Tiago P Peixoto.  The netzschleuder network catalogue and repository, 2020.
  * [33] Ofir Pele and Michael Werman.  Fast and robust earth mover’s distances.  In 2009 IEEE 12th international conference on computer vision, pages 460–467. IEEE, 2009.
  * [34] Benedek Rozemberczki and Rik Sarkar.  Characteristic functions on graphs: Birds of a feather, from statistical descriptors to parametric models.  In Proceedings of the 29th ACM international conference on information & knowledge management, pages 1325–1334, 2020.
  * [35] David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst.  The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains.  IEEE signal processing magazine, 30(3):83–98, 2013.
  * [36] David I Shuman, Benjamin Ricaud, and Pierre Vandergheynst.  Vertex-frequency analysis on graphs.  Applied and Computational Harmonic Analysis, 40(2):260–291, 2016\.
  * [37] Daniel A Spielman and Shang-Hua Teng.  Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems.  In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 81–90, 2004.
  * [38] Daniel A Spielman and Shang-Hua Teng.  Spectral sparsification of graphs.  SIAM Journal on Computing, 40(4):981–1025, 2011.
  * [39] Daniel A Spielman and Shang-Hua Teng.  A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning.  SIAM Journal on computing, 42(1):1–26, 2013.
  * [40] Daniel A Spielman and Shang-Hua Teng.  Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems.  SIAM Journal on Matrix Analysis and Applications, 35(3):835–885, 2014.
  * [41] Andrea Tacchella, Matthieu Cristelli, Guido Caldarelli, Andrea Gabrielli, and Luciano Pietronero.  A new metrics for countries’ fitness and products’ complexity.  Scientific reports, 2(1):1–7, 2012.
  * [42] Alessandro Vespignani, Huaiyu Tian, Christopher Dye, James O Lloyd-Smith, Rosalind M Eggo, Munik Shrestha, Samuel V Scarpino, Bernardo Gutierrez, Moritz UG Kraemer, Joseph Wu, et al.  Modelling covid-19.  Nature Reviews Physics, 2(6):279–281, 2020.
  * [43] Nisheeth K Vishnoi et al.  Lx= b.  Foundations and Trends® in Theoretical Computer Science, 8(1–2):1–141, 2013.
  * [44] Ulrike Von Luxburg.  A tutorial on spectral clustering.  Statistics and computing, 17:395–416, 2007.
  * [45] Duncan J Watts, Jonah Peretti, and Michael Frumin.  Viral marketing for the real world.  Harvard Business School Pub. Boston, 2007.
  * [46] Duncan J Watts and Steven H Strogatz.  Collective dynamics of ‘small-world’networks.  nature, 393(6684):440–442, 1998.
  * [47] Lilian Weng, Filippo Menczer, and Yong-Yeol Ahn.  Predicting successful memes using network and community structure.  In Eighth international AAAI conference on weblogs and social media, 2014.
  * [48] Robert West, Hristo S Paskov, Jure Leskovec, and Christopher Potts.  Exploiting social network structure for person-to-person sentiment analysis.  Transactions of the Association for Computational Linguistics, 2:297–310, 2014.
  * [49] C Shan Xu, Michal Januszewski, Zhiyuan Lu, Shin-ya Takemura, Kenneth J Hayworth, Gary Huang, Kazunori Shinomiya, Jeremy Maitin-Shepard, David Ackerman, Stuart Berg, et al.  A connectome of the adult drosophila central brain.  BioRxiv, 2020.
  * [50] Wei Zhao, Maxime Peyrard, Fei Liu, Yang Gao, Christian M Meyer, and Steffen Eger.  Moverscore: Text generation evaluating with contextualized embeddings and earth mover distance.  arXiv preprint arXiv:1909.02622, 2019.