11institutetext: Ludwig Maximilian University of Munich, Germany
22institutetext: IWR, Ruprecht Karl University of Heidelberg, Germany
22email<EMAIL_ADDRESS>
https://github.com/matthias-wright/art-fid

# ArtFID: Quantitative Evaluation of Neural Style Transfer

Matthias Wright 11 Björn Ommer 1122

###### Abstract

The field of neural style transfer has experienced a surge of research
exploring different avenues ranging from optimization-based approaches and
feed-forward models to meta-learning methods. The developed techniques have
not just progressed the field of style transfer, but also led to breakthroughs
in other areas of computer vision, such as all of visual synthesis. However,
whereas quantitative evaluation and benchmarking have become pillars of
computer vision research, the reproducible, quantitative assessment of style
transfer models is still lacking. Even in comparison to other fields of visual
synthesis, where widely used metrics exist, the quantitative evaluation of
style transfer is still lagging behind. To support the automatic comparison of
different style transfer approaches and to study their respective strengths
and weaknesses, the field would greatly benefit from a quantitative
measurement of stylization performance. Therefore, we propose a method to
complement the currently mostly qualitative evaluation schemes. We provide
extensive evaluations and a large-scale user study to show that the proposed
metric strongly coincides with human judgment.

###### Keywords:

neural style transfer image synthesis quantitative evaluation.

##  1 Introduction

Style transfer and texture transfer have been researched at least since the
early 2000s [25, 20]. In 2016, Gatys et al. proposed a novel method for style
transfer based on the features of a pretrained convolutional neural network.
The recent years have seen a surge of research exploring different avenues
including, but not limited to, optimization-based approaches [23, 40, 36, 41],
feed-forward models [33, 72], universal feed-forward models [30, 46, 7, 50,
57, 32, 65, 44], ultra-resolution techniques [75, 11], meta-learning
approaches [64, 85], and video style transfer [60, 10, 29, 6].
The developed techniques have not just progressed the field of style transfer,
but also led to breakthroughs in other areas of computer vision, such as
visual synthesis. For example, the perceptual loss [23, 33] has been applied
to tasks ranging from photographic image synthesis [9] to motion transfer [4],
the generator architecture employed by Johnson et al. [33] has been used to
synthesize photo-realistic images from semantic label maps [76] or for
unpaired image-to-image translation [88], and the AdaIN layer [30] was a key
ingredient for the StyleGAN generator [35] that produced state-of-the-art
results in unconditional generative image modeling.
In contrast to other areas of computer vision research such as classification
or even natural image synthesis, where quantitative evaluation and
benchmarking are already common practice, quantitative assessment of style
transfer models is still lacking.
Currently, the most common method for evaluating these models is a qualitative
comparison for a few, commonly used, style and content images. This is
generally useful for an initial impression, however, the performance of style
transfer models greatly varies across different style and content images. For
example, Fig. 1 shows stylized images from AdaIN [30] and WCT [46] for two
different style/content pairs. One can argue that AdaIN [30] outperforms WCT
[46] for the first pair and vice versa for the second pair.
Some papers provide a quantitative comparison using measurements for speed,
memory, or control [11, 30, 64, 54, 46, 72, 85, 28, 12, 49, 79, 82, 51, 13].
These measurements are very helpful to highlight a model’s performance with
respect to a specific property such as speed, but are generally not intended
to measure stylization performance. A few works [28, 37, 52, 82] also employ
classical perceptual metrics such as PSNR or SSIM [77], however, these metrics
are generally not consistent with human perception [86].
Sanakoyeu et al. [62] proposed the Deception rate to measure the quality of
stylized images. It is the fraction of stylized images that an artist
classification network has assigned to the artist, whose artwork has been used
for stylization. The deception rate can be useful in some cases but also
suffers from certain drawbacks and is not widely used as a result. First, it
only works for style images belonging to an artist for which the artist
classifier network has been trained and thus cannot be used for arbitrary
styles. And second, it completely disregards content preservation.
In the absence of a suitable quantitative measurement of stylization
performance, many authors have turned to human evaluation studies [40, 54, 28,
5, 57, 62, 50, 41, 75, 37, 8, 81, 80, 7, 82, 16, 83, 15, 43], where users are
asked to compare stylized images of different models and specify their
preference. These studies give better insights into a model’s stylization
performance in comparison to other methods, especially when conducted with
many users and for many different style and content images. Nonetheless, there
are cases where a user study is not feasible. Large-scale crowdsourcing can be
expensive and may not be an option for researchers with limited funding.
Furthermore, there are cases where a quantitative measurement is simply more
suitable. As an example, consider the closely-related field of image
synthesis, where quantitative measurements for image quality are used, not
just for evaluation, but also as a core part of the approach. Recent examples
include work by Mokady et al. [56], where Fréchet Inception Distance (FID)
[26] and Learned Perceptual Image Patch Similarity (LPIPS) [86] measurements
are employed for self-filtering a collection of images, work by Karras et al.
[34] that use the FID to detect GAN [24] overfitting, or a large-scale GAN
study by Lucic et al. [53] that utilize the FID to compare the sensitivity of
different GAN models to hyper-parameters. A quantitative measurement of
stylization performance would facilitate similar studies to further analyze
and improve style transfer methods. In this work, we propose a method that
fills this role and call it ArtFID. Our goal is not to replace the current
evaluation techniques, but rather to complement them.
Stylization performance is mostly determined by two factors: content
preservation and style matching. Content preservation refers to the extent to
which the semantic content from the content images is preserved in the
stylized images. Style matching refers to the extent to which the style of the
generated images resembles the style of the target style images. Measuring
content preservation is straightforward using the well-established perceptual
loss [23, 33], CLIP loss [59], or LPIPS metric [86]. However, measuring style
matching is more challenging because it confronts us with the question ”what
is style?”, a question that has been debated relentlessly by art historians
[42, 1, 73, 55, 63]. However, a commonly used definition is that style is the
”distinctive manner which permits the grouping of works into related
categories” [21]. This definition gives rise to a representation learning
approach, where artworks are classified into categories by a neural network to
obtain representations that reflect their stylistic similarity. To this end,
we collect a large-scale dataset of artworks, labeled by artist and stylistic
period. We make use of both labels by employing an architecture with two
classification heads. Having obtained the image representations in the form of
neural network features, we return to the issue of measuring style matching.
As shown by Li et al. [45], the task of style transfer corresponds to aligning
feature distributions of neural networks. To measure style matching, we can
thus measure how well the feature distribution of style images matches the
feature distribution of stylized images. Following the work by Heusel et al.
[26], we measure the distance between these two feature distributions with
respect to the first two moments using the Fréchet distance [22, 18].
Our contributions are as follows:

  * •

We propose a method for quantitatively evaluating style transfer models with
respect to stylization performance that strongly coincides with human
judgment.

  * •

We introduce a large-scale dataset, containing 250k images of labeled
artworks.

  * •

We provide extensive evaluations and a large-scale human evaluation study to
support our claims.

Figure 1: AdaIN [30] (arguably) performs better on the top style/content pair,
while WCT [46] (arguably) performs better on the bottom style/content pair.

##  2 Related Work

#### Style Transfer

Research in the fields of style transfer and texture transfer goes back to the
early 2000s. Efros and Freeman [20] proposed texture synthesis and transfer
using image quilting and Hertzmann et al. [25] proposed image analogies based
on a simple multi-scale autoregression. Other work in this area includes a
method for synthesizing directional textures [74].
In 2016, Gatys et al. [23] proposed an iterative optimization algorithm for
style transfer that leverages the representations learned by convolutional
neural networks. In the following, Johnson et al. [33] and Ulyanov et al. [72]
used feed-forward networks to approximate the optimization problem formulated
by Gatys et al. [23] for a specific style image.
In order to use mutliple styles with a single network, Dumoulin et al. [19]
proposed conditional instance normalization. Huang and Belongie [30] proposed
the first method for arbitrary style transfer, using adaptive instance
normalization. Li et al. [46] introduced another arbitrary style transfer
model, based on whitening and colouring transformations.
Li et al. [45] provided insights into the mechanics of style transfer by
proving that matching the Gram matrices of feature maps is equivalent to
minimizing the Maximum Mean Discrepancy with the second order polynomial
kernel.
Li et al. [47] proposed a closed-form solution for photorealistic stylization
that is based on the aforementioned whitening and colouring transformations.
Sheng et al. [65] introduced a method that semantically aligns content
features to trade off generalization and efficiency and Li et al. [44]
proposed a linear transformation for image and video style transfer.
Shen et al. [64] and Zhang et al. [85] employed meta-learning approaches to
handle the trade-off between speed, flexibility, and quality, and Svoboda et
al. [68] used graph neural networks to recombine style and content in latent
space. Another line of research used attention mechanisms to integrate local
style patterns and align content and style manifolds [57, 16, 50, 54, 32].
Recent work includes exemplar-based portrait style transfer [83], online
motion style transfer [71], transformer-based style transfer [15], lightweight
photorealistic style transfer [13], style transfer for scene reconstruction
[27], industrial style transfer [82], thumbnail instance normalization for
ultra-resolution style transfer [11], style transfer based on text
descriptions [43], internal-external style transfer with two contrastive
losses [7], reversible neural flows for unbiased stylization [2], and a
unified architecture for domain-aware style transfer [28].

#### Inception Score

Salimans et al. [61] proposed the Inception score, an evaluation metric for
generated images that correlates with human judgment. To compute the Inception
score, the Inception network [69] is used to compare the conditional label
distribution to the marginal distribution of the generated images. A downside
of the Inception score is that the statistics of the generated images are not
compared to the statistics of real images [26].

#### Fréchet Inception Distance

Heusel et al. [26] proposed the Fréchet Inception Distance (FID) that improves
the Inception score by computing the Fréchet distance [22, 18] between the
Gaussian distribution of Inception features of generated images and the
Gaussian distribution of Inception features of real images.

##  3 Approach

###  3.1 ArtFID

As stated before, the stylization quality is determined by content
preservation and style matching. In contrast to previous work, we measure both
factors and combine them to form a quantitative metric.
Let $X_{c}$ denote the set of content images, $X_{s}$ the set of style images,
and $X_{g}$ the set of stylized images, generated from a particular style
transfer model. To measure content preservation for a particular stylized
image, we compute a distance $d(X_{c}^{(i)},X_{g}^{(i)})$ between the content
image $X_{c}^{(i)}$ and the corresponding stylized image $X_{g}^{(i)}$.
Possible choices for $d(\cdot)$ are the VGG perceptual loss [23, 33], the CLIP
loss [59], or the LPIPS metric [86]. We select LPIPS and show in Sec. 4.5 that
it slightly outperforms the alternatives.
Measuring the content preservation for a style transfer model then simply
corresponds to evaluating $d(X_{c}^{(i)},X_{g}^{(i)})$ for a large batch of
stylized images and taking the mean.
As stated above, to measure style matching for a model, we first learn
suitable image representations by training a classifier on a large-scale
artwork dataset (Sec. 3.3). For the classifier, we use the Inception network
[69]. The architecture is modified by using two classification heads instead
of one. In doing so, we are able to harness the information from both the
artist labels as well as the labels for the stylistic period that are present
in the dataset. For more information about the classifier training, see Sec.
3.4. The image representations are the Inception features from the last layer
before the classifier heads. These features are computed for both the style
images $X_{s}$ and the stylized images $X_{g}$. To measure style matching
between the style images $X_{s}$ and the stylized images $X_{g}$, we measure
the distance between these two feature distributions. This is motivated by
work from Li et al. [45] that shows that the task of style transfer
corresponds to aligning feature distributions of deep neural networks. Similar
to Heusel et al. [26], we measure the distance between these two feature
distributions with respect to the first two moments using the Fréchet distance
[22, 18]

$\textrm{FID}(X_{s},X_{g})=||\mu_{s}-\mu_{g}||_{2}^{2}+\textrm{Tr}(\Sigma_{s}+\Sigma_{g}-2(\Sigma_{s}\Sigma_{g})^{\frac{1}{2}}),$
(1)

