Node-wise Localization of Graph Neural Networks

1 Introduction

Graphs are powerful data structures to model various entities (i.e., nodes) and their interactions (i.e., edges) simultaneously. To learn the representations of nodes on a graph, graph neural networks (GNNs) [Wu et al., 2020] have been proposed as a promising solution. Generally, state-of-theart GNNs [Kipf and Welling, 2017; Hamilton et al., 2017; Veliˇckovi´c et al., 2018] learn the representation of each node by recursively transferring and aggregating information from its receptive field, which is often defined as its set of neighboring nodes. Consider a toy citation graph in Fig. 1(a), consisting of papers in three areas: biology (bio), bioinformatbioinf ) and computer science (cs). To derive the representation of a node, say v1, GNNs aggregate keyword features from not only v1 itself, but also its neighbors, namely v2, v4, v5 and v6, as illustrated in Fig. 1(b). Such neighborhood aggregation can be performed recursively for the neighbors as well in more layers, to fully exploit the graph structures. To extract useful representations from the neighbors, GNNs aim to learn the model parameters formulated as a sequence of weight matricesW1 ,W2 , . . . ,Wl in each layer.

However, the implicit assumption of a global weight matrix (in each layer) for the entire graph is often too strict. Nodes do not distribute uniformly over the graph, and are associated with different local contexts. For instance, in Fig. 1(c), node v1 is associated with a bio context, v2 with a bioinf context and v3 with a cs context. Different local contexts are characterized by different keyword features, such as "gene" and "cell" in bio, "gene" and "svm" in bioinf, as well as "svm" and "vc-dim" in cs. Thus, a graph-level global weight matrix is inherently inadequate to express the varying importance of features at different localities. More specifically, a global weight matrix can be overly diffuse, for different nodes often have distinct optimal weight matrices, which tend to pull the model in many opposing directions. This may result in a biased model that centers its mass around the most frequent patterns while leaving others not well covered. A natural question follows: Can we allow each node to be parameterized by its own weight matrix? Unfortunately, this is likely to cause severe overfitting to local noises and suffer from significantly higher training cost.

In this work, to adapt to the local context of each node without overfitting, we localize the model for each node from a shared global model. As illustrated in Fig. 1(c), a localized weight matrixWlvi for each node vi can be derived from both the global weight Wl and the local context of vi. That is, Wlvi is a function of the global information and the local context. Globally, all nodes depend on a common underlying model to encode the general patterns at the graph level. Locally, each node leverages its local context to personalize the common model into its unique localized weight at the node level. It is also useful to incorporate a finer-grained localization at the edge level, where information received through each edge of the target node can be further adjusted. The proposed localization, which we call node-wise localized GNN (LGNN), aims to strike a balance between the global and local aspects of the graph. Moreover, LGNN is agnostic of the underlying global model, meaning that it is able to localize any GNN that follows the paradigm of recursive neighborhood aggregation, and subsumes various conventional GNNs as its limiting cases.

In summary, our main contributions are three-fold. (1) We identify the need to adapt to the local context of each node in GNNs. (2) We propose a node-wise localization of GNNs to capture both global and local information on the graph, and further discuss its connection to other works. (3) We conduct extensive experiments on four benchmark datasets and show that LGNN consistently outperforms prior art.

2 Proposed Approach

In this section, we introduce the proposed approach LGNN, and discuss its connection to other works.

2.1 General Formulation of Localization

We start with an abstract definition of localizing a global model to fit local contexts. Specifically, the localized model of an instance v is a function of both the global model and the local context. Let Θ denote the global model, and Cv the local context of v. Then the localized model for v is

where f can be any function such as a neural network. While we focus on graph data where v is a node, the general formulation is also pertinent to other kinds of data when there are varying, non-uniform contexts associated with instances. In particular, On a graph G = (V, E) with a set of nodes V and edges E, the local context of a node v can be materialized as the neighbors of v, in addition to v itself. That is,

2.2 Localization of GNNs

A typical GNN consists of multiple layers of recursive neighborhood aggregation. In the l-th layer, each node v receives and aggregates information from its neighbors to derive its hidden representation hlv ∈ Rdl , with dl being the dimension of the l-the layer representation. Note that the initial representation h0v is simply the input feature vector of v. The aggregation is performed on the local context of v which also covers the neighbors of v, as follows.

