Year: 2019

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

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

heading: 1 INTRODUCTION
text: The study of real world graphs, such as social network analysis (Hamilton et al. (2017a)), molecule screening (Duvenaud et al. (2015)), knowledge base reasoning (Trivedi et al. (2017)), and biological protein-protein networks (Zitnik & Leskovec (2017)), evolves with the development of computing technologies. Learning vector representations of graphs is effective for a variety of prediction and graph analysis tasks (Grover & Leskovec (2016); Tang et al. (2015)). High-dimensional information about neighbors of nodes are represented by dense vectors, which can be fed to off-the-shelf approaches to tasks, such as node classification (Wang et al. (2017); Bhagat et al. (2011)), link prediction (Perozzi et al. (2014); Wei et al. (2017)), node clustering (Nie et al. (2017); Ding et al. (2001)), recommender systems (Ying et al. (2018a)) and visualization (Maaten & Hinton (2008)).
There are mainly two types of models for graph representation learning. Transductive approaches (Perozzi et al. (2014); Grover & Leskovec (2016); Tang et al. (2015)) are able to learn representations of existing nodes but unable to generalize to new nodes. However, in real-world evolving graphs such as social networks, new users will join and must be represented. Inductive approaches were proposed to address this issue. GraphSAGE (Hamilton et al. (2017b)), a hierarchical sampling and aggregating framework, successfully leverages feature information to generate embeddings of the new nodes. However, GraphSAGE has its own faults. Firstly, it samples all neighborhood nodes randomly and uniformly; secondly, it treats the output of encoder as the final representation of node.
Based on the hierarchical framework of GraphSAGE, GAT (Velickovic et al. (2017)) uses given class labels to guide attention over neighborhood so as to aggregate useful feature information. However, without knowledge of ground-truth class labels, it is difficult for unsupervised approaches to apply attention. To address this issue, we introduce a dual encoding framework for unsupervised inductive representation learning of graphs. Instead of learning self-attention over neighborhoods of nodes, we exploit the bi-attention between representations of two nodes that co-occur in a short random-walk (which we call a positive pair).
In Figure 1, we illustrate how nodes are embedded into low-dimensional vectors, where each node v has an optimal embeddings ov . Yet the direct output of encoder zv of GraphSAGE could be located anywhere. Specifically, given feature input from both sides of a positive pair (v, vp), a neural network is trained to encode the pair into K different embeddings zkv and z k vp through different sampled neighborhoods or different encoding functions. Then, a bi-attention layer is applied to generate the most adjacent matches zv|vp and zvp|v, which will be referred as dual-representations. By putting most attention on the pair of embeddings with smallest difference, dual representation of nodes with less deviation will be generated, which can be visualized as zv|· in Figure 1.
GraphSAGE naively assumes that unseen graph structure should be (easily) represented by known graphs data. We combine the ground truth structure and the learned dual-encoder to generate final representation. Unseen nodes can be represented based on their neighborhood structure. Current inductive approaches have no direct memory of the training nodes. We combine the idea of both transductive and inductive approaches via associating an additive global embedding bias to each node, which can be seen as a memorable global identification of each node in training sets.
Our contributions can be summarized as follows:
• we introduce a dual encoding framework to produce context-aware representation for nodes, and conduct experiments to demonstrate its efficiency and effectiveness;
• we apply bi-attention mechanism for graph representation dual learning, managing to learn dual representation of nodes more precisely;
• we combine the training of transductive global bias with inductive encoding process, as memory of nodes that are already used for training.

heading: 2 RELATED WORK
text: Following (Cai et al. (2018), Kinderkhedia (2019) and Goyal & Ferrara (2018)), there are mainly two types of approaches:

heading: 2.1 NETWORK EMBEDDING
text: For unsupervised embedding learning, DeepWalk (Perozzi et al. (2014)) and node2vec (Grover & Leskovec (2016)) are based on random-walks extending the Skip-Gram model; LINE (Tang et al. (2015))seeks to preserve first- and second-order proximity and trains the embedding via negative sampling; SDNE (Wang et al. (2016)) jointly uses unsupervised components to preserve secondorder proximity and expolit first-order proximity in its supervised components; TRIDNR (Pan et al. (2016)), CENE(Sun et al. (2016)), TADW (Yang et al. (2015)),GraphSAGE (Hamilton et al. (2017b)) utilize node attributes and potentially node labels. Convolutional neural networks are also applied to graph-structured data. For instance, GCN (Kipf & Welling (2017)) proposed an simplified graph convolutional network. These graph convolutional network based approaches are (semi)supervised. Recently, inductive graph embedding learning (Hamilton et al. (2017b) Velickovic et al. (2017) Bojchevski & Günnemann (2017) Derr et al. (2018) Gao et al. (2018), Li et al. (2018), Wang et al. (2018) and Ying et al. (2018b)) produce impressive performance across several large-scale benchmarks.

heading: 2.2 ATTENTION
text: Attention mechanism in neural processes have been extensively studied in neuroscience and computational neuroscience (Itti et al. (1998); Desimone & Duncan (1995)) and 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)). Inspired by (Seo et al. (2016) and Abu-El-Haija et al. (2018)), we construct a bi-attention layer upon aggregators to capture useful parts of the neighborhood.

heading: 3 MODEL
text: Let G = {V,E,X} be an undirected graph, where a set of nodes V are connected by a set of edges E, and X ∈ R|V |×f is the attribute matrix of nodes. A global embedding bias matrix is denoted by B ∈ R|V |×d, where a row of B represents the d-dimensional global embedding bias of a node. The hierarchical layer number, the embedding output of the l-th layer and the final output embedding are denoted by L, hl and z, respectively.

heading: 3.1 CONTEXT-AWARE INDUCTIVE EMBEDDING ENCODING
text: The embedding generation process is described in Algorithm 1. Assume that the dual encoder is trained and parameters are fixed.
Algorithm 1 Context-Aware Dual-Encoding (CADE) input: the whole graph G = (V,E); the feature matrix X; the trained DualENC output: learned embeddings z;
1: Run random walks on G to gain a set of positive pair P; 2: Zv ← ∅, ∀v ∈ V 3: for (v, vp) ∈ P do 4: zv, zvp = DualENC(v, vp,G,X); 5: Zv ← Zv ∪ zv 6: Zvp ← Zvp ∪ zvp 7: end for 8: for v ∈ V do 9: zv = Mean(Zv);
10: end for
After training, positive pairs are collected by random walks on the whole dataset. The features of each positive pair are passed through a dual-encoder. Embeddings of nodes are generated so that the components of a pair are related and adjacent to each other.

