summaries: The paper characterizes the perception-distortion in the context of (image) enhancement tradeoff, complementing prior results. For example, in image super resolution, this tradeoff describes the relationship between the point-wise reconstruction quality (distortion) and how well the distribution of the reconstructions match the distribution of the high-resolution data one aims to reconstruct. The paper derives this general tradeoff explicitly and characterizes certain aspects specifically for Gaussian distributions. The theoretical results are illustrated with experiments.

summaries: Distortion-perception is the phenomenon that the better a criterion (on natural images) is optimized (for instance SNR in image denoising) the stronger the deviation to the distribution of the space of natural images. This paper characterises this phenomenon under Mean Squared Error (MSE) as the criterion under a Wasserstein bound on the conditional distribution. The result is an interpolation between the distribution of the conditional distribution and the distribution itself. An explicit formulation of the optimizer of their Distortion-perception function is provided. Simulations are made, showing that interpolating different models that approximates the quantities in their theoretical formulation can achieve better visual aspect.

summaries: The authors of this paper suggest that they show four novel contributions to the image compression literature that hold true for MSE distortion and Wasserstein-2 perception index: 1. They prove that the Distortion-perception function is always quadratic in the perception constraint P regardless of the underlying distribution 2.  The show that it is possible to construct estimators of the Distortion-perception curve from estimators at the two extremes of the tradeoff (the one that globally minimizes MSE and the one that minimizes MSE under a perfect perceptual quality constraint). 3.In the gaussian setting, they provide a closed form expression for optimal estimators and the corresponding Distortion-perception curve, they also show that this is a lower bound on the curve of any distribution having the same second-order stats. 4.They illustrate their results conclusively with super-resolution as their test case.

summaries: The paper studies the trade-off between minimizing the mean-square error (distortion) and the Wasserstein-2 distance (perception) when constructing an estimator \hat{X} of a random variable X. In particular, the work analyzes a distortion-perception function, which given the radius P of a Wasserstein-2 ball around X returns the minimal mean-square error of \hat{X} constrained to be in that ball.   The analysis reveals that for estimators with small Wasserstein-2 distance to the true distribution, one can often obtain an estimator with much better mean-square error by a simple linear interpolation in the output space.   The theoretical results are applied to deep image super-resolution, where it is shown that the perceptual quality of an estimator with small MSE can be improved by interpolating it with one having small Wasserstein-2 distance. Remarkably, the interpolated estimator often still has low MSE, while significantly lower Wasserstein-2 distance, leading to a greatly improved perceptual quality.

abstractText: The lower the distortion of an estimator, the more the distribution of its outputs generally deviates from the distribution of the signals it attempts to estimate. This phenomenon, known as the perception-distortion tradeoff, has captured significant attention in image restoration, where it implies that fidelity to ground truth images comes at the expense of perceptual quality (deviation from statistics of natural images). However, despite the increasing popularity of performing comparisons on the perception-distortion plane, there remains an important open question: what is the minimal distortion that can be achieved under a given perception constraint? In this paper, we derive a closed form expression for this distortion-perception (DP) function for the mean squared-error (MSE) distortion and the Wasserstein-2 perception index. We prove that the DP function is always quadratic, regardless of the underlying distribution. This stems from the fact that estimators on the DP curve form a geodesic in Wasserstein space. In the Gaussian setting, we further provide a closed form expression for such estimators. For general distributions, we show how these estimators can be constructed from the estimators at the two extremes of the tradeoff: The global MSE minimizer, and a minimizer of the MSE under a perfect perceptual quality constraint. The latter can be obtained as a stochastic transformation of the former.

authors:
Mohamed Abderrahmen Abid
Ihsen Hedhli
Christian Gagné

title: A generative model for hallucinating diverse versions of super resolution images

venue: arXiv preprint arXiv:2102.06624,

authors:
Luigi Ambrosio
Nicola Gigli
Giuseppe Savaré

title: Gradient flows: in metric spaces and in the space of probability measures

venue: Springer Science & Business Media,

authors:
Yuval Bahat
Tomer Michaeli

title: Explorable super resolution

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Yochai Blau
Tomer Michaeli

title: The perception-distortion tradeoff

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Yochai Blau
Roey Mechrez
Radu Timofte
Tomer Michaeli
Lihi Zelnik-Manor

title: The 2018 PIRM challenge on perceptual image super-resolution

venue: In Proceedings of the European Conference on Computer Vision (ECCV) Workshops,

title: Enhancing image quality via style transfer for single image super-resolution

venue: IEEE Signal Processing Letters,

authors:
Roy Friedman
Yair Weiss

title: Posterior sampling for image restoration using explicit patch priors

venue: arXiv preprint arXiv:2104.09895,

title: On a formula for the l2 wasserstein metric between measures on euclidean and hilbert spaces

venue: Mathematische Nachrichten,

title: Toeplitz and circulant matrices: A review

authors:
Martin Heusel
Hubert Ramsauer
Thomas Unterthiner
Bernhard Nessler
Sepp Hochreiter

title: Gans trained by a two time-scale update rule converge to a local nash equilibrium

venue: Advances in Neural Information Processing Systems,

authors:
Bahjat Kawar
Gregory Vaksman
Michael Elad

title: Stochastic image denoising by sampling from the posterior distribution

venue: arXiv preprint arXiv:2101.09552,

authors:
Martin Knott
Cyril S Smith

title: On the optimal mapping of distributions

venue: Journal of Optimization Theory and Applications,

authors:
Christian Ledig
Lucas Theis
Ferenc Huszár
Jose Caballero
Andrew Cunningham
Alejandro Acosta
Andrew Aitken
Alykhan Tejani
Johannes Totz
Zehan Wang

title: Photo-realistic single image super-resolution using a generative adversarial network

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Bee Lim
Sanghyun Son
Heewon Kim
Seungjun Nah
Kyoung Mu Lee

title: Enhanced deep residual networks for single image super-resolution

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition workshops,

authors:
Andreas Lugmayr
Martin Danelljan
Luc Van Gool
Radu Timofte

title: Srflow: Learning the super-resolution space with normalizing flow

venue: In European Conference on Computer Vision,

authors:
David Martin
Charless Fowlkes
Doron Tal
Jitendra Malik

title: A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics

venue: In Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001,

authors:
Pablo Navarrete Michelini
Dan Zhu
Hanwen Liu

title: Multi–scale recursive and perception– distortion controllable image super–resolution

authors:
Guy Ohayon
Theo Adrai
Gregory Vaksman
Michael Elad
Peyman Milanfar

title: High perceptual quality image denoising with a posterior sampling cgan

venue: arXiv preprint arXiv:2103.04192,

authors:
Felix Otto
Cédric Villani

title: Generalization of an inequality by talagrand and links with the logarithmic sobolev inequality

venue: Journal of Functional Analysis,

authors:
Victor M Panaretos
Yoav Zemel

title: An invitation to statistics in Wasserstein space

authors:
Mangal Prakash
Alexander Krull
Florian Jug

title: Divnoising: diversity denoising with fully convolutional variational autoencoders

venue: arXiv preprint arXiv:2006.06072,

authors:
Mangal Prakash
Mauricio Delbracio
Peyman Milanfar
Florian Jug

title: Removing pixel noises and spatial artifacts with generative diversity denoising methods

venue: arXiv preprint arXiv:2104.01374,

authors:
Mehdi SM Sajjadi
Bernhard Scholkopf
Michael Hirsch

title: Enhancenet: Single image super-resolution through automated texture synthesis

venue: In Proceedings of the IEEE International Conference on Computer Vision,

authors:
Tamar Rott Shaham
Tali Dekel
Tomer Michaeli

title: SinGAN: Learning a generative model from a single natural image

venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision,

authors:
Assaf Shocher
Nadav Cohen
Michal Irani

title: zero-shot” super-resolution using deep internal learning

authors:
Alon Shoshan
Roey Mechrez
Lihi Zelnik-Manor

title: Dynamic-net: Tuning the objective without re-training for synthesis tasks

title: On wasserstein geometry of gaussian measures

venue: Mathematical Society of Japan,

title: Transportation cost for gaussian and other product measures

venue: Geometric & Functional Analysis GAFA,

authors:
Dmitry Ulyanov
Andrea Vedaldi
Victor Lempitsky

title: Deep image prior

title: On the approximation of the discrete karhunen-loeve transform for stationary processes

venue: Signal Processing,

authors:
Xintao Wang
Ke Yu
Shixiang Wu
Jinjin Gu
Yihao Liu
Chao Dong
Yu Qiao
Chen Change Loy

title: ESRGAN: Enhanced super-resolution generative adversarial networks

authors:
Xintao Wang
Ke Yu
Chao Dong
Xiaoou Tang
Chen Change Loy

title: Deep network interpolation for continuous imagery effect transition

authors:
Zhen Zhang
Mianzhi Wang
Arye Nehorai

title: Optimal transport in reproducing kernel hilbert spaces: Theory and applications

venue: IEEE transactions on pattern analysis and machine intelligence,

heading: 1 Introduction