where $(\mu_{s},\Sigma_{s})$ and $(\mu_{g},\Sigma_{g})$ are the mean and
covariance of the Inception features of the style images $X_{s}$ and the
stylized images $X_{g}$, respectively.
Having obtained a measure for content preservation and a measure for style
matching, we combine these measures to form the ArtFID, formulated as follows

$\textrm{ArtFID}(X_{g},X_{c},X_{s})=\Bigg{(}1+\frac{1}{N}\sum\limits_{i=1}^{N}d(X_{c}^{(i)},X_{g}^{(i)})\Bigg{)}\cdot\Bigg{(}1+\textrm{FID}(X_{s},X_{g})\Bigg{)}$
(2)

Ones are added to both factors to avoid a degenerate minimum when
$X_{c}=X_{g}$ or $X_{s}=X_{g}$. The measures are combined to ensure that only
models that perform well on both content preservation and style matching
achieve a low ArtFID score. Multiplication lends itself well to this purpose.
We also tested the addition operation but the effect on the overall ranking
was negligible.

###  3.2 Unbiased ArtFID Computation

Chong and Forsyth [14] showed that the FID computed with a finite number of
samples $N$, denoted FIDN, is biased. This bias in FIDN vanishes when
$N\rightarrow\infty$. The authors [14] propose a method for computing
$\overline{\textrm{FID}}_{\infty}$, an unbiased estimate of
$\textrm{FID}_{\infty}$, using $N$ samples. The FID is computed $K$ times,
each time with a different number of samples $M_{1},...,M_{K}$. The
$M_{1},...,M_{K}$ are evenly spaced numbers over the interval $[5000,N]$. A
linear regression model is then fitted to the points
$(1/M_{1},\textrm{FID}_{M_{1}}),...,(1/M_{K},\textrm{FID}_{M_{K}})$. To obtain
$\overline{\textrm{FID}}_{\infty}$, the linear regression model is evaluated
at $0$. For an in-depth analysis, we refer to the work of Chong and Forsyth
[14].
We use $\overline{\textrm{FID}}_{\infty}$ for computing the ArtFID and denote
it as ArtFID∞. Tab. 2 shows that it performs slightly better than the biased
ArtFID.

###  3.3 Data

The dataset used for training the Inception network consists of 250K images,
labeled by artist and stylistic period. The images were collected from public
datasets (e.g. WikiArt [70]), as well as museum databases and art collections
(e.g. Art UK 111https://artuk.org/). See Sec. 0.A for more details about the
dataset.

###  3.4 Training

We broadly follow the methodology described by Szegedy et al. [69] for
training the Inception network. The classifier head is replaced by two
separate heads, one for each label (artist and stylistic period). We use the
Adam optimizer [38] with a learning rate of $0.0001$ and $\beta=(0.9,0.999)$.
The batch size is set to $64$ and the weight of the auxiliary classifier is
set to $0.3$. See Sec. 0.B for more information about the training and
evaluation.

##  4 Experiments

###  4.1 ArtFID Evaluation

We evaluate the ArtFID with 13 different style transfer methods from the
literature [50, 65, 7, 44, 16, 32, 54, 30, 23, 57, 68, 11, 46], some of which
are well-established, some are recently published, and some are in between.
For each method, we generate stylized images using the same pairs of content
and style images. Content images are sampled from the Places365 dataset [87]
and the COCO dataset [48]. Style images are sampled from the WikiArt dataset
[70] and the BAM dataset [78]. Images are sampled from multiple datasets to
increase the variability of style and content images. Following the
recommendations by Heusel et al. [26], we compute the ArtFID with samples of
50k images. Both style and content images are resized to 512x512, a commonly
used image size for style transfer methods. As proposed by Parmar et al. [58],
we resize style and content images with bicubic interpolation and antialiasing
and save the stylized images using the PNG format.
For each style transfer method, the ArtFID is computed with 5 different
samples containing 50k images each. The results are reported in Tab. 1.

###  4.2 Large-Scale Human Evaluation

In order to test the validity of the ArtFID, we conduct a large-scale human
evaluation study on Amazon Mechanical Turk (AMT). We use the same 13 style
transfer methods as before. Similar to [36, 40], we chose a pairwise
comparison, where the outputs of two methods are compared head-to-head. This
choice is in line with recent work from the field of psychology that provides
evidence that human perceptual decision-making is significantly impaired when
presented with multiple alternatives, rather than just two alternatives [84].
We compare each possible pairing of style transfer methods. For each pairing,
we perform 80 comparisons. Each comparison is voted on by 5 workers and the
winner is decided by majority vote. In total there were 31200 tasks and
workers were rewarded $0.03 for each task. Fig. 2 shows the interface that was
shown to the AMT workers for a particular task.

Figure 2: The interface shown to the ATM workers for the user study.

###  4.3 Correlation with Human Judgment

We evaluate the results of the AMT user study with the widely-used Bradley-
Terry model [3]. Given $m$ entities that are repeatedly compared with each
another in pairs, the Bradley-Terry model yields an overall score $\gamma_{i}$
for each entity $i$ that induces a global ranking of the entities. The model
works under the assumption that if we partition the set of entities into two
non-empty subsets, some entity in the first subset is compared to some entity
in the second subset at least once [31]. This requirement is easily satisfied
by comparing each entity with all the other entities, as described in Sec.
4.2. We can then estimate the scores $\gamma_{1},...,\gamma_{m}$ using the
log-likelihood of the Bradley-Terry model

$l(\gamma_{1},...,\gamma_{m})=\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}[w_{ij}\log(\gamma_{i})-w_{ij}\log(\gamma_{i}+\gamma_{j})],$
(3)

where $w_{ij}$ denotes the number of times that entity $i$ was preferred over
entity $j$, and we assume that $w_{ii}=0$ and $\sum_{i}\gamma_{i}=1$ [31].
There exists a simple iterative algorithm that yields a unique maximum of Eq.
3. See Sec. 0.C for an outline of the algorithm and [31] for a study of its
convergence properties.

To measure how well the ArtFID coincides with human judgment, we compute the
correlation between the ranking of style transfer methods obtained from the
human evaluation study and the ranking of the same methods induced by the
ArtFID. A commonly-used measure for this is Spearman’s rank correlation
coefficient (Spearman’s $\rho$) [66, 67], a non-parametric measure of
correlation between rankings. Spearman’s $\rho$ is calculated by replacing the
actual observations with the corresponding ranks in the formula for the
correlation coefficient [39]. Spearman’s $\rho$ is often used as a hypothesis
test to determine if there is a relation between two random variables [17].
For the two-sided test, the null hypothesis is that both random variables are
mutually independent and the alternative hypothesis is that there is either a
positive or a negative correlation. For the one-sided test, the null
hypothesis is that both random variables are mutually independent and the
alternative hypothesis is that there is a positive correlation. We report both
the Spearman’s $\rho$ as well as the $p$-values of the hypothesis tests in
Tab. 2.
To validate our results, we rely not only on our AMT user study but also
consider user studies from other style transfer works. We observe that the
ranking induced by the ArtFID coincides with the majority of user studies
reported in the literature [7, 54, 57, 50, 15, 44, 16]. For example, Chen et
al. [7] report that users preferred IEContraAST [7] over SANet [57], Gatys et
al. [23], LST [44], AdaAttN [50], WCT [46], and Avatar-Net [65]. Luo et al.
[54] report that users preferred PAMA [54] over AdaAttN [50], MANet [16],
SANet [57], MAST [32], and AdaIN [30]. Park and Lee [57] report that users
preferred SANet [57] over Gatys et al. [23], Avatar-Net [65], AdaIN [30], and
WCT [46], Liu et al. [50] report that users preferred AdaAttN [50] over LST
[44], SANet [57], MAST [32], AdaAttN [50], and Avatar-Net [65]. Deng et al.
[16] report that users preferred MANet [16] over SANet [57] and AdaIN [30].

###  4.4 Consistency with Increasing Perturbations

Heusel et al. [26] showed that the FID is consistent with respect to
increasing levels of perturbations that are applied to the images. We verify
that the ArtFID∞ inherits this property. Fig. 3 shows the ArtFID∞ evaluated
using the same image transformations as Heusel et al. [26]. The results for
the ArtFID are comparable.

Figure 3: The ArtFID∞ is consistent with respect to increasing perturbations
applied to the stylized images. The stylized images for this experiment were
generated using the algorithm proposed by Gatys et al. [23]. The line
represents the mean and the shaded area the standard deviation over 4 trials.

###  4.5 Ablations

We perform the following ablation experiments. All results are reported in
Tab. 3.

#### Using ImageNet features for ArtFID computation

Instead of using the modified Inception network trained on the art dataset
(Sec. 3.3), we use the ImageNet features from the original Inception network
to measure style matching. This shows the effectiveness of learning image
representations that reflect stylistic similarity for the style matching task.

#### Training the Inception network only with artist labels

We only use the artist labels when training the Inception network on the art
dataset. This experiment highlights the importance of harnessing the
information from both labels.

#### Training the Inception network only with style labels

We only use the style labels when training the Inception network on the art
dataset. Again, this shows the importance of using the information from both
labels.

#### Using CLIP for measuring content preservation

Instead of using the LPIPS metric [86] to measure content preservation, we use
CLIP [59]. We observe that the LPIPS metric performs slightly better.

#### Using VGG for measuring content preservation

Instead of using the LPIPS metric [86] to measure content preservation, we use
the VGG perceptual loss [23, 33]. Again, the LPIPS metric performs slightly
better.

Table 1: For each style transfer model, we report the user study score, the ArtFID∞ and the Deception rate. Model |  User Study Score $\boldsymbol{\gamma}$ $\uparrow$ |  ArtFID∞ $\downarrow$ |  Deception Rate $\uparrow$
---|---|---|---
PAMA [54] | 0.103 | 9.129 $\pm$ 0.478 | 0.307 $\pm$ 0.001
IEContraAST [7] | 0.105 | 9.495 $\pm$ 0.495 | 0.291 $\pm$ 0.006
URST [11] | 0.092 | 10.846 $\pm$ 0.426 | 0.167 $\pm$ 0.007
AdaAttN [50] | 0.093 | 10.911 $\pm$ 0.356 | 0.108 $\pm$ 0.008
Svoboda et al. [68] | 0.073 | 11.202 $\pm$ 0.766 | 0.127 $\pm$ 0.008
MANet [16] | 0.08 | 12.095 $\pm$ 0.878 | 0.128 $\pm$ 0.007
SANet [57] | 0.077 | 12.373 $\pm$ 0.179 | 0.171 $\pm$ 0.003
Avatar-Net [65] | 0.075 | 13.065 $\pm$ 0.844 | 0.089 $\pm$ 0.007
AdaIN [30] | 0.065 | 13.222 $\pm$ 0.549 | 0.096 $\pm$ 0.007
MAST [32] | 0.067 | 14.937 $\pm$ 0.442 | 0.131 $\pm$ 0.005
LST [44] | 0.066 | 14.941 $\pm$ 1.062 | 0.146 $\pm$ 0.008
Gatys et al. [23] | 0.054 | 15.707 $\pm$ 0.307 | 0.16 $\pm$ 0.008
WCT [46] | 0.05 | 25.495 $\pm$ 0.665 | 0.06 $\pm$ 0.006
Table 2: The correlation between the rankings induced by the different evaluation methods (ArtFID, ArtFID∞, and Deception rate) and the ranking induced by the AMT user study. The ranking from the ArtFID∞ strongly correlates with the ranking from the user study. Metric |  Spearman’s $\boldsymbol{\rho}$ $\uparrow$ |  Two-sided $p$-value $\downarrow$ |  One-sided $p$-value $\downarrow$
---|---|---|---
ArtFID∞ | 0.939 | 1.87e-06 | 9.39e-07
ArtFID | 0.934 | 2.99e-06 | 1.49e-06
Deception Rate | 0.549 | 0.051 | 0.025
Table 3: Ablation experiments. (a) ArtFID as described in Sec. 3, (b) the Inception network is trained on ImageNet instead of the art dataset, (c) the modified Inception network is trained using only the artist labels, (d) the modified Inception network is trained using only the style labels, (d) content preservation is measured using CLIP, and (d) content preservation is measured using the VGG perceptual loss. Configuration |  Spearman’s $\boldsymbol{\rho}$ $\uparrow$ |  Two-sided $p$-value $\downarrow$ |  One-sided $p$-value $\downarrow$
---|---|---|---
ArtFID | ArtFID∞ | ArtFID | ArtFID∞ | ArtFID | ArtFID∞
a Full | 0.934 | 0.939 | 2.99e-06 | 1.87e-06 | 1.49e-06 | 9.39e-07
b ImageNet features | 0.302 | 0.329 | 0.316 | 0.271 | 0.158 | 0.136
c Only artist labels | 0.868 | 0.868 | 0.0001 | 0.0001 | 5.95e-05 | 5.95e-05
d Only style labels | 0.851 | 0.851 | 0.0002 | 0.0002 | 0.0001 | 0.0001
e CLIP for content | 0.917 | 0.917 | 9.91e-06 | 9.91e-06 | 4.95e-06 | 4.95e-06
f VGG for content | 0.928 | 0.923 | 4.61e-06 | 6.85e-06 | 2.30e-06 | 3.42e-06

