summaries: The paper proposes the inclusive neural random field model. Compared the existing work, the model is different because of the use of the inclusive-divergence minimization for the generative model and the use of stochastic gradient Langevin dynamics (SGLD) and stochastic gradient Hamiltonian Monte Carlo  (SGHMC) for sampling. Experimental results are reported for unsupervised, semi-supervised, and supervised learning problems on both synthetic and real-world datasets. Specific comments follow:

summaries: This paper addresses an important problem of learning the random field using neural networks by using a inclusive auxiliary generator. Comparing to existing state-of-the-art methods for learning neural random fields, this paper used a the inclusive-divergence (KL divergence of the density approximate and the auxiliary generator) which avoids the intractable entropy term. SGLD/SGHMC are used to revise samples drawn from the auxiliary generator and these two sampling methods are examined theoretically.

abstractText: Neural random fields (NRFs), which are defined by using neural networks to implement potential functions in undirected models, provide an interesting family of model spaces for machine learning. In this paper we develop a new approach to learning NRFs with inclusive-divergence minimized auxiliary generator the inclusive-NRF approach, for continuous data (e.g. images), with solid theoretical examination on exploiting gradient information in model sampling. We show that inclusive-NRFs can be flexibly used in unsupervised/supervised image generation and semi-supervised classification, and empirically to the best of our knowledge, represent the best-performed random fields in these tasks. Particularly, inclusiveNRFs achieve state-of-the-art sample generation quality on CIFAR-10 in both unsupervised and supervised settings. Semi-supervised inclusive-NRFs show strong classification results on par with state-of-the-art generative model based semi-supervised learning methods, and simultaneously achieve superior generation, on the widely benchmarked datasets MNIST, SVHN and CIFAR-10.

authors:
Jonas Adler
Sebastian Lunz

title: Banach wasserstein gan

venue: arXiv preprint arXiv:1806.06621,

authors:
Martin Arjovsky
Soumith Chintala
Léon Bottou

title: Wasserstein generative adversarial networks

venue: In ICML,

authors:
Jörg Bornschein
Yoshua Bengio

title: Reweighted wake-sleep

authors:
Tianqi Chen
Emily Fox
Carlos Guestrin

title: Stochastic gradient hamiltonian monte carlo

authors:
Jifeng Dai
Yang Lu
Ying-Nian Wu

title: Generative modeling of convolutional neural networks

venue: arXiv preprint arXiv:1412.6296,

authors:
Zihang Dai
Amjad Almahairi
Philip Bachman
Eduard Hovy
Aaron Courville

title: Calibrating energy-based generative adversarial networks

venue: In ICLR,

authors:
Zihang Dai
Zhilin Yang
Fan Yang
William W Cohen
Ruslan R Salakhutdinov

title: Good semi-supervised learning that requires a bad gan

venue: In NIPS,

authors:
Vincent Dumoulin
Ishmael Belghazi
Ben Poole
Olivier Mastropietro
Alex Lamb
Martin Arjovsky
Aaron Courville

title: Adversarially learned inference

authors:
Zhe Gan
Liqun Chen
Weiyao Wang
Yuchen Pu
Yizhe Zhang
Hao Liu
Chunyuan Li
Lawrence Carin

title: Triangle generative adversarial networks

authors:
Ian Goodfellow
Jean Pouget-Abadie
Mehdi Mirza
Bing Xu
David Warde-Farley
Sherjil Ozair
Aaron Courville
Yoshua Bengio

title: Generative adversarial nets

authors:
Ishaan Gulrajani
Faruk Ahmed
Martín Arjovsky
Vincent Dumoulin
Aaron C. Courville

title: Improved training of wasserstein gans

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

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

authors:
Geoffrey E Hinton
Peter Dayan
Brendan J Frey
Radford M Neal

title: The "wake-sleep" algorithm for unsupervised neural networks

authors:
Xun Huang
Yixuan Li
Omid Poursaeed
John Hopcroft
Serge Belongie

title: Stacked generative adversarial networks

authors:
Taesup Kim
Yoshua Bengio

title: Deep directed generative models with energy-based probability estimation

venue: In ICLR Workshop,

authors:
Diederik P Kingma
Max Welling

title: Auto-encoding variational bayes

authors:
Diederik P. Kingma
Danilo Jimenez Rezende
Shakir Mohamed
Max Welling

title: Semi-supervised learning with deep generative models

authors:
Daphne Koller
Nir Friedman

title: Probabilistic graphical models: principles and techniques

venue: MIT press,

title: Learning multiple layers of features from tiny images

venue: Technical report, University of Toronto,

authors:
Volodymyr Kuleshov
Stefano Ermon

title: Neural variational inference and learning in undirected graphical models

authors:
Samuli Laine
Timo Aila

title: Temporal ensembling for semi-supervised learning

authors:
Hugo Larochelle
Michael I Mandel
Razvan Pascanu
Yoshua Bengio

title: Learning algorithms for the classification restricted boltzmann machine

venue: Journal of Machine Learning Research,

authors:
Yann LeCun
Léon Bottou
Yoshua Bengio
Patrick Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

authors:
Yann LeCun
Sumit Chopra
Raia Hadsell
M Ranzato
F Huang

title: A tutorial on energy-based learning

venue: Predicting structured data,

authors:
Daniel Levy
Matthew D. Hoffman
Jascha Sohl-Dickstein

title: Generalizing hamiltonian monte carlo with neural networks

authors:
Chongxuan Li
Taufik Xu
Jun Zhu
Bo Zhang

title: Triple generative adversarial nets

authors:
Xuanqing Liu
Cho-Jui Hsieh

title: From adversarial training to generative adversarial networks

venue: arXiv preprint arXiv:1807.10454,

authors:
Lars Maaloe
Casper Kaae Sonderby
Soren Kaae Sonderby
Ole Winther

title: Auxiliary deep generative models

authors:
Takeru Miyato
Shin-ichi Maeda
Masanori Koyama
Shin Ishii

title: Virtual adversarial training: a regularization method for supervised and semi-supervised learning

venue: arXiv preprint arXiv:1704.03976,

authors:
Takeru Miyato
Toshiki Kataoka
Masanori Koyama
Yuichi Yoshida

title: Spectral normalization for generative adversarial networks

title: Mcmc using hamiltonian dynamics

venue: Handbook of Markov Chain Monte Carlo,

authors:
Yuval Netzer
Tao Wang
Adam Coates
Alessandro Bissacco
Bo Wu
Andrew Y Ng

title: Reading digits in natural images with unsupervised feature learning

venue: In NIPS workshop on deep learning and unsupervised feature learning,

authors:
Jiquan Ngiam
Zhenghao Chen
Wei Koh Pang
Andrew Y. Ng

title: Learning deep energy models

authors:
Alec Radford
Luke Metz
Soumith Chintala

title: Unsupervised representation learning with deep convolutional generative adversarial networks

venue: arXiv preprint arXiv:1511.06434,

authors:
Antti Rasmus
Harri Valpola
Mikko Honkala
Mathias Berglund
Tapani Raiko

title: Semi-supervised learning with ladder networks

authors:
R. Salakhutdinov
G. Hinton

title: Deep boltzmann machines

authors:
Tim Salimans
Ian Goodfellow
Wojciech Zaremba
Vicki Cheung
Alec Radford
Xi Chen

title: Improved techniques for training gans

title: Unsupervised and semi-supervised learning with categorical generative adversarial networks

authors:
Antti Tarvainen
Harri Valpola

title: Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results

authors:
Yee Whye Teh
Alexandre H. Thiery
Sebastian Vollmer

title: Consistency and fluctuations for stochastic gradient langevin dynamics

authors:
Bin Wang
Zhijian Ou

title: Language modeling with neural trans-dimensional random fields

venue: In IEEE Workshop on Automatic Speech Recognition and Understanding (ASRU),

authors:
David Warde-Farley
Yoshua Bengio

title: Improving generative adversarial networks with denoising feature matching

authors:
Xiang Wei
Zixia Liu
Liqiang Wang
Boqing Gong

title: Improving the improved training of wasserstein GANs

authors:
Max Welling
Yee Whye Teh

title: Bayesian learning via stochastic gradient langevin dynamics

authors:
Jianwen Xie
Yang Lu
Song-Chun Zhu
Ying Nian Wu

title: Cooperative training of descriptor and generator networks

venue: arXiv preprint arXiv:1609.09408

title: Parametric inference for imperfectly observed gibbsian fields

venue: Probability Theory and Related Fields,

authors:
Junbo Zhao
Michael Mathieu
Yann LeCun

title: Energy-based generative adversarial networks

title: Semi-supervised learning literature survey

venue: Technical report, University of Wisconsin-Madison,

title: Confidence loss. Similar to Springenberg

title: 2017b)) and hyperparameters for semi-supervised inclusive

heading: 1 INTRODUCTION

text:
One of the core research problems in machine learning is learning with probabilistic models, which can be broadly classified into two classes - directed and undirected1 (Koller & Friedman, 2009). Significant progress has been made recently on learning with deep generative models (DGMs), which generally refer to models with multiple layers of stochastic or deterministic variables. There have emerged a bundle of deep directed generative models, such as variational AutoEncoders (VAEs) (Kingma & Welling, 2014), generative adversarial networks (GANs) (Goodfellow et al., 2014) and so on. In contrast, undirected generative models (also known as random fields (Koller & Friedman, 2009), energy-based models (LeCun et al., 2006)) received less attention with slow progress. This is presumably because fitting undirected models is more challenging than fitting directed models. In general, calculating the log-likelihood and its gradient is analytically intractable, because it involves the expectation with respect to (w.r.t.) the model distribution.
In this paper, we aims to advance the learning of neural random fields (RFs) which use neural networks with multiple (deterministic) layers to define the potential function2 uθ(x) over observation x with parameter θ. The probability distribution pθ(x) ∝ exp(uθ(x)) is then defined by normalizing the exponentiated potential function. This type of RFs has been studied several times in different contexts, once called deep energy models (DEMs) (Ngiam et al., 2012; Kim & Bengio, 2016), descriptive models (Xie et al., 2016), generative ConvNet (Dai et al., 2014), neural random field language models (Wang & Ou, 2017). For convenience, we refer to such models as neural random fields (NRFs) in general.
An important method of maximum likelihood (ML) learning of random fields is called stochastic maximum likelihood (SML) (Younes, 1989), which approximates the model expectations by Monte Carlo sampling for calculating the gradient. A recent progress in learning NRFs as studied in Kim & Bengio (2016); Xie et al. (2016); Wang & Ou (2017); Kuleshov & Ermon (2017) is to
1An easy way to tell an undirected model from a directed model is that an undirected model involves the normalizing constant (also called the partition function in physics), while the directed model is self-normalized.
2Note that compared to modeling with multiple deterministic layers, modeling with multiple stochastic layers, e.g. deep Boltzmann machines (DBMs) (Salakhutdinov & Hinton, 2009), presents much greater challenge for model learning and thus yields inferior performance. This is observed in both directed and undirected models.
pair the target random field pθ with an auxiliary directed generative model (often called generator) qφ(x) parameterized by φ, which approximates sampling from the target random field. Learning is performed by maximizing the log-likelihood of training data under pθ or some bound of the log-likelihood, and simultaneously minimizing some divergence between the target random field pθ and the auxiliary generator qφ. Different learning algorithms differ in the objective functions used in the joint training of pθ and qφ, and thus have different computational and statistical properties (partly illustrated in Figure 1). For example, minimizing the exclusive-divergence KL[qφ||pθ] ,∫ qφ log (qφ/pθ) w.r.t. φ, as employed in Kim & Bengio (2016), involves the intractable entropy term and tends to enforce the generator to seek modes, yielding missing modes. There are also other factors, e.g. modeling discrete or continuous data, different choices of the target RF and the generator, which lead to different algorithms. We leave detailed comparison and connection of our approach with existing studies to section 3 (related work).
In this paper, we propose to use inclusive-divergence minimized auxiliary generators (section 2.1). And particularly for continuous data (e.g. images), we propose to use SGLD (stochastic gradient Langevin dynamics (Welling & Teh, 2011)) and SGHMC (stochastic gradient Hamiltonian Monte Carlo (Chen et al., 2014)) to exploit gradient information in model sampling with solid theoretical examination (section 2.2). The new approach, abbreviated as the inclusive-NRF approach, offers some advantages over previous methods. First, minimizing the inclusive-divergence KL[pθ||qφ] ,∫ pθ log (pθ/qφ) w.r.t. φ avoids the annoying entropy term and tends to drive the generator to cover modes of the target density pθ. The SGLD/SGHMC sampling further pushes the samples towards the modes of pθ. Presumably, this helps to produce Markov chains that mix fast between modes and facilitate model learning. Second, the new approach enables us to flexibly use NRFs in unsupervised/supervised image generation and semi-supervised classification (section 2.3), and empirically to the best of our knowledge, represents the best-performed random fields in these tasks.
The main contributions of this paper can be summarized as follows:
• We develop the inclusive-NRF approach, which learns NRFs with inclusive auxiliary generators and particularly for continuous data, exploits gradient information in model sampling with solid theoretical examination. • Inclusive-NRFs achieve state-of-the-art sample generation quality, measured by both Incep-
tion Score (IS) and Frechet Inception Distance (FID). On CIFAR-10, we obtain unsupervised IS 8.28 (FID 20.9) and supervised IS 9.06 (FID 18.1), both using unconditional generation. • Semi-supervised inclusive-NRFs show strong classification results on par with state-of-
the-art DGM-based semi-supervised learning (SSL) methods, and simultaneously achieve superior generation, on the widely benchmarked datasets - MNIST, SVHN and CIFAR-10.