text:
Inverse problems that involve signal reconstruction from partial or noisy measurements, arise in numerous scientific domains. Examples range from medical imaging to tomography, microscopy, astronomy and audio enhancement. In many such problems it is desired to design an estimator that (i) has a small reconstruction error (low distortion), and (ii) outputs reconstructions that cannot be told apart from valid signals (good perceptual quality). Interestingly, however, it has been shown that the lower the average distortion of an estimator, the more the distribution of its outputs generally deviates from the distribution of the signals it attempts to estimate [4]. In other words, low distortion generally comes at the price of poor perceptual quality, and vice versa. This phenomenon, known as the perception-distortion tradeoff, has found particular interest in the image restoration domain (see Fig. 1), where algorithms are now commonly being evaluated using both distortion measures and perception indices [5].
Unfortunately, despite the increasing popularity of performing comparisons on the perceptiondistortion plane, the minimal distortion that can be achieved under a given perception constraint (red curve in Fig. 1) remains an open question. Blau and Michaeli [4] investigated several properties
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
of this distortion-perception function, such as monotonicity and convexity. But beyond this rather general characterization, little is known about its precise nature. In this paper, we derive a closed form expression for the distortion-perception (DP) function for the special case where distortion is measured by mean squared-error (MSE) and perception is measured by the Wasserstein-2 distance between the probability laws of the estimate and the estimand.
Our main contributions are: (i) We prove that the DP function is always quadratic in the perception constraint P , regardless of the underlying distribution (Theorem 1). (ii) We show that it is possible to construct estimators on the DP curve from the estimators at the two extremes of the tradeoff (Theorem 3): The one that globally minimizes the MSE, and a minimizer of the MSE under a perfect perceptual quality constraint. The latter can be obtained as a stochastic transformation of the former. (iii) In the Gaussian setting, we further provide a closed form expression for optimal estimators and for the corresponding DP curve (Theorems 4 and 5). We show this Gaussian DP curve is a lower bound on the DP curve of any distribution having the same second order statistics. Finally, we illustrate our results, numerically and visually, in a super-resolution setting in Section 5. The proofs of all our theorems are provided in Appendix B.
Our theoretical results shed light on several topics that are subject to much practical activity. Particularly, many recent works adress the task of diverse perceptual image reconstruction, by employing randomization among possible restorations [15, 3, 22, 1]. Commonly, such works attempt to sample from the posterior distribution of natural images given the degraded input image. This is done, for example, using priors over image patches [7], conditional generative models [18, 21], or implicit priors induced by deep denoiser networks [11]. Theoretically, posterior sampling leads to perfect perceptual quality (the restored outputs are distributed like the prior). However, a fundamental question is whether this is optimal in terms of distortion. As we show in Section 3.1, posterior sampling is often not an optimal strategy, in the sense that there exist perfect perceptual quality estimators that achieve lower distortion.
Another topic of practical interest is the ability to traverse the distortion-perception tradeoff at test time, without having to train a different model for each working point. Recently, interpolation between distortion-oriented models and perception-oriented ones, has been suggested for this end. Existing methods include interpolation in pixel space [31] or in some latent space [26], interpolation between network weights [31, 32], and style transfer between a low-distortion reconstruction and a high perceptual quality one [6]. In light of this plethora of approaches, it is natural to ask which strategy is optimal. In Section 3.2 we show that for the MSE–Wasserstein-2 tradeoff, linear interpolation in pixel space leads to optimal estimators. We also discuss a geometric connection between interpolation and the fact that estimators on the DP curve form a geodesic in Wasserstein space.

heading: 2 Problem setting and preliminaries

heading: 2.1 The distortion-perception tradeoff

text:
Let X,Y be random vectors taking values in Rnx and Rny , respectively. We consider the problem of constructing an estimator X̂ ofX based on Y . Namely, we are interested in determining a conditional distribution pX̂|Y such that X̂ constitutes a good estimate of X . For example, in the super-resolution setting shown in Fig. 1, Y is the low resolution image (left), X is the corresponding ground-truth high-resolution image (not shown), and X̂ is a super-resolution reconstruction generated from Y (e.g. the EDSR or ESRGAN estimators in the middle).
In many practical cases, the goodness of an estimator is associated with two factors: (i) the degree to which X̂ is close to X on average (low distortion), and (ii) the degree to which the distribution of X̂ is close to that of X (good perceptual quality). An important question, then, is what is the minimal distortion that can be achieved under a given level of perceptual quality? and how can we construct estimators that achieve this lower bound? In mathematical language, we are interested in analyzing the distortion-perception (DP) function (defined similarly to the perception-distortion function of [4])
D(P ) = min pX̂|Y
{ E[d(X, X̂)] : dp(pX , pX̂) ≤ P } . (1)
Here, d : Rnx × Rnx → R+ ∪ {0} is some distortion criterion, dp(·, ·) is some divergence between probability measures, and pX̂ is the probability measure on R nx induced by pX̂|Y and pY . The
expectation is taken w.r.t. the measure pXX̂ induced by pX̂|Y and pXY , where we assume that X̂ is independent of X given Y .
As discussed in [4], the function D(P ) is monotonically non-increasing and is convex whenever dp(·, ·) is convex in its second argument (which is the case for most popular divergences). However, without further concrete assumptions on the distortion measure d(·, ·) and the perception index dp(·, ·), little can be said about the precise nature of D(P ). Here, we focus our attention on the squared-error distortion d(x, x̂) = ‖x−x̂‖2 and the Wasserstein-2 distance dp(pX , pX̂) = W2(pX , pX̂), with which (1) reads
D(P ) = min pX̂|Y
{ E[‖X − X̂‖2] : W2(pX , pX̂) ≤ P } . (2)
We assume that all distributions have finite first and second moments. In addition, from Theorem 3 below it will follow that the minimum is indeed attained, so that (2) is well defined.
It is well known that the estimator minimizing the mean squared error (MSE) without any constraints, is given by X∗ = E[X|Y ]. This implies that D(P ) monotonically decreases until P reaches P ∗ ,W2(pX , pX∗), beyond which point D(P ) takes the constant value D∗ , E[‖X −X∗‖2]. This is illustrated in Fig. 2. It is also known that D(0) ≤ 2D∗ since the posterior sampling estimator pX̂|Y = pX|Y achieves W2(pX , pX̂) = 0 and E[‖X − X̂‖2] = 2D∗ [4]. However, apart from these rather general properties, the precise shape of the DP curve has not been determined to date, and neither have the estimators that achieve the optimum in (2). This is our goal in this paper.

heading: 2.2 The Wasserstein and Gelbrich Distances

text:
Before we present our main results, we briefly survey a few properties of the Wasserstein distance, mostly taken from [20]. The Wasserstein-p (p ≥ 1) distance between measures µ and γ on a separable Banach space X with norm ‖ · ‖ is defined by
W pp (µ, γ) , inf { E(U,V )∼ν [‖U − V ‖p] : ν ∈ Π(µ, γ) } , (3)
where Π(µ, γ) is the set of all probabilities on X × X with marginals µ and γ. A joint probability ν achieving the optimum in (3) is often referred to as optimal plan. The Wasserstein space of probability measures is defined as
Wp(X ) , { γ : ∫
X ‖x‖pdγ <∞
} ,
and Wp constitutes a metric onWp(X ). For any (m1,Σ1), (m2,Σ2) ∈ Rd × Sd+ (where Sd+ is the set of symmetric positive semidefinite matrices in Rd×d), the Gelbrich distance is defined as
G2((m1,Σ1), (m2,Σ2)) , ‖m1 −m2‖22 + Tr { Σ1 + Σ2 − 2 ( Σ 1 2 1 Σ2Σ 1 2 1 ) 1 2 } . (4)
The root of a PSD matrix is always taken to be PSD. For any two probability measures µ1, µ2 on Rd with means and covariances (m1,Σ1), (m2,Σ2), from [8, Thm. 2.1] we have that
W 22 (µ1, µ2) ≥ G2((m1,Σ1), (m2,Σ2)). (5)
When µ1 = N (m1,Σ1) and µ2 = N (m2,Σ2) are Gaussian distributions on Rd, we have that W2(µ1, µ2) = G((m1,Σ1), (m2,Σ2)). This equality is obvious for non-singular measures but is true for any two Gaussian distributions [20, p. 18]. If Σ1 and Σ2 are non-singular, then the distribution attaining the optimum in (3) corresponds to
U ∼ N (m1,Σ1), V = m2 + T1→2(U −m1), (6)
where
T1→2 = Σ − 12 1 ( Σ 1 2 1 Σ2Σ 1 2 1 ) 1 2 Σ − 12 1 (7)
is the optimal transformation pushing forward from N (0,Σ1) to N (0,Σ2) [12]. This transformation satisfies Σ2 = T1→2Σ1T1→2. For a discussion on singular distributions, please see App. A.

heading: 3 Main results

heading: 3.1 The MSE–Wasserstein-2 tradeoff