where Wl ∈ Rdl×dl-1 is a weight matrix in the l-th layer, σ(·) is an activation function, and AGGR(·) is an aggregation function. Different GNNs differ in the choice of the aggregation function. For instance, GCN [Kipf and Welling, 2017] uses an aggregator roughly equivalent to mean pooling [Hamilton et al., 2017], GAT [Veliˇckovi´c et al., 2018] uses an attention-weighted mean aggregator, and GIN [Xu et al., 2019] uses a multi-layer perceptron (MLP).

Node-level localization. In the above setup, we have a global model Wl for all nodes in the l-th layer. At the node level, the global model is localized to adapt to the local context of each node. Specifically, we modulate the global weight Wl by a node-specific transformation through scaling and shifting. The localized weight matrix of node v is given by

where alv , blv ∈ Rdl-1 are v-specific vectors for scaling and shifting, respectively. Here the notation [(x)×n] represents a matrix of n columns all of which are identical to the vector x, and ⊙ denotes element-wise multiplication. We essentially transform each row of the global matrix Wl by alv and blv in an element-wise manner, to generate the localized weight Wlv , so that various importance levels are assigned to each feature dimension of the node embedding hl-1 u .

It is important to recognize that the node-specific transformation should not be directly learned, for two reasons. First, directly learning them significantly increases the number of model parameters especially in the presence of a large number of nodes, causing overfitting. Second, node-wise localization is a function of both the global model and the local context as formulated in Eq. (1), in order to better capture the local information surrounding each node. Thus, for node v, we propose to generate the v-specific transformation in the l-th layer from its local contextual information clv . A straightforward recipe for clv is to pool the (l - 1)-th layer representations of the nodes in the local context Cv:

in which we adopt the mean pooling although other forms of pooling can be substituted for it. Given the local contextual information clv ∈ Rdl-1 , we further utilize a dense layer, shared by all nodes, to generate the v-specific transformation as follows.

where Mla ,Mlb ∈ Rdl-1×dl-1 are learnable parameters shared by all nodes, and 1 is a vector of ones to ensure that the scaling factors are centered around one. Note that if the dimension dl-1 is too large, such as that of the highdimensional raw features handled in the first layer of a GNN, we could employ two dense layers and set the first one with a smaller number of neurons.

Edge-level localization. The node-level localization of the global weight matrix is coarse-grained, as the same localized weight is applied on all neighbors of the target node. That is, the target node receives information through each of its edges uniformly. To enable a finer-grained localization, we further modulate how information propagates at the edge level.

Consider a node v with edges {〈u, v〉 : ∀u ∈ Cv}. In the l-th layer of the GNN, let clu,v denote the local contextual information of the edge 〈u, v〉, which is given by its two ends. Specifically, we concatenate the (l - 1)-th layer representations of nodes u and v, as follows.

To implement the edge-level localization, we similarly adopt an edge-specific transformation through scaling and shifting. Specifically, to derive the l-th layer representation of v, we scale and shift the information from each edge 〈u, v〉 during aggregation, by rewriting Eq. (3) as follows.

where alu,v , blu,v ∈ Rdl are edge 〈u, v〉-specific vectors for scaling and shifting, respectively. Like the node-specific transformation, we generate the edge-specific transformation with a dense layer given by

where Nla ,Nlb ∈ Rdl×2dl-1 are learnable parameters shared by all edges.

2.3 Semi-supervised Node Classification

In the benchmark task of semi-supervised node classification, each node belongs to one of the pre-defined classes {1, 2, . . . ,K}. However, we only know the class labels of a subset of nodes VY ⊂ V , called the labeled nodes. The goal is to predict the class labels of the remaining nodes. Following standard practice [Kipf and Welling, 2017], for K-way classification we set the dimension of the output layer to K, and apply a softmax function to the representation of each node. That is, given a total of ℓ layers,

For a labeled node v ∈ VY , let Yv,k ∈ {0, 1} be 1 if and only if node v belongs to class k. The overall loss is then formulated using a cross-entropy loss with regularization as

where ΘG = {Wl : l ≤ ℓ} contains the parameters of the global model, ΘL = {Mla ,Mlb ,Nla ,Nlb : l ≤ ℓ} contains the parameters of localization, and A, B are sets respectively containing the transformation vectors for scaling (alv 's and alu,v 's) and shifting (blv 's and blu,v 's). Note that the norms ‖ · ‖22 are computed over all tensor elements in the sets. While A and B are not learnable, they are functions of the learnable ΘL. We explicitly constrain them to favor small local changes, i.e., close-to-one scaling and close-to-zero shifting. Moreover, as A and B grow with the size of the graph, their norms are further normalized by the total number of tensor elements in them, denoted by |A| and |B|, respectively. λG, λL and λ are non-negative hyperparameters.

