Dual Graph Representation Learning
Authors: Huiling Zhu
Xin Luo
Hankz Hankui Zhuo
Venue:  (2020)

Abstract: Graph representation learning embeds nodes in large graphs as low-dimensional vectors and  benefit to many downstream applications. Most embedding frameworks, however, are inherently transductive and unable to  generalize to unseen nodes or learn representations across different graphs. Inductive approaches, such as GraphSAGE,  neglect different contexts of nodes and cannot learn node embeddings dually. In this paper, we present an unsupervised dual encoding framework, \textbf{CADE},  to generate context-aware representation of nodes by combining real-time neighborhood structure with neighbor-attentioned representation, and preserving extra memory of known nodes. Experimently, we exhibit that our approach is effective by comparing to state-of-the-art methods.

Under review as a conference paper at ICLR 2020
DUAL GRAPH REPRESENTATION LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph representation learning embeds nodes in large graphs as low-dimensional vectors and benefit to many downstream applications. Most embedding frame- works, however, are inherently transductive and unable to generalize unseen nodes or learn representations across different graphs. Inductive approaches, such as GraphSAGE, neglect different contexts of nodes and cannot learn node em- beddings dually. In this paper, we present context-aware unsupervised dual encoding framework, CADE, to generate representation of nodes by combining real-time neighborhood structure with neighbor-attentionee representation, and preserving extra memory of known nodes. Experimently, we exhibit that our ap- proach is effective by comparing to state-of-the-an art methods.
INTRODUCTION
The study of real world graphs. such as social network analysis (Hamilton el (2017a)), molecule screening (Quvenaud all (2015)), knowledge base reasoning (Urivedi at (2017)), and biological protein-protein networks (Zitmik & Leskoved (2017), evolves with the development of computing technologies. Learning vector representations of graphs is effective for a variety of prediction and graph analysis tasks (Grover & Leskoved (20T)); [Tang et al, (2015)). High-dimensional informa- tion about neighbors of nodes are represented by dense vectors, which can be fed to off-the-shelff approaches to tasks, such as node classification (Wang et al (2017); Bhagat ct al. (20I link
prediction (Perozzi et all (2014); Wei el all (2017)). node clustering ([ic et all (20117 Z); Ding ct al. (2IXII), recommender systems (Ying al. Sa) and visualization (Maaten & Hinton (2008)).
There are mainly two types of models for graph representation learning. Transductive approaches (Perozzi all (2014); Grover & Leskoved (2016;; Tang et all (2015)) are able to learn representations
of existing nodes but unable to generalize to new nodes. However, in real-world evolving graphs such social networks, new users will join and must be represented. Inductive approaches were proposed to address this issue. GraphSAGE (Hamiton et all (20176)), hicrarchical sampling and aggregating framework, successfully leverages feature information to generate embeddings of the new nodes. However, GraphSAGE has its own faults. Firstly, it samples all neighborhood nodes randomly and uniformly; secondly, it treats the output of encoder as the final representation of node.
Based on the hierarchical framework of GraphSAGE, GAT (Velickovic et all (201 uses given class labels to guide attention over neighborhood so as to aggregate useful feature information. However, without knowledge of ground-truth class labels, is difficult for unsupervised approaches to apply attention. To address this issue, we introduce a dual encoding framework for unsupervised inductive representation learning of graphs. Instead of learning self-attention over neighborhoods of nodes, we exploit the bi-attention between representations of two nodes that co-occur in a short ralk (which we call positive pair).
In Figure M. we illustrate how nodes are embedded into low-dimensional vectors, where each node has optimal embeddings og. Yet the direct output of encoder 2. of GraphSAGE could be located anywh Specifically, given feature input from both sides of a positive pair (v, o,). a neural network is trained to encode the pair into K different embeddings zt and = through different sampled neighborhoods or different encoding functions. Then, a bi-attention layer is applied to generate the most adjacent matches Zoin, and 2,,,v= which will be referred as ruuleeepressn..iions..... By putting most attention on the pair of embeddings with smallest difference, dual representation of nodes with less deviation will be generated, which can be visualized zy). in Figure II

---

Under review as a conference paper at ICLR 2020
2p
GngLSAGE
Figure Visual comparison between representations learnt by current methods and dual encoding.
GraphSAGE naively assumes that unseen graph structure should be (casily) represented by known graphs data. We combine the ground truth structure and the learned dual-encoder to generate final representation. Unseen nodes be represented based on their neighborhood structure. Current inductive approaches have no direct memory of the training nodes. We combine the idea of both transductive and inductive approaches via associating additive global embedding bias to each node, which can be seen as a memorable global identification of each node in training sets.
Our contributions can be summarized as follows:
we introduce dual encoding framework to produce context-aware representation for nodes, and conduct experiments to demonstrate its efficiency and effectiveness;
we apply bi-attention mechanism for graph representation dual learning, managing to learn dual representation of nodes more precisely;
we combine the training of transductive global bias with inductive encoding process, as memory of nodes that are already used for training.
RELATED WORK
Following (Caletal all (2018), Kinderkhedra (2019) and Goyal & Ferrara (2018)) there are mainly
two types of approaches:
2.1 NETWORK EMBEDDING
For unsupervised embedding learning, DeepWalk (Perozzi et all (2014)) and node2vec (Grover & Leskoved (2016) are based on random-walks extending the Skip- Skip-Gram model; LINE (Tang et al. (015))seeks to preserve first- and second-orde -oder proximity and trains the embedding via negative sampling: SDNE (Wang et al, (2016) jointly uses unsupervised components to preserve second- order proximity and expolit first-order proximity in its supervised components; TRIDNR (Pan
cLal (2))16)) CENE(Sun ctal (2016) TADW (Yang et all (2015)) GraphSSEE (Hamtion ef all (20175)) utilize node attributes and potentially node labels. Convolutional neural networks are also applicd to graph-structured data. For instance, GCN (Kıpl & Welling (2017)) proposed an simpli- fied graph convolutional network. These graph convolutional network based approaches
(semi- >supervised. Recently, inductive graph embedding learning (Hamilon et all (20176) Velickovic all
(2017) Bojchevski & Günnemann (2017) aCal (2018) Gaa. (2()) R) Lietal all (2018) Wang et all (2018) and Ying et al] (2018h)) produce impressive performance across several large-scale benchmarks.
2.2 ATTENTION
Attention mechanism in neural processes have been extensively studied in neuroscience and compu- tational neuroscience etal (1998); Desimone & Dunean (1995)) and frequently applied in deep learning for speech recognition (Chorowski at (2015). translation (Luong all (2015)) question
2

---

Under review as a conference paper at ICLR 2020
answering aL (2016) and visual identification of objects (Xutttal (2015)). Inspired by (Sen stall (2016) and Abu-El-Haija et all (20T8), we construct a bi-attention layer upon aggregators to capture useful parts of the neighborhood.
3 MODEL
Let G = (V, E, } be an undirected graph, where a set of nodes V are connected by set of edges E, and X E TR|V is the attribute matrix nodes. A global embedding bias matrix is denoted by B RIVixd, where a row B represents the d-dimensional global embedding bias of a node. The hierarchical layer number, the embedding output of the I-th layer and the final output embedding denoted by L, h' and x, respectively.
3.1 CONTEXT-AWARE INDUCTIVE EMBEDDING ENCODING
The embedding generation process is described in Algorithm II trained and parameters are fixed.
Assume that the dual encoder is
Algorithm Cowtext-Aware Dual Dual-Encoding (CADE)
input: the whole graph (V, E); the feature matrix X; the trained DualENC
output: learned embeddings
1: Run random walks 9 to gain set of positive pair P.
2: Zu + 0, Ve E
3: for (v, Up) IP do
4: Zv: 2n1 = DualENC(y, Vp, &,))))
5: Zy Zn U Zz
6: Zup + Eep Uup
7: end for
8: for E V do
9: 2, Mean(
10: end for
After training, positive pairs are collected by random walks on the whole dataset. The features of each positive pair passed through dual-encoder. Embeddings of nodes generated so that the components of a pair are related and adjacent to each other.
3.2 DUAL-ENCODER WITH SAMPLIG
In this subsection, we explain the dual encoder.
Algorithm DualENC.
input:
Training graph GVV, E); node attributes X; global embedding bias matrix B; sampling times K; positive node pair (o,up):
output: adjacent embeddings 2n and Zepi
1: For node v and Up. generate K embeddings, h. hug using base encoder SAGB
2: for i, E {1...., K} do
3: St.j + ah hvw))
4: end for
5: softmax on flattened similarity matrix S: St,j +-
8i. R Pin
6: calculate attention a, and a
aui Σx= St.j. aupt f- ΣK St
7: Σk 1==1 /
Zep Dtm an k opte
h
In the hierarchical sampling and aggregating framework (Hamilion et al (20176)), is challenging and vital select relevant neighbor with the layer goes deeper and deeper. For example, given
3

---

Under review as a conference paper at ICLR 2020
word "mouse" and its positive node "PC", it is better to sample "keyboard", instead of "cat", neighbor node. However, to sample the satisfying node according to heuristic rules layer by layer very time consuming, and it is difficult to learn attention neighborhood for unsupervised emhedding learning.
As matter of fact, these neighbor nodes considered be useful because they are more welcome to be sampled as input so as to produce more relevant output of the dual-encoder. Therefore, instead of physically sampling these neighbor nodes, in Step Step 6 in Algorithm we directly apply a bi-attention layer on the two sets of embedding outputs with different sampled neighborhood feature input, so as to locate the most relevant representation match, more efficient approach to exploring the most useful neighborhood.
We use the hierarchical sampling and aggregating framework base encoder in our experiments, but it can also be designed in many other ways.
Given node v, and node Up as positive node pair, after sampling and aggregating for K times, we have K different representations h hhy.k corresponding to K different sampled neighborhoods, their similarity matrix can be calculated by
S.j = a hrgs),
i.j = 1,.... K
where a represents dot-product operation.
our goal is to find the closest neighborhood match between o and up within x K possibilities, so we apply softmax on the flattened similarity matrix, and sum up by row(column). In this way, we manage to gain different attention over K neighborhoods of o(ep) with respect to Up(x).
exp(Si;)
Sij + K.K
(2)
exp( (Si))
0,0
avi
Sij
(3)
j=1
Ogy =
Szy
(4)
1=1
and up the /th layer representations with attention the dual-encoder outputs,
K a lonk
Zn
(5)
k=1
uup
Hoykhopk
(6)
km/
To train our encoder before using to generate final representations nodes, we apply a typical pair reconstruction loss function with negative sampling Hamilion et (20176)
Jg(),) = logga ze,)) -Q Ev,, (ogg 2v.))
where node Up co-occurs with u on fixed-length random walk (Perozzi al (2012)) o is the sigmoid function, P,, is negative sampling distribution, Q defines the number of negative samples. Note that 2, and E.,, are dual representation to each other while žp, represents the direct encoder output of negative sample Vn.
3.3 DUAL-ENCODER WITH MULTI-AGGREGATINN
Besides learning dual representation with multiple sampling, introduce another version of our dual encoder with multiple aggregator function. The intuition is that through different perspective, a node can be represented differently corresponding to different kinds of positive nodes.
4

