summaries: The paper develops an information-theoretic training scheme for Variational Auto-Encoders (VAEs). This scheme is tailored for addressing the well-known disentanglement problem of VAEs where an over-capacity encoder sometimes manages to both maximize data fit and shrink the KL divergence between the approximate posterior and prior to zero. Consequently, the latent representations of the observations become independent, making them unusable for any downstream task.

summaries: Overview: This paper describes the Variational InfoMax AutoEncoder (VIMAE), which is based on the learning principle of the Capacity Constrained InfoMax. The core idea behind VIMAE is that the encoding information is not bounded while network capacity is. The issue that VIMAE can handle, and where VAE fails, is that representations are not informative of input data, due to the information bottleneck idea that VAE is built upon. The authors describe InfoVAE and β-VAE, which both attempt to solve this problem. The theory behind VIMAE is then described and tested against VAE and β-VAE, in their abilities to evaluate the entropy of Z, in reconstruction and generative performance, and in robustness to noise and generalization.

summaries: I went over this work multiple times and had a really hard time judging the novelty of this work. The paper seems to be a summary of existing work reinterpreting variational autoencoding objectives from an information theoretic standpoint. In particular, the paper seems to follow the same analysis as in Wasserstein Autoencoders (Tolstikhin et al., 2017) and InfoVAE (Zhao et al., 2017).  It is unfair to say that the objectives were "derived independently" since these works are from a couple of years ago.

abstractText: The Variational AutoEncoder (VAE) can learn simultaneously a representation and a generative model, but often, in order to generate sharper samples, a useless representation is learnt. Starting from the observation that a meaningful representation is an informative one, in this work we analyse the VAE from an information theoretic perspective. We define the concept of capacity for the variational network, and we associate the two tasks of VAE: generation and representation quality, to two information properties of the network: information of the generative model and capacity of the network. Then we suggest that an optimal generative model is the one optimising the Capacity-Constrained InfoMax (CCIM), a theoretical objective learning the maximal informative generative model while maintaining bounded the network capacity. The theoretical assumptions are confirmed by the computational experiments, where between the different families of VAE, the one optimising a variational lower bound of the CCIM generates sharper samples and learns a clustered and robust representation. We call this the Variational InfoMax AutoEncoder (VIMAE).

authors:
Alessandro Achille
Tom Eccles
Loic Matthey
Chris Burgess
Nicholas Watters
Alexander Lerchner
Irina Higgins

title: Life-long disentangled representation learning with cross-domain latent homologies

venue: In Advances in Neural Information Processing Systems,

authors:
Alexander A Alemi
Ian Fischer
Joshua V Dillon
Kevin Murphy

title: Deep variational information bottleneck

venue: arXiv preprint arXiv:1612.00410,

authors:
Alexander A Alemi
Ben Poole
Ian Fischer
Joshua V Dillon
Rif A Saurous
Kevin Murphy

title: Fixing a broken elbo

venue: arXiv preprint arXiv:1711.00464,

authors:
Pierre Baldi
Kurt Hornik

title: Neural networks and principal component analysis: Learning from examples without local minima

venue: Neural networks,

authors:
Anthony J Bell
Terrence J Sejnowski

title: The independent components of natural scenes are edge filters

venue: Vision research,

authors:
Yoshua Bengio
Aaron Courville
Pascal Vincent

title: Representation learning: A review and new perspectives

venue: IEEE transactions on pattern analysis and machine intelligence,

authors:
Christopher P Burgess
Irina Higgins
Arka Pal
Loic Matthey
Nick Watters
Guillaume Desjardins
Alexander Lerchner

title: Understanding disentangling in β-vae

venue: arXiv preprint arXiv:1804.03599,

authors:
Xi Chen
Diederik P Kingma
Tim Salimans
Yan Duan
Prafulla Dhariwal
John Schulman
Ilya Sutskever
Pieter Abbeel

title: Variational lossy autoencoder

venue: arXiv preprint arXiv:1611.02731,

authors:
Laurent Dinh
Jascha Sohl-Dickstein
Samy Bengio

title: Density estimation using real nvp

venue: arXiv preprint arXiv:1605.08803,

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

title: Generative adversarial nets

venue: In Advances in neural information processing systems,

authors:
Aditya Grover
Stefano Ermon

title: Uncertainty autoencoders: Learning compressed representations via variational information maximization

venue: arXiv preprint arXiv:1812.10539,

authors:
Irina Higgins
Loic Matthey
Arka Pal
Christopher Burgess
Xavier Glorot
Matthew Botvinick
Shakir Mohamed
Alexander Lerchner

title: beta-vae: Learning basic visual concepts with a constrained variational framework

authors:
Geoffrey E Hinton
Simon Osindero
Yee-Whye Teh

title: A fast learning algorithm for deep belief nets

venue: Neural computation,

authors:
Aapo Hyvärinen
Jarmo Hurri
Patrick O Hoyer

title: Natural image statistics: A probabilistic approach to early computational vision., volume 39

venue: Springer Science & Business Media,

authors:
Sergey Ioffe
Christian Szegedy

title: Batch normalization: Accelerating deep network training by reducing internal covariate shift

venue: arXiv preprint arXiv:1502.03167,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Diederik P Kingma
Max Welling

title: Auto-encoding variational bayes

venue: arXiv preprint arXiv:1312.6114,

authors:
Durk P Kingma
Shakir Mohamed
Danilo Jimenez Rezende
Max Welling

title: Semi-supervised learning with deep generative models

authors:
Durk P Kingma
Tim Salimans
Rafal Jozefowicz
Xi Chen
Ilya Sutskever
Max Welling

title: Improved variational inference with inverse autoregressive flow

title: An application of the principle of maximum information preservation to linear systems

authors:
Ziwei Liu
Ping Luo
Xiaogang Wang
Xiaoou Tang

title: Deep learning face attributes in the wild

venue: In Proceedings of the IEEE international conference on computer vision,

authors:
Chris J Maddison
John Lawson
George Tucker
Nicolas Heess
Mohammad Norouzi
Andriy Mnih
Arnaud Doucet
Yee Teh

title: Filtering variational objectives

authors:
Emile Mathieu
Tom Rainforth
Siddharth Narayanaswamy
Yee Whye Teh

title: Disentangling disentanglement

venue: arXiv preprint arXiv:1812.02833,

authors:
Alec Radford
Luke Metz
Soumith Chintala

title: Unsupervised representation learning with deep convolutional generative adversarial networks

venue: arXiv preprint arXiv:1511.06434,

authors:
Jason Ramapuram
Magda Gregorova
Alexandros Kalousis

title: Lifelong generative modeling

venue: arXiv preprint arXiv:1705.09847,

authors:
Danilo Jimenez Rezende
Shakir Mohamed

title: Variational inference with normalizing flows

venue: arXiv preprint arXiv:1505.05770,

authors:
Danilo Jimenez Rezende
Shakir Mohamed
Daan Wierstra

title: Stochastic backpropagation and approximate inference in deep generative models

venue: arXiv preprint arXiv:1401.4082,

authors:
Salah Rifai
Grégoire Mesnil
Pascal Vincent
Xavier Muller
Yoshua Bengio
Yann Dauphin
Xavier Glorot

title: Higher order contractive auto-encoder

venue: In Joint European Conference on Machine Learning and Knowledge Discovery in Databases,

authors:
Andrew Michael Saxe
Yamini Bansal
Joel Dapello
Madhu Advani
Artemy Kolchinsky
Brendan Daniel Tracey
David Daniel Cox

title: On the information bottleneck theory of deep

authors:
Naftali Tishby
Fernando C Pereira
William Bialek

title: The information bottleneck method

venue: arXiv preprint physics/0004057,

authors:
Pascal Vincent
Hugo Larochelle
Yoshua Bengio
Pierre-Antoine Manzagol

title: Extracting and composing robust features with denoising autoencoders

venue: In Proceedings of the 25th international conference on Machine learning,

authors:
Oriol Vinyals
Charles Blundell
Timothy Lillicrap
koray kavukcuoglu
Daan Wierstra

title: Matching networks for one shot learning

authors:
Shengjia Zhao
Jiaming Song
Stefano Ermon

title: Infovae: Information maximizing variational autoencoders

venue: arXiv preprint arXiv:1706.02262,

heading: 1 INTRODUCTION

text:
A common assumption in machine learning is that any visible data x ∈ X is completely described by some generative factor o, living in a smaller hidden space O, i.e. x = g(o) with g a (possibly stochastic) generative function. The aim of unsupervised representation learning research is to find a representation z of the generative factor o living in a known space Z describing, as well as o, the visible data x. This is particularly relevant because the learnt small representation z is task agnostic and, in principle, can be used as input for networks performing different tasks, leading to faster and more robust learning (generalisation property), (Rifai et al., 2011).
Many models fφ : X → Z trying to learn such representations have been proposed (Dinh et al., 2016; Hinton et al., 2006; Maddison et al., 2017; Radford et al., 2015), but recently in order to solve this problem it was proposed to consider a dual problem: define a priori z and find a generator map gθ, such that for any z, gθ(z) is an element of X . In particular, two families of probabilistic generative models have become dominant: Variational AutoEncoder (VAE) (Kingma & Welling, 2013; Rezende et al., 2014) and Generative Adversarial Network (GAN) (Goodfellow et al., 2014). The common idea of the two approaches is that a good generator pθ(x|z) is the one able to generate the data that is as close as possible to the visible one, i.e. that with respect a certain metric D, the distance between the marginal pθ(x) = Ep(z)[pθ(x|z)] and the visible distribution pD(x) is minimal. In this manuscript we restrict our attention to the VAE model, since by its architecture, it is the only one where the learnt representation, possibly from different datasets, can be used as input for networks performing different tasks, (Achille et al., 2018; Ramapuram et al., 2017). Although VAE, by its training robustness and general good generative performance is the most popular model for representation learning, in particular cases it suffers from the uninformative representation issue: the representation is entangled and the generative model tends to be independent of z, i.e. pθ(x|z) ≈ pθ(x). As highlighted in the next section such behaviour is intrinsic in the variational loss, the Evidence Lower BOund (ELBO), encouraging a less informative representation.
Following the direction suggested in (Alemi et al., 2017; Zhao et al., 2017) we describe the VAE from an information theoretic perspective. Such description lead us to two observations: the WAE (Tolstikhin et al., 2017) and InfoVAE (Zhao et al., 2017) models are actually maximising a lower bound of the mutual information associated to a generator pθ(x|z) belonging in a certain family
P , the Variational InfoMax (VIM); and given that the capacity of the network is a function of the entropy of the prior p(z), the VIM is the variational expression of the Capacity-Constrained InfoMax (CCIM). Following the analogies between the CCIM and the Information Bottleneck (IB), the theoretical principle associated with the ELBO, we deduce that the representation quality is associated to the capacity term.
The theoretical arguments are confirmed by the performed experiments where we observe that, differently from what was argued in previous works (Higgins et al., 2017; Burgess et al., 2018), it is possible to train a model that is able to learn good (able to generalise) representations while maintaining optimal generative performance. The main contributions of the paper are summarised in the following points:
• derivation of a variational lower bound for the maximal mutual information of a generaive model belonging in a certain family, see equation 7;
• definition and bounds estimation for the network capacity for a variational autoencoder, see equation 9;
• association of the two main properties of VAE, generation quality and good representation, to two different information concepts, respectively Mutual Information and network capacity;
• proposal of a new learning principle for unsupervised models: the Capacity-Constrained InfoMax, see equation 10, that allows both to learn a good representation while maintaining optimal generative performance.
The work is divided as follows: in the second section we describe briefly the VAE and its variants; in the third and fourth sections we describe the variational infomax method and related work. We conclude the paper with the experimental results and the final observations.

heading: 2 BACKGROUND

