GCN-LASE: Towards Adequately Incorporating Link Attributes in Graph Convolutional Networks

1 Introduction

After several attempts and modifications ([Bruna et al., 2014] [Niepert et al., 2016] [Kipf and Welling, 2016] [Tao et al., 2017] [Jie et al., 2018]), Graph Convolutional Networks (GCNs) 1 are rapidly gaining popularity due to its excellent performance in aggregating neighborhood information for individual graph nodes. Although low-rank proximities and node features are successfully leveraged through the convolutional layers, the attributes that graph links may carry are generally ignored in GCNs. In almost all existing GCNs, graph links are regarded as indicators of proximities between nodes. These proximities are only used to identify neighborships (and their influences if weighted) in the local neighborhoods.

∗This work was supported by the National Natural Science Foundation of China (Grant No. 61876006 and No. 61572041).

†Corresponding author.

1 Although some papers do not explicitly use the term convolution, such as [Tao et al., 2017] and [Hamilton et al., 2017], a similar idea of aggregating features in a node's neighborhood can be seen in the models. Therefore, we categorize all similar work into the class of graph convolutional networks.

However, in real-world scenarios, a link between a pair of nodes carries a lot more information than a simple indicator of neighborship. It represents a hypostatic relationship between two entities, usually with concrete attributes. For example, two connected people in a social network may have different relationships including family members, colleagues and alumni, and thus their communication patterns and contents may vary; a link in a business network represents a transaction between two companies, and the properties of such transactions are tremendously informative. Therefore, revisiting these link attributes, which are generally ignored in current GCNs, allows us to recover the exact relationships between nodes.

While one can leverage link attributes in GCNs with tricks, such as concatenating them to neighbor node attributes, these implementations cannot adequately captures the interactions between the attributes 2 . To the best of our knowledge, there is no previous work focusing on incorporating link attributes into GCNs. We propose GCN-LASE (Graph Convolutional Network with Link Attributes and Sampling Estimation) as an attempt. LASE is an extension of GCN, which also learns a function that maps a target node to its hidden representation considering the local neighborhood features and structures, but including both link and neighbor node attributes. The aggregated features are then used to conduct downstream tasks.

To leverage the link and node attributes as well as the interactions in between, we adopt their tensor products as the fully associated neighbor features, based on which a neighbor kernel is developed using the inner products of tensors. We further derive corresponding graph kernels and finally the neural architectures following a similar route introduced in [Tao et al., 2017]. An intuitive understanding of LASE is then demonstrated, by modularizing it into a gate, an amplifier, and an aggregator. Meanwhile, we adopt the Monte Carlo method to quickly estimate the sum of features in neighborhoods. We also introduce a novel sampling setup for LASE to reduce the estimation variance.

2 See Section 3 for detailed introduction.

Recovering more information is not the only benefit LASE brings about-it also enlarges the expressive abilities of graph structures that GCNs can handle. At lease two other types of graph-structured data can be handled with LASE: i) Graphs with heterogenous links, where link weights from different perspectives can be arranged into vectors and used as attributes; ii) Dynamic or temporal graphs, where link weights from different time-stamps can be stacked together and used as attributes. See Figure 1 for detailed examples. We validate our approach on four datasets across different domains, and further design additional experiments in order to demonstrate the informativeness of link attributes and the effect of our sampling strategy.

2 RelatedWork

Our method builds upon previous work of machine learning on graph data, including graph convolutional networks, graph kernels and node representation learning.

Graph convolutional networks. The past few years have seen plenty of works focusing on implementing deep architectures over graphs ([Bruna et al., 2014] [Henaff et al., 2015] [Kipf and Welling, 2016] [Wang et al., 2016] [Niepert et al., 2016] [Hamilton et al., 2017] [Tao et al., 2017]), among which the convolutional networks seem to be the most appealing. There are mainly two types of convolutional networks existing, one learning features for entire graphs ([Tao et al., 2017] [Niepert et al., 2016]), the other for individual nodes ([Kipf and Welling, 2016] [Hamilton et al., 2017]). Both methods interpret the concept of convolution as merging node features in local neighborhoods. Meanwhile, as early GCNs ([Kipf and Welling, 2016]) does not support mini-batch training, modifications towards better efficiency emerge ([Hamilton et al., 2017] [Jie et al., 2018] [Huang et al., 2018]), in which the Monte Carlo method is generally used to estimate neighborhood representations through a controllable size of nodes. In our paper, a different sampling implementation is adopted, which makes a tradeoff between variance and efficiency by controlling the interval of calculating the optimal sampling probabilities.

