Graph Deformer Network
Authors: Wenting Zhao
Yuan Fang
Zhen Cui
Tong Zhang
Jian Yang
Wei Liu
Venue:  (2021)
Keywords: Graph Convolution
Anchor Space
Anisotropic Convolution
Graph Classification
Node Classification

Abstract: Convolution learning on graphs draws increasing attention recently due to its potential applications to a large amount of irregular data. Most graph convolution methods leverage the plain summation/average aggregation to avoid the discrepancy of responses from isomorphic graphs. However, such an extreme collapsing way would result in a structural loss and signal entanglement of nodes, which further cause the degradation of the learning ability. In this paper, we propose a simple yet effective graph deformer network (GDN) to fulfill anisotropic convolution filtering on graphs,  analogous to the standard convolution operation on images. Local neighborhood subgraphs (acting like receptive fields) with different structures are deformed into a unified virtual space, coordinated by several anchor nodes. In space deformation, we transfer components of nodes therein into anchors by learning their correlation, and build a pseudo multi-granularity plane calibrated with anchors. Anisotropic convolutional kernels can be further performed over the anchor-coordinated space to well encode local variations of receptive fields. By parameterizing anchors and stacking coarsening layers, we build a graph deformer network in an end-to-end fashion. Theoretical analysis indicates its connection to previous work and shows the promising property of isomorphism testing. Extensive experiments on widely-used datasets validate the effectiveness of the proposed GDN in node and graph classifications.

Under review as a conference paper at ICLR 2021
GRAPH DEFORMER NETWORK
Anonymous authors Paper under double-blind review
ABSTRACT
Convolution learning on graphs draws increasing attention recently due its po- tential applications to a large amount of irregular data. Most graph convolution methods leverage the plain summation/average aggregation avoid the discrep- ancy of responses from isomorphic graphs. However, such an extreme collapsing way would result in structural loss and signal entanglement of nodes, which further cause the degradation of the learning ability. In this paper, we propose a simple yet effective graph deformer network (GDN) to fulfill anisotropic con- volution filtering graphs, analogous to the standard convolution operation on images. Local neighborhood subgraphs (acting like receptive fields) with different structures are deformed into unified virtual space, coordinated by several anchor nodes. In space deformation, we transfer components of nodes therein into affini- tive anchors by learning their correlations, and build a pseudo multi-granularity plane calibrated with anchors. Anisotropic convolutional kernels can be further performed over the anchor-coordinated space to well encode local variations of receptive fields. By parameterizing anchors and stacking coarsening layers, we build graph deformer network in an end-to-end fashion. Theoretical analysis indicates its connection to previous work and shows the promising property of isomorphism testing. Extensive experiments on widely-used datasets validate the effectiveness of the proposed GDN in node and graph classifications.
INTRODUCTION
Graph flexible and universal data structure consisting of set of nodes and edges, where node can represent any kind of objects and edge indicates some relationship between pair of nodes. Research on graphs is not only important in theory, but also beneficial to in wide backgrounds of applications. Recently, advanced by the powerful representation capability of convolutional neural networks (CNNs) on grid-shaped 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 (Wu et al. 2017 Atwood & Towsley 2016 Hamilton et al. 2017 Velickovic et al.) 2017) have been proposed, and raise promising direction.
The main challenge is the irregularity and complexity of graph topology, causing difficulty in con- structing convolutional kernels. Most existing works take the plain summation average aggrega- tion scheme, and share a kernel for all nodes as shown in Fig. [(a)] However, there exist two non- ignorable weaknesses for them: i) losing the structure information of nodes the local neighbor- hood, and ii) causing signal entanglements of nodes due to collapsing to one central node. Thereby, an accompanying problem that the discriminative ability of node representation would be im- paired, and further -oomooooo graphs/subgraphs may produce the same responses.
Contrastively, in the standard convolutional kernel used for images, is important to encode the variations of local receptive fields. For example, a 3 x 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-fixi fixed nodes. However, this deterministic method is sen- sitive node ranking and more prone to being affected by graph noises. Furthermore, some graph convolution methods (Velickovic et al. [2017] Wang et al. (019)) introduce an attention mechanism to learn the importances of nodes. Such methods emphasize on mining those significant struc-

---

Under review as a conference paper at ICLR 2021
Node features
Single grain feature
Kernel
(a) Traditional aggregated
-aased based convolution
Anchors
Fine-grained features
Kernel
D (x,) -
C(F(2,K)
(b) Graph deformer convolution
Figure 1: An illustration of ours vs the previous convolution. The red node is reference node. (a) In traditional graph convolution, the convolution kernel is shared for all nodes due to the plain aggregation over all nodes in the neighborhood. (b) In our method, the irregular neighborhood deformed into a unified anchor space, which pseudo-grid shape, and then the anisotropic convolution kemel is used to encode the space variations of deformable features.
tures/features rather than designing anisotropic convolution kernels, so they cannot well represent local variations of structures in essence.
In this work, we propose novel yet effective graph deformer network (GDN) to implement anisotropic convolutional filtering on graphs as shown in Fig. [(b)] exactly behaving like the stan- dard convolution on images. Inspired by image-based convolution, we deform local neighborhoods of different sizes into 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 image-like anisotropic convolution kernels can be imposed on amchor-coording plane, and local variations of neighborhoods can be perceived effectively. Due to the importance anchors, we also deform anchor nodes with adaptive parameters to match the feature space of nodes. As anisotropic convolution kernels endowed with the fine-grained en- coding ability, our method can better perceive subtle variations of local neighborhood regions as well 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. Exten- sive experiments 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 method and then elaborate the details.
Denote g (V,E) as an undirected graph where represents set of nodes with | = n and is of edges with |g| matrix can be defined as E Baxx And X E Raxd is the feature matrix. To state conveniently, use X; or X; denote the feature of the i-th node. Besides, for node U. the first-order neighborhood consists of nodes directly connected to v,, which is denoted as N2, = {uy vi) E E}. Accordingly, we can define s-order neighborhood Nss as the set of s-hop reachable nodes.
According the link relations in E, the corresponding adjacency
2.1 BASIC FORMULATION
Given a reference node U, in graph g. we need to learn its representation based on the node itself well its contextual neighborhood Nr.. 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 pseudo space spanned by anchors. We
2

