Multi-scale Attributed Node Embedding
Authors: Benedek Rozemberczki
Carl Allen
Rik Sarkar
Venue:  (2020)
Keywords: network embedding
graph embedding
node embedding
network science
graph representation learning

Abstract: 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 multi-scale 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.

Under review as a conference paper at ICLR 2020
MULTI-SCALE ATTRIBUTED NODE EMBEDDING
Anonymous authors
Paper under double-blind review
ABSTRACT
We present network embedding algorithms that capture information about a node from the local distribution over node attributes around it, observed over random walks following an approach similar to Skip-gram. Observations from neighbor- hoods of different sizes are either pooled (AE) or encoded distinctly in multi- scale approach (MUSAE). Capturing surrbute-neiihborrhe multiple scales is useful for diverse range of applications, including latent fea- ture identification across disconnected networks with similar attributes. We prove theoretically that matrices of node-feature pointwise mutual information are im- plicitly factorized by the embeddings. Experiments show that our algorithms are robust, computationally efficient and outperform comparable models on social, web and citation network datasets.
relationships over
INTRODUCTION
Node embedding is fundamental technique in network analysis that serves as a precursor to numer- ous downstream machine learning and optimisation tasks, e.g. community detection, network visu- alization and link prediction (Perozzi et al., 2014; Grover & Leskovec, 2016; Tang et al., 2015). Sev- eral recent network embedding methods, such as Deepwalk (Perozzi al., 2014), Node2 Vee (Grover & Leskovec, 2016) and Walklets (Perozzi et al., 2017), achieve impressive performance by learning the network structure following an approach similar Word2Vec Skip-gram (Mikolov et al., 2013b), originally designed for word embedding. In these works, sequences of neighboring nodes gener- ated 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 network have attributes (or features), their embeddings can be used to capture information about the attributes in their local neighbourhood. For social network, attributes might represent a person's interests, habits, history or preferences. The pattern of node attributes are often similar in neighborhood, and conversely, nodes with similar attributes 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 2018) leverage this additional information 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 node can be considered 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 la 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, 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 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. Em- beddings 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 the probability of encountering each (context) node on a random walk from each starting node (Qiu et al., 2018).

---