heading: 3.2 DUAL-ENCODER WITH MULTI-SAMPLING
text: In this subsection, we explain the dual encoder.
Algorithm 2 DualENC input: Training graph G(V,E); node attributes X; global embedding bias matrix B; sampling times K; positive node pair (v, vp); output: adjacent embeddings zv and zvp ;
1: For node v and vp, generate K embeddings, hv , hvp , using a base encoder SAGB 2: for i, j ∈ {1, ...,K} do 3: Si,j ← α(hvi,hvpj) 4: end for 5: softmax on flattened similarity matrix S: Si,j ← e
Si,j∑K,K 0,0 e Si,j
6: calculate attention av and avp : avi ← ∑K j=1 Si,j ,avpj ← ∑K i=1 Si,j
7: zv ← ∑K t=1 avkh L vk
8: zvp ← ∑K t=1 avpkh L vpk
In the hierarchical sampling and aggregating framework (Hamilton et al. (2017b)), it is challenging and vital to select relevant neighbor with the layer goes deeper and deeper. For example, given
word ”mouse” and its positive node ”PC”, it is better to sample ”keyboard”, instead of ”cat”, as a neighbor node. However, to sample the satisfying node according to heuristic rules layer by layer is very time consuming, and it is difficult to learn attention over neighborhood for unsupervised embedding learning.
As a matter of fact, these neighbor nodes are considered to be useful because they are more welcome to be sampled as input so as to produce more relevant output of the dual-encoder. Therefore, instead of physically sampling these neighbor nodes, in Step 2 to Step 6 in Algorithm 2, we directly apply a bi-attention layer on the two sets of embedding outputs with different sampled neighborhood feature as input, so as to locate the most relevant representation match, as a more efficient approach to exploring the most useful neighborhood.
We use the hierarchical sampling and aggregating framework as a base encoder in our experiments, but it can also be designed in many other ways.
Given node v, and node vp as a positive node pair, after sampling and aggregating for K times, we have K different representations hvk/hvpk corresponding to K different sampled neighborhoods, their similarity matrix can be calculated by
Si,j = α(hvi,hvpj), i, j = 1, ...,K (1)
where α represents an dot-product operation.
our goal is to find the closest neighborhood match between v and vp within K ×K possibilities, so we apply softmax on the flattened similarity matrix, and sum up by row(column). In this way, we manage to gain different attention over K neighborhoods of v(vp) with respect to vp(v),
Sij ← exp(Sij)∑K,K
0,0 exp(Sij) (2)
avi = K∑ j=1 Sij (3)
avpj = K∑ i=1 Sij (4)
and sum up the lth layer representations with attention as the dual-encoder outputs,
zv = K∑
k=1
avkhvk (5)
zvp = K∑
k=1
avpkhvpk (6)
To train our encoder before using it to generate final representations of nodes, we apply a typical pair reconstruction loss function with negative sampling Hamilton et al. (2017b):
JG(zv) = −log(σ(zTv zvp))−Q · Evn∼Pn(v)log(σ(−z T v zvn)) (7)
where node vp co-occurs with v on fixed-length random walk (Perozzi et al. (2014)), σ is the sigmoid function, Pn is a negative sampling distribution, Q defines the number of negative samples. Note that zv and zvp are dual representation to each other while zvn represents the direct encoder output of negative sample vn.

heading: 3.3 DUAL-ENCODER WITH MULTI-AGGREGATING
text: Besides learning dual representation with multiple sampling, we introduce another version of our dual encoder with multiple aggregator function.The intuition is that through different perspective, a node can be represented differently corresponding to different kinds of positive nodes.
In Step 1 in Algorithm 2, for a node v, we sample neighborhood once and aggregate feature with K sets of parameters, gaining K different representations hvk corresponding to K different character of v. Given a positive node pair, v and vp, their dual representation are calculated by applying biattention as we described in the last section. There is but one difference that we use a weigh vector A ∈ R2d as parameter instead of dot-product, to calculate the K×K attention matrix between node v and node vp,
Sij ← exp(AT[hvi||hvpj ])∑K,K
0,0 exp(A T[hvi||hvpj ])
(8)
where ·T represents transposition and || is the concatenation operation. The rest of calculation of dual representation is the same as section 3.2.
Another difference is during training. With K sets of parameter for aggregating, negative sample vn is now also represented by K different embeddings. As shown in Figure 2, we set K = 5 and use different shape to represent the embeddings of the positive node pair and the negative sampled nodes.
As we can see in Figure 2, to make sure that any embeddings of node vn as far away from any of node v as possible, it is equal to maximizing the distance between their support embeddings, which is the closest pair of embeddings of v and vn. The support embedding can be calculated by the learned dual encoder. In conclusion, our loss function can be modified as follows,
JG(zv) = −log(σ(zTv zvp))−Q · Evn∼Pn(v)log(σ(−z ′T v zvn)) (9)
zv, zvp = DualENC(v, vp,A) (10) z′v,zvn = DualENC(v, vp,A ∗) (11)
where A∗ representing that we stop the back-propagation through A in dual encoding for negative sample node, since A are supposed to learn bi-attention between the positive node pair and be reused only to capture the support embedding of v and its negative sample nodes.