2.4 Connections to OtherWorks

Next, we discuss how LGNN is related to other lines of work in GNNs, network embedding and hypernetworks.

Relationshipwith existingGNNs. The proposed LGNN is able to localize any GNN model that follows the scheme of recursive neighborhood aggregation in Eq. (3). In particular, LGNN is a generalized GNN that subsumes, as special limiting cases, several conventional GNNs by adopting an appropriate aggregation function and regularization.

Specifically, as λ → ∞ in Eq. (11), the scaling and shifting would approach 1's and 0's in the limiting case, respectively. This is equivalent to removing all node-wise localization at both node and edge levels, where all nodes assume a global model. Thus, LGNN would be asymptotically equivalent to GCN [Kipf and Welling, 2017] and GIN [Xu et al., 2019], when using a graph convolution aggregator (roughly equivalent to the mean pooling) and an MLP aggregator on the sumpooled representations, respectively. Furthermore, with an appropriate regularization, LGNN can be asymptotically reduced to GAT 1 [Veliˇckovi´c et al., 2018]. Consider the vectors for scaling in A, which can be split into the node-specific AV (containing alv 's) and edge-specific AE (containing alu,v 's).

1 Here we only discuss GAT with one attention head.

For AV , we maintain the same regularization ‖AV - 1‖22 ; for AE, we adopt the regularization ‖AE - α‖22 such that α contains the corresponding attention coefficients on all edges. That is,

where αlu,v ∈ R is the attention coefficient on edge 〈u, v〉. Coupled with a mean aggregator, we obtain GAT as the limiting case when λ → ∞. Alternatively, we can also maintain the same regularization for both node- and edge-specific transformations, and adopt a weighted mean aggregator in accordance to the attention coefficients. Note that in GAT the attention coefficient on each edge is a scalar, whereas in our edge-level localization, the edge-specific scaling is represented by a vector, which is able to flexibly vary the contribution from different dimensions of the information received through the edges.

Relationship with network embedding. Network embedding [Cai et al., 2018] is a popular alternative to GNNs to learn node representations on a graph. In these methods, each node is directly encoded with a learnable parameter vector, which is taken as the representation of the node. In contrast, in GNNs, the representations of the nodes are derived from a shared learnable model. Thus, network embedding can be viewed as a set of individual local models that are loosely coupled by local graph structures, whereas GNNs capture a more global view of the structures. In contrast, the proposed LGNN achieves a balance between the local and global views, to allow localized variations grounded on a global model.

Relationship with hypernetworks. Our localization strategy can be deemed a form of hypernetworks [Ha et al., 2017], which use a secondary neural network to generate weights for the target network. In our case, we employ dense layers as a secondary network to generate the vectors for scaling and shifting, which are leveraged to ultimately generate the localized weights for the target GNN. Moreover, our approach boils down to the feature-wise modulation of information received from the conditioning local context (i.e., neighboring nodes) at both node and edge levels, which is inspired by the feature-wise modulation of neural activations in FiLMs [Perez et al., 2018; Birnbaum et al., 2019].

On graphs, GNN-FiLM [Brockschmidt, 2020] also uses a form of FiLM on GNNs. However, there are several fundamental differences between GNN-FiLM and our LGNN. First, in terms of problem and motivation, GNN-FiLM aims to model edge labels on relational networks for message passing. In contrast, our LGNN aims to model local contexts for node-wise localization, and works on general graphs. Second, in terms of model, GNN-FiLM models relationspecific transformations conditioned only on a node's selfinformation, which does not sufficiently reflect the full local context of the node as LGNN is conditioned on. Furthermore, when there is no edge labels, GNN-FiLM reduces to a "uniform edge" model. In LGNN, we still have both node and edge level modulation to achieve localization. Third, in terms of empirical performance, as discussed therein [Brockschmidt, 2020], GNN-FiLM only achieves at best comparable performance to existing GNNs on citation networks (such as Cora and Citeseer) where there is no edge label. Our own experiments also have reproduced similar results in the next section.

3 Experiments

In this section, we evaluate and analyze the empirical performance of our proposed approach LGNN.

3.1 Experimental Setup 2