Graph kernels. Kernel methods [Sch¨olkopf and Smola, 2002] have long been an important class of machine learning techniques, while it remains challenging to define effective and convenient kernels for graphs. Existing graph kernels ([G¨artner et al., 2003] [Vishwanathan et al., 2008] [Shervashidze et al., 2011]) are typically defined over of substructures in graphs, such as sub-trees and walk sequences. Later, [Tao et al., 2017] introduces an innovative route to develop neural architectures using graph kernels 3 . To the best of our knowledge, there is no existing work aiming at incorporating link attributes into graph kernels. In our paper, we adopt a similar route as [Tao et al., 2017] to design LASE, but using novel graph kernels which are able to handle link attributes.

Node representation learning (NRL). NRL aims to learn low-dimensional embeddings for graph nodes ([Perozzi et al., 2014] [Tang et al., 2015] [Grover and Leskovec, 2016] [Ribeiro et al., 2017] [Hamilton et al., 2017] [Li et al., 2018] [Du et al., 2018]), which are later used in downstream prediction tasks such as node classification and link prediction. GCNs can, in a broader sense, also be classified as NRL methods when regarding the hidden layers of nodes as embedding vectors. However, few existing NRL models incorporate link attributes. In Section 5, We compare the performances of LASE with several other NRL approaches.

3 Model

In this section, we introduce the architecture of LASE (see Figure 2) and the motivation behind. We first extend the concept of a neighbor 4 , and the features of a neighbor is then defined as the tensor product of its node and link attributes. As directly using these tensors of features in GCNs would be clumsy, we design new graph kernels under this setup, based on which we further derive possible architectures of LASE. In the end, we modularize LASE and provide intuitive understandings of the modules' functions. Notations in this paper are illustrated in Table 1. Vectors in this paper are all formed in columns.

3 These architectures have better explainability as the hidden representations can be interpreted as a series of inner products of the input graph and some sample graphs. See Theorem 1 for detailed explanation.

3.1 Neighbor Feature Tensors

One simplest idea to incorporate link attributes in GCN models is to concatenate them to the node's attributes, i.e.

where W = [W1,W2]. However, as attributes of neighbor nodes and neighbor links are individually summed among the neighborhood, such implementations can not at all capture the interactions within a (node, link) neighbor. As the key idea behind LASE is to adequately incorporate link attributes into node hidden representations, these interactions cannot be ignored. Moreover, this setup also leads to the confusion demonstrated in Figure 3, indicating that the graph structure is not appropriately captured.

Instead of simply adding or concatenating node and link attributes, we define their tensor product 5 as the associated neighbor feature. The calculated tensor contains all bilinear combinations of the two attributes, and serves as a fully conjoined feature. Formally, for the central node u connected to v by a link eu,v , the corresponding neighbor feature is defined as

4 The term neighbor is used for an ordered pair, containing a neighbor node and the link connecting it to the central node, similarly hereinafter.

However, directly using the tensor as inputs leads to unacceptably high dimensionalities and heavy redundancies, for the feature matrix (i.e. the 2D-tensor) is only of rank 1. Instead, we adapt existing graph kernels for so-defined neighbor features, and derive a concise architecture for LASE following [Tao et al., 2017]'s route.

3.2 Graph Kernels with Link Attributes

To adapt existing kernels to our setup of neighbor features, we first define the kernel of two neighbors, (v, e·,v) and (w, e·,w). The neighbor kernel is defined as the inner product of the neighbor tensors, i.e.

Based on the neighbor kernel, a kernel of two l-hop neighborhoods with central node u and u′ can be defined as K(l) N (u, u′ ) :=

5 Briefly speaking, the tensor product of two (column) vector a and b is calculated as abT with shape (da × db).

by regarding the lower-hop kernel, K(l-1) N (v, v′ ), as the inner product of the (l - 1)-th hidden representations of v and v′ . λ ∈ (0, 1) is a decay factor. Furthermore, by recursively applying the neighborhood kernel, we can derive the l-hop RandomWalk kernel for graphs with link attributes as

where Pl(G) denotes the set of all walk sequences of length l in graph G, and ui denotes the i-th node in sequence u. 6

3.3 FromKernels to Neural Architectures

Following the route introduced in [Tao et al., 2017] with above Random Walk kernel, a corresponding architecture LASE-RW can be immediately derived as