##  5 Limitations

Obtaining accurate ArtFID measurements is computationally expensive. It
requires evaluating the Inception network and the LPIPS metric for several
thousands of images.

##  6 Conclusion

In this work, we propose a method for quantitatively evaluating style transfer
models. The goal of this work is to complement the currently used evaluation
schemes by promoting the automatic comparison of different style transfer
approaches and to study their respective strengths and weaknesses through in-
depth analyses. A given model is evaluated by measuring content preservation
and style matching across many different style and content images. Content
preservation is quantified using the well-established LPIPS metric. To measure
style matching, we first learn suitable image representations using a large-
scale art dataset. We then measure the distance between the feature
distributions of the stylized images and style images with respect to the
first two moments. We evaluate our method by conducting a user study on Amazon
Mechanical Turk and show that it strongly coincides with human judgment.

##  7 Acknowledgements

This work has been funded by the Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation) within project 421703927.

## References

  * [1] Ackerman, J.S.: A theory of style. The Journal of Aesthetics and Art Criticism 20(3), 227–237 (1962)
  * [2] An, J., Huang, S., Song, Y., Dou, D., Liu, W., Luo, J.: Artflow: Unbiased image style transfer via reversible neural flows. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2021)
  * [3] Bradley, R.A., Terry, M.E.: Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika 39(3/4), 324–345 (1952)
  * [4] Chan, C., Ginosar, S., Zhou, T., Efros, A.A.: Everybody dance now. In: International Conference on Computer Vision (ICCV) (2019)
  * [5] Chandran, P., Zoss, G., Gotardo, P., Gross, M., Bradley, D.: Adaptive convolutions for structure-aware style transfer. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2021)
  * [6] Chen, D., Liao, J., Yuan, L., Yu, N., Hua, G.: Coherent online video style transfer. In: International Conference on Computer Vision (ICCV) (2017)
  * [7] Chen, H., Zhao, L., Wang, Z., Zhang, H., Zuo, Z., Li, A., Xing, W., Lu, D.: Artistic style transfer with internal-external learning and contrastive learning. In: Conference on Neural Information Processing Systems (NeurIPS) (2021)
  * [8] Chen, H., Zhao, L., Zhang, H., Wang, Z., Zuo, Z., Li, A., Xing, W., Lu, D.: Diverse image style transfer via invertible cross-space mapping. In: International Conference on Computer Vision (ICCV) (2021)
  * [9] Chen, Q., Koltun, V.: Photographic image synthesis with cascaded refinement networks. In: International Conference on Computer Vision (ICCV) (2017)
  * [10] Chen, X., Zhang, Y., Wang, Y., Shu, H., Xu, C., Xu, C.: Optical flow distillation: Towards efficient and stable video style transfer. European Conference on Computer Vision (ECCV) (2020)
  * [11] Chen, Z., Wang, W., Xie, E., Lu, T., Luo, P.: Towards ultra-resolution neural style transfer via thumbnail instance normalization. In: AAAI Conference on Artificial Intelligence (AAAI) (2022)
  * [12] Chiu, T.Y., Gurari, D.: Iterative feature transformation for fast and versatile universal style transfer. In: European Conference on Computer Vision (ECCV) (2020)
  * [13] Chiu, T.Y., Gurari, D.: Pca-based knowledge distillation towards lightweight and content-style balanced photorealistic style transfer models. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2022)
  * [14] Chong, M.J., Forsyth, D.: Effectively unbiased fid and inception score and where to find them. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2020)
  * [15] Deng, Y., Tang, F., Dong, W., Ma, C., Pan, X., Wang, L., Xu, C.: Stytr2: Image style transfer with transformers. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2022)
  * [16] Deng, Y., Tang, F., Dong, W., Sun, W., Huang, F., Xu, C.: Arbitrary style transfer via multi-adaptation network. In: ACM International Conference on Multimedia (2020)
  * [17] Dodge, Y.: The Concise Encyclopedia of Statistics. Springer, New York (2008)
  * [18] Dowson, D., Landau, B.: The fréchet distance between multivariate normal distributions. Journal of Multivariate Analysis 12(3), 450–455 (1982)
  * [19] Dumoulin, V., Shlens, J., Kudlur, M.: A learned representation for artistic style. In: nternational Conference on Learning Representations (ICLR) (2017)
  * [20] Efros, A.A., Freeman, W.T.: Image quilting for texture synthesis and transfer. In: Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques. p. 341–346. SIGGRAPH ’01, Association for Computing Machinery, New York, NY, USA (2001)
  * [21] Fernie, E.: Art History and Its Methods. Phaidon Press (1995)
  * [22] Fréchet, M.: Sur la distance de deux lois de probabilité. In: C. R. Acad. Sci. Paris, 244:689-692 (1957)
  * [23] Gatys, L.A., Ecker, A.S., Bethge, M.: Image style transfer using convolutional neural networks. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2016)
  * [24] Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., Bengio, Y.: Generative adversarial nets. In: Conference on Neural Information Processing Systems (NeurIPS) (2014)
  * [25] Hertzmann, A., Jacobs, C.E., Oliver, N., Curless, B., Salesin, D.H.: Image analogies. In: Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques. p. 327–340. SIGGRAPH ’01, Association for Computing Machinery, New York, NY, USA (2001)
  * [26] Heusel, M., Ramsauer, H., Unterthiner, T., Nessler, B., Klambauer, G., Hochreiter, S.: Gans trained by a two time-scale update rule converge to a nash equilibrium. In: Conference on Neural Information Processing Systems (NeurIPS) (2017)
  * [27] Höllein, L., Johnson, J., Nießner, M.: Stylemesh: Style transfer for indoor 3d scene reconstructions. In: Conference on Computer Vision and Pattern Recognition (CVPR) (June 2022)
  * [28] Hong, K., Jeon, S., Yang, H., Fu, J., Byun, H.: Domain-aware universal style transfer. In: International Conference on Computer Vision (ICCV) (2021)
  * [29] Huang, H., Wang, H., Luo, W., Ma, L., Jiang, W., Zhu, X., Li, Z., Liu, W.: Real-time neural style transfer for videos. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2017)
  * [30] Huang, X., Belongie, S.J.: Arbitrary style transfer in real-time with adaptive instance normalization. International Conference on Computer Vision (ICCV) (2017)
  * [31] Hunter, D.R.: Mm algorithms for generalized bradley-terry models. The Annals of Statistics 32(1), 384–406 (2004)
  * [32] Huo, J., Jin, S., Li, W., Wu, J., Lai, Y.K., Shi, Y., Gao, Y.: Manifold alignment for semantically aligned style transfer. In: International Conference on Computer Vision (ICCV) (2021)
  * [33] Johnson, J., Alahi, A., Fei-Fei, L.: Perceptual losses for real-time style transfer and super-resolution. In: European Conference on Computer Vision (ECCV) (2016)
  * [34] Karras, T., Aittala, M., Hellsten, J., Laine, S., Lehtinen, J., Aila, T.: Training generative adversarial networks with limited data. In: Conference on Neural Information Processing Systems (NeurIPS) (2020)
  * [35] Karras, T., Laine, S., Aila, T.: A style-based generator architecture for generative adversarial networks. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2019)
  * [36] Kim, S.S.Y., Kolkin, N., Salavon, J., Shakhnarovich, G.: Deformable style transfer. In: European Conference on Computer Vision (ECCV) (2020)
  * [37] Kim, S., Kim, S., Kim, S.: Deep translation prior: Test-time training for photorealistic style transfer. In: AAAI Conference on Artificial Intelligence (AAAI) (2022)
  * [38] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. In: International Conference on Learning Representations (ICLR) (2015)
  * [39] Kokoska, S., Zwillinger, D.: CRC Standard Probability and Statistics Tables and Formulae. Chapman & Hall, New York (2000)
  * [40] Kolkin, N., Salavon, J., Shakhnarovich, G.: Style transfer by relaxed optimal transport and self-similarity. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2019)
  * [41] Kotovenko, D., Wright, M., Heimbrecht, A., Ommer, B.: Rethinking style transfer: From pixels to parameterized brushstrokes. Conference on Computer Vision and Pattern Recognition (CVPR) (2021)
  * [42] Kubler, G.: Towards a reductive theory of visual style. In: Meyer, L.B., Lang, B. (eds.) The Concept of Style, pp. 119–127. University of Pennsylvania Press (1979)
  * [43] Kwon, G., Ye, J.C.: Clipstyler: Image style transfer with a single text condition. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2022)
  * [44] Li, X., Liu, S., Kautz, J., Yang, M.H.: Learning linear transformations for fast image and video style transfer. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2019)
  * [45] Li, Y., Wang, N., Liu, J., Hou, X.: Demystifying neural style transfer. In: Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI) (2017)
  * [46] Li, Y., Fang, C., Yang, J., Wang, Z., Lu, X., Yang, M.H.: Universal style transfer via feature transforms. In: Conference on Neural Information Processing Systems (NeurIPS) (2017)
  * [47] Li, Y., Liu, M.Y., Li, X., Yang, M.H., Kautz, J.: A closed-form solution to photorealistic image stylization. In: European Conference on Computer Vision (ECCV) (2018)
  * [48] Lin, T.Y., Maire, M., Belongie, S., Hays, J., Perona, P., Ramanan, D., Dollar, P., Zitnick, L.: Microsoft coco: Common objects in context. In: European Conference on Computer Vision (ECCV) (2014)
  * [49] Liu, S., Lin, T., He, D., Li, F., Deng, R., Li, X., Ding, E., Wang, H.: Paint transformer: Feed forward neural painting with stroke prediction. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2021)
  * [50] Liu, S., Lin, T., He, D., Li, F., Wang, M., Li, X., Sun, Z., Li, Q., Ding, E.: Adaattn: Revisit attention mechanism in arbitrary neural style transfer. In: International Conference on Computer Vision (ICCV) (2021)
  * [51] Liu, X.C., Yang, Y.L., Hall, P.: Learning to warp for style transfer. Conference on Computer Vision and Pattern Recognition (CVPR) (2021)
  * [52] Liu, X., Wu, W., Wu, H., Wen, Z.: Deep style transfer for line drawings. In: AAAI Conference on Artificial Intelligence (AAAI) (2021)
  * [53] Lucic, M., Kurach, K., Michalski, M., Gelly, S., Bousquet, O.: Are gans created equal? a large-scale study. In: Conference on Neural Information Processing Systems (NeurIPS) (2018)
  * [54] Luo, X., Han, Z., Yang, L., Zhang, L.: Consistent style transfer. arXiv preprint arXiv:2201.02233v1 (2022)
  * [55] Meyer, L.B., Lang, B.: The Concept of Style. University of Pennsylvania Press (1979)
  * [56] Mokady, R., Yarom, M., Tov, O., Lang, O., Daniel Cohen-Or, Tali Dekel, M.I., Mosseri, I.: Self-distilled stylegan: Towards generation from internet photos. arXiv preprint arXiv:2202.12211 (2022)
  * [57] Park, D.Y., Lee, K.H.: Arbitrary style transfer with style-attentional networks. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2019)
  * [58] Parmar, G., Zhang, R., Zhu, J.Y.: On aliased resizing and surprising subtleties in gan evaluation. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2022)
  * [59] Radford, A., Kim, J.W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., Krueger, G., Sutskever, I.: Learning transferable visual models from natural language supervision. In: International Conference on Machine Learning (ICML) (2021)
  * [60] Ruder, M., Dosovitskiy, A., Brox, T.: Artistic style transfer for videos and spherical images. International Journal of Computer Vision 126, 1199–1219 (2018)
  * [61] Salimans, T., Goodfellow, I., Zaremba, W., Cheung, V., Radford, A., Chen, X.: Improved techniques for training gans. In: Conference on Neural Information Processing Systems (NeurIPS) (2016)
  * [62] Sanakoyeu, A., Kotovenko, D., Lang, S., Ommer, B.: A style-aware content loss for real-time hd style transfer. In: European Conference on Computer Vision (ECCV) (2018)
  * [63] Schapiro, M.: Style. University of Chicago Press (1953)
  * [64] Shen, F., Yan, S., Zeng, G.: Neural style transfer via meta networks. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2018)
  * [65] Sheng, L., Lin, Z., Shao, J., Wang, X.: Avatar-net: Multi-scale zero-shot style transfer by feature decoration. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2018)
  * [66] Spearman, C.: The proof and measurement of association between two things. The American Journal of Psychology 15(1), 72–101 (1904)
  * [67] Spearman, C.: Demonstration of formulae for true measurement of correlation. The American Journal of Psychology 18(2), 161–169 (1907)
  * [68] Svoboda, J., Anoosheh, A., Osendorfer, C., Masci, J.: Two-stage peer-regularized feature recombination for arbitrary image style transfer. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2020)
  * [69] Szegedy, C., Vanhoucke, V., Ioffe, S., Shlens, J., Wojna, Z.: Rethinking the inception architecture for computer vision. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2016)
  * [70] Tan, W.R., Chan, C.S., Aguirre, H.E., Tanaka, K.: Ceci n’est pas une pipe: A deep convolutional network for fine-art paintings classification. In: International Conference on Image Processing (ICIP) (2016)
  * [71] Tao, T., Zhan, X., Chen, Z., van de Panne, M.: Style-erd: Responsive and coherent online motion style transfer. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2022)
  * [72] Ulyanov, D., Lebedev, V., Vedaldi, A., Lempitsky, V.S.: Texture networks: Feed-forward synthesis of textures and stylized images. In: International Conference on Machine Learning (ICML) (2016)
  * [73] Wallach, A.: Meyer schapiro’s essay on style: Falling into the void. The Journal of Aesthetics and Art Criticism 55(1), 11–15 (1997)
  * [74] Wang, B., Wang, W., Yang, H., Sun, J.: Efficient example-based painting and synthesis of 2d directional texture. Transactions on Visualization and Computer Graphics 10(3), 266–277 (2004)
  * [75] Wang, H., Li, Y., Wang, Y., Hu, H., Yang, M.H.: Collaborative distillation for ultra-resolution universal style transfer. Conference on Computer Vision and Pattern Recognition (CVPR) (2020)
  * [76] Wang, T.C., Liu, M.Y., Zhu, J.Y., Tao, A., Kautz, J., Catanzaro, B.: High-resolution image synthesis and semantic manipulation with conditional gans. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2018)
  * [77] Wang, Z., Bovik, A.C., Sheikh, H.R., Simoncelli, E.P.: Image quality assessment: From error visibility to structural similarity. In: Transactions on Image Processing, Vol. 13, No. 4 (2004)
  * [78] Wilber, M.J., Fang, C., Jin, H., Hertzmann, A., Collomosse, J., Belongie, S.: Bam! the behance artistic media dataset for recognition beyond photography. In: International Conference on Computer Vision (ICCV) (2017)
  * [79] Wu, X., Hu, Z., Sheng, L., Xu, D.: Styleformer: Real-time arbitrary style transfer via parametric style composition. In: International Conference on Computer Vision (ICCV) (2021)
  * [80] Wu, Z., Song, C., Zhou, Y., Gong, M., Huang, H.: Efanet: Exchangeable feature alignment network for arbitrary style transfer. In: AAAI Conference on Artificial Intelligence (AAAI) (2020)
  * [81] Xu, W., Long, C., Wang, R., Wang, G.: Drb-gan: A dynamic resblock generative adversarial network for artistic style transfer. International Conference on Computer Vision (ICCV) (2021)
  * [82] Yang, J., Guo, F., Chen, S., Li, J., Yang, J.: Industrial style transfer with large-scale geometric warping and content preservation. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2022)
  * [83] Yang, S., Jiang, L., Liu, Z., Loy, C.C.: Pastiche master: Exemplar-based high-resolution portrait style transfer. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2022)
  * [84] Yeon, J., Rahnev, D.: The suboptimality of perceptual decision making with multiple alternatives. Nature Communications 11(3857) (2020)
  * [85] Zhang, C., Zhu, Y., Zhu, S.C.: Metastyle: Three-way trade-off among speed, flexibility, and quality in neural style transfer. In: AAAI Conference on Artificial Intelligence (AAAI) (2019)
  * [86] Zhang, R., Isola, P., Efros, A.A., Shechtman, E., Wang, O.: The unreasonable effectiveness of deep features as a perceptual metric. In: Conference on Computer Vision and Pattern Recognition (CVPR) (2018)
  * [87] Zhou, B., Lapedriza, A., Khosla, A., Oliva, A., Torralba, A.: Places: A 10 million image database for scene recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence (2017)
  * [88] Zhu, J.Y., Park, T., Isola, P., Efros, A.A.: Unpaired image-to-image translation using cycle-consistent adversarial networks. In: International Conference on Computer Vision (ICCV) (2017)