---

Under review as a conference paper at ICLR 2020
In Step in Algorithm D. for node sample neighborhood once and aggregate feature with K sets parameters, gaining K different representations he corresponding to K different character of Given positive node pair, and Ep. their dual representation attention as we descrihed in the last section. There is but one difference that we use a weigh vector A R2d parameter instead of dot-product, to calculate the K K attention matrix between node v and node Up.
calculated by applying bi-
Sij + exp( (A [fvv (erps)))
(8)
K.K
exp(A) [hoi (boaa))))))
0,0
where .'' represents transposition and the concatenation operation. The rest of calculation of dual representation is the same as section S
Another difference is during training. With K sets parameter for aggregating, negative sample on is also represented by K different embeddings. As shown in Figure 2 we set K 5 and use different shape to represent the embeddings the positive node pair and the negative sampled nodes.
Zop
support embedding
Figure 2: training support embeddings of node and its negative sample node up.
As we can see in Figure 2 to make sure that any embeddings of node U, as far away from any of node possible, it is equal maximizing the distance between their support embeddings. which is the closest pair of embeddings of e and en. The support embedding can be calculated by the learned dual encoder. In conclusion, our loss function can be modified as follows,
Jg (zx) log(o 2),,) Be 2T,,)) (T,,))
(9)
z Zvp DualENC(r, Up. A)
(10)
2/ Zv, DualENC(r, Up. A*)
(11)
where A representing that stop the kack-propagation through A in dual encoding for negative sample node, since A are supposed to learn bi-attention between the positive node pair and be reused only to capture the support embedding of and its negative sample nodes.
3.4 MEMORABLE GLOBAL BIAS IN IIERARCHICCL ENCODING
In this section, we first explain the base encoder used in our proposed dual encoding framework, and then introduce how apply memorable global bias within this framework.
The general intuition of GraphSAGE is that at each iteration, nodes aggregate information from their local neighbors, and this process iterates, nodes incrementally gather more and more information