This architecture further enjoys a similar property to the architecture described in [Tao et al., 2017]. We first construct Ll,k = (VL, EL) using the k-th row vectors in the parameter matrices 7 as node and link attributes. The node set VL = {v0, · · · , vl} with f(vi) =W(i) k , and the link set EL ={evi,vi+1 } with f (evi ,vi+1 ) = U(i+1) k . Then, we have the following theorem:

Theorem 1. For any l ≥ 1, the sum of h(l) (v)[k] (the k-th coordinate of h(l) (v)) satisfies

and thus ∑v∈VG h(l) (v)[k] lies in the RKHS of kernel KlW . Similarly, the architecture LASE-WL derived from Weisfeiler-Lehman Kernel should be adapted as

6 A Weisfeiler-Lehman kernel can also be defined by adopting the graph relabeling process, which is detailedly introduced in [Tao et al., 2017]. We skip this part due to the limitation of space.

7 Denoted as {W(0) k , · · · ,W(l) k } and {U(1) k , · · · , U(l) k }.

The Weisfeiler-Lehman architecture is originally designed to convolute nodes through both depth (r) and breadth (h), however, the calculation of LASE-WL would be too complex. We unite the depth and breadth convolution to reduce model size, and by referring to the neighborhood aggregation concept in GraphSAGE [Hamilton et al., 2017], proposed LASE-

where ◦ is a combination operation such as +, ⊙ or ⊕.

3.4 Discussion

Although [Tao et al., 2017] is originally introduced for aggregating features for entire graphs, its output graph features are an activated sum of all nodes features. We reckon these node features be as well informative in node-wise prediction tasks. We also provide an intuitive understanding of LASE. The calculations in LASE can be divided into three common modules, namely a gate, an amplifier and an aggregator, as is shown in Figure 2. Intuitively, the gate (λu,v) evaluates v's influence in u's neighborhood. The amplifier (h(v)⊙Uf(eu,v)) element-wisely amplifies the node attributes using link information 8 . The aggregator sums up neighbor embeddings and combines them with the central node embedding using various strategies. Aggregators proposed in [Hamilton et al., 2017] may also be used in LASE.

4 Sampling Estimation

Similar to GCN [2016], scalability is an obvious challenge for LASE: calculating the convolutions demands a recursively expanded neighborhood. For nodes with high degrees, it will quickly cover a large portion of the graph. To control batch scales, we leverage the Monte Carlo method to estimate the summed neighborhood information by sampling a fixed number of neighbors. Despite different architectures, the output hidden embeddings of LASE can all be formulated as

where p(l) (·|u) denotes the sampling probabilities in N(u). We then approximate h(l) (u) through estimating the expectation. As the sampling process is always unbiased, we look for the optimal probabilities that minimize the estimation variance.

8 A slight elevation in performance can be observed when applying a sigmoid activation on Uf(eu,v), which makes the vector functions more analogously to an amplifier.

Although there are existing sampling strategies proposed for GCNs ([Jie et al., 2018] [Huang et al., 2018]), these methods cannot be directly transferred to LASE because of the absence of explicit, constant link weights. Besides, the optimal distribution varies through the training process. However, a similar idea of importance sampling, coined gate sampling, can be used in LASE by regarding the decay factor λs as the sampling weights, that is,

While sampling with gates may reduce the estimation variance, it is not an optimal solution because typically the norms of g(l) (v|u)s are different. According to the derivations of importance sampling in [Owen, 2013], we derive min var sampling, the optimal sampling probabilities as

Evaluating the sampling probabilities batch-wisely can be rather inefficient. Under the hypothesis that the network parameters do not dramatically vary from batch to batch, we make a tradeoff between variance and efficiency by controlling the interval of calculating the optimal distribution. That is, the sampling probabilities for all training nodes are calculated every k batches. Although the calculation may be timeconsuming, the batch-averaged time cost will be reduced to 1/k.

5 Experiments

5.1 Experiment Setups

Datasets. We validate our method on the four datasets introduced below, including a graph with link attributes (reddit), a graph with heterogenous links (dblp), and two temporal networks (email, fmobile). The statistics of datasets are shown in Table 2.

• Reddit is a Reddit post network with each node representing a post, and each link indicating that the connected two posts are commonly commented by at least three users. We adopt the same setup as [Hamilton et al., 2017] for the node attributes, and use the user-averaged distributions of comments in different communities as link attributes.
• Dblp is a co-author network constructed with papers from 2013 to 2017 in eight artificial intelligence conferences. We use the tf-idf vectors of paper titles as node attributes. The links are categorized under author perspective, i.e. the one-hot embeddings of the common authors are used as link attributes. The node and link attributes are reduced to 200 dimensions using PCA.
• Email and fmobile are two temporal networks constructed with user contacts in email and mobile-phone services. The contacts of exact times are discretized into