heading: 3.4 MEMORABLE GLOBAL BIAS IN HIERARCHICAL ENCODING
text: In this section, we first explain the base encoder used in our proposed dual encoding framework, and then we introduce how we apply memorable global bias within this framework.
The general intuition of GraphSAGE is that at each iteration, nodes aggregate information from their local neighbors, and as this process iterates, nodes incrementally gather more and more information
from further reaches of the graph. For generating embedding for one specific node u, we describe the process below. First, we construct a neighborhood tree with node u as the root, Nu, by iteratively sampling immediate neighborhood of nodes of the last layer as children. Nodes at the lth layer are represented by symbol Nlu, N0u = {u}. Then, at each iteration, each node i aggregates the representations of its children j, {hl−1j }, and of itself, h l−1 i , into a single vector h l i, as representation of the next layer. After L iterations, we gain the Lth layer representation of v, as the final output.
While this framework generates good representation for nodes, it cannot preserve sufficient embedding informations for known nodes. More specifically, for nodes that are known but trained less than average, the learned model would have treated them like nodes unmet before. Therefore, we intuitively apply distinctive and trainable global bias to each node, as follows:
hl−1S(i) ← AGGREGATEl({h l−1 j , ∀j ∈ S(i)}) (12)
hli ← σ(W l · [hl−1i ||h l−1 S(i)]) (13)
hli ← hli + bi, l < L (14) bi ← one hot(i)TB (15)
(16)
where B ∈ R|V |×d is the trainable global bias matrix, S(i) represents the sampled neighborhood and also the children nodes of node i in the neighborhood tree, AGGREGATE represents the neighborhood aggregator function, and || is a operator of concatenating vectors. On one hand, B can be reused to produce embeddings for the known nodes or the unknown connected with the known, as supplement to the neural network encoder. On another hand, the global bias vectors can partially offset the uncertainty of the encoding brought by the random sampling not only during the training but also the final generation. Lastly but not least, we use only one set of global bias for all nodes, which means for any node, its representations of hidden layers are all added by the same bias vector. As a result of that, we are able to update parameters of aggregator function in the lowest layer with the global updated bias of nodes, highly increasing the training efficiency.
It is important for us to apply no global bias to the last layer of output, which is also the candidate of the dual-encoder output of nodes before applied with attention. The reason is that applying extra bias onto the last layer would directly change the embedding distribution of known nodes, making it unequal to the embedding distribution of unseen nodes. In general, the implementation of the base encoder with global bias is shown in Algorithm 3. The * in Step 8 means the children of node i in the neighborhood tree Nu.
Algorithm 3 SAGB:sampling and aggregating with global bias input: node u; hierarchical depth L; weight matrices W l; non-linearity σ; differentiable neighbor aggregator AGGREGATEl; fixed-size uniform sampler S : v → 2V output: embedding zu;
1: N0u = {u}; 2: for l = 1...L do 3: Nlu ← {S(i), ∀i ∈ Nl−1u }; 4: end for 5: for l=1...L do 6: for i ∈ N0u ∪ N1u ∪ ... ∪ NL−lu do 7: hl−1S∗(i) ← AGGREGATEl({h l−1 j , ∀j ∈ S∗(i)}) 8: hli ← σ(W l · [h l−1 i ||h l−1 S∗(i)])
9: if l < L: hli ← hli + one hot(i)TB 10: end for 11: end for 12: return zu ← hLu

heading: 4 EXPERIMENTS
text: In this section, we compare CADE against two strong baselines in an inductive and unsupervised setting, on challenging benchmark tasks of node classification and link prediction. We also perform further studies of the proposed model in section 4.5.