heading: 2 THE INCLUSIVE-NRF APPROACH

text:
Consider a random field for modeling observation x with parameter θ:
pθ(x) = 1
Z(θ) exp [uθ(x)] (1) where Z(θ) = ∫
exp(uθ(x))dx is the normalizing constant, uθ(x) is the potential function3 which assigns a scalar value to each configuration of random variable x. The general idea of neural random fields (NRFs) is to implement uθ(x) : Rdx → R, by a neural network, taking the multi-dimensional x ∈ Rdx as input and outputting the scalar uθ(x) ∈ R. In this manner, we can take advantage of the representation power of neural networks for RF modeling. It is usually intractable to maximize the data log-likelihood logpθ(x̃) for observed x̃, since the gradient involves expectation w.r.t. the model distribution, as shown below:
∇θ log pθ(x̃) = ∇θuθ(x̃)− Epθ(x) [∇θuθ(x)] (2)

heading: 2.1 INTRODUCING INCLUSIVE-DIVERGENCE MINIMIZED AUXILIARY GENERATORS

text:
In this paper, we further develop NRF learning with auxiliary generators. We are mainly concerned with modeling fixed-dimensional continuous observations x ∈ Rdx (e.g. images), and choose a
3Negating the potential function defines the energy function.
Algorithm 1 Learning NRFs with inclusive auxiliary generators repeat
Sampling: Draw a minibatchM = { (x̃i, xi, hi), i = 1, · · · |M| }
from p̃(x̃)pθ(x)qφ(h|x) (see Algorithm 2); Updating: Update θ by ascending: 1|M| ∑ (x̃,x,h)∼M [∇θuθ(x̃)−∇θuθ(x)];
Update φ by ascending: 1|M| ∑
(x̃,x,h)∼M∇φ log qφ(x, h); until convergence
directed generative model, qφ(x, h) , q(h)qφ(x|h), for the auxiliary generator, which specifically is defined as follows4:
h ∼ N (0, Ih), x = gφ(h) + , ∼ N (0, σ2I ),
(3)
where gφ(h) : Rdh → Rdx is implemented as a neural network with parameter φ, which maps the latent code h to the observation space. Ih and I denote the identity matrices, with dimensionality implied by h and respectively. Drawing samples from the generator qφ(x, h) is simple as it is just ancestral sampling from a 2-variable directed graphical model.
Suppose that data D = {x̃1, · · · , x̃n}, consisting of n observations, are drawn from the true but unknown data distribution p0(·). p̃(x̃) , 1n ∑n k=1 δ(x̃ − x̃k) denotes the empirical data distribution. Then we formulate the maximum likelihood learning of pθ(x) with the inclusive-divergence minimized generator qφ(x) as optimizing5 min θ KL [p̃(x̃)||pθ(x̃)]
min φ KL [pθ(x)||qφ(x)]
(4)
The first line of Eq. (4) is equivalent to maximum likelihood training of the target RF pθ under the empirical data p̃, which requires sampling from pθ. Simultaneously, the second line optimizes the generator qφ to be close to pθ so that qφ becomes a good proposal for sampling from pθ. It can be easily seen that the gradients w.r.t. θ and φ (to be ascended) are defined as follows:{
∇θ = Ep̃(x̃) [∇θ log pθ(x̃)] = Ep̃(x̃) [∇θuθ(x̃)]− Epθ(x) [∇θuθ(x)] , ∇φ = Epθ(x) [∇φ log qφ(x)] = Epθ(x)qφ(h|x) [∇φ log qφ(x, h)] .
(5)
Both lines of Eq. (5) hold, as proved in Proposition 1 in the Supplement. In practice, we calculate noisy gradient estimators, and apply minibatch based stochastic gradient descent (SGD) to solve the optimization problem Eq. (4), as shown in Algorithm 1.

heading: 2.2 APPLYING SGLD/SGHMC FOR MODEL SAMPLING

text:
In Algorithm 1, we need to draw samples from pθ(x)qφ(h|x) given current θ and φ. For continuous observations, SGLD (stochastic gradient Langevin dynamics) (Welling & Teh, 2011) and SGHMC (Stochastic Gradient Hamiltonian Monte Carlo) (Chen et al., 2014) sampling provide mechanisms for exploiting (stochastic) gradients of the target density pθ(x)qφ(h|x), enabling efficient exploration of the state space. We take the theoretical results about SGLD from Teh et al. (2016) and SGHMC from Chen et al. (2014), which are briefly summarized in Theorem 1 in the Supplement, and apply them in the sampling step in Algorithm 1. Denoting the target density as p(z;λ) with given λ, Theorem 1 shows that SGLD/SGHMC, by utilizing ∂∂z log p(z;λ), yields a non-homogeneous Markov chain{ z(l), l ≥ 1 } , which converges to the equilibrium distribution p(z;λ).
By letting z , (x, h), p(z;λ) , pθ(x)qφ(h|x), λ , (θ, φ)T in Theorem 1, we can perform the sampling step in Algorithm 1 by running |M| parallel chains, each chain being executed as shown
4Note that during training, σ2 is absorbed into the learning rates and does not need to be estimated. 5Such optimization using two objectives is employed in a number of familiar learning methods, such as GAN
with logD trick (Goodfellow et al., 2014), wake-sleep algorithm (Hinton et al., 1995).
Algorithm 2 Sampling from pθ(x)qφ(h|x) 1. Do ancestral sampling by the generator, namely first drawing h′ ∼ p(h′), and then drawing x′ ∼ qφ(x′|h′); 2. Starting from (x′, h′) = z(0), run finite steps of SGLD/SGHMC (l = 1, · · · , L) to obtain (x, h) = z(L), which we call sample revision, according to Eq. (11)/(12). Return (x, h).
in Algorithm 2. In sample revision, the calculation of the gradient w.r.t. h, ∂∂h log p(z;λ) = ∂ ∂h log qφ(h|x) = ∂ ∂h log qφ(h, x), is straightforward. For the gradient w.r.t. x, we have
∂
∂x log p(z;λ) =
∂
∂x log pθ(x) +
∂
∂x log qφ(h, x)−
∂
∂x log qφ(x) ≈
∂
∂x log pθ(x). (6)
The reason is that ∂∂x log qφ(x) can be approximated by an unbiased estimate, as proved in Proposition 2 in the Supplement:
∂
∂x log qφ(x) ≈
∂
∂x log qφ(h, x).
Therefore, we can use ∂∂x log pθ(x) 6 as an unbiased estimate of the gradient ∂∂x log p(z;λ), and we can apply Theorem 1 in the Supplement with tractable gradients w.r.t. both x and h.
Remarks. Intuitively, the generator gives a proposal (x′, h′), and then the system follows the gradients of pθ(x) and qφ(h, x) (w.r.t. x and h respectively) to revise (x′, h′) to (x, h). The gradient terms pull samples moving to low energy region of the random field and adjust the latent code of the generator, while the noise term brings randomness. In this manner, we obtain Markov chain samples from pθ(x)qφ(h|x). Note that finite steps in sample revision will produce biased estimates of the gradients ∇θ and∇φ in Eq. (5). We did not find this to pose problems to the SGD optimization in practice, as similarly found in Bornschein & Bengio (2015) and Kuleshov & Ermon (2017), which work with biased gradient estimators.

heading: 2.3 SEMI-SUPERVISED LEARNING WITH INCLUSIVE NRFS

text:
In the following, we apply our inclusive-NRF approach in the SSL setting to show its flexibility. Note that different models are needed in unsupervised and semi-supervised learning, because SSL needs to additionally consider labels apart from observations.
Model definition. In semi-supervised tasks, we consider the following RF for joint modeling of observation x ∈ Rdx and class label y ∈ {1, · · · ,K}:
pθ(x, y) = 1
Z(θ) exp [uθ(x, y)] (7)
which is different from Eq.1 for unsupervised learning without labels. To implement the potential function uθ(x, y), we consider a neural network Φθ(x) : Rdx → RK , with x as the input and the output size being equal to the number of class labels, K. Then we define uθ(x, y) = onehot(y)TΦθ(x), where onehot(y) represents the one-hot encoding vector for the label y. In this manner, the conditional density pθ(y|x) is the classifier, defined as follows:
pθ(y|x) = pθ(x, y)
pθ(x) = exp [uθ(x, y)]∑ y exp [uθ(x, y)]
(8)
which acts like multi-class logistic regression using K logits calculated from x by the neural network Φθ(x). And we do not need to calculate Z(θ) for classification. The auxiliary generator is implemented the same as in Eq. 3, i.e. an unconditional generator.
With the definition the joint density in Eq. 7, it can be shown that, with abuse of notation, the marginal density pθ(x) = 1Z(θ) exp [uθ(x)] where uθ(x) , log ∑ y exp [uθ(x, y)].
6Note that ∂ ∂x log pθ(x) = ∂ ∂x uθ(x) does not require the calculation of the normalizing constant.
Model learning. Suppose that among the data D = {x̃1, · · · , x̃n}, only a small subset of the observations, for example the first m observations, have class labels, m n. Denote these labeled data as L = {(x̃1, ỹ1), · · · , (x̃m, ỹm)}. Then we can formulate the semi-supervised learning as jointly optimizing  min θ KL [p̃(x̃)||pθ(x̃)]− αd ∑ (x̃,ỹ)∼L logpθ(ỹ|x̃)
min φ KL [pθ(x)||qφ(x)]
(9)
which are defined by hybrids of generative and discriminative criteria, similar to Zhu (2006); Larochelle et al. (2012); Kingma et al. (2014). The hyper-parameter αd controls the relative weight between generative and discriminative criteria. Similar to deriving Eq. (5), it can be easily seen that the gradients w.r.t. θ and φ (to be ascended) are defined as follows: ∇semiθ =Ep̃(x̃) [∇θlogpθ(x̃)] + αd ∑ (x̃,ỹ)∼L ∇θlogpθ(ỹ|x̃) =Ep̃(x̃) [∇θuθ(x̃)]− Epθ(x) [∇θuθ(x)] + αd ∑ (x̃,ỹ)∼L ∇θlogpθ(ỹ|x̃)
∇semiφ =Epθ(x) [∇φlogqφ(x)] = Epθ(x)qφ(h|x) [∇φlogqφ(x, h)]
(10)
In practice, we calculate noisy gradient estimators, and apply minibatch based stochastic gradient descent (SGD) to solve the optimization problem Eq. (9), as shown in Algorithm 3 in the Supplement. Apart from the basic losses as shown in Eq. (9), there are some regularization losses that are found to be helpful to guide SSL learning and are presented in the Supplement. To conclude, we show that the inclusive-NRF can be easily applied to SSL. To the best of our knowledge, there are no priori studies in applying random fields to SSL. The semi-supervised inclusive-NRF model defined above is novel itself for SSL.

heading: 3 RELATED WORK

text:
Comparison and connection of our inclusive-NRF approach with existing studies are provided in the following from three perspectives.
Learning NRFs with auxiliary generators. These studies are most relevant to this work, which aims to learn NRFs. The classic method for learning RFs is the SML method (Younes, 1989), which works with the single target model pθ. Compared to learning traditional RFs which mainly use linear potential functions, learning NRFs which use NN based nonlinear potential functions, is more challenging. A recent progress in learning NRFs as studied in Kim & Bengio (2016); Xie et al. (2016); Wang & Ou (2017); Kuleshov & Ermon (2017) is to jointly train the target random field pθ(x) and an auxiliary generator qφ(x). Different studies differ in the objective functions used in the joint training, and thus have different computational and statistical properties.
• It is shown in Proposition 3 in the Supplement that learning in Kim & Bengio (2016) minimizes the exclusive-divergence KL[qφ||pθ] w.r.t. φ, which involves the intractable entropy term and tends to enforce the generator to seek modes, yielding missing modes. We refer to this approach as exclusive-NRF. • Learning in Wang & Ou (2017) and in this paper minimizes the inclusive-divergence KL[pθ||qφ] w.r.t. φ. But noticeably, this paper presents our innovation in development of NRFs for continuous data, which is fundamentally different from Wang & Ou (2017) for discrete data. The target NRF model, the generator and the sampler are all different. Wang & Ou (2017) mainly studies random field language models, using LSTM generators (autoregressive with no latent variables) and employing Metropolis independence sampler (MIS) - applicable for discrete data (natural sentences). In this paper, we mainly develop random field models for continuous data (images), using latent-variable generators and utilizing SGLD/SGHMC (with solid theoretical examination) to exploit gradient information in the continuous space. • In Xie et al. (2016), motivated by interweaving maximum likelihood training of the ran-
dom field pθ and the latent-variable generator qφ, a joint training method is introduced.
Operationally, in learning θ and φ, this method also uses Langevin sampling to generate samples. Two Langevin sampling steps are intuitively interleaved according to ∂∂x log pθ(x) and ∂∂h log qφ(h, x) separately. This is different from our sampling step, which moves (h, x) jointly, as theoretically justified in section 2.2. Let r(h, x) denote the distribution obtained by running the interleaved Langevin transitions starting from (h, x) ∼ qφ(h, x). Interpretation presented in Xie et al. (2016) relates their method to the following joint optimization problem:  min θ {KL [p̃(x̃)||pθ(x̃)]−KL [r(h, x)||pθ(x)]}
min φ KL [r(h, x)||qφ(h, x)]
which is also different from ours as shown in Eq. (4). Thus, learning in Xie et al. (2016) does not aim to minimize the inclusive-divergence KL[pθ||qφ] w.r.t. φ. • Learning in Kuleshov & Ermon (2017) minimizes the χ2-divergence χ2[qφ||pθ] ,∫ (pθ−qφ)2
qφ w.r.t. φ, which also tends to drive the generator to cover modes. But this
approach is severely limited by the high variance of the gradient estimator w.r.t. φ, and is only tested on the simpler MNIST and Omniglot.
Additionally, different NRF studies also differ in models used in the joint training. For example, the target NRF used in this work is different from those in previous studies Kim & Bengio (2016); Wang & Ou (2017); Xie et al. (2016). The differences are: Kim & Bengio (2016) includes linear and squared terms in uθ(x), Wang & Ou (2017) defines over sequences, and Xie et al. (2016) defines in the form of exponential tilting of a reference distribution (Gaussian white noise). There exist different choices for the generator, such as GAN models in Kim & Bengio (2016), LSTMs in Wang & Ou (2017), or latent-variable models in both Xie et al. (2016) and this work. All are easy to do sampling.
Moreover, all the previous NRF studies examine unsupervised learning, and none shows application or extension of their methods or models for semi-supervised learning.
Monte Carlo sampling. One step in our inclusive-NRF approach is to apply SGLD/SGHMC to draw samples from the target density pθ, starting from the proposal sample from the generator. Theoretically, improvements in NRF sampling methods could be potentially integrated into NRF learning algorithms. For example, it is recently studied in Levy et al. (2018) to learn MCMC transition kernels, also parameterized by neural networks, to improve the HMC sampling from the given target distribution. Integration into learning NRFs is interesting but outside the scope of this paper.
Comparison and connection with GANs. On the one hand, there are some efforts that aim to address the inability of GANs to provide sensible energy estimates for samples. The energy-based GANs (Zhao et al., 2017) proposes to view the discriminator as an energy function by designing an auto-encoder discriminator. The recent work in Dai et al. (2017a) connects Zhao et al. (2017) and Kim & Bengio (2016), and show another two approximations for the entropy term. However, it is known that as the generator converges to the true data distribution, the GAN discriminator converges to a degenerate uniform solution. This basically afflicts the GAN discriminator to provide density information, though there are some modifications. In contrast, our inclusive-NRFs, unlike GANs, naturally provide (unnormalized) density estimate. Moreover, none of the above energy-related GAN studies examine their methods or models for SSL, except in EBGAN which performs moderately.
On the other hand, there are interesting connections between inclusive-NRFs and GANs, as elaborated in section 11 in the Supplement. When interpreting the potential function uθ(x) as the critic in Wasserstein GANs, inclusive-NRFs seem to be similar to Wasserstein GANs. A difference is that in optimizing θ in inclusive-NRFs, the generated samples are further revised by taking finite-stepgradient of uθ(x) w.r.t. x. However, the critic in Wasserstein GANs can hardly be interpreted as an unnormalized log-density. Thus strictly speaking, inclusive-NRFs are not GAN-like.

heading: 4 EXPERIMENTS

text: We conduct a series of experiments to evaluate the performances of our approach (inclusive-NRFs) and various existing methods on synthetic and real-world datasets for both unsupervised and semisupervised learning tasks, with both visual and numerical evaluation. We refer to the Supplement for experimental details and additional results.

heading: 4.1 GMM SYNTHETIC EXPERIMENT

text:
The synthetic data consist of 1,600 training examples generated from a 2D Gaussian mixture model (GMM) with 32 equally-weighted, low-variance (σ = 0.1) Gaussian components, uniformly laid out on four concentric circles as in Figure 1(a). The data distribution exhibits many modes separated by large low-probability regions, which makes it suitable to examine how well different learning methods can deal with multiple modes. For comparison, we experiment with GAN with logD trick (Goodfellow et al., 2014) and WGAN-GP (Gulrajani et al., 2017) for directed generative model, exclusive-NRF (Kim & Bengio, 2016) and inclusive-NRF for undirected generative model.
Figure 1 visually shows the generated samples from the trained models using different methods. Table 1 reports the “covered modes” and “realistic ratio” as numerical measures of how the multi-modal data are fitted, similarly as in Dumoulin et al. (2017). The main observations are as follows. (1) GAN suffers from mode missing, generating realistic but not diverse samples. WGAN-GP increases “covered modes” but decreases “realistic ratio”. Inclusive-NRF performs much better than both GAN and WGAN-GP in sample generation. (2) Inclusive-NRF outperforms exclusive-NRF in both sample generation and density estimation. (3) After revision, samples from inclusive-NRF become more like real samples, achieving the best in both “covered modes" and “realistic ratio” metrics.

heading: 4.2 IMAGE GENERATION ON CIFAR-10

text:
We examine both unsupervised and supervised learning over the widely used real-world dataset CIFAR-10 Krizhevsky (2009) for image generation. To evaluate generation quality quantitatively, we use inception score (IS) Salimans et al. (2016), and Frechet inception distance (FID) Heusel et al. (2017). Table 2 reports the inception score and FID for state of the art methods, for both unsupervised and supervised settings. The supervised learning of inclusive-NRF is conducted as a special case of semi-supervised learning over all labeled images (m = n), which uses unconditional generation. We use ResNet in this experiment, see section 12.2 in the Supplement for experimental details.
From the comparison results in Table 2, it can be seen that the proposed inclusive-NRF model achieves the best inception score over CIFAR-10, to the best of our knowledge, in both unsupervised and supervised settings. Some generated samples are shown in Figure 5(c)(d) for unsupervised and supervised settings respectively. We also show in the Supplement the capability of inclusive-NRFs in latent space interpolation (section 14) and conditional generation (section 15).

heading: 4.3 SEMI-SUPERVISED LEARNING RESULTS

text:
For semi-supervised learning, we consider the three widely used benchmark datasets, namely MNIST (LeCun et al., 1998), SVHN (Netzer et al., 2011), and CIFAR-10 (Krizhevsky, 2009). As in previous work, we randomly sample 100, 1,000, and 4,000 labeled samples from MNIST, SVHN, and CIFAR10 respectively during training, and use the standard data split for testing. See section 12.3 in the Supplement for experimental details. We also provide a SSL toy experiment in section 13 in the Supplement to help understanding how semi-supervised inclusive-NRF works.
It can be seen from Table 3 that semi-supervised inclusive-NRFs produce strong classification results on par with state-of-art DGM-based SSL methods. See Figure 5(a)(b) in the Supplement for generated samples. Bad-GANs achieve better classification results, but as indicated by the low inception score, their generation is much worse than semi-NRF-IAGs. In fact, among DGM-based SSL methods, inclusive-NRFs achieve the best performance in sample generation. This is in contrast to the conflict of good classification and good generation, as observed in GAN-based SSL (Salimans et al., 2016; Dai et al., 2017b). It is analyzed in Dai et al. (2017b) that good GAN-based SSL requires a bad generator7. This is embarrassing and in fact obviates the original idea of generative SSL - successful generative training, which indicates good generation, provides regularization for finding good classifiers (Zhu, 2006; Larochelle et al., 2012). In this sense, Bad-GANs could hardly be classified as a generative SSL method.
7This analysis is based on using the (K + 1)-class GAN-like discriminator objective for SSL. To the best of our knowledge, the conflict does not seem to be reported in previous generative SSL methods Zhu (2006); Larochelle et al. (2012) which use the K-class classifier like in semi-supervised inclusive-NRFs.
Finally, note that some discriminative SSL methods, as listed in the lower block in Table 3 also produce superior performances, by utilizing data augmentation and consistency regularization. However, these methods are unable to generate (realistic) samples. It can be seen that discriminative SSL methods utilize different regularization from generative SSL methods and cannot be directly compared to generative SSL methods. Their combination, as an interesting future work, could yield further performance improvement.

heading: 4.4 ABLATION STUDY

text:
We report the results of ablation study of our inclusive-NRF method on CIFAR-10 in Table 4. In this experiment, we use the standard CNN (Miyato et al., 2018) for unsupervised learning and the same networks as those used in Table 3 for semi-supervised learning. See section 12.4 in the Supplement for experimental details. We analyze the effects of different settings in model training, such as using SGLD or SGHMC and the revision step L = 1/5/10 used. For each training setting, we also compare the two manners to generate samples - whether applying sample revision or not in inference (generating samples) given a trained NRF, as previously illustrated in Figure 1 over synthetic GMM data. The main observations are as follows.
First, given a trained NRF, after revision (i.e. following the gradient of the RF’s potential uθ(x) w.r.t. x), the quality (IS) of samples is always improved, as shown by the consistent IS improvement from the second column (generation) to the third (revision). This is in accordance with the results in the GMM synthetic experiments. Moreover, noting that in revision, it is the the estimated density pθ that guides the samples towards low energy region of the random field. This demonstrates one benefit of random field modeling, which, unlike GANs, can learn density estimate about the data manifold.
Second, a row-wise reading of Table 4 reveals that with more revision steps and using SGHMC in training, the SSL classification performance is improved. Utilizing SGHMC in inclusive-NRFs to
exploit gradient information with momentum yields better performance than simple SGLD as used in Xie et al. (2016). It is also found that more revision steps in model training do not significantly improve unsupervised IS. So we can use L = 1 in unsupervised learning for generation, which can reduce the computational cost.

heading: 5 DISCUSSION AND CONCLUSION

text:
In this paper we develop the inclusive-NRF approach, which learns NRFs with inclusive auxiliary generators and particularly for continuous data, exploits gradient information in model sampling with solid theoretical examination. Extensive empirical evaluations show that inclusive-NRFs obtain state-of-the-art sample generation quality and achieve strong semi-supervised learning results on par with state-of-the-art DGMs. The superior performances presumably are attributed to the two distinctive features in inclusive-NRFs - introducing the inclusive-divergence minimized auxiliary generator and utilizing sample revision by SGLD/SGHMC. Intuitively, the revised samples from the RF will guide the training of the generator, and subsequently the generator will propose samples for the RF to sense the data manifold. This forms positive interactions between the random field and the generator, which enables successful joint training of both models.
The new approach enables us to flexibly use NRFs in unsupervised, supervised and semi-supervised settings and successfully train them in a black-box manner. Interesting future work will consider inclusive-NRFs in more challenging tasks, e.g. unsupervised and semi-supervised learning with sequential data (e.g. speech, language, video, etc.).

heading: 6 PROOF OF PROPOSITION 1

text:
Proposition 1. Both lines of Eq.(5) for gradient calculations hold.
Proof. The first line of Eq.(5) can be obtained by directly taking derivative of KL [p̃(x̃)||pθ(x̃)] w.r.t. θ, as shown below,
∂
∂θ KL [p̃(x̃)||pθ(x̃)] =
∂
∂θ
∫ p̃(x̃) log p̃(x̃)
pθ(x̃) dx̃ = −
∫ p̃(x̃) ∂
∂θ log pθ(x̃)dx̃,
and then applying the basic formula of Eq. (2).
For the second line, by direct calculation, we first have Eqφ(h|x) [∇φ log qφ(h|x)] = ∫ qφ(h|x)qφ(h|x)−1∇φqφ(h|x)dh
= ∫ ∇φqφ(h|x)dh = ∇φ ∫ qφ(h|x)dh = ∇φ1 = 0.
Then combining ∂∂φKL [pθ(x)||qφ(x)] = −Epθ(x) [∇φ log qφ(x)] and
∇φ log qφ(x) = Eqφ(h|x) [∇φ log qφ(x)] = Eqφ(h|x) [∇φ log qφ(x, h)−∇φ log qφ(h|x)] = Eqφ(h|x) [∇φ log qφ(x, h)] .
will give the second line of Eq.(5).

heading: 7 SGLD/SGHMC

text:
Theorem 1. Denote the target density as p(z;λ) with given λ. Assume that one can compute a noisy, unbiased estimate ∆(z, ξ;λ) to the gradient ∂∂z log p(z;λ), where ξ is an auxiliary random variable which contains all the randomness involved in constructing the estimate, namely E [∆(z, ξ;λ)] = ∂ ∂z log p(z;λ). Assume the stability Assumptions 4 in Teh et al. (2016) holds.
For a sequence of asymptotically vanishing time-steps {δl, l ≥ 1} (satisfying ∑∞ l=1 δl = ∞ and∑∞
l=1 δ 2 l < ∞), an i.i.d. sequence η(l), and an independent and i.i.d. sequence ξl of auxiliary
random variables, l ≥ 1, the SGLD iterates as follows, starting from z(0):
z(l) = z(l−1) + δl 2
∆(z(l−1), ξl;λ) + √ δlη (l), η(l) ∼ N (0, I), l = 1, · · · (11)
Starting from z(0) and v(0) = 0, the SGHMC iterates as follows:v(l) = βv(l−1) + δl 2 ∆(z(l−1), ξl;λ) + √ δlη (l), η(l) ∼ N (0, I)
z(l) = z(l−1) + v(l), l = 1, · · · (12)
Then in both cases, the non-homogeneous Markov chain { z(l), l ≥ 1 } converges to the equilibrium
distribution p(z;λ).

heading: 8 PROOF OF PROPOSITION 2

text:
Proposition 2. Let z , (x, h), p(z;λ) , pθ(x)qφ(h|x), λ , (θ, φ)T in Theorem 1. The initial value (x(0), h(0)) is obtained from ancestral sampling by the generator. The SGLD/SGHMC as shown in Eq.(11)/(12) iteratively generates (x(m), h(m)), m = 1, · · · . Then, ∂
∂x(m) log qφ(h (m), x(m)) is an unbiased estimate of the gradient ∂
∂x(m) log qφ(x
(m)), m = 0, 1, · · · .
Proof. Note that Langevin dynamics and Hamiltonian dynamics are reversible Neal (2011). Thus the SGLD/SGHMC transitions Eq.(11)/(12) satisfy the detailed balance condition:
π(h(m−1), x(m−1))K(h(m), x(m)|h(m−1), x(m−1)) = π(h(m), x(m))K(h(m−1), x(m−1)|h(m), x(m)),
where π(·) denotes the target density, and K(·|·) denotes the transition kernel. Also note that Eh∼qφ(h|x) [ ∂ ∂x log qφ(h, x) ] = ∂∂x log qφ(x). Thus if we show that h
(m) is indeed drawn from qφ(h (m)|x(m)) during sample revision, m = 0, 1, · · · , then the unbiasedness will hold.
Denote by π(m)(h(m), x(m)) the state-occupation density at step m. Then we need to show that π(m)(h(m)|x(m)) actually follows π(h(m)|x(m)), i.e. qφ(h(m)|x(m)), m = 0, 1, · · · .
First, it is obvious that this holds for (h(0), x(0)). Then, we proceed by mathematical induction. Suppose π(m−1)(h(m−1)|x(m−1)) = π(h(m−1)|x(m−1)). Then we have
π(m−1)(h(m−1), x(m−1))K(h(m), x(m)|h(m−1), x(m−1))
=π(m−1)(h(m−1), x(m−1)) π(h(m), x(m))
π(h(m−1), x(m−1)) K(h(m−1), x(m−1)|h(m), x(m)).
(13)
Integrating out (h(m−1), x(m−1)) from both sides of Eq.13, we obtain
π(m)(h(m), x(m)) = π(h(m), x(m)) ∑
x(m−1)
π(m−1)(x(m−1))
π(x(m−1)) K(x(m−1)|h(m), x(m))
= π(h(m), x(m)) ∑
x(m−1)
π(m−1)(x(m−1))
π(x(m−1)) K(x(m−1)|x(m))
where the second equality, i.e. K(x|h′, x′) = K(x|x′), holds because in the SGLD/SGHMC transitions Eq.(11)/(12), generating next step x only depends on current x′ and is independent of current h′. Then we have
π(m)(h(m)|x(m)) = π(h(m)|x(m)) π(x (m))
π(m)(x(m)) ∑ x(m−1) π(m−1)(x(m−1)) π(x(m−1)) K(x(m−1)|x(m))
= π(h(m)|x(m))
where the second equality holds because we have
π(x(m))
π(m)(x(m)) ∑ x(m−1) π(m−1)(x(m−1)) π(x(m−1)) K(x(m−1)|x(m))
= 1
π(m)(x(m)) ∑ x(m−1) π(m−1)(x(m−1)) K(x(m−1)|x(m))π(x(m)) π(x(m−1))
=1
Thereby, we show h(m) ∼ π(h(m)|x(m)), i.e. qφ(h(m)|x(m)). This concludes the inductive step.

heading: 9 SEMI-SUPERVISED LEARNING WITH INCLUSIVE-NRFS

text:
Apart from the basic losses, as shown in Eq.10, in applying inclusive-NRFs in SSL, there are some regularization losses that are helpful to guide the semi-supervised learning.
Algorithm 3 Semi-supervised learning of inclusive-NRFs repeat
Sampling: Draw a unsupervised minibatch U ∼ p̃(x̃)pθ(x)qφ(h|x) and a supervised minibatch S ∼ L; Updating: Update θ by ascending: 1 |U| ∑ (x̃,x,h)∼U [∇θuθ(x̃)−∇θuθ(x)] + αd 1 |S| ∑ (x̃,ỹ)∼S [∇θlogpθ(ỹ|x̃)]
− 1|U| ∑ (x̃,x,h)∼U [ αc∇θH(pθ(y|x̃)) + αp∇θ [uθ(x̃)]2 ] ;
Update φ by ascending: 1 |U| ∑
(x̃,x,h)∼U ∇φlogqφ(x, h); until convergence
Confidence loss. Similar to Springenberg (2016); Li et al. (2017), we add the minimization of the conditional entropy of pθ(y|x̃) averaged over training data to the loss w.r.t. θ (i.e. the first line in Eq.9) as follows:
Lc(θ) = Ep̃(x̃) [H(pθ(y|x̃))] = −Ep̃(x̃) [∑
y pθ(y|x̃) log pθ(y|x̃) ] In this manner, we encourage the classifier pθ(y|x) derived from the RF to make classifications confidently. In practice, we use stochastic gradients of Lc(θ) over minibatches in optimizing θ, as shown in Algorithm 3.
Potential control loss. For random fields, the data log-likelihood logpθ(x̃) is determined relatively by the potential value uθ(x̃). To avoid the potential values not to increase unreasonably, we could control the squared potential values, by minimizing:
Lp(θ) = Ep̃(x̃) [uθ(x̃)] 2
In this manner, the potential values would be attracted to zeros. In practice, we use stochastic gradients of Lp(θ) over minibatches in optimizing θ, as shown in Algorithm 3.

heading: 10 PROOF OF PROPOSITION 3

text:
Proposition 3. For the RF as defined in Eq. 1, we have the following evidence upper bound:
logpθ(x̃) = U(x̃; θ, φ)−KL(qφ(x)||pθ(x)) ≤ U(x̃; θ, φ), U(x̃; θ, φ) , uθ(x̃)− ( Eqφ(x) [uθ(x)] +H [qφ(x)] ) .
Proof. Note that logpθ(x̃) = uθ(x̃) − logZ(θ). And we have the following lower bound on Z(θ) logZ(θ) = log ∫ exp(uθ(x))dx = log ∫ qφ(x)
exp(uθ(x)) qφ(x)
dx ≥ ∫ qφ(x)log
exp(uθ(x)) qφ(x) dx. This can be also seen from: ∫
qφ(x)uθ(x)dx = ∫ qφ(x)logpθ(x)dx+ logZ(θ)
=−KL(qφ(x)||pθ(x)) + logZ(θ) + ∫ qφ(x)logqφ(x)dx.
Furthermore, it can be seen that learning in Kim & Bengio (2016) amounts to optimizing the following evidence upper bound:
max θ min φ U(x̃; θ, φ),
which is unfortunately not revealed in this manner in Kim & Bengio (2016).

heading: 11 CONNECTION BETWEEN INCLUSIVE-NRFS AND GANS

text:
Note that for the generator as defined in Eq. 3, we have the following joint density
logqφ(x, h) = − 1
2σ2 ||x− gφ(h)||2 + constant.
The generator parameter φ is updated according to Eq. 5, which is rewritten as follows:
Epθ(x)qφ(h|x) [∇φlogqφ(x, h)] = 0
Specifically, we draw (h′, x′) ∼ qφ and then perform one-step SGLD to obtain (h, x). To simply the analysis of the connection, suppose h ≈ h′, x′ ≈ gφ(h′) ≈ gφ(h). Then we have
x = x′ + δ1 2
[ ∂
∂x logpθ(x) ]∣∣∣∣ x=x′ + √ δ1η (1), η(1) ∼ N (0, I)
x− gφ(h) ≈ δ1 2
[ ∂
∂x logpθ(x) ]∣∣∣∣ x=gφ(h) = δ1 2 [ ∂ ∂x uθ(x) ]∣∣∣∣ x=gφ(h)
(14)
The gradient in the updating step in Algorithm 1 becomes:
∇φlogqφ(x, h) = 1
σ2
[ ∂
∂φ gφ(h)
] [x− gφ(h)]
≈ 1 σ2
[ ∂
∂φ gφ(h) ] δ1 2 [ ∂ ∂x uθ(x) ]∣∣∣∣ x=gφ(h)
= 1 σ2 δ1 2
[ ∂
∂φ uθ(gφ(h)) ] where ∂∂φgφ(h) is a matrix of size dim(φ)× dim(x). Therefore, the inclusive-NRF Algorithm 1 can be viewed to perform the following steps:
1. Draw an empirical example x̃ ∼ p0. 2. Draw h ∼ p(h), x′ = gφ(h), and generate x by one-step-gradient according to Eq. 14. 3. Update θ by ascending: ∇θuθ(x̃)−∇θuθ(x).
4. Update φ by descending: − ∂∂φuθ(gφ(h)).
Now suppose that we interpret the potential function uθ(x) as the discriminator in GANs (or the critic in Wasserstein GANs), which assign high scalar scores to empirical samples x̃ ∼ p0 and low scalar scores to generated samples x. Then, the inclusive-NRF training could be viewed as playing a two-player minimax game:
min φ max θ Ex̃∼p0 [uθ(x̃)]− Eh∼p(h) [uθ(gφ(h))] , (15)
except that in optimizing θ, the generated sample are further revised by taking one-step-gradient of uθ(x) w.r.t. x (as shown in the above Step 2). The discriminator uθ is trained to discriminate between empirical samples and generated samples, while the generator qφ is trained to fool the discriminator by assigning higher scores to generated samples. From the above analysis, we find some interesting connections between inclusive-NRFs and existing studies in GANs.
• The optimization shown in Eq. 15 is in fact the same as that in Wasserstein GANs (Theorem 3 in Arjovsky et al. (2017)), except that in Wasserstein GANs, the critic uθ(x) is constrained to be 1-Lipschitz continuous. So hopefully we can improve the inclusive-NRF training by constraining the discriminator uθ(x) to be 1-Lipschitz continuous, e.g. by utilizing the recently developed technique of spectral normalization of weight matrices in the discriminator as in Miyato et al. (2018).
• To optimize θ, the generated sample is obtained by taking one-step-gradient of uθ(x) w.r.t. x. The tiny perturbation guided by the gradient to increase the score for the generated sample in fact creates an adversarial example. A similar idea is presented in Liu & Hsieh (2018) that when feeding real samples to the discriminator, 5 steps of PGD (Projected Gradient Descent) attack is taken to decrease the score to create adversarial samples. It is shown in Liu & Hsieh (2018) that training the discriminator with adversarial examples significantly improves the GAN traning. Hopefully in training the discriminator in inclusive-NRFs, the adversarial attack could be increasing scores for generated samples, or decreasing scores for real samples, or a mixed one.
• The above analysis assume the use of one-step SGLD. It can be seen that running finite steps of SGLD in sample revision in fact create adversarial samples to fool the discriminator.

heading: 12 DETAILS OF EXPERIMENTS

heading: 12.1 GMM SYNTHETIC EXPERIMENT

text:
In the GMM experiment, we use the following procedure to estimate the metrics “covered modes” and “realistic ratio” for each trained model.
1. Stochastically generate 100 samples.
2. A mode is defined to be covered (not missed) if there exist generated samples located closely to the mode (with squared distance < 0.02), and those samples are said to be realistic.
3. Count how many modes are covered and calculate the proportion of realistic samples.
4. Repeat the above steps 100 times and perform averaging.
For each method, we independently train 10 models and calculate the mean and standard deviation (SD) across the 10 independent runs.
The network architectures and hyperparameters are the same for all methods, as listed in Table 5. We use SGLD Welling & Teh (2011) for inclusive-NRFs on this synthetic dataset, with empirical revision hyperparameters δl = 0.01.

heading: 12.2 IMAGE GENERATION ON CIFAR-10

text:
Network architectures. For convenience, we refer to the two neural networks in implementing the potential uθ and the generator qφ in NRFs as the potential network and the generator network, respectively. For comparison of different methods, we use the same network architectures as in Table 4 in (Miyato et al., 2018) (ResNet using spectral normalization) for unsupervised learning of NRFs. For supervised learning, we use the semi-supervised inclusive-NRF Algorithm 3 over all labeled images. The difference in network architectures used for semi-supervised and unsupervised learning of inclusive-NRFs is that for SSL, the output layer of the potential network contains K = 10 scalar units, while a single scalar output unit is used for unsupervised learning.
Hyperparameters. We use Adam optimizer with the hyperparameter (β1 = 0, β2 = 0.9 and α = 0.0003 for random fields, α = 0.0001 for generators). For sample revision for inclusive-NRFs, we empirically choose SGLD with L = 1 (δl = 0.003). More revision steps do not significantly improve unsupervised IS, as discussed in section 4.4 Note that we use the potential control loss in both unsupervised (αp = 0.1) and supervised (αd = 1, αp = 0.1) settings, which is found beneficial for stable training.
Evaluation. Figure 5(c)(d) show the generated samples from inclusive-NRFs for unsupervised and supervised settings respectively. We compute inception score (IS) and Frechet inception distance (FID) in the same way as in Miyato et al. (2018). We trained 10 models with different random seeds, and then generate 5000 images 10 times and compute the average inception score and the standard deviation. We compute FID between the true distribution and the generated distribution empirically over 10000 (test set) and 5000 samples.

heading: 12.3 SEMI-SUPERVISED EXPERIMENT ON MNIST, SVHN AND CIFAR-10

text:
The network architectures (taken from the released code from Salimans et al. (2016) and widely used in Li et al. (2017); Dai et al. (2017b)) and hyperparameters for semi-supervised inclusiveNRFs on MNIST, SVHN and CIFAR-10 are listed in Table 6, Table 7 and Table 8 respectively. We use SGHMC for semi-supervised inclusive-NRFs for all three datasets, with empirical revision hyperparameters (β = 0.5, δl = 0.003) for MNIST and CIFAR-10, and (β = 0.5, δl = 0.01) for SVHN. The confidence loss is employed for semi-supervised inclusive-NRFs on MNIST and SVHN, and the potential control loss is employed on CIFAR-10.
Figure 5(a)(b) show the generated samples from semi-supervised inclusive-NRFs trained over SVHN and CIFAR-10 respectively.

heading: 12.4 ABLATION STUDY OF INCLUSIVE-NRFS ON CIFAR-10

text: For unsupervised learning, we use the same networks as in Table 3 in Miyato et al. (2018) (standard CNN using spectral normalization). We use Adam optimizer with the hyperparameter (α = 0.0002, β1 = 0, β2 = 0.9). For semi-supervised learning, the experimental setting is the same as in section 12.3 including the networks, number of labels, etc. For different revision steps, we use (δl = 0.003) for SGLD, and (β = 0.5, δl = 0.003) for SGHMC. The potential control loss is employed in both unsupervised (αp = 0.1) and semi-supervised (αd = 100, αp = 0.1) learning.

heading: 13 SSL TOY EXPERIMENT

text:
In Figure 2, we present the performance of semi-supervised inclusive-NRFs for SSL on a synthetic dataset, which emphasizes that inclusive-NRFs can provide (unnormalized) density estimates for pθ(x), pθ(x, y = 1) and pθ(x, y = 2). In contrast, the use of GANs as general purpose probabilistic generative models has been limited by the difficulty in using them to provide density estimates or even unnormalized potential values for sample evaluation.
The dataset is a 2D GMM with 16 Gaussian components, uniformly laid out on two concentric circles. The two circles represent two different classes, each class with 4 labeled data and 400 unlabeled data. The network architectures are the same as in Table 5, except that the neural network which implement the potential function uθ(x, y) for SSL now has two units in the output.

heading: 14 LATENT SPACE INTERPOLATION

text: Figure 3 shows that the auxiliary generator smoothly outputs transitional samples as the latent code h moves linearly in the latent space. The interpolated generation demonstrates that the model has indeed learned an abstract representation of the data.

heading: 15 CLASS-CONDITIONAL GENERATION

text:
Figure 4 shows class-conditional generation results on MNIST with semi-supervised inclusive-NRFs. Notice that the generator does not explicitly include class labels, thus it is unable to perform classconditional generation directly. However, the random field has modeling of pθ(x, y), based on which we can perform class-conditional generation as follows:
1. Generate a sample x unconditionally, by ancestral sampling with the generator. 2. Predict the label y for the sample x by the random field; 3. Starting from x, running SGLD/SGHMC revision with pθ(x|y) as the target density by
fixing y. The resulting samples could be viewed as conditional generations, according to Theorem 1.


summaries: This paper studies the problem of learning a better poisoned graph parameters that can maximize the loss of a graph neural network. The proposed using meta-learning to compute the second-order derivatives to get the meta-gradients seems reasonable. The authors also proposed approximate methods to compute the graph as learning parameters, which could be more efficient since the second-order derivatives are no longer computed. The experimental results on three graph datasets show that the proposed model could improve the misclassification rate of the unlabeled nodes.

summaries: This paper studied data poisoning attacking for graph neural networks. The authors proposed treating graph structures as hyperparameters and leveraged recent progress on meta-learning for optimizing the adversarial attacks. Different from some recent work on adversarial attacks for graph neural networks (Zuigner et al. 2018; Dai et al. 2018), which focus on attacking specific nodes, this paper focuses on attacking the  overall performance of graph neural networks. Experiments on a few data sets prove the effectiveness of the proposed approach.

abstractText: Deep learning models for graphs have advanced the state of the art on many tasks. Despite their recent success, little is known about their robustness. We investigate training time attacks on graph neural networks for node classification that perturb the discrete graph structure. Our core principle is to use meta-gradients to solve the bilevel problem underlying training-time attacks, essentially treating the graph as a hyperparameter to optimize. Our experiments show that small graph perturbations consistently lead to a strong decrease in performance for graph convolutional networks, and even transfer to unsupervised embeddings. Remarkably, the perturbations created by our algorithm can misguide the graph neural networks such that they perform worse than a simple baseline that ignores all relational information. Our attacks do not assume any knowledge about or access to the target classifiers.

authors:
Lada A Adamic
Natalie Glance

title: The political blogosphere and the 2004 US election: divided they blog

venue: In International workshop on Link discovery,

authors:
Forest Agostinelli
Matthew Hoffman
Peter Sadowski
Pierre Baldi

title: Learning activation functions to improve deep neural networks

venue: arXiv preprint arXiv:1412.6830,

authors:
Peter W Battaglia
Jessica B Hamrick
Victor Bapst
Alvaro Sanchez-Gonzalez
Vinicius Zambaldi
Mateusz Malinowski
Andrea Tacchetti
David Raposo
Adam Santoro
Ryan Faulkner

title: Relational inductive biases, deep learning, and graph networks

venue: arXiv preprint arXiv:1806.01261,

authors:
Samy Bengio
Yoshua Bengio
Jocelyn Cloutier
Jan Gecsei

title: On the optimization of a synaptic learning rule

venue: In Preprints Conf. Optimality in Artificial and Biological Neural Networks,

title: Gradient-based optimization of hyperparameters

venue: Neural computation,

authors:
Aleksandar Bojchevski
Stephan Günnemann

title: Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking

venue: In ICLR,

title: Adversarial attacks on node embeddings

venue: arXiv preprint arXiv:1809.01093,

title: Bayesian robust attributed graph clustering: Joint learning of partial anomalies and group structure

venue: In AAAI,

authors:
Aleksandar Bojchevski
Oleksandr Shchur
Daniel Zügner
Stephan Günnemann

title: NetGAN: Generating graphs via random walks

venue: In ICML,

authors:
Olivier Chapelle
Bernhard Schölkopf
Alexander Zien

title: Semi-Supervised Learning. Adaptive Computation and Machine Learning series

authors:
Yizheng Chen
Yacin Nadji
Athanasios Kountouras
Fabian Monrose
Roberto Perdisci
Manos Antonakakis
Nikolaos Vasiloglou

title: Practical attacks against graph-based clustering

venue: arXiv preprint arXiv:1708.09056,

authors:
Hanjun Dai
Hui Li
Tian Tian
Xin Huang
Lin Wang
Jun Zhu
Le Song

title: Adversarial attack on graph structured data

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

authors:
Ian J Goodfellow
Jonathon Shlens
Christian Szegedy

title: Explaining and harnessing adversarial examples

authors:
Thomas N Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

authors:
Johannes Klicpera
Aleksandar Bojchevski
Stephan Günnemann

title: Predict then propagate: Graph neural networks meet personalized pagerank

venue: In International Conference on Learning Representations (ICLR),

authors:
Ben London
Lise Getoor

title: Collective classification of network data

venue: Data Classification: Algorithms and Applications,

authors:
Andrew Kachites McCallum
Kamal Nigam
Jason Rennie
Kristie Seymore

title: Automating the construction of internet portals with machine learning

venue: Information Retrieval,

authors:
Shike Mei
Xiaojin Zhu

title: Using machine teaching to identify optimal training-set attacks on machine learners

authors:
Federico Monti
Davide Boscaini
Jonathan Masci
Emanuele Rodola
Jan Svoboda
Michael M Bronstein

title: Geometric deep learning on graphs and manifolds using mixture model cnns

venue: In CVPR,

authors:
Luis Muñoz-González
Battista Biggio
Ambra Demontis
Andrea Paudice
Vasin Wongrassamee
Emil C Lupu
Fabio Roli

title: Towards poisoning of deep learning algorithms with back-gradient optimization

venue: In 10th ACM Workshop on Artificial Intelligence and Security,

authors:
Devang K Naik
RJ Mammone

title: Meta-neural networks that learn by learning

venue: In IJCNN,

authors:
Alex Nichol
John Schulman

title: On first-order meta-learning algorithms

venue: arXiv preprint arXiv:1803.02999,

authors:
Bryan Perozzi
Rami Al-Rfou
Steven Skiena

title: Deepwalk: Online learning of social representations

venue: In SIGKDD,

authors:
Trang Pham
Truyen Tran
Dinh Q. Phung
Svetha Venkatesh

title: Column networks for collective classification

title: Learning to control fast-weight memories: An alternative to dynamic recurrent networks

venue: Neural Computation,

authors:
Prithviraj Sen
Galileo Namata
Mustafa Bilgic
Lise Getoor
Brian Galligher
Tina Eliassi-Rad

title: Collective classification in network data

venue: AI magazine,

authors:
Christian Szegedy
Wojciech Zaremba
Ilya Sutskever
Google Inc
Joan Bruna
Dumitru Erhan
Ian Goodfellow
Rob Fergus

title: Intriguing properties of neural networks

authors:
Sebastian Thrun
Lorien Pratt

title: Learning to learn: Introduction and overview

venue: In Learning to learn,

authors:
Mohamad Ali Torkamani
Daniel Lowd

title: Convex adversarial collective classification

venue: In ICML, pp

authors:
Daniel Zügner
Amir Akbarnejad
Stephan Günnemann

title: Adversarial attacks on neural networks for graph data

heading: 1 INTRODUCTION

text:
Graphs are a powerful representation that can model diverse data from virtually any domain, such as biology (protein interaction networks), chemistry (molecules), or social networks (Facebook). Not surprisingly, machine learning on graph data has a longstanding history, with tasks ranging from node classification, over community detection, to generative modeling.
In this paper, we study node classification, which is an instance of semi-supervised classification: given a single (attributed) network and a subset of nodes whose class labels are known (e.g., the topic of a paper in a citation graph), the goal is to infer the classes of the unlabeled nodes. While there exist many classical approaches to node classification (London & Getoor, 2014; Chapelle et al., 2006), recently deep learning on graphs has gained much attention (Monti et al., 2017; Bojchevski & Günnemann, 2018a; Battaglia et al., 2018; Perozzi et al., 2014; Bojchevski et al., 2018; Klicpera et al., 2019). Specifically, graph convolutional approaches (Kipf & Welling, 2017; Pham et al., 2017) have improved the state of the art in node classification.
However, recent works have also shown that such approaches are vulnerable to adversarial attacks both at test time (evasion) as well as training time (poisoning attacks) (Zügner et al., 2018; Dai et al., 2018). A core strength of models using graph convolution – exploiting the information in a node’s neighborhood to improve classification – is also a major vulnerability: because of these propagation effects, an attacker can change a single node’s prediction without even changing any of its attributes or edges. This is because the foundational assumption that all samples are independent of each other does not hold for node classification. Network effects such as homophily (London & Getoor, 2014) support the classification, while on the other hand they enable indirect adversarial attacks.
So far, all existing attacks on node classification models are targeted, that is, aim to provoke misclassification of a specific single node, e.g. a person in a social network. In this work, we propose the first algorithm for poisoning attacks that is able to compromise the global node classification performance of a model. We show that even under restrictive attack settings and without access to the target classifier, our attacks can render it near-useless for use in production (i.e., on test data).
Our approach is based on the principle of meta learning, which has traditionally been used for hyperparameter optimization (Bengio, 2000), or, more recently, few-shot learning (Finn et al., 2017). In essence, we turn the gradient-based optimization procedure of deep learning models upside down and treat the input data – the graph at hand – as a hyperparameter to learn.

heading: 2 RELATED WORK

text:
Adversarial attacks on machine learning models have been studied both in the machine learning and security community and for many different model types (Mei & Zhu, 2015). It is important to distinguish attacks from outliers; while the latter naturally occur in graphs (Bojchevski & Günnemann, 2018), adversarial examples are deliberately created with the goal to mislead machine learning models and often designed to be unnoticeable. Deep neural networks are highly sensitive to these small adversarial perturbations to the data (Szegedy et al., 2014; Goodfellow et al., 2015). The vast majority of attacks and defenses assume the data instances to be independent and continuous. This assumption clearly does not hold for node classification and many other tasks on graphs.
Works on adversarial attacks for graph learning tasks are generally sparse. Chen et al. (2017) have measured the changes in the resulting graph clustering when injecting noise to a bi-partite graph that represent DNS queries. However, their focus is not on generating attacks in a principled way. Torkamani & Lowd (2013) consider adversarial noise in the node features in order to improve robustness of collective classification via associative Markov networks.
Only recently researchers have started to study adversarial attacks on deep learning for graphs. Dai et al. (2018) consider test-time (i.e., evasion) attacks on graph classification (i.e., classification of graphs themselves) and node classification. However, they do not consider poisoning (i.e., trainingtime) attacks or evaluate transferability of their attacks, and restrict the attacks to edge deletions only. Moreover, they focus on targeted attacks, i.e. attacks designed to change the prediction of a single node. Zügner et al. (2018) consider both test-time and training-time attacks on node classification models. They circumvent explicitly tackling the bilevel optimization problem underlying poisoning attacks by performing their attacks based on a (static) surrogate model and evaluating their impact by training a classifier on the data modified by their algorithm. In contrast to Dai et al. (2018), their attacks can both insert and remove edges, as well as modify node attributes in the form of binary vectors. Again, their algorithm is suited only to targeted attacks on single nodes; the problem of training-time attacks on the overall performance of node classification models remains unexplored. Bojchevski & Günnemann (2018b) propose poisoning attacks on a different task: unsupervised node representation learning (or node embeddings). They exploit perturbation theory to maximize the loss obtained after training DeepWalk. In this work, we focus on semi-supervised learning.
Meta-learning (Thrun & Pratt, 1998; Naik & Mammone, 1992), or learning to learn, is the task of optimizing the learning algorithm itself; e.g., by optimizing the hyperparameters Bengio (2000), learning to update the parameters of a neural network (Schmidhuber, 1992; Bengio et al., 1992), or the activation function of a model (Agostinelli et al., 2014). Gradient-based hyperparameter optimization works by differentiating the training phase of a model to obtain the gradients w.r.t. the hyperparameters to optimize.
The key idea of this work is to use meta-learning for the opposite: modifying the training data to worsen the performance after training (i.e., training-time or poisoning attacks). Muñoz-González et al. (2017) demonstrate that meta learning can indeed be used to create training-time attacks on simple, linear classification models. On continuous data, they report little success when attacking deep neural networks, and on discrete datasets, they do not consider deep learning models or problems with more than two classes. Like most works on adversarial attacks, they assume the data instances to be independent. In this work, for the first time, we propose an algorithm for global attacks on (deep) node classification models at training time. In contrast to Zügner et al. (2018), we explicitly tackle the bilevel optimization problem of poisoning attacks using meta learning.

heading: 3 PROBLEM FORMULATION

text:
We consider the task of (semi-supervised) node classification. Given a single (attributed) graph and a set of labeled nodes, the goal is to infer the class labels of the unlabeled nodes. Formally, let G = (A,X) be an attributed graph with adjacency matrix A ∈ {0, 1}N×N and node attribute matrix X ∈ RN×D, where N is the number of nodes and D the dimension of the node feature vectors. W.l.o.g., we assume the node IDs to be V = {1, . . . , N}. Given the set of labeled nodes VL ⊆ V , where nodes are assigned exactly one class in C = {c1, c2, ..., cK}, the goal is to learn a function fθ, which maps each node v ∈ V to exactly one
of the K classes in C (or in a probabilistic formulation: to the K-simplex). Note that this is an instance of transductive learning, since all test samples (i.e., the unlabeled nodes) as well as their attributes and edges (but not their class labels!) are known and used during training (Chapelle et al., 2006). The parameters θ of the function fθ are generally learned by minimizing a loss function Ltrain (e.g. cross-entropy) on the labeled training nodes:
θ∗ = arg min θ Ltrain(fθ(G)), (1)
where we overload the notation of fθ to indicate that we feed in the whole graph G.

heading: 3.1 ATTACK MODEL

text:
Adversarial attacks are small deliberate perturbations of data samples in order to achieve the outcome desired by the attacker when applied to the machine learning model at hand. The attacker is constrained in the knowledge they have about the data and the model they attack, as well as the adversarial perturbations they can perform.
Attacker’s goal. In our work, the attacker’s goal is to increase the misclassification rate (i.e., one minus the accuracy) of a node classification algorithm achieved after training on the data (i.e., graph) modified by our algorithm. In contrast to Zügner et al. (2018) and Dai et al. (2018), our algorithm is designed for global attacks reducing the overall classification performance of a model. That is, the goal is to have the test samples classified as any class different from the true class.
Attacker’s knowledge. The attacker can have different levels of knowledge about the training data, i.e. the graph G, the target machine learning model M, and the trained model parameters θ. In our work, we focus on limited-knowledge attacks where the attacker has no knowledge about the classification model and its trained weights, but the same knowledge about the data as the classifier. In other words, the attacker can observe all nodes’ attributes, the graph structure, as well as the labels of the subset VL and uses a surrogate model to modify the data. Besides assuming knowledge about the full data, we also perform experiments where only a subset of the data is given. Afterwards, this modified data is used to train deep neural networks to degrade their performance.
Attacker’s capability. In order to be effective and remain undiscovered, adversarial attacks should be unnoticeable. To account for this, we largely follow Zügner et al. (2018)’s attacker capabilities. First, we impose a budget constraint ∆ on the attacks, i.e. limit the number of changes ‖A− Â‖0 ≤ ∆ (here we have 2∆ since we assume the graph to be symmetric). Furthermore, we make sure that no node becomes disconnected (i.e. a singleton) during the attack. One of the most fundamental properties of a graph is its degree distribution. Any significant changes to it are very likely to be noticed; to prevent such large changes to the degree distribution, we employ Zügner et al. (2018)’s unnoticeability constraint on the degree distribution. Essentially, it ensures that the graph’s degree distribution can only marginally be modified by the attacker. The authors also derive an efficient way to check for violations of the constraint so that it adds only minimal computational overhead to the attacks. While in this work we focus on changing the graph structure only, our algorithm can easily be modified to change the node features as well. We summarize all these constraints and denote the set of admissible perturbations on the data as Φ(G), where G is the graph at hand.

heading: 3.2 OVERALL GOAL

text:
Poisoning attacks can be mathematically formulated as a bilevel optimization problem:
min Ĝ∈Φ(G) Latk(fθ∗(Ĝ)) s.t. θ∗ = arg min θ Ltrain(fθ(Ĝ)). (2)
Latk is the loss function the attacker aims to optimize. In our case of global and unspecific (regarding the type of misclassification) attacks, the attacker tries to decrease the generalization performance of the model on the unlabeled nodes. Since the test data’s labels are not available, we cannot directly optimize this loss. One way to approach this is to maximize the loss on the labeled (training) nodes Ltrain, arguing that if a model has a high training error, it is very likely to also generalize poorly (the opposite is not true; when overfitting on the training data, a high generalization loss can correspond to a low training loss). Thus, our first attack option is to choose Latk = −Ltrain. Recall that semi-supervised node classification is an instance of transductive learning: all data samples (i.e., nodes) and their attributes are known at training time (but not all labels!). We can use
this insight to obtain a second variant of Latk. The attacker can learn a model on the labeled data to estimate the labels ĈU of the unlabeled nodes VU = V\VL. The attacker can now perform selflearning, i.e. use these predicted labels and compute the loss of a model on the unlabeled nodes, yielding our second option Latk = −Lself where Lself = L(VU , ĈU ). Note that, at all times, only the labels of the labeled nodes are used for training; Lself is only used to estimate the generalization loss after training. In our experimental evaluation, we compare both versions of Latk outlined above. Importantly, notice the bilevel nature of the problem formulation in Eq. (2): the attacker aims to maximize the classification loss achieved after optimizing the model parameters on the modified (poisoned) graph Ĝ. Optimizing such a bilevel problem is highly challenging by itself. Even worse, in our graph setting the data and the action space of the attacker are discrete: the graph structure is A = {0, 1}N×N , and the possible actions are edge insertions and deletions. This makes the problem even more difficult in two ways. First, the action space is vast; given a budget of ∆ perturbations, the number of possible attacks is, ignoring symmetry, ( N2
∆
) and thus in O(N2∆); exhaustive search is
clearly infeasible. Second, a discrete data domain means that we cannot use gradient-based methods such as gradient descent to make small (real-valued) updates on the data to optimize a loss.

heading: 4 GRAPH STRUCTURE POISONING VIA META-LEARNING

heading: 4.1 POISONING VIA META-GRADIENTS

text:
In this work, we tackle the bilevel problem described in Eq. (2) using meta-gradients, which have traditionally been used in meta-learning. The field of meta-learning (or learning to learn) tries to make the process of learning machine learning models more time and/or data efficient, e.g. by finding suitable hyperparameter configurations (Bengio, 2000) or initial weights that enable rapid adaptation to new tasks or domains in few-shot learning (Finn et al., 2017).
Meta-gradients (e.g., gradients w.r.t. hyperparameters) are obtained by backpropagating through the learning phase of a differentiable model (typically a neural network). The core idea behind our adversarial attack algorithm is to treat the graph structure matrix as a hyperparameter and compute the gradient of the attacker’s loss after training with respect to it: ∇metaG := ∇G Latk(fθ∗(G)) s.t. θ∗ = optθ(Ltrain(fθ(G))), (3) where opt(·) is a differentiable optimization procedure (e.g. gradient descent and its stochastic variants) andLtrain the training loss. Notice the similarity of the meta-gradient to the bi-level formulation in Eq. (2); the meta-gradient indicates how the attacker loss Latk after training will change for small perturbations on the data, which is exactly what a poisoning attacker needs to know.
As an illustration, consider an example where we instantiate opt with vanilla gradient descent with learning rate α starting from some intial parameters θ0
θt+1 = θt − α∇θtLtrain(fθt(G)) (4) The attacker’s loss after training for T steps is Latk(fθT (G)). The meta-gradient can be expressed by unrolling the training procedure: ∇metaG = ∇GLatk(fθT (G)) = ∇fLatk(fθT (G)) · [∇GfθT (G) +∇θT fθT (G) · ∇GθT ] ,where (5) ∇Gθt+1 = ∇Gθt − α∇G∇θtLtrain(fθt(G)) Note that the parameters θt itself depend on the graph G (see Eq. 4); they are not fixed. Thus, the derivative w.r.t. the graph has to be taken into account, chaining back until θ0. Given this, the attacker can use the meta-gradient to perform a meta update M on the data to minimize Latk:
G(k+1) ←M(G(k)) (6) The final poisoned dataG(∆) is obtained after performing ∆ meta updates. A straightforward way to instantiate M is (meta) gradient descent with some step size β: M(G) = G− β∇GLatk(fθT (G))). It has to be noted that such a gradient-based update rule is neither possible nor well-suited for problems with discrete data (such as graphs). Due to the discreteness, the gradients are not defined. Thus, in our approach we simply relax the data’s discreteness condition. However, we still perform discrete updates (actions) since the above simple gradient update would lead to dense (and continuous) adjacency matrices; not desired and not efficient to handle. Thus, in the following section, we propose a greedy approach to preserve the data’s sparsity and discreteness.

