Graph Deformer Network

1 Introduction

Graph is a flexible and universal data structure consisting of a set of nodes and edges, where nodes can represent any kind of object and edges indicate some relationship between a pair of nodes. Research on graphs is not only important in theory, but also beneficial to wide backgrounds of applications. Recently, advanced by the powerful representation capability of convolutional neural networks (CNNs) on gridshaped data, the study of convolution on graphs is drawing increasing attention in the fields of artificial intelligence and data mining. So far, many graph convolution methods [Kipf and Welling, 2017; Hamilton et al., 2017; Jiang et al., 2019; Gao and Ji, 2019; Zhao et al., 2019; Gao et al., 2020; Xu et al., 2020; Zhang, 2020; Hong et al., 2021] have been proposed, and raise a promising direction.

∗Contact Author

The main challenge is the irregularity and complexity of graph topology, causing difficulty in constructing convolutional kernels. Most existing works take the plain summation or average aggregation scheme, and share a kernel for all nodes as shown in Fig. 1(a). However, there exist two nonignorable weaknesses for them: i) losing the structure information of nodes in the local neighborhood, and ii) causing signal entanglements of nodes due to collapsing to one central node. Thereby, an accompanying problem is that the discriminative ability of node representation would be impaired, and further non-isomorphic graphs/subgraphs may produce the same responses.

Contrastively, in the standard convolutional kernel used for images, it is important to encode the variations of local receptive fields. For example, a 3 × 3 kernel on images can well encode local variations of 3 × 3 patches. An important reason is that the kernel is anisotropic to spacial positions, where each pixel position is assigned to a different mapping. However, due to the irregularity of graphs, defining and operating such an anisotropic kernel on graphs are intractable. To deal with this problem, Niepert et al. [Niepert et al., 2016] attempted to sort and prune neighboring nodes, and then run different kernels on the ranked size-fixed nodes. However, this deterministic method is sensitive to node ranking and more prone to being affected by graph noises. Furthermore, some graph convolution methods [Veliˇckovi´c et al., 2018; Wang et al., 2019] introduce an attention mechanism to learn the importance of nodes. Such methods emphasize mining those significant structures/features rather than designing anisotropic convolution kernels, so they cannot well represent local variations of structures in essence.

In this work, we propose a novel yet effective graph deformer network (GDN) to implement anisotropic convolutional filtering on graphs as shown in Fig. 1(b). Inspired by image-based convolution, we deform local neighborhoods of different sizes into a virtual coordinate space, implicitly spanned by several anchor nodes, where each space granularity corresponds to one anchor node. In order to perform space transformation, we define the correlations between neighbors and anchor nodes, and project neighboring nodes into the regular anchor space. Thereby, irregular neighborhoods are deformed into the anchor-coordinated space. Then, the imagelike anisotropic convolution kernels can be imposed on the anchor-coordinated plane, and local variations of neighborhoods can be perceived effectively. Due to the importance of anchors, we also deform anchor nodes with adaptive parameters to match the feature space of nodes. As anisotropic convolution kernels are endowed with the fine-grained encoding ability, our method can better perceive subtle variations of local neighborhood regions as well as reduce signal confusion. We also show its connection to previous work, and theoretically analyze the stronger expressive power and the satisfactory property of the isomorphism test. Extensive experiments on graph/node classification further demonstrate the effectiveness of the proposed GDN.

2 Our Approach

In this section, we elaborate on the proposed graph deformer method. Below we first give an abstract formulation for our method and then elaborate on the details.

Denote G = (V, E) as an undirected graph , where V represents a set of nodes with |V| = n and E is a set of edges with |E| = e. According to the link relations in E, the corresponding adjacency matrix can be defined as A ∈ Rn×n . And X ∈ Rn×d is the feature matrix. To state conveniently, we use Xi· or xi to denote the feature of the i-th node. Besides, for a node vi, the first-order neighborhood consists of nodes directly connected to vi, which is denoted as N 1 vi = {vj|(vj, vi) ∈ E}. Accordingly, we can define sorder neighborhood N s vi as the set of s-hop reachable nodes.

2.1 A Basic Formulation

Given a reference node vr in graph G, we need to learn its representation based on the node itself as well as its contextual neighborhood Nvr . However, the irregularity causes difficulty in designing anisotropic spatial convolution. To address this problem, we introduce anchor nodes to deform the neighborhood. All neighboring nodes are calibrated into a pseudo space spanned by anchors. We denote the set of anchor nodes by V = {v0, v1, ..., vm-1}. The convolution on Nvr is formulated as:

