# Deconstructing Denoising Diffusion Models for Self-Supervised Learning

Xinlei Chen1 Zhuang Liu1 Saining Xie2 Kaiming He1
1FAIR, Meta 2New York University

###### Abstract

In this study, we examine the representation learning abilities of Denoising
Diffusion Models (DDM) that were originally purposed for image generation. Our
philosophy is to _deconstruct_ a DDM, gradually transforming it into a
classical Denoising Autoencoder (DAE). This deconstructive procedure allows us
to explore how various components of modern DDMs influence self-supervised
representation learning. We observe that only a very few modern components are
critical for learning good representations, while many others are
nonessential. Our study ultimately arrives at an approach that is highly
simplified and to a large extent resembles a classical DAE. We hope our study
will rekindle interest in a family of classical methods within the realm of
modern self-supervised learning.

##  1 Introduction

Denoising is at the core in the current trend of generative models in computer
vision and other areas. Popularly known as Denoising Diffusion Models (DDM)
today, these methods [36, 37, 38, 23, 29, 11] learn a Denoising Autoencoder
(DAE) [39] that removes noise of multiple levels driven by a diffusion
process. These methods achieve impressive image generation quality, especially
for high-resolution, photo-realistic images [33, 32]—in fact, these generation
models are so good that they appear to have strong recognition representations
for understanding the visual content.

|  |
---|---|---
clean image | noised | denoised

Figure 1:  The latent Denoising Autoencoder (_l_ -DAE) architecture we have
ultimately reached, after a thorough exploration of deconstructing Denoising
Diffusion Models (DDM) [23], with the goal of approaching the classical
Denoising Autoencoder (DAE) [39] as much as possible. Here, the clean image
(left) is projected onto a latent space using patch-wise PCA, in which noise
is added (middle). It is then projected back to pixels via inverse PCA. An
autoencoder is learned to predict a denoised image (right). This simple
architecture largely resembles classical DAE (with the main difference that
noise is added to the latent) and achieves competitive self-supervised
learning performance.

While DAE is a powerhouse of today’s generative models, it was originally
proposed for learning representations [39] from data in a self-supervised
manner. In today’s community of representation learning, the arguably most
successful variants of DAEs are based on “masking noise” [39], such as
predicting missing text in languages (_e.g_., BERT [10]) or missing patches in
images (_e.g_., MAE [21]). However, in concept, these masking-based variants
remain significantly different from removing additive (_e.g_., Gaussian)
noise: while the masked tokens explicitly specify unknown _vs_. known content,
no clean signal is available in the task of separating additive noise.
Nevertheless, today’s DDMs for generation are dominantly based on additive
noise, implying that they may learn representations without explicitly marking
unknown/known content.

Most recently, there has been an increasing interest [40, 28] in inspecting
the representation learning ability of DDMs. In particular, these studies
directly take off-the-shelf pre-trained DDMs [23, 32, 11], which are
originally purposed for generation, and evaluate their representation quality
for recognition. They report encouraging results using these generation-
oriented models. However, these pioneering studies obviously leave open
questions: these off-the-shelf models were designed for generation, not
recognition; it remains largely unclear whether the representation capability
is gained by a denoising-driven process, or a diffusion-driven process.

In this work, we take a much deeper dive into the direction initialized by
these recent explorations [40, 28]. Instead of using an off-the-shelf DDM that
is generation-oriented, we train models that are recognition-oriented. At the
core of our philosophy is to deconstruct a DDM, changing it step-by-step into
a classical DAE. Through this deconstructive research process, we examine
every single aspect (that we can think of) of a modern DDM, with the goal of
learning representations. This research process gains us new understandings on
what are the critical components for a DAE to learn good representations.

Surprisingly, we discover that the main critical component is a tokenizer [33]
that creates a low-dimensional latent space. Interestingly, this observation
is largely independent of the specifics of the tokenizer—we explore a standard
VAE [26], a patch-wise VAE, a patch-wise AE, and a patch-wise PCA encoder. We
discover that it is the low-dimensional latent space, rather than the
tokenizer specifics, that enables a DAE to achieve good representations.

Thanks to the effectiveness of PCA, our deconstructive trajectory ultimately
reaches a simple architecture that is highly similar to the classical DAE
(Fig. 1). We project the image onto a latent space using patch-wise PCA, add
noise, and then project it back by inverse PCA. Then we train an autoencoder
to predict a denoised image. We call this architecture “latent Denoising
Autoencoder” (_l_ -DAE).

Our deconstructive trajectory also reveals many other intriguing properties
that lie between DDM and classical DAE. For one example, we discover that even
using a single noise level (_i.e_., not using the noise scheduling of DDM) can
achieve a decent result with our _l_ -DAE. The role of using multiple levels
of noise is analogous to a form of data augmentation, which can be beneficial,
but not an enabling factor. With this and other observations, we argue that
the representation capability of DDM is mainly gained by the denoising-driven
process, not a diffusion-driven process.

Finally, we compare our results with previous baselines. On one hand, our
results are substantially better than the off-the-shelf counterparts
(following the spirit of [40, 28]): this is as expected, because these are our
starting point of deconstruction. On the other hand, our results fall short of
baseline contrastive learning methods (_e.g_., [7]) and masking-based methods
(_e.g_., [21]), but the gap is reduced. Our study suggests more room for
further research along the direction of DAE and DDM.

##  2 Related Work

In the history of machine learning and computer vision, the generation of
images (or other content) has been closely intertwined with the development of
unsupervised or self-supervised learning. Approaches in generation are
conceptually forms of un-/self-supervised learning, where models were trained
without labeled data, learning to capture the underlying distributions of the
input data.

There has been a prevailing belief that the ability of a model to generate
high-fidelity data is indicative of its potential for learning good
representations. Generative Adversarial Networks (GAN) [18], for example, have
ignited broad interest in adversarial representation learning [13, 12].
Variational Autoencoders (VAEs) [26], originally conceptualized as generative
models for approximating data distributions, have evolved to become a standard
in learning localized representations (“tokens”), _e.g_., VQVAE [30] and
variants [16]. Image inpainting [2], essentially a form of conditional image
generation, has led to a family of modern representation learning methods,
including Context Encoder [31] and Masked Autoencoder (MAE) [21].

Analogously, the outstanding generative performance of Denoising Diffusion
Models (DDM) [36, 37, 38, 23, 11] has drawn attention for their potential in
representation learning. Pioneering studies [40, 28] have begun to investigate
this direction by evaluating existing pre-trained DDM networks. However, we
note that while a model’s generation capability suggests a certain level of
understanding, it does not necessarily translate to representations useful for
downstream tasks. Our study delves deeper into these issues.

On the other hand, although Denoising Autoencoders (DAE) [39] have laid the
groundwork for autoencoding-based representation learning, their success has
been mainly confined to scenarios involving masking-based corruption (_e.g_.,
[21, 41, 17, 5]). To the best of our knowledge, little or no recent research
has reported results on classical DAE variants with additive Gaussian noise,
and we believe that the underlying reason is that a simple DAE baseline (Fig.
2(a)) performs poorly111According to the authors of MoCo [20] and MAE [21],
significant effort has been devoted to DAE baselines during the development of
those works, following the best practice established. However, it has not led
to meaningful results ($<$20% accuracy). (_e.g_., in $\scriptstyle\sim$20%
Fig. 5).

##  3 Background: Denoising Diffusion Models

Our deconstructive research starts with a Denoising Diffusion Model (DDM) [36,
37, 38, 23, 11]. We briefly describe the DDM we use, following [11, 32].

A diffusion process starts from a clean data point ($z_{0}$) and sequentially
adds noise to it. At a specified time step $t$, the noised data $z_{t}$ is
given by:

$z_{t}=\gamma_{t}z_{0}+\sigma_{t}\epsilon$ (1)

where $\epsilon{\sim}\mathcal{N}(0,\mathbf{I})$ is a noise map sampled from a
Gaussian distribution, and $\gamma_{t}$ and $\sigma_{t}$ define the scaling
factors of the signal and of the noise, respectively. By default, it is set
$\gamma_{t}^{2}+\sigma_{t}^{2}=1$ [29, 11].

(a) a classical Denoising Autoencoders (DAE)

(b) a modern Denoising Diffusion Model (DDM) on a latent space

Figure 2: A classical DAE and a modern DDM. (a) A classical DAE that adds and
predicts noise on the image space. (b) State-of-the-art DDMs (_e.g_., LDM
[33], DIT [32]) that operate on a latent space, where the noise is added and
predicted.

A denoising diffusion model is learned to remove the noise, conditioned on the
time step $t$. Unlike the original DAE [39] that predicts a clean input, the
modern DDM [23, 29] often predicts the noise $\epsilon$. Specifically, a loss
function in this form is minimized:

$\|\epsilon-\mathtt{net}(z_{t})\|^{2}$ (2)

where $\mathtt{net}(z_{t})$ is the network output. The network is trained for
multiple noise levels given a noise _schedule_ , conditioned on the time step
$t$. In the generation process, a trained model is iteratively applied until
it reaches the clean signal $z_{0}$.

DDMs can operate on two types of input spaces. One is the original pixel space
[11], where the raw image $x_{0}$ is directly used as $z_{0}$. The other
option is to build DDMs on a _latent_ space produced by a tokenizer, following
[33]. See Fig. 2(b). In this case, a pre-trained tokenizer $f$ (which is often
another autoencoder, _e.g_., VQVAE [30]) is used to map the image $x_{0}$ into
its latent $z_{0}{=}f(x_{0})$.

##### Diffusion Transformer (DiT).

Our study begins with the Diffusion Transformer (DiT) [32]. We choose this
Transformer-based DDM for several reasons: (i) Unlike other UNet-based DDMs
[11, 33], Transformer-based architectures can provide fairer comparisons with
other self-supervised learning baselines driven by Transformers (_e.g_., [7,
21]); (ii) DiT has a clearer distinction between the encoder and decoder,
while a UNet’s encoder and decoder are connected by skip connections and may
require extra effort on network surgery when evaluating the encoder; (iii) DiT
trains much faster than other UNet-based DDMs (see [32]) while achieving
better generation quality.

We use the DiT-Large (DiT-L) variant [32] as our DDM baseline. In DiT-L, the
encoder and decoder put together have the size of ViT-L [15] (24 blocks). We
evaluate the representation quality (linear probe accuracy) of the encoder,
which has 12 blocks, referred to as “$\frac{1}{2}$L” (half large).

##### Tokenizer.

DiT instantiated in [32] is a form of Latent Diffusion Models (LDM) [33],
which uses a VQGAN tokenizer [16]. Specifically, this VQGAN tokenizer
transforms the 256$\times$256$\times$3 input image
(height$\times$width$\times$channels) into a 32$\times$32$\times$4 latent map,
with a stride of 8.

##### Starting baseline.

By default, we train the models for 400 epochs on ImageNet [9] with a
resolution of 256$\times$256 pixels. Implementation details are in Sec. A.

Our DiT baseline results are reported in Tab. 1 (line 1). With DiT-L, we
report a linear probe accuracy of 57.5% using its $\frac{1}{2}$L encoder. The
generation quality (Fréchet Inception Distance [22], FID-50K) of this DiT-L
model is 11.6. This is the starting point of our destructive trajectory.

Despite differences in implementation details, our starting point conceptually
follows recent studies [40, 28] (more specifically, DDAE [40]), which evaluate
off-the-shelf DDMs under the linear probing protocol.

##  4 Deconstructing Denoising Diffusion Models

Our deconstruction trajectory is divided into three stages. We first adapt the
generation-focused settings in DiT to be more oriented toward self-supervised
learning (Sec. 4.1). Next, we deconstruct and simplify the tokenizer step by
step (Sec. 4.2). Finally, we attempt to reverse as many DDM-motivated designs
as possible, pushing the models towards a classical DAE [39] (Sec. 4.3). We
summarize our learnings from this deconstructing process in Sec. 4.4.

###  4.1 Reorienting DDM for Self-supervised Learning

While a DDM is conceptually a form of a DAE, it was originally developed for
the purpose of image generation. Many designs in a DDM are oriented toward the
generation task. Some designs are not legitimate for self-supervised learning
(_e.g_., class labels are involved); some others are not necessary if visual
quality is not concerned. In this subsection, we reorient our DDM baseline for
the purpose of self-supervised learning, summarized in Tab. 1.