Datasets. We utilize four benchmark datasets. They include two academic citation networks, namely Cora and Citeseer [Yang et al., 2016], in which nodes correspond to papers and edges correspond to citations between papers. The input node features are bag-of-word vectors, indicating the presence of each keyword. A similar citation network for Wikipedia articles called Chameleon [Pei et al., 2020] is also used. Finally, we use an e-commerce co-purchasing network called Amazon [Hou et al., 2020], in which the nodes correspond to computer products and the edges correspond to copurchasing relationships between products. The input node feature vectors are constructed from product images. The statistics of the datasets are summarized in Table 1.

Baselines and our approach. We compare against three categories of baselines. (1) Embedding models: DeepWalk [Perozzi et al., 2014] and Planetoid [Yang et al., 2016]. Both employ a direct embedding lookup and adopt random walks to sample node pairs. However, DeepWalk is unsupervised such that node classification is performed as a downstream task on the learned representations, whereas Planetoid is an end-to-end model that jointly learns the representations and the classifier. (2) GNN models: GCN [Kipf and Welling, 2017], GAT [Veliˇckovi´c et al., 2018] and GIN [Xu et al., 2019]. (3) GNN-FiLM: The original GNN-FiLM works with a GCN-style model, which we call GCN-FiLM. We further extend it to two other GNN architectures GAT and GIN, resulting in two more versions GAT-FiLM and GIN-FiLM.

On the other hand, our approach LGNN can also be implemented on different GNN architectures. Specifically, we employ GCN, GAT and GIN as the global model, and obtain localized versions LGCN, LGAT and LGIN, respectively.

Main settings. For DeepWalk, we sample 10 randomwalks per node with walk length 100 and windows size 5, and set the embedding dimension to 128. We further train a logistic regression as the downstream classifier. For Planetoid, we set the path length to 10, window size to 3 and the embedding dimension to 50. We select the best results from their transductive and inductive versions for report. For all GNNbased approaches, we adopt two aggregation layers, noting that deeper layers often bring in noises from distant nodes [Pei et al., 2020] and cause "over-smoothing" such that all nodes obtain very similar representations [Li et al., 2018; Xu et al., 2018]. The dimension of the hidden layer defaults to 8, while we also present results using larger dimensions. The regularization of GNN parameters is set to λG = 0.0005. These settings are chosen via empirical validation, and are largely consistent with the literature [Perozzi et al., 2014; Kipf and Welling, 2017; Veliˇckovi´c et al., 2018]. For our models, the additional regularizations are set to λL = λ = 1 (except for λ = 0.1 in LGAT).

2 Additional implementation details and experimental settings are included in Sections A and B of the supplemental material.

Training and testing. For all datasets, we follow the standard split in the literature [Yang et al., 2016; Kipf and Welling, 2017; Veliˇckovi´c et al., 2018], which uses 20 labeled nodes per class for training, 500 nodes for validation and 1000 nodes for testing. We repeat 10 runs for each experiment, and report the average accuracy and micro-F score.

3.2 Performance Comparison

Table 2 shows the comparison of the classification performance on the four datasets. For each GNN architecture, we also include additional models by increasing the dimension of its hidden layer. For instance, GCN-64 denotes that the hidden layer of GCN has 64 neurons. The results reveal a few important observations.

Firstly, we observe that LGNN consistently achieves significant performance boosts w.r.t. three state-of-the-art GNNs on four datasets. This suggests that, our localization approach is agnostic of the particular GNN architecture of the global model, and can be used universally on different GNNs. Furthermore, LGNNs also outperform GNN-FiLMs, as GNNFiLMs only achieve at best comparable performance with the base GNNs. A potential reason is that GNN-FiLM is only conditioned on the target node's self-information to modulate message passing for different edge labels, which may not be useful on graphs without edge labels. In contrast, LGNN is conditioned on the full local context of the target node to achieve node-wise localization that could be useful to the classification of nodes residing across different localities on the graph. Secondly, GAT-based models generally attain better performance than GCN- and GIN-based models, and the performance gain in LGAT w.r.t. GAT is smaller. This is not surprising as the attention coefficients on the edges can be understood as a limited form of localization to differentiate the weight of different neighbors. Thirdly, the results imply that increasing the number of parameters alone cannot achieve the effect of localization. It may be argued that more parameters lead to higher model capacity, which can potentially assign some space to encode the local aspects. However, when the parameters are still shared globally, there is no explicit node-wise constraint and thus the model will still try to find a middle ground. Nevertheless, for a fair comparison, we use more parameters on each GNN baseline to match or exceed the number of parameters on the corresponding LGNN, as listed in Table 2 3 . As expected, more parameters only result in marginal improvements to the baselines. Thus, the efficacy of LGNN is derived from our localization strategy rather than just more parameters. Fourthly, LGNN is robust and stable given their relatively small standard deviations in many cases. We hypothesize that, in conventional GNNs, a bad initialization would risk a suboptimal global model shared by all nodes without recourse. In contrast, node-wise localization offers an opportunity to adjust the suboptimal model for some nodes, and is thus less susceptible to the initialization.