where

• v·, x·: an anchor node and a pseudo coordinate vector (a.k.a. feature vector). Please see Section 2.2 for anchor generation.
• D: the deformer function. It transforms node vt into a virtual coordinate space spanned by anchors. Θ is the deformer parameter to be learned. Please see Section 2.3 for details.
• F(r) ∈ Rm×d : the deformed multi-granularity feature from the neighborhood of node vr. Each granularity F(r) i corresponds to an anchor node vi.
• C,K: the anisotropic convolution operation on anchor space and convolution kernel. G ∗ f represents filter f acting on graph G. The relationship between anchor nodes can be built by some metrics such as Cosine distance, and anchor nodes may be formatted as a pseudo 2-D grid just like the patch in images. Please see the details in Section 2.3.

2.2 Anchor Generation

Anchor nodes are crucial to the graph convolution process because neighborhood regions are unitedly calibrated with them. Rigid anchors will not adapt to the variations of the feature space during convolution learning. Thus we choose to optimize anchor nodes as one part of the entire network learning. In the beginning, we cluster nodes randomly sampled from the graph as initial anchors. When enough anchors cover the space of neighborhood nodes, the anchors can be endowed with a strong expressive ability to encode neighborhoods like a code dictionary. Formally, we use the K-means clustering to generate initial anchors,

where Vsampling is the sampled node set, in which each node is randomly sampled from the graph, V = {(vk, xk)}|m-1 k=0 is the initial anchor set generated by clustering, in which vk represents k-th anchor node and xk represents its feature vector, m is the number of anchor nodes. Note when given anchor nodes, the response of our method will be invariant to permuted nodes of one graph during the training as well as testing stage. The clustering algorithm might affect the final anchors due to random sampling for initialization, but it cannot affect the property of permutation invariance, which just like random initialization on the network parameters.

Due to the sparsity of graphs, in practice, several anchors are sufficient to encode each neighborhood. To better collaborate with node/feature variations during graph convolution learning, we transform the initial anchors into a proper space by parameterizing them:

where WA, bA are the learnable parameters, and ReLU is the classic activation function. Besides, other flexible multi-layer networks may be selected to learn deformable anchors.

2.3 Deformer Convolution

Space Transformation

Now we define the deformer function D in Eqn. (2), transforming neighbor nodes to the anchor space. For each node vj ∈ Nvr (nr = |Nvr |), we derive the anchor-related feature (also query feature) and value feature vectors as

where WQ,WU are the learnable weight matrices, and bQ, bU are the biases. The query feature qj indicates how to transform vj to the anchor space by interacting with anchors, and the value vector uj is the transformable component to the anchor space.

For the neighborhood Nvr of node vr, the correlation to anchors defines a set of weights α = {α0,0, · · · , α0,m-1, · · · , αnr-1,0, · · · , αnr-1,m-1}, which measures the scores of all nodes within the neighborhood projected onto the directions of anchor nodes. Formally,

where 〈·, ·〉 denotes the inner production, 1 √d is the scaling factor as [Vaswani et al., 2017], then normalization is done by softmax function. αj,k may be viewed as the attention score of the node vj w.r.t. the anchor vk. After obtaining the attention score, the irregular neighborhood can be transformed into the anchor-coordinated space,

The deformed components are accumulated on each anchor, and form the final deformed features. Thus, any neighborhood with different sizes can be deformed into the virtual normalized space coordinated by anchors. In experiments, for simplicity, the query feature and value feature are shared with the same parameters in Eqns. (5) and (6).

Anisotropic Convolution in the Anchor Space

Afterward, the s-hop neighborhood of node vr is deformed into the size-fixed anchor space, i.e., N s vr → {˜u0, ˜u1, · · · , ˜um-1}. The anisotropic graph convolution can be implemented by imposing different mapping on each anchor as

where ˜x(s) r ∈ Rd′ , the matrix Ki is a d × d′ weight imposed on the features w.r.t. an anchor, and b is the bias vector.

In the convolution process, different filter weights are imposed on different features of anchor nodes, which is an anisotropic filtering operation. In contrast to the traditional aggregation method, the deformer convolution has two aspects of advantages: i) well preserving structure information and reducing signal entanglement; ii) transforming differentsized neighborhoods into the size-fixed anchor space to well advocate anisotropic convolution like the standard convolution on images.

Multi-Scale Extension