##  Appendix 0.A Artwork Dataset

The exact number of images is 241088. There are 109 unique style labels and
595 unique artist labels.

##  Appendix 0.B Training

For training, the images are resized to 299x299. Commonly used augmentations
such as random flipping are applied to the images. We use a weighted cross
entropy loss for training, where the weight for a particular class is the
reciprocal of the number of examples for that class. This is done to alleviate
class imbalances. Tab. 4 shows the validation accuracy of the network.

Table 4: Validation accuracies for the Inception network trained on the art dataset. Classifier Head | Top-1 Accuracy | Top-5 Accuracy
---|---|---
Artist | 0.79 | 0.91
Style | 0.69 | 0.95

##  Appendix 0.C Bradley-Terry Model

In this section, we will explain the iterative algorithm that maximizes log-
likelihood of the Bradley-Terry model. The explanation is mostly taken from
[31]. We also refer to [31] for a study of the convergence properties.
We start with an initial vector $\gamma^{(1)}$. We use
$\gamma^{(1)}$$=\\{1,...,1\\}$ in our experiments. We then iteratively update
$\gamma^{(k)}$ as follows:

$\gamma_{i}^{(k+1)}=W_{i}\left[\sum\limits_{j\neq
i}\frac{N_{ij}}{\gamma_{i}^{(k)}+\gamma_{j}^{(k)}}\right]^{-1},$ (4)

where $W_{i}$ denotes the number of times that entity $i$ was preferred in
total and $N_{ij}=w_{ij}+w_{ji}$ is the number of pairings between entity $i$
and entity $j$. If $\gamma^{(k+1)}$ does not satisfy the constraint
$\sum_{i}\gamma_{i}^{(k+1)}=1$, it is normalized accordingly.


# Graph Sparsification by Effective Resistances††thanks:  This material is
based upon work supported by the National Science Foundation under Grants No.
CCF-0707522 and CCF-0634957. Any opinions, findings, and conclusions or
recommendations expressed in this material are those of the author(s) and do
not necessarily reflect the views of the National Science Foundation.

Daniel A. Spielman
Program in Applied Mathematics and
Department of Computer Science
Yale University  Nikhil Srivastava
Department of Computer Science
Yale University

###### Abstract

We present a nearly-linear time algorithm that produces high-quality spectral
sparsifiers of weighted graphs. Given as input a weighted graph $G=(V,E,w)$
and a parameter $\epsilon>0$, we produce a weighted subgraph
$H=(V,\tilde{E},\tilde{w})$ of $G$ such that $|\tilde{E}|=O(n\log
n/\epsilon^{2})$ and for all vectors $x\in\mathbb{R}^{V}$

$(1-\epsilon)\sum_{uv\in
E}(x(u)-x(v))^{2}w_{uv}\leq\sum_{uv\in\tilde{E}}(x(u)-x(v))^{2}\tilde{w}_{uv}\leq(1+\epsilon)\sum_{uv\in
E}(x(u)-x(v))^{2}w_{uv}.$ (1)

This improves upon the spectral sparsifiers constructed by Spielman and Teng,
which had $O(n\log^{c}n)$ edges for some large constant $c$, and upon the cut
sparsifiers of Benczúr and Karger, which only satisfied (1) for
$x\in\\{0,1\\}^{V}$.

A key ingredient in our algorithm is a subroutine of independent interest: a
nearly-linear time algorithm that builds a data structure from which we can
query the approximate effective resistance between any two vertices in a graph
in $O(\log n)$ time.

##  1 Introduction

The goal of sparsification is to approximate a given graph $G$ by a sparse
graph $H$ on the same set of vertices. If $H$ is close to $G$ in some
appropriate metric, then $H$ can be used as a proxy for $G$ in computations
without introducing too much error. At the same time, since $H$ has very few
edges, computation with and storage of $H$ should be cheaper.

We study the notion of spectral sparsification introduced by Spielman and Teng
[25]. Spectral sparsification was inspired by the notion of cut
sparisification introduced by Benczúr and Karger [5] to accelerate cut
algorithms whose running time depends on the number of edges. They gave a
nearly-linear time procedure which takes a graph $G$ on $n$ vertices with $m$
edges and a parameter $\epsilon>0$, and outputs a weighted subgraph $H$ with
$O(n\log n/\epsilon^{2})$ edges such that the weight of every cut in $H$ is
within a factor of $(1\pm\epsilon)$ of its weight in $G$. This was used to
turn Goldberg and Tarjan’s $\widetilde{O}(mn)$ max-flow algorithm [16] into an
$\widetilde{O}(n^{2})$ algorithm for approximate $st$-mincut, and appeared
more recently as the first step of an $\widetilde{O}(n^{3/2}+m)$-time
$O(\log^{2}n)$ approximation algorithm for sparsest cut [19].

The cut-preserving guarantee of [5] is equivalent to satisfying (1) for all
$x\in\\{0,1\\}^{n}$, which are the characteristic vectors of cuts. Spielman
and Teng [23, 25] devised stronger sparsifiers which extend (1) to all
$x\in\mathbb{R}^{n}$, but have $O(n\log^{c}n)$ edges for some large constant
$c$. They used these sparsifiers to construct preconditioners for symmetric
diagonally-dominant matrices, which led to the first nearly-linear time
solvers for such systems of equations.

In this work, we construct sparsifiers that achieve the same guarantee as
Spielman and Teng’s but with $O(n\log n/\epsilon^{2})$ edges, thus improving
on both [5] and [23]. Our sparsifiers are subgraphs of the original graph and
can be computed in $\widetilde{O}(m)$ time by random sampling, where the
sampling probabilities are given by the effective resistances of the edges.
While this is conceptually much simpler than the recursive partitioning
approach of [23], we need to solve $O(\log n)$ linear systems to compute the
effective resistances quickly, and we do this using Spielman and Teng’s linear
equation solver.

###  1.1 Our Results

Our main idea is to include each edge of $G$ in the sparsifier $H$ with
probability proportional to its effective resistance. The effective resistance
of an edge is known to be equal to the probability that the edge appears in a
random spanning tree of $G$ (see, e.g., [9] or [6]), and was proven in [7] to
be proportional to the commute time between the endpoints of the edge. We show
how to approximate the effective resistances of edges in $G$ quickly and prove
that sampling according to these approximate values yields a good sparsifier.

