Title: BIGSAGE: UNSUPERVISED INDUCTIVE REPRESENTA-TION LEARNING OF GRAPH VIA BI-ATTENDED SAM-PLING AND GLOBAL-BIASED AGGREGATING

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.

1. INTRODUCTION:

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 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.

2. RELATED WORK:



2.1. NETWORK EMBEDDING:

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. Deep-Walk (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 & Gü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.

2.2. ATTENTION:

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.

3. MODEL:

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 h k , and the final output embedding z.

3.1. OVERVIEW:

To learn representations in unsupervised setting, we apply the same graph-based loss function used in the origin GraphSAGE:

J G (z v ) = -log(σ(z T v z vp )) -Q • E vn∼Pn(v) log(σ(-z T v z vn ))

where node v p co-occurs with v on fixed-length random walk (Perozzi et al. (2014) ), sigma is the sigmoid function, P n 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 G train (V train , E train ); node attributes X; global embedding bias matrix B; sampling times T 1: zero initialize(B) 2: h 0 v ← x v , ∀v ∈ V train 3: run random-walk in G train and do negative sampling to gain a set of triplets:

{(v, v p , v n )} 4: for (v, v p , v n ) do 5: Z 1 ← ∅, Z 2 ← ∅ 6:

for t ∈ {1, ..., T } do 7:

Z 1 ← Z 1 ∪ {SAGB(v)} 8: Z 2 ← Z 2 ∪ {SAGB(v p )} 9: z v , z vp ← BIATT(Z 1 , Z 2 ) 10: z vn ← SAGB(v n ) 11:

calculate the graph-based loss J G 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: 

Z i ← ∅, ∀i ∈ V test 3: for i, j ∈ {(v, v p )} do 4:

use step 5-9 in Algorithm 1 to generate z i , z j 5:

Z i ← Z i ∪ {z i } 6: Z j ← Z j ∪ {z j } return z v ← MEAN(Z v ), ∀v ∈ V test

3.2. CO-OCCURRENCE BI-ATTENDED "SAMPLING":

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

h K nt = A gg (h K-1 n , {h K-1 j∈N t (n) }) h K mt = A gg (h K-1 m , {h K-1 j∈N t (m) }) t = 1, ..., T

With T different representations corresponding to T different sampled neighborhoods, their similarity matrix can be calculated by S i,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):

• • • • • • • • Cross entropy loss Att u Att v Attention Matrix S ij

att n = reduce sum(sof tmax(S), 0), att m = reduce sum(sof tmax(S), 1), and apply attention to T Kth layer representations for the final encoded embeddings,

h n = T t=1 att nt h K nt h m = T t=1 att mt h K mt

The aggregation process with bi-attention architecture is illustrated by Figure 2 .

3.3. GLOBAL BIAS:

At first, we consider simply adding a trainable bias upon the encoder's final ouput for each node in training set,

z i = h K i + b i b i = one hot(i) T B

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: 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.

h k+1 i = W k+1 (h k i , {h k j∈N (i) }) + b k+1 agg + b i b i = one hot(i) T B z i ← h K i

We propose our aggregating process with global bias in Algorithm 3. 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.

4.3. GENERALIZING ACROSS GRAPHS:

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.

4.4. MODEL STUDY:

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.

4.5. TRADE-OFF:

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.

5. CONCLUSIONS:

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.

:

In random-walk based approaches, nodes that tend to cooccur in short random walks over the graph are usually referred as positive to each other.

Figures and Tables:

Figure 1: Visual illustration of the co-occurrence bi-attented sampling of nodes' neighborhood. The left one figure gives a vivid example of why we can use co-occurrence node to filter out useful information; and the two figures in the right show how attention from co-occurrence nodes affects sampling and aggregating over the neighborhood.

Figure 2: Bi-attention layer between the final aggregating layer and loss layer.

Figure 3: Applying global bias through aggregating .

Algorithm 2 BIGSAGE: generation of embedding input: Testing graph G test (V test , E test ); node attributes X test ; learned model BIGSAGE output: Vector representations z v for all v ∈ V test 1: run random-walks for each node in G test and gain a set of positive nodes pair:{(v, v p )} 2:

Table content: <table/>

Prediction results for the three datasets (micro-averaged F1 scores).

Table content: <table><tr><td/><td colspan="2">Reddit Pubmed</td><td>PPI</td></tr><tr><td>Graph2Gauss</td><td>-</td><td>0.789</td><td>0.430</td></tr><tr><td>SPINE</td><td>-</td><td>-</td><td>0.505</td></tr><tr><td colspan="2">GraphSAGE-mean 0.897</td><td>0.820</td><td>0.502</td></tr><tr><td>BIGSAGE-mean</td><td>0.927</td><td>0.834</td><td>0.573</td></tr><tr><td>GraphSAGE-seq</td><td>0.907</td><td>0.811</td><td>0.505</td></tr><tr><td>BIGSAGE-seq</td><td>0.903</td><td>0.828</td><td>0.563</td></tr><tr><td>GraphSAGE-pool</td><td>0.892</td><td>0.830</td><td>0.510</td></tr><tr><td>BIGSAGE-pool</td><td>0.915</td><td>0.843</td><td>0.566</td></tr></table>



Table content: <table><tr><td colspan="2">: Model Study</td></tr><tr><td/><td>PPI</td></tr><tr><td colspan="2">GraphSAGE 0.502</td></tr><tr><td colspan="2">BIGSAGE-ba 0.521</td></tr><tr><td colspan="2">BIGSAGE-sg 0.518</td></tr><tr><td colspan="2">BIGSAGE-cb 0.523</td></tr><tr><td>BIGSAGE</td><td>0.572</td></tr></table>

Peer review (iclr2019):
 This paper modifies the GraphSAGE on unsupervised inductive node embedding. The authors propose to use the bi-attention architecture to sample interesting nodes (instead of the uniform sampler in GraphSAGE), and to use a global embedding bias matrix in the local aggregating functions. The method showed improvements over GraphSAGE and other baselines on unsupervised graph embeddings. The proposition makes sense and the performance improvements are expected. A major comment, however, is that that the proposed method is useful in very restricted settings, and it is not clear how to generalize to other applications which GraphSAGE can be applied on. The overall technical contribution is incremental and may not have enough novelty to be published in ICLR. The technical representation is very poor, unorganized and not self-contained. The paper cannot pass the threshold merely based on the way it is presented. In the algorithms, please give the output besides the input. After the algorithms, please remark on the computational and memory cost. In algorithm 1, what is this function BIATT()? After algorithm 1, please describe this function as well as SAGE(). In the beginning of section 3, please describe the meaning of the global bias matrix. In algorithm 1, if B is zero-initialized, why does one need it as input? Some of the equations are poor formatted (e.g. reduce_sum in page 5). Please try to use rigorous mathematical formulations instead of "pseudo equations". For example, re-write "One_hot(i)". In section 3.2, explain A_{gg}, etc. use instead of . There are many typos.