GRAPH NEIGHBORHOOD ATTENTIVE POOLING
Authors: Zekarias Tilahun Kefato
Sarunas Girdzijauskas
Venue:  (2020)
Keywords: Network Representation Learning
Attentive Pooling Networks
Context-sensitive Embedding
Mutual Attention
Link Prediction
Node Clustering

Abstract: Network representation learning (NRL) is a powerful technique for learning low-dimensional vector representation of high-dimensional and sparse graphs. Most studies explore the structure and meta data associated with the graph using random walks and employ a unsupervised or semi-supervised learning schemes. Learning in these methods is context-free, because only a single representation per node is learned. Recently studies have argued on the sufficiency of a single representation and proposed a context-sensitive approach that proved to be highly effective in applications such as link prediction and ranking.
However, most of these methods rely on additional textual features that require RNNs or CNNs to capture high-level features or rely on a community detection algorithm to identifying multiple contexts of a node.
In this study, without requiring additional features nor a community detection algorithm, we propose a novel context-sensitive algorithm called GAP that learns to attend on different part of a node’s neighborhood using attentive pooling networks. We show the efficacy of GAP using three real-world datasets on link prediction and node clustering tasks and compare it against 10 popular and state-of-the-art (SOTA) baselines. GAP consistently outperforms them and achieves up to ≈9% and ≈20% gain over the best performing methods on link prediction and clustering tasks, respectively.

Under review as a conference paper at ICLR 2020
GRAPH NEIGHBORHOOD ATTENTIVE POOLING
Anonymous authors
Paper under double-blind review
ABSTRACT
Network representation learning (NRL) is powerful technique for learning low- dimensional vector representation of high- high-dimensional and sparse graphs. Most studies explore the structure and metadata associated with the graph using random walks and employ an unsupervised or semi-supervised learning schemes. Learn- ing in these methods is context-free, because only a single representation per node single representa-
is learned. Recently studies have argued on the sufficiency tion and proposed a context-sensitive approach that proved to be highly effective in applications such as link prediction and ranking.
However, most of these methods rely on additional textual features that require RNNs CNNs to capture high-level features rely community detection algorithm to identify multiple contexts of a node.
In this study, without requiring additional features nor community detection al- gorithm, we propose a novel context-sensitive algorithm called GAP that learns to attend on different parts of node's ' neighborhood using attentive pooling net- works. We show the efficacy of GAP using three real-world datasets on link pre- diction and node clustering tasks and compare it against 10 popular and state-of- the-art (SOTA) baselines. GAP consistently outperforms them and achieves up to x 9% and 20% gain over the best performing methods on link prediction and clustering tasks, respectively.
INTRODUCTION
NRL is a powerful technique to learn representation of graph. Such a representation gracefully lends itself to a wide variety of network analysis tasks, such as link prediction, node clustering, node classification, recommendation, and so forth.
In most studies, the learning is done in context-free fashion. That is, the representation of node characterizes just a single aspect of the node, for instance, the local or global neighborhood of node. Recently, a complementary line of research has questioned the sufficiency of single representations and considered a contex(-sensitive approach. Given a node, this approach projects it to different points in space depending other contexts it is coupled with. A context node can be sampled from a neighborhood (Tu et al.] 2017]] Zhang et al.) 2018), random walk (Ying et al., 2018). and so In this study we sample from a node neighborhood (nodes connected by edge). Thus, in the learning process of our approach a source node's 's representation changes depending on the target (context) node it is accompanied by. Studies have shown that context-sensitive approaches significantly outperform previous context-free SOTA methods in link-prediction task. A related notion (Peters et al., 2018 Devlin et al. 2018) NLP has significantly improved SOTA across several NLP tasks.
In this paper we propose GAP (Graph neighborhood attentive pooling), which inspired by atten- tive pooling networks (APN) (dos Santos et al. 2016), originally proposed for solving the problem of pair ranking in NLP. For instance, given a question g. and set of answers = {a1, (01,...,,2, .az), }. an APN can be trained to rank the answers in A with respect to q by using two-way attention mecha- nism. APN is based on the prevalent deep learning formula for SOTA NLP, that is, embed, encode, attend, predict (Honnibal 2018). Given question-answer pair (g, a.), the APN model first projects the embedding of the pairs using two separate encoders, and the encoder can be a CNN or LSTM. The projection helps to capture n-gram context information and/or long-term dependencies in the input sequence. Next, a soft-alignment matrix is obtained by a mutual-attention mechanism that transforms these projections using parameter matrix. Attention vectors are then computed through

---

