Year: 2018

Abstract:
Different kinds of representation learning techniques on graph have shown significant effect in downstream machine learning tasks. Recently, in order to inductively learn representations for graph structures that is unobservable during training, a general framework with sampling and aggregating (GraphSAGE) was proposed by Hamilton and Ying and had been proved more efficient than transductive methods on fileds like transfer learning or evolving dataset. However, GraphSAGE is uncapable of selective neighbor sampling and lack of memory of known nodes that’ve been trained. To address these problems, we present an unsupervised method that samples neighborhood information attended by co-occurring structures and optimizes a trainable global bias as a representation expectation for each node in the given graph. Experiments show that our approach outperforms the state-of-the-art inductive and unsupervised methods for representation learning on graphs.

heading: 1 INTRODUCTION
text: Graphs and networks, e.g., social network analysis Hamilton et al. (2017a), molecule screening Duvenaud et al. (2015), knowledge base reasoning Trivedi et al. (2017), and biological proteinprotein networks (Zitnik & Leskovec (2017)), emerge in many real-world applications. Learning low-dimensional vector embeddings of nodes in large graphs has been proved effective for a wide variety of prediction and graph analysis tasks (Grover & Leskovec (2016); Tang et al. (2015)). The high-level idea of node embedding is to explore high-dimensional information about the neighborhood of a node with a dense vector embedding, which can be fed to off-the-shelf machine learning approaches to tasks such as node classification and link prediction (Perozzi et al. (2014)).
Whereas previous approaches (Perozzi et al. (2014); Grover & Leskovec (2016); Tang et al. (2015)) can transductively learn embeddings on graphs, without re-training they cannot generalize to new nodes that are newly added to graphs. It is ubiquitous in real-world evolving networks, e.g., new users joining in a social friendship circle such as facebook. To address the problem, Hamilton et al. (2017b) propose an approach, namely GraphSAGE, to leverage node feature information (e.g., text attributes) to efficiently generate node embeddings for previously unseen nodes. Despite the success of GraphSAGE, it randomly and uniformly samples neighbors of nodes, which suggests it is difficult to explore the most useful neighbor nodes. It could be helpful if we can take advantage of the most relevant neighbors and ignore irrelevant neighbors of the target node. Besides, GraphSAGE only focuses on training parameters of the hierarchical aggregator functions, but lose sight of preserving the memory of the training nodes, which means when training is finished, those nodes that have been trained over and over again would still be treated like unseen nodes, which causes a huge waste.
To address the first issue, inspired by GAT (Velickovic et al. (2017)), a supervised approach that assigns different weights to all neighbors of each node in each aggregating layer, we introduce a bi-attention architecture (Seo et al. (2016)) to perform selective neighbor sampling in unsupervised learning scenarios. In unsupervised representation learning, when encoding embeddings of a positive1 node pair before calculating their proximity loss (Hamilton et al. (2017a)), we assume that
1In random-walk based approaches, nodes that tend to cooccur in short random walks over the graph are usually referred as positive to each other.
neighbor nodes positive to both of the pair should have larger chance to be selected, since they are statistically more relevant to the current positive pair than other neighbors. For example, when embedding words like ”mouse”, in Figure 1, it’s more reasonable to choose ”keyboard” rather than ”cat” as sampled neighbor while maximizing co-occrrence probability between ”mouse” and ”PC”, because ”keyboard” also tends to co-occurr with ”PC”, which means its imformation should be more relevant. We thus stack a bi-attention architecture (Seo et al. (2016)) on representations aggregated from both side in a positive node pair. In this way, we learn the most relevant representations for each positive node pair corresponding to their most relevant neighbors, and simply use a fixed-size uniform sampling which allows us to efficiently generate node embeddings in batches.
To address the second issue, we combine the idea behind transductive approaches and inductive approaches, by intuitively applying an additive global embedding bias to each node’s aggregated embedding. The global embedding biases are trainable as well as parameters of aggregator functions and can be considered as a memorable global identification of each node in training sets. When the training is completed, we generate the embedding for each node by calculating an average of multiple embedding outputs corresponding to different sampled neighbors with respect to different positive nodes. In this way, nodes that tend to co-occur in short random-walks will have more similar embeddings based on our bi-attention mechanism.
Based on the above-mentioned two techniques, we propose a novel approach, called BIGSAGE (which stands for the BI-attention architeture, global BIas and the original framework GraphSAGE,) to explore most relevant neighbors and preserve previously learnt knowledge of nodes by utilizing bi-attention architecture and introducing global bias, respectively.