##### Remove class-conditioning.

A high-quality DDM is often trained with conditioning on class labels, which
can largely improve the generation quality. But the usage of class labels is
simply not legitimate in the context of our self-supervised learning study. As
the first step, we remove class-conditioning in our baseline.

Surprisingly, removing class-conditioning substantially improves the linear
probe accuracy from 57.5% to 62.1% (Tab. 1), even though the generation
quality is greatly hurt as expected (FID from 11.6 to 34.2). We hypothesize
that directly conditioning the model on class labels may reduce the model’s
demands on encoding the information related to class labels. Removing the
class-conditioning can force the model to learn more semantics.

|  acc. ($\uparrow$) |  FID ($\downarrow$)
---|---|---
DiT baseline |  57.5 |  11.6
\+ remove class-conditioning |  62.5 |  30.9
\+ remove VQGAN perceptual loss |  58.4 |  54.3
\+ remove VQGAN adversarial loss |  59.0 |  75.6
\+ replace noise schedule |  63.4 |  93.2
Table 1: Reorienting DDM for self-supervised learning. We begin with the DiT
[32] baseline and evaluate its linear probe accuracy (acc.) on ImageNet. Each
line is based on a modification of the immediately preceding line. The entries
in gray, in which class labels are used, are not legitimate results for self-
supervised learning. See Sec. 4.1 for description.

##### Deconstruct VQGAN.

In our baseline, the VQGAN tokenizer, presented by LDM [33] and inherited by
DiT, is trained with multiple loss terms: (i) autoencoding reconstruction
loss; (ii) KL-divergence regularization loss [33];222The KL form in [33] does
not perform explicit vector quantization (VQ), interpreted as “the
quantization layer absorbed by the decoder” [33]. (iii) perceptual loss [44]
based on a supervised VGG net [35] trained for ImageNet classification; and
(iv) adversarial loss [18, 16] with a discriminator. We ablate the latter two
terms in Tab. 1.

As the perceptual loss [44] involves a supervised pre-trained network, using
the VQGAN trained with this loss is not legitimate. Instead, we train another
VQGAN tokenizer [33] in which we remove the perceptual loss. Using this
tokenizer reduces the linear probe accuracy significantly from 62.5% to 58.4%
(Tab. 1), which, however, provides the first legitimate entry thus far. This
comparison reveals that a tokenizer trained with the perceptual loss (with
class labels) in itself provides semantic representations. We note that the
perceptual loss is not used from now on, in the remaining part of this paper.

We train the next VQGAN tokenizer that further removes the adversarial loss.
It slightly increases the linear probe accuracy from 58.4% to 59.0% (Tab. 1).
With this, our tokenizer at this point is essentially a VAE, which we move on
to deconstruct in the next subsection. We also note that removing either loss
harms generation quality.

##### Replace noise schedule.

In the task of generation, the goal is to progressively turn a noise map into
an image. As a result, the original noise schedule spends many time steps on
very noisy images (Fig. 3). This is not necessary if our model is not
generation-oriented.

We study a simpler noise schedule for the purpose of self-supervised learning.
Specifically, we let $\gamma_{t}^{2}$ linearly decay in the range of
$1{>}\gamma_{t}^{2}{\geq}0$ (Fig. 3). This allows the model to spend more
capacity on cleaner images. This change greatly improves the linear probe
accuracy from 59.0% to 63.4% (Tab. 1), suggesting that the original schedule
focuses too much on noisier regimes. On the other hand, as expected, doing so
further hurts the generation ability, leading to a FID of 93.2.

##### Summary.

Overall, the results in Tab. 1 reveal that self-supervised learning
performance is not correlated to generation quality. The representation
capability of a DDM is not necessarily the outcome of its generation
capability.

Figure 3:  Noise schedules. The original schedule [23, 32], which sets
$\gamma_{t}^{2}{=}{\Pi_{s=1}^{t}{(1-\beta_{s})}}$ with a linear schedule of
$\beta$, spends many time steps on very noisy images (small $\gamma$).
Instead, we use a simple schedule that is linear on $\gamma^{2}$, which
provides less noisy images.

###  4.2 Deconstructing the Tokenizer

Next, we further deconstruct the VAE tokenizer by making substantial
simplifications. We compare the following four variants of autoencoders as the
tokenizers, each of which is a simplified version of the preceding one:

  * •

##### Convolutional VAE.

Our deconstruction thus far leads us to a VAE tokenizer. As common practice
[26, 33], the encoder $f(\cdot)$ and decoder $g(\cdot)$ of this VAE are deep
convolutional (conv) neural networks [27]. This convolutional VAE minimizes
the following loss function:

$\|x-g(f(x))\|^{2}+\mathbb{KL}\left[f(x)|\mathcal{N}\right].$

Here, $x$ is the input image of the VAE. The first term is the reconstruction
loss, and the second term is the Kullback-Leibler divergence [3, 16] between
the latent distribution of $f(x)$ and a unit Gaussian distribution.

  * •

##### Patch-wise VAE.

Next we consider a simplified case in which the VAE encoder and decoder are
both linear projections, and the VAE input $x$ is a patch. The training
process of this patch-wise VAE minimizes this loss:

$\|x-U{{}^{T}}Vx\|^{2}+\mathbb{KL}\left[{{V}{x}}|\mathcal{N}\right].$

Here $x$ denotes a patch flattened into a $D$-dimensional vector. Both $U$ and
$V$ are $d{\times}{D}$ matrixes, where $d$ is the dimension of the latent
space. We set the patch size as 16$\times$16 pixels, following [15].

  * •

##### Patch-wise AE.

We make further simplification on VAE by removing the regularization term:

$\|x-U{{}^{T}}Vx\|^{2}.$

As such, this tokenizer is essentially an autoencoder (AE) on patches, with
the encoder and decoder both being linear projections.

  * •

##### Patch-wise PCA.

Finally, we consider a simpler variant which performs Principal Component
Analysis (PCA) on the patch space. It is easy to show that PCA is equivalent
to a special case of AE:

$\|x-V^{T}Vx\|^{2}.$

in which $V$ satisfies $VV^{T}{=}I$ (${d}{\times}{d}$ identity matrix). The
PCA bases can be simply computed by eigen-decomposition on a large set of
randomly sampled patches, requiring no gradient-based training.

Thanks to the simplicity of using patches, for the three patch-wise
tokenizers, we can visualize their filters in the patch space (Fig. 4).

Tab. 2 summarizes the linear probe accuracy of DiT using these four variants
of tokenizers. We show the results w.r.t. the latent dimension “per token”.333
For patch-wise VAE/AE/PCA (patch stride is 16), we treat each patch as a
token, so the latent dimension is simply $d$ for each patch. For the default
convolutional VAE that has a stride of $8$, the DiT implementation [32] treats
each 2$\times$2 patch on the latent space as a “token”; as a result, its
latent dimension “per token” should be multiplied by 4 for calibration.  We
draw the following observations.

(a) patch-wise VAE

(b) patch-wise AE

(c) patch-wise PCA

Figure 4: Visualization of the patch-wise tokenizer. Each filter corresponds
to a row of the linear projection matrix $V$ ($d{\times}D$), reshaped to
16$\times$16$\times$3 for visualization. Here $d{=}16$.

latent dim. $d$ |  8 |  16 |  32 |  64 |  128
---|---|---|---|---|---
conv. VAE (baseline) |  54.5 |  63.4 |  62.8 |  57.0 |  48.1
patch-wise VAE |  58.3 |  64.9 |  64.8 |  56.8 |  -
patch-wise AE |  59.9 |  64.7 |  64.6 |  59.9 |  -
patch-wise PCA |  56.0 |  63.4 |  65.1 |  60.0 |  53.9

Table 2: Linear probe accuracy _vs_. latent dimension. With a DiT model, we
study four variants of tokenizers for computing the latent space. We vary the
dimensionality $d$ (per token) of the latent space. The table is visualized by
the plot above. All four variants of tokenizers exhibit similar trends,
despite their differences in architectures and loss functions. The 63.4% entry
of “conv. VAE” is the same entry as the last line in Tab. 1.

#### Latent dimension of the tokenizer is crucial for DDM to work well in
self-supervised learning.

As shown in Tab. 2, all four variants of tokenizers exhibit similar trends,
despite their differences in architectures and loss functions. Interestingly,
the optimal dimension is relatively low ($d$ is 16 or 32), even though the
full dimension per patch is much higher (16$\times$16$\times$3=768).

Surprisingly, the convolutional VAE tokenizer is neither necessary nor
favorable; instead, all patch-based tokenizers, in which each patch is encoded
independently, perform similarly with each other and consistently outperform
the Conv VAE variant. In addition, the KL regularization term is unnecessary,
as both the AE and PCA variants work well.

To our further surprise, even the PCA tokenizer works well. Unlike the VAE or
AE counterparts, the PCA tokenizer does not require gradient-based training.
With pre-computed PCA bases, the application of the PCA tokenizer is analogous
to a form of image pre-processing, rather than a “network architecture”. The
effectiveness of a PCA tokenizer largely helps us push the modern DDM towards
a classical DAE, as we will show in the next subsection.

Figure 5:  Linear probe results of the pixel-based tokenizer, operated on an
image size of 256, 128, 64, and 32, respectively with a patch size of 16, 8,
4, 2. The “latent” dimensions of these tokenized spaces are 768, 192, 48, and
12 per token. Similar to other tokenizers we study, this pixel-based tokenizer
exhibits a similar trend: a relatively small dimension of the latent space is
optimal.

#### High-resolution, pixel-based DDMs are inferior for self-supervised
learning.

Before we move on, we report an extra ablation that is consistent with the
aforementioned observation. Specifically, we consider a “naïve tokenizer” that
performs identity mapping on patches extracted from resized images. In this
case, a “token” is the flatten vector consisting all pixels of a patch.

In Fig. 5, we show the results of this “pixel-based” tokenizer, operated on an
image size of 256, 128, 64, and 32, respectively with a patch size of 16, 8,
4, 2. The “latent” dimensions of these tokenized spaces are 768, 192, 48, and
12 per token. In all case, the sequence length of the Transformer is kept
unchanged (256).

Interestingly, this pixel-based tokenizer exhibits a similar trend with other
tokenizers we have studied, although the optimal dimension is shifted. In
particular, the optimal dimension is $d$=48, which corresponds to an image
size of 64 with a patch size of 4. With an image size of 256 and a patch size
of 16 ($d$=768), the linear probe accuracy drops dramatically to 23.6%.

These comparisons show that the tokenizer and the resulting latent space are
crucial for DDM/DAE to work competitively in the self-supervised learning
scenario. In particular, applying a classical DAE with additive Gaussian noise
on the pixel space leads to poor results.

###  4.3 Toward Classical Denoising Autoencoders

Next, we go on with our deconstruction trajectory and aim to get as close as
possible to the classical DAE [39]. We attempt to remove every single aspect
that still remains between our current PCA-based DDM and the classical DAE
practice. Via this deconstructive process, we gain better understandings on
how every modern design may influence the classical DAE. Tab. 3 gives the
results, discussed next.

|  acc.
---|---
patch-wise PCA baseline |  65.1
\+ predict clean data (rather than noise) |  62.4
\+ remove input scaling (fix $\gamma_{t}\equiv 1$) |  63.6
\+ operate on image input with inv. PCA |  63.6
\+ operate on image output with inv. PCA |  63.9
\+ predict original image |  64.5
Table 3: Moving toward a classical DAE, starting from our patch-wise PCA
tokenizer. Each line is based on a modification of the immediately preceding
line. See Sec. 4.3 for descriptions.

##### Predict clean data (rather than noise).

While modern DDMs commonly predict the noise $\epsilon$ (see Eq. 2), the
classical DAE predicts the clean data instead. We examine this difference by
minimizing the following loss function:

$\lambda_{t}\|z_{0}-\mathtt{net}(z_{t})\|^{2}$ (3)