text:
The DP function (2) depends, of course, on the underlying joint probability pXY of the signal X and measurements Y . Our first key result is that this dependence can be expressed solely in terms of D∗ and P ∗. In other words, knowing the distortion and perception index attained by the minimum MSE estimator X∗, suffices for determining D(P ) for any P .
Theorem 1 (The DP function). The DP function (2) is given by
D(P ) = D∗ + [(P ∗ − P )+]2 , (8) where (x)+ = max(0, x). Furthermore, an estimator achieving perception index P and distortion D(P ) can always be constructed by applying a (possibly stochastic) transformation to X∗.
Theorem 1 is of practical importance because in many cases constructing an estimator that achieves a low MSE (i.e. an approximation of X∗) is a rather simple task. This is the case, for example, in image restoration with deep neural networks. There, it is common practice to train a network by minimizing its average squared error on a training set. Measuring the MSE of such a network on a large test set provides an approximation for D∗. We can also obtain an approximation of at least a lower bound on P ∗ by estimating the second order statistics of X and X∗. Specifically, recall that P ∗ is lower bounded by the Gelbrich distance between (mX ,ΣX) and (mX∗ ,ΣX∗), which is given by (G∗)2 , Tr{ΣX + ΣX∗ − 2(Σ1/2X ΣX∗Σ 1/2 X )
1/2} (see (5)). Given approximations for D∗ and G∗, we can approximate a lower bound on the DP function for any P ,
D(P ) ≥ D∗ + [(G∗ − P )+]2. (9) The bound is attained when X and Y are jointly Gaussian.
Uniqueness A remark is in place regarding the uniqueness of an estimator achieving (8). As we discuss below, what defines an optimal estimator X̂ is its joint distribution with X∗. This joint distribution may not be unique, in which case the optimal estimator is not unique. Moreover, even if pX̂X∗ is unique, the uniqueness of the estimator is not guaranteed because there may be different conditional distributions pX̂|Y that lead to the same optimal pX̂X∗ . In other words, given the optimal pX̂X∗ , one can choose any joint probability pX̂Y X∗ that has marginals pX̂X∗ and pY X∗ . One option is to take the estimator X̂ to be a (possibly stochastic) transformation of X∗, namely pX̂|Y = pX̂|X∗pX∗|Y . But there may be other options. In cases where either Y or X̂ are a deterministic transformation of X∗ (e.g. when X∗ has a density, or is an invertible function of Y ), there is a unique joint distribution pX̂Y X∗ with the given marginals [2, Lemma 5.3.2]. In this case, if pX̂X∗ is unique then so is the estimator pX̂|Y .
Randomness Under the settings of image restoration, many methods encourage diversity in their output by adding randomness [15, 3, 22]. In our setting, we may ask under what conditions there exists an optimal estimator X̂ which is a deterministic function of Y . For example, when pY = δ0 but X has some non-atomic distribution, it is clear that no deterministic function of Y can attain perfect perceptual quality. It turns out that a sufficient condition for the optimal X̂ to be a deterministic function of Y is that X∗ have a density. We discuss this in App. B and explicitly illustrate it in the Gaussian case (see Sec. 3.3), where if X∗ has a non-singular covariance matrix then X̂ is a deterministic function of Y .
When is posterior sampling optimal? Many recent image restoration methods attempt to produce diverse high perceptual quality reconstructions by sampling from the posterior distribution pX|Y [7, 18, 11]. As discussed in [4], the posterior sampling estimator attains a perception index of 0 (namely W2(pX , pX̂) = 0) and distortion 2D
∗. But an interesting question is: when is this strategy optimal? In other words, in what cases do we have that the DP function at P = 0 equals precisely 2D∗ and is not strictly smaller? Note from the definition of the Wasserstein distance (3), that (P ∗)2 = W 22 (pX , pX∗) ≤ E[‖X −X∗‖2] = D∗. Using this in (8) shows that the DP function at P = 0 is upper bounded by D(0) = D∗ + (P ∗)2 ≤ 2D∗, (10) and the upper bound is attained when (P ∗)2 = D∗. To see when this happens, observe that
Tr { ΣX + ΣX∗ − 2(Σ 1 2 XΣX∗Σ 1 2 X) 1 2 } = (G∗)2 ≤ (P ∗)2 ≤ D∗ = Tr{ΣX − ΣX∗}. (11)
We can see that when Tr{ΣX∗} = Tr{(Σ1/2X ΣX∗Σ 1/2 X ) 1/2}, the leftmost and rightmost sides become equal, and thus (P ∗)2 = D∗. To understand the meaning of this condition, let us focus on the case where ΣX and ΣX∗ are jointly diagonalizable. This is a reasonable assumption for natural images,
where shift-invariance induces diagonalization by the Fourier basis [30]. In this case, the condition can be written in terms of the eigenvalues of the matrices, namely ∑ i λi(ΣX∗) = ∑ i √ λi(ΣX∗)λi(ΣX). This condition is satisfied when each λi(ΣX∗) equals either λi(ΣX) or 0. Namely, the ith eigenvalue of the error covariance of X∗, which is given by ΣX −ΣX∗ , is either λi(ΣX) or 0. We conclude that posterior sampling is optimal when there exists a subspace S spanned by some of the eigenvectors of ΣX , such that the projection of X onto S can be recovered from Y with zero error, but the projection of X onto S⊥ cannot be recovered at all (the optimal estimator is trivial). This is likely not the case in most practical scenarios. Therefore, it seems that posterior sampling is often not optimal. That is, posterior sampling can be improved upon in terms of MSE without any sacrifice in perceptual quality.

heading: 3.2 Optimal estimators