text: The aim of this section is to describe VAE, understand principal issues of the ELBO objective and describe the three most relevant approaches to overcome such issues.

heading: 2.1 NOTATION AND PRELIMINARY DEFINITIONS

text:
We use calligraphic letters (i.e. X ) for sets, capital letters (i.e. X) for random variables, and lower case letters (i.e. x) for their samples. With abuse of notation we denote both the probability and the corresponding density with the lower case letters (i.e. p(x)).
KL divergence Given two random distributions p(x) and q(x), the Kullback-Leibler (KL) divergence
DKL(p(x)||q(x)) = ∫ log (p(y) q(y) ) p(y)dy (1)
is an (intuitive) measure of the distance between the distributions p and q.
Mutual Information and Capacity Given a channel Z → X with X and Z random variables, jointly distributed according to p(x, z) and with marginals p(x) and p(z). The mutual information
I(X,Z) = DKL(p(x, z)||p(x)p(z)),
is a measure of the reduction of uncertainty in X due to the knowledge of Z, and the capacity
C(X,Z) = sup p(z)∈P I(X,Z)
is the maximal information that can be shared for a fixed generator p(x|z).

heading: 2.2 VARIATIONAL AUTOENCODER

text:
From now on let us assume that the unknown distribution of the data p(x) coincides with the empirical one pD(x), and that the distribution of the latent representation p(z) is known. In this context the VAE is a model solving the following optimisation problem: find the generative model pθ(x, z) ∈ Pθ, specified by the parameters θ of the associated neural network, maximising the ELBO objective
ELBOθ,φ = Ep(x)[−DKL(qφ(z|x)||p(z)) + Eq(z|x)[log p(x|z)]], (2)
a lower bound of the unfeasible-to-compute marginal likelihood Ep(x)[log pθ(x)]. The ELBO objective is optimised by a regularised autoencoder, with encoder and decoder parametetrising, respectively, the inference and generative distributions, qφ(z|x) and pθ(x|z), with φ ∈ Φ, θ ∈ Θ and regulariser defined by the rate term DKL(qφ(z|x)||p(z)), measuring the excess number of bits required to encode samples from the encoder using the optimal code designed for p(z).

heading: 2.3 UNINFORMATIVE REPRESENTATION ISSUE

text:
As underlined in the introduction, the main issue of VAE is that the representations are not really informative of the input data and in the worst case, it is learned a Z-independent generative model pθ(x|z) = pθ(x). Such issues are intrinsic in the ELBO objective, equation 2, that can reach the optimum when DKL(qφ(z|x)||p(z)) = 0 (Zhao et al., 2017). The latter case means that the representation is completely uninformative, indeed the rate term, which can be rewritten as
DKL(qφ(z|x)||p(z)) = Iq(X,Z) +DKL(qφ(z)||p(z)),
is a penalty on the encoding information, and is zero when Iq(X,Z) = 0, with qφ(z|x) = qφ(z) = p(z), i.e. when qφ does not encode any information about the input x.
We now describe the three most relevant models that try to overcome the uninformative representation issue.
InfoVAE In (Zhao et al., 2017) the InfoVAE family of models was proposed, a generalisation of the VAE model optimising the objective
−αIq(X,Z)− λDKL(qφ(z)||p(z)) + Ep(x)[Eq(z|x)[log p(x|z)]],
with α and λ two real positive hyper-parameters.
The main advantage of this definition is that it is possible to consider separately the two components of the rate term. In particular, in (Zhao et al., 2017) it was observed that by eliminating the information penalty (α = 0), the generative performance of the model improves and the representation results are more informative.
β-VAE In (Higgins et al., 2017), starting from the observation that the optimal case is rare, but most of the learned features by VAE are not disentangled, it is proposed an opposite approach: put a high penalty to the rate term, in order to constrain the model to learn the most informative property of the data, and then have a disentangled representation of the data. The β-VAE family is a particular case of InfoVAE where α = λ 1. This idea, that at first sight looks counter-intuitive, is based on the observation that by the additive property of the KL-divergence
DKL(qφ(z|x)||p(z)) = dim(Z)∑ i=1 DKL(qφ(zi|x)||p(zi)) (3)
pushing the penalty associated with the rate is equivalent to penalising the informativeness of most features, leaving few features containing the relevant information. Starting from a bits-back coding argument, a similar conclusion was derived in (Chen et al., 2016).
Minimal rate bound In order to avoid the null rate issue, and maintain semantic informative representation, in (Alemi et al., 2017) was suggested to optimise the following variant of ELBO:
Ep(x)[Eq(z|x)[log p(x|z)]]− β|R0 −DKL(qφ(z|x)||p(z))|, (4)
where R0 > 0, defines both the lower bound of the rate and the upper bound of the encoding information Iq(X,Z). If, as we will see below, the objective in equation 4 is a generalisation of both InfoVAE (R0 = maxθ Iθ(X,Z)) and β-VAE (R0 = 0), the correct R0 is unknown and its optimisitation is not an easy task.

heading: 3 THE MODEL

heading: 3.1 THE VARIATIONAL INFOMAX

text:
Assuming the distribution associated to the two random variables p(x) and p(z) is known, the InfoMax objective is defined as: find the joint distribution pθ(x, z) ∈ Pθ := {pθ(x, z) : Ep(z)[pθ(x|z)] = p(x), Ep(x)[pθ(z|x)] = p(z)} maximising the mutual information Iθ(X,Z) = DKL(pθ(x, z)||p(x)p(z)), i.e. find θ∗ ∈ Θ s.t. Iθ∗ ≥ Iθ for any θ ∈ Θ. Since the definition via KL divergence is computationally intractable, it is necessary to re-write the mutual information as Iθ(X,Z) = hθ(X)− hθ(X|Z), (5) where hθ(X) = −Epθ(x)[log pθ(x)] is the entropy of X , and hθ(X|Z) = −Epθ(x,z)[log pθ(x|z)] is the conditional entropy hθ(X|Z). Since pθ(x, z) ∈ Pθ the entropy hθ(X) = h(X) is constant, and in order to maximise the mutual information it is sufficient to minimise the conditional entropy.
Excluding some special cases (Bell & Sejnowski, 1997), minimising the conditional entropy is unfeasible, so it is necessary to consider an associated variational problem: for any qφ(z|x) such that qφ(z) = p(z) and φ ∈ Φ = Θ, learn the generative model pθ(x|z) minimising the reconstruction accuracy term Ep(x)[Eqφ(z|x)[log(pθ(x|z))]]. Indeed, the following variational objective:
Iθ,φ(X,Z) = h(X) + Ep(x)Eq(z|x)[log pθ(x|z)] s.t. qφ(z) = p(z) (6)
is a lower bound of Iθ∗(X,Z) and is maximal when q(z|x) = pθ(z|x) = pθ∗(z|x), (see the Appendix).
Unfortunately, the formulation in equation 6 is still unfeasible to compute, because it requires that qφ(z) = p(z), but by the butterfly architecture of the autoencoder, qφ(z) tends to be uniformly distributed on the space Z . For this reason, the model is trained maximising the following relaxed form: V IMθ,φ = Ep(x)Eq(z|x)[log pθ(x|z)]− λD(qφ(z)||p(z)), (7) where it is introduced a term D(qφ(z)||p(z)) encouraging the empirical distribution qφ(z) to be close, according to the metric D, to p(z). In the following we assume D = DKL, and in order to avoid any confusion the variational autoencoder trained maximising equation 7 will be dubbed VIMAE.
Encoding channel In VAE we observed that an uninformative representation was caused by the non-informativeness of the encoding map qφ(z|x). Since from equation 7 it is not clear how qφ(z|x) behaves, we consider an equivalent representation, (see the Appendix):
V IMθ,φ = −DKL(p(x)||pθ(x))− (λ− 1)DKL(qφ(z)||p(z)) + Iθ,φ(X,Z). (8)
From equation 8 we see that the infomax objective, equation 7, can be read as a composition of three sub-objectives: find a generative model pθ(x|z), with marginal resembling the visible distribution p(x) (first term); maximise the (unbounded) variational mutual information (third term); and learn an inferred distribution qφ(z, x) close to the generative model pθ(x, z). Then the optimum is obtained by qφ(x, z) = pθ(x, z) such that Iθ(X,Z) is maximal, confirming the validity of the approximation made above.

heading: 3.2 CHANNEL CAPACITY

text:
In a channel with variational mutual information Iθ,φ as defined in equation 6 the (variational) capacity Cθ,φ(X,Z), is defined as
Cθ,φ(X,Z) = sup θ,φ,p(z)∈P Iθ,φ(X,Z). (9)
If P is the space of all distributions on Z , the capacity of the network coincides with the variational mutual information of the model trained minimising only the reconstruction loss. In the latter case, as observed above, it is not guaranteed to learn the generator with pθ(z) = p(z). This is because, given two equally informative generative models pθ(x|z) and pθ′(x|z), with encoder respectively qφ(z|x) and qφ′(z|x), with h(qφ(z)) < h(qφ′(z)), then Iθ,φ < Iθ′,φ′ . From such observation we deduce that bounding the entropy of the representation Z is the way to bound the capacity without penalising the encoding information, and that the penalty introduced in equation 7 is actually a bound to the capacity itself. So, the VIM objective can be defined as a variational approximation of the Capacity-Constrained InfoMax:
max Z∈Z
I(X,Z)− λC(X,Z), (10)
which given a set of equally informative generators, learns the one having the minimal capacity. The idea of the CCIM is similar to the idea of the IB, from which was derived the β-VAE: constrain the capacity of the network in order to learn only the relevant features of the input data. The difference with the IB,
max Z∈Z
I(X,Z)− λIq(X,Z) (11)
lies in the second term: the network capacity instead of the encoding information. This choice allows the network to learn a good representation (small capacity) while maintaining good generative performance (high mutual information). Indeed, as shown in equation 8, the generative performance is associated to the informativeness of qφ(z|x) and pθ(x|z). In order to test the assumption that it is sufficient to bound the entropy of Z, instead of the encoding mutual information, to learn a good representation, in the experiments (see below) we consider the cases Z is Normal (VIMAE-n) or Logistic (VIMAE-l) distributed. We choose to compare the popular Normal distribution with the Logistic one for two reasons: the Logistic has less entropy than a Gaussian distribution and because it is a common assumption in natural science to suppose that the hidden factors of the visible data are logistically distributed (Hyvärinen et al., 2009).
Entropy vs Rate According to what written above the choice of the distribution p(z) is a way to bound the maximal information Iθ of the generative model as well as R0 in equation 4, indeed, if we choose R0 = C(X,Z) the theoretical solutions of equation 4 and equation 7 coincide. Although the two approaches are similar, both defines a target Iθ for the generator pθ(x|z), they differ in one fundamental aspect: the ratio between the information Iθ and network capacity C. For any given choice of the prior p(z) the generative model maximising VIM is the one with Iθ = C, instead for any R0 < C the information Iθ associated to the generative model learned, by equation 4, coincides with R0, i.e. Iθ = R0 < C. That implies an high sensitivity to the hyper-parameter R0 for the model in equation 4. In fact, as suggested in (Mathieu et al., 2018), a ratio Iθ/C ≈ 1, guarantees an appropriate level of overlap in the latent space between latent encoding, and then a better representation quality.

heading: 4 RELATED WORK