Here $z_{0}$ is the clean data (in the latent space), and
$\mathtt{net}(z_{t})$ is the network prediction. $\lambda_{t}$ is a
$t$-dependent loss weight, introduced to balance the contribution of different
noise levels [34]. It is suggested to set
$\lambda_{t}={\gamma_{t}^{2}}/{\sigma_{t}^{2}}$ as per [34]. We find that
setting $\lambda_{t}={\gamma_{t}^{2}}$ works better in our scenario.
Intuitively, it simply puts more weight to the loss terms of the cleaner data
(larger $\gamma_{t}$).

With the modification of predicting clean data (rather than noise), the linear
probe accuracy degrades from 65.1% to 62.4% (Tab. 3). This suggests that the
choice of the prediction target influences the representation quality.

Even though we suffer from a degradation in this step, we will stick to this
modification from now on, as our goal is to move towards a classical DAE.444We
have revisited undoing this change in our final entry, in which we have not
observed this degradation.

##### Remove input scaling.

In modern DDMs (see Eq. 1), the input is scaled by a factor of $\gamma_{t}$.
This is not common practice in a classical DAE. Next, we study removing input
scaling, _i.e_., we set $\gamma_{t}\equiv 1$. As $\gamma_{t}$ is fixed, we
need to define a noise schedule directly on $\sigma_{t}$. We simply set
$\sigma_{t}$ as a linear schedule from 0 to $\sqrt{2}$. Moreover, we
empirically set the weight in Eq. 3 as $\lambda_{t}={1}/{(1+\sigma_{t}^{2})}$,
which again puts more emphasis on cleaner data (smaller $\sigma_{t}$).

After fixing $\gamma_{t}\equiv 1$, we achieve a decent accuracy of 63.6% (Tab.
3), which compares favorably with the varying $\gamma_{t}$ counterpart’s
62.4%. This suggests that scaling the data by $\gamma_{t}$ is not necessary in
our scenario.

##### Operate on the image space with inverse PCA.

Thus far, for all entries we have explored (except Fig. 5), the model operates
on the latent space produced by a tokenizer (Fig. 2 (b)). Ideally, we hope our
DAE can work directly on the image space while still having good accuracy.
With the usage of PCA, we can achieve this goal by inverse PCA.

The idea is illustrated in Fig. 1. Specially, we project the input image into
the latent space by the PCA bases (_i.e_., $V$), add noise in the latent
space, and project the noisy latent back to the image space by the inverse PCA
bases ($V^{T}$). Fig. 1 (middle, bottom) shows an example image with noise
added in the latent space. With this noisy image as the input to the network,
we can apply a standard ViT network [15] that directly operate on images, as
if there is no tokenizer.

Applying this modification on the input side (while still predicting the
output on the latent space) has 63.6% accuracy (Tab. 3). Further applying it
to the output side (_i.e_., predicting the output on the image space with
inverse PCA) has 63.9% accuracy. Both results show that operating on the image
space with inverse PCA can achieve similar results as operating on the latent
space.

##### Predict original image.

While inverse PCA can produce a prediction target in the image space, this
target is not the original image. This is because PCA is a lossy encoder for
any reduced dimension $d$. In contrast, it is a more natural solution to
predict the original image directly.

When we let the network predict the original image, the “noise” introduced
includes two parts: (i) the additive Gaussian noise, whose intrinsic dimension
is $d$, and (ii) the PCA reconstruction error, whose intrinsic dimension is
$D-d$ ($D$ is 768). We weight the loss of both parts differently.

Formally, with the clean original image $x_{0}$ and network prediction
$\mathtt{net}(x_{t})$, we can compute the residue $r$ projected onto the full
PCA space: $r\triangleq V(x_{0}-\mathtt{net}(x_{t}))$. Here $V$ is the
$D$-by-$D$ matrix representing the full PCA bases. Then we minimize the
following loss function:

$\lambda_{t}\sum_{i=1}^{D}w_{i}{r_{i}^{2}}.$ (4)

Here $i$ denotes the $i$-th dimension of the vector $r$. The per-dimension
weight $w_{i}$ is 1 for $i\leq d$, and 0.1 for $d<i\leq D$. Intuitively,
$w_{i}$ down-weights the loss of the PCA reconstruction error. With this
formulation, predicting the original image achieves 64.5% linear probe
accuracy (Tab. 3).

This variant is conceptually very simple: its input is a noisy image whose
noise is added in the PCA latent space, its prediction is the original clean
image (Fig. 1).

##### Single noise level.

Lastly, out of curiosity, we further study a variant with single-level noise.
We note that multi-level noise, given by noise scheduling, is a property
motived by the diffusion process in DDMs; it is conceptually unnecessary in a
classical DAE.

We fix the noise level $\sigma$ as a constant ($\sqrt{1/3}$). Using this
single-level noise achieves decent accuracy of 61.5%, a 3% degradation _vs_.
the multi-level noise counterpart (64.5%). Using multiple levels of noise is
analogous to a form of data augmentation in DAE: it is beneficial, but not an
enabling factor. This also implies that the representation capability of DDM
is mainly gained by the denoising-driven process, not a diffusion-driven
process.

As multi-level noise is useful and conceptually simple, we keep it in our
final entries presented in the next section.

Figure 6: The overall deconstructive trajectory from a modern DDM to _l_ -DAE,
summarizing Tab. 1, Tab. 2, and Tab. 3. Each line is based on a modification
of the immediately preceding line.

###  4.4 Summary

In sum, we deconstruct a modern DDM and push it towards a classical DAE (Fig.
6). We undo many of the modern designs and conceptually retain only two
designs inherited from modern DDMs: (i) a low-dimensional latent space in
which noise is added; and (ii) multi-level noise.

We use the entry at the end of Tab. 3 as our final DAE instantiation
(illustrated in Fig. 1). We refer to this method as “ _latent_ Denoising
Autoencoder”, or in short, _l_ -DAE.

##  5 Analysis and Comparisons

Figure 7:  Visualization: pixel noise _vs_. latent noise. Left: clean image,
256$\times$256 pixels. Middle: Gaussian noise added to the pixel space. Right:
Gaussian noise added to the latent space produced by the PCA tokenizer,
visualized by back projection to the image space using inverse PCA.
$\sigma{=}\sqrt{1/3}$ in both cases.  Figure 8: Denoising results of _l_ -DAE,
evaluated on ImageNet validation images. This denoising problem, serving as a
pretext task, encourages the network to learn meaningful representations in a
self-supervised manner. For each case, we show: (left) clean image; (middle)
noisy image that is the input to the network, where the noise is added to the
latent space; (right) denoised output.

##### Visualizing latent noise.

Conceptually, _l_ -DAE is a form of DAE that learns to remove noise added to
the latent space. Thanks to the simplicity of PCA, we can easily visualize the
latent noise by inverse PCA.

Fig. 7 compares the noise added to pixels _vs_. to the latent. Unlike the
pixel noise, the latent noise is largely independent of the resolution of the
image. With patch-wise PCA as the tokenizer, the pattern of the latent noise
is mainly determined by the patch size. Intuitively, we may think of it as
using patches, rather than pixels, to resolve the image. This behavior
resembles MAE [21], which masks out patches instead of individual pixels.

##### Denoising results.

Fig. 8 shows more examples of denoising results based on _l_ -DAE. Our method
produces reasonable predictions despite of the heavy noise. We note that this
is less of a surprise, because neural network-based image restoration [4, 14]
has been an intensively studied field.

Nevertheless, the visualization may help us better understand how _l_ -DAE may
learn good representations. The heavy noise added to the latent space creates
a challenging pretext task for the model to solve. It is nontrivial (even for
human beings) to predict the content based on one or a few noisy patches
locally; the model is forced to learn higher-level, more holistic semantics to
make sense of the underlying objects and scenes.

##### Data augmentation.

Notably, all models we present thus far have no data augmentation: only the
center crops of images are used, with no random resizing or color jittering,
following [11, 32]. We further explore a mild data augmentation (random
resized crop) for our final _l_ -DAE:

aug. |  center crop |  random crop
---|---|---
acc. |  64.5 |  65.0

which has slight improvement. This suggests that the representation learning
ability of $l$-DAE is largely independent of its reliance on data
augmentation. A similar behavior was observed in MAE [21], which sharply
differs from the behavior of contrastive learning methods (_e.g_., [6]).

##### Training epochs.

All our experiments thus far are based on 400-epoch training. Following MAE
[21], we also study training for 800 and 1600 epochs:

epochs |  400 |  800 |  1600
---|---|---|---
acc. |  65.0 |  67.5 |  69.6

As a reference, MAE [21] has a significant gain (4%) extending from 400 to 800
epochs, and MoCo v3 [7] has nearly no gain (0.2%) extending from 300 to 600
epochs.

##### Model size.

Thus far, our all models are based on the DiT-L variant [32], whose encoder
and decoder are both “ViT-$\frac{1}{2}$L” (half depth of ViT-L). We further
train models of different sizes, whose encoder is ViT-B or ViT-L (decoder is
always of the same size as encoder):

encoder |  ViT-B |  ViT-$\frac{1}{2}$L |  ViT-L
---|---|---|---
acc. |  60.3 |  65.0 |  70.9

We observe a good scaling behavior w.r.t. model size: scaling from ViT-B to
ViT-L has a large gain of 10.6%. A similar scaling behavior is also observed
in MAE [21], which has a 7.8% gain from ViT-B to ViT-L.

##### Comparison with previous baselines.

Finally, to have a better sense of how different families of self-supervised
learning methods perform, we compare with previous baselines in Tab. 4. We
consider MoCo v3 [7], which belongs to the family of contrastive learning
methods, and MAE [21], which belongs to the family of masking-based methods.

Interestingly, _l_ -DAE performs decently in comparison with MAE, showing a
degradation of 1.4% (ViT-B) or 0.8% (ViT-L). We note that here the training
settings are made as fair as possible between MAE and _l_ -DAE: both are
trained for 1600 epochs and with random crop as the data augmentation. On the
other hand, we should also note that MAE is more efficient in training because
it only operates on unmasked patches. Nevertheless, we have largely closed the
accuracy gap between MAE and a DAE-driven method.

Last, we observe that autoencoder-based methods (MAE and _l_ -DAE) still fall
short in comparison with contrastive learning methods under this protocol,
especially when the model is small. We hope our study will draw more attention
to the research on autoencoder-based methods for self-supervised learning.

##  6 Conclusion

We have reported that _l_ -DAE, which largely resembles the classical DAE, can
perform competitively in self-supervised learning. The critical component is a
low-dimensional latent space on which noise is added. We hope our discovery
will reignite interest in denoising-based methods in the context of today’s
self-supervised learning research.

method | ViT-B (86M) | ViT-L (304M)
---|---|---
MoCo v3 | 76.7 | 77.6
MAE | 68.0 | 75.8
_l_ -DAE | 66.6 | 75.0
Table 4: Comparisons with previous baselines of MoCo v3 [7] and MAE [21]. The
entries of both MAE and _l_ -DAE are trained for 1600 epochs and with random
crop as the data augmentation. Linear probe accuracy on ImageNet is reported.
In the brackets are the number of parameters of the encoder.

##### Acknowledgement.

We thank Pascal Vincent, Mike Rabbat, and Ross Girshick for their discussion
and feedback.

##  A Implementation Details

##### DiT architecture.

We follow the DiT architecture design [32]. The DiT architecture is similar to
the original ViT [15], with extra modifications made for conditioning. Each
Transformer block accepts an embedding network (a two-layer MLP) conditioned
on the time step $t$. The output of this embedding network determines the
scale and bias parameters of LayerNorm [1], referred to as adaLN [32].
Slightly different from [32], we set the hidden dimension of this MLP as 1/4
of its original dimension, which helps reduce model sizes and save memory, at
no accuracy cost.

##### Training.

The original DiTs [32] are trained with a batch size of 256. To speed up our
exploration, we increase the batch size to 2048. We perform linear learning
rate warm up [19] for 100 epochs and then decay it following a half-cycle
cosine schedule. We use a base learning rate blr = 1e-4 [32] by default, and
set the actual lr following the linear scaling rule [19]: blr $\times$
batch_size / 256. No weight decay is used [32]. We train for 400 epochs by
default. On a 256-core TPU-v3 pod, training DiT-L takes 12 hours.

##### Linear probing.