Under review as a conference paper at ICLR 2020
volumn-wise and row-wise pooling operations the alignment matrix. Finally, the weighted sum of each of the above projections by its respective attention vector is computed to obtain the rep- resentations of the question and answer. Each candidate answer a; is then ranked according to its similarity with the question computed using the representations of q and 0z.
Recently, APN have been applied to context-sensitive NRL by Tu et al. (2017), and the inputs textual information attached with a pair of incident nodes of edges in a graph. Such information, however, has the added overhead of encoding textual information.
Though we adopt APN in GAP, we capitalize on the graph neighborhood of nodes to avoid the need for textual documents without compromising the quality of the learned representations, Our hypothesis is that one can learn high-quality context-sensitive node representations just by mutually attending the graph neighborhood of node and its context node. To achieve this, we naturally assume that the order of nodes in the graph neighborhood of node is arbitrary. Moreover, we exploit this assumption to simplify the APN model by removing the expensive encode phase.
Akin to textual features in APN, GAP simply uses graph neighborhood of nodes. That is, for every node in the graph we define graph neighborhood function to build fixed size neighborhood sequence, which specifies the input of GAP. In the APN model, the encoder phase is usually required to capture high-level features such as n-grams, and long term and order dependencies in textual inputs. As have textual features and due to assumption that there is ordering in the graph neighborhood nodes, we can effectively strip off the encoder. The encoder is the expensive part of APN it involves RNN or CNN, and hence GAP can be trained faster than APN.
This simple yet empirically fruitful modification of the APN model enables GAP to achieve SOTA performance on link prediction and node clustering tasks using three real world datasets. Further- more, we have empirically shown that GAP is more than 2 times faster than an APN like NRL algorithm based text input. In addition, the simplification in GAP does not introduce new hyper- parameters other than the usual ones, such as the learning rate and sequence length in APN.
APN ARCHITECTURE
For the sake of being self-contained, here we briefly describe the original APN architecture. We are given a pair of natural language texts (z, y) as input, where. (Wi,... wx) and y (w1...., wy are a sequence of words of variable lengths, and each word wy is a sample from a vocabulary V, X 1sl. Y lyl. and X and Y could be different. The APN'S forward execution is shown in Fig. AA and in the following we describe each component.
First embedding matrices of x and y are constructed through lookup operation an embedding matrix E E [dx[Vi| of words, where d is the embedding dimension. That is, for both and y. respectively, embedding matrices X = [w....., wx] and Y [wi..... wy] are con- structed by concatenating embeddings w, of each word w, in x and the Embed box in Fig. AA).
Embed:
Encode: Each embedding matrix is then projected using a CNN or BI-LSTM encoder to capture inherent high-level features, the Encode box in Fig. [[)). More formally, the embedded texts X e R Y E d are projected
Xene = f(X, Q) and Yenc f(Y, () where is the encoder, CNN or BI-LSTM, θ is the set of parameters of the encoder, and X Xene E R and Yone E RReYY where is the number of filters hidden features of the CNN and BI-LSTM, respectively.
Attend: In the third step, a parameter matrix E Rx introduced so as to learn a similarity or soft-alignment matrix A E Xx between the sequence projections Xene and Y as:
A = tanh XT PY.P.ee enc
Then unnormalized attention weight vectors x' X and y' RY are obtained through column-win wise and row-wise max-pooling operations on A, respectively as x max(A,,). v/ = max(A.,)) where 0 < < X, 5 < Y and A,, and A.j are the i-th and j-th row and column of A, respectively. Next, the attention vectors are normalized using softmax, softmax
2

---

Under review as a conference paper at ICLR 2020
8,
Endee
Erahed Y (.
Emted 15 Mj
Escede
Encedr You
No. =
XT
CV Rg
Affend
tanh PT)
Nxer
Vxe
Attend
izab X PX.r)
Calera wise mas-geeling
Ronoeke mas--gellng
Colmmniis mas-paaling
Rowinise maa mat--posiing
zo fofimeste 1
5 Xac softmaxix y
Yor softmaxxt))
Prodit
(B)
Figure I:
The APN (A) and GAP (B) models forward execution for question answering and context- sensitive node representation, respectively.
and y = softmax(y/)) Finally, the normalized attention vectors are used to compute the final representations as r, X enc x²" and ry- Yone y².
Predict: In the last step, the representations Tu and ry will be used for ranking depending on the task on hand. For instance, in a question and answer setting, each candidate answer's representation Ty will be ranked based its similarity score with the question's representation rz.
GAP
GAP adopts the APN model for learning the representations of node pairs in graph G (V, with a set of n nodes V and m edges E. G can be a directed or undirected and weighted or unweighted graph. Without loss of generality we assume that G' is an unweighted directed graph.
We define a neighborhood function N V + 2V, which maps each node E V to set of nodes Na C V. A simple way of materializing N,, to consider the first-order neighbors of u, that is, N, = [e= (u, v) E E V (v E F.]. An important assumption that we have on N,, is that the ordering of the nodes in Nr, not important. GAP capitalizes on this assumption to simplify the APN model and achieve SOTA performance. Even though
explore more sophisticated neighborhood functions, in this study we simply consider the first order neighborhood.
Our goal is to learn node representations using the simplified APN based on the node neighborhood function N. Hence, akin to the input text pairs in APN, we consider pair of neighborhood sequences
N, (4,, ... us) and N₁ (V1...., vr) associated with a pair (s, t) E of nodes and t. and
= N. and T = [N,] Without loss of generality we consider S T. Recall that we assume the order of nodes in N. and N, is arbitrary.
3

---

Under review as a conference paper at ICLR 2020
Dataset
#Nodes
#Eddees
Features
Cora 2277
5214
Paper Abstract
Zhihu
10000
43894
User post
Email
1005
25571
NA
Table Summary of datasets, the Features column is relevant to some the baselines not GAP
Given source node s, seek to learn multiple context-sensitive embeddings of with respect to a target node it is paired with. In principle one can learn using all pairs of nodes, however that is not scalable, and hence we restrict learning between pairs in E.
GAP'S forward execution model is shown in Fig B)) and learning starts by embedding N, and Nr. respectively, as S (ui..... ug)) and T (V....., UT). Since there is no order dependency between the nodes in N, or N,, besides being a neighbor of the respective node, we leave out the CNN or BI-LSTM based projections S and that could capture the dependencies. No encoder!
Thus, the next step of GAP is mutually attending on the embeddings, S and T. of the graph neigh- borhood of the node pairs; the Attend box BB). That is, we employ the trainable parameter matrix P E R and compute the soft-alignment matrix, A, between the neighbors of and f.
A tanh(S" PT)
Here A is soft-alignment matrix between every pair of nodes, v) E N₂ Nr. Therefore, for each axis of A, we proceed by pooling the maximum alignment score for each node to obtain the unnormalized attention vectors s max(A,.) and tj max(A.,). As a result of the pooling operations, each neighbor u N₂ of the source node, selects a neighbor e E N₂ of the target N₂-
node, with the maximum alignment or similarity score. A similar selection done for This enables the source and target neighborhood sequences of the pair to influence each other in order to learn a context-sensitive representation then obtained by applying softmax as so softmas softmax(s)) and t = softmax(!'). Ultimately, compute the context-sensitive representations r, and ry of the source and target nodes s and t, respectively as r. S s" and T T
and t. The normalized attention vectors are
The objective of GAP to maximize the likelihood of the graph (edges) by pre- dicting edge similarities using the dot product of the source and target representations rs T2 the Predict box of Fig BB). Hence, we employ a hard-margin loss given in Eq. 2
Optimization:
((8,6) max (0, v. Pr. +' ... rT)
where ri is the representation of negative target node t_, that is (s, & E. The goal is to learn, in an unsupervised fashion, a context-sensitive embedding of nodes that enable us to rank the positive edges ts, E E higher than the negative pairs (s,t").
Finally word on the computational complexity of GAP that proportional the the number of edges, as we are considering each edge as input pair.
4 EXPERIMENTAL EVALUATION
In this section we provide an empirical evaluation of GAP. To this end, experiments are carried out using the following datasets, and basic summary is given in Table
1. Cora Tu et al. 2017); Zhang et al.
(2018): is a citation network dataset, where a node represents that paper has cited paper
represents paper and an edge (u, v)
2. Zhihu Tu et al. (2017); Zhang et al. (2018): is the biggest social network for Q&A and it is based China. Nodes are users and the edges are follower relations between the users.
3. Email Leskovee al. (2007): is email communication network between the largest European research institutes. A node represents a person and an edge (u, v) E G denotes that person has sent email to
4

---

Under review as a conference paper at ICLR 2020
Dataset
#Neighborhood (S and 7)
Dropout
Learning rate
Representation size
Cora
100
0.5
0.0001
200
Zhihu 250
0.65
0.0001
200
Email 100
0.8
0.0001
200
Table 2: Conifguration of GAP
The first two datasets have features (documents) associated to nodes. For Cora, abstract of papers and Zhihu user posts. Some of the baselines, discussed beneath, require textual information, and hence they consume the aforementioned features. The Email dataset has ground-truth community assignment for nodes based on person's s affiliation to one of the 42 departments.
We compare method against the following 10 popular and SOTA baselines grouped as:
Structure based methods: DEEPWALK Perozzi et al. 2014). NODE2VEC Grover & Perozer
Leskovec 2016). WALKLETS Perozzi et al. 2016), ATTENTIVE WALK Abu-EI-Haii et al. (017)), LINE Tang et al. (2015):
Structure and attribute based methods: TRIDNR et et (016)), TADW Yang et al. 2015
CENE Sun et al. (2016)
Context-sensitive: CANE Tu et al. (2017), DMTE Zhang et al. (0018)
We are aware of another SOTA context-sensitive algorithm (Epasto Perozzi 2019) that not require textual information, however we have not included it in our experiments because the source code not available Now we report the experimental results carried out two tasks, which are link prediction and node clustering. All experiments performed using 24-Core CPU and 125GB RAM Ubuntu 18.04 machine.
4.1
LINK PREDICTION
Link prediction is an important task that graph embedding algorithms are applied to. Particularly context-sensitive embedding techniques have proved to be well suited for this task. Similar to exist- ing studies we perform this experiment using a fraction of the edges as training set. We hold out the remaining fraction of the edges from the training phase and we will only reveal them during the test phase, results reported using this set. All paper--rrreeter tuning is performed by taking small fraction the training set as a validation set.
Zhang et al. 2018). the percentage of training edges ranges from 15% to 95% by step of 1O. The syper-parameter of all algorithms are tuned using random-search. For some of the baselines, our results are consistent with what is reported in previous studies, and hence for Cora and Zhihu simply report these results.
Setup: In-line with existing techniques Tu et al. 2017
Except the "umavoidable" hyper-paramete parameters (eg. learning rate, regularization/dropouu rate) that are common in all the algorithms, our model has just one hyper-parameter which is the neighborhood sequence length (#Neighhorhood = = T), for nodes with smaller neighborhood size we use zero padding. As we shall verify later, GAP is not significantly affected by the choice of this parameter.
The quality of the prediction task is measured using the AUC score. AUC indicates the probability that randomly selected pair (u, w) & E will have a higher similarity score than edge (u, v) E E. Similarity between a pair of nodes is computed as the dot product of their representation. For all the algorithms the representation size d 200 and GAP'S configuration shown in Table
The results of the empirical evaluations on the Cora, Zhihu, and Email datasets are re- ported in Tables and 3 GAP outperforms the SOTA baselines in all cases for Zhihu and Email, and in almost all cases for Cora. One can see that as we increase the percentage of training edges, performance increases for all the algorithms. As indicated by the "Gain" row, GAP achieves up 9% improvement over SOTA context-sensitive techniques. Notably the gain is pronounced for
Results:
We have contacted the authors and have been told that the code ready for release
5

---

Under review as a conference paper at ICLR 2020
% training edges
Algorithm
15%
25%
35%
45%
55%
65%
75%
85%
95%
DEEPWALK
56.0
63.0
70.2
73.5
80.1
85.2
85.3
87.8
90.3
LINE
55.0
58.6
66.4
73.0
77.6
82.8
85.6
88.4
89.3
N0DE2VEC
55,9
62.4
66.1
75.0
78.7
81.6
85.9
87.3
88.2
WALKLETS
69.8
77.3
82.8
85.0
86.6
90.4
90.9
92.0
93.3
ATTENTIVEWALK
64.2
76.7
81.0
83.0
87.1
88.2
91.4
92.4
93.0
TADW
86.6
88.2
90.2
90.8
90.0
93.0
91.0
93.0
92.7
TRIDNR
85.9
88.6
90.5
91.2
91.3
92.4
93.0
93.6
93.7
CENE
72.1
86.5
84.6
88.1
89.4
89.2
93.9
95.0
95.9
CANE
86.8
91.5
92.2
93.9
94.6
94.9
95.6
96.6
97.7
DMTE
91.3
93.1
93.7
95.0
96.0
97.1
97.4
98.2
98.8
GAP
95.8
96.4
97.1
97.6
97.6
97.6
97.8
98.0
98.2
GAIN%
4.5%
3.6%
3.4%
2.6%
1.6%
0.5%
0.4%
Table 3: AUC score for link prediction on the Cora dataset
%f fraining edges
Algorithm
15%
25%
35%
45%
55%
65%
75%
85%
95%
DEEPWALK
56.6
58.1
60.1
60.0
61.8
61.9
63.3
63.7
67.8
LINE
52.3
55.9
59.9
60.9
64.3
66.0
67.7
69.3
71.1
NODE2VEC
54.2
57.1
57.3
58.3
58.7
62.5
66.2
67.6
68.5
WALKLETS
50.7
51.7
52.6
54.2
55.5
57.0
57.9
58.2
58.
ATTENTIVEWALK
69.4
68.0
74.0
75.9
76.4
74.5
74.7
71.7
66.8
TADW
52.3
54.2
55.6
57.3
60.8
62.4
65.2
63.8
69.0
TRIDNR
53.8
55.7
57.9
59.5
63.0
64.2
66.0
67.5
70.3
CENE
56.2
57.4
60.3
63.0
66.3
66.0
70.2
69.8
73.8
CANE
56.8
59.3
62.9
64.5
68.9
70.4
71.4
73.6
75.4
DMTE
58.4
63.2
67.5
71.6
74.0
76.7
78.7
80.3
82.2
GAP
72.6
77.9
81.2
80.8
81.4
81.8
82.0
83.7
86.3
GAIN%
3.2%
9.9%
7.2%
5.1%
5.0%
5.1% 1%
3.3%
3.4%
4.1%
Table 4: AUC score for link prediction the Zhihu dataset
%f training edges
Algorithm
15%
25%
35%
45%
55%
65%
75%
85%
95%
DEEPWALL
69.2
71.4
74.1
74.7
76.6
76.1
78.7
75.7
79.0
LINE
65.6
71.5
73.8
76.0
76.7
77.8
78.5
77.9
78,8
NODE2VEC
66.4
68.6
71.2
71.7
72.7
74.0
74.5
74.4
76.1
WALKLETS
70.3
73.2
75.2
78.7
78.2
78.1
78.9
80.0
78.5
ATTENTIVEWALK
68.8
72.5
73.5
75.2
74.
74.9
73.0
70.3
68.6
GAP
77.6
81.6
81.9
83.3
83.1
84.1
84.5
84.8
84.8
GAIN%
7.3%
8,4%
6.7%
4.6%
4.9%
6.0%
5.6%
4.8%
5.8%
Table 5: AUC score for link prediction on the Email dataset
smaller values of percentage of edges used for training. This is shows that GAP is suitable both in cases where there are several missing links and most of the links are present.
4.2 NODE CLUSTERING
Nodes in network has the tendency to form cohesive structures based some kinds of shared aspects. These structures are usually referred to as groups, clusters or communities and identifying them is important task in network analysis. In this section ground truth communities, and there are 42 of them. Since this dataset has only structural informa- tion, we have excluded the baselines that require textual information.
the Email dataset that has

---

Under review as a conference paper at ICLR 2020
of training edges
Algorithm
25%
55%
75%
95%
NMI
AMI
NMI
AMI
NMI
AMI
NMI
AMI
DEEPWALK
41.3
28.6
53.6
44.8
50.6
42.4
57.6
49.9
LINE
44.0
30.3
49.9
38.2
53.3
42.6
56.3
46.5
NODE2VEC
46.6
35.3
45.9
35.3
47.8
38.5
53.8
45.5
WALKLETS
47.5
39.9
55.3
47.4
54.0
45.4
50.1
41.6
ATTENTIVEWALK
42.9
30.0
45.7
36.5
44.3
35.7
47.4
38.5
GAP
67.8
58.8
64.7
55.7
65.6
57.6
65.4
58.7
% Gain
20.3%
9.4%
11.0%
7.8%
Table 6: NMI and AMI scores for node clustering experiment on the Email dataset. with respect to the NMI only.
The Gain is
Neighborhood
50
100
150
200
250
cora
email
zhihu
1.00
0.8
0.8
0.75
0.6
0.6
AUC
0.50
0.4
0.4
0.25
0.2
0.2
0.00
0.0
0.0
25
55
75
95
25
55
75
95
25
55
75
95
% of training edges
Figure 2: Sensitivity of GAP the size of node's neighborhood (S, 2) on the link prediction task
Setup:
Since each node belongs to exactly one cluster, we employ the Spectral Clustering algo- rithm identify clusters. The learned representations of nodes by certain algorithm are the input features of the clustering algorithm. In this experiment the percentage of training edges varies from 25% 95% by step of 20%, for the rest we use the same configuration as in the above experiment.
Given the ground truth community assignment of nodes and the predicted community assignments J. usually the agreement between y and ý are measured using mutual information T(y. 9). However, I is not bounded and difficult for comparing methods, hence we use two other variants of (Vinh) al. 2010). Which are, the normalized mutual information N NM 9). which simply normalizes 7 and adjusted mutual information AM (y. 9). which adjusts or normalizes / to random chances.
The results of this experiment reported in Table and GAP significantly outperforms all the baselines by up to 20% with respect to AMI score. Consistent to our previous experiment GAP performs well in both extremes for the value of the percentage of the training edges. Similar improvements are achieved for AMI score.
Results:
4.3 PARAMETER SENSITIVITY ANALYSIS
Here we first show the sensitivity of the main hyper-parameter of GAP, which is the size of the neighborhood, #Neighborhood = 5 T. Figures A) show the effects of this parameter both on link prediction and node clustering tasks. In both cases notice that GAP is not significantly affected by the change values. We show the effect across different values of percentage and fixed (55%) of training edges for link prediction and node clustering tasks, respectively. Regardless of the percentage of training edges, we only see a small change of AUC (Fig and NMI and AMI (Fig a) across different values of #Neighborhood.
Next, we analyze the run time of training GAP and our goal is to show the benefit of removing the encoder of APN and do this by comparing GAP against CANE, which employs the exact APN