Under review as a conference paper at ICLR 2020
41
O:
{C:
(?:
10:
{
Facebook
B
)
Demsity
0.4
GitWehMI.
Twitch RU
0.2
Chumeleons Squircels
(4)
(4: )}
(a) Attributed example graph.
(b) Densification of the target matrix.
Figure 1: Phenomena affecting and inspiring the design of the multi-scan attributed network embed- ding procedure. In Figure la attributed nodes D and G have the same feature set and their nearest neighbours also exhibit equivalent sets of features, whereas features at higher order neighbourhoods differ. Figure 1b shows that as the order of neighbourhoods considered (r) increases, the product of the adjacency matrix power and the feature matrix becomes less sparse. This suggests that an implicit decomposition method would be computationally beneficial.
Our key contributions are:
1. to introduce the first Skip-gram gram style embedding algorithms that consider attribute distributions over local neighborhoods, both pooled (AF) and multi-scale (MUSAF), and their counterparts that attribute distinet 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 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 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 eval- uation at ht attps: / //gttttthubb wttp:/...oooomcccca////ee.e... www.
MUSAE.
2 RELATED WORK
Efficient unsupervised learning of node embeddings for large networks has seen unprecedented de- velopment 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 the embedding space. Our work falls under the last of these categories our goal is to learn similar latent representations for nodes with similar sets of features in their neighborhoods, both on 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 neigh- borhood 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 mu- tual information (PMT) matrix (Levy & Goldberg, 2014) obtained from a text corpus. This procedure inspired DeepWalt Walk (Perozzi et al., 2014), 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 DeepWalk implicitly factorizes a PMI matrix, which can be shown, based on the underlying first-order Markov process, to correspond to the mean of set of normal- be
ized adjacency matrix powers up given order (Qiu al., 2018). Such pooling of matrices suboptimal since neighbors over increasing path lengths (or scales) are treated equally or according to fixed weightings (Mikolov al., 2013a; Grover & Leskovec, 2016); whereas it has been found
2

---

Under review as a conference paper at ICLR 2020
that an optimal weighting may be task or dataset specific (Abu-El-Hajja 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 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 altributes (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 node's 's neigh- borhood 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 el- emental 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 mod- els, such as SINE (Zhang et al., 2018) and ASNE (Liao et al., 2018), implicitly factorize 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 non-negative matrix factor- ization problem in which node representations obtained from sub-tasks are used to regularize one another. AANE (Huang et al., 2017) uses 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 prod- uct of a normalized adjacency matrix power and 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 GC- NNs. Widely used graph convolutional layers, such as GCN (Kipf & Welling, 2017). GraphSage (Hamilton et al., 2017). GAT (Veličković 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.
ATTRIBUTED EMBEDDING MODELS
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, LL) be an undirected graph of interest where and L are the sets of vertices and edges (or links) respectively; and let FF be the set of all possible node features (i.e. attributes). We define F. S F as the subset of features belonging to each node E V. An embedding of nodes is a mapping : V + Rdd that assigns a d-dimensional representation g(v) (or simply gu) to each node v and is fully described by a matrix G E R xd Similarly, an embedding of the features (to the same latent space) is a mapping h F + Rd with embeddings denoted (f) (or simply l1y), and is fully described by matrix H E g|
3.1 ATTRIBUTED EMBEDDING
The Attributed Embedding (AE) procedure is described by Algorithm 1. We sample n nodes wis from which to start attributed random walks on G, with probability proportional to their degree (Line 2). From each starting node, node sequence of length 1 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/ nodes of the sequence termed source nodes Wy (Line 4). For each source node, we consider the following t nodes as target nodes (Line 5). For each target node tr, we add the tuple (wy. f) to the corpus D for each target feature f F wy+r (Lines 6 and 7). We also consider features of the source node f E adding each (wi+r: f) tuple to D (Lines 9 and 10). Running Skip-gram on ID with b negative samples (Line 15) generates the d-dimensional node and feature embeddings.
3

---

Under review as a conference paper at ICLR 2020
Data:
(V.L) Graph to be embedded.
[Fu]y Set made festure sets.
Number sequence camples.
Duta:
0
(V.L) - Graph be embodded.
1-
sqquenees
(2. Set aode teature secs
Contest
Number sequence sumples.
EEbbedding dimension.
[-
Length sequenses.
Comeent size.
Nodo enbolkings featune emboldings for L.....f.
Namber acgutive sumples.
Embedding dimension.
Number
sumples.
Resolt: Node eobeekling y
enbsllding
Pick My 6 accorrding to P(tr)) t (vol())
(stL Ma.... sns Sumple Nodes(Si,
for in ::E- (C-3-0
2.
Pick uy according to P(ws) dew(sss//vllgee
lue in 1: for Fu... do Adi the tuple (wy..) multiset 12 end
[ity (1g us) Sample Nodes/G mi
for in 1::7-tda do
for for f in To,..
for F.,, do Adi the tuple (Myen. multiset
Add (wg. mubtiset
and
end
cnd
Add (alyer- / multiset 12,
cnd
and
end
for
do
end
16
Create 12, by unitication D., and in.
SONS D, with negative samples and dimencions. Ousput sl. Ve V. and ky. Yf F UyF
Rus SCIS on 13 with negative samples and dimemiiass. Ootpur go, Vo an hy, Vf UV?.,
Algorithm I: AE sampling and training procedure
Algurithm 2: MUSAE sampling and training procedure
3.2 MULTI-SCALE ATTRIBUTED EMBEDDING
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 altributed node embeddings (MUSAE). The embedding component of a node ve V for a specific proximity E (1 is given by mapping g" V Rd/t (assuming divides d). Similarly, the embedding component of feature f E at proximity r is given by a mapping h" gd/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 starting nodes W1 with a probability proportional to node degree (Line 2) and, for each, sample a node sequence of length over (Line 3) according to either first second order random walk. For given window size f, we iterate over the first - (source) nodes wj of the sequence (Line 4) and for each source node we iterate through the (target) nodes W/tr that follow (Line 5). We again consider each target node feature f f #ソ+- but now add tuples (w,, f) to sub-corpus ID (Lines 6 and 7). We add tuples (wj+r./) to another sub-corpus D for each source node feature f f (Lines 9 and 10). Running Skip-gram on each sub-corpus ID, D DD= Dr with b negative samples (Line 16) output & ( (utputtoo)immmssioonn dimensiionll node and feature embeddings that are concatenated.
ATTRIBUTED EMBEDDING AS IMPLICIT MATRIX FACTORIZATION
Levy & Goldberg (2014) showed that the loss function of Skip-gram with negative sampling (SGNS) is minimized if the embedding matrices factorize matrix of pointwise mutual information (PMI) of word co-occurrence statistics. Specifically, for a word dictionary V with V = SGNS (with negative samples) outputs two embedding matrices W. C R such that Vw, cEV:
w. R log
#ww.c)D [w)
logb,
where #(w, c). # (w), #(c) denote counts of word-context pair (w, c), w and e over a corpus D; and word embeddings was C. ERd are columns of W and C corresponding to w and e respectively. Considering #(w) #(c) #(w.c) as empirical estimates of p(w)) p(c) and p(w,c) respectively shows:
1 [D
C PMI( c) log ll..ev
bl..bl...er
icc an approximate low-rank factorization of shifted PMI matrix (low rank since typically d n)).).
Qiu 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 Deep where random walks are first-order Markov, the joint probability distributions walk can be expressed in closed form. A closed form then follows for the factorized PMI matrix. We show that AE and MUSAF implicitly perform analogous matrix factorizations.
nodes at different stages of random
4

---

Under review as a conference paper at ICLR 2020
Notation: A denotes the adjacency matrix and D e R the diagonal degree matrix of a graph G, ie. D Dw, = deg( w) = Ev Aw,v- We denote the volume of g by Lv,w A We define the binary attribute matrix F f0, 111 by Fu.s- SeF.. Yu V f.F. For ease of notation, let P D-1 A and E diigg DF), where diag indicates diagonal matrix.
Interpretation: Assuming is ergodic: p(w) deg(w) w E V is the stationary distribution
nodes, i.e. c diag(p(w)): and c is the stationary joint distribution over consecu- tive nodes p(u,, mz+1). F can be considered a Bernoulli parameter describing the probability p(flw) of observing a feature f at a node w and so c=1 DF describes the stationary joint distri- bution p(f. wi) over nodes and features. Accordingly, P is the matrix of conditional distributions p(w5+ +1 [[0y); and E is diagonal matrix proportional to the probability of observing each feature at whereas p(w) necessarily must).
the stationary distribution p(f) (note that p(f) need not
4.1 MULTI-SCALE CASE (MUSAE)
We know that the SGNS aspect of MUSAE (Algorithm 2, Line 17) minimized when the learned embeddings gh hy satisfy gi T hy = log
(( log Vu E V, f.F. Our aim to express #( #())
this factorization in terms of known properties of the graph G and its features.
The empirical statistics of node-feature pairs obtained from random walks give unbiased estimates of joint probabilities of observing feature f E F. r steps (i) after; or (ii) before node E V, as given by:
Lemma 1.
#(w.f) plim 14000 121
#(w.f) ( DP
=c
plim 1000
(F
[B
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 r steps either side of node v E V, given by:
plim
#(arf).
[ = =c (DP
10000
Proof. See Appendix.
Marginalizing gives unbiased estimates of stationary probability distributions of nodes and features:
plim #(w) 1 [..
deg(w)
and
plim 1-000
#
deg(w)
E
D.
FEF
Theorem 1. MUSAE embeddings approximately factorize the node mode-feature PMI matrix:
log (c (cP'FE-L) log b, for 1,,,,
Proof.
# (ww D- #()+ (mn)
#ww Dr
#
#(w)e
[.pl
Dr
B ((cD (c DP" F ()E w.f
cPP (AP'Fl FE Dw.ff
5

---

Under review as a conference paper at ICLR 2020
4.2 POOLED CASE (AE)
Lemma 3. The empirical statistics of node-feature pairs learned by the AE algorithm give unbiased estimates of mean joint probabiliiiess over different path lengths follows:
plim #(w 10000
(
P') w.
Proof. By construction, Er [. # ()= #(w,
(w,,), Dr. Vr. and
so [D& =t [DD] Combining with Lemma 2, the result follows.
Theorem 2. AE embeddings approximately factorize the pooled node-feature matrix:
log (
P")FE
-log b.
Proof. The proof is analogous to the proof of Theorem
Remark 1. DeepWalk is corner case of AE with IvI
AE if each node has single unique feature. Thus E diag(1" DI)= and, by Theorem 2, DeepWalk's embeddings factorize log (#(E==) P PO)D-1) log b, previously noted by Qiu et al. (2018).
That is, DeepWalk is equivalent
Remark 2. Walklets is corner case of MUSAE with F F=
Thus, for 1,, the embeddings of Walklets factorise log (cP'D-=) log b.
Remark 3. Appending an identity matrix the feature matrices F of AE and MUSAE (denoted [F; Il) adds unique feature to each node, The resulting algorithms, named AE-EGO and MUSAE- EGO, learn embeddings that, respectively, approximately factorize the mode-feature PMI matrices:
log (c Pe [F;1]E= log (r. and
log (
Σ P') PPIE logb.
4.3 COMPLEXITY ANALYSIS
Under the assumption of a constant number of features source node and first-order attributed random walk sampling, the corpus generation has runtime complexity of O(n D(n/tz) sinltt//y), where
= Epey |F,l the total number of features across all nodes (including repetition) and y V single asynchronous
the number of nodes. Using negative sampling, the optimization runtime gradient descent epoch on AE and the joint optimization runtime of MUSAE embeddings is described by dl Lx/g)) If one does truncated walks from each source node, the corpus generation complexity is Opp 1 L a)) and the model optimization runtime is P(bdpylia Our later runtime experiments in Section will underpin optimization runtime complexity discussed above.
Corpus generation has a memory complexity of On Lt Ltz/v) while the same when generating truncated walks per node has a memory complexity of O(p y lt). Storing the parameters an AE embedding has memory complexity of Oly d) and MUSAE embeddings also use O d) memory.
EXPERIMENTAL EVALUATION
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 al., 2018). Across all experiments settings our own model, competing unsupervised methods and graph neural networks these are respectively listed in Appendices C, and F.
the same hyperparameter

---

Under review as a conference paper at ICLR 2020
5.1 NODE CLASSIFICATION
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 fixed size train-test split to compare against various embedding methods and competitive neural network architectures.
5.1.1 K-SHOT LEARNING
In this experiment we take & randomly selected samples per class, and use the attributed node em- beddings train logistic regression model with l2 regularization and predict the labels 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 miero averaged Fi scores to compare our own methods with other unsupervised node embedding procedures. We varied 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 MUSAF and AE embeddings have little gains in terms of miero Fi score when additional data points are added to the training set when larger than 12. This implies that method is data efficient. Moreover, MUSAE-EGO and AE-EGO have 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.
Facebook Paye-Pige
Githab Machine Letnnng
Poctugal
0.50
0.80
1ee mico 1; soore
0.
Toe niom F. soore
0.20
0.00
3
0.00
0.50
0.30
0.30
0.00
0.30
0.30
12
Training samples per class
Triining samples per class
Truining samples per class
DADW
AANE
ASNE
BANE
TENE
AE
MUSAL
AB EGO
MUSAL EGO
Figure 2:
Node classification k-shot learning performance function of training samples per class evaluated by average micro Fi scores calculated from a 100 seeded train-test splits.
5.1.2 FIXED RATIO TRAIN-TEST SPLITS
In this series of experiments created 100 seeded train test splits of nodes (80% train 20% test) and calculated weighted, micro and macro averaged Fi 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 compa- rable. 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 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 GitHuu 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 F, this relative advantage over best performing model variant is the largest with 4.67% on the Facebook network, and only 0.1 % on Twitch Portugal.
One can make four general observations based with the classification tasks compared to pooled ones; (ii) the addition of the nodes in the ego aug- mented models the feature sets does not help the performance when large amount of labeled
results (i) multi-scale representations can help
7

---

Under review as a conference paper at ICLR 2020
training data is available; (iii) based the standard errors supervised neural models do not nec- essarily 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 neighbour- hoods have poor performance.
5.2 TRANSFER LEARNING ON TWITCH SOCIAL NETWORKS
Neighbourhood based methods such as DeepWalk (Perozzi al., 2014) are transductive and the function used to create the embedding cannot map nodes that are not connected to the original graph the latent space. However, vanilla MUSAE and AE are inductive and can easily map nodes the embedding space if the attributes across the source and target graph are shared. This also means that supervised models trained on embedding of a source graph are transferable. Importantly those attributed embedding methods such AANE or ASNE that explicitly use the graph are unable to do this transfer.
MUSAE transfer to users
MUSAE transfer EN users
MUSAE transfer to users
Micro F; Score
Micro Score
Micro H; Score
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
DE
EN
ES
FR
PT
DE
ES
FR
PT
RU
DE
EN
FR
PT
RU
AE transfer to DE users
AE transfer to EN users
AE transfer to ES users
Micro Fi Score
Micro F; Score
Micro Fi Score
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
EN
ES
FR
PT
DE
ES
FR
PT
RU
DE
EN
FR
PT
RU
Non transfer performance
Random guessing performance
Figure 3: Mean micro Fi scores and standard errors calculated from 10 transfer learning runs with MUSAE and AE on the Twitch graphs using Germany, England and Spain as target for the transfer. The blue reference line denotes the test performance on the target dataset in non transfer learn- ing scenario (standard hyperparameter settings and split ratio). The red reference line denotes the performance of random guesses.
Using the disjoint Twitch country level social networks (inter country edges are not present) we did transfer learning experiment. First, we learn an embedding function given the social network from 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 Fj score based on 10 experimental repetitions. These averages with standard error bars are plotted for the Twitch Germany, England and Spain datasets 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 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 effective in terms of miero Fi score. Transfer from English users to German ones considerably improves performance, and the other way around there 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.
5.3 REGRESSION ON WIKIPEDIA GRAPHS
We created embeddings of the Wikipedia webgraphs with all of our methods and the unsupervised baselines. Using 80% train 20% test split we predict the log of average traffic for each page using
8

---

Under review as a conference paper at ICLR 2020
elastic net model. The hyperparameters of the downstream model are available in Appendix D. In Table Appendix we report average test R² and standard error of the predictive performance over 100 seeded train-test splits. Our key observation mark neighbourhood preserving and attributed node embedding methods, with the strongest MUSAF variant outperforming the best baseline between 2.05% and 10.03% (test R²); (ii) that MUSAE sig- nificantly outperforms AE by between 2.49% and 21 21.64% (test R(²); and (iii) the benefit of using the vertices features (ego augmented model) can improve the performance of embeddings, but appears to be dataset specific phenomenon.
(i) that MUSAE outperforms all bench-
5.4 LINK PREDICTION ON WEB GRAPIIS AND SOCIAL NETWORKS
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 4 norm and the element- wiise l2 norm of vectors. Finally, we created 100 seeded 80% train 20% test splits and used logistic regression to predict whether edge exists.
We compared to attributed and neighbourhood based embedding methods and average AUC scores are presented Tables and of Appendix Our results show that Walklets (Perozzi et al., 2017) the multi-scale neighbourhood based embedding method materially outperforms every other method on most the datasets and attributed embedding methods generally do poorly in terms AUC compared to neighbourhood based ones.
5.5 SCALABILITY
In order to show the efficacy of algorithms run series of experiments synthetic graphs where we are able to manipulate the input size. Specifically, we look at the effect changing the number of vertices and features per vertex. Our detailed experimental setup was follows. Each point in Figure 4 is the mean runtime obtained from 100 experimental runs on Erdos-Reny graphs. The base graph that manipulated had 2 nodes, 2 edges and the same number of unique features per node uniformly selected from feature set of 2 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 cores and included a dashed line as the linear runtime reference in each subfigure.
MUSAE
AE
MUSAE
Lng, Rumiine secouds in
lany Runtine in soconnds
Iogy Rumtine it soconds
Ing Rumime
Jug Average number Stunures
Arerage number Soutares
Number modes
Number of modes
Figure 4: Optimization time as a function of average feature count / number of vertices.
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 linear behaviour. Doubling the imput size simply results in doubled optimization runtime. In addition, if one interpolates linearly from these results it comes that a network with I million nodes, edges per node, 8 unique features per node can be embedded with MUSAE commodity hardware in less than 5 hours. This

---

Under review as a conference paper at ICLR 2020
interpolation assumes that the standard parameter settings proposed in Appendix C and 4 cores were used for optimization.
6 DISCUSSION AND CONCLUSION
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 algo- rithms 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) 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, out- perform 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 at- tributed node embedding procedures (Yang al. (2015); Liao al. (2018); Huang al. (2017); Yang et al. (2018); Yang & Yang (2018)).
Our proposed embedding models are differentiated from other methods in that they encode fea- ture 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.
REFERENCES
Sami Abu-El-Haija. Bryan Perozzi, Rami AI-Rfou, and Alexander A Alemi. Watch your step: Learning node embeddings via graph attention. In S. Bengio, H. Wallach, H. Larochelle, K. Grau- man, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 9198-9208. 2018.
Sami Abajal-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. MixHop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In Proceedings of the 36th International Con- ference on Machine Learning (ICML), pp. 21-29, 2019.
Nesreen K Ahmed, Ryan Rossi, John Boaz Lee, Xiangnan Kong, Theodore L Willke, Rong Zhou, and Hoda Eldardiry. Learning role-based graph embeddings. arXiv preprint arXiv:1802.000 2018.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In Proceedings of the 24th ACM International on Conference Informa- tion and Knowledge Management, pp. 891-900, 2015.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery &#38; Data Mining (KDD), pp. 257-266 2019.
Matthias Fey and Jan F. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NIPS) 30, pp. 1024-1034. Curran Asso- ciates, Inc., 2017.
Xiao Huang, Jundong Li, and Xia Hu. Accelerated attributed network embedding. In Proceedings of the 2017 SIAM International Conference on Data Mining, pp. 633-641. SIAM, 2017.
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irreg- ular graphs. SIAM Journal scientific Computing, 20(1):359-39) -922, 1998.
10

---

Large-scale Under review as a conference paper at ICLR 2020
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR). 2017.
Johannes Kliepera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations (ICLR), 2019.
Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. In Ad- vances neural information processing systems, pp. 2177-2185, 2014.
Lizi Liao, Xiangnan He, Hanwang Zhang, and Tat-Seng Chua. Attributed social network embed-
ding. IEEE Transactions on Knowledge and Data Engineering, 30(12):2257-2277, 2018.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word represen- tations in vector space. 2013a.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed represen- tations of words and phrases and their compositionality. In Advances neural information pro- cessing systems, pp- 31 11-31 2013b.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th International Conference on Machine Learning (ICML), pp. 807-814,
2010.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-leam: Machine learming in python. Journal of machine learning research, 12(0ct):2855-2830 2011.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining., 2014.
Bryan Perozzi, Vivek Kulkarni, Haochen Chen, and Steven Skiena. Don't walk, skip!: Online learning of multi- scale network embeddings. In Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017, pp. 258-266 2017.
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pp. 459-467, 2018
Leonardo F.R. Ribeiro, Pedro H.P. Saverese, and Daniel R. Figueiredo. Struc2vec: Learning node representations from structural identity. In Proceedings of the 23rd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '77, pp. 385-394, 2017.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurIPS 2018, 2018
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: information network embedding. In Proceedings of the 24th International Conference on World Wide Web, pp. 1067-1077, 2015.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning (ICMI., pp. 6861-6871, 2019.

---

Under review as a conference paper at ICLR 2020
Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Y Chang. Network representation learning with rich text information. IJCA,, pp. 2111-2117, 2015.
Hong Yang, Shirui Pan, Peng Zhang. Ling Chen, Defu Lian, and Chengqi Zhang. Binarized tributed network embedding. In 2018 IEEE International Conference on Data Mining (ICDM), pp. 1476-1188. IEEE, 2018.
Shuang Yang and Bo Yang. Enhanced network embedding with text information. In 2018 24th International Conference on Pattern Recognition (ICPR), pp. 326-331. IEEE, 2018.
Daokun Zhang, Jie Yin, Xingquan Zhu, and Chengqi Zhang. Sine: Scalable incomplete network embedding. In 2018 IEEE International Conference on Data Mining (ICDM), pp. 737-746. IEEE, 2018.
A PROOFS
Lemma 1. The empirical statistics of node-feature pairs obtained from random walks give unbiased estimates of joint probabilities of observing feature E steps (i) after; or (ii) before node E V, as given by:
# #(w.f)
#(w.f)
plim
= (DPPF
plim
= (FTT))
DP"))
10000
1+000
Proof. The proof is analogous to that given for Theorem 2.1 in Qiu al. (2018). We show that the computed statistics correspond to sequences of random variables with finite expectation, bounded variance and covariances that tend zero as the separation between variables within the sequence tends to infinity. The Weak Law of Large Numbers (S.N. B...ntettii))) then guarantees that the sample mean converges to the expectation of the random variable. We first consider the special case 1, i.e. we have a single sequence ".,..., generated by a random walk (see Algorithm 1), For particular node-feature pair (w, f), we Y., E {l,..., - l), be the indicator function the event w, and Fitr. Thus, have:
#(w p
Y
the sample average of the Y.s. We also have:
E|] deg(w) (P" F) - (DP" F) F
(DP"F).)
E E|YY Prob WE w. Fitri -
E s+rl
deg(w)
diag(F.))
pi- (it(it))
p F
p(w;=u)) p(ua (o p(SE (1 p(uy =
p(fEF)i /
p(u;=u (w)
for j > itr. This allows us to compute the covariance:
deg(w) Cov(Y,, Yj) = E[V,Y,] - EYY
p diag ( F.j) (pi-(++) des(w) F.f,
(3)
e
tends to 0 1-100
where 1 is vector of ones. The difference term (indicated) tends to zero j oo since then p(u, w/ ((+r) tends the stationary distribution p(w) deg(w)) regardless of w Thus, applying the Weak Law of Large Numbers, the sample average converges in probability to the expected value, i.c.:
1-t
1-t Σ E.J ()D"F)
# #ww
Yi
D
#(w.f)+ |=_| with expectation term (F DP*) In both cases, the argument readily extends to the general setting where n > with suitably defined indicator functions for each of the random walks (see Qiu al. (2018)).
similar argument applies to
12

---

Under review as a conference paper at ICLR 2020
Lemma 2. Empirical statistics of node-feature pairs obtained from random walks give unbiased estimates of joint probabilities of observing feature f F.F. r steps either side of node u V, given by:
plim
#(m.f).
(DP'F)))
10000
Proof.
#(w,5)
#(w+)
+
Dzl
|B,1
#(w,5)
#mm, [2-]
4 3 F) mf (F DP") s.m)
(DP'F P DF wif
+ ( DA' w.
(DDP' +D(D D(D-IAAY))) w.
((DP"F)
The final step follows by symmetry A, indicating how the Lemma can be extended to directed graphs.
B DATASETS AND DESCRIPTIVE STATISTICS
Our method evaluated variety of social networks and web page-page graphs that col- lected from openly available API services. In Table 1 we described the graphs with widely used statisties with respect size, diameter, and level of clustering. We also included the average num- ber 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: / htt///gtttt /gittub..../ com/ cenm/icrr2200000 /
Table I: Descriptive statistics of the networks used in our experimental evaluation.
Clustering Coefficient
Average Feature
Unique Features
Dataset
Nodes
Edges
Diameter
Density
Facebook Page-Page
22,470
171,002
15
0.232
0.001
14.000
4,714
GitHub Web-ML
37,700
289,003
7
0.013
0.001
18.312
4,005
Wikipedia Chameleon
2,277
31,421
11
0.314
0.012
21.547
3,132
Wikipodia Crocodile
11,631
170,918
11
0.026
0.003
75.161
13,183
Wikipedia Squirrel
5,201
198,493
10
0.348
0.015
26.474
3,148
Twitch DE
9,498
153,138
7
0.047
0.003
20.397
2,545
Twitch EN
7,126
35,324
10
0.042
0.002
20.799
2,545
Twitch ES
4,648
59,382
9
0.084
0.006
19,391
2,545
Twitch FR
6,549
112,666
7
0.054
0.005
19.758
2,545
Twitch PT
1,912
31,299
7
0.131
0.017
19.944
2,545
Twitch RU
4,385
37,304
9
0.049
0.004
20.635
2,545
B. FACEBOOK PAGE-PAGE DATASET
This webgraph is 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 summarize the purpose of the site. This graph was col- lected 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, tele- vision shows and companies. As one can see Table 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.
13

---

Under review as a conference paper at ICLR 2020
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 the graph is binary node classification one has to predict whether the GitHub user is a web learning developer. This target feature was derived from the job title of each user. As the descriptive statistics show in Table this is the largest graph that use for evaluation with the highest sparsity.
machine
B.3 WIKIPEDIA DATASETS
The datasets that we use to perform node level regression are Wikipedia page-page networks col- lected on three specific topics:
chameleons, crocodiles and squirrels. In these networks nodes 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 vari- able. Table 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 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, loca- tion 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 these networks is binary node classification explicit language.
has to predict whether streamer
C STANDARD HYPERPARAMETER SETTINGS OF OUR EMBEDDING MODELS
In MUSAE and AE models we have a set of parameters that we use for model evaluation. Our param- eter 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 Doc2Vec (Mikolov al., 2013a;b) embedding of node features this is done such way that the overall dimension still 128.
Table 2: Standard hyperparameter settings of the AE and MUSAE embeddings.
Parameter
Value
Notation
Dimensions
128
d
Walk length
80
[
Number of walks per node
10
p
Number of epochs
k
Window size
t
Initial learning rate
0.05
Omaz
Final learning rate
0,025
Omii
Negative samples
b
D HYPERPARAMETER SETTINGS OF THE DOWNSTREAM MODELS
The downstream tasks uses logistic and elastic net regression from Seikit-learn (Pedregosa et al., 201 for node level classification, regression and link prediction. For the evaluation of every em- bedding model we use the standard settings of the library except for the regularization and norm mixing parameters. These are described in Table 3.
E HYPERPARAMETER SETTINGS OF COMPETING UNSUPERVISED EMBEDDING METHODS
Our purpose was a fair evaluation compared to other node embedding procedures. Because this each tried use hyperparameter settings that give similar expressive power the competing
14

---

Under review as a conference paper at ICLR 2020
Table 3:
Standard hyperparameter settings of the downstream logistic and elastic net regression models that use the embeddings for classification, link prediction and regression.
Parameter
Value
Notation
Regularization coefficient
0.01
X
Norm mixing parameter
0.5
methods with respect to target matrix approximation (Perozzi et al., 2014; Grover & Leskovec, 2016; Perozzi al., 2017) and number of dimensions.
Deep Walk (Perozzi et al., 2014): We used the hyperparameter settings described in Table 2. While the original DeepWalk model uses hierarchical softmax speed up calculations we used negative sampling based implementation. This way DeepWalk can be seen special case of Node2 Vec (Grover & Leskovec, 2016) when the second-order random walks are equivalent to the firs-order walks.
LINE₂ (Tang et al., 2015): We created 64 dimensional embeddings based on first and sec- ond order proximity and concatenated these together for the downstream tasks, Other hy- perparameters are taken from the original work.
Node2Vec (Grover Leskovee, 2016): Except for the in-out and return parameters that control the second-order random walk behavior we used the hyperparameter settings de- scribed Table 2. These behavior control parameters were tuned with grid search from the (4. 2, 1, 0.5, 0.25) set using 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 the down- stream tasks is 128 dimensional.
F HYPERPARAMETER SETTINGS OF COMPETING GRAPH NEURAL NETWORKS
Each model was optimized with the Adam optimizer (Kingma & Ba, 2015) with the standard mov- ing average parameters and the model implementations are sparsity aware modifications based on PyTorch Geometric (Fey & Lenssen, 2019). We needed these modifications in order to accommo- date the large number of vertex features (Veličković et al., 2018) we used ReLU intermediate activation functions (Nair & Hinton, 2010) with softmax unit in the final layer for classification. The hyperparameters used for the training and regularization of the neural models are listed Table 4.
the last column in Table 1. Except for the GAT model
Table 4: Hyperparameter settings used for training the graph neural network baselines.
Parameter
Value
Epochs
200
Learning rate
0.01
Dropout
0.5
(2 Weight regularization
0.001
Depth
2
Filters per layer
32
Except for the APPNP model each baseline uses information up 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.
15

---

Under review as a conference paper at ICLR 2020
GraphSAGE (Hamilton al., 2017): We utilized graph convolutional aggregator the sampled neighbourhoods, samples 40 nodes per source, and standard settings.
CAT (Veličković et al., 2018): The negative slope parameter of the leaky ReLU function was 0.2, we applied a single attention head, and used the standard hyperparameter settings.
MixHop AAbu-El-Halj et al., 2019): We took advantage of the 0th, 1st and 2nd powers of the normalized adjacency matrix with 32 dimensional convolutional filters for creating the first hidden representations. This was fed to a forward layer classify the nodes.
ClusterGCN (Chiang et al., 2019): Just as Chiang et al. (2019) did, we used the METIS procedure (Karypis & Kumar, 1998). We clustered the graphs into disjoint clusters, and the number of clusters was the same as the number node classes (e.g. in case the Facebook page-page network we created clusters). For training we used the earlier described setup.
APPNP (Kliepera et al., 2019): The top level feed-forward layer had 32 hidden neurons, the teleport probability pagerank calculation.
0.2 and used 20 steps for approximate personalized
SGCONV (Wu al., 2019): We used the 2nd power the normalized adjacency matrix for training the classifier.
G CLASSIFICATION PERFORMANCE
Table 5: Node classification test performance evaluated by weighted, micro and macro Fi scores calculated from 10 seeded train-test splits. We included standard errors the scores and used 80% of nodes for training 20% of nodes for testing. Red numbers denote the best performing node embedding method.
Datasets
Cora
Cileseer
Pubmed
Weighted
Micro
Macro
Weighted
Micro
Macro
Weighted
Micro
Macro
Deep
0,832
0.833
0.823
0.597
0.603
0.360
0.801
0.802
0.789
20.005
E0.004
10.004
20.007
20,007
20.006
10.001
-0.001
20.002
LINEa
0.775
0.777
0.768
0.542
0.486
0.798
20.006
-0.001
20.001
Node2Vee
0.840
0.840
0,826
0.616
0.622
0.581
0.809
0.810
0.797
Walklets
0.843
0.843
0.827
0 0.624
0.630
0,590
0.815
0.815
0 808
20.003
20
10:006
20.003
10.001
20.001
2 20.002
0.683
20.004
+0.000
+0.005
20.004
10.004
20.004
+4.0022
6.002
2 0.002
AANE
0.793
0.793
0.777
0.728
0.733
0.693
0.867
0.867
0.867
ASNE
0.831
0.830
0.812
0.713
0.718
0.677
0.846
0.846
0.843
10.003
+0.
D. 10.004
+0,004
+0.004
+0.002
-0.002
BANE
0.807
0,807
0.787
0. 0.707
0.713
0.670
0,823
0.823
0.822
20.005
10.005
10.005
ZE0 0X3
220.00
20.004
10.002
-0.002
2 0-002
100.00
10.004
0.004
001
009
AE
0.835
0.835
0.815
0.730
0.739
U.688
0.839
U.839
0 840
20.005
10.005
-000000
20.005
20.006
4.0.00
= -0.002
2
AE-EGO
0,835
0.835
0.816
0.729
0.739
0.690
0.840
0,840
0.839
20,005
+0.006
#0.005
=0.00
#0.008
+0,007
+0.002
-0.009
0- 000002
MUSAE
20,004
1.0.00
$.0.00
0.804
210.00
0.004
+.00011
00.001
2 0.00012
MUSAE-EGO
0.849
0.849
0.833
0.736
0.741
0.706
0.850
0.851
0.850
16

---

Under review as a conference paper at ICLR 2020
Table 6: Node classification test performance evaluated by weighted, miero and macro Fi scores calculated from 10 seeded train-test splits. We included standard emrors of the scores and used 80% of nodes for training 20% of nodes for testing. Red numbers denote the best performing node embedding method and blue ones denote the best performing supervised graph neural network.
Datasets
Facehook
Page-PPee 'age
Gitlinh WebMIL.
Foringal
Weighted
Mícro
Macro
Weighted
Micro
Macro
Weighted
Micro
Macro
DeepWalk
0.861
0.863
0.848
0.852
0.858
0.801
0.650
0.672
0.594
LINE2
0.874
0.875
0.862
0,855
0.858
0,800
0.636
0.670
0.571
20.001
10.001
10.001
20.001
20.001
20.002
10.008
=0.006
20:006
Node2Vee
0,889
0.890
0.880
0.853
0.859
0,802
0.605
0.686
0.612
20.001
20.001
20.001
20.00
20.001
20.001
20.001
20.001
20:001
Walklets
0.886
0.875
0.560
0.599
20.001
10.001
10:001
20.001
20.002
10
TADW
0,760
0.765
0.740
0.650
0.748
0,528
0.459
0,659
0.406
#0.00
=0
000000
00.003
AANE
0.793
0.796
0.775
0.848
0.856
0. 794
0.636
0.661
0.577
+0.001
+0.001
#0.001
+0.001
+0,001
+00002
+ +0.008
0.006
+0 000006
0.539
20.001
1000011
20.001
2.00011
20.000
20.002
1:0.006
2:000
4.00
BANE
0,868
0.868
0.859
0,711
0.762
0.576
0.644
0.664
0.587
TENE
0.724
0.731
6.999
0.842
0.850
0.785
0.613
0.664
0.536
20.002
10.002
E0.
20.001
20.001
20.002
10.000
-0.006
20.006
AE
0,887
0.888
0.858
0.863
0,807
0.598
20,001
+00001
#0.001
00.001
+0,001
#0,001
+0.005
-0.004
=0 #0.000
AE-EGO
0.898
0.899
0,890
0.857
0.863
0.807
0.652
0.671
0,399
MUSAE
0,886
887
0.877
0,859
0.864
0.810
0.654
0.672
0. 1,600
20.001
#0
#0.
8491
20000
2000
000006
MUSAE-EGO
0.893
0.894
0,881
0.859
0.864
0.810
0.655
0.671
O. 0.604
+0.001
#0.001
#0.001
1.00
10.00
HU00
+0.008
00.002
+ 000000
GCN
0.928
0.859
0. 0,865
0,809
0.677
000001
GraphSAGE
0,812
0.814
0.795
0,848
0.854
0.791
0.618
0,631
0 0,563
GAT
0.918
0.919
0,912
0.856
0.864
0,803
0.648
0.678
0.588
20,003
20.001
20. 001
E 001
20.
200 00/00
4. 008
-0.007
E 000
MixHop
0,940
0.937
0.847
0.85
0,800
0.630
0.576
24000
1-0.001
2. 50,000
+0,001
00000
+00.03
-0.004
= 00.003
ClusterGCN
0.937
0,937
0.934
0.853
0.859
0,807
0.634
O.
000
000
APENP
0.938
0.938
0.935
0,860
0.868
0.811
0.683
0.702
0.623
20,001
#0. 001
B482
110.0
1'00999
20812
K.800
SGCONY
0.832
0.836
0.812
0.816
0.829
U,747
0.652
0.663
0. 0.604
+0.0002
#0.002
#0.002
00.00L
+0.001
000002
+00.00
0.0003
0. 00.004
H ADDITIONAL TRANSFER LEARNING RESULTS ON THE TWITCH GRAPHS
MUSAF transfer users
MUSAF transfer PT users
MUSAF transfer to RU
Micro Fi Scoore
0.8
Micro Score
Micro Fi Score
0.6
0.6
0.6
0..4
0.4
0.4
0.2
0.2
0.2
4
DE
EN
ES
PT
RU
DE
EN
ES
FR
RU
DE
EN
ES
FR
PT
AE transfer to FR users
AE transfer to PT users
AE transfer to RU users
Micro Fi Score
0.8
Micro Fj Score
0.8
Micro Fi Score
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0-
DE
EN
FS
PT
RU
DE
FN
ES
FR
RU
DF
EN
ES
FR
PT
Non transfer performance
Random guessing performance
Figure 5: Mean micro F, scores and standard enrors calculated from 10 transfer learning runs with MUSAF and AE on the Twitch graphs using France, Portugal and Russia as targets for the transfer.
The blue reference line denotes the test performance the target dataset in transfer learn- ing scenario (standard hyperparameter settings and split ratio). The red reference line denotes the performance of random guesses.
17

---

Under review as a conference paper at ICLR 2020
I REGRESSION RESULTS ON WIKIPEDIA PAGE-PAGE GRAPHS
Table 7: Average test R values and standard errors on the Wikipedia traffic prediction tasks. Red numbers denote the best results on each page-page network.
Datasets
Wikipedia Chameleons
Wikipedia Crocodiles
Wikipedia Squirrels
Method
Deep
0.375
0.553
0.170
20:004
20.001
20.002
LINE2
0,381
0,586
0,232
20.003
10.001
10,002
Node2Vee
0,414
0.574
0.174
10.001
Walklets
0.426
0.625
0.249
+0.003
+0.001
+0,002
TADW
0.527
0.636
0.271
0.0003
4.00011
#:0,00
AANE
0.598
0.732
0,287
10.007
10.002
1.00002
ASNE
0.410
0.572
0,229
#0.009
+0.003
000000
BANE
0.464
0.617
0.168
10.001
TENE
0.494
0.701
0.321
20.02
20.003
20.007
AE
0.6642
0.743
0.291
AE-EGO
0.644
0.732
0,283
$0.009
+0.002
00000
MUSAE
0.658
0.736
0.338
+00004
20.003
00.00
MUSAE-EGO
0,653
0.747
0.354
J LINK PREDICTION RESULTS ON SOCIAL AND WEB NETWORKS
Table 8: Link prediction results average AUC on the test set using attributed embeddings and logistic regression. We created 100 seeded splits (80% training 20% test). Standard emrors of AUC are included below. Red denotes the best performing embedding model considering both neighbourhood based and attributed methods. We used 4 element- wise operators to create features.
Datasets
Facebook Page-Page
Gilllub Web-MI.
Twitch
Twitch Germany
Wikipedia Chameleons
Wikipedia Crocodiles
Operator
Method
Spain
DeepWalk
0.526
0.550
0.568
0.575
0.635
0.661
00.
14.001
10.309
20.000
20.002
20.00
LINE,
0.517
0.55
0.540
0.544
0.627
0.708
10.003
Average
Node2Vec
0.534
0.573
0.575
0.584
0.611
0.669
20
20.000
10:012
20.000
2 000009
10 20-007
Walklets
0.518
0.552
0.541
0.545
0.635
0.716
=0. 008
$3.003
10.006
20 0000
20.016
20. 20.003
DeepWalk
0.981
0.799
0.781
0.750
0.974
0.966
10 20.001
10.001
10.002
20 060
-0 000
10 001
LINE,
0.979
0.899
0,843
0 1.755
0.939
0,938
#0.001
#0.001
#0.003
=0 20.001
=0.003
200 001
Hadamard
Node2Vec
0.982
0.829
0,810
D.780
0.979
0.973
20.001
10.
2 003
10,00
200 001
Walklets
0.984
0.925
0.873
0.819
0.966
0.980
+0.001
F0.063
+0.001
-0.004
2100
Delk
0.921
0.658
0.723
0.711
0.950
0.896
20.00
20.001
10.004
2000002
20.002
20.001
LINE,
0.924
0.913
0,882
0.855
0.922
0.930
20.001
10.002
10.002
20 20.000 001
20.003
000
4 Norm
Node2Vee
0.725
0.761
0.745
0,913
20.001
20.001
10.004
2. 000001
20.003
20.001
Walklets
000001
20.001
+0062
20.001
20.004
40.001
Delp
0.731
0.717
+0.001
#0.001
+0.004
20.000
=0.002
+0.000
0.855
20.001
13.001
10.002
2.00001
20.003
10.001
Norm
Node2Vec
-0.002
+0.001
+0.007
+0.001
0.002
+0.001
Walklets
20.000
$.0.001
20.002
2.0.002
20.005
20.001
18

---

Under review as a conference paper at ICLR 2020
Table 9: Link prediction results average AUC on the using neighbourhood based embed- dings and logistic regression. We created 100 seeded splits (80% training 20% test). Standard errors of AUC are included below. Red denotes the best performing embedding model consider- ing both neighbourhood based and attributed methods. We used 4 element-wis operators create features.
Datasets
Facebook Page-Page
GitlTub
Twitch
Twitch
Wikipedin
Wikipedia
Operator
Method
Spain
Germany
Chameleons
Crocodiles
TADW
0.517
0.553
0,541
0.556
0.573
0.625
20.004
20.004
20.007
20. 50.008
20.012
20.005
0.554
20.003
20.003
20.001
004
20.013
20.003
ASNE
0.547
0.596
0,562
0.579
0,050
0.723
BANE
0.625
0.630
0,616
0.634
0.617
0,671
Average
20.003
20.002
20:001
20 003
20.011
20.000
TENE
0.547
0.515
0.532
0.555
0.555
0.644
$0.004
20.004
20.011
20.00
$0.011
20.003
0.572
0.719
0.723
0.669
0,834
20.006
MUSAE
0.642
0,780
0 0,733
0.771
0.810
0,899
AE-EGO
0.514
0.516
0,523
0.545
0.563
0,660
#0.007
#0.006
+0.011
+0. +0.007 007
#0.011
+0 +0.000
MUSAE-EGO
0.546
20.000
20.003
20.003
20 008
20.006
20.003
TADW
0.973
0.915
O 1,836
0,884
0.964
0 0,967
AANE
0.911
0.772
0.833
0.811
0.917
0.892
10.00 002
10.
10:003
10 002
10.000 000
20:003
ASNE
0.973
0.912
0,883
0.8G6
0,945
0.940
#0.001
#0.001
20.003
20.002
$00000
=0.001
BANE
0.653
0.664
0 1,659
0.816
0.578
0,738
Hadamard
0002
TENE
0.735
0,878
0.722
0.748
0.883
0.872
AE
0.926
0.811
0.743
0. 7.702
0.939
0.9-9
#0.001
+0.002
+0 +0.003
+0. 003
+0.002
+0.001
20.001
20.002
2: 200000
2: 20.003 003
10.000
20.001
AE-EGO
0.928
0.786
0,727
0,687
0.935
0,939
MUSAE-EGO
0.938
0.911
0,881
0. 2.855
0.952
0.969
20
10.002
007
20.001
TADW
0.971
0.909
0.881
0.962
20.001
20.002
20.003
20.001
20.002
20.001
AANE
0.866
0.720
0,771
0,768
0.944
0.913
ASNE
0.815
0.806
0 1,836
0,849
0.869
0,874
001
BANE
0.653
0.661
0,658
0.816
0.578
0. 74
1 Norm
10
10
2 000
10 0002
10.014
200 20.002
TENE
0.837
0.927
20.001
1000
0. 2.0004
0.000
10.008
20.001
0.968
0.589
0.871
0,870
0.955
0.952
MUSAE
0.973
0.908
O 888
0.879
0.956
0.967
20.
AE-EGO
0.973
0.801
0.872
0.872
0.953
0.955
#0.001
#0.001
200002
+-0 0.0002
#0.002
#0.001
MUSAE-EGO
0.891
20.0001
10.001
20.002
1000
+00000
20.001
TADW
0.972
0.913
0,883
0.879
0.961
0.961
AANE
0.877
0.732
0.779
0.774
0.941
0.901
20
100 801
20.003
10 007
10 000
20.001
ASNE
0,800
0.872
0.839
0.852
0.875
0,850
$0.004
#0. 00.
20.003
20.002 002
$00000
20.001
BANE
0.659
0.
0.578
0,738
Norm
20.002
00-0002
TENE
0.893
0.884
O 0,826
0,797
0.930
0.863
AE
0.968
0.881
0,872
0,867
0.954
0.953
#0.001
+0.001
#0.001
00.002
#0.003
+0.001
MUSAE
0.877
0.965
20.001
20.001
20.002
20 20.000 003
20.006
20.001
AE-EGO
0.973
0.884
0.873
0.871
0.952
0,956
MUSAE-EGO
0.977
0.907
0.891
0.881
0.951
0.961
10.001
20:063
20.002
20.001
19


Reviews:
[{"review_id": "ryxLNTmaYS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe proposed embedding methods are standard. The key contribution of this paper comes from the theoretical part, which establishes the equivalence between the proposed embedding methods and matrix factorization. It looks interesting, although there are several similar works before, as mentioned in the paper. I don’t know how different your work is from the Qiu’s paper.\n\nThe experimental results are not convincing. The node classification is a very standard task in the performance evaluation of network embedding, but you put the results into the appendix. I examine the results anyway, and I found the performance gain is very limited, and on some datasets, the proposed methods even perform inferiorly.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "Skx3TcKRKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe proof part follows Qiu et al (2018). But it is unclear, why c^{−1}A is the stationary joint distribution over consecutive nodes p(wj , wj+1).  and c^{−1}DF describes the stationary joint distribution p(f,wj) over nodes and features. There needs more explanation. \n\nThe Remark 1 and 2 discuss the case AE with F=I_|V|,  which is in fact the case when there is no node attributes. In this case, the AE process naturally goes back to plain network embedding, where DeepWalk and WalkLets are proposed for. Therefore, these remarks are done by Qiu et al (2018) already, not make no much new contribution here. \n\nFigure 2 shows that the presented two approaches just slightly better or equivalent, or sometimes worse than baseline methods. As mentioned earlier, it is not beneficial to randomly select features to propagate. \n\nThe experiments presented in Section 5.2 evaluate whether the learned embedding can be used for label inference in a different graph. But it is unknown how success the transferring is. There is no F1-score of a solution that does embedding of the target network itself independently, and then classify the target network nodes. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "S1lMVC0pKr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\nFollowing are some review’s questions:\n1. In MUSAE, what is the intention that the tuples are added to different sub-corpus for source and target nodes? Besides, the D_r should be a corpus rather sub-corpus.\n2. In 5.2, I’m not quite understand what do you mean by ‘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’.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper constitutes interesting progress on an important topic; the reviewers identify certain improvements and directions for future work, and I urge the authors to continue to develop refinements and extensions.
Decision: Reject