Our linear probing implementation follows the practice of MAE [21]. We use
clean, $256{\times}256$-sized images for linear probing training and
evaluation. The ViT output feature map is globally pooled by average pooling.
It is then processed by a parameter-free BatchNorm [25] layer and a linear
classifier layer, following [21]. The training batch size is 16384, learning
rate is $6.4{\times}10^{-3}$ (cosine decay schedule), weight decay is 0, and
training length is 90 epochs. Randomly resized crop and flipping are used
during training and a single center crop is used for testing. Top-1 accuracy
is reported.

While the model is conditioned on $t$ in self-supervised pre-training,
conditioning is not needed in transfer learning (_e.g_., linear probing). We
fix the time step $t$ value in our linear probing training and evaluation. The
influence of different $t$ values (out of 1000 time steps) is shown as
follows:

fixed $t$ |  0 |  10 |  20 |  40 |  80
---|---|---|---|---|---
w/ clean input |  64.1 |  64.5 |  64.1 |  63.3 |  62.2
w/ noisy input |  64.2 |  65.0 |  65.0 |  65.0 |  64.5

We note that the $t$ value determines: (i) the model weights, which are
conditioned on $t$, and (ii) the noise added in transfer learning, using the
same level of $t$. Both are shown in this table. We use $t$ = 10 and clean
input in all our experiments, except Tab. 4 where we use the optimal setting.

Fixing $t$ also means that the $t$-dependent MLP layers, which are used for
conditioning, are not exposed in transfer learning, because they can be merged
given the fixed $t$. As such, our model has the number of parameters just
similar to the standard ViT [15], as reported in Tab. 4.

The DiT-L [32] has 24 blocks where the first 12 blocks are referred to as the
“encoder” (hence ViT-$\frac{1}{2}$L) and the others the “decoder”. This
separation of the encoder and decoder is artificial. In the following table,
we show the linear probing results using different numbers of blocks in the
encoder, using the same pre-trained model:

enc. blocks |  9 |  10 |  11 |  12 |  13 |  14 |  15
---|---|---|---|---|---|---|---
acc. |  58.5 |  62.0 |  64.1 |  64.5 |  63.6 |  61.9 |  59.7

The optimal accuracy is achieved when the encoder and decoder have the same
depth. This behavior is different from MAE’s [21], whose encoder and decoder
are asymmetric.

##  B Fine-tuning Results

In addition to linear probing, we also report end-to-end fine-tuning results.
We closely followed MAE’s protocol [21]. We use clean, $256{\times}256$-sized
images as the inputs to the encoder. Globally average pooled outputs are used
as features for classification. The training batch size is 1024, initial
learning rate is $4{\times}10^{-3}$, weight decay is 0.05, drop path [24] is
0.1, and training length is 100 epochs. We use a layer-wise learning rate
decay of 0.85 (B) or 0.65 (L). MixUp [43] (0.8), CutMix [42] (1.0), RandAug
[8] (9, 0.5), and exponential moving average (0.9999) are used, similar to
[21]. The results are summarized as below:

method | ViT-B | ViT-L
---|---|---
MoCo v3 | 83.2 | 84.1
MAE | 83.6 | 85.9
_l_ -DAE | 83.7 | 84.7

Overall, both autoencoder-based methods are better than MoCo v3. _l_ -DAE
performs similarly with MAE with ViT-B, but still fall short of MAE with
ViT-L.

## References

  * Ba et al. [2016] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton.  Layer normalization.  _arXiv:1607.06450_ , 2016.
  * Bertalmio et al. [2000] Marcelo Bertalmio, Guillermo Sapiro, Vincent Caselles, and Coloma Ballester.  Image inpainting.  In _SIGGRAPH_ , 2000.
  * Bishop and Nasrabadi [2006] Christopher M Bishop and Nasser M Nasrabadi.  _Pattern recognition and machine learning_.  Springer, 2006.
  * Burger et al. [2012] Harold Christopher Burger, Christian J Schuler, and Stefan Harmeling.  Image denoising: Can plain neural networks compete with BM3D?  In _CVPR_ , 2012.
  * Chen et al. [2023] Kai Chen, Zhili Liu, Lanqing Hong, Hang Xu, Zhenguo Li, and Dit-Yan Yeung.  Mixed autoencoder for self-supervised visual representation learning.  In _CVPR_ , 2023.
  * Chen et al. [2020] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In _ICML_ , 2020.
  * Chen et al. [2021] Xinlei Chen, Saining Xie, and Kaiming He.  An empirical study of training self-supervised Vision Transformers.  In _ICCV_ , 2021.
  * Cubuk et al. [2020] Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le.  Randaugment: Practical automated data augmentation with a reduced search space.  In _CVPR Workshops_ , 2020.
  * Deng et al. [2009] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  ImageNet: A large-scale hierarchical image database.  In _CVPR_ , 2009.
  * Devlin et al. [2019] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _NAACL_ , 2019.
  * Dhariwal and Nichol [2021] Prafulla Dhariwal and Alexander Nichol.  Diffusion models beat GANs on image synthesis.  In _NeurIPS_ , 2021.
  * Donahue and Simonyan [2019] Jeff Donahue and Karen Simonyan.  Large scale adversarial representation learning.  _arXiv:1907.02544_ , 2019.
  * Donahue et al. [2017] Jeff Donahue, Philipp Krähenbühl, and Trevor Darrell.  Adversarial feature learning.  In _ICLR_ , 2017.
  * Dong et al. [2014] Chao Dong, Chen Change Loy, Kaiming He, and Xiaoou Tang.  Learning a deep convolutional network for image super-resolution.  In _ECCV_ , 2014.
  * Dosovitskiy et al. [2021] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _ICLR_ , 2021.
  * Esser et al. [2021] Patrick Esser, Robin Rombach, and Björn Ommer.  Taming transformers for high-resolution image synthesis.  In _CVPR_ , 2021.
  * Fang et al. [2022] Yuxin Fang, Li Dong, Hangbo Bao, Xinggang Wang, and Furu Wei.  Corrupted image modeling for self-supervised visual pre-training.  _arXiv:2202.03382_ , 2022.
  * Goodfellow et al. [2014] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In _NeurIPS_ , 2014.
  * Goyal et al. [2017] Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He.  Accurate, large minibatch SGD: Training ImageNet in 1 hour.  _arXiv:1706.02677_ , 2017.
  * He et al. [2020] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning.  In _CVPR_ , 2020.
  * He et al. [2022] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick.  Masked autoencoders are scalable vision learners.  In _CVPR_ , 2022.
  * Heusel et al. [2017] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.  GANs trained by a two time-scale update rule converge to a local Nash equilibrium.  In _NeurIPS_ , 2017.
  * Ho et al. [2020] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  In _NeurIPS_ , 2020.
  * Huang et al. [2016] Gao Huang, Yu Sun, Zhuang Liu, Daniel Sedra, and Kilian Q Weinberger.  Deep networks with stochastic depth.  In _ECCV_ , 2016.
  * Ioffe and Szegedy [2015] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In _ICML_ , 2015.
  * Kingma and Welling [2013] Diederik P Kingma and Max Welling.  Auto-encoding variational bayes.  In _ICLR_ , 2013.
  * LeCun et al. [1989] Yann LeCun, Bernhard Boser, John S Denker, Donnie Henderson, Richard E Howard, Wayne Hubbard, and Lawrence D Jackel.  Backpropagation applied to handwritten zip code recognition.  _Neural computation_ , 1989.
  * Mukhopadhyay et al. [2023] Soumik Mukhopadhyay, Matthew Gwilliam, Vatsal Agarwal, Namitha Padmanabhan, Archana Swaminathan, Srinidhi Hegde, Tianyi Zhou, and Abhinav Shrivastava.  Diffusion models beat GANs on image classification.  _arXiv:2307.08702_ , 2023.
  * Nichol and Dhariwal [2021] Alexander Quinn Nichol and Prafulla Dhariwal.  Improved denoising diffusion probabilistic models.  In _ICML_ , 2021.
  * Oord et al. [2017] Aaron van den Oord, Oriol Vinyals, and Koray Kavukcuoglu.  Neural discrete representation learning.  In _NeurIPS_ , 2017.
  * Pathak et al. [2016] Deepak Pathak, Philipp Krahenbuhl, Jeff Donahue, Trevor Darrell, and Alexei A Efros.  Context encoders: Feature learning by inpainting.  In _CVPR_ , 2016.
  * Peebles and Xie [2023] William Peebles and Saining Xie.  Scalable diffusion models with Transformers.  In _ICCV_ , 2023.
  * Rombach et al. [2022] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In _CVPR_ , 2022.
  * Salimans and Ho [2022] Tim Salimans and Jonathan Ho.  Progressive distillation for fast sampling of diffusion models.  In _ICLR_ , 2022.
  * Simonyan and Zisserman [2015] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In _ICLR_ , 2015.
  * Sohl-Dickstein et al. [2015] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli.  Deep unsupervised learning using nonequilibrium thermodynamics.  In _ICML_ , 2015.
  * Song and Ermon [2019] Yang Song and Stefano Ermon.  Generative modeling by estimating gradients of the data distribution.  _NeurIPS_ , 2019.
  * Song et al. [2020] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole.  Score-based generative modeling through stochastic differential equations.  _arXiv:2011.13456_ , 2020.
  * Vincent et al. [2008] Pascal Vincent, Hugo Larochelle, Yoshua Bengio, and Pierre-Antoine Manzagol.  Extracting and composing robust features with denoising autoencoders.  In _ICML_ , 2008.
  * Xiang et al. [2023] Weilai Xiang, Hongyu Yang, Di Huang, and Yunhong Wang.  Denoising diffusion autoencoders are unified self-supervised learners.  In _ICCV_ , 2023.
  * Xie et al. [2022] Zhenda Xie, Zheng Zhang, Yue Cao, Yutong Lin, Jianmin Bao, Zhuliang Yao, Qi Dai, and Han Hu.  SimMIM: A simple framework for masked image modeling.  In _CVPR_ , 2022.
  * Yun et al. [2019] Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo.  Cutmix: Regularization strategy to train strong classifiers with localizable features.  In _ICCV_ , 2019.
  * Zhang et al. [2018a] Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz.  mixup: Beyond empirical risk minimization.  In _ICLR_ , 2018a.
  * Zhang et al. [2018b] Richard Zhang, Phillip Isola, Alexei A Efros, Eli Shechtman, and Oliver Wang.  The unreasonable effectiveness of deep features as a perceptual metric.  In _CVPR_ , 2018b.


# Understanding and Improving Deep Graph Neural Networks:
A Probabilistic Graphical Model Perspective

Jiayuan Chen1 Xiang Zhang2 Yinfei Xu2,∗ Tianli Zhao3 Renjie Xie4,5&Wei Xu4,5
1School of Computer Science and Engineering, Southeast University
2School of Information Science and Engineering, Southeast University
3Institute of Automation, Chinese Academy of Sciences
4National Mobile Communications Research Laboratory, Southeast University
5Purple Mountain Laboratories

###### Abstract

Recently, graph-based models designed for downstream tasks have significantly
advanced research on graph neural networks (GNNs). GNN baselines based on
neural message-passing mechanisms such as GCN and GAT perform worse as the
network deepens. Therefore, numerous GNN variants have been proposed to tackle
this performance degradation problem, including many deep GNNs. However, a
unified framework is still lacking to connect these existing models and
interpret their effectiveness at a high level. In this work, we focus on deep
GNNs and propose a novel view for understanding them. We establish a
theoretical framework via inference on a probabilistic graphical model. Given
the fixed point equation (FPE) derived from the variational inference on the
Markov random fields, the deep GNNs, including JKNet, GCNII, DGCN, and the
classical GNNs, such as GCN, GAT, and APPNP, can be regarded as different
approximations of the FPE. Moreover, given this framework, more accurate
approximations of FPE are brought, guiding us to design a more powerful GNN:
coupling graph neural network (CoGNet). Extensive experiments are carried out
on citation networks and natural language processing downstream tasks. The
results demonstrate that the CoGNet outperforms the SOTA models.

##  1 Introduction

Graphs have received increasing attention in recent years, driving the
unprecedented development of graph neural networks (GNNs). In particular,
neural graph-based models are applied to various downstream tasks such as
biology Aittokallio and Schwikowski (2006); Fout et al. (2017), social
analysis Li and Goldwasser (2019), and computer vision Yan et al. (2018); Li
et al. (2019); Han et al. (2022). However, it has been observed that classical
GNNs like GCN and GAT achieve the best performance in most downstream tasks at
only a two-layer network. With the network depth increasing, the performance
drops rapidly.