heading: 4.2 GREEDY POISONING ATTACKS VIA META GRADIENTS

text:
We assume that the attacker does not have access to the target classifier’s parameters, outputs, or even knowledge about its architecture; the attacker thus uses a surrogate model to perform the poisoning attacks. Afterwards the poisoned data is used to train deep learning models for node classification (e.g. a GCN) to evaluate the performance degradation due to the attack. We use the same surrogate model as Zügner et al. (2018), which is a linearized two-layer graph convolutional network:
fθ(A,X) = softmax(Â 2XW ), (7)
where Â = D−1/2ÃD−1/2, Ã = A+ I , A is the adjacency matrix, X are the node features, D the diagonal matrix of the node degrees, and θ = {W} the set of learnable parameters. In contrast to Zügner et al. (2018) we do not linearize the output (softmax) layer.
Note that we only perform changes to the graph structure A, hence we treat the node attributes X as a constant during our attacks. For clarity, we replace G with A in the meta gradient formulation.
We define a score function S : V × V → R that assigns each possible action a numerical value indicating its (estimated) impact on the attacker objective Latk. Given the meta-gradient for a node pair (u, v), we define S(u, v) = ∇metaauv · (−2 · auv + 1) where auv is the entry at position (u, v) in the adjacency matrix A. We essentially flip the sign of the meta-gradients for connected node pairs as this yields the gradient for a change in the negative direction (i.e., removing the edge).
We greedily pick the perturbation e′ = (u′, v′) with the highest score one at a time e′ = arg max
e=(u,v):M(A,e)∈Φ(G) S(u, v), (8)
whereM(A, e) ∈ Φ(G) ensures that we only perform changes compliant with our attack constraints (e.g., unnoticeability). The meta update function M(A, e) inserts the edge e = (i, j) by setting aij = 1 if nodes (i, j) are currently not connected and otherwise deletes the edge by setting aij = 0.