3 Details of the calculation are included in Section C of the supplemental material.

It has also been discussed that in GNNs overfitting to the validation set is an issue [Shchur et al., 2018], and thus models with more parameters tend to perform better given a larger validation set. Therefore, we further compare different methods using a smaller validation set of only 100 nodes 4 . Our proposed LGNN still outperforms all the baselines across the four datasets, demonstrating its power and stability.

3.3 Further Model Analyses

Due to space constraint, we only present an ablation study here 5 . In the ablation study, we investigate the effectiveness of the node- and edge-level localization modules in LGNN. To validate the contribution of each module, we compare the accuracy of four variants in Fig. 2: (1) global only without any localization; (2) node-level localization only; (3) edgelevel localization only; and (4) the full model with both localization modules. We observe that utilizing only one module, whether at the node or edge level, consistently outperform the global model. Between the two modules, the node-level localization tends to perform better. Nevertheless, modeling both jointly results in the best performance, which implies that both modules are effective and possess complementary localization power.

4 RelatedWork

Graph representation learning has received significant attention in recent years. Earlier network embedding approaches [Perozzi et al., 2014; Tang et al., 2015; Grover and Leskovec, 2016] employ a direct embedding lookup for node representations, which are often coupled via local structures such as skip-grams. To better capture global graph structures, GNNs [Kipf and Welling, 2017; Hamilton et al., 2017; Veliˇckovi´c et al., 2018; Xu et al., 2019] open up promising opportunities. They generally follow a paradigm of recursive neighborhood aggregation, in which each node receives information from its neighbors on the graph. More complex structural information is also exploited by recent variants [Zhang et al., 2020; Pei et al., 2020; Chen et al., 2020], but none of them deals with the node-wise localization.

4 These results are in Section D of the supplemental material.

5 More analyses on the complexity and effect of regularization, as well as model visualization, can be found in Sections E, F and G of the supplemental material.

While our approach can be deemed a form of hypernetworks [Ha et al., 2017; Perez et al., 2018] as discussed in Sect. 2.4, several different forms of local models have been explored in related problems. In manifold learning [Yu et al., 2009; Ladicky and Torr, 2011], local codings are used to approximate any point on the manifold as a linear combination of its surrounding anchor points. In low-rank matrix approximation [Lee et al., 2013], multiple low-rank approximations are constructed for different regions of the matrix before aggregation. These methods are tightly coupled with their problems, and cannot be easily extended to localize GNNs. Some meta-learning frameworks [Vinyals et al., 2016; Snell et al., 2017; Finn et al., 2017] can also be viewed as adapting to local contexts. Given a set of training tasks, meta-learning aims to learn a prior that can be adapted to new unseen tasks, often for addressing few-shot learning problems. In particular, existing meta-learning models on graphs are mostly designed for few-shot node classification [Zhou et al., 2019; Yao et al., 2020; Liu et al., 2021] or regression [Liu et al., 2020]. Such few-shot settings are fundamentally different from our localization objective, in which all nodes are seen during training and we leverage the local contexts of the nodes in order to enhance their representations.

5 Conclusions

In this work, we identified the need to localize GNNs for different nodes that reside in non-uniform local contexts across the graph. This motivated us to propose a node-wise localization approach, named LGNN, in order to adapt to the locality of each node. On one hand, we encode graph-level general patterns using a global weight matrix. On the other hand, we modulate the global model to generate localized weights specific to each node, and further perform an edge-level modulation to enable finer-grained localization. Thus, the proposed LGNN can capture both local and global aspects of the graph well. Finally, our extensive experiments demonstrate that LGNN significantly outperforms state-of-the-art GNNs.

Acknowledgments

This research is supported by the Agency for Science, Technology and Research (A*STAR) under its AME Programmatic Funds (Grant No. A20H6b0151).