Intuitively, the first-order neighborhood is necessary to be used for node aggregation, because it indicates that two nodes linked by an edge are always similar. However, real-world graphs are often so sparse, and there exist many nodes that are similar to each other but not linked by direct edges. The first-order neighborhood alone is not sufficient for extracting useful features and preserving the structural information. It is natural to incorporate higher-order proximity to capture more information. Generally, second-order information is sufficient as most works [Abu-El-Haija et al., 2019; Wang et al., 2016; Tang et al., 2015]. Higher-order information can also be considered, but the computational complexity will increase. It can be understood as a trade-off of expressive ability and computational complexity. In this paper, we consider both first-order and second-order neighborhoods. Specifically, we deform both first-order and secondorder neighborhoods into feature space represented by anchor nodes, and convolve over them respectively. Then the learned different neighborhood representations and the original node feature are concatenated as the final filtering response,

where ˜xr denotes the convolution response on the s-order neighborhood N s vr of node vr. Further, we can stack multiply layers to extract robust features on larger receptive fields.

2.4 Graph Coarsening

Similar to the pooling in standard CNN, the coarsening on graphs could enlarge the receptive field of nodes as well as reduce the computation cost. Below we simply introduce graph coarsening used here.

Graph classification. We employ the graph cut used in [Jiang et al., 2019] to partition an entire graph into several subgraphs. During graph coarsening, a binary cluster matrix Z ∈ Rn×c is obtained, where only one element in each row is non-zero, i.e., Zic = 1 when the vertex vi falls into the cluster c. Then the adjacency matrix and feature matrix of the input graph are transformed into

where ⊗ represents a max operation. The output can be used as the input of the next convolutional layer. Then the graph convolution and coarsening can be alternatingly stacked into a deep network.

Node classification. We do not need to remove nodes for node classification task. The pooling is node-wise diffusion on a local receptive field, and can be performed over multiscale neighborhoods. The pooling over S scale neighborhoods w.r.t. the reference node vr is

where the pooling P is usually defined as "max" or "mean". In practice, their performance has little difference, so we choose the mean operation in experiments.

2.5 Neural Network Training

For graph classification, we adopt the cross-entropy as cost function to learn graph representation. However, in the scenario of semi-supervised node classification, a main limitation is that a small portion of nodes is annotated as the training set. Our aim is to use labeled nodes as well as graph structure to train a model with a good generalization ability. A straightforward way is to add a regularization term to avoid overfitting. To this end, we employ a global consistency constraint through positive pointwise mutual information as used in [Zhuang and Ma, 2018] to regularize the loss function. Finally, backpropagation algorithm is used to compute the gradient and the stochastic gradient descent algorithm updates neural network parameters.

2.6 Computational Complexity

For the computational complexity, we analyze the main module of graph convolution. In one-layer convolution, GCN [Kipf and Welling, 2017] is about O(edS + ndd′S), where n, e are the numbers of nodes and edges, S is the scale of the neighborhood, and d, d′ are the dimensions of the input/hidden layers. For our GDN model, the computational complexity is mainly from two parts, i.e., "Space Transformation" and "Convolution in Anchor Space", which are about O(emd2S) and O(nmdd′S), respectively, where m is the number of anchor nodes. Thus, the total computational complexity is O(emd2S + nmdd′S), which is linearly proportional to GCN with the factor m when d and d′ have the same order number.

3 Theoretical Analysis

We present a theoretical analysis about the expressive power of several aggregation methods including the mean, sum, and graph deformer operation. Inspired by [Xu et al., 2019], we evaluate them by verifying whether graphs are isomorphic. Then, we give the following propositions.

Proposition 1 There exists a set of network parameters that make two non-isomorphic graphs G1 and G2 can be distinguished by graph deformer process, but cannot be distinguished by mean/sum aggregation.

Proposition 2 The proposed anisotropic graph deformer convolution can be as powerful as the Weisfeiler-Lehman (WL) graph isomorphism test.

The proofs of the above two propositions can be found in the supplementary material 1 . We can conclude that the expressive power of the proposed graph deformer network is provably stronger than mean/sum aggregation, which can accomplish an injective mapping as powerful as the WeisfeilerLehman (WL) graph isomorphism test.

1 https://github.com/wtzhao1631/gdn

4 Experiments

In this section, we carry out extensive experiments to assess the proposed GDN model on both graph and node classification tasks. For node classification, three citation graphs are used: Cora, Citeseer, and Pubmed. We adopt the data preprocessed in the work [Yang et al., 2016], and follow its data partitioning rules. For graph classification, we adopt eight datasets [Jiang et al., 2019] to assess our GDN method: MUTAG, PTC, NCI1, PROTEINS, ENZYMES, IMDB-BINARY, IMDB-MULTI, and REDDIT-MULTI-12K.