text:
Autoencoder literature Autoencoder models are one of the most used family of neural networks to extract features in an unsupervised way (Bengio et al., 2013), and their relationship with Information Theory is well-established from the first unregularised autoencoders (Baldi & Hornik, 1989). The classical unregularised autoencoders, minimising the reconstruction loss Ep(x)[Eqφ(z|x)[− log pθ(x|z)]], are maximising an unbounded information, i.e. they are looking for a solution in the space P̃θ = {pθ : pθ(x) = p(x)}. In general, a solution in this wide space is good only for reconstruction performance because Z contains all the possible information that can be stored in the space Z , and is not robust to input noise (Vincent et al., 2008); but, as observed in (Grover & Ermon, 2018), if qφ(z|x) ∼ N (µ(x), σ(x)) the model pθ(x|z) is robust to noise and is a Gaussian generator. In this context the uninformative issue is avoided, but the price to pay is the impossibility to sample directly from a prior p(z) that is not defined; indeed, the model described in (Grover & Ermon, 2018) requires running relatively expensive Markov Chain to obtain samples.
Many regularised models have been proposed, but the most well known is VAE, that minimises the expected code length of communicating x. As we observed in the previous sections, it is not
guaranteed that the method finds a useful representation. Such issue can be solved both controlling the information of the model, or considering a more flexible prior p(z),(Rezende & Mohamed, 2015; Kingma et al., 2016; Dinh et al., 2016). In this manuscript we do not consider the latter approach, because by the model structure, it requires quite expensive computation (autoregressive models are necessary) and because the learned representation is not suitable for task different than the generation such as lifelong context, for which the standard VAE is used with success (Achille et al., 2018).
The objective in equation 7 was firstly derived in (Tolstikhin et al., 2017) and (Zhao et al., 2017). Particularly relevant is the derivation in (Tolstikhin et al., 2017) because it allows us to describe an informative model pθ(x, z) as the one minimising the transport cost between the original and generated data.
Finally, we underline that in case we wish to consider a Jensen-Shannon divergence in equation 7 it is necessary to consider an adversarial network model, discriminating the true samples z ∼ p(z) from the fake sampled by qφ(z) (Goodfellow et al., 2014). In the latter case the obtained model is equivalent to the Adversarial AutoEncoder (Makhzani et al., 2015). We conclude by remarking that in all the cases cited above the Infomax objective was never maximised using a prior p(z) different from a Gaussian.
Information theoretic literature Information theory is strongly related with neural networks, and not only with autoencoders. Originally the InfoMax objective was applied to a self-organised system with a single hidden layer, (Bell & Sejnowski, 1997; Linsker, 1989) where the bound in the capacity was given by the numbers of hidden neurons. More recently, the (naive) InfoMax has given way to a new information-theoretic principle: the Information-Bottleneck (Tishby et al., 2000). The idea of this principle is that a feed-forward neural network trained for task T tends to learn a minimal sufficient representation of the data, maximising the following objective:
max Z
I(Z, T )− βI(X,Z). (12)
Although it was shown that in the general case this principle does not hold true (Saxe et al., 2018), the principle was used as a regularisation technique with success both in unsupervised (Alemi et al., 2017; Higgins et al., 2017) and supervised (Alemi et al., 2016) settings. We observe that the VIM, equation 7, and IB, equation 12, coincide in the case of a deterministic encoder, where the encoding information is the entropy of Z.

heading: 5 EXPERIMENTS

text:
Here we empirically evaluate the VIMAE. The section is divided into three parts: in the first part we compare the ability of the described models to infer the representation, z ∼ N (0, I). Such an experiment is to evaluate the entropy of Z ∼ q(Z) and then, as observed in section 3.2, an indirect way to estimate capacity of the network (C(X,Z) ∝ h(Z)). In the second part we evaluate the reconstruction and generative performance of the models. Indeed, the combination of the two tasks is estimation of the mutual information of the generative model Iθ(X,Z), see equation 8.
In the third part we evaluate the robustness to noise and generalisation property of the learnt representation, observing that an informative model with small capacity is the best one for these tasks.
In all the described experiments, the divergence DKL(q(z)||p(z)) in equation 7 is approximated via the Maximum Mean Discrepancy (Zhao et al., 2017) defined as:
MMD(q(z), p(z)) = sup f :‖f‖Hk≤1 Ep(z)[f(Z)]− Eq(z)[f(Z)] (13)
where Hk is the Reproducing Kernel Hilbert Space associated to a positive definite kernel k(·, ·) : Z×Z → R+. Moreover, by difficulties to compute the objective equation 4, as suggested in (Alemi et al., 2017) we decided to optimise a β-VAE, denoted βA-VAE, with β < 1; in order to avoid any confusion, the original version proposed in (Higgins et al., 2017) with β 1 will be renamed βH -VAE.

heading: 5.1 THE ENTROPY OF Z

text:
Experiments in this part are performed with an autoencoder trained with the MNIST data-set, a collection of 70k monocromatic handwritten digits, where both the inference and generative distribution are modelled by 3-layer deep neural nets with 256 hidden units in each layer and Z = R2. From the 2d hidden distribution learnt by the different methods in figure 1, we observe that the ELBO-based models are not able to learn a distribution q(z) that is close to the prior p(z); and, as we will see in the following experiments, βH -VAE, the only ELBO-model having comparing results to the VIMAE, has to penalise drastically the decoding information.
Thanks to this experiment we see that, in general, the ELBO-based models are not seeking for a small capacity network, since h(q(z)) h(p(z)), and that the divergence penalty introduced in equation 7 is a bound for the entropy h(q(z)), and then of the channel capacity C.

heading: 5.2 THE MODEL INFORMATION

text:
The experiments in these final sections were performed with the same settings and autoencoder models used in (Tolstikhin et al., 2017), an architecture similar to the DCGAN (Radford et al., 2015) with batch normalization (Ioffe & Szegedy, 2015) (more details given in the Appendix). We consider four data-sets: MNIST and CIFAR10, two standard data-sets with ground-truth labels; Omniglot, a data-set of 1623 characters from 50 alphabets, 30 training and 20 evaluation, where each character appears 80 times, to evaluate the informativeness of the model and the quality of the learned representation; in the Appendix, we also consider CelebA (Liu et al., 2015), consisting of roughly of 203k faces of 64 × 64 resolution, in order to compare the generative quality of the pictures. After considering many parameters for βH , βA and λ, we choose, in accordance with what was suggested in (Tolstikhin et al., 2017), βH = λ = 10, and βA = 0.2 for MNIST and Omniglot and β = λ = 100 and βA = 0.4 for CelebA and CIFAR10 experiments.
The goal of this section is to evaluate the informativeness of the learnt generative model pθ(x|z). From what was described above, the reconstruction loss or the generation quality alone are not reliable metrics, because the reconstruction loss is an estimation of the variational mutual information Iθ,φ(X,Z), and the generation quality is an estimation of DKL(pθ(x)||p(x)) that, as observed in section 2.3, it is possible to minimise with an uninformative generator. But, according to equation 8 the combination of the two task performances is a good empirical estimation of Iθ(X,Z); indeed, by generative experiments, we require that q(z) = p(z), so the KL divergence term in equation 8 comes for free.
Reconstruction and generative performances According to what was asserted above, we observe from figure 2 (top) and figure 3 that an high penalty on the rate term (small encoding information) in the ELBO based model coincides with poor reconstruction. Indeed, the βH -VAE, is the one with worst reconstruction, and instead βA-VAE is the model that behaves similarly to VIMAE, that is optimising an encoding information-free objective. Such behaviour is consistent with the rate term associated to each model, see caption of each figure, where we observe that VIMAE, have the highest rate and in particular this is twice the one associated to βA-VAE, confirming that VIMAE learns a maximal informative decoder, and that βA-VAE is only theoretically analogous to VIMAE.
The models that we are considering are defined as generative models, so giving a sample z ∼ p(z) they should be able to generate a new data x similar to the original one. As we observe from the
generated samples of Omniglot in figure 2 (bottom) and Negative LogLikelihood (NLL) listed in table 1, both VAE and βH -VAE do not generate good samples, confirming that sharper samples are associated to informative generators. Such qualities on Omniglot are confirmed by the experiments with the CIFAR10 and CelebA data-set (Liu et al., 2015), see the Appendix, where it is observed that if the generative difference between the two VIMAEs is small, the difference with the VAE counterparts is high. Such behaviour is in agreement with what was observed until now: the ELBO based model does not learn a good generative network, and the good reconstruction is simply associated to a large entropy of Z, (encoding information) instead of an informative generative model pθ(x|z).
Table 1: NLL for generated samples on Omniglot (smaler is better)
Method NLL
VAE 1224 βH -VAE 1254 βA-VAE 1228 VIMAE-n 1190 VIMAE-l 1223
Similar experiments were conducted with the MNIST dataset and are discussed in the appendix.

heading: 5.3 GENERALISATION PROPERTY

text:
We defined a good representation as the one containing the relevant properties of the visible data and able to generalise from the task for which was trained. In order to evaluate such quality, following the approach proposed in (Rifai et al., 2011), we evaluate the accuracy of an SVM directly trained on the learned features of the data. Proceeding as in (Zhao et al., 2017), we train the M1+TSVM (Kingma et al., 2014) and use the semi-supervised performance over 1000 (100 for Omniglot) samples as an approximate metric to verify the relevance and the quality of the learned representation. In order to evaluate the robustness of the learned features, we performed the same algorithm on the representation associated to corrupted data, i.e. z ∼ q(z|x+ν), considering two types of noise: Gaussian and mask. In the Gaussian case, we add to each pixel a ν value sampled from N (0, σ2) with σ ∈ {0.2, 0.3, 0.4}, and in the masking
Table 3: Semi-supervised classification, MNIST.
accuracy (%)
Method ν = 0 ν = N (0, σ2) ν = B(p) 0.2 0.4 0.2 0.5
VAE 80 77 70 72 52 βH -VAE 92 86 82 91 84 βA-VAE 93 66 13 85 65 VIMAE-n 93 92 86 92 86 VIMAE-l 93 92 88 92 87
Table 4: Semi-supervised classification, Omniglot (random sampling: 20%).
accuracy (%)
ν = 0 ν = N (0, σ2) ν = B(p) 0.2 0.4 0.2 0.5
22 22 17 22 16 21 21 22 19 17 22 22 21 21 24 22 23 24 22 22 24 23 20 23 22
case a fraction ν of the elements is forced to be 0: each pixel is masked according to a Bernoulli distribution B(p), p ∈ {0.2, 0.5}. Higher classification performance suggests that the learned representation contains the relevant information and, in case of corrupted input data, that it is robust. In the Omniglot case by the challenge of the task (the test alphabet was never seen in the training) we consider a 5-character data-set, split into 300 (60× 5) for training and 100 for evaluation. From the classification scores listed in tables 2- 4, we see that the ELBO-based model learnt good representations for clean data, but not when corrupted data is given as input. This is particularly clear in the Bernoulli case, that is a noise different from the one seen in the training. Particularly relevant is the behaviour of the two VIMAEs: they are comparable in the cases of clean data and small noise, but the one with big capacity, VIMAE-n, suffers in large noise, while the one with small capacity, VIMAE-l, is the most robust and in some challenging cases, see table 2, the noise helps to improve the model accuracy. Such a result is consistent with the idea that a small capacity network is learning the relevant factors of the input data, that are the only ones robust to the input noise.

heading: 6 CONCLUSION

text:
We observe, via an information theoretic description of VAE, that it is possible to learn a good generative model while maintaining a meaningful hidden representation, and that goal can be reached by optimising the CCIM, an objective that separates out the two properties of a network: the generative information and its capacity. We compare both theoretically and computationally the CCIM objective with the IB and its variation (Alemi et al., 2017), observing that the CCIM optimal solution, in particular cases, coincides with the IB one, but that in the practical case the difference is substantial.
Future work includes the extension of the VIMAE model to a lifelong task, a scenario where it is necessary to learn both an informative representation while maintaining bounded the capacity of the network, in order to avoid the catastrophic forgetting issue (Achille et al., 2018).

heading: RELATIONSHIP BETWEEN ENCODING, DECODING AND VARIATIONAL INFORMATION