heading: 2 RELATED WORK

heading: 2.1 NETWORK EMBEDDING
text: In this paper, we focus on unsupervised and inductive node embedding learning for large and evolving network data. For unsupervised learning, many different approachs have been proposed. DeepWalk (Perozzi et al. (2014)) and node2vec (Grover & Leskovec (2016))are two classic approaches that learn node embeddings based on random-walks using or extending the Skip-Gram model. Similarly, LINE (Tang et al. (2015))seeks to preserve first- and second-order proximity and trains the embedding via negative smpling. SDNE(Wang et al. (2016)) jointly uses unsupervised components to preserve second-order proximity and expolit first-order proximity in its supervised components.
Unlike the methods mentioned above, some approaches were proposed to takes use of not only network structure but also node attributes and potentially node labels. Such as TRIDNR(Pan et al. (2016)), CENE(Sun et al. (2016)), TADW(Yang et al. (2015)). GraphSAGE(Hamilton et al. (2017b)), which this paper is motivated from, also requires rich attributes of nodes for sampling and aggregating into embeddings that preserve rich local neighborhood strutural infromation.
Recently, in order to address the problem in large and dense networks of consequently encounted newly jointed nodes/edges, approaches such as Hamilton et al. (2017b) Velickovic et al. (2017)
Bojchevski & Günnemann (2017) were proposed as inductive ways of graph embedding learning and had produced impressive performance across several large-scale inductive benchmarks. In fact, we find that the key of inductive learning is to learn an embedding encoder that relies on only information from a single node itself and/or its local observable neighborhood, instead of the entire graph as in transductive setting.

heading: 2.2 ATTENTION
text: Attention mechanism in neural processes have been largely studied in Neuroscience and Computational Neuroscience (Itti et al. (1998); Desimone & Duncan (1995)) and since these few years frequently applied in Deep Learning for speech recognition (Chorowski et al. (2015)), translation(Luong et al. (2015)), question answering (Seo et al. (2016)) and visual identification of objects Xu et al. (2015) . The principle inside attention mechanism is that focusing on most pertinent parts of the input, rather than using all available information, a large part of which being irrelevant to compute the desirable output. In this paper, we are inspired by Seo et al. (2016) to construct a bi-attention layer upon aggregators in order to capture the useful part of the neighborhood.

heading: 3 MODEL
text: In this section, we propose a hierarchical bi-attended sampling and global-biased aggregating framework (BIGSAGE). We start by presenting an overview of our framework: the training in Algorithm 1 and the embedding generation in Algorithm 2. Followingly, section 3.2 gives the detailed implemention of our bi-attention architeture, section 3.3 demonstrates how we combine global bias within the framework. Given an undirected network G = {V,E,X}, in which a set of nodes V are connected by a set of edges E, and X ∈ R|V |×f is the attribute matrix of nodes. We denote the global embedding bias matrix as B ∈ R|V |×d, where each row of B represents the d-dimensional global embedding bias of each node. The hierarchical layer number is set as K, the embedding output of k-th layer is represented by hk, and the final output embedding z.