heading: 4.3 APPROXIMATING META-GRADIENTS

text:
Computing the meta gradients is expensive both from a computational and a memory point-of-view. To alleviate this issue, Finn et al. (2017) propose a first-order approximation, leading to
∇metaA = ∇ALatk(fθT (A)) ≈ ∇ALatk(fθ̃T (A)) = ∇fLatk(fθ̃T (A)) · ∇Afθ̃T (A). (9)
We denote by θ̃t the parameters at time t independent of the data A (and θ̃t−1), i.e. ∇Aθ̃t = 0; the gradient is thus not propagated through θ̃t. This corresponds to taking the gradient of the attack loss Latk w.r.t. the data, after training the model for T steps. We compare against this baseline in our experiments; as also done in Zügner et al. (2018). However, unlike the meta-gradient, this approximation completely disregards the training dynamics.
Nichol & Schulman (2018) propose a heuristic of the meta gradient in which they update the initial weights θ0 on a line towards the local optimum θT to achieve faster convergence in a multi-task learning setting: ∇metaθ0 ≈ ∑T t=1∇θ̃tLtrain(fθ̃t(A;X)). Again, they assume θ̃t to be independent of θ̃t−1. While there is no direct connection to the formulation of the meta gradient in Eq. (5), there is an intuition behind it: the heuristic meta gradient is the direction, in which, on average, we have observed the strongest increase in the training loss during the training procedure. The authors’ experimental evaluation further indicates that this heuristic achieves similar results as the meta gradient while being much more efficient to compute (see Appendix C for a discussion on complexity).
Adapted to our adversarial attack setting on graphs, we get ∇metaA ≈ ∑T t=1∇ALtrain(fθ̃t(A;X)). We can view this as a heuristic of the meta gradient when Latk = −Ltrain. Likewise, again taking the transductive learning setting into account, we can use self-learning to estimate the loss on the unlabeled nodes, replacing Ltrain by Lself. Indeed, we combine these two views
∇metaA ≈ ΣTt=1λ∇ALtrain(fθ̃t(A;X)) + (1− λ)∇ALself(fθ̃t(A;X)), (10) where λ can be used to weight the two objectives. This approximation has a much smaller memory footprint than the exact meta gradient since we don’t have to store the whole training trajectory θ̃1, . . . , θ̃T in memory; additionally, there there are no second-order derivatives to be computed. A summary of our algorithm can be found in Appendix A.