---

Under review as a conference paper at ICLR 2020
from further reaches of the graph. For generating embedding for one specific node describe the process below. First, we construct a neighborhood tree with node u as the root, Nu, by iteratively sampling immediate neighborhood of nodes of the last layer children. Nodes at the Ith layer are represented by symbol Ny. No = {u}. Then, at each iteration, each node i aggregates the representations of its children j. {h [h- and of itself, h into a single vector h1, as representation of the next layer. After L iterations, we gain the Lth layer representation of c, the final output.
While this framework generates good representation for nodes, it cannot preserve sufficient embed- ding informations for known nodes. More specifically, for nodes that are known but trained less than average, the learned model would have treated them like nodes unmet before. Therefore, we intuitively apply distinctive and trainable global bias to each node, as follows:
h 1-1 AGGREGATE .Vj S(I)) S(G)
(12)
4 f (W [h] 1h:-1114 14-""1n's0 5())
(13)
h/ + h4 + b., 1 < L
(14)
b, oot B
(15)
(16)
where B RIV xd the trainable global bias matrix, S(i) represents the sampled neighborhood and also the children nodes of node in the neighborhood tree, AGGREGATE represents the neigh- borhood aggregator function, and || is a operator of concatenating vectors.
On one hand, B can be reused to produce embeddings for the known nodes the unknown con- nected with the known, as supplement to the neural network encoder. On another hand, the global bias vectors partially offset the uncertainty of the encoding brought by the random sampling not only during the training but also the final generation. Lastly but not least, we use only one set of global bias for all nodes, which means for any node, its representations of hidden layers are all added by the same bias vector. As a result of that, we are able to update parameters of aggregator function in the lowest layer with the global updated bias of nodes, highly increasing the training efficiency.
is important for us to apply no global bias to the last layer of output, which is also the candidate of the dual-encoder output of nodes before applied with attention. The reason is that applying extra bias onto the last layer would directly change the embedding distribution of known nodes, making it unequal to the embedding distribution of unseen nodes. In general, the implementation of the base encoder with global bias is shown in Algorithm EL The in Step 8 means the children of node in the neighborhood tree N..
Algorithm samBing and aggregating with global bias
input: node u; hierarchical depth L; weight matrices W non -oneeinearty σ; differentiable neighbor aggregator AGGREGATE; fixed-size uniform sampler S u + 2 output: embedding Za:
1: No- = {u];
2: for [ = 1...L do
3: N +- (S(i), Vi E NN-1);
4: end for
5: for I=1...L do
6: for E No. UN,, UNG do
7:
h5-1)) + AGGREGATE Vj E (i))
8:
h oW! "o/ (1h
9: i/ L: h² + tot + hot(i
10: end for
11:
end for
12: return zu - h.

---

Under review as a conference paper at ICLR 2020
4 EXPERIMENTS
In this section, we compare CADE against two strong baselines an inductive and unsupervised setting, challenging benchmark tasks of node classification and link prediction. We also perform further studies of the proposed model in section 4...
4.1 DATASETS
The following graph datasets are used in experiments and statisties are summarized in TableII:
The PubMed Diabetes (Sen et all (2008)) ) dataset is citation dataset which consists of scientific publications from Pubemd database pertaining diabetes classified into one of three classes. Each publication in the dataset is described by a TF/IDF (Salton
Pubmed:
Yu (19733) weighted word vector from a dictionary.
Blogcatalog: BlogCatalog' is social blog directory which manages bloggers and their blogs, where bloggers following each others forms the network dataset.
Reddit: Reddit' is an internet forum where users can post or comment on any content. We use the exact dataset conducted by (Hamilion et (20176), where each link connects two posts the same user comments on both them.
PPI: The protein-proteinn-nteeraaiinnnnnn (PPI) networks dataset contains 24 graphs correspond- ing to different human tissues(Zitmik & Leskoved (2017)). We use the preprocessed data also provided by (Hamilton (2017h)).
Table 1: Dataset Statistics
Dataset
Nodes
Edges
Classes
Features
Avg Degree
Pubmed 19717
44324
500
4.47
Blogcatalog
5196
171743
6
8189
66.11
Reddit
232,965
11,606,919
41
602
100.30
PPI
56944
818716
1214
50
28.76
4.2 EXPERIMENTAL SETTINGS
We compare CADE against the following approaches in a fully unsupervised and inductive setting:
GraphSAGE: In our proposed model, CADE, the base encoder mainly originates from GraphSAGE, hierarchical neighbor sampling and aggregating encoder for inductive learn- ing. Three alternative aggregators are used in Graphsage and CADE: (1) Mean aggregator,
which simply takes the elementwise mean of the vectors in h h== (u) (2) LSTM aggrega-
tor, which adapts LSTMs to encode random permutation of node's neighbors' h--1; (3) Maxpool aggregator, which apply an elementwise maxpooling operation to aggregate information across the neighbor nodes.
Graph2Gauss (Bojchevski & Günnemann (2017)): Unlike GraphSAGE and my method, G2G only uses the attributes nodes to learn their representations, with no need for link information. Here we compare against G2G to prove that certain trade-off between sam- pling granularity control and embedding effectiveness does exists in inductive learning scenario.
Beside the above two models, we also include experiment results raw features as baselines. In comparison, call the version of dual-encoder with multiple sampling as CADE-MS, while the version with multiple aggregator function as CADE-MA.
Availaale at https://liggs.ee https://lingssse..uue wttpii/ssseeuuuusccom wcsc..du/daaa.. http://www.booccattlog
http://www.reddit.com PPT is multi-labe dataset.

---

Under review as a conference paper at ICLR 2020
agg L = 2, the neighbor sampling sizes as $1 = 20, $2 = 10, and the number of random-walks for each node as 100 and the walk length as 4. The sampling time in CADE-MS
For CADE-MS, CADE-MA and GraphSAGE, we the depth of hierarchical aggregating
the number of aggregator in CADE-MA is set as K = 10. And for all emedding learning models, the dimension of embeddings is feature, use all the dimensions. Our approach is impemented in Tensorflow (Abadi et all (2UT)) and trained with the Adam optimizer (Kingma & Ba (2014)) at an initial learning rate of 0.0001.
set to 256, for
4.3 INDUCTIVE NODE CLASSIFICATION
We evaluate the node classification performance of methods on the four datasets. On Reddit and PPI, we follow the same alog, we randomly selected 10%/20%/30%% nodes for training while the rest remain unseen. We report the averaged results over 10 random split.
split used in GraphSAGE. On Pubmed and Blogcat-
After spliting the graph dataset, the model trained in an unsupervised manner, then the learnt model computes the embeddings for all nodes, node classifier is trained with the embeddings of training nodes and finally the learnt classifier evaluated with the learnt embeddings of the testing nodes, ie the unseen nodes.
Table 2: Prediction results for Pubmed/Blogcatalog w.r.t different unseen ratio
Methods
Pubmed
Blogcatalog
unseen-ratio
10%
30%
50%
10%
30%
50%
RawFeats
79.22
77.66
77.74
90.00
89.05
87.08
G2G
80.70
76.67
76.31
62.35
56.19
48.46
GraphSAGE
82.05
81.32
79.68
71.48
69.33
64.92
CADE-MS
84.25
83.40
81.74
77.35
73.71
70.88
CADE-MA
84.56
83.03
82.40
84.33
82.21
79.04
Comparation on node classification performance on Pubmed and Blogcatalog dataset with respect to varying ratios of unseen nodes, are reported in Table QI CADE-MS and CADE-MA outperform other approaches on Pubmed. On Blogcatalog dataset, however, RawFeats performs best mainly because that, in Blogcatalog dataset, node features not only directly extracted from a set of user-defined tags, but also are very high dimensionality (up to 8, 189). Hence extra neighborhood information not needed. As shown in Table Z CADE-MA performs better than CADE-MS. and both outperform GraphSAGE and G2G. CADE-MA is capable of reducing high dimensionality while losing less information than CADE-MS, CADE-MA is more likely to search for the best aggregator function that can focus on those important features of nodes. As a result, the 256-dimensional embedding learnt by CADE-MA shows the cloest node classification performance the 8k-dimensional raw features.
Comparasion among GraphSAGE, CADE and other aggregator functions is reported in Figurell Each dataset contains 30% unseen nodes. In general, the model CADE shows significant advance the other two state-of-art embedding learning models in node classification on four different challenging graph datasets.
4.4 INDUCTIVE LINK PREDICTION
Link prediction task evaluates how much network structural information is preserved by embed- dings. We preform the following steps: (1) mark some nodes as unseen from the training of em- bedding learning models. For Pubmed 20% nodes are marked as unseen; (2) randomly hide certain percentage edges and equal-number of non-edges as testing edge set for link prediction, and make sure not to produced any dangling node; (3) the rest of edges are then used to form the input graph for embedding learning and with equal number of non-edges form the training edge set for link pre- dictor; (4) after training and inductively generation of embeddings, the training edge set and their corresponding embeddings will help to train a link predictor; (5) finally evaluate the performance on the testing edges by the area under the ROC curve (AUC) and the average precision (AP) scores.
8

---

Under review as a conference paper at ICLR 2020
532
11:M
Caa add
casee dffyee
cask cddeaat
cLse and
Cheer
catte
Reddit
(b) PPI
A2.13
20.00
0130
cartobl
cameitumed coorat
duettoo Cevesaeteo
cunmatimnn
commit
cada
Cone
(c) Pubmed
(d) Blogcatalog
Figure 3: Classification results (micro-averaged F1 scores) w.r.t diffcrent aggregators on four datasets
Table 3: Link prediction results for Pubmed/PPI w.r.t different percentage of hidden-edges
Dataset
Methods
90%%10%
80%:20%
60%:40%
40%:60%
AUC
AP
AUC
AP
AUC
AP
AUC
AP
RawFeats
57.61
54.72
58.51
56.19
54.47
52.82
52.41
50.77
G2G
64.13
68.60
63.52
65.15
60.03
66.16
58.97
61.17
Pubmed
GraphSAGE
85.49
82.79
87.64
83.35
81.07
77.47
79.34
74.92
CADE-MS
89.95
88.79
90.36
86.67
87.14
83.77
84.76
79.53
CADE-MA
89.73
89.76
90.94
88.90
90.54
87.89
85.27
80.15
RawFeats
57.46
56.99
57.34
56.86
57.35
56.75
56.83
56.36
G2G
60.62
58.98
60.99
59.38
61.05
59.54
60.93
59.49
PPI
GraphSAGE
82.74
81.20
82.21
80.66
82.11
80.51
82.07
80.70
CADE-MS
85.87
85.08
84.21
83.48
84.46
82.84
83.61
82.39
CADE-MA
86.33
85.32
85.85
84.63
84.15
82.15
81.98
79.54
Comparation on performance with respect varying percentage of hidden edges are reported in Tablesl CADE shows best link prediction performance on both datasets.
4.5
MODEL STUDY STUDY
4.5.1
SAMPLING COMPLEXITY IN CADE-MS
Our proposed CADE-MS requires multiple neighborhood sampling, which increases the complexity of embedding learning. Yet by comparing CADE-MS against GraphSAGE with the same quantity of sampled neighborhood per node, the superiority of CADE model over existing models is still vast. In practice, we set the sampling layer L = and the first-layer sampling size as 20. For the second layer, denote by s' the sampling size in GraphSAGE, and by $2 and T the sampling size and sampling time in CADE-MS. We compare the two methods with s/ = $2 K. variant of CADE, called CADE-gb, applies only memorable global bias and dual-encoding framework,

---

Under review as a conference paper at ICLR 2020
*GrphSMME
x CADE--g = MS
56
Scor!
64
53.54
50
48
26-945
100-10x10
15H4-
400-20-20
#/2 = 52 K
Figure 4: node classification performance (micro-fl score) w.r. varying sampling sizes
has the same sampling complexity as GraphSAGE. For efficiency experiment, we conduct experiments of node classification small subset of PPI, denoted by subPPI, which includes training graphs plus one validation graph and one test graph. Results are reported in Figure g With much smaller sampling width, CADE-MS still outperforms the original framework significantly.
implicates that searching for the best representation match through multiple sampling and bi- attention is efficient filtering userful neighbor nodes without supervision from any node labels, and that the contett-wware dual-encoding framework capable of improving the inductive embedding learning ability without increasing sampling complexity. We aslo observe that CADE-gb, the variant simply adding the memorable global bias, continually shows advance in different sampling sizes.
4.5.2 THE NECESSARITY OF HIDDEN MEMORY
is necessary not to apply global bias to the encoder output. We compare the original framework GraphSAGE, CADE with the variants of method: applying global bias only to the last layer, and only to the former layers. As Table E shows, CADE-gl performs poorly, while CADE-gb demon- strates the effect of keeping memory of the hidden representation for each node.
Table 4: node classification performance (fl-micro score) with different way of applying global bias
method
Fl-micro
GraphSAGE
50.22
CADE-gl
39.24
CADE-gb
54.13
CADE
58.22
5 CONCLUSION
In this paper, we proposed CADE, an unsupervised and inductive network embedding approach which is capable of preserving local connectiveness distinctively as well as learning and memoriz- ing global identities for seen nodes while generalizing to unseen nodes. We applied a bi-attention architeture upon hierarchical aggregating layers to capture the most relevant representations dually for any positive pair. We also present an effective way of combining inductive and transductive ideas by allowing trainable global embedding bias to be retrieved in hidden layers within the hierarchi- cal aggregating framework. Experiments demonstrate the superiority of CADE over the state-of-art baselines on unsupervised and inductive tasks. In the future, we would explore several possibili- ties, such expanding dual encoding from wiir-wise n-wise, using dual encoding framework in supervised embedding learning, or combing dual encoding with G2G by learning distribution representations dually for positive pairs.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Gre- gory S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, lan J. Good- fellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Józefowiez, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dan Mané, Rajat Monga, Sherry Moore. Derek Gor- don Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul A. Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda B. Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. Tensorflow: Large-scale machine learning on heterogeneous distributed systems. CoRR, abs/1603.04461 2016.
Sami Abu-El-Haija, Bryan Perozzi, Rami AI-Rfou, and Alexander A. Alemi. Watch your step: Learning node embeddings via graph attention. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018. Montréal, Canada., pp. 9198 9208, 2018.
Smriti Bhagat, Graham Cormode, and S. Muthukrishnan. Node classification in social networks. In Social Network Data Analytics, pp. 115-148. Springer, 2011.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of attributed graphs: Unsupervised inductive learning via ranking. CoRR, abs/1707 0a2/1777003815,, 2017.
Hong Yun Cai, Vincent W. Zheng, and Kevin Chen-Chuan Chang. A comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE Trans. Knowl. Data Eng., 30(9): 1616 1637, 2018.
Jan K Chorowski, Dzmitry Bahdanau, Dmitriy Serdyuk, Kyunghyun Cho, and Yoshua Bengio. Attention-bain based models for speech recognition. In Advances neural information processing systems, pp. 577-585, 2015.
Tyler Derr, Yao Ma, and Jiliang Tang. Signed graph convolutional networks. In IEEE International Conference on Data Mining, ICDM 2018, Singapore, November 17-20, 2018. pp. 929-934, 2018.
Robert Desimone and John Duncan. Neural mechanisms of selective visual attention. Annual review of neuroscience, 18(1):193-222) 1995.
Chris H. Q. Ding, Xiaofeng He, Hongyuan Zha, Ming Gu, and Horst D. Simon. min-max cut algorithm for graph partitioning and data clustering. In Proceedings of the 2001 IEEE Interna- tional Conference on Data Mining, 29 November December 2001, San Jose, California, USA,
pp. 107-114, 2001.
David K. Duvenaud, Dougal Maclaurin, Jorge Aguilera-Iparre Iparraguire,, Rafael Kômez-Bombareell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In NIPS, pp. 2224-2234 2015.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, pp. 1416-1424, 2018.
Palash Goyal and Emilio Ferrara. Graph embedding techniques, applications, and performance: A survey. Knowl.-Based Syst., 151:78-94, 2018.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In KDD, pp- 855-864, 2016.
William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Eng. Bull., 40(3):52-74, 2017a.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, 2017b.
Laurent Itti, Christof Koch, and Ernst Niebur. A model of caliency-based visual attention for rapid scene analysis. IEEE Transactions on pattern analysis and machine intelligence. 1254 1259, 1998.
11