4.1 Experimental Setups

Graph classification. A three-layer GDNmodel is applied for the learning of overall graphs. Each convolutional layer is followed by a pooling/coarsening layer with a downsampling rate of 0.5. The channels of the three convolutional layers are set to {64, 128, 256}, respectively. Finally, a fullyconnected layer with the softmax function directly predicts the label. The network structure can be simply represented as Input - C(64) - P(0.5) - C(128) - P(0.5) - C(256) - P(all)-FC(softmax)-Output, where C, P and FC denote convolution, pooling/coarsening, and fully connected layer, respectively. P(all) means that only a supernode is retained at the last pooling layer. The number of anchor nodes is set to 16. The scale of the neighborhood is set to 2, i.e, including the features of the node itself, first-order and second-order neighborhoods. We randomly divide the dataset with the proportion of 9:1, where 9 folds are as the training set and the remaining 1 fold is as the testing set. The accuracies are reported in terms of "mean ± standard deviation" of 10-fold cross-validation. We adopt Momentum optimizer to train the network for 500 epochs, where its batch size, initial learning rate, decay rate and momentum are set to 128, 0.05, 0.95 and 0.9, respectively. The dropout rate is set to 0.5, and the ReLU unit is leveraged as a nonlinear activation function.

Node classification. Two convolutional layers are used to form the network architecture, each of which is followed by a pooling layer. Then a fully connected layer and an output layer with the softmax function generate the final predictions. The network structure can be simply represented as Input - C - P(mean) - C - P(mean) - FC(softmax) - Output, where P(mean) indicates the "mean" operation in the pooling layer. Also, the number of anchor nodes is set to 16 and the scale of the neighborhood is set to 2. We adopt Adam optimizer to train the model for 500 epochs with an initial learning rate of 0.05, decay rate of 0.95. The dropout rate is set to 0.5 and the ReLU unit is nonlinear activation function. We run 10 experiments to take the averaged accuracy "mean±standard deviation" as the metric to measure the performance.

4.2 Comparison with State-of-the-arts

Graph classification. Table 1 shows the results on graph classification. Overall, our GDN approach achieves state-ofthe-art or comparable performance and obtains remarkable improvement on most datasets. For graph kernel-based methods (WL [Shervashidze et al., 2011], GK [Shervashidze et al., 2009] and DGK [Yanardag and Vishwanathan, 2015]), we can observe the WL kernel can obtain better results on most datasets than GK and DGK. In contrast to WL, the proposed GDN is able to improve by a large margin of 5.9% on NCI1, 14.35% on ENZYMES, 6.44% on IMDB-BINARY, etc. Recently the neural network-based works (PSCN [Niepert et al., 2016], NgramCNN [Luo et al., 2017], IGN [Maron et al., 2018], PPGN [Maron et al., 2019], GNTK [Du et al., 2019], CapsGNN [Xinyi and Chen, 2018], GIC [Jiang et al., 2019], GIN [Xu et al., 2019]) are superior to traditional machine learning methods. Compared to GIC, the GDN model still achieves superior performances, about 3 percentages on average, although a relatively lower result is gotten on the PTC dataset. This may be attributed to differences in the dataset or less appropriate parameter settings. Compared with these baseline methods, GDN can render impressive performance.

Node classification. We compare the performance of GDN against several baseline works: GCN [Kipf and Welling, 2017], GAT [Veliˇckovi´c et al., 2018], DGCN [Zhuang and Ma, 2018], JK-Net [Xu et al., 2018], GIN [Xu et al., 2019], GraphNAS [Gao et al., 2020], g-U-Nets [Gao and Ji, 2019], GRAPH-BERT [Zhang et al., 2020] and DiffNet [Zhang, 2020]. The accuracies are reported in Table 2, indicating that our GDN obtains a remarkable improvement. Compared to GCN, GAT, JK-Net, and GIN, our GDN achieves a relatively large gain. We attribute this improvement to the graph deformer convolution. Though GDN utilizes global consistency constraint, it still obtains better results than DGCN. Compared to recent methods GraphNAS, g-U-Nets, GRAPHBERT, and DiffNet, GDN still achieves superior performance on these three datasets. These demonstrate that the proposed GDN method performs well on various graph datasets by building the graph deformer process, where structure variations can be well captured and fine-grained node features can be extracted to enhance the discriminability between nodes. In summary, the remarkable gains indicate that the proposed GDN is effective to deal with graph classification.