To define effective resistance, identify $G=(V,E,w)$ with an electrical
network on $n$ nodes in which each edge $e$ corresponds to a link of
conductance $w_{e}$ (i.e., a resistor of resistance $1/w_{e}$). Then the
effective resistance $R_{e}$ across an edge $e$ is the potential difference
induced across it when a unit current is injected at one end of $e$ and
extracted at the other end of $e$. Our algorithm can now be stated as follows.

$H=\textbf{Sparsify}(G,q)$
---
Choose a random edge $e$ of $G$ with probability $p_{e}$ proportional to
$w_{e}R_{e}$, and add $e$ to $H$ with weight $w_{e}/qp_{e}$. Take $q$ samples
independently with replacement, summing weights if an edge is chosen more than
once.

Recall that the Laplacian of a weighted graph is given by $L=D-A$ where $A$ is
the weighted adjacency matrix $(a_{ij})=w_{ij}$ and $D$ is the diagonal matrix
$(d_{ii})=\sum_{j\neq i}w_{ij}$ of weighted degrees. Notice that the quadratic
form associated with $L$ is just $x^{T}Lx=\sum_{uv\in
E}(x(u)-x(v))^{2}w_{uv}$. Let $L$ be the Laplacian of $G$ and let $\tilde{L}$
be the Laplacian of $H$. Our main theorem is that if $q$ is sufficiently
large, then the quadratic forms of $L$ and $\tilde{L}$ are close.

######  Theorem 1.

Suppose $G$ and $H=\mathbf{Sparsify}(G,q)$ have Laplacians $L$ and $\tilde{L}$
respectively, and $1/\sqrt{n}<\epsilon\leq 1$. If $q=9C^{2}n\log
n/\epsilon^{2}$, where $C$ is the constant in Lemma 5 and if $n$ is
sufficiently large, then with probability at least $1/2$

$\forall x\in\mathbb{R}^{n}\quad(1-\epsilon)x^{T}Lx\leq
x^{T}\tilde{L}x\leq(1+\epsilon)x^{T}Lx.$ (2)

Sparsifiers that satisfy this condition preserve many properties of the graph.
The Courant-Fischer Theorem tells us that

$\lambda_{i}=\max_{S:\dim(S)=k}\min_{x\in S}\frac{x^{T}Lx}{x^{T}x}.$

Thus, if $\lambda_{1},\dots,\lambda_{n}$ are the eigenvalues of $L$ and
$\tilde{\lambda}_{1},\dots,\tilde{\lambda}_{n}$ are the eigenvalues of
$\tilde{L}$, then we have

$(1-\epsilon)\lambda_{i}\leq\tilde{\lambda}_{i}\leq(1+\epsilon)\lambda_{i},$

and the eigenspaces spanned by corresponding eigenvalues are related. As the
eigenvalues of the normalized Laplacian are given by

$\lambda_{i}=\max_{S:\dim(S)=k}\min_{x\in
S}\frac{x^{T}D^{-1/2}LD^{-1/2}x}{x^{T}x},$

and are the same as the eigenvalues of the walk matrix $D^{-1}L$, we obtain
the same relationship between the eigenvalues of the walk matrix of the
original graph and its sparsifier. Many properties of graphs and random walks
are known to be revealed by their spectra (see for example [6, 8, 15]). The
existence of sparse subgraphs which retain these properties is interesting its
own right; indeed, expander graphs can be viewed as constant degree
sparsifiers for the complete graph.

We remark that the condition (2) also implies

$\forall x\in\mathbb{R}^{n}\quad\frac{1}{1+\epsilon}x^{T}L^{+}x\leq
x^{T}\tilde{L}^{+}x\leq\frac{1}{1-\epsilon}x^{T}L^{+}x,$

where $L^{+}$ is the pseudoinverse of $L$. Thus sparsifiers also approximately
preserve the effective resistances between vertices, since for vertices $u$
and $v$, the effective resistance between them is given by the formula
$(\chi_{u}-\chi_{v})^{T}L^{+}(\chi_{u}-\chi_{v})$, where $\chi_{u}$ is the
elementary unit vector with a coordinate 1 in position $u$.

We prove Theorem 1 in Section 3. At the end of Section 3, we prove that the
spectral guarantee (2) of Theorem 1 is not harmed too much if use approximate
effective resistances for sampling instead of exact ones(Corollary 6).

In Section 4, we show how to compute approximate effective resistances in
nearly-linear time, which is essentially optimal. The tools we use to do this
are Spielman and Teng’s nearly-linear time solver [23, 24] and the Johnson-
Lindenstrauss Lemma [18, 1]. Specifically, we prove the following theorem, in
which $R_{uv}$ denotes the effective resistance between vertices $u$ and $v$.

######  Theorem 2.

There is an $\widetilde{O}(m(\log r)/\epsilon^{2})$ time algorithm which on
input $\epsilon>0$ and $G=(V,E,w)$ with $r=w_{max}/w_{min}$ computes a
$(24\log n/\epsilon^{2})\times n$ matrix $\widetilde{Z}$ such that with
probability at least $1-1/n$

$(1-\epsilon)R_{uv}\leq\|\widetilde{Z}(\chi_{u}-\chi_{v})\|^{2}\leq(1+\epsilon)R_{uv}$

for every pair of vertices $u,v\in V$.

Since $\widetilde{Z}(\chi_{u}-\chi_{v})$ is simply the difference of the
corresponding two columns of $\widetilde{Z}$, we can query the approximate
effective resistance between any pair of vertices $(u,v)$ in time $O(\log
n/\epsilon^{2})$, and for all the edges in time $O(m\log n/\epsilon^{2})$. By
Corollary 6, this yields an $\widetilde{O}(m(\log r)/\epsilon^{2})$ time for
sparsifying graphs, as advertised.

In Section 5, we show that $H$ can be made close to $G$ in some additional
ways which make it more useful for preconditioning systems of linear
equations.

###  1.2 Related Work

Batson, Spielman, and Srivastava [4] have given a deterministic algorithm that
constructs sparsifiers of size $O(n/\epsilon^{2})$ in $O(mn^{3}/\epsilon^{2})$
time. While this is too slow to be useful in applications, it is optimal in
terms of the tradeoff between sparsity and quality of approximation and can be
viewed as generalizing expander graphs. Their construction parallels ours in
that it reduces the task of spectral sparsification to approximating the
matrix $\Pi$ defined in Section 3; however, their method for selecting edges
is iterative and more delicate than the random sampling described in this
paper.

In addition to the graph sparsifiers of [5, 4, 23], there is a large body of
work on sparse [3, 2] and low-rank [14, 2, 22, 10, 11] approximations for
general matrices. The algorithms in this literature provide guarantees of the
form $\|A-\tilde{A}\|_{2}\leq\epsilon$, where $A$ is the original matrix and
$\tilde{A}$ is obtained by entrywise or columnwise sampling of $A$. This is
analogous to satisfying (1) only for vectors $x$ in the span of the dominant
eigenvectors of $A$; thus, if we were to use these sparsifiers on graphs, they
would only preserve the large cuts. Interestingly, our proof uses some of the
same machinery as the low-rank approximation result of Rudelson and Vershynin
[22] — the sampling of edges in our algorithm corresponds to picking
$q=O(n\log n)$ columns at random from a certain rank $(n-1)$ matrix of
dimension $m\times m$ (this is the matrix $\Pi$ introduced in Section 3).

The use of effective resistance as a distance in graphs has recently gained
attention as it is often more useful than the ordinary geodesic distance in a
graph. For example, in small-world graphs, all vertices will be close to one
another, but those with a smaller effective resistance distance are connected
by more short paths. See, for instance [13, 12], which use effective
resistance/commute time as a distance measure in social network graphs.

##  2 Preliminaries

###  2.1 The Incidence Matrix and the Laplacian

Let $G=(V,E,w)$ be a connected weighted undirected graph with $n$ vertices and
$m$ edges and edge weights $w_{e}>0$. If we orient the edges of $G$
arbitrarily, we can write its Laplacian as $L=B^{T}WB$, where $B_{m\times n}$
is the signed edge-vertex incidence matrix, given by