heading: 4.1 DATASETS
text: The following graph datasets are used in experiments and statistics are summarized in Table1:
• Pubmed: The PubMed Diabetes (Sen et al. (2008))1 dataset is a citation dataset which consists of scientific publications from Pubemd database pertaining to diabetes classified into one of three classes. Each publication in the dataset is described by a TF/IDF (Salton & Yu (1973)) weighted word vector from a dictionary.
• Blogcatalog: BlogCatalog2 is a social blog directory which manages bloggers and their blogs, where bloggers following each others forms the network dataset.
• Reddit: Reddit3 is an internet forum where users can post or comment on any content. We use the exact dataset conducted by (Hamilton et al. (2017b)), where each link connects two posts if the same user comments on both of them.
• PPI: The protein-protein-interaction (PPI) networks dataset contains 24 graphs corresponding to different human tissues(Zitnik & Leskovec (2017)). We use the preprocessed data also provided by (Hamilton et al. (2017b)).

heading: 4.2 EXPERIMENTAL SETTINGS
text: We compare CADE against the following approaches in a fully unsupervised and inductive setting:
• GraphSAGE: In our proposed model, CADE, the base encoder mainly originates from GraphSAGE, a hierarchical neighbor sampling and aggregating encoder for inductive learning. Three alternative aggregators are used in Graphsage and CADE: (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.
Beside the above two models, we also include experiment results of raw features as baselines. In comparison, we call the version of dual-encoder with multiple sampling as CADE-MS, while the version with multiple aggregator function as CADE-MA.
1Available at https://linqs.soe.ucsc.edu/data. 2http://www.blogcatalog.com/ 3http://www.reddit.com/ 4PPI is a multi-label dataset.
For CADE-MS, CADE-MA and GraphSAGE, we set the depth of hierarchical aggregating as L = 2, the neighbor sampling sizes as s1 = 20, s2 = 10, and the number of random-walks for each node as 100 and the walk length as 4. The sampling time in CADE-MS or the number of aggregator in CADE-MA is set as K = 10. And for all emedding learning models, the dimension of embeddings is set to 256, as for raw feature, we use all the dimensions. 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.

heading: 4.3 INDUCTIVE NODE CLASSIFICATION
text: We evaluate the node classification performance of methods on the four datasets. On Reddit and PPI, we follow the same training/validation/testing split used in GraphSAGE. On Pubmed and Blogcatalog, we randomly selected 10%/20%/30% nodes for training while the rest remain unseen. We report the averaged results over 10 random split.
After spliting the graph dataset, the model is trained in an unsupervised manner, then the learnt model computes the embeddings for all nodes, a node classifier is trained with the embeddings of training nodes and finally the learnt classifier is evaluated with the learnt embeddings of the testing nodes, i.e the unseen nodes.
Comparation on node classification performance on Pubmed and Blogcatalog dataset with respect to varying ratios of unseen nodes, are reported in Table 2. CADE-MS and CADE-MA outperform other approaches on Pubmed. On Blogcatalog dataset, however, RawFeats performs best mainly because that, in Blogcatalog dataset, node features are not only directly extracted from a set of user-defined tags, but also are of very high dimensionality (up to 8,189). Hence extra neighborhood information is not needed. As shown in Table 2, CADE-MA performs better than CADE-MS, and both outperform GraphSAGE and G2G. CADE-MA is capable of reducing high dimensionality while losing less information than CADE-MS, CADE-MA is more likely to search for the best aggregator function that can focus on those important features of nodes. As a result, the 256-dimensional embedding learnt by CADE-MA shows the cloest node classification performance to the 8k-dimensional raw features.
Comparasion among GraphSAGE, CADE and other aggregator functions is reported in Figure3. Each dataset contains 30% unseen nodes. In general, the model CADE shows significant advance to the other two state-of-art embedding learning models in node classification on four different challenging graph datasets.

heading: 4.4 INDUCTIVE LINK PREDICTION
text: Link prediction task evaluates how much network structural information is preserved by embeddings. We preform the following steps: (1) mark some nodes as unseen from the training of embedding learning models. For Pubmed 20% nodes are marked as unseen; (2) randomly hide certain percentage of edges and equal-number of non-edges as testing edge set for link prediction, and make sure not to produced any dangling node; (3) the rest of edges are then used to form the input graph for embedding learning and with equal number of non-edges form the training edge set for link predictor; (4) after training and inductively generation of embeddings, the training edge set and their corresponding embeddings will help to train a link predictor; (5) finally evaluate the performance on the testing edges by the area under the ROC curve (AUC) and the average precision (AP) scores.
Comparation on performance with respect to varying percentage of hidden edges are reported in Table3. CADE shows best link prediction performance on both datasets.

heading: 4.5 MODEL STUDY

heading: 4.5.1 SAMPLING COMPLEXITY IN CADE-MS
text: Our proposed CADE-MS requires multiple neighborhood sampling, which increases the complexity of embedding learning. Yet by comparing CADE-MS against GraphSAGE with the same quantity of sampled neighborhood per node, the superiority of CADE model over existing models is still vast. In practice, we set the sampling layer L = 2 and the first-layer sampling size as 20. For the second layer, denote by s′2 the sampling size in GraphSAGE, and by s2 and T the sampling size and sampling time in CADE-MS. We compare the two methods with s′2 = s2 ∗K. A variant of CADE, called CADE-gb, applies only memorable global bias and no dual-encoding framework,
has the same sampling complexity as GraphSAGE. For the efficiency of experiment, we conduct experiments of node classification on a small subset of PPI, denoted by subPPI, which includes 3 training graphs plus one validation graph and one test graph. Results are reported in Figure 4. With much smaller sampling width, CADE-MS still outperforms the original framework significantly.
It implicates that searching for the best representation match through multiple sampling and biattention is efficient to filtering userful neighbor nodes without supervision from any node labels, and that the context-aware dual-encoding framework is capable of improving the inductive embedding learning ability without increasing sampling complexity. We aslo observe that CADE-gb, the variant simply adding the memorable global bias, continually shows advance in different sampling sizes.

heading: 4.5.2 THE NECESSARITY OF HIDDEN MEMORY
text: It is necessary not to apply global bias to the encoder output. We compare the original framework GraphSAGE, CADE with the variants of our method: applying global bias only to the last layer, and only to the former layers. As Table 4 shows, CADE-gl performs poorly, while CADE-gb demonstrates the effect of keeping memory of the hidden representation for each node.

heading: 5 CONCLUSION
text: In this paper, we proposed CADE, an unsupervised and inductive network embedding approach which is capable of preserving local connectiveness distinctively , as well as learning and memorizing global identities for seen nodes while generalizing to unseen nodes. We applied a bi-attention architeture upon hierarchical aggregating layers to capture the most relevant representations dually for any positive pair. We also present an effective way of combining inductive and transductive ideas by allowing trainable global embedding bias to be retrieved in hidden layers within the hierarchical aggregating framework. Experiments demonstrate the superiority of CADE over the state-of-art baselines on unsupervised and inductive tasks. In the future, we would explore several possibilities, such as expanding dual encoding from pair-wise to n-wise, or using dual encoding framework in supervised embedding learning, or combing dual encoding with G2G by learning distribution representations dually for positive pairs.

Review summaries:
This paper proposed a dual graph representation method to learn the representation of nodes in a graph. In particular, it learns the embedding of paired nodes simultaneously for multiple times, and use the mean values as the final representation. The experimental result demonstrates some improvement over existing methods. Overall, the idea is presented clearly and the writing is well structured. But the novelty is limited. Specifically, 

This paper extends GraphSAGE in several dimensions: 1) applying attention when aggregating neighbors (already used by GAT and many other approached); 2) Ensembling node embedding by applying DualENC multiple times on positive pairs selected by random walk (this is doing aggregation of neighborhood again); and 3) adding global bias. All this makes the proposed method an incremental extension of existing solutions.  There is no theoretical justification why these extensions should work.