4.3 Ablation Study

The scale s of neighborhood region. The influences of neighborhood scales are reported in Table 3. GDN-N (0) denotes that only the feature of the node itself is used, GDNN (0,1) includes the features of the node itself and first-order neighborhood, and so on. Due to the lack of structural information, we find that the performance of GDN-N (0) is obviously lower. As more information is considered, the accuracy of GDN-N (0,1,2) is generally superior to GDN-N (0,1) . This validates the importance of local neighborhood information, which is also a crucial property of traditional CNNs.

The number m of anchor nodes. We select the value m in the range [1, 25] to observe the changes of performance. As shown in Fig. 2, the performance of GDN indeed varies with the number of anchor nodes, but the accuracy trend is generally similar on different datasets (increasing first, then turning to degrade or be stable). Specifically, when m = 1, the accuracies are significantly lower, because only one anchor node is used, which is similar to sum aggregation. When m = 2, the performance is also relatively lower, 2 anchor nodes are insufficient to capture more variations. Then, the performance is relatively stable with m increasing. As realworld graph data is rather sparse, e.g., on average about 2

edges for each node in Cora and Citeseer datasets, so a few anchors matching the neighborhood size should be saturated to represent the variations without the information loss.

Graph convolution and graph coarsening. We further explore the effectiveness of graph convolution by removing the pooling layer from the GDN model, named as "GDN w/o P". Similarly, "GDN w/o C" means that graph convolution is removed. Table 4 shows the performance on citation datasets. Compared to GDN, both "GDN w/o P" and "GDN w/o C" obtain lower performances. But "GDN w/o P" is better than "GDN w/o C", while they are comparable on the Pubmed dataset. It indicates that the deformer convolution indeed improves the discriminability of nodes. Note that "GDN w/o C" has no convolutional layer, but average aggregation still is performed in the pooling layer for node classification.

Attention scores α. We visualize correlation scores α between neighborhood nodes and anchors. We respectively select some nodes from Cora and Citeseer datasets as center nodes and compute the scores of their first-order neighbors to anchor nodes. The neighbors have different emphasis on anchor nodes. As shown in Fig. 3, for node v20 in Cora, the attention score of the neighbor "A" on anchor node a4 is largest while the other four neighbors is close to anchor node a1. For node v153 in Citeseer, the neighbors "A" and "C" are more inclined to anchor node a6, while neighbor "D" prefers a12, and neighbor "B" is similar in most directions. This shows that neighbors of center nodes indeed place different emphasis on anchor nodes, so different proportions of features are assigned to the directions of these anchors, and then anisotropic convolution can be used to extract more fined-grained representation, which is superior to the sum/mean aggregation.

5 Discussion and Conclusion

How to set depth and width of the neural network?

The depth of network (i.e., layer number) and the width of filtering (i.e., order number) has some relation to the diameter of the graph. Usually, the total receptive field size of the top layer in the convolution network may be upper-bounded by the diameter of the graph. For a fixed receptive field size, we may employ a deeper network (stacking multiple layers) with small order (small width), or a shallow network with large order number (large width). Like numerous standard CNN, deeper networks (e.g., ResNet) with a small width (small kernel size) usually have better performance than shallow network with a large width.

How the problem of over-smoothness is handled?

Specifically, we introduce anchor nodes generated by imposing a non-linear transformation on cluster centers to match the updated features. Then, we project local neighborhoods with different structures onto multiple directions (w.r.t. anchors). Anisotropic convolution kernels can thus be performed over the anchor-coordinated space to well encode subtle variations of local neighborhoods. The anisotropic convolution realizes weight sharing for different local neighborhoods, which not only maintains computational efficiency, but also able to capture some common property between local neighborhoods just like the standard convolution kernel on images, and helps improve the expressive power of model.

Summarily, analogous to the standard convolution on images, we present a novel yet effective graph deformer network (GDN) to fulfill anisotropic convolution filtering on graphs. Further, we build a graph deformer network in an end-to-end learning fashion by stacking the deformable convolutional layers as well as the coarsening layers. Our proposed GDN archives significantly better performances on graph and node classifications. In the future, we will extend the GDN to more applications in the real world, such as link prediction, heterogeneous graph analysis, etc.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (Grants Nos., 62072244 and 61906094), the Natural Science Foundation of Jiangsu Province (Grant BK20190019), the Natural Science Foundation of Shandong Province (Grant No. ZR2020LZH008), and in part by State Key Laboratory of High-end Server & Storage Technology.