$B(e,v)=\left\\{\begin{array}[]{ll}1&\textrm{if $v$ is $e$'s head}\\\
-1&\textrm{if $v$ is $e$'s tail}\\\ 0&\textrm{otherwise}\end{array}\right.$

and $W_{m\times m}$ is the diagonal matrix with $W(e,e)=w_{e}$. Denote the row
vectors of $B$ by $\\{b_{e}\\}_{e\in E}$ and the span of its columns by
$\mathbb{B}=\mathrm{im}(B)\subseteq\mathbb{R}^{m}$ (also called the cut space
of $G$ [15]). Note that $b_{(u,v)}^{T}=(\chi_{v}-\chi_{u})$.

It is immediate that $L$ is positive semidefinite since

$x^{T}Lx=x^{T}B^{T}WBx=\|W^{1/2}Bx\|_{2}^{2}\geq 0\quad\textrm{ for every
$x\in\mathbb{R}^{n}$.}$

We also have $\ker(L)=\ker(W^{1/2}B)=\textrm{span}(\mathbf{1})$, since

$\displaystyle x^{T}Lx=0$ $\displaystyle\iff\|W^{1/2}Bx\|_{2}^{2}=0$
$\displaystyle\iff\sum_{uv\in E}w_{uv}(x(u)-x(v))^{2}=0$ $\displaystyle\iff
x(u)-x(v)=0\quad\textrm{for all edges $(u,v)$}$ $\displaystyle\iff\textrm{ $x$
is constant, since $G$ is connected.}$

###  2.2 The Pseudoinverse

Since $L$ is symmetric we can diagonalize it and write

$L=\sum_{i=1}^{n-1}\lambda_{i}u_{i}u_{i}^{T}$

where $\lambda_{1},\ldots,\lambda_{n-1}$ are the nonzero eigenvalues of $L$
and $u_{1},\ldots,u_{n-1}$ are a corresponding set of orthonormal
eigenvectors. The Moore-Penrose Pseudoinverse of $L$ is then defined as

$L^{+}=\sum_{i=1}^{n-1}\frac{1}{\lambda_{i}}u_{i}u_{i}^{T}.$

Notice that $\ker(L)=\ker(L^{+})$ and that

$LL^{+}=L^{+}L=\sum_{i=1}^{n-1}u_{i}u_{i}^{T},$

which is simply the projection onto the span of the nonzero eigenvectors of
$L$ (which are also the eigenvectors of $L^{+}$). Thus, $LL^{+}=L^{+}L$ is the
identity on
$\mathrm{im}(L)=\ker(L)^{\perp}=\mathrm{span}(\mathbf{1})^{\perp}$. We will
rely on this fact heavily in the proof of Theorem 1.

###  2.3 Electrical Flows

Begin by arbitrarily orienting the edges of $G$ as in Section 2.1. We will use
the same notation as [17] to describe electrical flows on graphs: for a vector
$\mathbf{i_{\textrm{ext}}}(u)$ of currents injected at the vertices, let
$\mathbf{i}(e)$ be the currents induced in the edges (in the direction of
orientation) and $\mathbf{v}(u)$ the potentials induced at the vertices. By
Kirchoff’s current law, the sum of the currents entering a vertex is equal to
the amount injected at the vertex:

$B^{T}\mathbf{i}=\mathbf{i_{\textrm{ext}}}.$

By Ohm’s law, the current flow in an edge is equal to the potential difference
across its ends times its conductance:

$\mathbf{i}=WB\mathbf{v}.$

Combining these two facts, we obtain

$\mathbf{i_{\textrm{ext}}}=B^{T}(WB\mathbf{v})=L\mathbf{v}.$

If $\mathbf{i_{\textrm{ext}}}\perp\mathrm{span}(\mathbf{1})=\ker(L)$ — i.e.,
if the total amount of current injected is equal to the total amount extracted
— then we can write

$\mathbf{v}=L^{+}\mathbf{i_{\textrm{ext}}}$

by the definition of $L^{+}$ in Section 2.2.

Recall that the effective resistance between two vertices $u$ and $v$ is
defined as the potential difference induced between them when a unit current
is injected at one and extracted at the other. We will derive an algebraic
expression for the effective resistance in terms of $L^{+}$. To inject and
extract a unit current across the endpoints of an edge $e=(u,v)$, we set
$\mathbf{i_{\textrm{ext}}}=b_{e}^{T}=(\chi_{v}-\chi_{u})$, which is clearly
orthogonal to $\mathbf{1}$. The potentials induced by
$\mathbf{i_{\textrm{ext}}}$ at the vertices are given by
$\mathbf{v}=L^{+}b_{e}^{T}$; to measure the potential difference across
$e=(u,v)$, we simply multiply by $b_{e}$ on the left:

$\mathbf{v}(v)-\mathbf{v}(u)=(\chi_{v}-\chi_{u})^{T}\mathbf{v}=b_{e}L^{+}b_{e}^{T}.$

It follows that the effective resistance across $e$ is given by
$b_{e}L^{+}b_{e}^{T}$ and that the matrix $BL^{+}B^{T}$ has as its diagonal
entries $BL^{+}B^{T}(e,e)=R_{e}$.

##  3 The Main Result

We will prove Theorem 1. Consider the matrix $\Pi=W^{1/2}BL^{+}B^{T}W^{1/2}$.
Since we know $BL^{+}B^{T}(e,e)=R_{e}$, the diagonal entries of $\Pi$ are
$\Pi(e,e)=\sqrt{W(e,e)}R_{e}\sqrt{W(e,e)}=w_{e}R_{e}$. $\Pi$ has some notable
properties.

######  Lemma 3 (Projection Matrix).

(i) $\Pi$ is a projection matrix. (ii)
$\mathrm{im}(\Pi)=\mathrm{im}(W^{1/2}B)=W^{1/2}\mathbb{B}$. (iii) The
eigenvalues of $\Pi$ are $1$ with multiplicity $n-1$ and $0$ with multiplicity
$m-n+1$. (iv) $\Pi(e,e)=\|\Pi(\cdot,e)\|^{2}$.

###### Proof.

To see (i), observe that

$\displaystyle\Pi^{2}$
$\displaystyle=(W^{1/2}BL^{+}B^{T}W^{1/2})(W^{1/2}BL^{+}B^{T}W^{1/2})$
$\displaystyle=W^{1/2}BL^{+}(B^{T}WB)L^{+}B^{T}W^{1/2}$
$\displaystyle=W^{1/2}BL^{+}LL^{+}B^{T}W^{1/2}\quad\textrm{ since
$L=B^{T}WB$}$ $\displaystyle=W^{1/2}BL^{+}B^{T}W^{1/2}$ since $L^{+}L$ is the
identity on $\mathrm{im}(L^{+}$) $\displaystyle=\Pi.$

For (ii), we have

$\mathrm{im}(\Pi)=\mathrm{im}(W^{1/2}BL^{+}B^{T}W^{1/2})\subseteq\mathrm{im}(W^{1/2}B).$

To see the other inclusion, assume $y\in\mathrm{im}(W^{1/2}B)$. Then we can
choose $x\perp\ker(W^{1/2}B)=\ker(L)$ such that $W^{1/2}Bx=y$. But now

$\displaystyle\Pi y$ $\displaystyle=W^{1/2}BL^{+}B^{T}W^{1/2}W^{1/2}Bx$
$\displaystyle=W^{1/2}BL^{+}Lx\quad\textrm{since $B^{T}WB=L$}$
$\displaystyle=W^{1/2}Bx\quad\textrm{since $L^{+}Lx=x$ for $x\perp\ker(L)$}$
$\displaystyle=y.$

Thus $y\in\mathrm{im}(\Pi)$, as desired.

For (iii), recall from Section 2.1 that $\dim(\ker(W^{1/2}B))=1$.
Consequently, $\dim(\mathrm{im}(\Pi))=\dim(\mathrm{im}(W^{1/2}B))=n-1$. But
since $\Pi^{2}=\Pi$, the eigenvalues of $\Pi$ are all $0$ or $1$, and as $\Pi$
projects onto a space of dimension $n-1$, it must have exactly $n-1$ nonzero
eigenvalues.

(iv) follows from $\Pi^{2}(e,e)=\Pi(\cdot,e)^{T}\Pi(\cdot,e)$, since $\Pi$ is
symmetric. ∎

To show that $H=(V,\tilde{E},\tilde{w})$ is a good sparsifier for $G$, we need
to show that the quadratic forms $x^{T}Lx$ and $x^{T}\tilde{L}x$ are close. We
start by reducing the problem of preserving $x^{T}Lx$ to that of preserving
$y^{T}\Pi y$. This will be much nicer since the eigenvalues of $\Pi$ are all
$0$ or $1$, so that any matrix $\tilde{\Pi}$ which approximates $\Pi$ in the
spectral norm (i.e., makes $\|\tilde{\Pi}-\Pi\|_{2}$ small) also preserves its
quadratic form.

We may describe the outcome of $H=\mathbf{Sparsify}(G,q)$ by the following
random matrix:

$S(e,e)=\frac{\tilde{w_{e}}}{w_{e}}=\frac{\textrm{(\\# of times $e$ is
sampled)}}{qp_{e}}.$ (3)

$S_{m\times m}$ is a nonnegative diagonal matrix and the random entry $S(e,e)$
specifies the ‘amount’ of edge $e$ included in $H$ by $\mathbf{Sparsify}$. For
example $S(e,e)=1/qp_{e}$ if $e$ is sampled once, $2/qp_{e}$ if it is sampled
twice, and zero if it is not sampled at all. The weight of $e$ in $H$ is now
given by $\tilde{w_{e}}=S(e,e)w_{e}$, and we can write the Laplacian of $H$
as:

$\tilde{L}=B^{T}\tilde{W}B=B^{T}W^{1/2}SW^{1/2}B$

since $\tilde{W}=WS=W^{1/2}SW^{1/2}$. The scaling of weights by $1/qp_{e}$ in
$\mathbf{Sparsify}$ implies that $\mathbb{E}\tilde{w_{e}}=w_{e}$ (since $q$
independent samples are taken, each with probability $p_{e}$), and thus
$\mathbb{E}S=I$ and $\mathbb{E}\tilde{L}=L$.

We can now prove the following lemma, which says that if $S$ does not distort
$y^{T}\Pi y$ too much then $x^{T}Lx$ and $x^{T}\tilde{L}x$ are close.

######  Lemma 4.

Suppose $S$ is a nonnegative diagonal matrix such that

$\|\Pi S\Pi-\Pi\Pi\|_{2}\leq\epsilon.$

Then

$\forall x\in\mathbb{R}^{n}\quad(1-\epsilon)x^{T}Lx\leq
x^{T}\tilde{L}x\leq(1+\epsilon)x^{T}Lx,$

where $L=B^{T}WB$ and $\tilde{L}=B^{T}W^{1/2}SW^{1/2}B$.

###### Proof.

The assumption is equivalent to

$\sup_{y\in\mathbb{R}^{m},y\neq 0}\frac{|y^{T}\Pi(S-I)\Pi
y|}{y^{T}y}\leq\epsilon$

since $\|A\|_{2}=\sup_{y\neq 0}|y^{T}Ay|/y^{T}y$ for symmetric $A$.
Restricting our attention to vectors in $\mathrm{im}(W^{1/2}B)$, we have

$\sup_{y\in\mathrm{im}(W^{1/2}B),y\neq 0}\frac{|y^{T}\Pi(S-I)\Pi
y|}{y^{T}y}\leq\epsilon.$

But by Lemma 3.(ii), $\Pi$ is the identity on $\mathrm{im}(W^{1/2}B)$ so $\Pi
y=y$ for all $y\in\mathrm{im}(W^{1/2}B)$. Also, every such $y$ can be written
as $y=W^{1/2}Bx$ for $x\in\mathbb{R}^{n}$. Substituting this into the above
expression we obtain:

$\displaystyle\sup_{y\in\mathrm{im}(W^{1/2}B),y\neq 0}\frac{|y^{T}\Pi(S-I)\Pi
y|}{y^{T}y}$ $\displaystyle=\sup_{y\in\mathrm{im}(W^{1/2}B),y\neq
0}\frac{|y^{T}(S-I)y|}{y^{T}y}$
$\displaystyle=\sup_{x\in\mathbb{R}^{n},W^{1/2}Bx\neq
0}\frac{|x^{T}B^{T}W^{1/2}SW^{1/2}Bx-x^{T}B^{T}WBx|}{x^{T}B^{T}WBx}$
$\displaystyle=\sup_{x\in\mathbb{R}^{n},W^{1/2}Bx\neq
0}\frac{|x^{T}\tilde{L}x-x^{T}Lx|}{x^{T}Lx}\leq\epsilon.$

Rearranging yields the desired conclusion for all $x\notin\ker(W^{1/2}B)$.
When $x\in\ker(W^{1/2}B)$ then $x^{T}Lx=x^{T}\tilde{L}x=0$ and the claim holds
trivially.∎

To show that $\|\Pi S\Pi-\Pi\Pi\|_{2}$ is likely to be small we use the
following concentration result, which is a sort of law of large numbers for
symmetric rank 1 matrices. It was first proven by Rudelson in [21], but the
version we state here appears in the more recent paper [22] by Rudelson and
Vershynin.

######  Lemma 5 (Rudelson & Vershynin, [22] Thm. 3.1).

Let $\mathbf{p}$ be a probability distribution over
$\Omega\subseteq\mathbb{R}^{d}$ such that $\sup_{y\in\Omega}\|y\|_{2}\leq M$
and $\|\mathbb{E}_{\mathbf{p}}yy^{T}\|_{2}\leq 1$. Let $y_{1}\ldots y_{q}$ be
independent samples drawn from $\mathbf{p}$. Then

$\mathbb{E}\left\|\frac{1}{q}\sum_{i=1}^{q}y_{i}y_{i}^{T}-\mathbb{E}yy^{T}\right\|_{2}\leq\min\left(CM\sqrt{\frac{\log
q}{q}},1\right)$

where $C$ is an absolute constant.

We can now finish the proof of Theorem 1.

###### Proof of Theorem 1.

$\mathbf{Sparsify}$ samples edges from $G$ independently with replacement,
with probabilities $p_{e}$ proportional to $w_{e}R_{e}$. Since
$\sum_{e}w_{e}R_{e}=\textrm{Tr}(\Pi)=n-1$ by Lemma 3.(iii), the actual
probability distribution over $E$ is given by $p_{e}=\frac{w_{e}R_{e}}{n-1}$.
Sampling $q$ edges from $G$ corresponds to sampling $q$ columns from $\Pi$, so
we can write

$\displaystyle\Pi S\Pi$
$\displaystyle=\sum_{e}S(e,e)\Pi(\cdot,e)\Pi(\cdot,e)^{T}$
$\displaystyle=\sum_{e}\frac{(\\#\textrm{ of times $e$ is
sampled})}{qp_{e}}\Pi(\cdot,e)\Pi(\cdot,e)^{T}\quad\textrm{by (\ref{defS})}$
$\displaystyle=\frac{1}{q}\sum_{e}(\\#\textrm{ of times $e$ is
sampled})\frac{\Pi(\cdot,e)}{\sqrt{p_{e}}}\frac{\Pi(\cdot,e)^{T}}{\sqrt{p_{e}}}$
$\displaystyle=\frac{1}{q}\sum_{i=1}^{q}y_{i}y_{i}^{T}$

for vectors $y_{1},\ldots,y_{q}$ drawn independently with replacement from the
distribution

$y=\frac{1}{\sqrt{p_{e}}}\Pi(\cdot,e)\quad\textrm{with probability }p_{e}.$

We can now apply Lemma 5. The expectation of $yy^{T}$ is given by

$\mathbb{E}yy^{T}=\sum_{e}p_{e}\frac{1}{p_{e}}\Pi(\cdot,e)\Pi(\cdot,e)^{T}=\Pi\Pi=\Pi,$