---

Under review as a conference paper at ICLR 2020
Mital Kinderkhedia. Learning representations of graph data A survey. CoRR, abs/ Abss/196.00299, 2019.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization.
CoRR,
abs/1412.6980) 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Qimai Li. Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the Thirty-Second AAAI Conference on Artifi- cial Intelligence, (AAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pp. 3538-3545, 2018.
Minh- Sonh-Thang Luong, Hieu Pham, and Christopher D Manning. Effective approaches to attention- based neural machine translation. arXiv preprini
2015.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(ovv)2259 26059,226602220 2008.
Feiping Nie, Wei Zhu, and Xuclong Li. Unsupervised large graph embedding. In Proceedings of the Thisty-First AAAI Conference Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA., pp. 2422-2428 2017.
Shirui Pan, Jia Wu, Xingquan Zhu, Chengqi Zhang, and Yang Wang. Tri-party deep network repre- sentation. In IJCAI, pp. 1895-1901, 2016.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: online learning of social representa- tions. In KDD, pp. 701-710, 2014.
Gerard Salton and Clement T. Yu. On the construction of effective vocabularies for information re- trieval. In Proceedings of the 1973 meeting Programming languages and information retrieval, Gaithersburg, Maryland, USA, November 4-6, 1973, pp. 48-60, 1973.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data. Al Magazine, 29(3):93-106, 2008
Min Joon Seo, Aniruddha Kembhavi, Ali Farhadi, and Hannaneh Hajishirzi. Bidirectional attention flow for machine comprehension. CoRR, abs/1611 00111611101600 .01603, 2016.
Xiaofei Sun, Jiang Guo, Xiao Ding, and Ting Liu. A general framework for content-enhanced network representation learning. CoRR, abs/1610.02900 2016.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang. Jun Yan, and Qiaozhu Mci. LINE: large-scale information network embedding. In wWW, pp. 1067-1077, 2015.
Rakshit Trivedi, Hanjun Dai, Yichen Wang, and Le Song. Know-evolve: Deep temporal reasoning for dynamic knowledge graphs. In Proceedings of the 34th International Conference on Machine Learning. JCML 2017, Sydney, NSW, Australia, 6-11 August 2017, pp.
2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lið, and Yoshua Bengio. Graph attention networks. CoRR, abs/1710.10900 2017.
Daixin Wang. Peng Cui, and Wenwu Zhu. Structural deep network embedding. In KDD, pp. 1225- 1234, 2016.
Hongwei Wang, Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, and Minyi Guo. Graphgan: Graph representation learning with generative adversarial nets. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pp. 3508-2515 2018
Xiao Wang, Peng Cui, Jing Wang, Jian Pei, Wenwu Zhu, and Shiqiang Yang. Community pre- serving network embedding. In Proceedings of the Thirty- First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA., pp. 203-209, 2017.
12

---

Under review as a conference paper at ICLR 2020
Xiaokai Wei, Linchuan Xu, Bokai Cao, and Philip S. Yu. Cross view link prediction by learning noise-resilient representation consensus. In Proceedings of the 26th International Conference on World Wide Web, WWW 2017, Perth, Australia, April 3-7, 2017, pp. 1611-1619,001
Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron C. Courville, Ruslan Salakhutdinov, Richard S. Zemel, and Yoshua Bengio. Show, attend and tell: Neural image caption generation with visual attention. In ICML, pp. 1048-2057, 2015.
Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Y. Chang. Network representation learning with rich text information. In IJCAI, pp. 2111-2117, 2015.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Pro- ceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, pp. 974-983, 2018a.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. Advances in Neural formation Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada., pp. 4805-4815, 2018b.
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33(14):1190-i199 2017.
13


Reviews:
[{"review_id": "rklZ33titH", "reviewer": "AnonReviewer2", "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 proposed a dual graph representation method to learn the representation of nodes in a graph. In particular, it learns the embedding of paired nodes simultaneously for multiple times, and use the mean values as the final representation. The experimental result demonstrates some improvement over existing methods. Overall, the idea is presented clearly and the writing is well structured. But the novelty is limited. Specifically, \n\n1. The proposed method is very similar with the unsupervised GraphSAGE, which also optimizes Eq.(7). The  difference is that the proposed method learns a multi-channel representation and uses the attention technique to aggregate the multi-channel representation. Thus, the novelty is incremental.\n\n2. Since the proposed method uses the multi-channel representation, how to set the number of channels $K$? How does this parameter affect the performance?\n\n3. Some unsupervised network embedding baseline methods, such as DeepWalk and Node2Vec,  should be included into the experiment section. \n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "S1lWKbq0Yr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "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 extends GraphSAGE in several dimensions: 1) applying attention when aggregating neighbors (already used by GAT and many other approached); 2) Ensembling node embedding by applying DualENC multiple times on positive pairs selected by random walk (this is doing aggregation of neighborhood again); and 3) adding global bias. All this makes the proposed method an incremental extension of existing solutions.  There is no theoretical justification why these extensions should work.\n\nThe evaluation only uses two baselines. However, there are many other inductive graph embedding learning approaches, such as (Hamilton et al. (2017b) Velickovic et al. (2017) Bojchevski & Gu ̈nnemann (2017) Derr et al. (2018) Gao et al. (2018), Li et al. (2018), Wang et al. (2018) and Ying et al. (2018b)). It is necessary to compare with these approaches. \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": "HJl_y-pTFB", "reviewer": "AnonReviewer3", "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": "Strengths: \n1. This paper presents a unified framework CADE for unsupervised graph representation learning, which combining the local neighbors and global information. \n2. Based on GraphSAGE, the module DualENC can include positive pairs simultaneously, capturing the context-aware information.\n3. In extensive experiments on Pubmed and PPI for link prediction, they demonstrate that their model beats the state-of-the-arts.\n\nDrawbacks:\n1. In this paper, the “Dual” refers to output adjacent nodes embeddings, where the adjacent nodes are collected by random walk. But the “dual” here is inconformity with its intrinsic definition and applications, according to the existing work “Dual-Primal Graph Convolutional Networks”. In other words, this paper lacks novelty, which seems incremental to the existing works. Specifically, the base-encoder is a variant of GraphSAGE plus a global embedding. The bi-attention is a variant of GAT.\n2. The paper is not clear and structured. There are some confused logics and inaccurate interpretation. For example, in Introduction section, “Based on the hierarchical framework of GraphSAGE, GAT ….”. In Model section, there exists information redundancy and incoherence. For example, in section 3.2, equations 2-6 are reduplicative that have already appeared in algorithm 2.  Figure 1needs more information to help understand the model. To sum up, the connection and presentation of the four modules are not clear, which makes it difficult to read.\n3. The experimental comparison methods and results are not complete. The baseline lacks the optimal method, “Deep Graph Infomax (DGI) ICLR 2019”, on unsupervised node classification. The results are not enough to support the claims (Only two benchmarks are compared).  Some important models on unsupervised graph representation learning are missing, e.g., Deep Graph Infomax(Veličković, 2018). \n\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 carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes context-aware representation of graph nodes leveraging attention over neighbors (as already done in previous work). Reviewers concerns about lack of novelty, lack of clarity of paper and lack of comparison to state of the art methods have not been addressed at all.
We recommend rejection.
Decision: Reject