text:
Defined q(z, x) := qφ(z|x)p(x) the encoding distribution and pθ(x, z) := pθ(x|z)p(z) the decoding one. The encoding Iq(X,Z), decoding Iθ(X,Z) and the variational Iθ,φ(X,Z) information are defined respectively:
Iq(X,Z) = DKL(q(z, x)||q(z)p(x)) = h(X)− hq(X|Z) Iθ(X,Z) = DKL(pθ(z, x)||p(z)p(x)) = h(X)− hθ(X|Z)
Iθ,φ(X,Z) = h(X)− Eq(z,x)[− log pθ(x|z)]
Assuming θ∗ ∈ Θ is the parameter associated to the maximal decoding information, Iθ(X,Z) ≤ Iθ∗(X,Z) for any θ ∈ Θ, it follows that for any qφ(x, z) ∈ Pθ, i.e. for any qφ(z) = Ep(x)[qφ(x|z)] = p(z) and φ ∈ Φ ⊂ Θ,
Iθ∗(X,Z) ≥ Iq(X,Z).
Then a lower bound of Iq is a lower bound of Iθ∗ . By property of KL-divergence we have that for any pθ(x|z) the following relationship holds:
Eq(z,x)[− log pθ(x|z)] = hq(X|Z) + Eq(z)[DKL(qφ(x|z)||pθ(x|z))] (14)
From equation 14 and the definition of the variational information Iθ,φ we deduce that:
Iθ∗(X,Z) ≥ Iq(X,Z) ≥ Iθ,φ(X,Z)
We conclude observing that if Θ = Φ, at optimum the three information terms above are equal, and then qφ(x, z) = pθ(x, z).
Observation: If Φ ⊂ Θ, the variational mutual information can be at most equal to Iq∗ , the maximal Iq , but it is not guaranteed that Iq∗ = Iθ∗ .

heading: DERIVATION OF EQUATION 8

text:
In (Zhao et al., 2017), it is observed that equation 7 can be written as follows:
V IMθ,φ =−DKL(p(x)||pθ(x))− Ep(x)[DKL(qφ(z|x)||pθ(z|x))]− − (λ− 1)DKL(qφ(z)||p(z)) + Iq(X,Z).
From equation above, to verify that equation 8 is correct, it is sufficient to show that
Iθ,φ(X,Z) = Iq(X,Z)− Ep(x)[DKL(qφ(z|x)||pθ(z|x))]. (15)
The equation 15 follows by the property of the autoencoder and equation 15.
More precisely, by equation 14 we have that
Iθ,φ(X,Z) = Iq(X,Z)− Eq(z)DKL(qφ(x|z)||pθ(x|z))
and, by AutoEncoder architecture, as observed in section 3, pθ(z) = Ep(x)[pθ(z|x)] = q(z). Then the following equation holds
Eq(z)DKL(qφ(x|z)||pθ(x|z)) = Ep(x)DKL(qφ(z|x)||pθ(z|x)).
Indeed, Eq(z)DKL(qφ(x|z)||pθ(x|z)) = ∫ q(z) ∫ q(x|z) log q(x|z)
pθ(x|z) dxdz
= ∫ ∫ q(x)q(z|x) log q(x|z)q(z)
pθ(x|z)(z) dxdz =
∫ p(x) ∫ q(z|x) log q(z|x)
pθ(z|x) dxdz =
= Ep(x)DKL(qφ(z|x)||pθ(z|x)).

heading: FURTHER DETAILS ON EXPERIMENTS

text: In all the experiments in section 5.2 we considered the latent space Z = Rd, for all the models we choose the prior p(z) to be a Gaussian with zero mean and identity covariance, only in VIMAE-l we choose the prior p(z) to be a logistic with mean zero and identity variance. We choose pθ(x|z) to be similar to DCGAN with batch normalization and qφ(z|x) to be a convolutional deep neural network. The entire models are trained end to end by Adam (Kingma & Ba, 2014) with α = 10−3, β1 = 0.5, β2 = 0.999. We considered a deterministic decoder and we approximate the reconstruction loss with the L2 loss, i.e. Ep(x)[Eq(z|x)[− log pθ(x|z)]] = ‖x − xg‖22, with xg indicating the generated datum. In VIMAE case, while training we were adding a pixel-wise Gaussian noise truncated at 0.01 to all the images before feeding them to encoder, in order to make the encoder random. In VAE and β−VAE case, instead we used the standard reparameterization trick (Kingma & Welling, 2013). In the following we describe the data-sets considered and the associated neural networks, we follow the same description given in (Tolstikhin et al., 2017) since we used the same neural nets.

heading: MNIST AND OMNIGLOT

text:
MNIST is a data-set containing 70k grey-scale handwritten digits and associated labels of resolution 28× 28, subdivided in three subsets: train (50k), validation (10k) and test (10k). Omniglot is a data-set containing 1623 different handwritten characters of resolution 28 × 28 from 50 different alphabets. Each of the 1623 characters was drawn online via Amazon’s Mechanical Turk by 20 different people. In the same fashion as done in (Vinyals et al., 2016) we considered an augmented version where each character is rotated respectively by 90, 180, 270 degrees, in this way each character appears 80 times. The Omniglot data-set although has the same resolution of the MNIST, for this reason we use the same network, it is more challenging because, it is more entropic then MNIST, in fact the classes move from 10 to 1623 and the test classes are never seen in the training.
We chooseZ = R8, and β = λ = 10, we used mini-batches of size 100 and trained the model for 80 epochs. Both encoder and decoder used fully convolutional architectures with 4 × 4 convolutional filters. Encoder:
x ∈ R28×28 → Conv128 → BN→ ReLu → Conv256 → BN→ ReLu → Conv512 → BN→ ReLu → Conv1024 → BN→ ReLu
Decoder:
z ∈ R8 → FC7×7×1024 → FSConv512 → BN→ ReLu → FSConv256 → BN→ ReLu→ FSConv1
Where Convk stands for a convolution with k filters, FSConvk for the fractional strided convolution with k filters, BN for batch normalization, ReLU for the rectified linear units, and FCk for the fully connected layer mapping to Rk. All the convolutions in the encoder used vertical and horizontal strides 2 and SAME padding.

heading: CELEBA AND CIFAR10

text:
CelebA is a data-set with 202 599 faces images. We preprocessed the images by first taking a 140 × 140 center crops and then resizing to the 64 × 64 resolution and we consider the last 20k images as test subset. CIFAR10 is a dataset consisting of of 60k 32× 32 colour images in 10 classes, with 6k images per class. There are 50k training images and 10k test images.
For these data-sets we choose the same network with the same hyper-parameters, λ = 100 and Z = R64. We used mini-batches of size 100 and trained the model for 60 epochs. Both encoder and decoder used a fully convolutional architectures with 5× 5 convolutioanal filters. Encoder:
x ∈ R64×64×3 → Conv128 → BN→ ReLu → Conv256 → BN→ ReLu → Conv512 → BN→ ReLu → Conv1024 → BN→ ReLu
Decoder:
z ∈ R64 → FC8×8×1024 → FSConv512 → BN→ ReLu → FSConv256 → BN→ ReLu → FSConv128 → BN→ ReLu→ FSConv1

heading: CELEBA AND OMNIGLOT EXPERIMENTS

text: In section 5.2 we evaluate the generative performance on relatively simple grey-scale data-set. In order to consider a more challenging data-set and quantitatively compare the generative performances of the trained models we evaluate the Frechet Inception Distance (FID) on CelebA and CIFAR10 based on 104 samples. From table 5, we observe, in agreement on what observed in section 5.2 and figures 4 and 5 that the difference between the two VIMAE models is minimal, instead it is big the difference with the ELBO based models (βH -VAE is not listed in table 5, because it does not converge).

heading: MNIST EXPERIMENTS

text: The MNIST dataset is a classical benchmark but quite simple, indeed as we see from figure 6 all the models considered are able to reconstruct without big differences, although as we see from the L2 reconstruction loss in the VIMAE models is smaller than the ELBO-based counterpart. That results combined with the high value of the rate term, suggest that the VIMAE are actually learning a maximal informative decoder. We conclude observing that, according to what seen until now, the high rate value for βA-VAE is associated to an high entropy h(q(z)), this is well visible by the generated samples from p(z) in figure 7, where the samples associated to βA-VAE seem to belong to the same cluster.


summaries: This paper proposed an attributed network embedding method by leveraging a node’s local distribution over attributes. The neighborhood attribute distribution of a node is considered in both a pooled and a multi-scale way. The multi-scale embedding approach considers the neighborhood nodes with different distance to the interested node distinctly, providing more flexibilities to the model. Then, the paper proved theoretically that the proposed embedding methods, both the pooled and multi-scale versions, can be equivalently written the factorization of a node-feature pointwise mutual information matrix.

summaries: This manuscript introduces embedding algorithms that consider attribute distribution. To address the multi-scale attribute information, the multi-scale version of AE is derived (MUSAE). Then the proposed algorithms are proven theoretically to implicitly factorize the PMI matrix, which enhance their interpretability. The experiments are conducted on various scenarios including node classification, transfer learning, regression and link prediction. showing the quality of learned embeddings. The results show the benefits of multi-scaling and several conclusions are drawn.

summaries: This paper introduces Skip-gram style embedding algorithms that consider attribute distributions over local neighborhoods. Algorithm 1 and 2 shows that in fact they propagate randomly selected node features to neighbors. The reviewer doesn’t think this random-walk way for selecting node feature is appropriate.  Node features describe node content. The features of neighboring nodes may complement each other. However, there is no benefit to select random features and then propagate, given that there already many approaches smartly combining node content in neighborhood.

abstractText: We present network embedding algorithms that capture information about a node from the local distribution over node attributes around it, as observed over random walks following an approach similar to Skip-gram. Observations from neighborhoods of different sizes are either pooled (AE) or encoded distinctly in a multiscale approach (MUSAE). Capturing attribute-neighborhood relationships over multiple scales is useful for a diverse range of applications, including latent feature identification across disconnected networks with similar attributes. We prove theoretically that matrices of node-feature pointwise mutual information are implicitly factorized by the embeddings. Experiments show that our algorithms are robust, computationally efficient and outperform comparable models on social, web and citation network datasets.

authors:
Sami Abu-El-Haija
Bryan Perozzi
Rami Al-Rfou
Alexander A Alemi

title: Watch your step: Learning node embeddings via graph attention

venue: Advances in Neural Information Processing Systems

authors:
Sami Abu-El-Haija
Bryan Perozzi
Amol Kapoor
Nazanin Alipourfard
Kristina Lerman
Hrayr Harutyunyan
Greg Ver Steeg
Aram Galstyan

title: MixHop: Higher-order graph convolutional architectures via sparsified neighborhood mixing

venue: In Proceedings of the 36th International Conference on Machine Learning (ICML),

authors:
Nesreen K Ahmed
Ryan Rossi
John Boaz Lee
Xiangnan Kong
Theodore L Willke
Rong Zhou
Hoda Eldardiry

title: Learning role-based graph embeddings

venue: arXiv preprint arXiv:1802.02896,

authors:
Shaosheng Cao
Wei Lu
Qiongkai Xu

title: Grarep: Learning graph representations with global structural information

venue: In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management,

authors:
Wei-Lin Chiang
Xuanqing Liu
Si Si
Yang Li
Samy Bengio
Cho-Jui Hsieh

title: Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks

venue: In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery  Data Mining (KDD),

authors:
Matthias Fey
Jan E. Lenssen

title: Fast graph representation learning with PyTorch Geometric

venue: In ICLR Workshop on Representation Learning on Graphs and Manifolds,

authors:
Aditya Grover
Jure Leskovec

title: node2vec: Scalable feature learning for networks

venue: In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,

authors:
Will Hamilton
Zhitao Ying
Jure Leskovec