so $\|\mathbb{E}yy^{T}\|_{2}=\|\Pi\|_{2}=1$. We also have a bound on the norm
of $y$:

$\frac{1}{\sqrt{p_{e}}}\|\Pi(\cdot,e)\|_{2}=\frac{1}{\sqrt{p_{e}}}\sqrt{\Pi(e,e)}\\\
=\sqrt{\frac{n-1}{R_{e}w_{e}}}\sqrt{R_{e}w_{e}}=\sqrt{n-1}.$

Taking $q=9C^{2}n\log n/\epsilon^{2}$ gives:

$\mathbb{E}\left\|\Pi
S\Pi-\Pi\Pi\right\|_{2}=\mathbb{E}\left\|\frac{1}{q}\sum_{i=1}^{q}y_{i}y_{i}^{T}-\mathbb{E}yy^{T}\right\|_{2}\leq
C\sqrt{\epsilon^{2}\frac{\log(9C^{2}n\log n/\epsilon^{2})(n-1)}{9C^{2}n\log
n}}\leq\epsilon/2,$

for $n$ sufficiently large, as $\epsilon$ is assumed to be at least
$1/\sqrt{n}$.

By Markov’s inequality, we have

$\|\Pi S\Pi-\Pi\|_{2}\leq\epsilon$

with probability at least $1/2$. By Lemma 4, this completes the proof of the
theorem. ∎

We now show that using approximate resistances for sampling does not damage
the sparsifier very much.

######  Corollary 6.

Suppose $Z_{e}$ are numbers satisfying $Z_{e}\geq R_{e}/\alpha$ and
$\sum_{e}w_{e}Z_{e}\leq\alpha\sum_{e}w_{e}R_{e}$ for some $\alpha\geq 1$. If
we sample as in $\mathbf{Sparsify}$ but take each edge with probability
$p_{e}^{\prime}=\frac{w_{e}Z_{e}}{\sum_{e}w_{e}Z_{e}}$ instead of
$p_{e}=\frac{w_{e}R_{e}}{\sum_{e}w_{e}R_{e}}$, then $H$ satisfies:

$(1-\epsilon\alpha)x^{T}\tilde{L}x\leq
x^{T}Lx\leq(1+\epsilon\alpha)x^{T}\tilde{L}x\quad\forall x\in\mathbb{R}^{n},$

with probability at least $1/2$.

###### Proof.

We note that

$p_{e}^{\prime}=\frac{w_{e}S_{e}}{\sum_{e}w_{e}S_{e}}\geq\frac{w_{e}(R_{e}/\alpha)}{\alpha\sum_{e}w_{e}R_{e}}=\frac{p_{e}}{\alpha^{2}}$

and proceed as in the proof of Theorem 1. The norm of the random vector $y$ is
now bounded by:

$\frac{1}{\sqrt{p_{e}^{\prime}}}\|\Pi(e,\cdot)\|_{2}\leq\frac{\alpha}{\sqrt{p_{e}}}\sqrt{\Pi(e,e)}\\\
=\alpha\sqrt{n-1}$

which introduces a factor of $\alpha$ into the final bound on the expectation,
but changes nothing else.∎

##  4 Computing Approximate Resistances Quickly

It is not clear how to compute all the effective resistances $\\{R_{e}\\}$
exactly and efficiently. In this section, we show that one can compute
constant factor approximations to all the $R_{e}$ in time $\widetilde{O}(m\log
r)$. In fact, we do something stronger: we build a $O(\log n)\times n$ matrix
$\widetilde{Z}$ from which the effective resistance between any two vertices
(including vertices not connected by an edge) can be computed in $O(\log n)$
time.

###### Proof of Theorem 2.

If $u$ and $v$ are vertices in $G$, then the effective resistance between $u$
and $v$ can be written as:

$\displaystyle R_{uv}$
$\displaystyle=(\chi_{u}-\chi_{v})^{T}L^{+}(\chi_{u}-\chi_{v})$
$\displaystyle=(\chi_{u}-\chi_{v})^{T}L^{+}LL^{+}(\chi_{u}-\chi_{v})$
$\displaystyle=((\chi_{u}-\chi_{v})^{T}L^{+}B^{T}W^{1/2})(W^{1/2}BL^{+}(\chi_{u}-\chi_{v}))$
$\displaystyle=\|W^{1/2}BL^{+}(\chi_{u}-\chi_{v})^{2}\|_{2}^{2}.$

Thus effective resistances are just pairwise distances between vectors in
$\\{W^{1/2}BL^{+}\chi_{v}\\}_{v\in V}$. By the Johnson-Lindenstrauss Lemma,
these distances are preserved if we project the vectors onto a subspace
spanned by $O(\log n)$ random vectors. For concreteness, we use the following
version of the Johnson-Lindenstrauss Lemma due to Achlioptas [1].

######  Lemma 7.

Given fixed vectors $v_{1}\ldots v_{n}\in\mathbb{R}^{d}$ and $\epsilon>0$, let
$Q_{k\times d}$ be a random $\pm 1/\sqrt{k}$ matrix (i.e., independent
Bernoulli entries) with $k\geq 24\log n/\epsilon^{2}$. Then with probability
at least $1-1/n$

$(1-\epsilon)\|v_{i}-v_{j}\|_{2}^{2}\leq\|Qv_{i}-Qv_{j}\|_{2}^{2}\leq(1+\epsilon)\|v_{i}-v_{j}\|_{2}^{2}$

for all pairs $i,j\leq n$.

Our goal is now to compute the projections $\\{QW^{1/2}BL^{+}\chi_{v}\\}$. We
will exploit the linear system solver of Spielman and Teng [23, 24], which we
recall satisfies:

######  Theorem 8 (Spielman-Teng).

There is an algorithm $x=\mathtt{STSolve}(L,y,\delta)$ which takes a Laplacian
matrix $L$, a column vector $y$, and an error parameter $\delta>0$, and
returns a column vector $x$ satisfying

$\|x-L^{+}y\|_{L}\leq\epsilon\|L^{+}y\|_{L},$

where $\left\|y\right\|_{L}=\sqrt{y^{T}Ly}$. The algorithm runs in expected
time $\widetilde{O}\left(m\log(1/\delta)\right)$, where $m$ is the number of
non-zero entries in $L$.

Let $Z=QW^{1/2}BL^{+}$. We will compute an approximation $\widetilde{Z}$ by
using STSolve to approximately compute the rows of $Z$. Let the column vectors
$z_{i}$ and $\tilde{z_{i}}$ denote the $i$th rows of $Z$ and $\tilde{Z}$,
respectively (so that $z_{i}$ is the $i$th column of $Z^{T}$). Now we can
construct the matrix $\widetilde{Z}$ in the following three steps.

  1. 1.

Let $Q$ be a random $\pm 1/\sqrt{k}$ matrix of dimension $k\times n$ where
$k=24\log n/\epsilon^{2}$.

  2. 2.

Compute $Y=QW^{1/2}B$. Note that this takes $2m\times 24\log
n/\epsilon^{2}+m=\widetilde{O}(m/\epsilon^{2})$ time since $B$ has $2m$
entries and $W^{1/2}$ is diagonal.

  3. 3.

Let $y_{i}$, for $1\leq i\leq k$, denote the rows of $Y$, and compute
$\tilde{z}_{i}=\mathtt{STSolve}(L,y_{i},\delta)$ for each $i$.

We now prove that, for our purposes, it suffices to call STSolve with

$\delta=\frac{\epsilon}{3}\sqrt{\frac{2(1-\epsilon)w_{min}}{(1+\epsilon)n^{3}w_{{max}}}}.$

######  Lemma 9.

Suppose

$(1-\epsilon)R_{uv}\leq\left\|Z(\chi_{u}-\chi_{v})\right\|^{2}\leq(1+\epsilon)R_{uv},$

for every pair $u,v\in V$. If for all $i$,

$\|z_{i}-\tilde{z}_{i}\|_{L}\leq\delta\|z_{i}\|_{L},$ (4)

where

$\delta\leq\frac{\epsilon}{3}\sqrt{\frac{2(1-\epsilon)w_{min}}{(1+\epsilon)n^{3}w_{{max}}}}$
(5)

then

$(1-\epsilon)^{2}R_{uv}\leq\|\widetilde{Z}(\chi_{u}-\chi_{v})\|^{2}\leq(1+\epsilon)^{2}R_{uv},$

for every $uv$.

###### Proof.

Consider an arbitrary pair of vertices $u$, $v$. It suffices to show that

$\left|\left\|Z(\chi_{u}-\chi_{v})\right\|-\|\tilde{Z}(\chi_{u}-\chi_{v})\|\right|\leq\frac{\epsilon}{3}\left\|Z(\chi_{u}-\chi_{v})\right\|$
(6)

since this will imply

$\displaystyle\left|\left\|Z(\chi_{u}-\chi_{v})\right\|^{2}-\|{\tilde{Z}(\chi_{u}-\chi_{v})}\|^{2}\right|$
$\displaystyle=\left|\left\|Z(\chi_{u}-\chi_{v})\right\|-\|\tilde{Z}(\chi_{u}-\chi_{v})\|\right|\cdot\left|\left\|Z(\chi_{u}-\chi_{v})\right\|+\|\tilde{Z}(\chi_{u}-\chi_{v})\|\right|$
$\displaystyle\leq\frac{\epsilon}{3}\cdot\left(2+\frac{\epsilon}{3}\right)\left\|Z(\chi_{u}-\chi_{v})\right\|^{2}.$

As $G$ is connected, there is a simple path $P$ connecting $u$ to $v$.
Applying the triangle inequality twice, we obtain

$\displaystyle\left|\left\|Z(\chi_{u}-\chi_{v})\right\|-\left\|\widetilde{Z}(\chi_{u}-\chi_{v})\right\|\right|$
$\displaystyle\leq\left\|(Z-\widetilde{Z})(\chi_{u}-\chi_{v})\right\|$
$\displaystyle\leq\sum_{ab\in
P}\left\|(Z-\widetilde{Z})(\chi_{a}-\chi_{b})\right\|.$

We will upper bound this later term by considering its square:

$\displaystyle\left(\sum_{ab\in
P}\left\|(Z-\widetilde{Z})(\chi_{a}-\chi_{b})\right\|\right)^{2}$
$\displaystyle\leq n\sum_{ab\in
P}\left\|(Z-\widetilde{Z})(\chi_{a}-\chi_{b})\right\|^{2}\qquad\text{by
Cauchy-Schwarz}$ $\displaystyle\leq n\sum_{ab\in
E}\left\|(Z-\widetilde{Z})(\chi_{a}-\chi_{b})\right\|^{2}$
$\displaystyle=n\left\|(Z-\widetilde{Z})B^{T}\right\|_{F}^{2}\qquad\text{writing
this as a Frobenius norm}$
$\displaystyle=n\left\|B(Z-\widetilde{Z})^{T}\right\|_{F}^{2}$
$\displaystyle\leq\frac{n}{w_{min}}\left\|W^{1/2}B(Z-\widetilde{Z})^{T}\right\|_{F}^{2}\qquad\text{since
$\|W^{-1/2}\|_{2}\leq 1/\sqrt{w_{min}}$}$
$\displaystyle\leq\delta^{2}\frac{n}{w_{min}}\left\|W^{1/2}BZ^{T}\right\|_{F}^{2}$
since
$\|W^{1/2}B(z_{i}-\tilde{z}_{i})\|^{2}\leq\delta^{2}\|W^{1/2}Bz_{i}\|^{2}$ by
(4) $\displaystyle=\delta^{2}\frac{n}{w_{min}}\sum_{ab\in
E}w_{ab}\left\|Z(\chi_{a}-\chi_{b})\right\|^{2}$
$\displaystyle\leq\delta^{2}\frac{n}{w_{min}}\sum_{ab\in
E}w_{ab}(1+\epsilon)R_{ab}$
$\displaystyle\leq\delta^{2}\frac{n(1+\epsilon)}{w_{min}}(n-1)\qquad\text{ by
Lemma~{}\ref{lempi}.(iii).}$

On the other hand,