---

Under review as a conference paper at ICLR 2021
denote the set of anchor nodes by V (vo, vi,... mm-1)- The convolution on Nr, is formulated as:
x, (g * (1,), C(F(F)) ((Fp(),K)), K),
F F Σ
D Dv- (I,, Xx, θ)
(2)
where
V. x.: anchor node and pseudo coordinate vector (a.k.a. feature vector). Please
Section 2.2 for anchor generation.
D: the deformer function. transforms node v into a virtual coordinate space spanned by anchors. O is the deformer parameter to be learned. Please see Section 2.3. for details.
p(r) E Rmxd, the deformed multi-granularity feature from the neighborhood of node ür- Each granularities F!!)) corresponds to an anchor node v,.
C, KC: the anisotropic convolution operation on anchor space and convolution kernel. * f represents filter f acting on graph g. The relationship between anchor nodes can be built by some metries such as Cosine distance, and anchor nodes may format as a pseudo 2-D grid just like the patch in images. Please see the details in Section 2.3.2
2.2 ANCIIOR GENERATION
Anchor nodes are crucial to the graph convolution process, because neighborhood regions are unit- edly 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, chors. 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,
cluster some nodes randomly sampled from the graph initial
D + Clustering {(v,, xx) U E )sampling)
(3)
where Viampling the sampled node set, in which each node randomly sampled from the graph, y {(V,, xx) is the initial anchor set generated by clustering, which Vμ represents k- th anchor node and X2 represents its feature vector, m is the number of anchor nodes. Note that when given anchor nodes, the response of our method will be invariant however to permute nodes of one graph during the training stage as well as testing stage. The clustering algorithm might affect the final anchors due to random sampling for initialization, but cannot affect the property of permutation invariance, which just like random initialization the network parameters.
A larger m could increase the expression capacity of anchors, but causes more redundancy and a larger computational cost. Due to the sparsity of graphs, in practice, several anchors sufficient to encode each neighborhood region. To better collaborate with node/feature variations during graph convolution learning, transform the initial anchors into proper space by parameterizing them:
3 ReLU (W + bA).
k = 0, 0, ... m 1,
(4)
where W A. 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
2.3.1 SPACE TRANSFORMATION
Now we define the deformer function D in Eqn. ( which transforms neighborhood nodes to the anchor space. For each node Uy E No,, we derive anchor-related feature (also query feature) and value feature vectors as
qj = ReLU (Wox, + bo),
j j= 0, 1, ... Rr 1,
(5)
uy ReLU (Wux, + bu),
j 0, 1, nn 1,
(6)
3

---

Under review as a conference paper at ICLR 2021
where W Q. Wo are the learnable weight matrices, and bq. by the biases. The query feature qj indicates how to transform Ui to the anchor space by interacting with anchors, and the value vector uj is the transformable component to the anchor space.
For the neighborhood No.. the correlation to anchors defines a set of weights a {01,1,".. A1,,.. O'n,,,:"... On,,,,) ), which measures the scores of all nodes within the neigh- borhood projected onto the directions of anchor nodes. Formally,
exp((g,,ā.)
Oj.k Ex exp(((s ax)))
- ... m
where (:-)) denotes the inner production, then normalization is done by softmax function. Oj,k may be viewed as the attention score of the node by w.r.t. the anchor Vi- After obtaining the attention score, the irregular neighborhood can be transformed into the anchor-corddinated space.
U La agauy, == 0,11 ny 1.
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. experiment, for simplicity, the query feature and value feature are shared with the same parameters in Eqns. (5) and (6).
2.3.2 ANISOTROPIC CONVOLUTION IN THE ANCHOR SPACE
Afterward, s-hop neighborhood of node v, is deformed into the size-fixed anchor space, i.e., - (ūo, ü, .... 1m The anisotropic graph convolution can be implemented by imposing different mapping on each anchor as
ReLU ( KTTū b), = m
(9)
where x((() E Rd,, the matrix Kr is d x d' weight parameter imposed the features w.r.t. anchor, and b is the bias vector.
In the convolution process, different filter weights imposed different features of anchor nodes, which is an anisotropic filtering operation. For an intuitive description, we assume the simplest case of 2-D space, which of course can be extended higher dimension. Assuming in 2-D, we project all neighborhood nodes onto anchor nodes, then employ different filters on different anchor nodes in 2-D plane, which likes the standard convolution, so called anisotropic convolution. 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 different-sized neighborhoods into the size-fixed anchor space to well advocate anisotropic convolution like the standard convolution on images.
2.3.3 MULTI-SCALE EXTENSION
Intuitively, the first-order neighborhood is necessary to be used for node aggregation, because it in- dicates 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 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 natural incorporate higher-order proximity to capture more informa- tion. Generally, second-order information is sufficient as most works (Tang et al. 2015 Wang et al.) 2016). Higher-order information can also considered, but the computational complexity will in- crease. It can be understood as a trade-off of expression ability and computational complexity. In this paper, we consider both first-order and second-order neighborhoods. Specifically, we deform both first-order and second-order neighborhoods into feature space represented by anchor nodes, and convolve over them respectively. Then the learned different neighborhood representations and the original node feature concatenated the final filtering response,
[x, x(211
(10)
where x, denotes the convolution response on the s-order neighborhood Nos node v,.. Further, can stack multiply layers to extract more robust features larger receptive fields.
4

---

Under review as a conference paper at ICLR 2021
2.4 COARSENING
Graph coarsening can not only reduce the computational cost but also enlarge the receptive field to learn abstract features like image pooling. Below simply introduce this operation used here.
Node Classification. We do not need to remove nodes, and thus name it as pooling. The pooling node-wise diffusion on local region, and be performed over multi-scale neighborhoods. The pooling over S scale neighborhoods w.r.t. the reference node v, is
P(G(u,)) P((x)))) E N,, 5- = 1........... ,)),
(11)
where the pooling P is usually defined as "max" or "mean". In practice, their performance has little difference in graph convolution, so we choose the mean operation in our experiments.
Graph Classification. We employ the graph cut method used in (Jiang et al., 2019) to partition an entire graph into several subgraphs. During graph coarsening, binary cluster matrix Z E Rn is obtained, where only one element in each row is non non-zerr zeroo i.c., Zic = 1 when the vertex v falls into the cluster Then the adjacent matrix and feature matrix of the input graph transformed into
A' + AZ X' Z X,
(12)
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.
2.5 LOSS FUNCTION
For node and graph classifications, the final convolution output is denoted as Y after feeding several network layers forward. Then we use the cross-entropy loss on the training D...
L = Dirl
Σ (Y = (1)==
(13)
However, in the scenario of semi supervupe node classification, main limit is that small portion of nodes is annotated as the training set. Our aim is to use labeled nodes as well as graph structure train model with a good generalization ability. A straightforward way add a regularization term to avoid overfitting. To this end, we employ a global consistency constraint through positive pointwise mutual information as used in [huang & Ma 2018) regularize the loss function.
2.6 COMPUTATIONAL COMPLEXITY
For the computational complexity, analyze the main module of graph convolution. In one-layer convolution, GCN (Kipf & Welling 2016) 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' 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 Oeedd S) and O'umdd' S), respectively, where m is the number of anchor nodes. Thus, the total computational complexity is O S rmmdd' S), which is linearly proportional GCN with the factor when d and d' have the same order number.
3 CONNECTION TO RELATED WORK
In contrast to previous methods (Kipf & Welling 2016 Xu et al., 2019 Zhuang & Ma 2018), etc., the way of aggregation is obviously different. GCNs usually bypass the irregularity of graphs by utilizing weighted-sum aggregation over the neighborhoods, which is an isotropic filter. Our GDN instead firstly transforms the local neighborhoods into a regular anchor space and then performs anisotropic filters on the regular anchor space.
In contrast to Transformer (multi-head attention mechanism) (Vaswani et al. 2017) and its a gener- alization, graph attention network (Velickovic et al.) 2017), give the following differences. In the Transformer, all center nodes are anchor nodes, and the attention coefficient is computed between each central node and its neighbor nodes. In our GDN, several anchor nodes are initially generated
5