heading: 3.1 OVERVIEW
text: To learn representations in unsupervised setting, we apply the same graph-based loss function used in the origin GraphSAGE:
JG(zv) = −log(σ(zTv zvp))−Q · Evn∼Pn(v)log(σ(−z T v zvn))
where node vp co-occurs with v on fixed-length random walk (Perozzi et al. (2014)), sigma is the sigmoid function, Pn is a negative sampling distribution, and Q defines the number of negative samples.
Algorithm 1 shows the training of our framework.
Algorithm 1 BIGSAGE: training input: Training graph Gtrain(Vtrain, Etrain); node attributes X; global embedding bias matrix B; sampling times T
1: zero initialize(B) 2: h0v ← xv,∀v ∈ Vtrain 3: run random-walk in Gtrain and do negative sampling to gain a set of triplets: {(v, vp, vn)} 4: for (v, vp, vn) do 5: Z1 ← ∅,Z2 ← ∅ 6: for t ∈ {1, ..., T} do 7: Z1 ← Z1 ∪ {SAGB(v)} 8: Z2 ← Z2 ∪ {SAGB(vp)} 9: zv, zvp ← BIATT(Z1,Z2)
10: zvn ← SAGB(vn) 11: calculate the graph-based loss JG and update model parameters with SGD
When generating embeddings with the learned parameters after optimization is done, GraphSAGE encode only one single random-partial-sampled neighborhoods for each node, likely leaving out information of those unselected part.
To fully preseve the structural information around, we first rerun random walk on a full graph that inlcudes the seen and unseen nodes; Then, through our bi-attention mechanism built upon the aggregating layers, we generate the most relevant embeddings of each node w.r.t its positive nodes; Eventually, we take average of these generated embeddings as final embeddings of each node and use them in downstream machine learning tasks. The generation process is shown in Algorithm 2:
Algorithm 2 BIGSAGE: generation of embedding input: Testing graph Gtest(Vtest, Etest); node attributes Xtest; learned model BIGSAGE output: Vector representations zv for all v ∈ Vtest
1: run random-walks for each node in Gtest and gain a set of positive nodes pair:{(v, vp)} 2: Zi ← ∅,∀i ∈ Vtest 3: for i, j ∈ {(v, vp)} do 4: use step 5-9 in Algorithm 1 to generate zi, zj 5: Zi ← Zi ∪ {zi} 6: Zj ← Zj ∪ {zj}
return zv ← MEAN(Zv),∀v ∈ Vtest

heading: 3.2 CO-OCCURRENCE BI-ATTENDED ”SAMPLING”
text: We now describe our bi-attention achitecture. Given node n, and node m as a positive node pair, after sampling T times using a uniform fixed-size sampler, we have
hKnt = Agg(h K−1 n , {hK−1j∈Nt(n)})
hKmt = Agg(h K−1 m , {hK−1j∈Nt(m)})
t = 1, ..., T
With T different representations corresponding to T different sampled neighborhoods, their similarity matrix can be calculated by
Si,j = α(h K ni,h K mj), i, j = 1, ..., T
where α represents an dot-product operation.
our goal is to find the most similar or relevant neighborhood match between n and m within T × T possibilities, so we need to apply softmax on the flattened similarity matrix, and sum up by collumn(row) to gain attention over T neighborhoods of n(m):
attn = reduce sum(softmax(S), 0),
attm = reduce sum(softmax(S), 1),
and apply attention to T Kth layer representations for the final encoded embeddings,
hn = T∑ t=1 attnth K nt
hm = T∑ t=1 attmth K mt
The aggregation process with bi-attention architecture is illustrated by Figure 2.