heading: 5 EXPERIMENTS

text:
Setup. We evaluate our approach on the well-known CITESEER (Sen et al., 2008), CORA-ML (McCallum et al., 2000), and POLBLOGS (Adamic & Glance, 2005) datasets; an overview is given in Table 6. We split the datasets into labeled (10%) and unlabeled (90%) nodes. The labels of the unlabeled nodes are never visible to the attacker or the classifiers and are only used to evaluate the generalization performance of the models. Our code is available at https://www.kdd.in. tum.de/gnn-meta-attack.
We evaluate the transferability of adversarial attacks by training deep node classification models on the modified (poisoned) data. For this purpose, we use Graph Convolutional Networks (GCN) (Kipf & Welling, 2017) and Column Networks (CLN) (Pham et al., 2017). Both are models utilizing the message passing framework (a.k.a. graph convolution) and trained in a semi-supervised way. We further evaluate the node classification performance achieved by training a standard logistic regression model on the node embeddings learned by DeepWalk (Perozzi et al., 2014). DeepWalk itself is trained in an unsupervised way and without node attributes or graph convolutions; thus, this is arguably an even more difficult transfer task.
We repeat all of our attacks on five different splits of labeled/unlabeled nodes and train all target classifiers ten times per attack (using the split that was used to create the attack). In our tables, the uncertainty indicates 95 % confidence intervals of the mean obtained via bootstrapping. For our meta-gradient approaches, we compute the meta-gradient ∇metaA Latk(fθT (A;X)) by using gradient descent with momentum for 100 iterations. We refer to our meta-gradient approach with self-training as Meta-Self and to the variant without self-training as Meta-Train. Similarly, we refer to our approximations as A-Meta-Self (with λ=0), A-Meta-Train (λ=1), and A-Meta-Both (λ=0.5).
Comparing meta-gradient heuristics. First, we analyze the different meta gradient heuristics described in Section 4.3. The results can be seen in Table 1. All principles successfully increase the misclassification rate (i.e., 1 − accuracy on unlabeled nodes) obtained on the test data, compared to the results obtained with the unperturbed graph. Since A-Meta-Self consistently shows a weaker performance than A-Meta-Both, we do not further consider A-Meta-Self in the following.
Comparison with competing methods. We compare our meta-gradient approach as well as its approximations with various baselines and Nettack (Zügner et al., 2018). DICE (‘delete internally, connect externally’) is a baseline where, for each perturbation, we randomly choose whether to insert or remove an edge. Edges are only removed between nodes from the same class, and only inserted between nodes from different classes. This baseline has all true class labels (train and test) available and thus more knowledge than all competing methods. First-order refers to the approximation proposed by Finn et al. (2017), i.e. ignoring all second-order derivatives. Note that Nettack is not designed for global attacks. In order to be able to compare to them, for each perturbation we ran-
domly select one target node from the unlabeled nodes and attack it using Nettack while considering all nodes in the network. In this case, its time and memory complexity is O(N3) and thus it was not feasible to run it on any but the sparsest dataset. Meta w/ Oracle corresponds to our meta-gradient approach when supplied with all true class labels on the test data – this only serves as a reference point since it cannot be carried out in real scenarios where the test nodes’ labels are unknown. For all methods, we enforce the unnoticeability constraint introduced by Zügner et al. (2018), which ensures that the graph’s degree distribution changes only slightly. In Appendix D we show that the unnoticeability constraint does not significantly limit the impact of our attacks.
In Table 2 we see the misclassification rates (i.e., 1 - accuracy on unlabeled nodes) achieved by changing 5% ofELCC edges according to the different methods (larger is better, except for the average rank). That is, each method is allowed to modify 5% of ELCC , i.e. the number of edges present in the graph before the attack. We present similar tables for 1% and 10% changes in Appendix F. Our meta-gradient with self-training (Meta-Self) produces the strongest drop in performance across all models and datasets as indicated by the average rank. Changing only 5% of the edges leads to a relative increase of up to 48% in the misclassification rate of GCN on CORA-ML.
Remarkably, our memory efficient meta-gradient approximations lead to strong increases in misclassifications as well. They outperform both baselines and are in many cases even on par with the more expensive meta-gradient. In Appendix F, Table 11 we also show that using only T = 10 training iterations of the surrogate models for computing the meta gradient (or its approximations) can significantly hurt the performance across models and datasets. Moreover, in Table 8 in Appendix F we show that our heuristic is successful at attacking a dataset with roughly 20K nodes.
While the focus of our work is poisoning attacks by modifying the graph structure, our method can be applied to node feature attacks as well. In Appendix E we show a proof of concept that our attacks are also effective when attacking by perturbing both node features and the graph structure.
In Fig. 1 we see the drop in classification performance of GCN on CORA-ML for increasing numbers of edge insertions/deletions (similar plots for the remaining datasets and models are provided in Appendix F). Meta-Self is even able to reduce the classification accuracy below 50%. Fig. 2 shows the classification accuracy of GCN and CLN as well as a baseline operating on the node attributes only, i.e. ignoring the graph. Not surprisingly, deep models achieve higher accuracy than the baseline when trained on the clean CITESEER graph – exploiting the network information improves classification. However, by only perturbing 5% of the edges, we obtain the opposite: GCN and CLN perform worse than the baseline – the graph structure now hurts classification.
Impact of graph structure and trained weights. Another interesting property of our attacks can be seen in Table 3, whereW and Ŵ correspond to the weights trained on the clean CORA-ML network A and a version Â poisoned by our algorithm (here with even 25 % modified edges), respectively.
Note that the classification accuracy barely changes when modifying the underlying network for a given set of trained weights; even when applying the clean weightsW on the highly corrupted Â, the performance drops only marginally. Likewise, even the clean graph A only leads to a low accuracy when using it with the weights Ŵ . This result emphasizes the importance of the training procedure for the performance of graph models and shows that our poisoning attack works by derailing the training procedure from the start, i.e. leading to ‘bad’ weights.
Adversarial edges Original edges
0 5 10
Shortest path (a)
D en
si ty
−15 −10 −5 log(CE)
(b)
1 4 16 64 256
Node degree (c)
Figure 3: Analysis of adversarially inserted edges
Table 5: Share (in %) of edge deletions (DEL) and insertions (INS) by Meta-Self on CORA-ML.
ci=cj ci 6=cj DEL 15.3 3.9 INS 9.4 71.4
Analysis of attacks. An interesting question to ask is why the adversarial changes created by our meta-gradient approach are so destructive, and what patterns they follow. If we can find out what makes an edge insertion or deletion a strong adversarial change, we can circumvent expensive metagradient computations or even use this knowledge to detect adversarial attacks.
In Fig. 3 we compare edges inserted by our meta-gradient approach to the edges originally present in the CORA-ML network. Fig. 3 (a) shows the shortest path lengths between nodes pairs before being connected by adversarially inserted edges vs. shortest path lengths between all nodes in the original graph. In Fig. 3 (b) we compare the edge betweenness centrality (CE) of adversarially inserted edges to the centrality of edges present in the original graph. In (c) we see the node degree distributions of the original graph and the node degrees of the nodes that are picked for adversarial edges. For all three measures no clear distinction can be made. There is a slight tendency for the algorithm to connect nodes that have higher-than-average shortest paths and low degrees, though.
As we can see in Table 5, roughly 80% of our meta attack’s perturbations are edge insertions (INS). As expected by the homophily assumption, in most cases edges inserted connect nodes from different classes and edges deleted connect same-class nodes. However, as the comparison with the DICE baseline shows, this by itself can also not explain the destructive performance of the meta-gradient.
Limited knowledge about the graph structure. In the experiments described above, the attacker has full knowledge about the graph structure and all node attributes (as typical in a transductive setting). We also tested our algorithm on a sub-graph of CORA-ML and CITESEER. That is, we select the 10% labeled nodes and randomly select neighbors of these until we have a subgraph with number of nodes n = 0.3N . We run our attacks on this small subgraph, and afterwards plug in the perturbations into the original graphs to train GCN and CLN as before. Table 4 summarizes the results: Even in this highly restricted setting, our attacks consistently increase misclassification rate across datasets and models, highlighting the effectiveness of our method.