$\left\|Z(\chi_{u}-\chi_{v})\right\|^{2}\geq(1-\epsilon)R_{uv}\geq\frac{2(1-\epsilon)}{nw_{max}},$

by Proposition 10. Combining these bounds, we have

$\displaystyle\frac{\left|\left\|Z(\chi_{u}-\chi_{v})\right\|-\left\|\widetilde{Z}(\chi_{u}-\chi_{v})\right\|\right|}{\left\|Z(\chi_{u}-\chi_{v})\right\|}$
$\displaystyle\leq\delta\left({\frac{n(1+\epsilon)}{w_{min}}(n-1)}\right)^{1/2}\cdot\left(\frac{nw_{max}}{2(1-\epsilon)}\right)^{1/2}$
$\displaystyle\leq\frac{\epsilon}{3}\qquad\textrm{by
(\ref{eqn:stprecision}),}$

as desired. ∎

######  Proposition 10.

If $G=(V,E,w)$ is a connected graph, then for all $u,v\in V$,

$R_{uv}\geq\frac{2}{nw_{max}}.$

###### Proof.

By Rayleigh’s monotonicity law (see [6]), each resistance $R_{uv}$ in $G$ is
at least the corresponding resistance $R_{uv}^{\prime}$ in
$G^{\prime}=w_{{max}}\times K_{n}$ (the complete graph with all edge weights
$w_{{max}}$) since $G^{\prime}$ is obtained by increasing weights (i.e.,
conductances) of edges in $G$. But by symmetry each resistance
$R_{uv}^{\prime}$ in $G^{\prime}$ is exactly

$\frac{\sum_{uv}R_{uv}^{\prime}}{\binom{n}{2}}=\frac{(n-1)/w_{{max}}}{n(n-1)/2}=\frac{2}{nw_{{max}}}.$

Thus $R_{uv}\geq\frac{2}{nw_{{max}}}$ for all $u,v\in V$. ∎

Thus the construction of $\widetilde{Z}$ takes
$\widetilde{O}(m\log(1/\delta)/\epsilon^{2})=\widetilde{O}(m\log
r/\epsilon^{2})$ time. We can then find the approximate resistance
$\|\widetilde{Z}(\chi_{u}-\chi_{v})\|^{2}\approx R_{uv}$ for any $u,v\in V$ in
$O(\log n/\epsilon^{2})$ time simply by subtracting two columns of
$\widetilde{Z}$ and computing the norm of their difference. ∎

Using the above procedure, we can compute arbitrarily good approximations to
the effective resistances $\\{R_{e}\\}$ which we need for sampling in nearly-
linear time. By Corollary 6, any constant factor approximation yields a
sparsifier, so we are done.

##  5 An Additional Property

Corollary 6 suggests that $\mathbf{Sparsify}$ is quite robust with respect to
changes in the sampling probabilities $p_{e}$, and that we may be able to
prove additional guarantees on $H$ by tweaking them. In this section, we prove
one such claim.

The following property is desirable for using $H$ to solve linear systems
(specifically, for the construction of ultrasparsifiers [23, 24], which we
will not define here):

$\textrm{For every vertex $v\in V,$}\quad\sum_{e\ni
v}\frac{\tilde{w}_{e}}{w_{e}}\leq 2\deg(v).$ (7)

This says, roughly, that not too many of the edges incident to any given
vertex get blown up too much by sampling and rescaling. We show how to
incorporate this property into our sparsifiers.

######  Lemma 11.

Suppose we sample $q>4n\log n/\beta$ edges of $G$ as in $\mathbf{Sparsify}$
with probabilities that satisfy

$p_{(u,v)}\geq\frac{\beta}{n\min(\deg(u),\deg(v))}$

for some constant $0<\beta<1$. Then with probability at least $1-1/n$,

$\sum_{e\ni v}\frac{\tilde{w}_{e}}{w_{e}}\leq 2\deg(v)\quad\textrm{for all
$v\in V$.}$

###### Proof.

For a vertex $v$, define i.i.d. random variables $X_{1},\ldots,X_{q}$ by:

$X_{i}=\left\\{\begin{array}[]{ll}\frac{1}{p_{e}}&\textrm{if $e\ni v$ is the
$i$th edge chosen}\\\ 0&\textrm{otherwise}\end{array}\right.$

so that $X_{i}$ is set to $1/p_{e}$ with probability $p_{e}$ for each edge $e$
attached to $v$. Let

$D_{v}=\sum_{e\ni v}\frac{\tilde{w_{e}}}{w_{e}}=\sum_{e\ni
v}\frac{\textrm{(\\# of times $e$ is
sampled)}}{qp_{e}}=\frac{1}{q}\sum_{i=1}^{q}X_{i}.$

We want to show that with high probability, $D_{v}\leq 2\deg(v)$ for all
vertices $v$. We begin by bounding the expectation and variance of each
$X_{i}$:

$\displaystyle\mathbb{E}X_{i}$ $\displaystyle=\sum_{e\ni
v}p_{e}\frac{1}{p_{e}}=\deg(v)$ $\displaystyle\mathbf{Var}(X_{i})$
$\displaystyle=\sum_{e\ni
v}p_{e}\left(\frac{1}{p_{e}^{2}}-\frac{1}{p_{e}}\right)$
$\displaystyle\leq\sum_{e\ni v}\frac{1}{p_{e}}$
$\displaystyle\leq\sum_{(u,v)\ni
v}\frac{n\min(\deg(u),\deg(v))}{\beta}\quad\textrm{by assumption}$
$\displaystyle\leq\sum_{(u,v)\ni v}\frac{n\deg(v)}{\beta}$
$\displaystyle=\frac{n\deg(v)^{2}}{\beta}$

Since the $X_{i}$ are independent, the variance of $D_{v}$ is just

$\mathbf{Var}(D_{v})=\frac{1}{q^{2}}\sum_{i=1}^{q}\mathbf{Var}(X_{i})\leq\frac{n\deg(v)^{2}}{\beta
q}.$

We now apply Bennett’s inequality for sums of i.i.d. variables (see, e.g.,
[20]), which says

$\mathbb{P}[|D_{v}-\mathbb{E}D_{v}|>\mathbb{E}D_{v}]\leq\exp\left(\frac{-(\mathbb{E}D_{v})^{2}}{\mathbf{Var}(D_{v})(1+\frac{\mathbb{E}D_{v}}{q})}\right)$

We know that $\mathbb{E}D_{v}=\mathbb{E}X_{i}=\deg(v)$. Substituting our
estimate for $\mathbf{Var}(D_{v})$ and setting $q\geq 4n\log n/\beta$ gives:

$\displaystyle\mathbb{P}[D_{v}>2\deg(v)]$
$\displaystyle\leq\exp\left(\frac{-\deg(v)^{2}}{\frac{n\deg(v)^{2}}{\beta
q}(1+\frac{\deg(v)}{q})}\right)$ $\displaystyle\leq\exp\left(\frac{-\beta
q}{2n}\right)\quad\textrm{since $1+\frac{\deg(v)}{q}\leq 2$}$
$\displaystyle\leq\exp\left(-2\log n\right)=1/n^{2}.$

Taking a union bound over all $v$ gives the desired result.∎

Sampling with probabilities

$p^{\prime}_{e}=p^{\prime}_{(u,v)}=\frac{1}{2}\left(\frac{\|Zb_{e}^{T}\|^{2}w_{e}}{\sum_{e}\|Zb_{e}^{T}\|^{2}w_{e}}+\frac{1}{n\min(\deg(u),\deg(v))}\right)$

satisfies the requirements of both Corollary 6 (with $\alpha=2$) and Lemma 11
(with $\beta=1/2$) and yields a sparsifier with the desired property.

######  Theorem 12.

There is an $\widetilde{O}(m/\epsilon^{2})$ time algorithm which on input
$G=(V,E,w),\epsilon>0$ produces a weighted subgraph
$H=(V,\tilde{E},\tilde{w})$ of $G$ with $O(n\log n/\epsilon^{2})$ edges which,
with probability at least $1/2$, satisfies both (2) and (7).

## References

  * [1] D. Achlioptas.  Database-friendly random projections.  In PODS ’01, pages 274–281, 2001.
  * [2] D. Achlioptas and F. McSherry.  Fast computation of low rank matrix approximations.  In STOC ’01, pages 611–618, 2001.
  * [3] S. Arora, E. Hazan, and S. Kale.  A fast random sampling algorithm for sparsifying matrices.  In APPROX-RANDOM ’06, volume 4110 of Lecture Notes in Computer Science, pages 272–279. Springer, 2006.
  * [4] Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava.  Twice-Ramanujan sparsifiers.  In STOC ’09: Proceedings of the 41st annual ACM symposium on Theory of computing, pages 255–262, New York, NY, USA, 2009. ACM.
  * [5] A. A. Benczúr and D. R. Karger.  Approximating s-t minimum cuts in $\tilde{O}(n^{2})$ time.  In STOC ’96, pages 47–55, 1996.
  * [6] B. Bollobas.  Modern Graph Theory.  Springer, July 1998.
  * [7] A. K. Chandra, P. Raghavan, W. L. Ruzzo, and R. Smolensky.  The electrical resistance of a graph captures its commute and cover times.  In STOC ’89, pages 574–586, 1989.
  * [8] F. R. K. Chung.  Spectral Graph Theory.  CBMS Regional Conference Series in Mathematics. American Mathematical Society, 1997.
  * [9] P. Doyle and J. Snell.  Random walks and electric networks.  Math. Assoc. America., Washington, 1984.
  * [10] P. Drineas and R. Kannan.  Fast monte-carlo algorithms for approximate matrix multiplication.  In FOCS ’01, pages 452–459, 2001.
  * [11] P. Drineas and R. Kannan.  Pass efficient algorithms for approximating large matrices.  In SODA ’03, pages 223–232, 2003.
  * [12] A. Firat, S. Chatterjee, and M. Yilmaz.  Genetic clustering of social networks using random walks.  Computational Statistics & Data Analysis, 51(12):6285–6294, August 2007.
  * [13] F. Fouss, A. Pirotte, J.-M. Renders, and M. Saerens.  Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation.  Knowledge and Data Engineering, IEEE Transactions on, 19(3):355–369, 2007.
  * [14] A. Frieze, R. Kannan, and S. Vempala.  Fast monte-carlo algorithms for finding low-rank approximations.  J. ACM, 51(6):1025–1041, 2004.
  * [15] Chris Godsil and Gordon Royle.  Algebraic Graph Theory.  Graduate Texts in Mathematics. Springer, 2001.
  * [16] A. V. Goldberg and R. E. Tarjan.  A new approach to the maximum flow problem.  In STOC ’86, pages 136–146, 1986.
  * [17] S. Guattery and G. L. Miller.  Graph embeddings and Laplacian eigenvalues.  SIAM J. Matrix Anal. Appl., 21(3):703–723, 2000.
  * [18] W. Johnson and J. Lindenstrauss.  Extensions of Lipschitz mappings into a Hilbert space.  Contemp. Math., 26:189–206, 1984.
  * [19] R. Khandekar, S. Rao, and U. Vazirani.  Graph partitioning using single commodity flows.  In STOC ’06, pages 385–390, 2006.
  * [20] G. Lugosi.  Concentration-of-measure inequalities, 2003.  Available at
http://www.econ.upf.edu/$\sim$lugosi/anu.ps.

  * [21] M. Rudelson.  Random vectors in the isotropic position.  J. of Functional Analysis, 163(1):60–72, 1999.
  * [22] M. Rudelson and R. Vershynin.  Sampling from large matrices: An approach through geometric functional analysis.  J. ACM, 54(4):21, 2007.
  * [23] D. A. Spielman and S.-H. Teng.  Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems.  In STOC ’04, pages 81–90, 2004.  Full version available at http://arxiv.org/abs/cs.DS/0310051.
  * [24] D. A. Spielman and S.-H. Teng.  Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems.  Available at http://www.arxiv.org/abs/cs.NA/0607105, 2006.
  * [25] D. A. Spielman and S.-H. Teng.  Spectral Sparsification of Graphs.  Available at http://arxiv.org/abs/0808.4134, 2008.