title: Inductive representation learning on large graphs

venue: In Advances in Neural Information Processing Systems (NIPS)

authors:
Xiao Huang
Jundong Li
Xia Hu

title: Accelerated attributed network embedding

venue: In Proceedings of the 2017 SIAM International Conference on Data Mining,

authors:
George Karypis
Vipin Kumar

title: A fast and high quality multilevel scheme for partitioning irregular graphs

venue: SIAM Journal on scientific Computing,

authors:
Diederik Kingma
Jimmy Ba

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

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

authors:
Omer Levy
Yoav Goldberg

title: Neural word embedding as implicit matrix factorization

venue: In Advances in neural information processing systems,

authors:
Lizi Liao
Xiangnan He
Hanwang Zhang
Tat-Seng Chua

title: Attributed social network embedding

venue: IEEE Transactions on Knowledge and Data Engineering,

authors:
Tomas Mikolov
Kai Chen
Greg Corrado
Jeffrey Dean

title: Efficient estimation of word representations in vector space

authors:
Tomas Mikolov
Ilya Sutskever
Kai Chen
Greg S Corrado
Jeff Dean

title: Distributed representations of words and phrases and their compositionality

authors:
Vinod Nair
Geoffrey E Hinton

title: Rectified linear units improve restricted boltzmann machines

venue: In Proceedings of the 27th International Conference on Machine Learning (ICML),

authors:
Fabian Pedregosa
Gaël Varoquaux
Alexandre Gramfort
Vincent Michel
Bertrand Thirion
Olivier Grisel
Mathieu Blondel
Peter Prettenhofer
Ron Weiss
Vincent Dubourg

title: Scikit-learn: Machine learning in python

venue: Journal of machine learning research,

authors:
Bryan Perozzi
Rami Al-Rfou
Steven Skiena

title: Deepwalk: Online learning of social representations

venue: In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining.,

authors:
Bryan Perozzi
Vivek Kulkarni
Haochen Chen
Steven Skiena

title: Don’t walk, skip!: Online learning of multi-scale network embeddings

venue: In Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017,

authors:
Jiezhong Qiu
Yuxiao Dong
Hao Ma
Jian Li
Kuansan Wang
Jie Tang

title: Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec

venue: In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining,

authors:
Leonardo F.R. Ribeiro
Pedro H.P. Saverese
Daniel R. Figueiredo

title: Struc2vec: Learning node representations from structural identity

venue: In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’17,

authors:
Oleksandr Shchur
Maximilian Mumme
Aleksandar Bojchevski
Stephan Günnemann

title: Pitfalls of graph neural network evaluation

venue: Relational Representation Learning Workshop,

authors:
Jian Tang
Meng Qu
Mingzhe Wang
Ming Zhang
Jun Yan
Qiaozhu Mei

title: Line: Large-scale information network embedding

venue: In Proceedings of the 24th International Conference on World Wide Web,

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

title: Graph attention networks

authors:
Felix Wu
Amauri Souza
Tianyi Zhang
Christopher Fifty
Tao Yu
Kilian Weinberger

title: Simplifying graph convolutional networks

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

title: Network representation learning with rich text information

venue: In IJCAI,

authors:
Hong Yang
Shirui Pan
Peng Zhang
Ling Chen
Defu Lian
Chengqi Zhang

title: Binarized attributed network embedding

venue: IEEE International Conference on Data Mining (ICDM),

authors:
Shuang Yang
Bo Yang

title: Enhanced network embedding with text information

venue: 24th International Conference on Pattern Recognition (ICPR),

authors:
Daokun Zhang
Jie Yin
Xingquan Zhu
Chengqi Zhang

title: Sine: Scalable incomplete network embedding

title: The proof is analogous to that given for Theorem

title: HYPERPARAMETER SETTINGS OF COMPETING GRAPH NEURAL NETWORKS Each model was optimized with the Adam optimizer (Kingma & Ba, 2015) with the standard moving average parameters and the model implementations are sparsity aware modifications based on PyTorch