heading: 6 CONCLUSION

text: We propose an algorithm for training-time adversarial attacks on (attributed) graphs, focusing on the task of node classification. We use meta-gradients to solve the bilevel optimization problem underlying the challenging class of poisoning adversarial attacks. Our experiments show that attacks created using our meta-gradient approach consistently lead to a strong decrease in classification performance of graph convolutional models and even transfer to unsupervised models. Remarkably, even small perturbations to a graph based on our approach can lead to graph neural networks performing worse than a baseline ignoring all relational information. We further propose approximations of the metagradients that are less expensive to compute and, in many cases, have a similarly destructive impact on the training of node classification models. While we are able to show small statistical differences of adversarial and ‘normal’ edges, it is still an open question what makes the edges inserted/removed by our algorithm so destructive, which could then be used to detect or defend against attacks.

heading: ACKNOWLEDGEMENTS

text: This research was supported by the German Research Foundation, grant GU 1409/2-1.

heading: A ALGORITHM

text:
Algorithm 1: Poisoning attack on graph neural networks with meta gradients and self-training Input: Graph G = (A,X), modification budget ∆, number of training iterations T , training class labels
CL Output: Modified graph Ĝ = (Â,X)
θ̂ ← train surrogate model on the input graph using known labels CL; ĈU ← predict labels of unlabeled nodes using θ̂; Â← A; while ‖Â−A‖0 < 2∆ do
randomly initialize θ0;
for t in 0 . . . T − 1 do θt+1 ← step (θt,∇θtLtrain(fθt(Â,X));CL); // update e.g. via gradient descent
// Compute meta gradient via backprop through the training procedure ∇meta Â ← ∇ÂLself(fθT (Â,X); ĈU ); S ← ∇meta Â (−2Â+ 1) ; // Flip gradient sign of node pairs with edge e′ ← maximum entry (u, v) in S that fulfills constraints Φ(G); Â← insert or remove edge e′ to/from Â;
Ĝ← (Â,X); return : Ĝ
Algorithm 2: Poisoning attack on GNNs with approximate meta gradients and self-training Input: Graph G = (A,X), modification budget ∆, number of training iterations T , gradient weighting λ, training class labels CL Output: Modified graph Ĝ = (Â,X)
θ̂ ← train surrogate model on the input graph using known labels CL; ĈU ← predict labels of unlabeled nodes using θ̂; Â← A; while ‖Â−A‖0 < 2∆ do
randomly initialize θ0;
∇meta Â ← λ∇ÂLtrain(fθ0(Â;X);CL) + (1− λ)∇ÂLself(fθ0(Â;X); ĈU ) for t in 0 . . . T − 1 do θt+1 ← step (θt,∇θtLtrain(fθt(Â,X));CL); // update e.g. via gradient descent
θ̃t+1 ← stop gradient(θt+1) ; // no backprop through training ∇meta Â ← ∇meta Â + λ∇ÂLtrain(fθ̃t+1(Â;X);CL) + (1− λ)∇ÂLself(fθ̃t+1(Â;X); ĈU )
S ← ∇meta Â (−2Â+ 1) ; // Flip gradient sign of node pairs with edge e′ ← maximum entry (u, v) in S that fulfills constraints Φ(G); Â← insert or remove edge e′ to/from Â;
Ĝ← (Â,X); return : Ĝ