heading: 3.3 GLOBAL BIAS
text: At first, we consider simply adding a trainable bias upon the encoder’s final ouput for each node in training set,
zi = h K i + bi
bi = one hot(i) TB
By training global bias, Our framework will be able to learn parameters of aggregator functions for inductive learning meanwhile preserve sufficient embedding informations for known nodes. On one hand, these informations can be reused to produce embeddings for the known nodes or the unknown connected with the known, as supplement to the aggregator. On the other hand, they can patially offset the uncertainty of the generation braught by the random sampling. But through further research, we find it more efficient when appling global bias to not only the last layer but also all hidden layers, as follows:
hk+1i = W k+1(hki , {hkj∈N(i)}) + b k+1 agg + bi
bi = one hot(i) TB
zi ← hKi
Applying globla bias vectors through all layers improves not only the expressivity of representations on hidden layers, but also the training efficiency. In fact, the hidden layers’ output embeddings and the global biases are now belonging to one single d-dimensional vector space, as a result of which, the parameters from lower layers can be updated more directly by the involving global bias vectors that are adjusted for all different layers including the last layer, which means the loss funtion can now have more instant impact on the lower layers instead of back-propagating from top to bottom.
We propose our aggregating process with global bias in Algorithm 3.
Algorithm 3 SAGB: sampling and aggregating with globa bias input: node u; hierarchical depth K; weight matrices W k; non-linearity σ; differentiable neighbor aggregator Akgg; fixed-size uniform sampler S : v → 2V output: embedding zu;
1: N0u = {u}; 2: for l = 1...K do 3: Nlu ← {S(i),∀i ∈ Nl−1u }; 4: Nu = N0u ⋃ N1u ⋃ ... ⋃ NKu ; 5: for k=1...K do 6: for j ∈ N0u ⋃ N1u ⋃ ... ⋃ NK−ku do 7: hkj ← σ(Akgg(h k−1 j , {hk−1m ,∀m ∈ S∗(j)},W k)) + one hot(j)TB
return zu ← hKu

heading: 4 EXPERIMENTS
text: In this section, we evaluate BIGSAGE against strong baselines on three challenging benchmark tasks: (i) classifying Reddit posts as belonging to different community; (ii) predicting different classes of papers in Pubmed (Sen et al. (2008)); (iii) classifying protein functions across varieties of protein-protein interaction (PPI) graphs (Zitnik & Leskovec (2017)). We start by summarizing the overall settings in our comparison experiments, and then present the experiment results of each task. We also study the seperate effect of our bi-attention architecture and global bias in section 4.4.

heading: 4.1 EXPERIMENTAL SETTINGS
text: We compare BIGSAGE against the following approaches for graph representations learning under a fully unsupervised and inductive setting:
• GraphSAGE: Our proposed method originates from the unsupervised variant of GraphSAGE, a hierarchical sampling and aggregating framwork for inductive learning. We compare our method against GraphSAGE using three different aggregator: (1) Mean aggregator, which simply takes the elementwise mean of the vectors in hk−1u∈N(v); (2) LSTM aggregator, which adapts LSTMs to encode a random permutation of a node’s neighbors’ hk−1; (3) Maxpool aggregator, which apply an elementwise maxpooling operation to aggregate information across the neighbor nodes.
• Graph2Gauss(Bojchevski & Günnemann (2017)): Unlike GraphSAGE and my method, G2G only uses the attributes of nodes to learn their representations, with no need for link information. Here we compare against G2G to prove that certain trade-off between sampling granularity control and embedding effectiveness does exists in inductive learning scenario.
• SPINE, Guo et al. (2018): Instead of hierarchical neighbor sampling, SPINE uses RootedPageRankLiben-Nowell & Kleinberg (2007) to represent the high-order structural proximities of neighborhood. The k largest proximities are then employed to aggregate attributes of the corresponding k neighbor nodes.
For our proposed approach and the origin framework, we set the number of hierarchical layers as K = 2 with neighbor sampling sizes S1 = 20 and S2 = 10, the number of random-walks for each node as 100 and the walk length as 5. The sampling time of our bi-attention layer is set as T = 10. For all methods, the dimensionality of embeddings is set to 256. Our approach is impemented in Tensorflow (Abadi et al. (2016)) and trained with the Adam optimizer (Kingma & Ba (2014)) at an initial learning rate of 0.0001. We report the comparison results in Table 1.