Hence, a profusion of work tries to tackle the performance degradation
problem. These deep GNN models design various feature propagation processes
based on the message-passing mechanism of GNN. For instance, JKNet Xu et al.
(2018) flexibly adjusts the neighbor range of each node by using a layer
aggregation network architecture. Another excellent model Deep Adaptive Graph
Neural Network decouples transformation and propagation to leverage larger
receptive fields. GCNII Chen et al. (2020a) adds Initial residual and Identity
mapping based on GCN, extending GCN to a $k$-th order of polynomial filter.
Despite fruitful achievements, these works study GNNs from various
perspectives, including the spatial and spectral domains that have garnered
the most attention in recent years. Driven by the different interpretations of
GNNs, a question arises: Is there a framework that can interpret these deep
GNNs uniformly? If such a framework exists, we can leverage it to understand
the performance degradation problem of classical GNNs more in-depth and
identify the weakness of the existing deep GNNs to facilitate their
development.

In this paper, we understand graph convolution from a probabilistic
perspective and develop a general interpretation framework for deep GNNs. GNNs
and probabilistic graphical models (PGMs) are prominent tools for studying
structured data. Dai et al. (2016) note the iterative propagation scheme of
variational inference in PGMs, which provides an intuitively appealing
direction for connecting GNNs. Thus, we start from the variational inference
of Markov random fields and obtain its iterative solution embedded in the
Hilbert space. Inspired by the close connection between GNNs and the first-
order Taylor expansion of the iterative solution, we establish a unified
framework for representing different GNNs and their deep variants. We then
incorporate some popular deep graph networks, such as JKNet, DGCN, and GCNII
Xu et al. (2018); Cong et al. (2021); Chen et al. (2020a), into the developed
theoretical framework with the help of high-order Taylor approximation.
Furthermore, with the proposed framework, we analyze the performance
degradation problem and design a more effective model, the Coupling Graph
Neural Network (CoGNet). Through extensive experiments on three semi-
supervised node classification benchmarks and natural language processing
downstream tasks, including text classification and multi-hop question
answering, we demonstrate that the CoGNet achieves strong performances in both
shallow and deep network layers, including multiple SOTA results.

##  2 Related Work

###  2.1 Graph Neural Networks

Graph Neural Network (GNN) is a framework for graph representation learning.
The basic GNNs follow a neural message-passing mechanism. They exchange
messages between connected nodes and update node features using neural
networks. In the past few years, some baseline GNN models, such as GCN, GIN,
and GAT Welling and Kipf (2016); Xu et al. (2019b); Veličković et al. (2017),
have been proposed and achieved great popularity. These models have been
successfully applied to many downstream tasks, including recommender systems
Ying et al. (2018); He et al. (2020), drug analysis Duvenaud et al. (2015),
community detection Chen et al. (2020b); Liu et al. (2021); Okuda et al.
(2021), etc.

However, these GNN models are known to suffer from performance degradation
when deepening the network structures. This phenomenon may be caused by
problems such as over-parameterization, over-smoothing, and weak
generalization of the model. Many works on improving the performance of deep
GNN models have been proposed recently. Jumping Knowledge Network Xu et al.
(2018) is one of the earliest deep GNNs, combining the node representations of
each layer at the last layer. Another excellent model DAGNN Liu et al. (2020)
adaptively incorporates information from large receptive fields. Recently,
DropEdge Rong et al. (2020) randomly mutes a certain number of edges during
each training epoch to alleviate the over-smoothing issue. Other deep models,
such as GCNII Chen et al. (2020a) and DGCN Cong et al. (2021), have also
achieved good performance. However, these models design their propagations
from different perspectives, and a unified language is lacking to describe
them.

###  2.2 Interpretability of GNNs

Theoretical interpretability has become a focus of research on graph
representation learning. As a generalization of convolution on graph-
structured data, graph convolution has inspired many works to explore GNNs
from the spectral perspective. Li et al. (2018) shows that the propagation
process of the GCN is a low-pass filter and attributes performance degradation
to the over-smoothing problem. Ma et al. (2021) understands GNNs as graph
signal denoising. Graph wavelet neural network Xu et al. (2019a) uses graph
wavelets to replace the Fourier basis in GCN. Defferrard et al. (2016); Wu et
al. (2019); Levie et al. (2019) design the network aggregation from the
perspective of spectral filters. Another line of work analyzes the connections
between GNNs and graph isomorphism testing. Xu et al. (2019b) proves that
message-passing GNNs are no more powerful than the Weisfeiler-Lehman (WL)
algorithm Weisfeiler and Leman (1968) when given discrete information as node
features. Feng et al. (2022) shows that the expressive power of $K$-hop
message passing is bounded by 3-WL test. Most recently, several works have
been devoted to generalizing deep learning theory to graph machine learning.
Du et al. (2019) uses Neural Tangent Kernel to analyze infinitely wide multi-
layer GNNs trained by gradient descent. Esser et al. (2021) explores
generalization in GNNs through VC Dimension based generalization error bounds.
In this work, we understand GNNs from a novel probabilistic perspective and
analyze their intrinsic connections.

##  3 GNNs as Embedded Graphical Models

In this section, we establish the connections between the GNN models and the
probabilistic inference in graphical models. We first introduce the notations
used throughout the paper.

Notations. Given a weighted undirected Graph $G=(V,E)$ with $n$ nodes
$v_{i}\in V$ and edges $\left(v_{i},v_{j}\right)\in E$, let
$\mathbf{A}\in\mathbb{R}^{n\times n}$ denote the adjacency matrix and
$\mathbf{D}$ denote the diagonal degree matrix, i.e.,
$\mathbf{D}_{ii}=\sum_{(v_{i},v_{j})\in E}\mathbf{A}_{ij}$. Let
$\hat{\mathbf{A}}=\left(\mathbf{D}+\mathbf{I}_{n}\right)^{-\frac{1}{2}}(\mathbf{I}_{n}+\mathbf{A})(\mathbf{D}+\mathbf{I}_{n})^{-\frac{1}{2}}$
denote a normalized variant of the adjacency matrix (with self-loops). We
denote the node feature matrix as $\mathbf{X}\in\mathbb{R}^{n\times d}$ for a
$d$-dimensional feature vector $\mathbf{x}_{i}$ associated with each node
$v_{i}$ and use $\mathcal{N}(i)$ to represent the set of neighboring nodes of
node $v_{i}$ (including itself).

We next introduce message passing in graphical models. Our starting point is
structured data modeled with the PGM. Markov random field is a PGM based on an
undirected graph. It is especially suitable for handling high-dimensional data
with graph structure. With the conditional independence assumptions of graph
structure, we can simplify the joint distribution $p$ over some set of
discrete random variables $\mathcal{X}=\\{x_{1},...,x_{n}\\}$, and then solve
it by optimization. Considering an undirected Graph $G$, we introduce latent
variable ${z}_{u}$ associated with each node $u$. The input node features
$\mathbf{X}\in\mathbb{R}^{n\times d}$ is the observed variable. The aim is to
find conditional distributions $p\left(\mathbf{z}\mid\mathbf{X}\right)$ over
latent variables $\mathbf{z}=\\{{z}_{1},\cdots,z_{n}\\}$ so that we can make
inference.

For a Markov random field with graph $G$, computing the posterior $p$ is a
computationally intractable task. Mean-field variational inference, one of the
most popular approximate inference techniques, is employed here for
approximation:

$p\left({z}_{1},\cdots,{z}_{n}\mid\mathbf{X}\right)\approx\prod_{i=1}^{n}q_{i}\left({z}_{i}\right).$
(1)

By minimizing the free energy between the approximate posterior $q$ and the
true posterior $p$, we obtain the optimal distribution $q^{*}$. It’s hard to
find a direct solution to this optimization problem. Wainwright et al. (2008)
shows that the above optimization problem satisfies the following fixed point
equations:

$\log
q^{*}_{i}\left(z_{i}\right)=c+\log\left(\phi\left(z_{i},x_{i}\right)\right)+\sum_{j\in\mathcal{N}(i)}\sum_{z_{j}}q^{*}_{j}\left(z_{j}\right)\log\left(\psi\left(z_{i},z_{j}\right)\right),$

where $c$ is a constant, $\psi$ and $\phi$ are non-negative potential
functions. The above equation exhibits the relationship between marginals of
adjacent nodes, and we can obtain its iterative form solution:

$\displaystyle\log q_{i}^{(l+1)}\left(z_{i}\right)=$ $\displaystyle
c^{(l)}_{i}+\log\left(\phi\left(z_{i},x_{i}\right)\right)$ (2)
$\displaystyle+\sum_{j\in\mathcal{N}(i)}\sum_{z_{j}}q^{(l)}_{j}\left(z_{j}\right)\log\left(\psi\left(z_{i},z_{j}\right)\right),$

where $q_{i}^{*}(z_{i})=\underset{l\rightarrow\infty}{\lim}q^{l}(z_{i})$. We
can abbreviate Eq. (2) as:

$q_{i}^{(l+1)}\left({z}_{i}\right)=\mathcal{F}_{i}\left({z}_{i},{q^{(l)}_{j}\left(z_{j}\right)}\right),\quad{j\in\mathcal{N}(i)}.$
(3)

Here $\mathcal{F}_{{i}}(\cdot)$ is a function determined by the potential
functions. Note that these potential functions are defined on the clique where
node $i$ is located. Eq. (3) establishes an iterative update formula to
aggregate the neighbor information. And Dai et al. (2016) further mapped it to
a high-dimensional space with the help of Hilbert space embedding, thus
linking the high-dimensional data and the low-dimensional structure. They map
distributions $q(z)$ into Hilbert space using some injective functions
$\phi_{\alpha}$. As a result, we can obtain the embedding ${\mu}_{z_{i}}$ in
Hilbert space by
${\mu}_{z_{i}}:=\int_{{z_{i}}}\phi_{\alpha}(z_{i})q_{i}(z_{i})dz_{i}$.

######  Theorem 1.

Smola et al. (2007) Given a finite-dimensional feature map $\phi$ that maps
$p(x)$ to $\mu$, if $\phi$ is injective, then any function that applies on
p(x) is equivalent to computing a corresponding function on $\mu$.

According to Theorem 1, we can denote the function corresponding to
$\mathcal{F}_{{i}}$ in Eq. (3) after the kernel embedding as
$\tilde{\mathcal{F}}_{\alpha}$. For the recursive expression of $q_{{i}}$ (Eq.
(3)), we have the following iterative formula after Hilbert space embedding:

${u}_{i}^{(l)}=\tilde{\mathcal{F}}_{\alpha,i}\left({u}_{j}^{(l-1)},{j\in\mathcal{N}(i)}\right).$
(4)

In order to have a more straightforward distinction, we use $\ell$ to denote
the number of network layers in graph networks and $l$ to represent the number
of iterations.

Following the breakthrough work of Dai et al. (2016), several papers put
forward further discussions. Grover et al. (2019) find the theoretical
connection between message-passing GNN and mean-field variational inference.
This inspires us to apply the idea to analyzing GNNs and explore it further.
For simplicity of derivation, we start from the assumption that $u_{i}$ is
unidimensional. We denote $\mathbf{U}_{i}\in\mathbb{R}^{m\times
1},m=\left|\mathcal{N}(i)\right|$, as the vector consisting of the
neighbourhoods of node $i$:

$\mathbf{U}_{i}^{(l)}=\left[u_{1}^{(l)},u_{2}^{(l)},...,u_{m}^{(l)}\right]^{\top},\quad
m\in\mathcal{N}(i).$ (5)

where $u_{m}^{(l)}$ is the $m$-th entrie of vector $\mathbf{U}_{i}^{(l)}$. Now
we can give the Taylor expansion of Eq. (4) at
$\mathbf{U}_{i}^{(l)}=\mathbf{0}$ as:

$\displaystyle u_{i}^{(l)}=$
$\displaystyle\tilde{\mathcal{F}}_{\alpha,{i}}(\mathbf{0})+\tilde{\mathcal{F}}_{\alpha,{i}}^{\prime}(\mathbf{0})\mathbf{U}_{i}^{(l-1)}+\frac{1}{2}{\mathbf{U}_{i}^{\left(l-1\right)^{\top}}}\tilde{\mathcal{F}}_{\alpha,{i}}^{\prime\prime}(\mathbf{0})\mathbf{U}_{i}^{(l-1)}$
$\displaystyle+\cdots+\frac{\tilde{\mathcal{F}}_{\alpha,{i}}^{n}(\mathbf{0})}{n!}\left[\mathbf{U}_{i}^{(l-1)}\right]^{n}+o\left[\mathbf{U}_{i}^{(l-1)}\right]^{n}.$
(6)

We denote the $n^{th}$ order derivative by
$\tilde{\mathcal{F}}_{\alpha,{i}}^{n}$. The value of
$\tilde{\mathcal{F}}_{\alpha,{i}}^{n}(\mathbf{0})$ is node-specific. Actually,
we can already find the connection between the probabilistic graph model and
the GNN through Eq. (3). The embedded high-dimensional variables and the
iterative message-passing mechanism match perfectly with GNN. To make it more
understandable, in the following, we briefly analyze the first-order
approximation of Eq. (3):

$u_{i}^{(l)}\approx\tilde{\mathcal{F}}_{\alpha,{i}}(\mathbf{0})+\tilde{\mathcal{F}}_{\alpha,{i}}^{\prime}(\mathbf{0})\mathbf{U}_{i}^{\left(l-1\right)},$
(7)

where $\mathbf{U}_{i}^{(l-1)}$ consists of its neighbors and $u_{i}^{(l)}$
corresponds to the embedding of conditional probability $q_{i}$ in the Hilbert
space. We can find that Eq. (7) satisfies the recursive message-passing
mechanism.
$\tilde{\mathcal{F}}_{\alpha,{i}}^{\prime}(\mathbf{0})\mathbf{U}_{i}^{(l-1)}$
is an inner product term, which aggregates neighbors $u_{j}^{(l-1)}$
(including $u_{i}^{(l-1)}$) after multiplying by the coefficients:

$u_{i}^{(l)}\approx\tilde{\mathcal{F}}_{\alpha,{i}}(\mathbf{0})+\sum_{j\in\mathcal{N}{(i)}}f_{ij}\cdot
u_{j}^{(l-1)},$ (8)

where
$[f_{ij},j\in\mathcal{N}(i)]^{\top}\triangleq\tilde{\mathcal{F}}_{\alpha,{i}}^{\prime}(\mathbf{0})$.
This form is exactly consistent with the neural message-passing mechanism of
GNN.

##  4 A Unified Framework

In the previous section, we elaborate message-passing mechanism of GNN from
the perspective of inference on PGMs. According to Eq. (8), we can find that
the vanilla GNN is equivalent to the first-order approximation of Eq. (3). In
this section, we establish a unified framework to interpret existing GNN
baselines and some well-designed deep GNN variants.

The formula of variational inference after embedding into Hilbert space
exhibits a close connection with the mechanism of GNNs. Eq. (4) aggregates
neighborhood variables and updates its own variable, which is the same as the
key core of neural message-passing. This implies that different GNN
propagation mechanisms are different approximations of the function
$\tilde{\mathcal{F}}_{\alpha,i}$. With the help of Taylor expansion Eq. (3),
we can understand this framework more clearly. In the following, we
theoretically prove that the propagation mechanisms of some popular GNN
variants can be seen as fitting different order approximations of Eq. (3).

###  4.1 Interpreting GCN and SGC

Graph Convolutional Network (GCN) is a popular baseline GNN inspired by
spectral graph convolutions. We show the definition of vanilla graph
convolution Welling and Kipf (2016) with bias as follows:

$h_{i}^{(\ell)}=\sigma\left(b^{(\ell)}_{i}+\sum_{j\in\mathcal{N}{(i)}}\frac{w_{j}^{(\ell)}}{\sqrt{d_{i}d_{j}}}h_{j}^{(\ell-1)}\right).$
(9)

A $k$-layer GCN can aggregate the messages of $k$-hop neighbors. Simplifying
Graph Convolutional Network (SGC) removes nonlinearity activation in GCN while
doing propagations. We will discuss the effect of nonlinearity activation in
Section 4.5. Here we assume that nonlinearity activations do not significantly
affect the network and analyze the two similar models, SGC and GCN, together.

As a basic message-passing neural network, GCN naturally satisfies the form of
Eq. (8). To be specific, $\tilde{\mathcal{F}}_{\alpha,{i}}$ is determined by
the potential functions defined on the clique, but since the kernel mapping
$\phi_{\alpha}$ is undetermined, the learnable weights $w$ coming with clique-
related constants $d_{i},d_{j}$ are used to approximate it. On the other hand,
the bias in Eq. (9) corresponds to the constant term in Eq. (8). The specific
equivalence is as follows:

$h_{i}^{(\ell)}\Rightarrow u_{i}^{(l)},\quad
b_{i}\Rightarrow\tilde{\mathcal{F}}_{\alpha,{i}}(\mathbf{0}),\quad\frac{w_{j}^{(\ell)}}{\sqrt{d_{i}d_{j}}}\Rightarrow
f_{ij}.$

The aggregation layer of the GCN is inherently connected to the first-order
approximation of Eq. (3). Through the analysis in Section 5.1, we will find
that such a propagation process will deteriorate the performance after the
network structure is deepened.

###  4.2 Interpreting GAT

Graph attention network (GAT) Veličković et al. (2017) applies a popular
attention mechanism to the aggregation layer. It uses attention weights to
weigh aggregate neighbor messages. The ways to parameterize the attention
weights $\alpha$ can be dot product or feedforward neural network. The layers
of the GAT-styled model can be represented as follows:

$\displaystyle
h^{(\ell)}_{i}=\sigma\left(\sum_{j\in\mathcal{N}(i)}\alpha_{ij}w_{j}h_{j}^{(\ell-1)}\right),$
(10)
$\displaystyle\alpha_{ij}=\text{Softmax}\left(f(h_{i}^{(\ell-1)},h_{j}^{(\ell-1)})\right),$

where $\alpha_{ij}$ denotes the attention weight on neighbor
$j\in\mathcal{N}(i)$ when we are aggregating information at node $v_{i}$, and
$f(\cdot)$ denotes a learnable attention weight calculation function.

We notice that the node aggregation process of GCN and GAT is quite similar.
Compared with GCN, which uses the degree of nodes $d$ for weighted
aggregation, GAT uses attention weights $\alpha$ instead. So its equivalence
with Eq. (8) is:

$\alpha_{ij}w_{j}^{\ell}\approx\left.\dfrac{\partial\tilde{\mathcal{F}}_{\alpha,{i}}(\mathbf{U}_{i})}{\partial
u_{j}}\right|_{\mathbf{U}_{i}=0}.$ (11)

The attention mechanism has a greater computational cost, but its attention
coefficients can better fit $\tilde{\mathcal{F}}_{\alpha,{i}}$ than GCN. This
is because the value of the function $\tilde{\mathcal{F}}_{\alpha,{i}}$ is
determined by the node $v_{i}$ and its neighbors. GAT can learn the features
of the clique according to the node vector and its neighbors, while GCN can
only use the node degree. The experimental results in Section 6 also verified
this conclusion.

Both GCN and GAT are derived based on the first-order Taylor expansion, so
they have performance degradation problems. There are several existing works
on this issue, and their network architectures can alleviate the performance
degradation problem of deep networks to some extent. In the following, we will
interpret them from the perspective of PGM representation and analyze why they
can achieve better results.

###  4.3 Interpreting APPNP and GCNII

In the previous section, we elaborated on the classical GNNs under our
framework. Intuitively, we have two ways to design a more powerful GNN. One is
to find a more precise technique to fit $\tilde{\mathcal{F}}_{\alpha,{i}}$,
and the other is to perform message propagation based on the higher-order
expansion of Eq. (3). Indeed, the propagation process of APPNP and GCNII can
be regarded as the generalized form of second-order expansion. To prove this,
we first briefly present two models.

APPNP Gasteiger et al. (2018) is a simple GNN originated from Personalized
PageRank. It can be considered as the linear combination of the initial
features and the current layer:

$\mathbf{H}^{(\ell+1)}=(1-\alpha)\hat{\mathbf{A}}\mathbf{H}^{(\ell)}+\alpha\mathbf{H}^{(0)}.$
(12)

GCNII Chen et al. (2020a) and APPNP explore the improvement of GCN from
different perspectives. Still, the feature propagation of GCNII can be
regarded as introducing identity mapping and a trainable weight matrix based
on APPNP. The network propagation of GCNII is:

$\displaystyle\mathbf{H}^{(\ell+1)}=\sigma\left(\left(\left(1-\alpha\right)\hat{\mathbf{A}}\mathbf{H}^{(\ell)}+\alpha\mathbf{H}^{(0)}\right)\right.$
(13)
$\displaystyle\qquad\qquad\qquad\left.\left(\left(1-\beta\right)\mathbf{I}_{n}+\beta\mathbf{W}^{(\ell)}\right)\right).$

The identity mapping in GCNII model helps assure that it performs at least as
well as a shallow network. While in the theoretical analysis, we do not need
to consider network optimization. In this case, we can reformulate the
aggregation formula of GCNII as:

$\mathbf{H}^{(\ell+1)}=\sigma\left(\hat{\mathbf{A}}\mathbf{H}^{(\ell)}\mathbf{W}^{(\ell_{1})}+\mathbf{H}^{(0)}\mathbf{W}^{(\ell_{2})}\right).$
(14)

When we adopt $\beta=0$ in GCNII, we can find out that GCNII reduces to APPNP
Gasteiger et al. (2018). In other words, APPNP can be seen as a degenerate
form of GCNII. Next, we will only analyze the propagation process of GCNII,
and it is straightforward to modify the proof to obtain a nearly equivalent
result for the APPNP.

######  Proposition 1.

The propagation process of GCNII is equivalent to the second-order expansion
of Eq. (3), where the initial residual corresponds to the approximation of the
quadratic term.

###### Proof.

We start with the second-order Taylor expansion:

$\displaystyle u_{i}^{(l)}$
$\displaystyle\approx\tilde{\mathcal{F}}_{\alpha,{i}}(\mathbf{0})+\tilde{\mathcal{F}}^{\prime}_{\alpha,{i}}(\mathbf{0})\mathbf{U}_{i}^{(l-1)}$
(15)
$\displaystyle+\frac{1}{2}\mathbf{U}_{i}^{(l-1)^{\top}}\tilde{\mathcal{F}}_{\alpha,{i}}^{\prime\prime}(\mathbf{0})\mathbf{U}_{i}^{(l-1)}+o\left[\mathbf{U}_{i}^{(l-1)}\right]^{2}.$

We cannot directly express the quadratic term in the form of a graph
convolution. To circumvent this problem, we approximate it with a linear term
of the node features $\mathbf{U}_{i}$. We know from Eq. (5) that
$\mathbf{U}_{i}$ is a tensor consisting of the features of node $v_{i}$ and
its neighbors. So we can rewrite the quadratic term as:

$\frac{1}{2}\mathbf{U}_{i}^{(l-1)^{\top}}\tilde{\mathcal{F}}_{\alpha,{i}}^{\prime\prime}(\mathbf{0})\mathbf{U}_{i}^{(l-1)}=f_{1}\left({u}_{i}^{(0)}\right)+\sum_{j\in\mathcal{N}(i)}f_{2}\left(u^{(l-1)}_{j}\right),$
(16)

where $f_{1}$ and $f_{2}$ denote different transformations. Hence Eq. (15) is
deduced as the following form:

$u_{i}^{(l)}\approx\tilde{\mathcal{F}}_{\alpha,{i}}(\mathbf{0})+\sum_{j\in\mathcal{N}{(i)}}g_{ij}\cdot
u_{j}^{(l-1)}+f_{1}\left({u}_{i}^{(0)}\right),$ (17)

where we only keep the linear terms about $u_{i}$ and $u_{j}$, and $g_{ij}$
represent the parameters. We represent Eq. (15) as the first-order expansion
plus the initial residual, which is consistent with the ideas of GCNII and
APPNP. The detailed proof is deferred to the appendix. ∎