venue: Geometric (Fey & Lenssen,

title: did, we used the METIS procedure (Karypis

venue: ClusterGCN (Chiang et al.,

heading: 1 INTRODUCTION

text:
Node embedding is a fundamental technique in network analysis that serves as a precursor to numerous downstream machine learning and optimisation tasks, e.g. community detection, network visualization and link prediction (Perozzi et al., 2014; Grover & Leskovec, 2016; Tang et al., 2015). Several recent network embedding methods, such as Deepwalk (Perozzi et al., 2014), Node2Vec (Grover & Leskovec, 2016) and Walklets (Perozzi et al., 2017), achieve impressive performance by learning the network structure following an approach similar to Word2Vec Skip-gram (Mikolov et al., 2013b), originally designed for word embedding. In these works, sequences of neighboring nodes are generated from random walks over a network, and representations are distilled from extracted node-node proximity statistics that capture local neighbourhood information.
When the nodes of a network have attributes (or features), their embeddings can be used to capture information about the attributes in their local neighbourhood. For a social network, attributes might represent a person’s interests, habits, history or preferences. The pattern of node attributes are often similar in a neighborhood, and conversely, nodes with similar attributes are more likely to be connected. This property is known as homophily. Attributed network embedding methods (Yang et al., 2015; Huang et al., 2017; Liao et al., 2018) leverage this additional information to supplement that of node neighbourhood structure, benefiting many applications, e.g. recommender systems, node classification and link prediction (Yang et al., 2018; Yang & Yang, 2018; Zhang et al., 2018).
The neighborhood of a node can be considered at different path lengths, or scales. In a social network, near neighbors may correspond to classmates, whereas nodes separated by greater scales may be in different cities or countries. Attributes of neighbors at different scales can be considered separately (multi-scale) or pooled in some way (e.g. weighted average). Figure 1a shows how the attribute distribution over neighbourhoods at different scales can indicate nodes with similar network roles even if they are distant in the network, or even in different networks. Methods that take attributes of nearby nodes into account generalizes those that do not, e.g. Perozzi et al. (2017), for which feature vectors can be considered standard basis vectors.
Many embedding methods correspond to matrix factorization, indeed some attributed embedding methods (e.g. Yang et al. (2018)) explicitly factorize a matrix of link-attribute information. Embeddings learned using Skip-gram are known to factorize a matrix of pointwise mutual information (PMI) of co-occurrences between each word and local context words (Levy & Goldberg, 2014). Related network embedding methods (Perozzi et al., 2014; Grover & Leskovec, 2016; Tang et al., 2015; Qiu et al., 2018) also implicitly factorize PMI matrices based on the probability of encountering each (context) node on a random walk from each starting node (Qiu et al., 2018).
Our key contributions are:
1. to introduce the first Skip-gram style embedding algorithms that consider attribute distributions over local neighborhoods, both pooled (AE) and multi-scale (MUSAE), and their counterparts that attribute distinct features to each node (AE-EGO and MUSAE-EGO);
2. to theoretically prove that their embeddings approximately factorize PMI matrices based on the product of an adjacency matrix power and node-feature matrix;
3. to show that popular network embedding methods DeepWalk (Perozzi et al., 2014) and Walklets (Perozzi et al., 2017) are special cases of our AE and MUSAE;
4. we show empirically that AE and MUSAE embeddings enable strong performance at regression, classification, and link prediction tasks for real-world networks (e.g. Wikipedia and Facebook), are computationally scalable and enable transfer learning between networks.
We provide reference implementations of AE and MUSAE, together with the datasets used for evaluation at https://github.com/iclr2020/MUSAE.

heading: 2 RELATED WORK

text:
Efficient unsupervised learning of node embeddings for large networks has seen unprecedented development in recent years. The current paradigm focuses on learning latent space representations of nodes such that those that share neighbors (Perozzi et al., 2014; Tang et al., 2015; Grover & Leskovec, 2016; Perozzi et al., 2017), structural roles (Ribeiro et al., 2017; Ahmed et al., 2018) or attributes are located close together in the embedding space. Our work falls under the last of these categories as our goal is to learn similar latent representations for nodes with similar sets of features in their neighborhoods, both on a pooled and multi-scale basis.
Neighborhood preserving node embedding procedures place nodes with common first, second and higher order neighbors within close proximity in the embedding space. Recent works in the neighborhood preserving node embedding literature were inspired by the Skip-gram model (Mikolov et al., 2013a;b), which generates word embeddings by implicitly factorizing a shifted pointwise mutual information (PMI) matrix (Levy & Goldberg, 2014) obtained from a text corpus. This procedure inspired DeepWalk (Perozzi et al., 2014), a method which generates truncated random walks over a graph to obtain a “corpus” from which the Skip-gram model generates neighborhood preserving node embeddings. In doing so, DeepWalk implicitly factorizes a PMI matrix, which can be shown, based on the underlying first-order Markov process, to correspond to the mean of a set of normalized adjacency matrix powers up to a given order (Qiu et al., 2018). Such pooling of matrices can be suboptimal since neighbors over increasing path lengths (or scales) are treated equally or according to fixed weightings (Mikolov et al., 2013a; Grover & Leskovec, 2016); whereas it has been found
that an optimal weighting may be task or dataset specific (Abu-El-Haija et al., 2018). In contrast, multi-scale node embedding methods such as LINE (Tang et al., 2015), GraRep (Cao et al., 2015) and Walklets (Perozzi et al., 2017) separately learn lower-dimensional node embedding components from each adjacency matrix power and concatenate them to form the full node representation. Such un-pooled representations, comprising distinct but less information at each scale, are found to give higher performance in a number of downstream settings, without increasing the overall number of free parameters (Perozzi et al., 2017).
Attributed node embedding procedures refine ideas from neighborhood based node embeddings to also incorporate node attributes (equivalently, features or labels) (Yang et al., 2015; Liao et al., 2018; Huang et al., 2017; Yang et al., 2018; Yang & Yang, 2018). Similarities between both a node’s neighborhood structure and features contribute to determining pairwise proximity in the node embedding space. These models follow quite different strategies to obtain such representations. The most elemental procedure, TADW (Yang et al., 2015), decomposes a convex combination of normalized adjacency matrix powers into a matrix product that includes the feature matrix. Several other models, such as SINE (Zhang et al., 2018) and ASNE (Liao et al., 2018), implicitly factorize a matrix formed by concatenating the feature and adjacency matrices. Other approaches such as TENE (Yang & Yang, 2018), formulate the attributed node embedding task as a joint non-negative matrix factorization problem in which node representations obtained from sub-tasks are used to regularize one another. AANE (Huang et al., 2017) uses a similar network structure based regularization approach, in which a node feature similarity matrix is decomposed using the alternating direction method of multipliers. The method most similar to our own is BANE (Yang et al., 2018), in which the product of a normalized adjacency matrix power and a feature matrix is explicitly factorized to obtain attributed node embeddings. Many other methods exist, but do not consider the attributes of higher order neighborhoods (Yang et al., 2015; Liao et al., 2018; Huang et al., 2017; Zhang et al., 2018; Yang & Yang, 2018).
The relationship between our pooled (AE) and multi-scale (MUSAE) attributed node embedding methods mirrors that between graph convolutional neural networks (GCNNs) and multi-scale GCNNs. Widely used graph convolutional layers, such as GCN (Kipf & Welling, 2017), GraphSage (Hamilton et al., 2017), GAT (Veličković et al., 2018), APPNP (Klicpera et al., 2019), SGCONV (Wu et al., 2019) and ClusterGCN (Chiang et al., 2019), create latent node representations that pool node attributes from arbitrary order neighborhoods, which are then inseparable and unrecoverable. In contrast, MixHop (Abu-El-Haija et al., 2019) learns latent features for each proximity.

heading: 3 ATTRIBUTED EMBEDDING MODELS

text: We now define algorithms to learn node embeddings using the attributes of nearby nodes, that allows both node and attribute embeddings to be learned jointly. The aim is to learn similar embeddings for nodes that occur in neighbourhoods of similar attributes; and similar embeddings for attributes that often occur in similar neighbourhoods of nodes. Let G = (V,L) be an undirected graph of interest where V and L are the sets of vertices and edges (or links) respectively; and let F be the set of all possible node features (i.e. attributes). We define Fv ⊆ F as the subset of features belonging to each node v ∈V. An embedding of nodes is a mapping g : V→Rd that assigns a d-dimensional representation g(v) (or simply gv) to each node v and is fully described by a matrix G ∈ R|V|×d. Similarly, an embedding of the features (to the same latent space) is a mapping h : F → Rd with embeddings denoted h(f) (or simply hf ), and is fully described by a matrix H∈R|F|×d.

heading: 3.1 ATTRIBUTED EMBEDDING

text:
The Attributed Embedding (AE) procedure is described by Algorithm 1. We sample n nodes w1, from which to start attributed random walks on G, with probability proportional to their degree (Line 2). From each starting node, a node sequence of length l is sampled over G (Line 3), where sampling follows a first order random walk. For a given window size t, we iterate over each of the first l−t nodes of the sequence termed source nodes wj (Line 4). For each source node, we consider the following t nodes as target nodes (Line 5). For each target node wj+r, we add the tuple (wj , f) to the corpus D for each target feature f ∈Fwj+r (Lines 6 and 7). We also consider features of the source node f ∈Fwj , adding each (wj+r, f) tuple to D (Lines 9 and 10). Running Skip-gram on D with b negative samples (Line 15) generates the d-dimensional node and feature embeddings.
Data: G = (V,L) – Graph to be embedded. {Fv}V – Set of node feature sets. n – Number of sequence samples. l – Length of sequences. t – Context size. d – Embedding dimension. b – Number of negative samples. Result: Node embedding g and feature embedding h.
1 for i in 1 : n do
2 Pick w1 ∈ V according to P (w1) ∼ deg(w1)/vol(G). 3 (w1, w2, . . . , wl)← Sample Nodes(G, w1, l) 4 for j in 1 : l − t do
5 for r in 1 : t do 6 for f in Fwj+r do 7 Add tuple (wj , f) to multiset D. 8 end 9 for f in Fwj do
10 Add tuple (wj+r, f) to multiset D. 11 end 12 end 13 end 14 end 15 Run SGNS on D with b negative samples and d dimensions. 16 Output gv, ∀v ∈ V, and hf , ∀f ∈ F = ∪VFv .
Algorithm 1: AE sampling and training procedure
Data: G = (V,L) – Graph to be embedded. {Fv}V – Set of node feature sets. n – Number of sequence samples. l – Length of sequences. t – Context size. d – Embedding dimension. b – Number of negative samples. Result: Node embeddings gr and feature embeddings hr for r = 1, . . . , t.
1 for i in 1 : n do
2 Pick w1 ∈ V according to P (w1) ∼ deg(w1)/vol(G). 3 (w1, w2, . . . , wl)← Sample Nodes(G, w1, l) 4 for j in 1 : l − t do 5 for r in 1 : t do 6 for f in Fwj+r do 7 Add the tuple (wj , f) to multiset D→
r .
8 end 9 for f in Fwj do 10 Add the tuple (wj+r, f) to multiset D← r
. 11 end 12 end 13 end 14 end 15 for r in 1 : t do 16 Create Dr by unification of D→
r and D← r .
17 Run SGNS on Dr with b negative samples and dt dimensions. 18 Output grv, ∀v ∈ V, and hrf , ∀f ∈ F = ∪VFv . 19 end
Algorithm 2: MUSAE sampling and training procedure

heading: 3.2 MULTI-SCALE ATTRIBUTED EMBEDDING

text: The AE method (Algorithm 1) pools feature sets of neighborhoods at different proximities. Inspired by the performance of (unattributed) multi-scale node embeddings, we adapt the AE algorithm to give multi-scale attributed node embeddings (MUSAE). The embedding component of a node v∈V for a specific proximity r ∈ {1, ..., t} is given by a mapping gr : V → Rd/t (assuming t divides d). Similarly, the embedding component of feature f ∈ F at proximity r is given by a mapping hr : F→ Rd/t. Concatenating gives a d-dimensional embedding for each node and feature. The Multi-Scale Attributed Embedding procedure is described by Algorithm 2. We again sample n starting nodes w1 with a probability proportional to node degree (Line 2) and, for each, sample a node sequence of length l over G (Line 3) according to either a first or second order random walk. For a given window size t, we iterate over the first l − t (source) nodes wj of the sequence (Line 4) and for each source node we iterate through the t (target) nodes wj+r that follow (Line 5). We again consider each target node feature f ∈Fwj+r , but now add tuples (wj , f) to a sub-corpus D r→ (Lines 6 and 7). We add tuples (wj+r, f) to another sub-corpus D r← for each source node feature f ∈Fwj (Lines 9 and 10). Running Skip-gram on each sub-corpus Dr = D r→ ∪D r← with b negative samples (Line 16) output t (dt )-dimensional node and feature embeddings that are concatenated.

heading: 4 ATTRIBUTED EMBEDDING AS IMPLICIT MATRIX FACTORIZATION

text:
Levy & Goldberg (2014) showed that the loss function of Skip-gram with negative sampling (SGNS) is minimized if the embedding matrices factorize a matrix of pointwise mutual information (PMI) of word co-occurrence statistics. Specifically, for a word dictionary V with |V|=n, SGNS (with b negative samples) outputs two embedding matrices W ,C ∈ Rd×n such that ∀w, c∈V:
w>wcc ≈ log (#(w,c)|D| #(w)#(c) ) − log b ,
where #(w, c), #(w), #(c) denote counts of word-context pair (w, c), w and c over a corpus D; and word embeddings ww, cc∈Rd are columns of W and C corresponding to w and c respectively. Considering #(w)|D| , #(c) |D| , #(w,c) |D| as empirical estimates of p(w), p(c) and p(w, c) respectively shows:
W>C ≈ [PMI(w, c)− log b ]w,c∈V , i.e. an approximate low-rank factorization of a shifted PMI matrix (low rank since typically d n). Qiu et al. (2018) extended this result to node embedding models that apply SGNS to a “corpus” generated from random walks over the graph. In the case of DeepWalk where random walks are first-order Markov, the joint probability distributions over nodes at different stages of a random walk can be expressed in closed form. A closed form then follows for the factorized PMI matrix. We show that AE and MUSAE implicitly perform analogous matrix factorizations.
Notation: A∈Rn×n denotes the adjacency matrix and D∈Rn×n the diagonal degree matrix of a graph G, i.e. Dw,w = deg(w) = ∑ v Aw,v . We denote the volume of G by c = ∑ v,w Av,w. We define the binary attribute matrix F ∈ {0, 1}|V|×|F| by Fw,f = 1f∈Fw , ∀w ∈V, f ∈ F. For ease of notation, we let P =D−1A and E=diag(1>DF ), where diag indicates a diagonal matrix.
Interpretation: Assuming G is ergodic: p(w) = deg(w)c , w ∈ V is the stationary distribution over nodes, i.e. c−1D = diag(p(w)); and c−1A is the stationary joint distribution over consecutive nodes p(wj , wj+1). Fw,f can be considered a Bernoulli parameter describing the probability p(f |w) of observing a feature f at a node w and so c−1DF describes the stationary joint distribution p(f, wj) over nodes and features. Accordingly, P is the matrix of conditional distributions p(wj+1|wj); and E is a diagonal matrix proportional to the probability of observing each feature at the stationary distribution p(f) (note that p(f) need not sum to 1, whereas p(w) necessarily must).

heading: 4.1 MULTI-SCALE CASE (MUSAE)

text:
We know that the SGNS aspect of MUSAE (Algorithm 2, Line 17) is minimized when the learned embeddings grv , h r f satisfy g r w >hrf ≈ log (#(w,f)r|Dr| #(w)r#(f)r ) − log b ∀w∈V, f ∈F. Our aim is to express this factorization in terms of known properties of the graph G and its features.
Lemma 1. The empirical statistics of node-feature pairs obtained from random walks give unbiased estimates of joint probabilities of observing feature f ∈F r steps (i) after; or (ii) before node v ∈ V, as given by:
plim l→∞
#(w,f)→ r
|D→ r | = c −1(DP rF )w,f plim l→∞
#(w,f)← r
|D← r | = c
−1(F>DP r)f,w
Proof. See Appendix.
Lemma 2. Empirical statistics of node-feature pairs obtained from random walks give unbiased estimates of joint probabilities of observing feature f ∈F r steps either side of node v∈V, given by:
plim l→∞ #(w,f)r |Dr| = c −1(DP rF )w,f ,
Proof. See Appendix.
Marginalizing gives unbiased estimates of stationary probability distributions of nodes and features:
plim l→∞ #(w) |Dr| = deg(w) c = c −1Dw,w and plim l→∞ #(f) |Dr| = ∑ w|f∈Fw deg(w) c = c −1Ef,f
Theorem 1. MUSAE embeddings approximately factorize the node-feature PMI matrix: log ( cP rFE−1 ) − log b, for r = 1, ... , t.
Proof.
#(w,f)r|Dr| #(f)r#(w)r = (#(w,f)r |Dr| ) / (#(f)r |Dr| #(w)r |Dr| ) p−→ ( (cD−1)(c−1DP rF )(cE−1) ) w,f
= c(P rFE−1)w,f

heading: 4.2 POOLED CASE (AE)

text:
Lemma 3. The empirical statistics of node-feature pairs learned by the AE algorithm give unbiased estimates of mean joint probabilities over different path lengths as follows:
plim l→∞
#(w,f) |D| = c t
( D( t∑ r=1 P r)F ) w,f
(1)
Proof. By construction, |D|= ∑ r |Dr|, #(w, f)= ∑
r #(w, f)r, |Dr|= |Ds| ∀ r, s∈{1, . . . , t} and so |Ds|= t−1|D|. Combining with Lemma 2, the result follows.
Theorem 2. AE embeddings approximately factorize the pooled node-feature matrix:
log ( c t ( t∑ r=1 Pr)FE−1 ) − log b .
Proof. The proof is analogous to the proof of Theorem 1.
Remark 1. DeepWalk is a corner case of AE with F =I|V|.
That is, DeepWalk is equivalent to AE if each node has a single unique feature. Thus E = diag(1>DI)=D and, by Theorem 2, DeepWalk’s embeddings factorize log ( c t ( ∑t r=1 P r)D−1 ) − log b, as previously noted by Qiu et al. (2018).
Remark 2. Walklets is a corner case of MUSAE with F =I|V|. Thus, for r = 1, . . . , t, the embeddings of Walklets factorise log ( cPrD−1 ) − log b.
Remark 3. Appending an identity matrix I to the feature matrices F of AE and MUSAE (denoted [F ; I]) adds a unique feature to each node. The resulting algorithms, named AE-EGO and MUSAEEGO, learn embeddings that, respectively, approximately factorize the node-feature PMI matrices: log ( cP r [F ; I]E−1 ) − log b, ∀r∈{1, ..., t}; and log ( c t (
t∑ r=1 P r) [F ; I]E−1 ) − log b .

heading: 4.3 COMPLEXITY ANALYSIS

text:
Under the assumption of a constant number of features per source node and first-order attributed random walk sampling, the corpus generation has a runtime complexity of O(n l t x/y), where x = ∑ v∈V |Fv| the total number of features across all nodes (including repetition) and y = |V| the number of nodes. Using negative sampling, the optimization runtime of a single asynchronous gradient descent epoch on AE and the joint optimization runtime of MUSAE embeddings is described by O(b d n l t x/y). If one does p truncated walks from each source node, the corpus generation complexity is O(p y l t x) and the model optimization runtime is O(b d p y l t x). Our later runtime experiments in Section 5 will underpin optimization runtime complexity discussed above.
Corpus generation has a memory complexity of O(n l t x/y) while the same when generating p truncated walks per node has a memory complexity of O(p y l t x). Storing the parameters of an AE embedding has a memory complexity ofO(y d) and MUSAE embeddings also useO(y d) memory.

heading: 5 EXPERIMENTAL EVALUATION

text: In order to evaluate the quality of created representations we test the embeddings on supervised downstream tasks such as node classification, transfer learning across networks, regression, and link prediction. Finally, we investigate how changes in the input size affect the runtime. For doing so we utilize social networks and web graphs that we collected from Facebook, Github, Twitch and Wikipedia. The data sources, collection procedures and the datasets themselves are described with great detail in Appendix B. In addition we tested our methods on citation networks widely used for model evaluation (Shchur et al., 2018). Across all experiments we use the same hyperparameter settings of our own model, competing unsupervised methods and graph neural networks – these are respectively listed in Appendices C, E and F.

heading: 5.1 NODE CLASSIFICATION

text: We evaluate the node classification performance in two separate scenarios. In the first we do k-shot learning by using the attributed embedding vectors with logistic regression to predict labels on the Facebook, Github and Twitch Portugal graphs. In the second we test the predictive performance under a fixed size train-test split to compare against various embedding methods and competitive neural network architectures.

heading: 5.1.1 K-SHOT LEARNING

text:
In this experiment we take k randomly selected samples per class, and use the attributed node embeddings to train a logistic regression model with l2 regularization and predict the labels on the remaining vertices. We repeated the above procedure with seeded splits 100 times to obtain robust comparable results (Shchur et al., 2018). From these we calculated the average of micro averaged F1 scores to compare our own methods with other unsupervised node embedding procedures. We varied k in order to show the efficacy of the methods – what are the gains when the training set size is increased. These results are plotted in Figure 2 for Facebook, Github and Twitch Portugal networks.
Based on these plots it is evident that MUSAE and AE embeddings have little gains in terms of micro F1 score when additional data points are added to the training set when k is larger than 12. This implies that our method is data efficient. Moreover, MUSAE-EGO and AE-EGO have a slight performance advantage, which means that including the nodes in the attributed random walks helps when a small amount of labeled data is available in the downstream task.

heading: 5.1.2 FIXED RATIO TRAIN-TEST SPLITS

text:
In this series of experiments we created a 100 seeded train test splits of nodes (80% train - 20% test) and calculated weighted, micro and macro averaged F1 scores on the test set to compare our methods to various embedding and graph neural network methods. Across procedures the same random seeds were used to obtain the train-test split this way the performances are directly comparable. We attached these results on the Facebook, Github and Twitch Portugal graphs as Table 6 of Appendix G. In each column red denotes the best performing unsupervised embedding model and blue corresponds to the strongest supervised neural model. We also attached additional supporting results using the same experimental setting with the unsupervised methods on the Cora, Citeseer, and Pubmed graphs as Table 5 of Appendix G.
In terms of micro F1 score our strongest method outperforms on the Facebook and GitHub networks the best unsupervised method by 1.01% and 0.47% respectively. On the Twitch Portugal network the relative micro F1 advantage of ASNE over our best method is 1.02%. Supervised node embedding methods outperform our and other unsupervised methods on every dataset for most metrics. In terms of micro F1 this relative advantage over our best performing model variant is the largest with 4.67% on the Facebook network, and only 0.11% on Twitch Portugal.
One can make four general observations based on our results (i) multi-scale representations can help with the classification tasks compared to pooled ones; (ii) the addition of the nodes in the ego augmented models to the feature sets does not help the performance when a large amount of labeled
training data is available; (iii) based on the standard errors supervised neural models do not necessarily have a significant advantage over unsupervised methods (see the results on the Github and Twitch datasets); (iv) attributed node embedding methods that only consider first-order neighbourhoods have a poor performance.

heading: 5.2 TRANSFER LEARNING ON TWITCH SOCIAL NETWORKS

text:
Neighbourhood based methods such as DeepWalk (Perozzi et al., 2014) are transductive and the function used to create the embedding cannot map nodes that are not connected to the original graph to the latent space. However, vanilla MUSAE and AE are inductive and can easily map nodes to the embedding space if the attributes across the source and target graph are shared. This also means that supervised models trained on the embedding of a source graph are transferable. Importantly those attributed embedding methods such as AANE or ASNE that explicitly use the graph are unable to do this transfer.
Using the disjoint Twitch country level social networks (inter country edges are not present) we did a transfer learning experiment. First, we learn an embedding function given the social network from a country with the standard parameter settings. Second, we train regularized logistic regression on the embedding to predict whether the Twitch user streams explicit content. Third, using the embedding function we map the target graph to the embedding space. Fourth, we use the logistic model to predict the node labels on the target graph. We evaluate the performance by the micro F1 score based on 10 experimental repetitions. These averages with standard error bars are plotted for the Twitch Germany, England and Spain datasets as target graphs on Figure 3. We added additional results with France, Portugal and Russia being the target country in Appendix H as Table 5.
These results support that MUSAE and AE create features that are transferable across graphs that share vertex features. For example, based on a comparison to non transfer-learning results we find that the transfer between the German and English user graphs is effective in terms of micro F1 score. Transfer from English users to German ones considerably improves performance, and the other way around there is a little gain. We also see that the upstream and downstream models that we trained on graphs with more vertices transfer well while transfer to the small ones is generally poor – most of the times worse than random guessing. There is no clear evidence that either MUSAE or AE gives better results on this specific problem.

heading: 5.3 REGRESSION ON WIKIPEDIA GRAPHS

text:
We created embeddings of the Wikipedia webgraphs with all of our methods and the unsupervised baselines. Using a 80% train - 20% test split we predict the log of average traffic for each page using
an elastic net model. The hyperparameters of the downstream model are available in Appendix D. In Table 7 of Appendix I we report average test R2 and standard error of the predictive performance over 100 seeded train-test splits. Our key observation are: (i) that MUSAE outperforms all benchmark neighbourhood preserving and attributed node embedding methods, with the strongest MUSAE variant outperforming the best baseline between 2.05% and 10.03% (test R2); (ii) that MUSAE significantly outperforms AE by between 2.49% and 21.64% (test R2); and (iii) the benefit of using the vertices as features (ego augmented model) can improve the performance of embeddings, but appears to be dataset specific phenomenon.

heading: 5.4 LINK PREDICTION ON WEB GRAPHS AND SOCIAL NETWORKS

text:
The final series of experiments dedicated to the representation quality is about link prediction. We carried out an attenuated graph embedding trial to predict the removed edges from the graph. First, we randomly removed 50% of edges while the connectivity of the graph was not changed. Second, an embedding is created from the attenuated graph. Third, we calculate features for the removed edges and the same number of randomly selected pairs of nodes (negative candidates) with binary operators to create d-dimensional edge features. We use the binary operators applied by Grover & Leskovec (2016). Specifically, we calculated the average, element-wise product, element-wise l1 norm and the element-wise l2 norm of vectors. Finally, we created a 100 seeded 80% train - 20% test splits and used logistic regression to predict whether an edge exists.
We compared to attributed and neighbourhood based embedding methods and average AUC scores are presented in Tables 8 and 9 of Appendix J. Our results show that Walklets (Perozzi et al., 2017) the multi-scale neighbourhood based embedding method materially outperforms every other method on most of the datasets and attributed embedding methods generally do poorly in terms of AUC compared to neighbourhood based ones.

heading: 5.5 SCALABILITY

text:
In order to show the efficacy of our algorithms we run a series of experiments on synthetic graphs where we are able to manipulate the input size. Specifically, we look at the effect of changing the number of vertices and features per vertex. Our detailed experimental setup was as follows. Each point in Figure 4 is the mean runtime obtained from 100 experimental runs on Erdos-Renyi graphs. The base graph that we manipulated had 211 nodes, 23 edges and the same number of unique features per node uniformly selected from a feature set of 211. Our experimental settings were the same as the ones described in Appendix C except for the number of epochs. We only did a single training epoch with asynchronous gradient descent on each graph. We tested the runtime with 1, 2 and 4 cores and included a dashed line as the linear runtime reference in each subfigure.
We observe that doubling the average number of features per vertex doubles the runtime of AE and MUSAE. Moreover, the number of cores used during the optimization does not decrease the runtime when the number of unique features per vertex compared to the cardinality of the feature set is large. When we look at the change in the vertex set size we also see a linear behaviour. Doubling the input size simply results in a doubled optimization runtime. In addition, if one interpolates linearly from these results it comes that a network with 1 million nodes, 8 edges per node, 8 unique features per node can be embedded with MUSAE on commodity hardware in less than 5 hours. This
interpolation assumes that the standard parameter settings proposed in Appendix C and 4 cores were used for optimization.

heading: 6 DISCUSSION AND CONCLUSION

text:
We investigated attributed node embedding and proposes efficient pooled (AE) and multi-scale (MUSAE) attributed node embedding algorithms with linear runtime. We proved that these algorithms implicitly factorize probability matrices of features appearing in the neighbourhood of nodes. Two widely used neighbourhood preserving node embedding methods Perozzi et al. (2014; 2017) are in fact simplified cases of our models. On several datasets (Wikipedia, Facebook, Github, and citation networks) we found that representations learned by our methods, in particular MUSAE, outperform neighbourhood based node embedding methods (Perozzi et al. (2014); Grover & Leskovec (2016)), multi-scale algorithms (Tang et al. (2015); Perozzi et al. (2017)) and recently proposed attributed node embedding procedures (Yang et al. (2015); Liao et al. (2018); Huang et al. (2017); Yang et al. (2018); Yang & Yang (2018)).
Our proposed embedding models are differentiated from other methods in that they encode feature information from higher order neighborhoods. The most similar previous model BANE (Yang et al., 2018) encodes node attributes from higher order neighbourhoods but has non-linear runtime complexity and the product of adjacency matrix power and feature matrix is decomposed explicitly.

heading: A PROOFS

text:
Lemma 1. The empirical statistics of node-feature pairs obtained from random walks give unbiased estimates of joint probabilities of observing feature f ∈F r steps (i) after; or (ii) before node v ∈ V, as given by:
plim l→∞
#(w,f)→ r
|D→ r | = c −1(DP rF )w,f plim l→∞
#(w,f)← r
|D← r | = c
−1(F>DP r)f,w
Proof. The proof is analogous to that given for Theorem 2.1 in Qiu et al. (2018). We show that the computed statistics correspond to sequences of random variables with finite expectation, bounded variance and covariances that tend to zero as the separation between variables within the sequence tends to infinity. The Weak Law of Large Numbers (S.N.Bernstein) then guarantees that the sample mean converges to the expectation of the random variable. We first consider the special case n = 1, i.e. we have a single sequence w1, ..., wl generated by a random walk (see Algorithm 1). For a particular node-feature pair (w, f ), we let Yi, i ∈ {1, ..., l − t}, be the indicator function for the event wi = w and f ∈ Fi+r. Thus, we have:
#(w,f)→ r
|D→ r | =
1 l−t l−t∑ i=1 Yi, (2)
the sample average of the Yis. We also have:
E[Yi] = deg(w)c (P rF )w,f = 1 c (DP rF )w,f
E[YiYj ] = Prob[wi = w, f ∈ Fi+r, wj = w, f ∈ Fj+r]
= deg(w)c︸ ︷︷ ︸ p(wi=w) P r:w︸︷︷︸ p(wi+r|wi=w) diag(F:f )︸ ︷︷ ︸ p(f∈Fi+r|wi+r) P j−(i+r):w︸ ︷︷ ︸ p(wj=w|wi+r)︸ ︷︷ ︸
p(wj=w,f∈Fi+r|wi=w)
P rw:F:f︸ ︷︷ ︸ p(f∈Fj+r|wj=w)
for j > i+ r. This allows us to compute the covariance: Cov(Yi, Yj) = E[YiYj ]− E[Yi]E[Yj ]
= deg(w)c P r w:diag(F:f ) ( P j−(i+r):w − deg(w) c 1 )︸ ︷︷ ︸ tends to 0 as j−i→∞ P rw:F:f , (3)
where 1 is a vector of ones. The difference term (indicated) tends to zero as j − i → ∞ since then p(wj = w|wi+r) tends to the stationary distribution p(w) = deg(w)c , regardless of wi+r. Thus, applying the Weak Law of Large Numbers, the sample average converges in probability to the expected value, i.e.:
#(w,f)→ r
|D→ r | =
1 l−t l−t∑ i=1 Yi p→ 1l−t l−t∑ i=1 E[Yi] = 1c (DP rF )w,f
A similar argument applies to #(w,f)← r
|D← r | , with expectation term 1 c (F >DP r)f,w. In both cases, the
argument readily extends to the general setting where n > 1 with suitably defined indicator functions for each of the n random walks (see Qiu et al. (2018)).
Lemma 2. Empirical statistics of node-feature pairs obtained from random walks give unbiased estimates of joint probabilities of observing feature f ∈F r steps either side of node v∈V, given by:
plim l→∞ #(w,f)r |Dr| = c −1(DP rF )w,f ,
Proof.
#(w,f)r |Dr| =
#(w,f)→ r |Dr| + #(w,f)← r |Dr|
= 12 (#(w,f)→ r
|D→ r | +
#(w,f)← r |D← r | )
p→ 12 ( 1 c (DP rF )w,f + 1 c (F >DP r)f,w )
= 12c ( DP rF + P r>DF ) w,f
= 12c ( (DP r + (A>D−1)rD)F ) w,f
= 12c ( (DP r +D(D−1A>)r)F ) w,f
= 1c (DP rF )w,f .
The final step follows by symmetry of A, indicating how the Lemma can be extended to directed graphs.

heading: B DATASETS AND DESCRIPTIVE STATISTICS

text:
Our method was evaluated on a variety of social networks and web page-page graphs that we collected from openly available API services. In Table 1 we described the graphs with widely used statistics with respect to size, diameter, and level of clustering. We also included the average number of features per vertex and unique feature count in the last columns. These datasets are available with the source code of MUSAE and AE at https://github.com/iclr2020/MUSAE.
B.1 FACEBOOK PAGE-PAGE DATASET
This webgraph is a page-page graph of verified Facebook sites. Nodes represent official Facebook pages while the links are mutual likes between sites. Node features are extracted from the site descriptions that the page owners created to summarize the purpose of the site. This graph was collected through the Facebook Graph API in November 2017 and restricted to pages from 4 categories which are defined by Facebook. These categories are: politicians, governmental organizations, television shows and companies. As one can see in Table 1 it is a highly clustered graph with a large diameter. The task related to this dataset is multi-class node classification for the 4 site categories.
B.2 GITHUB WEB AND MACHINE LEARNING DEVELOPERS DATASET The largest graph used for evaluation is a social network of GitHub developers which we collected from the public API in June 2019. Nodes are developers who have starred at least 10 repositories and edges are mutual follower relationships between them. The vertex features are extracted based on the location, repositories starred, employer and e-mail address. The task related to the graph is binary node classification – one has to predict whether the GitHub user is a web or a machine learning developer. This target feature was derived from the job title of each user. As the descriptive statistics show in Table 1 this is the largest graph that we use for evaluation with the highest sparsity.
B.3 WIKIPEDIA DATASETS The datasets that we use to perform node level regression are Wikipedia page-page networks collected on three specific topics: chameleons, crocodiles and squirrels. In these networks nodes are articles from the English Wikipedia collected in December 2018, edges are mutual links that exist between pairs of sites. Node features describe the presence of nouns appearing in the articles. For each node we also have the average monthly traffic between October 2017 and November 2018. In the regression tasks used for embedding evaluation the logarithm of average traffic is the target variable. Table 1 shows that these networks are heterogeneous in terms of size, density, and clustering.
B.4 TWITCH DATASETS These datasets used for node classification and transfer learning are Twitch user-user networks of gamers who stream in a certain language. Nodes are the users themselves and the links are mutual friendships between them. Vertex features are extracted based on the games played and liked, location and streaming habits. Datasets share the same set of node features, this makes transfer learning across networks possible. These social networks were collected in May 2018. The supervised task related to these networks is binary node classification – one has to predict whether a streamer uses explicit language.

heading: C STANDARD HYPERPARAMETER SETTINGS OF OUR EMBEDDING MODELS

text: In MUSAE and AE models we have a set of parameters that we use for model evaluation. Our parameter settings listed in Table 2 are quite similar to the widely used general settings of random walk sampled implicit factorization machines (Perozzi et al., 2014; Grover & Leskovec, 2016; Ribeiro et al., 2017; Perozzi et al., 2017). Each of our models is augmented with a Doc2Vec (Mikolov et al., 2013a;b) embedding of node features – this is done such way that the overall dimension is still 128.

heading: D HYPERPARAMETER SETTINGS OF THE DOWNSTREAM MODELS

text: The downstream tasks uses logistic and elastic net regression from Scikit-learn (Pedregosa et al., 2011) for node level classification, regression and link prediction. For the evaluation of every embedding model we use the standard settings of the library except for the regularization and norm mixing parameters. These are described in Table 3.

heading: E HYPERPARAMETER SETTINGS OF COMPETING UNSUPERVISED EMBEDDING METHODS

text:
Our purpose was a fair evaluation compared to other node embedding procedures. Because of this each we tried to use hyperparameter settings that give similar expressive power to the competing
methods with respect to target matrix approximation (Perozzi et al., 2014; Grover & Leskovec, 2016; Perozzi et al., 2017) and number of dimensions.
• DeepWalk (Perozzi et al., 2014): We used the hyperparameter settings described in Table 2. While the original DeepWalk model uses hierarchical softmax to speed up calculations we used a negative sampling based implementation. This way DeepWalk can be seen as a special case of Node2Vec (Grover & Leskovec, 2016) when the second-order random walks are equivalent to the firs-order walks.
• LINE2 (Tang et al., 2015): We created 64 dimensional embeddings based on first and second order proximity and concatenated these together for the downstream tasks. Other hyperparameters are taken from the original work.
• Node2Vec (Grover & Leskovec, 2016): Except for the in-out and return parameters that control the second-order random walk behavior we used the hyperparameter settings described in Table 2. These behavior control parameters were tuned with grid search from the {4, 2, 1, 0.5, 0.25} set using a train-validation split of 80% − 20% within the training set itself.
• Walklets (Perozzi et al., 2017): We used the hyperparameters described in Table 2 except for window size. We set a window size of 4 with individual embedding sizes of 32. This way the overall number of dimensions of the representation remained the same.
• The attributed node embedding methods AANE, ASNE, BANE, TADW, TENE all use the hyperparameters described in the respective papers except for the dimension. We parametrized these methods such way that each of the final embeddings used in the downstream tasks is 128 dimensional.

heading: F HYPERPARAMETER SETTINGS OF COMPETING GRAPH NEURAL NETWORKS

text:
Each model was optimized with the Adam optimizer (Kingma & Ba, 2015) with the standard moving average parameters and the model implementations are sparsity aware modifications based on PyTorch Geometric (Fey & Lenssen, 2019). We needed these modifications in order to accommodate the large number of vertex features – see the last column in Table 1. Except for the GAT model (Veličković et al., 2018) we used ReLU intermediate activation functions (Nair & Hinton, 2010) with a softmax unit in the final layer for classification. The hyperparameters used for the training and regularization of the neural models are listed in Table 4.
Except for the APPNP model each baseline uses information up to 2-hop neighbourhoods. The model specific settings when we needed to deviate from the basic settings which are listed in Table 4 were as follows:
• Classical GCN (Kipf & Welling, 2017): We used the standard parameter settings described in this section.

heading: G CLASSIFICATION PERFORMANCE

text:
Datasets Cora Citeseer Pubmed
Weighted Micro Macro Weighted Micro Macro Weighted Micro Macro DeepWalk 0.832
±0.003 0.833 ±0.004 0.823 ±0.004
0.597 ±0.007
0.603 ±0.007 0.560 ±0.006
0.801 ±0.001
0.802 ±0.001 0.789 ±0.002
LINE2 0.775 ±0.004
0.777 ±0.004 0.768 ±0.005
0.529 ±0.006
0.542 ±0.006 0.486 ±0.005
0.798 ±0.001
0.799 ±0.001 0.785 ±0.001
Node2Vec 0.840 ±0.003
0.840 ±0.003 0.826 ±0.003
0.616 ±0.005
0.622 ±0.005 0.581 ±0.005
0.809 ±0.002
0.810 ±0.002 0.797 ±0.002
Walklets 0.843 ±0.003
0.843 ±0.003 0.827 ±0.003
0.624 ±0.005
0.630 ±0.006 0.590 ±0.005
0.815 ±0.001
0.815 ±0.001 0.804 ±0.002
TADW 0.819 ±0.004
0.819 ±0.004 0.804 ±0.005
0.725 ±0.004
0.734 ±0.004 0.685 ±0.004
0.862 ±0.002
0.862 ±0.002 0.863 ±0.002
AANE 0.793 ±0.006
0.793 ±0.006 0.777 ±0.006
0.728 ±0.005
0.733 ±0.004 0.693 ±0.005
0.867 ±0.001
0.867 ±0.001
0.867 ±0.002
ASNE 0.831 ±0.003
0.830 ±0.003 0.812 ±0.004
0.713 ±0.004
0.718 ±0.004 0.677 ±0.004
0.846 ±0.002
0.846 ±0.002 0.843 ±0.002
BANE 0.807 ±0.005
0.807 ±0.005 0.787 ±0.005
0.707 ±0.003
0.713 ±0.003 0.670 ±0.004
0.823 ±0.002
0.823 ±0.002 0.822 ±0.002
TENE 0.829 ±0.005
0.829 ±0.005 0.815 ±0.004
0.664 ±0.004
0.681 ±0.003 0.611 ±0.002
0.842 ±0.001
0.842 ±0.001 0.843 ±0.002
AE 0.835 ±0.005
0.835 ±0.005 0.815 ±0.006
0.730 ±0.005
0.739 ±0.005 0.688 ±0.006
0.839 ±0.002
0.839 ±0.002 0.840 ±0.002
AE-EGO 0.835 ±0.005
0.835 ±0.006 0.816 ±0.005
0.729 ±0.004
0.739 ±0.005 0.690 ±0.007
0.840 ±0.002
0.840 ±0.003 0.839 ±0.002
MUSAE 0.848 ±0.004
0.848 ±0.004 0.832 ±0.005
0.737 ± 0.004
0.742 ±0.004
0.706 ±0.004
0.853 ±0.001
0.853 ±0.001 0.854 ±0.002
MUSAE-EGO 0.849 ±0.004
0.849 ±0.004
0.833 ±0.004
0.736 ±0.004
0.741 ±0.004 0.706 ±0.004
0.850 ±0.002
0.851 ±0.002 0.850 ±0.002

heading: H ADDITIONAL TRANSFER LEARNING RESULTS ON THE TWITCH GRAPHS

heading: J LINK PREDICTION RESULTS ON SOCIAL AND WEB NETWORKS

heading: I REGRESSION RESULTS ON WIKIPEDIA PAGE-PAGE GRAPHS

title: MULTI-SCALE ATTRIBUTED NODE EMBEDDING