heading: B DATASET STATISTICS

text: In Table 6 we see the characteristics of the datasets used in this work. Results for PUBMED can be found in Table 8 in Appendix F.

heading: C COMPLEXITY ANALYSIS

text:
In our attack we handle both edge insertions and deletions, i.e. each element in the adjacency matrix A ∈ {0, 1}N×N can be changed. This means that without further optimization, the (approximate) meta gradient for each node pair has to be computed, leading to a baseline memory and computational complexity of O(N2). For the meta gradient computation we additionally have to store the entire weight trajectory during training, adding O(T · |θ|) to the memory cost, where T is the number of inner training steps and |θ| the number of weights. Thus, memory complexity of our meta gradient attack is O(N2 + T · |θ|). The second-order derivatives at each step T in the meta gradient formulation can be computed in O(N2) using Hessian-vector products, leading to a computational complexity of O(T ·N2). For the meta gradient heuristics, the computational complexity is similar since we have to evaluate the gradient w.r.t. the adjacency matrix at every training step. However, the training trajectory of the weights does not have to be kept in memory, yielding a memory complexity of O(N2). This is highly beneficial, as memory (especially on GPUs) is limited.
The computational and memory complexity of our adversarial attacks implies that (as-is) it can be executed for graphs with roughly 20K nodes using a commodity GPU. The complexity, however, can be drastically reduced by pre-filtering the elements in the adjacency matrix for which the (meta) gradient needs to be computed, since only a fraction of entries in the adjacency matrix are promising candidate perturbations. We leave such performance optimization for future work.