With this connection, one can show that the propagation process of GCNII is
equivalent to the approximate form of the second-order expansion of Eq. (3).
This means that our framework based on PGM representation can well explain
this deep GNN model.

###  4.4 Interpreting JKNet and DGCN

Jumping Knowledge Network (JKNet) and Decoupled Graph Convolutional Network
(DGCN) are well-designed deep GNNs, and we connect their propagation
operations in our framework using a similar pattern.

The JKNet proposed by Xu et al. (2018) combines all previous representations
at the last layer. The specific combination mechanisms can be max-pooling,
concatenation, and LSTM-attention. For convenience, as is similar to Ma et al.
(2021), we omit the non-linear activation $\sigma(\cdot)$. We denote
$\mathbf{Z}$ as the final output of the model and take the attention mechanism
as an example of combination process for analyzing. The attention-JKNet can be
described as:

$\mathbf{Z}=\sum_{\ell=1}^{L}\alpha_{\ell}\hat{\mathbf{A}}^{\ell}\mathbf{X}\mathbf{W}^{\ell},$
(18)

where $\alpha_{\ell}$ are learnable attention weights and
$\sum_{\ell=1}^{L}\alpha_{\ell}=1$. DGCN adopts a representation ensemble
similar to JKNet, and uses a transformation process in each layer similar to
GCNII :

$\mathbf{Z}=\sum_{\ell=1}^{L}\alpha_{\ell}\hat{\mathbf{A}}^{\ell}\mathbf{X}\left(\beta_{\ell}\mathbf{W}^{(\ell)}+\left(1-\beta_{\ell}\right)\mathbf{I}_{n}\right).$
(19)

$\alpha_{\ell}$ and $\beta_{\ell}$ are trainable weights, $\mathbf{I}_{n}$ is
the identity mapping. DGCN ensures that the performance of the deep network is
at least not worse than the shallow network by adding identity mapping. In
fact, its propagation process is the same as JKNet.

For this kind of operation that ensemble the representations of $k$ layers, it
corresponds to the $k$-th expansion of Eq. (3):

$u_{i}^{(l)}=\sum_{k=1}^{K}\frac{\tilde{\mathcal{F}}_{\alpha,{i}}^{k}(\mathbf{0})}{k!}\left[\mathbf{U}_{i}^{(l-1)}\right]^{k},$
(20)
$\frac{\tilde{\mathcal{F}}_{\alpha,{i}}^{k}(\mathbf{0})}{k!}\left[\mathbf{U}_{i}^{(l-1)}\right]^{k}\Rightarrow\alpha_{k}\hat{\mathbf{A}}^{k}\mathbf{X}\mathbf{W}^{k}.$

Since the $k$-th order term of the expansion will contain high-dimensional
tensors, we do not show the specific correspondence here. But we can know that
the $k$-th term in Eq. (3) can aggregate k-hop information, and the
coefficient items
$\frac{\tilde{\mathcal{F}}_{\alpha,{i}}^{k}(\mathbf{0})}{k!}$ are fitted by
the trainable weight matrix.

In section 4.3, we proved that the transformations and identity mappings of
GCNII can effectively reduce the error, so DGCN that applies a similar
transformations method will theoretically perform better than JKNet. The
experimental results also verify our presumptions.

###  4.5 Discussion on Non-linearity

In the above subsections, we did not pay attention to non-linearity when
analyzing these models. Here we discuss the role of activation functions in
our framework. Recall what we stated in section 3, when we embed the formula
of the obtained iterative solution into the Hilbert space, the mapping
function needs to be injective. In Xu et al. (2019b), the authors discussed
the graph convolution and proved its injectivity. This implies that adding an
activation function (ReLU) satisfies our assumption. On the other hand, our
network parameters need to fit the function $\tilde{\mathcal{F}}$, and the
non-linear activation can help the network better fit the non-linear
functions.

##  5 On Designing Deep GNNs

In section 4, we obtained a unified framework that establishes the connection
between the GNN models and the Taylor expansions of Eq. (4). However, the
popular message-passing GNNs, such as GCN and GAT, are known to suffer from
the performance degradation problem, which limits the deepening of their
network structure. In this section, we use our framework to understand the
performance degradation problem and explore a methodology to improve GNNs.

###  5.1 Performance Degradation Problem

Several works study this performance degradation phenomenon from different
perspectives, including generalization capability, low pass filtering on
graphs, optimization of GNN, etc. Here we use the relationship between the GNN
and Eq. (3) to analyze the reasons for the performance degradation of the
classical GNNs.

We know that after enough iterations of Eq. (3), $q^{l}$ will converge to the
optimal solution $q^{*}$. However, the propagation formula of GNN is not
identical to Eq. (3) (Hilbert space embedding of Eq. (3)), but more similar to
its first-order approximation. This means each layer of the GNN introduces an
extra noise $\epsilon^{(l)}$ when updating $q^{(l)}$:

$\hat{q_{i}}^{(l+1)}\left({z}_{i}\right)+\epsilon_{i}^{(l+1)}={F}_{i}\left({z}_{i},\hat{q_{j}}^{(l)}\left(z_{j}\right)\right),\quad{j\in\mathcal{N}(i)},$
(21)

where $F_{i}$ denotes the approximate form of Eq. (3), and $\hat{q_{i}}$
denotes the iterative result111Technically, the iteration of the GNN acts on
the embedding vector of $q_{i}$, here we simply replace it with $q_{i}$. of
the GNNs. As the network deepens (the number of iterations increases), the
convergence rate of $q^{(l)}$ gradually slows down, but the accumulation of
errors $\epsilon^{(l)}$ increases. Therefore, the performance of baseline GNNs
degrades greatly when stacking more layers. For concreteness, we limit our
discussion here. We refer readers to the appendix for a more detailed
description.

###  5.2 Coupling Graph Neural Network

Based on the established framework, we have some approaches to improve the
performance of the GNN model from a high-level view. Using GNN for semi-
supervised node classification can be regarded as a marginal distribution
estimation of latent variables on PGMs. Thus, we can improve GNN from the
perspective of the iterative solution of PGM. A deeper network corresponds to
more iterations in Eq. (4); hence it can obtain better results. But this still
requires the propagation process of the network to fit Eq. (3) as closely as
possible. The approximation to Eq. (3) will introduce errors, causing
performance degradation after the network reaches a certain depth.

Intuitively, Eq. (3) can be considered as the upper bound of the performance
that variants of GNN can achieve. However, the computational cost of the
propagation process and network structure which completely follows Eq. (3), is
unacceptable. To this end, We need to design a computationally efficient
approximation of Eq. (3) with as little error as possible. We propose a novel
GNN model, Coupling Graph Neural Network (CoGNet), based on our established
framework. Formally, we define the $\ell$-th layer of CoGNet as:

$\displaystyle\mathbf{P}^{(\ell+1)}=\mathcal{G}(\mathbf{H}^{\ell},\mathbf{H}^{\ell-1})(\lambda_{\ell}\mathbf{{W}}_{\ell}+(1-\lambda_{\ell})\mathbf{I}_{n}),$
(22)
$\displaystyle\mathcal{G}(\mathbf{H}^{\ell},\mathbf{H}^{\ell-1})=\gamma_{\ell}\hat{\mathbf{A}}\mathbf{H}^{(\ell)}+(1-\gamma_{\ell})\mathbf{H}^{(\ell-1)},$

where $\lambda$ and $\gamma$ are layer-specific learnable weights, and
$\mathbf{H}^{(\ell+1)}=\text{ReLU}(\mathbf{P}^{(\ell+1)})$.

In fact, the propagation process of CoGNet is equivalent to the second-order
Taylor expansion of Eq. (4), but it is more accurate than GCNII. See the
appendix for more detailed proof. We use the coupling of the two
representations $\mathcal{G}(\mathbf{H}^{\ell},\mathbf{H}^{\ell-1})$ as an
approximation to Eq. (3), which reduces computational cost with small
approximation errors. Note that in deep network layers, we use the initial
representation as the coupling term. On the other hand, the learnable weights
$\lambda$ and $\gamma$ enable the network to fit better the propagation
process of Eq. (3). In addition, following the idea of GCNII, we also
introduce identity mapping to enhance the deep network performance further.

The propagation process of CoGNet, compared with the vanilla GCN, introduces
additional storage costs. Therefore, we follow the idea of the Reversible
Transformer Kitaev et al. (2019) and design reversible coupling, which
recovers the representation of the previous layer in the backward pass without
the need for checkpoints. For the large graph input, the reversible coupling
can effectively reduce the model’s memory requirements.

##  6 Experiment

In this section, we conduct extensive semi-supervised node classification
experiments to evaluate CoGNet. We test the performance of CoGNet on the
citation networks and natural language processing (NLP) downstream tasks.

###  6.1 Citation Networks

####  6.1.1 Dataset and Baselines

We use three standard benchmark citation datasets: Cora, Citeseer, and Pubmed
for semi-supervised node classification. Their statistics are summarized in
the appendix. We use the same fixed training/validation/testing split as
Welling and Kipf (2016) on three datasets. We evaluate our model against the
following baselines:

  * •

Graph convolutions: Chebyshev Defferrard et al. (2016), GCN Welling and Kipf
(2016), GAT Veličković et al. (2017), SGC Wu et al. (2019), APPNP Gasteiger et
al. (2018), Graph U-Net Gao and Ji (2019).

  * •

Deep GNNs: JKNet Xu et al. (2018), GCNII Chen et al. (2020a), DAGNN Liu et al.
(2020), DGCN Cong et al. (2021).

  * •

Regularized GNN: Dropedge Rong et al. (2020), GraphMix Verma et al. (2021),
GRAND Feng et al. (2020). Same as Feng et al. (2020), we report the results of
these methods with GCN as the backbone.

We use CoGNet-S to denote a shallow CoGNet with less than 4 layers. We further
propose the CoGNet++ model, which applies two strategies, Consistency
Regularization Feng et al. (2020) and Dropedge Rong et al. (2020), on CoGNet.

####  6.1.2 Experiment Results

We summarize the performance on citation datasets in Table 1. We run CoGNet
100 times and report the mean and standard deviation of these 100 runs.

The upper part of Table 1 shows the variants of GNN, which are all shallow
models. We can observe that CoGNet-S outperforms most baseline models.
Specifically, the accuracy of the CoGNet compared with GCN and GAT has been
greatly improved. In addition, we also compare the performance of popular deep
GNN models, such as JKNet, GCNII, DAGNN, etc. We observe CoGNet outperforms
all baseline deep GNN models. On the other hand, the deep CoGNet has a
significant improvement over its shallow model, indicating that it can
effectively alleviate the performance degradation problem of GNNs.

To better compare the performance of CoGNet and other deep GNNs, we plot the
performance of the deep models with various numbers of layers in Fig. 1. We
can observe that for the same number of network layers, CoGNet performs best
in most cases. This result verifies the superiority of the propagation process
of our model. It is worth noting that for the performance of shallow layers,
models such as JKNet and GCNII have no advantage over GCN, but CoGNet can
achieve better results than them in shallow networks.

We also apply the popular regularization strategy on graph-based models to our
model, proposing CoGNet++. We can observe that it achieves state-of-the-art
performance on Cora and Pubmed datasets, and it also achieves competitive
results on the Citeseer dataset.

Model | Cora | Citeseer | Pubmed
---|---|---|---
Chebyshev | 81.2 | 69.8 | 74.4
GCN | 81.4 | 70.9 | 79.1
GAT | 83.3 | 72.6 | 78.5
SGC | 81.0 | 71.9 | 78.9
APPNP | 83.3 | 71.8 | 80.1
Graph U-Net | 84.4 | 73.2 | 79.6
JKNet | 81.1 | 69.8 | 78.1
GCNII | 85.5 | 73.4 | 80.2
DAGNN | 84.4 | 73.3 | 80.5
DGCN | 84.8 | 72.7 | 80.0
Dropedge | 82.8 | 72.3 | 79.6
GraphMix | 83.9 | 74.5 | 81.0
GRAND | 85.4 | $\mathbf{75.4}$ | 82.7
CoGNet-S | $84.4\pm 0.7$ | $72.4\pm 0.6$ | $79.6\pm 0.9$
CoGNet | $85.6\pm 0.5$ | $73.7\pm 0.7$ | $80.5\pm 0.5$
CoGNet++ | $\mathbf{86.5\pm 0.3}$ | $75.2\pm 0.4$ | $\mathbf{82.9\pm 0.4}$
Table 1: Summary of semi-supervised classification accuracy results on Cora,
Citeseer, and Pubmed.