heading: 4.2 INDUCTIVE LEARNING IN EVOLVING GRAPHS
text: In real-world large and evolving graphs, inductive node embedding learning techniques would require high efficiency of the information extraction strategy as well as stability and robustness of the
embedding encoder. We here perform comparison against other approaches to show our method’s effective use in these challenging datasets.
Reddit is an large internet forum where users can post and comment on any content they are interested in. The task is to predict the community, that a post belongs to. We use the exact dataset conducted by Hamilton et al. (2017b). In this dataset, each node represents a post and are connected with one another if the same user comments on both of them. The node attribute is constructed by word2vec embeddings of post contents. The first 20 days is for training, and the rest for testing/validation. In all, this dataset contains 232,965 nodes(posts) with an average degree of 492. The first collumn summarizes the comparison results against GraphSAGE. For LSTM aggregator, our model shows slightly poorer performance, which is reasonable, because LSTM aggregator causes more differences between multiple sampled neighborhoods, not only the components but also the order, making it harder for our bi-attention layer to capture the proximities between neighborhoods. One can observe that BIGSAGE outperforms GraphSAGE in both mean and pool aggregator.
Another representative of evolving graphs we evaluate on is Pubmed, one of the commonly used citation network data . This dataset contains 19717 nodes and 44324 edges. We remove 20 percengt of the nodes as unseen, the rest for training. From the second column of Table 2 we find our model have better prediction results in all three aggregators.

heading: 4.3 GENERALIZING ACROSS GRAPHS
text: Generalizing accross graphs requires inductive methods capable of learning a transferable encoder function rather than the present community structure.
The protein-protein-interaction(PPI) networks dataset consists of 24 graphs corresponding to different human tissues(Zitnik & Leskovec (2017)). We use the preprocessed data provided by Hamilton et al. (2017b), where 20 graphs for training, 2 for validation and 2 for testing. For each node, there are 50 features representing their positional gene sets, motif gene sets and immunological signatures, and 121 labels set from gene ontology( collected from the Molecular Signatures Database (?)). This dataset contains 56944 nodes and 818716 edges.
The final collumn of Table 1 shows us that our method outperforms GraphSAGE by 14% at most on the PPI data. The results on three different aggregators indicates that the Mean-aggregator beats the other two in our method. And we also quote the micro-averaged F1 score of SPINE which is based on the exact same PPI dataset as ours.

heading: 4.4 MODEL STUDY
text: In this section we adjust BIGSAGE for tests on PPI to further study the seperate effect of bi-attention layer and global bias:
• BIGSAGE-ba: only with bi-attention layer, no global bias; • BIGSAGE-sg: with bi-attention layer, global bias only applied to embeddings of the last
layer;
• BIGSAGE-cb: with bi-attention layer, global bias applied to all layer during training but forgotten (reset to zero matrix) while generating embeddings.
From Table 2, we observe the three variant of BIGSAGE still show certain advance to the origin GraphSAGE, but reasonably less accurate than the origin BIGSAGE. The result of using only biattention layer proves the effect of bi-attended sampling. And the comparison between BIGSAGE-sg and BIGSAGE shows the high efficiency of applying global bias through all layers. From the result of BIGSAGE-cb, we find that even after training with global-bias, it’s critical to have the memory of the known nodes, which is stored in the learnt global embedding biases.

heading: 4.5 TRADE-OFF
text: We compare Graph2Gauss against our model as well as GraphSAGE on Pubmed and PPI. Note that Graph2Gauss only needs node attributes for embedding learning. The comparison results in Table 1 shows that our model and GraphSAGE beat g2g whether in evolving network data or generalizing across different graphs, which proves the significance of neighbor sampling for inductive learning and that certain trade-off exists between encoding granularity and embedding effect.

heading: 5 CONCLUSIONS
text: In this paper, we proposed BIGSAGE, an unsupervised and inductive network embedding approach which is able to preserve local proximity wisely as well as learn and memorize global identities for seen nodes while generalizing to unseen nodes or networks. We apply a bi-attention architeture upon hierarchical aggregating layers to directly capture the most relevant representations of co-occurring nodes. We also present an efficient way of combining inductive and transductive approaches by allowing trainable global embedding bias to be retrieved in all layers within the hierarchical aggregating framework. Experiments demenstrate the superiority of BIGSAGE over the state-of-art baselines on unsupervised and inductive tasks.

Review summaries:
This paper studied learning unsupervised inductive node embeddings with an attention mechanism. For each positive edge, multiple different sets of neighborhoods are sampled for both the source and target nodes, and the similarity between the neighborhood are used as the attention functions. Experimental results prove the effectiveness of the proposed approach over GraphSAGE on a few networks.