heading: D UNNOTICEABILITY CONSTRAINT

text: In all our experiments, we enforce the unnoticeability constraint on the degree distribution proposed by (Zügner et al., 2018). In Fig. 4 we show that this constraint does not significantly limit the destructive performance of our attacks. Thus we conclude that these constraints should always be enforced, since they improve unnoticeability while at the same time our attacks remain effective.

heading: E ATTACKS WITH CHANGES TO THE NODE FEATURES

text: While the focus of our work is poisoning attacks by modifying the graph structure, our method can be applied to node feature attacks as well. The most straightforward case is when the node features are binary, since then we can use the same greedy algorithm as for the graph structure (ignoring the degree distribution constraints). Among the datasets we evaluated, CITESEER has binary node features, hence in Table 7 we display the results when attacking both node features and graph structure (while the total number of perturbations stays the same). We can observe that the impact of the combined attacks is slightly lower than the structure-only attack. We attribute this to the fact that we assign the same cost to structure and feature changes, but arguably we expect a structure perturbation to have a stronger effect on performance than a feature perturbation. Future work can provide a framework where structure and feature changes impose a different cost on the attacker. When the node features are continuous, there also needs to be some tuning of the meta step size and considerations whether multiple features per instance can be changed in a single step.

heading: F ADDITIONAL RESULTS

text: In this section we present additional results of our experiments. In Table 8 we see that our heuristic is successful at attacking PUBMED, a dataset with roughly 20K nodes. Tables 9 and 10 show misclassification rates with 1% and 10% perturbed edges, respectively. Table 11 displays results when training the surrogate model for T = 10 iterations to obtain the (meta) gradients. Finally, Figures 5 through 12 show how the respective models’ classification accuracies change for different attack methods and datasets.