---

Under review as a conference paper at ICLR 2020
Metric
AMI
NMI
Algorithm
CANE
GAP
0.675
Time seconds)
Measurement
0.650
1000
0.625
.667
0.600
500
315
0.575
115
0
150 200 #Neighborhood
BAG
Cora
ERG
Zhihu
Dataset
(a)
(b)
Figure 3: (a) Sensitivity of GAP to the size of node's neighborhood on the node clustering task and (b) the run time comparison of GAP and CANE using two real and two synthetic datasets
chitecture. For this experiment we include two randomly generated graphs using ErdósRényi (ERG) and BarabásiAlbert (BAG) models. ERG has 200K edges, and BAG has 1.5M edges. Figure 3(B) clearly shows that GAP is at least 2 times faster than CANE in all the graphs.
RELATED WORK
NRL is usually carried out by exploring the structure of the graph and meta data, such as node attributes, attached to the graph (Perozzi et al. 2014: Grover & Leskovec 2016 Tang et al.) 2015 Perozzi et al.] 2016 Wang et al.) 2016] Yang et al. 2015: Pan et al., 2016 Sheikh et al.) 2019). Random walks widely used to explore local/global neighborhood structures, which are then fed into a learning algorithm. The learning is carried out in unsupervised manner by maximizing the likelihood of observing the neighbor nodes and/or attributes of center node.
Recently graph convolutional networks have also been proposed for semi-supervised network anal- ysis tasks (Kipf & Welling 2017 Hamilton al. 2017: Wu al.) 2019: Velickovic et 2017 Abu-EI-Haija et al.) 2019). These algorithms work by way of aggregating neighborhood features, with a down-stream objective based partial labels of nodes, for example. All these methods are essentially different from our approach because they are context-free.
Context-sensitive learning another paradigm to NRL that challenges the sufficiency of a single representation of node for applications such as, link prediction, product recommendation, ranking. While some of these methods (Tu et al.] 2017] Zhang et al. (0188) rely on textual information, others have also shown that similar goal can be achieved using just the structure of the graph (Epasto) Perozzi 2019). However, they require an extra step persona decomposition that is based on microscopic level community detection algorithms the first approaches our algorithm does not require extra textual information and with respect to the second ones approach does not require any sort of community detection algorithm.
identify multiple contexts of node. Unlike
CONCLUSION
In this study we present a novel context-sensitive graph embedding algorithm called GAP. It con- sumes node neighborhood as input feature, which are constructed based on an important assumption that their ordering is arbitrary. To learn representations of nodes GAP employs attentive pooling APN
networks (APN). By exploiting the above assumption, it makes an important simplification and gains more than 2X speed up over another SOTA method, which employs the exact APN. Fur- thermore, GAP consistently outperforms all the baselines and achieves up to z 9% and == 20% improvement over the best performing ones the link prediction and node clustering tasks, respec- tively. future we will investigate how node attributes can be incorporated and provide theoretical framework the relation between the neighborhood sampling and topological properties.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Sami Abu-EI-Haija, Bryan Perozzi, Rami Al-Rfou, and Alex Alemi. Watch your step: Learning graph embeddings through attention. CoRR, abs/1710.09599, 2017. URL http://arxiv.
org/abs/ 1710. 09599
Sami Abu-al-Haija, Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan, Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolu- tional architectures via sparsified neighborhood mixing. CoRR, abs/1905.00067, 2019. URL
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. CoRR, abs/1810.04805, 2018. URL
http://arxiv org/
bbbrg//ab/// abw /1800 04805
Cícero Nogueira dos Santos, Ming Tan, Bing Xiang, and Bowen Zhou, Attentive pooling networks. 03609
CoRR, abs/1602.03609, 2016.
Alessandro Epasto and Bryan Perozzi. a single embedding enough? learning node representations that capture multiple social contexts. CoRR, (bs/1905.02133, 2019. URL http:://rxiv:
oxg/aba/1905. 02138
Aditya Grover and Jure Leskovec. Node2vec: Scalable feature learning for networks. Proceedings of the 22Nd ACM SIGKDD International Conference Knowledge Discovery and Data Mining,
KDD '16. pp. 855-864, New York, NY, USA, 2016. ACM. ISBN 978- 1 1-4503--232--2 doi: 10.
1145/2939672.2939755 URL http::/ttcooo acm. www.oo.g//...o...ooo 45/ 1ww.111////997..222 2939772...99975
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. CoRR, abs/1706.02216 2017. URL http:////aaxiiieaa www.oo/gg.oooo abs
aallaaasb/////////////////////1a 1706. 02216
Matthew Honnibal. Embed, encode, attend, predict: The new deep learning for-
mula for state-of-the-art nlp models. 2018. URL
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
Jure Leskovee, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data, 1(1), March 2007. ISSN 1556-4681. doi: 10.1145 2217299.1217301 URL /tt:://ooi..e acm 111.//1...1111111
Shirui Pan, Jia Wu, Xingquan Zhu, Chengqi Zhang, and Yang Wang. Tri-party deep network representation. In Proceedings of the Twenty-Fiith International Joint Conference on Artificial
Intelligence, IJCAI'6, pp. 1895-1901. AAAI Press, 2016. ISBN 978-1-57735-770-4 URL
http::/dl. acm. wwtp:/iiaiiiiin./ cfm?id 3060832.
3060832.30608886 3060886
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa-
tions. CoRR, abs/1403.6653 2014. URL httLht:::/// http:tttpaxxiii org /trgg//b//// aww//a//..... 6652
Bryan Perozzi, Vivek Kulkarni, and Steven Skiena. Walklets: Multiscale graph embeddings for interpretable network classification. CoRR, abs/1605.021 2016. URL http:://rxiiv
prg/abs/1605 02115
Matthew F. Peters, Mark Neumann, Mohit lyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. Deep contextaaized word representations. CoRR, abs/1802.05365, 2018.
URL http://t:/aaa httt:::/aaxxv..ot. org/ wwt.s////....... 05365
Nasrullah Sheikh, Zekarias Kefato, and Alberto Montresor, gat2vec: Representation learning for attributed graphs. In Journal of Computing. Springer, May 2019.
Xiaofei Sun, Jiang Guo, Xiao Ding, and Ting Liu. A general framework for content-enhanced network representation learning. CoRR, abs/ htts//11002900 2016. URL http: //tr/v..vv./././//////aa///aawav www.iivooo org/ abs 1 62906

---

Under review as a conference paper at ICLR 2020
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. LINE: large-scale information network embedding. CoRR, abs//1503.3357,, 2015. URL http:://axxi...ettttt
abs abss1103... 03578
Cunchao Tu, Han Liu, Zhiyuan Liu, and Maosong Sun. CANE: Context-aware network embed- ding for relation modeling. In Proceedings of the 55th Annual Meeting the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1722-1731, Vancouver, Canada, July 2017. Association for Computational Linguistics. doi: 10.18633/1//177-1558. URL ac org/ httgg//achhooloy/11--1111
https:/ http://wwwwwww....o..o
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks, ArXiv, abs/1710.10900 2017.
Nguyen Xuan Vinh, Julien Epps, and James Bailey. Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. J. Mach. Learn. Res., 11:2837-2854, 2010.
Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 16, pp. 1225-1234, New York, NY, USA, 2016. ACM. ISBN 978-1-4503-4232-22 doi: 10. htLLhtt::// //ooi. doi. acm. org/ 10. 091444//2939722.9999999
1145/2939672.2999755
Felix Wu, Tianyi Zhang, Amauri H. Souza Jr., Christopher Fifty, Tao Yu, and Kilian Q. Wein- berger. Simplifying graph convolutional networks. CoRR, abs/ ths//992.077553 153, 2019. htthtt
//axxiv.org/e/ 0ttp///9020011.3.
Cheng Yang. Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Y. Chang. Network representa- tion learning with rich text information. In Proceedings of the 24th International Conference on Artificial Intelligence, ICCAI'5, pp. 2111-2117. AAAI Press, 2015. ISBN 978-1-57735-738-44 URL
wwtp:m/ttttoatttooo..oooa.a.aa.e cfm? 25...oo.........21115552522
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William I.. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. CoRR, Abs/1806.01973 2018. URL httt::/ttaaxiiiii org/ www/sass... 01973
Xinyuan Zhang, Yitong Li, Dinghan Shen, and Lawrence Carin. Diffusion maps for textual net- work embedding. In Proceedings of the 32Nd International Conference on Neural Informa- fion Processing Systems, NIPS' 18, pp. 7598-7608, USA, 2018. Curran Associates Inc. URL attp://d1 acm. wwtpoo/ggtttioooooooooo wtt.:oo..cc..........33m
3327858
A APPENDIX
Here we give a brief ablation experiment to strengthen the case for GAP. Concretely, we seek to compare GAP with different baselines further motivate choice of (i) the way model nodes using their neighborhood, (ii) the assumption that order in this neighborhood is not important, and (iii) the choice of the APN algorithm without the CNN or BI-LSTM encoder. To this end, introduce the following baselines and apart from the indicated difference everything will be the same as GAP.
Datasets
Cora
Email
Training ratio
Training ratio
Baselines
25%
55%
75%
95%
25%
55%
75%
95%
GAPCN
60
60
61
74
74
78
79
GAPAPN
59
60
60
65
74
77
78
78
GAPMLP
56
63
66
73
72
77
78
77
GAP
96
97
97
98
81
83
84
Table 7: AUC results for the variants of GAP using the Cora and Email datasets
10

---

Under review as a conference paper at ICLR 2020
1. First assume order is important in the neighborhood of nodes based on neighbors simi- larity with the current node. We use a topological feature to induce order, which is common neighbors. This baseline is referred as GAPCN and uses the exact APN model to capture "order""
2. Second, we use the same input as GAP, but nodes' neighborhood is now randomly per- muted and fed multiple times (concretely 5 times), and the exact APN model is employed; this baseline is referred to as GAPAPN
3. Finally we replace GAP'S Attend component with a standard feed-forward neural network that consumes the same input (Embedding matrices S and T) and also has the same learning objective specified in Eq. 2 the baseline is referred to as GAPMLP.
In Table we report the results of the ablation experiment. This sheds some light the assumptions and the design choices of GAP. For the reported results, GAPCN and GAPAPN use a CNN Encoder. In both cases, they quickly over-fit the data, and we found out that we have to employ aggressive regularization using a dropout rate of 0.95. In addition, for GAPCN we have also observed that as we increase the kernel size to greater values than (up to 5) the results keep getting worse, and hence, what we reported is the best one which is obtained using kernel size of 1. For example, with kernel size of 3 and training ratios 25, 55, 75, and 95 percent the AUC scores respectively dropped to 54, 55, 56, and 58 percent the Cora dataset, and 66, 69, 78 and 77 percent the Email dataset. We conjecture that this due the model's attempt to enforce high-level neighborhood patterns (eg. combination of arbitrary neighbors) that are not intrinsically governing the underlying edge formation phenomena. Rather, what is important is to effectively pay attention to the presence of individual neighbors both in N₂ and N₂ regardless of their order. Apparently, training this model is at least twice slower than GAP as it is also illustrated in Section
In the case of GAPAPN, though the variations in AUC are marginal with respect the change in the kernel size, the training time of these model has increased almost by an order of magnitude. Finally we see that the mutual attention mechanism (Attend component) plays important role by comparing the results between the GAPMLP and GAP.
11


Reviews:
[{"review_id": "rylsqZtauS", "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": "This paper proposed a GAP (graph neighborhood attentive pooling) method to solve problems of node clustering and link prediction. The proposed idea is mostly inspired by the attentive pooling network approach (APN) that has been widely used in the NLP domains; indeed the detailed steps of the proposed method is almost a ``mirror” application of APN from question-answer pair ranking in NLP to the graph domains, and the only difference is that rather than using an RNN or LSTM to deal with the temporal orders in sentences (as in APN), the proposed method simply collect the first-order neighbors of the source node and target node and concatenate them without considering their orders. For the rest part, the authors used a hard margin loss function which is also the same as in APN.\n\nThe proposed method is very similar to the APN method and so its novelty is limited. Another concern is that although graph nodes do not have temporal orders as in word sentences, their relative connections manifested through the edges are important topological information that should be captured in contextualize a node. Unfortunately the authors almost totally ignored this information. The ignorance of the node orders appear to me not an advantage but instead a limitation, though it makes the computation and implementation much easier.\n\nThe graph attention network (GAT) is a very related method but I see no comparison with it in node clustering tasks. Also many recent methods on graph convolutional networks are not incorporated for comparison. \n\nBased on the concerns of novelty, lack of considering node topologies, and lack of comparison with strongly related methods, it is hard to recommend acceptance of this paper.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "SJlUP9iqFr", "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": "- Minimal theoretical novelty: The paper is too focussed on the empirical advantage achieved on the datasets used in the experiments. \n\n- Regarding equation (2), what is the guarantee this modification depicted by the hard-margin loss will always lead to improved performance like what happened with the experimented datasets? or more practically what are the required conditions for it to perform well?\n\n- Writing really needs to improve. There are too many typos and grammatical mistakes. \nExamples include:\n -- p1: \"to learn representation of graphs\". \n -- p1: \"on other contexts its coupled with\".\n -- p1: \"NRL studies have shown a context-sensitive approach significantly outperform previous context-free SOTA methods in link-prediction task.\"\n -- p3: \"a more sophisticated neighborhood functions\".\n -- p5: \"reporeted\"\n -- p7: \"two other variant\"\n -- p8: \"and gain\"\n\n- The latter issue makes is sometimes tricky to follow the ideas presented. \nExample:\n -- last two lines in Section 3. \n\n- Last paragraph in Section 1 is pretty informative about the pros and cons of the method. It also rather admits the first issue mentioned here in the review.  \n\nMinor:\n- p4: \"Eg. \" --> eg. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "B1gUZkOTKB", "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": "Summary:\nThe proposed paper adapts Attentive Pooling Network (ATN) for graphs, by noting that the order of\nneighbors of any node in a graph does not matter unlike the neighboring words in a sentence (for\nwhich APN was developed). A simple modification of removing the layer which encodes higher order\nsequential properties in APN, eg n-gram like statistics, the APN is adapted to GAP. This allows\nencoding context from the neighboring nodes for a specific pair to be compared. Applications on Link\nPrediction and Node Clustering are demonstrated on three benchmark datasets.\n\nDetailed comments:\n- The paper is simple and easy to read and the modification of APN to GAP is also small while being\nwell motivated and empirically important.\n\n- There are some confusions in the writing: p4 first paragraph says that \"In principle one can learn\nusing all pairs of nodes, however that is not scalable, and hence we restrict learning between pairs\nin E.\" However from and around Eq2 it appears that r_s.r_t^- is also computed, where (s,r^-) is not\nan edge.\n\n- Also the statement below Eq2 \"The goal is to learn, in an unsupervised fashion...\" is not correct\n  specially for link prediction task, as having a training graph (with edges) is having annotations.\n        \n- Although, the removal of the `encoding' step from APN makes sense, it would also be possible that\n  the encoding operation is learned to be an identity function automatically if the training data is\n  presented appropriately. I would assume that learning in such a case might take longer, and might\n  not achieve the performance achieved by GAP. An ablation experiment could be reported to support\n  GAP further where encoder is kept in APN, but at the training same pair is presented multiple\n  times with the order of the neighborhoods randomized.      \n       \n- Similar to the experiment above, the order of the nodes could be arbitrarily fixed by some simple\n  logic. Eg order the neighboring nodes sorted by the feature similarity with the current node. This\n  can then be fed to APN and a baseline could be reported.\n\n- I do not directly work with Link Prediction or Node Clustering tasks, so am not familiar with the\n  literature and the baselines reported. However, it might be that many baselines do not use a\n  discriminative objective. Perhaps just using the discriminative objective gives a lot of boost and\n  using the context from neighbors is not very important? From Fig2 and Fig3a it seems that\n  neighborhood size does not make a big difference? This should also be ablated. One experiment\n  could be to use just the current feature and have a small MLP on it, and learn using the proposed\n  discriminative objective. If any other experiment can be designed in similar lines, it should be\n  included as well.\n\n- Why are run time comparison given on simulated data and not real data?\n\n- The experimental setup for training edge selection should be detailed more. In particular, I\n  would recommend that true generalization in terms of nodes and edges should be ensured, by having\n  no test node (i) appear in the train set and (ii) has an edge which connects it to a training\n  node. If this is not used then the alternative scheme used should be explained and argued for.\n\n\nI am not a direct expert in the area and felt that the paper was somewhat lacking. I am putting my initial rating\nto the conservative side. I am very open to revising the rating based on the author responses and the other \nreviewers' comments.", "extra_scores": {"experience_assessment": "I have read many 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 carefully checked 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: All three reviewers are consistently negative on this paper. Thus a reject is recommended.
Decision: Reject