481632$60$$70$$80$Acc.Cora

481632$20$$40$$60$Citeseer

481632$40$$60$$80$Pubmed

1

Figure 1: Semi-supervised node classification performance with various depths
from 4 to 32.

###  6.2 NLP Tasks

Many NLP problems can be naturally expressed as graph structures, such as
constructing sentences as graphs with words as nodes and constructing text as
graphs composed of paragraphs and entities. Therefore, neural graph-based
models have emerged in recent years and have received increasing attention.
However, shallow networks limit their performance. For example, in multi-hop
Question Answering (QA), the two-layer graph convolutional network makes the
nodes only access two-hop information and invisible for long-range knowledge.
We only need to replace the GNN in the model Yao et al. (2019); Qiu et al.
(2019) with the CoGNet, which makes the network acquire a wider node
perception field while deepening network layers and thus reach better results.
We conduct experiments to test the performance of CoGNet on two NLP tasks,
including text classification and multi-hop QA. Specific parameters of the
experiment and more detailed illustrations refer to the appendix.

####  6.2.1 Datasets

To thoroughly compare our model with the GCN, we test it on five widely used
datasets of text classification: 20NG, MR, Ohsumed, R8, and R52. Their
statistics are summarized in the appendix. HotpotQA is a dataset for
explainable multi-hop QA.

Model | 20NG | R8 | R52 | Ohsumed | MR
---|---|---|---|---|---
TextGCN | 86.3 | 97.1 | 93.5 | 68.4 | 76.8
+SGC | 88.5 | 97.2 | 94.0 | 68.5 | 75.9
+CoGNet | 88.3 | 97.4 | 94.1 | 69.1 | 77.2
Table 2: Summary of test accuracy on text classification.

####  6.2.2 Text Classification

Text classification is a fundamental task in NLP. Yao et al. (2019) constructs
a corpus-level heterogeneous graph containing document nodes and word nodes
and uses a 2-layer GCN for classification. The results in Table 2 demonstrate
a significant improvement of CoGNet over GCN and SGC in text classification.

####  6.2.3 Multi-hop QA

Multi-hop text-based QA is a popular topic in NLP. Many models explicitly find
the inference path of the question with the help of graphs. For this case,
multi-layer GNNs can obtain multi-hop information to assist inference. DFGN
Qiu et al. (2019) constructs a graph of the entities mentioned in the query
and then dynamically combines them with the help of a GAT. The two-layer GAT
in DFGN can only reach two hops of information. Deepening the network depth
can obtain multi-hop information, but the accuracy of downstream tasks is
affected by the deep GNN. Table 3 reveals the test performance on the Hotpot
QA dataset. We can observe that GCN has the worst performance, while shallow
CoGNet (CoGNet-S) has a significant improvement over DFGN (GAT). On the other
hand, deepening the CoGNet can achieve better results.

Dataset | Model | Joint EM | Joint F1
---|---|---|---
HotpotQA | DFGN | 33.62 | 59.82
GCN | 33.60 | 59.70
CoGNet-S | 33.75 | 60.11
CoGNet | 34.12 | 60.15
Table 3: Summary of test performance on multi-hop QA.

##  7 Conclusion and Future Work

In this paper, we developed a unified theoretical framework to understand the
GNN baselines as well as various deep GNN models using a graphical model
representation. Specifically, we obtained an iterative solution of variational
inference on Markov random fields, and the propagation operation of GNNs can
be represented as approximate forms of it. We also proposed a theoretically
motivated and powerful GNN which performs well on both shallow and deep
network layers. An interesting direction for future work is to establish the
connection between the approximate sampling methods, and the graph neural
network to pursue a faster and more powerful sample-based GNN Chen et al.
(2018); Hamilton et al. (2017); Hasanzadeh et al. (2020). To complete the
picture, understanding and improving the general GNN with the help of other
variational methods would also be interesting.

## References

  * Aittokallio and Schwikowski [2006] Tero Aittokallio and Benno Schwikowski.  Graph-based methods for analysing networks in cell biology.  Briefings in bioinformatics, 7(3):243–255, 2006.
  * Chen et al. [2018] Jie Chen, Tengfei Ma, and Cao Xiao.  Fastgcn: Fast learning with graph convolutional networks via importance sampling.  In Proc. ICLR, 2018.
  * Chen et al. [2020a] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li.  Simple and deep graph convolutional networks.  In Proc. ICML, pages 1725–1735, 2020.
  * Chen et al. [2020b] Zhengdao Chen, Lisha Li, and Joan Bruna.  Supervised community detection with line graph neural networks.  In Proc. ICLR, 2020.
  * Cong et al. [2021] Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi.  On provable benefits of depth in training graph convolutional networks.  In Proc. NeurIPS, pages 9936–9949, 2021.
  * Dai et al. [2016] Hanjun Dai, Bo Dai, and Le Song.  Discriminative embeddings of latent variable models for structured data.  In Proc. ICML, page 2702–2711, 2016.
  * Defferrard et al. [2016] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.  Convolutional neural networks on graphs with fast localized spectral filtering.  In Proc. NeurIPS, 2016.
  * Du et al. [2019] Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu.  Graph neural tangent kernel: Fusing graph neural networks with graph kernels.  In Proc. NeurIPS, 2019.
  * Duvenaud et al. [2015] David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams.  Convolutional networks on graphs for learning molecular fingerprints.  In Proc. NeurIPS, 2015.
  * Esser et al. [2021] Pascal Esser, Leena Chennuru Vankadara, and Debarghya Ghoshdastidar.  Learning theory can (sometimes) explain generalisation in graph neural networks.  In Proc. NeurIPS, pages 27043–27056, 2021.
  * Feng et al. [2020] Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang.  Graph random neural networks for semi-supervised learning on graphs.  In Proc. NeurIPS, pages 22092–22103, 2020.
  * Feng et al. [2022] Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang.  How powerful are k-hop message passing graph neural networks.  In Proc. NeurIPS, 2022.
  * Fout et al. [2017] Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur.  Protein interface prediction using graph convolutional networks.  In Proc. NeurIPS, 2017.
  * Gao and Ji [2019] Hongyang Gao and Shuiwang Ji.  Graph u-nets.  In Proc. ICML, pages 2083–2092, 2019.
  * Gasteiger et al. [2018] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann.  Predict then propagate: Graph neural networks meet personalized pagerank.  In Proc. ICLR, 2018.
  * Grover et al. [2019] Aditya Grover, Aaron Zweig, and Stefano Ermon.  Graphite: Iterative generative modeling of graphs.  In Proc. ICML, pages 2434–2444, 2019.
  * Hamilton et al. [2017] William L. Hamilton, Rex Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In Proc. NeurIPS, 2017.
  * Han et al. [2022] Kai Han, Yunhe Wang, Jianyuan Guo, Yehui Tang, and Enhua Wu.  Vision gnn: An image is worth graph of nodes.  In Proc. NeurIPS, 2022.
  * Hasanzadeh et al. [2020] Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki, Mingyuan Zhou, Nick Duffield, Krishna Narayanan, and Xiaoning Qian.  Bayesian graph neural networks with adaptive connection sampling.  In Proc. ICML, pages 4094–4104, 2020.
  * He et al. [2020] Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang.  Lightgcn: Simplifying and powering graph convolution network for recommendation.  In Proc. SIGIR, pages 639–648, 2020.
  * Kitaev et al. [2019] Nikita Kitaev, Łukasz Kaiser, and Anselm Levskaya.  Reformer: The efficient transformer.  In Proc. ICLR, 2019.
  * Levie et al. [2019] Ron Levie, Federico Monti, Xavier Bresson, and Michael M. Bronstein.  Cayleynets: Graph convolutional neural networks with complex rational spectral filters.  IEEE Trans. Signal Processing, pages 97–109, 2019.
  * Li and Goldwasser [2019] Chang Li and Dan Goldwasser.  Encoding social information with graph convolutional networks forPolitical perspective detection in news media.  In Proc. ACL, pages 2594–2604, 2019.
  * Li et al. [2018] Qimai Li, Zhichao Han, and Xiao-Ming Wu.  Deeper insights into graph convolutional networks for semi-supervised learning.  In Proc. AAAI, pages 3538–3545, 2018.
  * Li et al. [2019] Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem.  Deepgcns: Can gcns go as deep as cnns?  In Proc. CVPR, pages 9267–9276, 2019.
  * Liu et al. [2020] Meng Liu, Hongyang Gao, and Shuiwang Ji.  Towards deeper graph neural networks.  In Proc. 26th ACM SIGKDD, pages 338–348, 2020.
  * Liu et al. [2021] Fanzhen Liu, Shan Xue, Jia Wu, Chuan Zhou, Wenbin Hu, Cecile Paris, Surya Nepal, Jian Yang, and Philip S Yu.  Deep learning for community detection: progress, challenges and opportunities.  In Proc. IJCAI, pages 4981–4987, 2021.
  * Ma et al. [2021] Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah.  A unified view on graph neural networks as graph signal denoising.  In Proc. CIKM, pages 1202–1211, 2021.
  * Okuda et al. [2021] Makoto Okuda, Shin’ichi Satoh, Yoichi Sato, and Yutaka Kidawara.  Community detection using restrained random-walk similarity.  IEEE Trans. Pattern Analysis and Machine Intelligence, 43(1):89–103, 2021.
  * Qiu et al. [2019] Lin Qiu, Yunxuan Xiao, Yanru Qu, Hao Zhou, Lei Li, Weinan Zhang, and Yong Yu.  Dynamically fused graph network for multi-hop reasoning.  In Proc. ACL, pages 6140–6150, 2019.
  * Rong et al. [2020] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang.  Dropedge: Towards deep graph convolutional networks on node classification.  In Proc. ICLR, 2020.
  * Smola et al. [2007] Alex Smola, Arthur Gretton, Le Song, and Bernhard Schölkopf.  A hilbert space embedding for distributions.  In Proc. ALT, 2007.
  * Veličković et al. [2017] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph Attention Networks.  In Proc. ICLR, pages 1–12, 2017.
  * Verma et al. [2021] Vikas Verma, Meng Qu, Kenji Kawaguchi, Alex Lamb, Yoshua Bengio, Juho Kannala, and Jian Tang.  Graphmix: Improved training of gnns for semi-supervised learning.  In Proc. AAAI, pages 10024–10032, 2021.
  * Wainwright et al. [2008] Martin J Wainwright, Michael I Jordan, et al.  Graphical models, exponential families, and variational inference.  Foundations and Trends® in Mach. Learning, pages 1–305, 2008.
  * Weisfeiler and Leman [1968] Boris Weisfeiler and Andrei Leman.  The reduction of a graph to canonical form and the algebra which appears therein.  NTI, Series, pages 12–16, 1968.
  * Welling and Kipf [2016] Max Welling and Thomas N Kipf.  Semi-supervised classification with graph convolutional networks.  In Proc. ICLR, 2016.
  * Wu et al. [2019] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger.  Simplifying graph convolutional networks.  In Proc. ICML, pages 6861–6871, 2019.
  * Xu et al. [2018] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka.  Representation learning on graphs with jumping knowledge networks.  In Proc. ICML, pages 5453–5462, 2018.
  * Xu et al. [2019a] B. Xu, H. Shen, Q. Cao, Y. Qiu, and X. Cheng.  Graph wavelet neural network.  In Proc. ICLR, 2019.
  * Xu et al. [2019b] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  In Proc. ICLR, pages 1–17, 2019.
  * Yan et al. [2018] Sijie Yan, Yuanjun Xiong, and Dahua Lin.  Spatial temporal graph convolutional networks for skeleton-based action recognition.  In Proc. AAAI, 2018.
  * Yao et al. [2019] Liang Yao, Chengsheng Mao, and Yuan Luo.  Graph convolutional networks for text classification.  In Proc. AAAI, pages 7370–7377, 2019.
  * Ying et al. [2018] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec.  Graph convolutional neural networks for web-scale recommender systems.  In Proc. 24th ACM SIGKDD, pages 974–983, 2018.