---

Under review as a conference paper at ICLR 2021
by K-means Cluster from global nodes which implicitly represents several different directions like a k x & patch (upper left, upper right, etc.) in images, and the attention coefficient computed between local neighbors and anchor nodes. Because the anchor nodes generated from the global graph, all local neighborhoods are projected into a common anchor space, some common property for all local neighborhood can be captured by imposing an anisotropic filter anchors. In contrast, though multi-head mechanism is used, the Transformer is still locally aggregated. Another weakness of the Transformer computationally intensive, especially for large graphs.
Our proposed GDN is different form other peer works, P-GNN (You et al. 2019) selects several an- chor nodes as position characterization, and concatenates the feature of node with features of anchor nodes, then mean aggregation is employed on different anchor sets followed by fully-connected transform, which is an isotropic filter. LGGN (Gao et al.) 2018) performs feature selection by sorting the top k-largest values on each feature dimension, and produces k new nodes (fixed size) for the next filtering process. CapsGNN (Xinyi & Chen 2018) presents capsule graph network to learn graph capsules of different aspects from node capsules by utilizing attention module and routing mechanism. contrast, our proposed method transforms local neighborhood into an anchor space spanned by several anchor nodes, the filtering is operated in the anchor space. Transforming irregular structures into a regular space also be studied in 3D domain. PointCNN (Li et al.) 2018b) learns an X-transformation from the input points and then applies convolution operator the X-transformed features. KPConv (Thomas et al.) 2019) takes radius neighhorhoods as input and processes them with weights spatially located by small set of kernel points. essence, PointCNN (Li et al. 2018b) leverages the self-attention mechanism to produce fixed-size output for different-size local neighbor regions. KPConv (Thomas et al. 2019) projects neighbor 3D points into 3D kernel points, and this projection is only operated in 3D point space. In contrast, our proposed method focus on the more general graph domain. More related work can be found in Appendix.
4 THEORETICAL ANALYSIS
Here, we present a theoretical analysis about the expressive power of several aggregation methods including the mean, sum, and proposed graph deformer operation. Inspired by (Xu et al. 2019)) we evaluate them by verifying whether graphs are isomorphic. Then, we give the following proposi- tions.
Proposition 1. There exists set of network parameters able to graph deformer process can distin- guish two non-isomorphic graphs 91 and G2, which cannot be distinguished by mean/sum aggrega- tion.
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 Appendix. We can draw the conclu- sion that the expressive power of the proposed graph deformer network is provably stronger than mean/sum aggregation, which can accomplish an injective as powerful as the Weisfeiler-Lehmmnn (WL.) graph isomorphism test.
Table 1:
Comparison with state-of-the-art methods on node classification. The number in parenthe- denotes the number of convolutional layers in certain network.
Method
Cora
Citeseer
Pubmed
SVM
Planetoid
Yang et al.
2016
75.7
64.7
77.2
ChebyNet (Defferrard
2016)
81.2
69.8
74.4
Spectral
GCN Kipf & Welling
2016
81.5
70.3
79.0
DGCN (Zhuang & Ma
2018
83.5
72.6
80.0
MoNet MMonti et al.
2017
81.7
78.8
GAT /Velickovic al 2011
83.0
72.5
79.0
JK-Net (Xu 2018
79.71 0.62
69.03 0.55
78.17 0.27
Spacial
GIN Xt al. 2019
79.49 0.65
67.78 0.89
78.37 0.29
GDN(I
85. 85. 16 0.47
73.13 = 0.826
79.8 1 0.297
GDN(2L)
84.76 + 0.587
73.77 = 0.447
80.77 0.24

---

Under review as a conference paper at ICLR 2021
Table 2: Comparison with state-of-the-art methods graph classification.
Method
MUTAG
PTC
NC11
ENZYMES
PROTEINS
IMDB-BINARY
IMDB-MULTI
WL
80.72 + 3.00
56.97 2.01
80. 00.13:2 0.50
53.15 = 1.14
72.92 0.56
72.86 = 0.76
30.35 =
Kernel
GK
$1,06 + 2.11
57.
1.41
02.26
0.29
26.61 0.99
71.67 0.55
05.67 + 0.98
43.89 0.38
DGK
$2.66
57.32
62.48
0.25
27.08
0.79
71.68
0.50
86.96 0.58
0.52
FB
$4,66 +: 2.01
55.58 2.30
62.90 +: 0.96
29.00
1.16
60.97
1.34
72.02 +: 4.71
47.34 3.56
Feature
DyF
2.37
68.27
0.34
33.21
1.20
75.04
0.65
72.87
4.05
3.56
PSCN
82.63 1: 4.21
60.00 1: 4.82
78.39 4: 1.89
75.89 1: 2.76
71.00) 1: 2:29
45.23 21 2.84
NgramCNN
91.99 5.63
1.72
2.71
1.10
SAEN
$4.90 +: 1.82
57.04
1.30
77.80 0.42
75.31
0.70
T1.26 0.74
49.11
0.64
IGN
83.80 12.95
58.53
6.86
74.33
2.71
76.58 5.49
72.0 5.54
48.73
3.41
GNN
PPGN
90.35 8 8.7
66.17
6.54
83.19
1.11
77.2
4.73
72.6
50 3.15
GNTK
90.0 8.5
6.9
$1.2
75.6 2 1.2
76.9 3.6
52.8 2 166
CapaGNN
56.67
78.35
1.55
5.67
9.36
T3.10 4.83
2.65
GIC
91.41 1: 4.43
77.64 2: 6,98
81.08
1.77
62.50 5.12
77.65
1322
76.70
3.25
51.66
3.40
GIN
$9.1
6..6
76.2
5.11
52.3
GDN (3L)
97.39- + 2.65
75.57 + 7.56
86.03 + 1.23
67. + 6.96
81.32 3.09
79.3
3.26
55.2 + 4. 3.34
EXPERIMENTS
In the section, carry out extensive experiments to assess the proposed GDN model on both node and graph classification tasks. For node classification, three citation graphs are used: Cora, Citeseer, and Pubmed. For graph classification, we adopt seven datasets assess GDN method: MUTAG, PTC, NCII, PROTEINS, ENZYMES, -INAB,, and IMDB-MULTI. The details of these datasets and experimental setups can be found in the Appendix.
5.1 COMPARISON WITH STATE-OF-THER -FEE--OF--EERRERE
Node classification. We compare the performance of GDN against several baseline works: ChebyNet (Defferrard et al. 2016), GCN (Kipi & Welling 2016), MoNet (Monti et al. (017). GAT Velickovie et al. 2017). DGCN (Zhuang & |a|2008) JK-Net eX al. 2018) and GIN (Xu ct al. 2019). The accuracies are reported in Table I which clearly indicates that our GDN obtains remarkable improvement. Deep and Planetoid aim generate effective node embeddings, and our proposed GDN significantly outperforms these two methods. GCN is a first-order approx- imation of ChebyNet and has realized relatively higher results. Simultaneously, it can be regarded as a special case of Monet, and their classification accuracies are similar. Compared to GCN, our GDN achieves relatively large gain. We attribute this improvement to the graph deformer con- volution. We further compare GDN to GAT, still achieving superior performance on these three datasets. Though GDN utilizes global consistency constraint, there is still a marked improvement compared to DGCN. Compared to recent methods JK-Net and GIN, GDN also obtains large mar- gin over them. 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 fineggrained node features can be extracted to enhance the discriminability between nodes.
Graph classification. Table 2 shows the results on graph classification. Overall, except for PTC, our GDN approach achieves state-of-the-arr performance on all datasets and obtains remarkable improvement. For graph kernel-based methods (WL (Shervashidze et al.) 2011), GK (Shervashidze et al. 2009) and DGK (Yanardag & Vishwanathan 2015)). we can observe the WL kernel can obtain better results most datasets than GK and DGK. In contrast WL, the proposed GDN is able to improve by a large margin of 5.9% on NCI1, 14.35% on ENZYMES, 6.44% on AMDB-BINARY etc. For the feature-based methods (FB (Barnett et al., 2016). DyF (Gomez al. 2017)) GDN obviously outperforms them. Also. GDN is better than SAEN (Orsini et al.
Recently the
GNN-based work (PSCN (Niepert et al. 2016), NgramCNN (Luo et al. (017). IGN MMaron al.
2018), PPGN (Maron et al., (211)). GNTK (Du et al.) 2019). CapsGNN (Xinyi & Chen, 2018)), GIC (Jiang et al. 2011)) GIN (Xu et al. 2019)) is 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 gotten on the PTC dataset. This may be attributed to differences in the dataset or less appropriate model parameter settings. Compared with these baseline methods, our GDN can render impressive performance. In summary, the remarkable gains indicate that the proposed GDN is effective to deal with graph classification.
7