text:
While Theorem 1 reveals the shape of the DP function, it does not provide a recipe for constructing optimal estimators on the DP tradeoff. We now discuss the nature of such estimators.
Our first observation is that since X̂ is independent of X given Y , its MSE can be decomposed as E[‖X − X̂‖2] = E[‖X −X∗‖2 + E[‖X∗ − X̂‖2] (see App. B). Therefore, the DP function (2) can be equivalently written as
D(P ) = D∗ + min pX̂|Y
{ E[‖X̂ −X∗‖2] : W2(pX , pX̂) ≤ P } . (12)
Note that the objective in (12) depends on the MSE between X̂ and X∗, so that we can perform the minimization on pX̂|X∗ rather than on pX̂|Y (once we determine the optimal pX̂|X∗ we can construct a consistent pX̂|Y as discussed above).
Now, let us start by examining the leftmost side of the curve D(P ), which corresponds to a perfect perceptual quality estimator (i.e. P = 0). In this case, the constraint becomes pX̂ = pX . Therefore,
D(0) = D∗ + min pX̂X∗
{ E[‖X̂ −X∗‖2] : pX̂X∗ ∈ Π(pX , pX∗) } , (13)
where Π(pX , pX∗) is the set of all probabilities on Rnx × Rnx with marginals pX , pX∗ . One may readily recognize this as the optimization problem underlying the Wasserstein-2 distance between pX and pX∗ . This leads us to the following conclusion.
Theorem 2 (Optimal estimator for P = 0). Let X̂0 be an estimator achieving perception index 0 and MSE D(0). Then its joint distribution with X∗ attains the optimum in the definition of W2(pX , pX∗). Namely, pX̂0X∗ is an optimal plan between pX and pX∗ .
Having understood the estimator X̂0 at the leftmost end of the tradeoff, we now turn to study optimal estimators for arbitrary P . Interestingly, we can show that Problem (12) is equivalent to (see App. B)
D(P ) = D∗ + min pX̂
{ W 22 (pX̂ , pX∗) : W2(pX̂ , pX) ≤ P } . (14)
Namely, an optimal pX̂ is closest to pX∗ among all distributions within a ball of radius P around pX , as illustrated in Fig. 2. Moreover, pX̂X∗ is an optimal plan between pX̂ and pX∗ . As it turns out, this somewhat abstract viewpoint leads to a rather practical construction for X̂ from the estimators X̂0 and X∗ at the two extremes of the tradeoff. Specifically, we have the following result.
Theorem 3 (Optimal estimators for arbitrary P ). Let X̂0 be an estimator achieving perception index 0 and MSE D(0). Then for any P ∈ [0, P ∗], the estimator
X̂P =
( 1− P
P ∗
) X̂0 + P
P ∗ X∗ (15)
is optimal for perception index P . Namely, it achieves perception index P and distortion D(P ).
Theorem 3 has important implications for perceptual signal restoration. For example, in the task of image super-resolution, there exist many deep network based methods that achieve a low MSE [14, 29, 25]. These provide an approximation for X∗. Moreover, there is an abundance of methods that achieve good perceptual quality at the price of a reasonable degradation in MSE (often by
incorporating a GAN-based loss) [13, 31, 24]. These constitute approximations for X̂0. However, achieving results that strike other prescribed balances between MSE and perceptual quality commonly require training a different model for each setting. Shoshan et al. [26] and Navarrete Michelini et al. [17] tried to address this difficulty by introducing new training techniques that allow traversing the distortion-perception tradeoff at test time. However, Theorem 3 shows that such specialized training methods are not required in our setting. Having a model that leads to low MSE and one that leads to good perceptual quality, it is possible to construct any other estimator on the DP tradeoff, by simply averaging the outputs of these two models with appropriate weights. We illustrate this in Sec. 5.

heading: 3.3 The Gaussian setting

text:
When X and Y are jointly Gaussian, it is well known that the minimum MSE estimator X∗ is a linear function of the measurements Y . However, it is not a-priori clear whether all estimators along the DP tradeoff are linear in this case, and what kind of randomness they possess. As we now show, equipped with Theorem 3, we can obtain closed form expressions for optimal estimators for any P . For simplicity, we assume here that X and Y have zero means and that ΣX ,ΣY 0. It is instructive to start by considering the simple case, where ΣX∗ is non-singular (in Theorem 4 below we address the more general case of a possibly singular ΣX∗ ). It is well known that
X∗ = ΣXY Σ −1 Y Y, ΣX∗ = ΣXY Σ −1 Y ΣY X . (16)
Now, since we assumed that ΣX ,ΣX∗ 0, we have from Theorem 2 and (6),(7) that
X̂0 = Σ − 12 X∗
( Σ 1 2
X∗ΣXΣ 1 2 X∗
) 1 2
Σ − 12 X∗X ∗. (17)
Finally, we know that P ∗ = G∗, which is given by the left-hand side of (11). Substituting these expressions into (15), we obtain that an optimal estimator for perception P ∈ [0, G∗] is given by
X̂P =
(( 1− P
G∗
) Σ − 12 X∗ ( Σ 1 2 X∗ΣXΣ 1 2 X∗ ) 1 2 Σ − 12 X∗ + P
G∗ I
) ΣXY Σ −1 Y Y. (18)
As can be seen, this optimal estimator is a deterministic linear transformation of Y for any P .
The setting just described does not cover the case where Y is of lower dimensionality than X because in that case ΣX∗ is necessarily singular (it is a nx × nx matrix of rank at most ny; see (16)). In this case, any deterministic linear function of Y would result in an estimator X̂ with a rank-ny covariance. Obviously, the distribution of such an estimator cannot be arbitrarily close to that of X , whose covariance has rank nx. What is the optimal estimator in this more general setting, then? Theorem 4 (Optimal estimators in the Gaussian case). Assume X and Y are zero-mean jointly Gaussian random vectors with ΣX ,ΣY 0. Denote T ∗ , TpX→pX∗ = Σ −1/2 X (Σ 1/2 X ΣX∗Σ 1/2 X ) 1/2Σ −1/2 X . Then for any P ∈ [0, G∗], an estimator with perception index P and MSE D(P ) can be constructed as
X̂P =
(( 1− P
G∗
) Σ 1 2
X
( Σ 1 2
XΣX∗Σ 1 2 X
) 1 2
Σ − 12 X Σ † X∗ + P
G∗ I
) ΣXY Σ −1 Y Y + ( 1− P
G∗
) W, (19)
whereW is a zero-mean Gaussian noise with covariance ΣW = Σ 1/2 X (I−Σ 1/2 X T ∗Σ†X∗T ∗Σ 1/2 X )Σ 1/2 X , which is independent of Y,X , and Σ†X∗ is the pseudo-inverse of ΣX∗ .
Note that in this case, we indeed have a random noise component that shapes the covariance of X̂P to become closer to ΣX as P gets closer to 0. It can be shown (see App. B) that when ΣX∗ is invertible, ΣW = 0 and (19) reduces to (18). Also note that, as in (18), the dependence of X̂P on Y in (19) is only through X∗ = ΣXY Σ−1Y Y .
As mentioned in Sec. 3.1, the optimal estimator is generally not unique. Interestingly, in the Gaussian setting we can explicitly characterize a set of optimal estimators. Theorem 5 (A set of optimal estimators in the Gaussian case). Consider the setting of Theorem 4. Let ΣX̂0Y ∈ R nx×ny satisfy
ΣX̂0Y Σ −1 Y ΣY X = Σ
1 2 X(Σ 1 2 XΣX∗Σ 1 2 X) 1 2 Σ − 12 X , (20)
and W0 be a zero-mean Gaussian noise with covariance
ΣW0 = ΣX − ΣX̂0Y Σ −1 Y Σ T X̂0Y
0 (21)
that is independent of X,Y . Then, for any P ∈ [0, G∗], an optimal estimator with perception index P can be obtained by
X̂P =
(( 1− P
G∗
) ΣX̂0Y + P
G∗ ΣXY
) Σ−1Y Y + ( 1− P
G∗
) W0. (22)
The estimator given in (19) is one solution to (20)-(21), but is generally not unique.

heading: 3.4 A Comment on the MSE–Wasserstein-p tradeoff

text: While our results concern the MSE−W2 tradeoff, they can be used to draw conclusions regarding the DP tradeoff with other divergences. In particular, (8) constitutes a lower bound on the MSEWasserstein-p tradeoff for any p ≥ 2. Furthermore, we can show that the MSE−W1 DP function is lower bounded by D∗ + [(P ∗1 − P )+]2, where P ∗1 ,W1(pX , pX∗). Note that at the point P = 0, the DP function coincides with (8) for any plausible divergence. For a detailed discussion, we kindly refer the reader to the Appendix.

heading: 4 A geometric perspective on the distortion-perception tradeoff

text:
In this section we provide a geometric point of view on our main results. Specifically, we show that the results of Theorems 1 and 3 are a consequence of a more general geometric property of the space W2(Rnx). In the Gaussian case, this is simplified to a geometry of covariance matrices. Recall from (14) that the optimal pX̂ is the one closest to pX∗ (in terms of Wasserstein distance) among all measures at a distance P from pX . This implies that to determine pX̂ , we should traverse the geodesic between pX∗ and pX until reaching a distance of P from pX . Furthermore, pX̂X∗ should be the optimal plan between pX̂ and pX∗ . Interestingly, geodesics in Wasserstein spaces take a particularly simple form, and their explicit construction also turns out to satisfy the latter requirement. Specifically, let γ, µ be measures inW2(Rd), let ν ∈ Π(γ, µ) be an optimal plan attaining W2(γ, µ), and let πi denote the projection πi : Rd × Rd → Rd such that πi((x1, x2)) = xi, i = 1, 2. Then, the curve γt , [(1− t)π1 + tπ2] #ν, t ∈ [0, 1] (23) is a constant-speed geodesic from γ to µ inW2(Rd) [2], where # is the push-forward operation1. Particularly, W2(γt, γs) = |t− s|W2(γ, µ), (24) and it follows that W2(γt, γ) = tW2(γ, µ) and W2(γt, µ) = (1 − t)W2(γ, µ). Furthermore, if γt, t ∈ [0, 1] is a constant-speed geodesic with γ0 = γ, γ1 = µ, then the optimal plans between γ, γt and between γt, µ are given by
[π1, (1− t)π1 + tπ2] #ν, [(1− t)π1 + tπ2, π2] #ν, (25) respectively, where ν ∈ Π(γ, µ) is some optimal plan. Applying (23) to (X̂0, X∗) ∼ ν with t = P/P ∗, we obtain (15), where we show that the obtained estimator achieves E[‖X̂P −X∗‖2] = (1− t)2W 22 (pX , pX∗). This explains the result of Theorem 3. It is worth mentioning that this geometric interpretation is simplified under some common settings. For example, when γ is absolutely continuous (w.r.t. the Lebesgue measure), we have a measurable map Tγ→µ which is the solution to the optimal transport problem with the quadratic cost [20, Thm 1.6.2, p.16]. The geodesic (23) then takes the form
γt = [Id+ t(Tγ→µ − Id)]#γ, t ∈ [0, 1]. (26)
Therefore, in our setting, if γ = pX∗ has a density, then we can obtain X̂P by the deterministic transformation [X∗+ ( 1− PP∗ ) (TpX∗→pX (X
∗)−X∗)] (see Remark about randomness in Sec. 3.1). 1For measures γ, µ on X ,Y , we say that a measurable transform T : X → Y pushes γ forward to µ (denoted
T#γ = µ) iff γ(T−1(B)) = µ(B) for any measurable B ⊆ Y.
Further simplification arises when γ, µ are centered non-singular Gaussian measures, in which case Tγ→µ is the linear and symmetric transformation (7). Then, γt is a Gaussian measure with covariance Σγt = TtΣγTt, where Tt , [I + t(Tγ→µ − I)]. Therefore, in the Gaussian case, the shortest path (23) between distributions is reduced to a trajectory in the geometry of covariance matrices induced by the Gelbrich distance [27]. If additionally Σγ and Σµ commute, then the Gelbrich distance is further reduced to the `2-distance between matrices, as we discuss in App. D.

heading: 5 Numerical illustration

text:
We now experimentally illustrate the results of Theorems 1 and 3. We compute distortion and perception indices for 13 super resolution algorithms in a 4× magnification task on the BSD100 dataset2 [16]. We then demonstrate the efficiency of approximating the lower bound (9) on the distortion D(P ), and of the estimators suggested in (15), in this practical setting. The evaluated algorithms include EDSR [14], ESRGAN [31], SinGAN [24], ZSSR [25], DIP [29], SRResNet variants which optimize MSE and VGG2,2, SRGAN variants which optimize MSE, VGG2,2 and VGG5,4 in addition to an adversarial loss [13], ENet [23] (“PAT” and “E” variants), and the stochastic explorable SR method of [3] (ExpSR). Low resolution images were obtained by 4× downsampling of BSD100 images using a bicubic kernel.
In Fig. 3 we plot each method on the distortion-perception plane. In the left pane, we consider natural (and reconstructed) images to be stationary random sources, and use 9× 9 patches (totally 1.6× 106 patches) to empirically estimate the mean and covariance matrix for the ground-truth images, and for the reconstructions produced by each method. We then use the estimated Gelbrich distances (4) between the patch distribution of each method and that of ground-truth images, as a perceptual quality index. Recall this is a lower bound on the Wasserstein distance. In the right pane of Fig. 3, we measure perception using the popular FID index [10], which relies on the Fréchet distance between deep feature distributions of ground-truth and reconstructed images (assuming they are normally distributed). FID is known to correlate well with visual quality, and while it is not directly related to our theory, we can see a qualitatively similar behavior to that depicted in the left pane.
We consider the EDSR method [14] to constitute a good approximation for the minimum MSE estimator X∗ since it achieves the lowest MSE among the evaluated methods. We therefore estimate the lower bound (9) as D̂(P ) = DEDSR + [(PEDSR − P )+]2 , where DEDSR is the MSE of EDSR, and PEDSR is the estimated Gelbrich distance between EDSR reconstructions and ground-truth images. Note the unoccupied region under the estimated curve in Fig. 3, which is indeed unattainable according to the theory.
The figure also shows 9 estimators X̂t, which we construct by interpolation between EDSR and ESRGAN, X̂t = tXEDSR + (1− t)XESRGAN with t ∈ [0, 1]. We observe that estimators constructed using these two extreme points are closer to the optimal DP tradeoff than the other evaluated methods. This is true both for the Gelbrich perception index and for FID. In Fig. 4 we present a visual comparison between SRGAN-VGG2,2 [13] and our interpolated estimator X̂0.12. Both achieve roughly the same RMSE distortion (18.08 for SRGAN, 18.14 for X̂0.12), but our estimator achieves a lower perception index. Namely, by using interpolation, we manage to achieve improvement in perceptual quality, without degradation in distortion. The improvement in visual quality is also apparent in the figure. Additional visual comparisons including more points along the DP curve and ground-truth images can be found in the Appendix.

heading: 6 Conclusion

text:
In this paper we provide a full characterization of the distortion-perception tradeoff for the MSE distortion and the Wasserstein-2 perception index. We show that optimal estimators are obtained by interpolation between the minimum MSE estimator and an optimal perfect perceptual quality estimator. In the Gaussian case, we explicitly formulate these estimators. To the best of our knowledge, this is the first work to derive such closed-form expressions. Our work paves the way towards fully
2All codes are freely available and provided by the authors.
S R
G A N V G G 2, 2
X̂ 0. 12
E S
R
G
A
N
E D S
R L ow R es .
G ro
u n
d .
4853 1420 4592
Figure 4: A visual comparison between estimators with approximately the same MSE. Upper: SRGAN-VGG2,2. Lower: X̂0.12, an interpolation between EDSR and ESRGAN using t = 0.12. Observe the improvement in perceptual quality, without any significant degradation in distortion.
understanding the DP tradeoff under more general distortions and perceptual criteria, and bridging between fidelity and visual quality at test-time, without training different models.
Broader impact Synthesis of photo-realistic visual contents may raise concerns of inappropriate and malicious use. This is true for image generation in general (e.g. with GANs), but to some extent also for image restoration tasks like super-resolution. However, even without malicious intent, the outputs of a high perceptual quality algorithm can often not be very close to the ground truth images. In this paper we quantify this effect, by studying the best similarity (lowest distortion) one can hope to achieve with an algorithm having a prescribed level of perceptual quality.
Acknoledgments This work was partially supported by grants 451/17 and 852/17 from the Israel Science Foundation, by the Ollendorff Center of the Viterbi Faculty of Electrical and Computer Engineering at the Technion, and by the Skillman chair in biomedical sciences.
10

title: A Theory of the Distortion-Perception Tradeoff in Wasserstein Space


summaries: This paper proposes a means to encode text feature for nodes in textual graphs, where a layerwise aggregation module (implemented as a multi-head self-attention) is appended after each Transformer encoder block that aggregates the hidden representations of (sampled) neighbor nodes. The produced contextual representations are dispatched to each node for the computation of next Transformer encoder block. To mitigate the possible model degradation issue that the aggregation module might be insufficiently trained, the authors also propose a two-stage training schedule where the model is first trained on nodes with corrupted inputs until convergence and then trained on normal data.

summaries: For representation learning on textual graphs, Cascaded Transformers-GNN architectures have been used, as language models and GNN are independently and consecutively deployed. The authors' claims, however, this approach has a limitation of information fusion of text encoding and graph structures. The authors proposed GNN-nested Transformers named as GraphFormers, where GNN components are nested alongside the transformer layers of language models. Also, the author proposed a progressive learning strategy and unidirectional graph attention to effectively train the graph network modules. The efficacy of the GraphFormers is demonstrated on 3 textual graph datasets (DBLP, Wiki, and Product Ads datasets), achieving SOTA performance.

summaries: The paper proposes GraphFormer, an architecture built on top of GAT and Transformers for textual graphs. The motivation behind the architecture is that the existing techniques on textual graphs involve a cascade process where the nodes are first encoded using a language model after which a GNN is applied. With GraphFormers, the graph aggregation and encoding can happen iteratively, allowing for better contextualization of nodes with text like “notes on transformers” since transformers can be interpreted as ML models or electrical devices depending on the surrounding context.  The authors also lay out a 2-step training procedure whereby they first train on a version of the graph with injected noise via link prediction before training on the actual graph. The motivation behind this is given as the fact that training on the graph with injected noise makes the GNN component of the GraphFormer model more robust without which the transformer part will dominate.

summaries: This paper proposes GraphFormers for text graph tasks where GNNs are nested in each layer of the transformer-based pretrained language model. In this way, each node can appropriate graph structure to build semantic representations more effectively. Two-stage progressive training and unidirectional graph aggregation are further proposed to improve representation quality and avoid unnecessary computation. They use three real-world million-scale textual graph datasets (DBMLP, Wikidata, Product Graph) and demonstrate consistent improvements compared with traditional cascaded transformers-GNN models.

abstractText: The representation learning on textual graph is to generate low-dimensional embeddings for the nodes based on the individual textual features and the neighbourhood information. Recent breakthroughs on pretrained language models and graph neural networks push forward the development of corresponding techniques. The existing works mainly rely on the cascaded model architecture: the textual features of nodes are independently encoded by language models at first; the textual embeddings are aggregated by graph neural networks afterwards. However, the above architecture is limited due to the independent modeling of textual features. In this work, we propose GraphFormers, where layerwise GNN components are nested alongside the transformer blocks of language models. With the proposed architecture, the text encoding and the graph aggregation are fused into an iterative workflow, making each node’s semantic accurately comprehended from the global perspective. In addition, a progressive learning strategy is introduced, where the model is successively trained on manipulated data and original data to reinforce its capability of integrating information on graph. Extensive evaluations are conducted on three large-scale benchmark datasets, where GraphFormers outperform the SOTA baselines with comparable running efficiency. The source code is released at https://github.com/microsoft/GraphFormers .

authors:
Songhao Piao
Ming Zhou

title: Unilmv2: Pseudo-masked language models for unified 8https://support.google.com/adsense/answer/190515?hl=en 9https://support.google.com/google-ads/answer/116495?hl=en

authors:
Yoshua Bengio
Jérôme Louradour
Ronan Collobert
Jason Weston.

title: Curriculum learning

venue: Proceedings of the 26th annual international conference on machine learning, pages 41–48.

authors:
Tom B Brown
Benjamin Mann
Nick Ryder
Melanie Subbiah
Jared Kaplan
Prafulla Dhariwal
Arvind Neelakantan
Pranav Shyam
Girish Sastry
Amanda Askell

title: Language models are few-shot learners. arXiv preprint arXiv:2005.14165

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova.

title: Bert: Pre-training of deep bidirectional transformers for language understanding

venue: arXiv preprint arXiv:1810.04805.

authors:
Tianyu Gao
Xingcheng Yao
Danqi Chen.

title: Simcse: Simple contrastive learning of sentence embeddings

venue: arXiv preprint arXiv:2104.08821.

authors:
Will Hamilton
Zhitao Ying
Jure Leskovec.

title: Inductive representation learning on large graphs

venue: Advances in neural information processing systems, pages 1024–1034.

authors:
William L Hamilton
Rex Ying
Jure Leskovec.

title: Representation learning on graphs: Methods and applications

venue: arXiv preprint arXiv:1709.05584.

authors:
Ziniu Hu
Yuxiao Dong
Kuansan Wang
Kai-Wei Chang
Yizhou Sun.

title: Gpt-gnn: Generative pre-training of graph neural networks

venue: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1857–1867.

authors:
Vladimir Karpukhin
Barlas Oğuz
Sewon Min
Ledell Wu
Sergey Edunov
Danqi Chen
Wentau Yih.

title: Dense passage retrieval for open-domain question answering

venue: arXiv preprint arXiv:2004.04906.

authors:
Thomas N Kipf
Max Welling.

title: Semi-supervised classification with graph convolutional networks

venue: arXiv preprint arXiv:1609.02907.

authors:
Chaozhuo Li
Bochen Pang
Yuming Liu
Hao Sun
Zheng Liu
Xing Xie
Tianqi Yang
Yanling Cui
Liangjie Zhang
Qi Zhang.

title: Adsgnn: Behavior-graph augmented relevance modeling in sponsored search

venue: arXiv preprint arXiv:2104.12080.

authors:
Yinhan Liu
Myle Ott
Naman Goyal
Jingfei Du
Mandar Joshi
Danqi Chen
Omer Levy
Mike Lewis
Luke Zettlemoyer
Veselin Stoyanov.

title: Roberta: A robustly optimized bert pretraining approach

venue: arXiv preprint arXiv:1907.11692.

authors:
Zhenghao Liu
Chenyan Xiong
Maosong Sun
Zhiyuan Liu.

title: Fine-grained fact verification with kernel graph attention network

venue: arXiv preprint arXiv:1910.09796.

authors:
Yi Luan
Jacob Eisenstein
Kristina Toutanova
Michael Collins.

title: Sparse, dense, and attentional representations for text retrieval

venue: arXiv preprint arXiv:2005.00181.

authors:
Tomas Mikolov
Ilya Sutskever
Kai Chen
Greg Corrado
Jeffrey Dean.

title: Distributed representations of words and phrases and their compositionality

venue: arXiv preprint arXiv:1310.4546.

authors:
Jeffrey Pennington
Richard Socher
Christopher D Manning.

title: Glove: Global vectors for word representation

authors:
Matthew E Peters
Mark Neumann
Mohit Iyyer
Matt Gardner
Christopher Clark
Kenton Lee
Luke Zettlemoyer.

title: Deep contextualized word representations

venue: arXiv preprint arXiv:1802.05365.

authors:
Alec Radford
Karthik Narasimhan
Tim Salimans
Ilya Sutskever

title: Improving language understanding by generative pre-training

authors:
Colin Raffel
Noam Shazeer
Adam Roberts
Katherine Lee
Sharan Narang
Michael Matena
Yanqi Zhou
Wei Li
Peter J Liu.

title: Exploring the limits of transfer learning with a unified text-to-text transformer

venue: arXiv preprint arXiv:1910.10683.

authors:
Samyam Rajbhandari
Jeff Rasley
Olatunji Ruwase
Yuxiong He

title: Zero: Memory optimizations toward training trillion parameter models

venue: In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis,

authors:
Nils Reimers
Iryna Gurevych.

title: Sentence-bert: Sentence embeddings using siamese bertnetworks

venue: arXiv preprint arXiv:1908.10084.

authors:
Jianlin Su
Jiarun Cao
Weijie Liu
Yangyiwen Ou.

title: Whitening sentence representations for better semantics and faster retrieval

venue: arXiv preprint arXiv:2103.15316.

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Lukasz Kaiser
Illia Polosukhin.

title: Attention is all you need

venue: arXiv preprint arXiv:1706.03762.

authors:
Petar Veličković
Guillem Cucurull
Arantxa Casanova
Adriana Romero
Pietro Lio
Yoshua Bengio.

title: Graph attention networks

venue: International Conference on Learning Representations (ICLR).

authors:
Chenguang Wang
Yangqiu Song
Haoran Li
Ming Zhang
Jiawei Han.

title: Text classification with heterogeneous information network kernels

venue: Proceedings of the AAAI Conference on Artificial Intelligence, volume 30.

authors:
Jizhe Wang
Pipei Huang
Huan Zhao
Zhibo Zhang
Binqiang Zhao
Dik Lun Lee.

title: Billionscale commodity embedding for e-commerce recommendation in alibaba

venue: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 839–848.

authors:
Suhang Wang
Jiliang Tang
Charu Aggarwal
Huan Liu.

title: Linked document embedding for classification

venue: Proceedings of the 25th ACM international on conference on information and knowledge management, pages 115–124.

authors:
Wenlin Wang
Chenyang Tao
Zhe Gan
Guoyin Wang
Liqun Chen
Xinyuan Zhang
Ruiyi Zhang
Qian Yang
Ricardo Henao
Lawrence Carin.

title: Improving textual network learning with variational homophilic embeddings

venue: arXiv preprint arXiv:1909.13456.

authors:
Xiaozhi Wang
Tianyu Gao
Zhaocheng Zhu
Zhiyuan Liu
Juanzi Li
Jian Tang.

title: Kepler: A unified model for knowledge embedding and pre-trained language representation

venue: arXiv preprint arXiv:1911.06136.

authors:
Yonghui Wu
Mike Schuster
Zhifeng Chen
Quoc V Le
Mohammad Norouzi
Wolfgang Macherey
Maxim Krikun
Yuan Cao
Qin Gao
Klaus Macherey

title: 2016. Google’s neural machine translation system: Bridging the gap between human and machine translation

venue: arXiv preprint arXiv:1609.08144

authors:
Keyulu Xu
Weihua Hu
Jure Leskovec
Stefanie Jegelka

title: How powerful are graph neural networks? arXiv preprint arXiv:1810.00826

authors:
Zenan Xu
Qinliang Su
Xiaojun Quan
Weijia Zhang.

title: A deep neural information fusion architecture for textual network embeddings

venue: arXiv preprint arXiv:1908.11057.

authors:
Cheng Yang
Zhiyuan Liu
Deli Zhao
Maosong Sun
Edward Y Chang.

title: Network representation learning with rich text information

venue: IJCAI, volume 2015, pages 2111–2117.

authors:
Zhilin Yang
Zihang Dai
Yiming Yang
Jaime Carbonell
Ruslan Salakhutdinov
Quoc V Le.

title: Xlnet: Generalized autoregressive pretraining for language understanding

venue: arXiv preprint arXiv:1906.08237.

authors:
Michihiro Yasunaga
Rui Zhang
Kshitijh Meelu
Ayush Pareek
Krishnan Srinivasan
Dragomir Radev.

title: Graph-based neural multi-document summarization

venue: arXiv preprint arXiv:1706.06681.

authors:
Rex Ying
Ruining He
Kaifeng Chen
Pong Eksombatchai
William L Hamilton
Jure Leskovec.

title: Graph convolutional neural networks for web-scale recommender systems

venue: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 974–983.

authors:
Jie Zhou
Ganqu Cui
Shengding Hu
Zhengyan Zhang
Cheng Yang
Zhiyuan Liu
Lifeng Wang
Changcheng Li
Maosong Sun

title: Graph neural networks: A review of methods and applications

venue: AI Open,

authors:
Jie Zhou
Xu Han
Cheng Yang
Zhiyuan Liu
Lifeng Wang
Changcheng Li
Maosong Sun.

title: Gear: Graph-based evidence aggregating and reasoning for fact verification

venue: arXiv preprint arXiv:1908.01843.

authors:
Jason Zhu
Yanling Cui
Yuming Liu
Hao Sun
Xue Li
Markus Pelger
Liangjie Zhang
Tianqi Yan
Ruofei Zhang
Huasha Zhao.

title: Textgnn: Improving text encoder via graph neural network in sponsored search

venue: arXiv preprint arXiv:2101.06323.

heading: 1 Introduction

text:
The textual graph is a widely existed data format, where each node is annotated with its textual feature. The representation learning on textual graph is to generate low-dimensional node embeddings based on the individual textual features and the information from the neighbourhood. In recent years, the breakthroughs in pretrained language models and graph neural networks contribute to the development of corresponding techniques. Particularly, with pretrained language models, such as BERT (Devlin et al., 2018) and RoBERTa (Liu et al., 2019a), the underlying semantics of texts can be captured more precisely; at the same time, with graph neural networks, like GraphSage (Hamilton et al., 2017a) and GAT (Veličković et al., 2018), neighbours can be effectively aggregated for more informative node embeddings. It is necessary to combine both techniques for better textual graph representation. As
∗Work was done by 2021.01 during Junhan Yang and Shitao Xiao’s internship in MSRA
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
suggested by GraphSage (Hamilton et al., 2017a) and PinSage (Ying et al., 2018), the textual feature can be independently modeled by text encoders and further aggregated by rear-mounted GNNs for the final node embeddings. Such a representation paradigm has been widely adopted by subsequent works on various scenarios (Zhu et al., 2021; Li et al., 2021; Hu et al., 2020; Liu et al., 2019b; Zhou et al., 2019), where GNNs are combined with powerful PLM-based text encoders.
The above way of combination is called the “Cascaded Transformers-GNN” architecture (Figure 1 A), as the language models (built upon Transformers) are deployed ahead of the GNN component. With the above architecture, the text encoding and the graph aggregation are performed in two consecutive steps, where there is no information exchange between the nodes when text embeddings are generated. However, the above workflow is defective considering that the linked nodes are correlated, whose underlying semantics can be mutually enhanced. For example, given a node “notes on transformers” and its neighbour “tutorials on machine translation”; by making reference to the whole context, the “transformers” here can be interpreted as a machine learning model, rather than an electric device.
Our Work. We propose “GNN-nested Transformers” (GraphFormers), which are highlighted for the fusion of GNNs and language models (Figure 1 B). In GraphFormers, the GNN components are nested alongside the transformer layers (TRM) of language models, where the text encoding and graph aggregation are fused as an iteratively workflow. In each iteration, the linked nodes will exchange information with each other in the layerwise GNN component; thus, each node will be augmented by its neighbourhood information. The transformer component will work on the augmented node features, where increasingly informative node representations can be generated for the next iteration. Compared with the cascaded architecture, GraphFormers achieve more sufficient utilization of the cross-node information on graph, which significantly benefit the representation quality. Given that the layerwise GNN components merely involve simple and effective multi-head attention, GraphFormers preserve comparable running costs as the existing cascaded Transformers-GNN models.
On top of the proposed model architecture, we further improve GraphFormers’ representation quality and practicability as follows. Firstly, the training of GraphFormers is likely to be shortcut: in many cases, the center node itself can be “sufficiently informative”, where the training tasks can be accomplished without leveraging the neighbourhood information. As such, GraphFormers may end up with insufficiently trained GNNs. Inspired by recent success of curriculum learning (Bengio et al., 2009), we propose to train the model progressively: the first round of training is performed with manipulated data, where the nodes are randomly polluted; thus, it becomes harder to make prediction merely rely on the center nodes, and the model will be forced to leverage the whole input nodes. The second round of training gets back to the unpolluted data, where the model will be fit into the targeted distribution. Another concern about GraphFormers is that all the linked nodes are mutually dependent in the representation process: once a new node is presented, all the neighbours, regardless of whether they have been processed before, need to be encoded from scratch. As a result, a great deal of unnecessary computations will be incurred. We introduce unidirectional graph attention to alleviate this problem: only the center node is required to make reference to the neighbours, while the neighbour nodes remain independently encoded. By this means, the existing neighbours’ encoding results can be cached and reused, which significantly saves the computation cost.
Extensive evaluations are conducted with three million-scale textual graph datasets: DBLP, Wiki and Product, where the representation quality is measured by the link prediction accuracy. According to our experiment results, GraphFormers significantly outperform the SOTA cascaded TransformersGNN baselines with comparable running efficiency.

heading: 2 Related Work

text:
The textual graph representation is an important research topic in multiple areas, such as natural language processing, information retrieval and graph learning (Yang et al., 2015; Wang et al., 2016b,a; Yasunaga et al., 2017; Wang et al., 2019a; Xu et al., 2019). To learn high-quality representation for textual graph, techniques on natural language understanding and graph representation need to be jointly leveraged. In recent years, breakthroughs on pretrained language models (PLM) and graph neural networks (GNN) significantly advance the development of corresponding techniques.
PLM. The PLMs are proposed to learn universal language models with neural networks trained on large-scale corpus. The early works were based on shallow networks, e.g, word embeddings learned by Skip-Gram (Mikolov et al., 2013) and GloVe (Pennington et al., 2014). In recent years, the backbone networks are being quickly scaled up: from EMLo (Peters et al., 2018), GPT (Radford et al., 2018), to BERT (Devlin et al., 2018), XLNet (Yang et al., 2019), T5 (Raffel et al., 2019), GPT-3 (Brown et al., 2020). The large-scale models, which get fully trained with massive data, demonstrate superior performances on general NLP tasks. One of the most critical usages of PLMs is text representation, where the underlying semantics of texts are captured by low-dimensional embeddings. Such embeddings achieve competitive results on downstream tasks, like text retrieval and classification (Reimers and Gurevych, 2019; Luan et al., 2020; Gao et al., 2021; Su et al., 2021).
GNN. Graph neural networks are recognized as powerful tools of modeling graph data (Hamilton et al., 2017b; Zhou et al., 2020). Such methods (e.g., GCN (Kipf and Welling, 2016), GAT (Veličković et al., 2018), GraphSage (Hamilton et al., 2017a)) learn effective message passing mechanisms such that information between the nodes can get aggregated for expressive graph representations.
Graph neural networks may also incorporate node attributes, like texts; and it’s quite straightforward to leverage GNNs and PLMs for textual graph representation following the “cascaded architecture” suggested by GraphSage (Hamilton et al., 2017a): the node features are independently encoded at first; then, the node embeddings are aggregated via GNNs to generate the final representations. Such a representation paradigm is widely adopted by subsequent works (Zhu et al., 2021; Li et al., 2021; Hu et al., 2020; Liu et al., 2019b; Zhou et al., 2019). However, the above approaches treat the text encoding and graph aggregation as two consecutive steps, where the node-level features are independently processed. Our work is different from these approaches as the text encoding and graph aggregation are fused as an iterative workflow based on the “GNN-nested Transformers”.

heading: 3 GraphFormers

text: In this work, we deal with textual graph data, where each node x is a text. The node x together with its neighbours Nx are denoted as Gx. Our model learns the embedding for node x based on its own textual feature and the information of its neighbourhood Nx. The generated embeddings are expected to capture the relationship between the nodes, i.e., to accurately predict whether two nodes xq and xk are connected based on the embedding similarity.

heading: 3.1 GNN-nested Transformers

text:
The encoding process of GraphFormers is indicated as follows. The input nodes (the center node and its neighbours) are tokenized into sequences of tokens, with special tokens [CLS] padded in the front, whose states are used for node representation. The input sequences are mapped into the initial embedding sequences {H0g}G based on the summation of word embeddings and position embeddings. The embedding sequences are encoded by multiple layers of GNN-nested Transformers (shown as Figure 2), where the graph aggregation and text encoding are iteratively performed.
• Graph Aggregation in GNN. Each node is enhanced by its neighbourhood information based on the layerwise graph aggregation. For each node in the l-th layer, the first token-level embedding (corresponding to [CLS]) is taken as the node-level embedding: zlg ← Hlg[0]. The node-level embeddings
are gathered from all the nodes and passed to the layerwise GNN for graph aggregation. We leverage Multi-Head Attention (MHA) to encode the node-level embeddings ZlG ({zlg}G), similar as GAT (Veličković et al., 2018). For each attention head, the scaled dot-product attention is performed as:
ẐlG = MHA(Z l G);
MHA(ZlG) = Concat(head1, ...,headh);
headj = softmax( QKT√
d +B)V;
Q = ZlGW Q j ; K = Z l GW K j ; V = Z l GW V j ;
(1)
In the above equations, WQj , W K j , and W V j are the projection matrices of MHA, corresponding to the j-th attention head. A learnable position bias B is added to the dot-product result; the positions differentiate the relationship between the nodes; i.e., “center-to-center” (x to x), “center-to-neighbour” (x to Nx), and “neighbour-to-neighbour” (Nx to Nx), respectively.
Each of the embeddings ẑlg (ẑ l g ∈ ẐlG) is dispatched to its original node and concatenated (⊕) with the token-level embeddings, which gives rise to the graph-augmented token-level embeddings:
Ĥlg ← Concat(ẑlg,Hlg). (2)
In this place, the GNN-processed node-level embeddings ẐlG can be interpreted as “messagers”, with which the neighbourhood information can be introduced to each of the nodes.
• Text Encoding in Transformer. The graph-augmented token-level embeddings Ĥlg are processed by the transformer component (Vaswani et al., 2017), where the following computations are performed:
Ĥlg = LN(H l g +MHA asy(Ĥlg));
Hl+1g = LN(Ĥ l g +MLP(Ĥ l g)).
(3)
In the above equations, MLP is the Multi-Layer Projection unit, and LN is the Layer-Norm unit. We use asymmetric Multi-Head Attention (MHAasy), where Q, K, V are computed as:
Q = HlgW Q j ; K = Ĥ l gW K j ; V = Ĥ l gW V j . (4)
Therefore, the output sequence Hl+1g will be of the same length as the input sequence H l g. The encoding result will be used as the input token-level embeddings for the next layer. The node-level embedding at the last layer zLx (i.e., H L g [0]) will be used as the final node representation.
•Workflow. We summarize GraphFormers’ encoding workflow as Algorithm 1. The initial tokenlevel embeddings {H0g}G are independently encoded by the first Transformer layer TRM
0. For a L-layer GraphFormers, the graph aggregation and text encoding are iteratively performed for the subsequent L-1 steps (from 1 to L− 1). In each step, the node-level embeddings ZlG are gathered and
Algorithm 1: GraphFormers’ Workflow Input: The input graphs G (consist of the center node x and its neighbours). Output: The embedding for the center node hx.
1 begin 2 for each text g ∈ G do 3 H1g ← TRM 0(H0g); // Get the initial token-level embeddings
4 for l = 1, ..., L− 1 do 5 ZlG ← {zlg|g∈G}; // Gather node-level embeddings to GNN 6 ẐlG ← GNN(ZlG); // Graph aggregation in GNN 7 for each text g ∈ G do 8 Ĥlg ← Concat(ẑlg,Hlg); // Get graph-augmented token-level embeddings 9 Hl+1g ← TRM l(Ĥlg); // Text encoding in Transformer
10 Return hx ← zLx ;
processed by the layerwise GNN component. The output node-level embeddings ẐlG are dispatched to their original nodes, which generates the graph-augmented token-level embeddings Ĥlg . The graphaugmented token-level embedding are further processed by the Transformer component. Finally, The node-level embedding (for the center node x) in the last layer zLx is taken as our representation result.
• Encoding Complexity. Given an input of M nodes, each one has P tokens; the time complexity of each layer’s encoding operation is O(M2 +MP 2): the graph aggregation takes O(M2), because M node-level embeddings are gathered for multi-head attention; the text encoding takes O(MP 2), as each of the M node calls for the multi-head attention of P tokens. Compared with Transformers, the GNN’s computation cost is much smaller, mainly because of two reasons: 1) M2 MP 2 in general, 2) operations like MLP are not needed in graph aggregation. Therefore, the working efficiency of GraphFormers is close to the cascaded GNN-Transformers as the extra computation cost of layerwise graph aggregation is relatively small. Such a property is also empirically verified in our experiment.

heading: 3.2 Model Simplification: Unidirectional Graph Aggregation

text:
One concern about GraphFormers is that the input nodes are mutually dependent on each other during the encoding process. As a result, to generate the embedding for a node, all the related nodes in its neighbourhood need to be encoded from scratch, regardless of whether they have been processed before. Such a property is unfavorable in practice as a great deal of unnecessary computation cost might be incurred (i.e., a node will be repetitively encoded every time it serves as a neighbour node). We leverage a simple but effective simplification, the unidirectional graph aggregation, to address this problem. Particularly, only the center node x is required to make reference to the neighbourhood; while the rest of nodes Nx remain independently encoded all by their own textual features:
Hl+1g =
{ TRMl(Ĥlx), g = x;
TRMl(Hlg), ∀g ∈ Nx. (5)
Because the encoding of the neighbour nodes is independent of the center node, the intermediate encoding results {z1...Lg }Nx can be cached in storage2 and reused in subsequent computations when they are needed. As a result, the nodes can be prevented from being encoded repetitively, which saves a great deal of unnecessary computation cost. We empirically verify that GraphFormers maintain similar performances when the above simplification is introduced.

heading: 3.3 Model Training: Two-Stage Progressive Learning

text:
• Training Objective. We take advantage of link prediction as our training task. Given a pair of nodes q and k, the model is learned to predict whether they are connected based on their embedding
2The encoding results can be kept in low-cost devices, whose storage capacity can be regarded as infinite.
similarity. Particularly, the following classification loss is minimized for a positive pair of q and k:3
L = − log exp(〈hq,hk〉) exp(〈hq,hk〉) + ∑ r∈R exp(〈hq,hr〉) . (6)
In the above equation, hq and hk are the node embeddings; 〈·〉 denotes the computation of inner product; R stands for the negative samples. In our implementation, we leverage “in-batch negative samples” (Karpukhin et al., 2020; Luan et al., 2020) for the reduction of encoding cost: a positive sample in one training instance will be used as a negative sample in the rest of the training instances within the same mini-batch.
• Two-stage Training. In GraphFormers, the information from the center node and neighbour nodes are not treated equally, which may undermine the model’s training effect. Particularly, the center node’s information can be directly utilized, while the neighbourhood information needs to be introduced via three steps: 1) encoded as node-level embeddings, 2) making graph aggregation with the center node, and 3) introduced to center node’s graph augmented token-level embeddings. The message passing pathway can shortcut when the center nodes are “sufficiently informative”, i.e., two nodes are sufficiently similar with each other in terms of their own textual features, such that their connection can be predicted without considering the neighbours. Given the existence of such cases, GraphFormers may end up with well-trained Transformers but insufficiently trained GNNs.
To alleviate the above problem, we introduce a warm-up training task, where the link prediction is made based on the polluted input nodes. Particularly, for each input node g, a subset of its tokens gm will be randomly masked4. As a result, the classification loss becomes:
L′ = − log exp(〈hq̃,hk̃〉) exp(〈hq̃,hk̃〉) + ∑ r∈R exp(〈hq̃,hr̃〉) , (7)
where hq̃ , hk̃, hr̃ are the embeddings generated from the polluted nodes. The masked tokens reduce the informativeness of each individual node; therefore, the model is forced to leverage the whole input nodes to make the right prediction.
Finally, the model training is organized as a two-stage progressive learning process. In the first stage, the model is trained to minimize L′ based on the polluted nodes until its convergence, which reinforce the model’s capability of integrating information on graph. In the second stage, the model is continually trained to minimize L based on the original data until the convergence, which makes the model fit into the target distribution.

heading: 4 Experimental Studies

heading: 4.1 Data and Settings

text:
We make use of the following three real-world textual graph datasets for our experimental studies.
• DBLP5, which contains the paper citation graph from DBLP up to 2020-04-09. Two papers are linked if one is cited by the other one. The paper’s title is used as the textual feature.
•Wikidata5M6 (Wiki) (Wang et al., 2019b), which contains the entity graph from Wikipedia. The first sentence in each entity’s introduction is taken as its textual feature.
3We remove the naive cases where q and k are included by each other’s neighbour set, Nq and Nk. 4We use the common MLM strategy, where 15% of the input tokens are masked: 80% of them are replaced
by [MASK], the rest ones are replaced randomly or kept as the original tokens with the same probabilities. 5https://originalstatic.aminer.cn/misc/dblp.v12.7z 6https://deepgraphlearning.github.io/project/wikidata5m
• Product Graph (Product), an even larger dataset of online products collected by a world-wide search engine. In this dataset, the users’ web browsing behaviors are tracked for the targeted product webpages (e.g., Amazon webpages of Nike shoes). The user’s continuously browsed webpages within a short period of time (e.g., 30 minutes) is called a “session”. The products within a common session are connected in the graph (which is a common way of graph construction in e-commerce scenarios (Ying et al., 2018; Wang et al., 2018)). Each product has its unique textual description, which specifies information like the product name, brand, and saler, etc.
The textual features of all the datasets are in English. We make use of uncased WordPiece (Wu et al., 2016) to tokenize the input text. In our experiment, each text is associated with 5 uniformly sampled neighbours (without replacement); for texts with neighbourhood smaller than 5, all the neighbours will be utilized. We summarized the specifications of all the datasets with Table 1. The experiment results are evaluated in terms of link prediction accuracy, i.e., to predict whether a query node and key node are connected given the textual features of themselves and their neighbours. In each testing instance, one query is provided with 300 keys: 1 positive plus 299 randomly sampled negative cases. We leverage three common metrics to measure the prediction accuracy: Precision@1, NDCG, and MRR. Without specifications, we will take the unidirectional-simplified GraphFormers trained with the two-stage progressive learning as our default model. More details about the implementations and the training/testing configurations are summarized in an Appendix file. It is submitted together with our source code within the supplementary materials.

heading: 4.2 Baselines

text:
We focus on the comparison between GNN-nested Transformers and Cascaded Transformers-GNN. To make sure the difference between both architectures can be truthfully reflected from the evaluation results, GraphFormers and the Cascaded Transformers-GNN baselines are equipped with text encoders and graph aggregators of the same capacities. Particularly, we use the BERT-like PLM as our text encoder, where UniLM-base7 (Bao et al., 2020) is chosen as the network backbone for all related methods; the final layer’s [CLS] token embedding is used for the text embedding.
We enumerate the following representative graph aggregators as used in GAT (Veličković et al., 2018), GIN (Xu et al., 2018), GraphSage (Hamilton et al., 2017a). The GAT aggregator, where the node embedding is generated as the weighted sum of all the text embeddings. Each text embedding’s relative importance is calculated as the attention score with the center node. The Pooling-andConcat aggregators, where the center node’s text embedding is concatenated with the neighbours’ pooling result and linearly transformed for the final representation. Depending on the form of pooling function, we have the following options: Max and Mean, where neighbours are aggregated by max-pooling and mean-pooling, respectively; Att, where the neighbours are summed up based on the attention weights with the center node. By comparison, the neighbourhood information may get more emphasized with GAT; while the center node itself tends to be highlighted with Pooling-and-Concat.
We consider two more baselines which make use of simplified text encoders (such as CNN) and network embeddings: TNVE (Wang et al., 2019a) and IFTN (Xu et al., 2019). We also include the PLM only baseline, which merely leverages the textual feature of the center node.
7An enhanced BERT-like PLM showing more competitive performances than peers like RoBERTa, XLNet.

heading: 1 0.6485 0.8087 0.7522 0.6249 0.7946 0.7342

heading: 2 0.6841 0.8308 0.7804 0.6538 0.8137 0.7583

heading: 3 0.6980 0.8396 0.7916 0.6728 0.8256 0.7734

heading: 4 0.7126 0.8485 0.8029 0.6823 0.8319 0.7814

heading: 5 0.7267 0.8565 0.8133 0.6934 0.8386 0.7900

heading: 4.3 Overall Evaluation

text:
The overall evaluation results are reported in Table 2. It’s observed that GraphFormers consistently outperform all the baselines, especially the ones based on the cascaded Transformers-GNN, with notable advantages. Particularly, it achieves 2.9%, 4.8%, 6.5% relative improvements over the most competitive baselines (underlined) on each of the experimental datasets. Such an observation indicates that the relationship between the nodes can be captured more accurately based on the node embeddings generated by GraphFormers, which verifies the effectiveness of our proposed method.
We also observe the following underlying factors that may influence the representation quality.
Firstly, the effective utilization of neighbourhood information is critical. With the joint consideration of the center node and neighbour nodes, the PLM+GNNs methods, including GraphFormers and the cascaded Transformers-GNN baselines, significantly outperform the PLM only baseline in most of the time. We further analyze the impact of neighbourhood size as Table 3, with a fraction of neighbour nodes randomly sampled for each center node (using DBLP for illustration). It can be observed that both GraphFormers and PLM+Max (the most competitive baseline) achieve higher prediction accuracy than the PLM only method (P@1:0.5673, NDCG:0.7484, MRR:0.6777, as reported in Table 2), even with fewer neighbour nodes included. With the increasing number of neighbour nodes, the advantages become gradually enlarged. However, the marginal gain is vanishing, as the relative improvement becomes smaller when more neighbours are included. In all the testing cases, GraphFormers maintain consistent advantages over PLM+Max, which reaffirms the effectiveness of our proposed methods.
Secondly, the capacity of the text encoder is crucial for textual graph representation. All the pretrained language model based methods (GraphFormers, Cascaded Transformers-GNN baselines, PLM-only baseline) significantly outperform the baselines with simplified text encoders (TNVE, IFTN).
Thirdly, the representation quality is also sensitive to the form of graph aggregator. In Product, the cascaded Transformers-GNN baselines’ performances are quite close to each other. In DBLP, PLM+(Max, Mean, Att) outperforms PLM+GAT. In Wiki, not only PLM+(Max, Mean, Att) but also PLM-only baseline outperform PLM+GAT. Such phenomenons could be attributed to the type of graph: whether it is homogeneous or heterogeneous. Particularly, both Product and DBLP can be regarded as homogeneous graphs as the nodes are connected based on the same relationships; i.e., co-view relationship in Product, and citation relationship in DBLP. In both homogeneous graphs, the connected nodes may have quite similar semantics (the co-viewed products usually serve similar user intents, and the citation relationships usually indicate similar research topics); thus, the incorporated neighbour nodes will probably provide complementary information for the link prediction between the center nodes. However, Wiki is a heterogeneous graph, where the connections between entities may have highly different semantics. As a result, the incorporation of neighbour nodes may not contribute to the link prediction task, especially when the incorporated neighbours and the prediction target are connected to the center nodes with totally different relationships. Considering that GAT tends to focus more on the neighbourhood, its performance can be vulnerable in such unfavorable situations. These findings suggest that the neighbourhood information should be properly handled in case that the information of the center node is wiped out.
Finally, we may conclude different methods’ utility in textual graph representation: simplified text encoders ≺ PLMs ≺ Cascaded Transformers-GNN ≺ GNNs-nested Transformers. Such findings are consistent with our expectation that the precise modeling of individual textual feature and the effective integration of neighbourhood information will jointly contribute to high-quality textual graph representation. GraphFormers enjoy the high expressiveness of PLMs and leverage layerwise nested-GNNs to facilitate graph aggregation, which contributes to both of the above perspectives.

heading: 4.4 Ablation Studies

text:
The ablation studies (as Table 4) are performed to clarify the following issues: 1) the impact of two-stage progressive learning, and 2) the impact of unidirectional-simplified GraphFormers.
Firstly, the two-stage progressive learning substantially improves GraphFormers’ representation quality. Without such a training strategy ("-Progressive": training directly on the original data), the model’s performance is decreased by 0.98%, 1.71%, and 1.18% in each of the datasets, respectively.
Secondly, the performances between simplified and non-simplified (“-Simplified”) GraphFormers are comparable. In fact, the necessity of graph aggregation is not equivalent for the center node and the neighbour nodes: since the center node is the one for representation, it is much more important to ensure that the center node may extract complementary information from its neighbours. The unidirectional-simplified GraphFormers maintain such a property; thus, there is little impact on the final performances. Such a finding affirms that we may safely leverage the simplified model to save the cost of repetitively encoding the existing neighbours.
We make two additional ablation studies. “-Shared GNNs”: the GNNs parameters sharing is disabled, where each layer maintains its own graph aggregator (by default, the layerwise GNN components in GraphFormers share the same set of parameters). “-Position”: the learnable position bias (b in Eq. 1) is disabled in GNNs. We find that model’s performance is little affected from the above changes.

heading: 4.5 Efficiency Analysis

text:
We compare the time efficiency between GNN-nested Transformers (GraphFormers) and Cascaded Transformers+GNN (using PLM+Max for comparison). The evaluation is made with a Nvidia P100 GPU. Each mini-batch contains 32 encoding instances; each instance contains one center and #N neighbour nodes; the token length of each node is 16. We report the average time and memory (GPU RAM) costs per mini-batch as Table 5.
Firstly, the time and memory costs of both methods grow linearly with the increment of neighbours. (There are overheads of time and memory costs. The time cost overhead may come from CPU processing; while the memory cost overhead is mainly due to the model parameters (Rajbhandari et al., 2020)). We may approximately remove the overheads by deducting the time and memory costs where #N=3). Such a finding is consistent with our theoretical analysis in Section 3.1.
Secondly, the overall time and memory costs of GraphFormers are quite close to PLM+Max. When the number of neighbour nodes is small, the differences between both methods are almost ignorable. The differences become slightly larger when more neighbour nodes are included, because the layerwise
graph aggregations in GraphFormers get increasingly time consuming. However, the differences are still relatively small: merely around 3.5% of the overall running costs when #N is increased to 200 (“#N=200” is already more than enough for most of the real world scenarios).
Based on the above observations, we may conclude that GraphFormers are more accurate, meanwhile equally efficient and scalable as the conventional cascaded Transformer+GNNs.

heading: 4.6 Online A/B Test on Bing Search

text: GraphFormers has been deployed as one of the major ads retrieval algorithms on Bing Search, and it achieves highly competitive performance against the previous production system (the combination of a wide spectrum of semantic representation algorithms, including large-scale PLMs and cascaded PLMsGNNs). Particularly, the primary objective of Ads service is to maximize the revenue meanwhile increasing the user clicks. Therefore, the following three metrics are taken as the major performance indicators: RPM8 (revenue per thousand impressions), CY (click yield), and CPC9 (cost per click) . During our large-scale online A/B test, GraphFormers significantly improves the overall RPM, CY, CPC by 1.87%, 0.96% and 0.91%, respectively. A 11-day performance snapshot is demonstrated as Figure 3; it can be observed that in most of the time, all three metrics are significantly improved thanks to the utilization of GraphFormers (the daily performance are measured based on millions of impressions, thus having strong statistic significance).

heading: 5 Conclusion

text: In this paper, we propose a novel model architecture GraphFormers for textual graph representation. By having GNNs nested alongside each transformer layer of the pretrained language model, the underlying semantic of each textual node can be precisely captured and effectively integrated for high-quality textual graph representation. On top of the fundamental architecture, we introduce the two-stage progressive training strategy to further strengthen GraphFormers’ representation quality; we also simplify the model with the unidirectional graph aggregation, which eliminates the unnecessary computation cost. The experimental studies on three large-scale textual graph datasets verify the effectiveness of our proposed methods, where GraphFormers notably outperform the existing cascaded Transformer-GNNs methods with comparable running efficiency and scalability.

heading: 6 Acknowledgement

text: We are grateful to anonymous reviewers for their constructive comments on this work. The work was supported by grants from the National Natural Science Foundation of China (No. 62022077).

title: GraphFormers: GNN-nested Transformers for Representation Learning on Textual Graph