time-slices and used as link attributes. As there is no available node features in the datasets, we use node embeddings with dim=128 obtained from transductiveLINE [2015] as the pre-trained node features in all convolution-based models.

Baselines. We compare the performance of LASE with baselines including raw features, LINE [2015], DeepWalk [2014], GCN [2016] and GraphSAGE [2017]. For LINE and DeepWalk, we adopt an online-style training strategy for the test / validation set introduced in [Hamilton et al., 2017] 9 , and a one-layer softmax-activated neural classifier is trained for all models. To demonstrate the ability of LASE in leveraging link attributes through the amplifiers, we also test the performance of a LASE variant, LASE-concat, implemented by na¨ıvely concatenating link attributes to node attributes.

5.2 Node-wise Classification

We implement node-wise classification respectively over the four datasets mentioned above by predicting the community (reddit, email and fmobile) or the conference (dblp) that a node belongs to. In all datasets, 65% nodes are used as the training set, 15% as the validation set and the rest as the test set. The nodes in the training set with no neighbors are abandoned. The micro-averaged f1 scores on the test set are shown in Table 3.

As one of the most distinguished strengths of GCNs is to aggregate neighborhood features, convolutional-based models including GCN, GraphSAGE and LASE show significant advantages to proximity-based models on datasets with node attributes. Through leveraging link attributes, LASE outperforms other GCNs. Moreover, with LASE-RW and LASE-SAGE outperforming the na¨ıve implementation LASE-concat, the effect of the amplifier module can be corroborated. Although there is no original features in two temporal networks, LASE still outperforms pre-trained features by exploring edge attributes, while GCN and GraphSAGE do not capture these additional information and struggles in over-fitting the proximity-based features.

Figure 4 a) demonstrate the accuracies of LASE-SAGE using contaminated link attributes of different signal-to-noise ratios (SNRs). That is, we add normal-distributed noises of different standard deviations to the original link attributes according to given SNRs, and separately train LASE-SAGE

9 As there is no implementation of online-LINE and [Qiu et al., 2018] proves that LINE is theoretically equivalent with DeepWalk with walk length=1, we use the implementation of onlineDeepWalk in [Hamilton et al., 2017] instead. N walks is respectively added to compensate the reduction in node contexts.

models under identical model settings. The SNR is defined as

where A(·) denotes the standard deviation of the inputs. As SNR increases, a significant trend of decrease in accuracy can be observed. This corroborates the informativeness of link attributes in the LASE architecture.

5.3 Comparison of Sampling Strategies

We look into the training processes of different neighborhood sampling strategies introduced in Section 4, namely uniform, gate and minimal variance (min var) sampling. We separately train models with corresponding sampling strategy on email, and present the variations of accuracies on the validation set against training epochs in Figure 4 b). While the convergence speeds appear analogous, min var sampling consistently attains better convergence performance compared with uniform and gate sampling. The reason that gate sampling does not show a significant advantage over uniform sampling may be that the norms of transformed neighbor features (g(l) (v|u)) varies greatly in the neighborhood.

Figure 4 c) shows the tradeoff between performance and efficiency made through different calculation intervals of the sampling distribution (under min var setup). As the interval k increases, the performance slightly drops. Calculating the probabilities batch-wise attains a significant elevation in the performance, while the computation cost can be unacceptably high on larger datasets. Additionally, when k becomes large enough, increasing k does not significantly influence the training performance.

6 Conclusions and FutureWork

In this paper, we propose LASE as an extension of graph convolutional networks, which leverages more information from graph links than existing GCNs by incorporating the link attributes. The contribution of LASE lies in three folds: i) LASE provides a ubiquitous solution to a wider class of graph data by incorporating link attributes; ii) LASE outperforms strong baselines and na¨ıve concatenating implementations by adequately leveraging the information in the link attributes; iii) LASE adopt a more explainable approach in determining the neural architecture and thus enjoys better explainability.

For future work, we are looking for better sampling solutions for LASE, as although stressed with calculation intervals, current sampling setup seems to be rather clumsy when the graph becomes massively large. We are also looking for other possible approaches, hopefully with better performance, to incorporating link attributes. Besides, as LASE is an universal solution to all graph-structured data, an intriguing direction may be designing domain- or task-specific architectures based on LASE to attain better performances, such as more elegant adaptations to dynamic networks.