---

Under review as a conference paper at ICLR 2021
Table 3: Comparison on the scales of neighhorhood regions.
Method
Cora
Citeseer
Pubmed
GDN-A/0)
54.95 + 2.004
55.7 1.259
72.94 + 1.582
GDN-M/O.
82.62 + 0.668
72,56 + 0.945
80.24 + 0.224
(DN-A/(01122
84. 74.76 + 0.587
73.77 + 0.447
80.77 + 0.241
163
15.0
715-
$4.5
64.0
52.
033
22.0
030
71.-
625
12
12 15
12
12 26
The number of anchar nodes
The number of anchor modes
(a) Cora
(b) Citeseer
Figure 2: Comparison on the number m of anchor nodes.
Table 4: The verification of convolutional layer C and pooling layer P in our GDN method. Pubmed
Method
Cora
Citeseer
GDN w/o P GDN w/o C GDN
83.97 + 0.393
72.53 + 0.593
78.86 + 0.902
82.82 + 0.724
71.57 + 0.831
78.75 + 0.626
84.76 + 0.587
73.77 + 0.447
80.77 + 0.241
5.2 ABLATION STUDY
The scale of neighborhood region. The influences of neighborhood scales are reported in Table GDN-N(0) denotes that only the feature of the node itself is used, GDN-N'0..1 includes the features of the node itself and first-order neighborhood, and we find that the performance of GDN-N(0) is obviously lower. As more information is considered, the accuracy of GDN-A is generally superior to GDN-N1(011) This validates the importance of local neighborhood information, which is also a crucial property of traditional CNNs.
Due to the lack of structural information,
The number m of anchor nodes. We select the value in the range [1, to observe the changes of performance. As shown in Fig. 2 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, which means anchor nodes are insufficient to capture more variations. Then, the performance is relatively stable with increasing. The reason should be that, as real- world graph data is rather sparse, e.g., on average about 2 edges for each node in Cora and Citeseer datasets, 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 convo- lution 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. T 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" actually similar to the plain aggregation with the average operation.
Attention scores a. We visualize correlation scores a 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. As shown in Fig. 3 for node V2o in Cora dataset, the attention score of the neighbor "A" on anchor node ã4 is largest while the other four neighbors is close to anchor node ai. For node vi in Citeseer, the neighbors "A" and "C" are more inclined to anchor node ag. while neighbor "D" prefers ā12. and neighbor "B" is similar in most directions. These neighbors place different emphases on anchor nodes, then different proportions of features are assigned to the directions of these anchors, and an anisotropic convolution is used to extract more fined-grained representation, which is superior the sum/mean aggregation.
8

---

Under review as a conference paper at ICLR 2021
0.10
0.0
0.200
0.12
0.09
0.5
0.175
84
31
0.0
55
0.05
51
0.125
0.05
0.15
0.100
80
0.06
81
0.10
0.04
0.03
0.050
0.02
0.02
0.025
(a) node U20
(b) node 1/30
(c) node U54
(d) node 1/53
Figure 3: Visualization of attention scores in the first-order neighborhood of nodes U20 and 030 in the Cora dataset, and ti44 and V159 in the Citeseer dataset. (a) Node U2u has 5 neighbors while (b) node van has neighbors. (c) Node U54 has 3 neighbors while (d) node 0153 has 4 neighbors.
CONCLUSION
In this work, analogous to the standard convolution on images, we proposed novel yet effective graph deformer network (GDN) fulfill anisotropic convolution filtering graphs. We trans- formed local neighborhoods with different structures into a unified virtual space, coordinated by several anchor nodes. Anisotropic convolution kernels thus be performed over the anchor- coordinated space to well encode subtle variations of local neighborhoods. Further, we built graph deformer network in an end-to-end learning fashion by stacking the deformable convolutional layers as well the coarsening layers. Our proposed GDN accomplishes significantly better performances on both node and graph classifications. In the future, we will extend the graph deformer method to allow more applications in the real world, such as link prediction, heterogeneous graph analysis, etc.
REFERENCES
James Atwood and Don Towsley. Diffussion-conoluttinnal neural networks. In Advances in Neural Information Processing Systems, pp. 1993-2001, 2016.
Ian Barnett, Nishant Malik, Maricke Lydia Kuijjer, Peter Mucha, and Jukka-Pekka Onnela. Feature-based classification of networks. ArXiv, abs/1610.05866 2016.
Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 2s(supLL1);: i47-i56, 2005.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. International Conference Learning Representations, 2014.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018.
Fan RK Chung. Spectral graph theory. Number 92. American Mathematical society, 1997.
Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Cor- win Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro com- pounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-797, 1991.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, pp. 3844-3852, 2016.
Simon Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang. and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In H. Wallach,

---

Under review as a conference paper at ICLR 2021
H. Larochelle, A. Beygelzimer, F. dAlché- Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32, pp. 5723-5733. Curran Associates, Inc., 2019.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Pp. 1416-1424. ACM, 2018.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning-Volume Volume 70, pp. 1263-1272. JMLR. org, 2017.
Leonardo Gutierrez Gomez, Benjamin Chiem, and lean-Charles Delvenne. Dynamics based features for graph classification. arXiv preprint (tdi::/705..0050 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs In Advances Neural Information Processing Systems, pp. 1024-1034, 2017.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data, arXiv preprint arXiv:1506.051663 2015.
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, (2):251-257, 1991.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Advances in Neural Information Processing Systems, pp. 4558-4567, 2018.
Jiatao Jiang, Zhen Cui, Chunyan Xu, and Jian Yang. Gaussian-induced convolution for graphs. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. International Conference on Learning Representations, 2016.
Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. Cayleynets: Graph con- volutional neural networks with complex rational spectral filters. IEEE Transactions Signal Processing, 67(1)977-109, 2018.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirly-Second AAAI Conference on Artificial Intelligence, 2018a.
Qimai Li, Xiao-Ming Wu, Han Liu, Xiaotong Zhang, and Zhichao Guan. Label efficient semi- supervised learning via graph filtering. In Conference on Computer Vision and Pattern Recogni- tion, 2019.
Yangyan Li, Rui Bu, Mingchao Sun, Wei Wu, Xinhan Di, and Baoquan Chen. Pointenn: Convolu- tion on x-transformed points. In Advances in neural information processing systems, pp. 820-830, 2018b.
Ziqi Liu, Chaochao Chen, Longfei Li, Jun Zhou, Xiaolong Li, Le Song, and Yuan Qi. Geniepath: Graph neural networks with adaptive receptive paths. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4424 4431, 2019.
Z. Luo, L. Liu, J. Yin, Y. Li, and Z. Wu. Deep learning of graphs with ngram convolutional neural networks. IEEE Transactions on Knowledge and Data Engineering, 29(10):2125-22 2139, 2017.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and cquivariant graph networks. arXiv preprint arXiv: Siii:v8112099033 2018
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, pp. 2156-2167, 2019.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Conference Computer Vision and Pattern Recognition, pp. 51 5125-122,, 2017.
10

---

Under review as a conference paper at ICLR 2021
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In International conference on machine learning, pp. 2014-2023, 2016.
Francesco Orsini, Daniele Baracchi, and Paolo Frasconi. Shift aggregate extract networks. arXiv preprint arXiv: 05537, 2017.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mchlhorn, and Karsten Borgwardt. Ef- ficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics, pp- 488 495, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisfeiler-Icmaa graph kernels. Journal of Machine Learning Research, 12(23):2539- 2561, 2011.
David Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing graphs: Extending high-dimensional data analysis to net- works and other irregular domains. IEEE Signal Processing Magazine, 30(3):83-98, 2013.
Martin Simonovsky and Nikos Komodakis. Dynamic edge-conditioned filters in convolutional neu- ral networks on graphs. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3693-3702, 2017.
Felipe Petroski Such, Shagan Sah, Miguel Alexander Dominguez, Suhas Pillai, Chao Zhang, An- drew Michael, Nathan D Cahill, and Raymond Ptucha. Robust spatial filtering with graph convo- lutional neural networks. IEEE Journal of Selected Topics in Signal Processing. 11(6):884-896, 2017.
Ana Susnjara, Nathanael Perraudin, Daniel Kressner, and Pierre Vandergheynst. Accelerated filter- ing on graphs using lanezos method. arXiv preprint arXiv:/509.044 2015.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proceedings of the 24th international conference on world wide web, pp. 1067-1077. International World Wide Web Conferences Steering Committee, 2015.
Hugues Thomas, Charles R Qi, Jean-Emmanuel Deschaud, Beatriz Marcotegui, Francois Goulette, and Leonidas J Guibas. Kpconv: Flexible and deformable convolution for point clouds. In Proceedings of the IEEE International Conference on Computer Vision, pp. 6411-6420, 2019,
Hannu Toivonen, Ashwin Srinivasan, Ross D King, Stefan Kramer, and Christoph Helma. Statistical evaluation of the predictive toxicology challenge 2000-2001. Bioinformatics, 19(10): 183-1193, 2003.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710. 10903, 2017.
Nikil Wale, Ian A Watson, and George Karypis. Comparison of descriptor spaces for chemical com- pound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008.
Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 2016.
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. Heterogeneous graph attention network. In The World Wide Web Conference, pp. 0022-003,, 2019.
Bo Wu, Yang Liu, Bo Lang. and Lei Huang. DGCNN: disordered graph convolutional neural net- work based on the gaussian mixture model. arXiv preprint 13120037,, 2017.
Zhang Xinyi and Lihui Chen. Capsule graph neural network. International conference on learning representations, 2018
11

---

Under review as a conference paper at ICLR 2021
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. arXiv preprint 1ef1::880600333, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful graph neural networks? International Conference on Learning Representations, 2019.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374.
ACM, 2015.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33rd International Conference on International Conference Machine Learning, volume 48, pp. 40 48, 2016.
Jiaxuan You, Rex Ying, and Jure Leskovee. Position-awar graph neural networks. arXiv preprint 14Xx:11906.4417,, 2019.
Chenyi Zhuang and Qiang Ma. Dual graph convolutional networks for graph-based semi-supervised classification. In Proceedings of the 2018 World Wide Web Conference on World Wide Web, pp- 499-508. WWW, 2018
12


Reviews:
[{"review_id": "dIOMJAhWOMi", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n\nThis work proposes the Graph Deformer Network (GDN), whose key component is the proposed Graph Deformer Convolution (GDC). The GDC is based on the attention mechanism, where a fixed number of query vector comes from a clustering process of some randomly sampled nodes (In my opinion, the q vector in the paper should be named the key vector instead query vector, according to [1]). The attention thus yields a fixed number of ordered vectors as outputs, where an anisotropic convolution can be applied on. Experimental results on both node and graph classification tasks demonstrate the effectiveness of the proposed GDC.\n\n[1] Vaswani et al. \"Attention is all you need\", NeurIPS 2017.\n\n##########################################################################\n\nReasons for score: \n\nOverall, I vote for rejection. My major concerns lie in three aspects, as detailed in Cons below: 1) The methods were not clearly described. Many details are lost; 2) The experimental results on graph classification tasks are not convincing; 3) Important studies with the same motivation or similar methods are not discussed.\n\n##########################################################################\n\nPros:\n\n1. The experimental studies on node classification tasks seem comprehensive and convincing.\n\n2. The motivation is well-explained by comparing graph convolutions with regular convolutions on images.\n\n##########################################################################\n\nCons: \n\n1. The methods were not clearly described. Many details are lost.\nFor example, in section 2.1, the f and K in Equation (1) are not explained.\nIn section 2.2, V_sampling in Equation (3) is not clearly explained. It is not clear what \"all neighborhoods\" means. Are they just \"all nodes\"?\nIn addition, the notation is confusing. How to cluster a tuple? I assume that clustering is performed on feature vectors.\nAnother key question is that, clustering outputs do not naturally have orders. How do you order those m clusters? This is crucial for graph classification tasks, as the weight parameters K_i is associated with the indices i=0,1,...,m-1. If you don't have certain ways to order the m clusters, the learned parameters may not generalize well.\n\n2. The experimental results on graph classification tasks are not convincing. It is because the proposed GDN uses a different readout function as strong competitors like GIN. The GDN uses Equation (12) plus a convolutional neural network, similar to [2], while GIN simply use sum/avg followed by an MLP. Ablation studies with the same readout function are required to show that the improvement of GDN indeed comes from GDC.\n\n[2] Zhang et al. \"An End-to-End Deep Learning Architecture for Graph Classification\", AAAI 2018\n\n3. Important studies with the same motivation or similar methods are not discussed, like [3,4].\n\n[3] Gao et al. \"Large-Scale Learnable Graph Convolutional Networks\", KDD 2018\n[4] Zhang et al. \"Capsule Graph Neural Network\", ICLR 2019\n\n##########################################################################\n\nQuestions during rebuttal period: \n\nPlease address and clarify the cons above.\n\n##########################################################################\n\nComments after rebuttal period: \n\nI appreciate the authors' efforts on increasing the clarity of this paper. However, the answers to \"How do you order those m clusters?\" are not convincing (as well as the responses to R4's 2nd concern, which mentions the same problem). It is a key point in generalization across different graphs. According to the experimental results, I believe there is an implicit mechanism in the proposed method that achieves the ordering, but it is not clearly explained and analyzed. I will keep my score.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "4J3woGWTBbS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose to extend isotropic convolutional operator on graphs to anisotropic one, well suited to encode complex geometric topology of the graphs while providing representations at different levels of granularity. It is achieved by considering a multi scale neighboring system.\n\nOne of the challenges in the design of powerful graph convolutional networks is the ability of the network to capture the complex geometric structure of irregular graphs characterized by a strong topological variability where nodes have different number of connections ranging from sparse connectivity to dense one. Moreover, graphs are of variable size. \nIn contrary to isotropic convolution  which lacks of expressivity and are not capable at leveraging discriminating representations at different direction of information, this paper cope with this problem.\n\nThe focus of paper is mainly oriented to the design of anisotropic convolutional operator corroborated by a convincing empirical validation, including different datasets for both node and graph classification. Moreover, the authors provide a theoretical analysis showing that the proposed  Graph Deformer Network under certain conditions, it could distinguish two non-isomorphic graphs (developed in the supplementary part) where most of aggregation operators fail, namely  averaging and sum.\n\nThe authors have explored well the different families of methods designed for  learning on graphs; ranging from spectral to spatial methods. In this paper, the proposed method can be added to the class of spatial methods. Relevant works to the contribution are discussed and cited in the related works parts and experiments.\n\nOn of the strong points of the paper is the anchor representation which enables the explicit design of anisotropic convolution operator. This representation is based on K-means sampling. It is beneficial to control the variable-sized graphs.\n\nHowever, the proposed network is relatively expensive in time and space which can hinder processing very large graphs and datasets. For instance, in community detection and particle physics simulations where the number of nodes is in general higher than 2 millions. The latter can be reduced drastically to thousands of nodes thanks to subsampling techniques such as K-means so that Graph Deformer Network can be tractable in practice at the expense of a possible loss of geometric structure. The idea is to come up with a trade-off between the number of nodes with respect to the initial geometry and the expressive power of the anisotropic convolutional operator.\n\nIn order to clarify some points, l have some questions :\n\n1- How the problem of over-smootheness is handled  by the GDN? \n\n2- In equation (10), why only second order is considered ? what about the diameter of the graphs ? or different orders w.r.t to the graph connectivity and edge distribution at a given neighboring systems.\n\n3- How different is the injective function proposed in this work compared to the one in GIC network ? It is mentioned in the supplementary part  that the designed injective function is stronger than standard schemes based on averaging and sum aggregations. However, in Table 2 (second column), GIC outperforms GDN.\n\n4- Why in the setting of graph classification, GDN is composed of 3 layers while in node classification setting, GDN is composed of 2 layers ? even  if node classification data are larger than graph classification.\n\n5- How do you explain the slight gain in performances for GDN with pubmed dataset compared to other dataset ? \n\n6- Pubmed data is composed of very large graphs, how do you explain the fact that it needs only 2 layers as other datasets ? It could be interesting to show the results with different number of layers to see whether the depth of the network brings extra gain or suffers from over-fitting. Moreover, it’s still not clear whether deeper networks are needed to tackle graph data. For that reason, it could be interesting to summarize the depth and width of the proposed models for each dataset for more interpretability. The depth can be upper-bounded by the diameter of the graph in the case of symmetric graphs.\n7- How could one explain that the sum of neighbors in the local neighborhood is the same as the sum on each anchor node after deformation?\n\nFor more clarity tables could be organized as follow :  \n\nA- Baselines (Linear SVM, MLP) \n\nB- Euclidean ConvNets\n\nC- Non Euclidean ConvNets (C-1 : Spectral methods , 2- : Spatial methods)\n\nAs future works, one may consider : \n\nA-  To study the proposed network from spectral standpoint and visualize the Fourrier atoms  to analyze the behaviour of  the anisotropic convolutional operation.\n\nB- To show the genericity of the proposed network, it could be beneficial to extend this work to challenging real world problems such as spatio-temporal data in computer vision, high energy physics,... etc. Moreover, node regression could be considered.\n\nC- Linear SVM and MLP classifiers could be a very important baselines. The latter allow to assess  the extra gain of GCN with respect to the number of parameters of the model.\n\nThe approach is well placed in the litterature, the organization of the paper is clear and the supplementary part is helpful including theoretical details and experimental ones. However, the experimental part could be explored more.\n\nFor all these reasons, l would like to recommend to accept this paper. Beneficial for both theoretical follow-up studies and empirical ones.\n\n\n\n\n\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "320Lm8eHAg3", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work tries to realize the anisotropic convolution by using anchor nodes in the graph. There are some concerns for this work:\n\n1.\tThe key idea of space conversion is to use the attention operator to generate a fixed number of features for each node. The anchor nodes features are serving as query vectors and produce the output by attending each node’s neighboring nodes. In this way, each node will have a fixed number of feature representations. However, the regular convolution cannot be applied due to lack of locality information. In the paragraph under Eq. (8), the authors claimed that this can be viewed as a regular 2-D plane. Since there is still no ordering information among these selected anchors, how can we view them as a regular 2-D plane. Similar argument presents in section 2.3.2. Currently, I cannot see a solid support for this argument, which directly leads the failure of motivation in this work.\n\n2.\tPermutation invariant issue exists in this work. We know that the permutation invariant is an important property especially for GNN methods. However, in Eq. (3), the clustering algorithm is used to determine the anchor vectors based on sampled nodes. This means different execution of the algorithm will lead to different results. The authors need to clarify this.\n\n3.\tThe authors perform extensive experimental studies on various datasets. However, I would recommend the authors to provide results on relatively larger datasets such as REDDIT-MULTI-12K. Also, some numbers reported in Table 2 are not consistent with those in the baseline papers such as GIN. The baseline models are quite outdated. There have been many works in this field such as StrctPool.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0AQxpPsbK0I", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In order to perform anisotropic convolution on graphs, this paper proposes to project a local neighborhood into a unified virtual space by introducing anchor nodes. A theoretical analysis is provided to show the expressive power of the proposed graph deformer operation on graph isomorphism test. Extensive experiments are performed on several node classification and graph classification datasets.\n\nPros:\n\n+ The proposed anchor-based anisotropic convolution provides an interesting view of architectural design on graphs;\n+  A good theoretical analysis in terms of the expressive power justifies the motivation of the proposed method.\n\nCons:\n\n- Transforming irregular structures into a regular domain is not new. There is a lack of comparison or discussion with methods in 3D domain such as Point-CNN (Li et al., 2018) and KPConv (Thomas et al., 2019). It seems the proposed method is very similar to KPConv but on graphs instead of point sets;\n-The discussion on the number of parameters is missing. In Figure 2, it shows that the best performance is achieved with more than 15 anchor nodes. This means graph deformer network (GDN) will use approximately 15x parameters compared to a regular GNN. It is unclear whether the performance gains come from the usage of more parameters or the proposed anisotropic convolution.\n\nMinor Comment:\n\n* The chosen datasets are relatively small. It would be great if more experiments can be conducted on the Open Graph Benchmark (Hu et al., 2020).\n\n\nReferences:\n* Yangyan Li, Rui Bu, Mingchao Sun, Baoquan Chen. “PointCNN: Convolution On X -Transformed Points”. arXiv preprint arXiv:1801.07791, 2018.\n* Thomas, Hugues, Charles R. Qi, Jean-Emmanuel Deschaud, Beatriz Marcotegui, François Goulette, and Leonidas J. Guibas. \"Kpconv: Flexible and deformable convolution for point clouds.\" In Proceedings of the IEEE International Conference on Computer Vision, pp. 6411-6420. 2019.\n* Hu, Weihua, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. \"Open graph benchmark: Datasets for machine learning on graphs.\" arXiv preprint arXiv:2005.00687 (2020).\n\nPost rebuttal Comments:\nThank the authors for the response. I keep my score as 5.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three of the reviewers are significantly concerned about this submission, while R1 is positive. Meanwhile, R1 is also concerned about some details in the paper, including space and time complexity etc. The authors provided detailed feedback to these comments, but R1 does not provide support to this work during discussions. Thus a reject is recommended.
Decision: Reject