Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification
Authors: Ting Chen
Song Bian
Yizhou Sun
Venue:  (2020)
Keywords: graph neural nets
graph classification
set function

Abstract: Graph Neural Nets (GNNs) have received increasing attentions, partially due to their superior performance in many node and graph classification tasks. However, there is a lack of understanding on what they are learning and how sophisticated the learned graph functions are.  In this work, we propose a dissection of GNNs on graph classification into two parts: 1) the graph filtering, where graph-based neighbor aggregations are performed, and 2) the set function, where a set of hidden node features are composed for prediction. To study the importance of both parts, we propose to linearize them separately. We first linearize the graph filtering function, resulting Graph Feature Network (GFN), which is a simple lightweight neural net defined on a \textit{set} of graph augmented features. Further linearization of GFN's set function results in Graph Linear Network (GLN), which is a linear function. Empirically we perform evaluations on common graph classification benchmarks. To our surprise, we find that, despite the simplification, GFN could match or exceed the best accuracies produced by recently proposed GNNs (with a fraction of computation cost), while GLN underperforms significantly. Our results demonstrate the importance of non-linear set function, and suggest that linear graph filtering with non-linear set function is an efficient and powerful scheme for modeling existing graph classification benchmarks.

Under review as a conference paper at ICLR 2020
ARE POWERFUL GRAPH NEURAL NETS NECESSARY? A DISSECTION ON GRAPH CLASSIFICATION
Anonymous authors
Paper under double-bling review
ABSTRACT
Graph Neural Nets (GNNs) have received increasing attentions, partially due to their superior performance in many node and graph classification tasks. However, there is a lack of understanding on what they are learning and how sophisticated the learned graph functions are. In this work, we propose a dissection of GNNs on graph classification into two parts: 1) the graph filtering, where graph-based neighbor aggregations are performed, and 2) the set function, where a set of hidden node features are composed for prediction. To study the importance of both parts, we propose to linearize them separately. We first linearize the graph filtering function, resulting Graph Feature Network (GFN), which is a simple lightweight neural net defined on a set of graph augmented features. Further linearization of GFN's set function results in Graph Linear Network (GLN), which is linear function. Empirically we perform evaluations on common graph classification benchmarks. To our surprise, we find that, despite the simplification, GFN could match or exceed the best accuracies produced by recently proposed GNNs (with a fraction of computation cost), while GLN underperforms significantly. Our results demonstrate the importance of non-linear set function, and suggest that linear graph filtering with non-linear set function is an efficient and powerful scheme for modeling existing graph classification benchmarks.
INTRODUCTION
Recent years have seen increasing attention to Graph Neural Nets (GNNs) (Scarselli et al. 2009
Li et al. 2015 Defferrard et al. 2016, Kipf and Welling, 2016), which have achieved superior performance in many graph tasks, such as node classification (Kipf and Welling 2016 Wu et al.) 2019) and graph classification (Simonovsky and Komodakis 2017 Xinyi and Chen 2019). Different from traditional neural networks that are defined regular structures such as sequences images, graphs provide a more general abstraction for structured data, which subsume regular structures as special cases. The power of GNNs is that they directly define learnable compositional function on (arbitrary) graphs, thus extending classic networks (e.g. CNNs, RNNs) to more irregular and general domains.
Despite their success, it is unclear what GNNs have learned, and how sophisticated the learned graph functions are. It is shown in (Zeiler and Fergus 2014) that traditional CNNs used in image recognition have learned complex hierarchical and compositional features, and that deep non-linear computation can be beneficial He al. (2016). Is this also the case when applying GNNs common graph problems? Recently, Wu et al. (2019) showed that, for common node classification benchmarks, non-linearity can be removed in GNNs without suffering much loss of performance. The resulting linear GNNs collapse into logistic regression on graph propagated features. This raises doubts on the necessity of complex GNNs, which require much more expensive computation, for node classification benchmarks. Here take a step further dissecting GNNs, and examine the necessity of complex GNN parts on more challenging graph classification benchmarks (Yanardag and Vishwanathan 2015
Zhang al. 2018a Xinyi and Chen 2019).
To better understand GNNs on graph classification, we dissect into two parts/stages: 1) the graph filtering part, where graph-based neighbor aggregations are performed, and 2) the set function part, where a set of hidden node features are composed for prediction. We aim to test the importance of both parts separately, and seek answers to the following questions. Do we need a sophisticated graph

---

Under review as a conference paper at ICLR 2020
filtering function for particular task or dataset? And if we have a powerful set function, is it enough to use a simple graph filtering function?
To answer these questions, propose to linearize both parts separately. We first lincarize graph filtering part, resulting Graph Feature Network (GFN); a simple lightweight neural net defined on set of graph augmented features. Unlike GNNs, which learn multi-step neighbor aggregation function on graphs (Dai et al., 2016 Gilmer et al.) 2017). the GFN only utilizes graphs in constructing its input features. It first augments nodes with graph structural and propagated features, and then learns a neural net directly on the set of nodes (i.e. a bag of graph pre-processed feature vectors), which make it more efficient. We then further linearize set function in GFN, and arrive at Graph Linear Network (GLN), which is linear function of augmented graph features.
Empirically, we perform evaluations on common graph classification benchmarks (Ynarddag and Vishwanathan 2015 Zhang et al.) 201 Sa Xinyi and Chen 2019). and find that GFN can match or exceed the best accuracies produced by recently proposed GNNs, at a fraction of the computation cost. GLN performs much poorly than both GFN and recent GNNs. This result casts doubts on the necessity of non-linear graph filtering, and suggests that the existing GNNs may not have learned more sophisticated graph functions than linear neighbor aggregation on these benchmarks. Furthermore, we find non-linear set function plays an important role, as its linearization can hurt performance significantly.
2 PRELIMINARIES
Graph classification problem. We use G = (V. F) E G to denote a graph, where V is set of vertices/nodes, and F. is a set of edges. We further denote attributed graph as Gx (G. X) 9x, where X E 12xd are node attributes with n = [V]. It is assumed that each attributed graph is associated with some label y E V, where is set of pre-defined categories. The goal in graph classification problem is to learn mapping function f 9x - y, such that we can predict the target class for unseen graphs accurately. Many real world problems can be formulated as graph classification problems, such as social and biological graph classification Yanardag and Vishwanathan (2015) Kipf and Welling (016)).
Graph neural networks. Graph Neural Networks (GNNs) define functions the space of at- tributed graph Gx. Typically, the graph function, GN, learns a multiple-step transformation of the original atrributes/signals for final node level or graph level prediction. In each of the step f, new node presentation, h is learned. Initially, h1()) is initialized with the node attribute vector, and during each subsequent step, neighbor aggregation function is applied to generate the new node representation. More specifically, common neighbor aggregation functions for the v-th node take the following form:
(n
where ((v) is a set of neighboring nodes of node v. To instantiate this neighbor aggregation function, (Kipf and Welling 2016) proposes the Graph Convolutional Network (GCN) aggregation scheme as follows.
h (1+1) =
Áno (W (N)
Σ
(2)
where W(t) Raxd' is the learnable transformation weight. À = D-1 ( 11/2 is the normalized adjacency matrix with c as a constant (c in Kipf and Welling (0166) and D. Σ, As + c. (.) is non -inerr activation function, such as ReLU. This transformation can also be written as ((++1) ar (AH(0 where (()) E Ra the hidden states of all nodes f-th step.
More sophisticated neighbor aggregation schemes also proposed, such GraphSAGE (Hamilton et al. 2017) which allows pooling and recurrent aggregation over neighboring nodes. Most recently, in Graph Isomorphism Network (GIN) (Xu al. 2019). more powerful aggregation function is
2

---

Under review as a conference paper at ICLR 2020
proposed follows.
1 = MLP(0) M ((1+c0)) ng)))))))))
Σ
h((-1)
(3)
uEN(e)
where MLP abbreviates for multi-layer perceptrons and e can either be zero a learnable parameter.
Finally, in order to generate graph level representation hag a readout function is used, which generally takes the following form:
hG = T =(((
(4)
This can be instantiated by global sum pooling, i.e. ha - N followed by fully connected layers to generate the categorical or numerical output.
3 APPROACH
3.1 GRAPH FEATURE NETWORK
Motivated by the question that, with a powerful graph readout function, whether simplify the sophisticated multi-step neighbor aggregation functions (such as Eq. 2 and 3}. Therefore we propose Graph Feature Network (GFN); neural set function defined on set of graph augmented features.
Graph augmented features. GFN, we replace the sophisticated neighbor aggregation functions (such Eq. [ and 3) with graph augmented features based on Gx. Here we consider two categories as follows: 1) graph structura/topologicall features, which are related to the intrinsic graph structure, such as node degrees, or node centrality scores" but do not rely node attributes; 2) graph propagated features, which leverage the graph as a medium to propagate node attributes. The graph augmented features X can be
the output of feature extraction function defined the attributed graph, i.e. X = y(G X), and Eq. 55 beloo gives a specific form, which combine node degree features and multi-scale graph propagated features as follows:
x = >C,
d, X, X, A2x
AK X
(5)
where d E Rax1 is the degree vector for all nodes, and Á again the normalized adjacency matrix (A D- (A ef)D-1/3 but other designs of propagation operator are possible (Klicpera et 2019
Features separated by comma are concatenated to form X
Neural set function. To build a powerful graph readout function based on graph augmented features X we use neural set function. The neural set function discards the graph structures and learns purely based on the set of augmented node features. Motivated by the general form of a permutation- invariant set function shown in Zaheer et al. (2017), , define neural set function for GFN as follows:
Σ Φ X xx)) NEV
X)
Both o(-) and p(-) are parameterized by neural networks. Concretely, we parameterize the function <(-) as a multi-layer perceptron (MLP), i.c. d(x) = = (x" w()). (U)) (T)) Note that a single layer of d(-) resembles a graph convolution layer H(++1) (AHH)(()) with the normalized adjacency matrix À replaced by identity matrix (a.k.a. 1 x convolution). As for the function p(-), we parameterize with another MLP (i.e. fully connected layers in this case).
We only use node degree this work it very efficient calculate during both training and inference.
3

---

Under review as a conference paper at ICLR 2020
Computation efficiency. GFN provides way approximate GNN with less computation over- heads, especially during the training process. Since the graph augmented features can be pre-computed before training starts, the graph structures are not involved in the iterative training process. This brings the following advantages. First, since there is no neighbor aggregation step in GFN, it reduces computational complexity. To see this, one can compare single layer feature transformation function in GFN, i.e. o o//W), against the neighbor aggregation function in GCN, i.e. a (AHW). Secondly, since graph augmented features of different scales are readily available from the input layer, GFN can leverage them much earlier, thus may require fewer transformation layers. Lastly, it also eases the implementation related overhead, since the neighbor aggregation operation in graphs are typically implemented by sparse matrix operations.
Graph Linear Network. When we use linear set function instead of the generic one used in Eq. we arrive graph linear network, which can be expressed as follows.
GLN(G, X) = a W Σ VEV
Where W is weight matrix, and (-) is softmax function produce class probability.
3.2 FROM GNN TO GFN AND GLN: A DISSECTION OF GNNS
To better understand GNNs on graph classification, we propose a formal dissection/decomposiiion of GNNs into two parts/stages: the graph filtering part and the set function part. As we shall see shortly, the simplification of the graph filtering part allows us to derive GFN from GNN, and also be able to assess the importance of the two GNN parts separately.
To make concepts more clear, we first give formal definitions of the two GNN parts in the dissection.
Definition 1. (Graph filtering) A graph filtering function, Y= Fo(() performs a transformation of input signals based on the graph G, which takes a set of signals X Raxd and outputs another set of filtered signals Y E mxd"'"
Graph filtering in most existing GNNs consists of multi-step neighbor aggregation operations, i.e. multiple steps of Eq. [ For example, in GCN Kipf and Welling (2016), the multi-step neighbor aggregation can be expressed as HT)) o (Aoo ([A((...((AXX W(T)).
Definition 2. (Set function) set function, y = T(Y), takes a set of vectors Y E Rmxdd where their order does not matter, and outputs task specific prediction e
The graph readout function in Eq. 4 is set function, which enables the graph level prediction that is permutation invariant w.r.t. nodes in the graph. Although a typical readout function is simply global pooling (Xu et al., 2019), the set function can be as complicated as Eq. 6
Claim 1. A GNN that is mapping of 9x + 3 can be decomposed into graph filtering function followed by a set function, i.e. GNN(G, = T o FX).).
This claim is obvious for the neighbor aggregation framework defined by Eq. a where most existing GNN variants such as GCN, GraphSAGE and GIN follow. This claim also general, even for unforeseen GNN variants that do not explicitly follow this framework 2
We aim to assess the importance of two GNN parts separately. However, is worth pointing out that the above decomposition is not unique in general, and the functionality of the two parts can overlap: the graph filtering part has fully transformed graph features, then a simple set function may be used for prediction. This makes it challenging to answer the question: do we need sophisticated graph filtering part for a particular task or dataset, especially when a powerful set function is used? To better disentangle these two parts and study their importance more independently, similar to Wu et al. (2019), we propose to simplify the graph filtering part by linearizing it.
Definition 3. (Linear graph filtering) We say graph filtering function Fx( is linear w.r.t. X iff it can be expressed as (x) = [(G, X)0, where T(G, X) is a linear map of X, and 0 is the only learnable parameter.
We can absorb the set function T into Fa- That is, let the output Y =FF(-) be final logits for pre-defined classes and set T(-) softmax function with zero temperature, i.c. exp(#/r)/2 with T 0
4

---

Under review as a conference paper at ICLR 2020
Intuitively, one construct linear graph filtering by removing the non-linear operations from graph filtering part in existing GNNs, such as non-linear activation function a(-) in Eq. 2 3 By doing so, the graph filtering becomes linear w.r.t. X. thus multi-layer weights collapse into single linear transformation, described by 0. More concretely, let us consider a linearized GCN Kipf and Welling 2016), its K-th layer can be written as H(K) = A ( k=1 W()), (K))) and we can rewrite the weights with = | W(k),
The linearization of graph filtering part enables us disentangle graph filtering and the set function more thoroughly: the graph filtering part mainly constructs graph augmented features (by setting X), = I'G X)), and the set function learns compose them for the graph-level prediction. This leads to the proposed GFN. In other words, GNNs with linear graph filtering part can be expressed as GFN with appropriate graph augmented features. This is shown more formally in the following proposition [
Proposition Let GNN X) be a mapping of gx - y that has a linear graph filtering part, i.c. Fx(X) = I(G, X)O, then we have GNN (G, X) = GFN(G, where (G, = T(G, X).
The proof can be found in the appendix. Noted that a GNN with a linear graph filtering can be seen as GFN, but the reverse may not be true. General GFN can have non-linear graph filtering. e.g. when the feature extraction function (G, X) is not a linear map of X (Eq. 5 is a linear map of X).
Why GFN? GFN can also help us understand the functions that GNNs learned on current bench- marks. First, by comparing GNN with linear graph filtering (i.e. GFN) against standard GNN with non-linear graph filtering, can assess the importance of non-linear graph filtering part. Secondly, by comparing GFN with linear set function (i.e. GLN) against GFN with non-linear set function, we assess the importance of non-linear set function.
Beyond as a tool to study GNN parts, GFN is also more efficient than GNN counterpart, which makes it fast approximation. Furthermore, GFNs can be very powerful framework without restriction on the feature extraction function 7(, X) and the exact forms of the set function. The potential expressiveness of GFN is demonstrated by the following proposition.
Proposition 2. For any GNN F defined in Gx, there exists graph to set mapping M: G S where S is a set space, and set function T that approximates F to arbitrary precision, i.e. VG e 9x, F(G) = T(M(G)).
The proof is provided in the appendix. We want to provide an intuitive interpretation here. There exists some way(s) that we can encode any graph into set, and learn a generic set function on it. As long as the set contains the graph information, powerful set function can learn to integrate it in a flexible way. So well constructed GFN can be as powerful as, if not more powerful than, the most powerful GNNs. This shows the potential of the GFN framework in modeling arbitrary graph data.
EXPERIMENTS
4.1 DATASETS AND SETTINGS
The main datasets we consider are commonly used graph classification benchmarks YYa nardag and Vishwanathan 2015 Xinyi and Chen 2019 Xu et al. 2019). The graphs in the collection can be categorized into two categories: (1) biological graphs, including MUTAG, NCII, PROTEINS, D&D, ENZYMES; and (2) social graphs, including COLLAB, IMDB-Binary (IMDB-B), IMDB- Multi (IMDB-M), Reddit- that the social graphs have node attributes, while the biological graphs come with categorical node attributes. The detailed statistics can be found in the appendix.
Datasets.
(RE-M5K), Reddit-Mulle Multi- 12K (RE-M12K). It is worth noting
Baselines. We compare with two families of baselines. The first family of baselines are kernel-based, namely the Seisffeiler-Lhmmar subtree kernel (WL) (Shervashidze et al. [001]). Deep Graph Kernel (DGK) Yanardag and Vishwanathan 2015) and AWE (Ivaoov and Burnaev] 2018) that incorporate hernel-based methods with learning- based approach to learn embeddings. The second family of baselines are GNN-based models, which include recently proposed PATCHY-SAN (PSCN) (Niepert
5

---

Under review as a conference paper at ICLR 2020
Table 1: Test accuracies (%) for biological graphs. The best results per dataset and in average are highlighted. means the results are not available for a particular dataset.
Algorithm
MUTAG
NCI1
PROTEINS
D&D
ENZYMES
Average
WL 82.05-10.36
82.19
74.68:10.49
1.338
52.22
74.18
AWE
87.87-99.76
71.51
35.77-45.93
DGK
87.44=2.72
80.31=0.46
75.68
73.50=11011
53,43+0991
74.07
PSCN
88.95-+4.37
16.34+1.68
75.00++2.51
76.27+22.64
DGCNN
85.83+1.666
74.44+0.47
75.54+00.94
79.37+0094
51.00+7.29
73.24
CapsGNN
86.67=6.88
78.35=1.55
76.28:13.63
75.38-4.117
54.67=:..77
74.27
GIN
89.40=1..60
12.70=1..70
76.20-12.80
GCN
87.20-15.11
83.65+1.66
75.65-:3.24
79.12++3.07
66.50+6.91
78.42
GLN
82.15
68.61
75.65:14.43
76.75
43.83.15.16
69.54
GFN
90.84_7.22
82.77
76.46.14.06
78.78113449
70.1715.58
79.80
GFN-light
89.89
81.4311.65
77.44.3.777
78.62.15.43
69.50-17.37
79.38
Table 2: Test accuracies (%) for social graphs. The best results per dataset and in average are highlighted. means the results are not available for a particular dataset.
Algorithm
COLLAB
IMDB-B
IMDB-M
RE-MSK
RE-MI2K
Average
WL 19.72-+1.77
73.40+4..3
49.33-14.75
29.44
38.1841.300
57.87
AWE
1..9
74.45--5.83
51.54
50.46+
39.20+t2.09
57.92
DGK
73.09-+0.25
66.96+00.56
4..55
41.274+0.18
32.22++0.10
51.62
PSCN
72.60-+2.15
71.00+22.29
45.23-42.84
49.10-+0.70
41,32-H0.42
55.85
DGCNN
73.76++0.49
70.03++0.86
47.83++0.85
48.70-+4.54
CapsGNN
79.62-10.91
43.10.44.83
50.27:12.55
52.88
46.62.11900
60.50
GIN
1.90
75.10.1..10
52.30
57.50
GCN
11.7
73.30+:5.29
51.20:5..13
56.81+2.37
49.31
62,47
GLN
75.72.12.51
73.1011.118
50.40-15.61
52.97
39.84
58.41
GFN
81.50-12.42
73.00.14.35
51.80
57.59
49.43.11.36
62.66
GFN-light
11.33
73.00.14.29
51.20
57.11
49.75.1..19
62.48
et al. 2016). Deep Graph CNN (DGCNN) (Zhang et al. 2018a). CapsGNN (inyyi and Chen 2019
and GIN (Xu al. 2019).
For the above baselines, we use their accuracies reported in the original papers, following the same evaluation setting as in (Xu al. 2019). Architecture and hyper-parameters can make difference, so to enable a better controlled comparison between GFN and GNN, we also implement Graph Convolutional Networks (GCN) from (Kipf and Welling 2016). More specifically, our GCN model contains dense feature transformation layer, i.e. H (XW (W())), followed three GCN layers, i.c. if++1) o (t
We also vary the number of GCN layers in our ablation study. To enable graph level prediction, we add a global sum pooling, followed by two fully-con calle-connected layers that produce categorical probability over pre-defined categories.
Model configurations. For the proposed GFN, we mirror our GCN model configuration to allow direct comparison. Therefore, we use the same architecture, parameterization and training setup, but replace the GCN layer with feature transformation layers (totaling four such layers). Converting GCN layer feature transformation layer equivalent to setting / in GCN layers. We also construct faster GFN, namely "GFN-light", that contains only single feature transformation layer, which can further reduce the training time while maintaining similar performance.
For both our GCN and GFN, utilize ReLU activation and batch normalization (loffe and Szegedy 2015), and fix the hidden dimensionality to 128. No regularization is applied. Furthermore we use batch size of 128, fixed learning rate of 0.001, and the Adam optimizer (Kingma and Ba] 2014). GLN follows the same setting as GFN, but contains no feature transform layer. only has the global sum pooling of graph features followed by single fully connected layer. To compare with existing

---

Under review as a conference paper at ICLR 2020
work, follow (Xinyi and Chen 2019; Xu et al. 2019) and perform 10-fold cross validation. We run the model for 100 epochs, and select the epoch in the same way as Xu et al. (2019), i.., a single epoch with the best cross- voss-validation accuracy averaged over the 10 folds is selected. We report the average and standard deviation of test accuracies at the selected epoch over 10 folds.
In terms of input node features for GFN and GLN, by default, use both degree and multi-scale propagated features (up K 3), that is (d. X, A' X, A²x, X. We turn discrete features into one-hot vectors, and also discretize degree features into one-hot vectors, as suggested in Fey and Lenssen (201)). We set X = for the social graphs we consider as there are no node attributes. By default, we also augment node features in our GCN with an extra node degree feature (to counter that the normalized adjacency matrix may lose the degree information). Other graph augmented features are also studied for GCN (which has minor effects). All experiments are run Nvidia GTX 1080 Ti GPU.
4.2 PERFORMANCE COMPARISON BETWEEN GLN, GFN AND EXISTING GNN VARIANTS
Table D and 2 show the results of different methods in both biological and social datasets. It is worth noting that in both datasets, GFN achieves similar performances with our GCN, and match or exceed existing state-of-the-ar results on multiple datasets, while GLN performs worse most of the datasets. This result suggests the importance of non-linean set function, while casting doubt the necessity of non-linear graph filtering for these benchmarks.
05-
0.50
0.75
04-
0.40
0.-
8.08
04
GChprar)
Gchboa
0:5-
0.5
045
02-
Spach
Fyeit
(a) NCT1
(b) IMDB- MIDB-BINARY
REDDIT-MULLTT12K
Figure 1: Training and test performance versus training epoch.
Figure 1 shows training/test curves for both GCN and GFN. We observe that GCN usually perform better than GFN during the training, but their test performances are mostly similar (sometimes GFN is better as training continues). This concludes that GFN works well not because it is casier to optimize.
4.3 TRAINING TIME COMPARISONS BETWEEN GFNS AND GCNS
Since GFN's performance is on par with GCN's, further compare the training time of our GCN and the proposed GFNs. Figure 2 shows that a significant speedup (from 1.4x to 6.7x x as fast) by utilizing GFN compared to GCN, especially for datasets with denser edges such as the COLLAB dataset. Also since our GFN can work with fewer transformation layers, GFN-light can achieve better speedup by reducing the number of transformation layers. Note that our GCN is already very efficient as it is built on a highly optimized framework Fey and Lenssen (2019).
4.4 ABLATIONS
Node features. To better understand the impact of features, we test both models with different input node features. Table shows that 1) graph features very important for both GFN and GCN, 2) the node degree feature is surprisingly important, and multi-scale features can further improve on that, and 3) even with multi-scale features, GCN still performs similarly to GFN, which further suggests that linear graph filtering is enough. More detailed results (per dataset) can be found in the appendix.
Architecture depth. We vary the number of convolutional layers (with two FC-layers after sum pooling kept the same). Table[[shows that 1) GCN benefits from multiple grpah convolutional layers with significant diminishing return, GFN with single feature transformation layer works pretty
7

---

Under review as a conference paper at ICLR 2020
400
Time per fold (sec)
Model
GFN-light
1.64
300
GPN
GCN
100
4.2X
2.2X
1.0%.
2.55,
2.0X
2.7X
1.4X
PROTEINS
IMDB-8
IMDB-M
NC11
COLLAB
RE-M5K
Datasets
Figure Training time comparisons. The annotation, e.g. 1.0x, denotes speedup compared to GCN.
Table Accuracies (%) under various augmented features. Averaged results over multiple datasets are shown here. 1 X is abbreviated for A X, A²X, A X, and default node feature X is always used (if available) but not displayed reduce clutter. Best results per row/block are highlighted.
Graphs
Model
None
A X
1
A 1,2,3
d, d
d, A
d, 4.233x
GCN
78.52
78.51
78.23
78.24
78.68
79.10
79.26
79.69
Bío.
GFN
76.27
77.84
78.78
79.09
79.17
78.71
79.21
79.13
GCN
34.02
62.35
59.20
60.39
60.28 60.09
62.45 62.47
62.71
62.77
Soical
GFN
30.45
60.79
58.04
59.83
62.63
62.60
Table 4: Accuracies (%) under different number of Conv, layers.
3
GCN
77.17
79.38
78.86
78.21 78.75
Bio.
GFN
79.59
79.77
79.78
78.99
78.14
GCN
60.69
62.12
62.37
62.70
62.46
Soical
GFN
62.70
62.88
62.81
62.80
62.60
well already. likely due to the availability of multi-scale input node features, which otherwise require multiple GCN layers to obtain.
Visualization. We also provide visualization of random and misclassified samples from the tested graph datasets the appendix[] []] We could not clearly distinguish graphs from different classes easily based on their appearance, suggesting that both GFN and GCN capturing underlying non-trivial features.
DISCUSSION
In this work, we conduct dissection of GNNs on common graph classification benchmarks. We first decompose GNNs into two parts, and linearize the graph filtering part resulting GFN. We then further linearize the function of GFN resulting GLN. our extensive experiments, can match exceed the best results by recently proposed GNNs, with a fraction of computation cost. The linearization of graph filtering (i.e. GFN) has little impact on performance, while linearization of both graph filtering and set function (i.e. GLN) leads to worse performance.
find GFN
Since GCN usually achieve better training accuracies while not better test accuracies, we conjecture that the linear graph filtering may be good inductive bias for tested datasets, though this is speculative and requires more future investigations. Another possibility is that complexity of current graph classification benchmarks is limited, that linear graph filtering is enough, thus moving datasets or problems with information that is more structurally complicated could require sophisticated non-linear graph filtering.
We also observe the potential of GFN, which leverages generic set function to model graphs. In the future, would like to build upon the powerful general GFN framework for structured data.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Hanjun Dai, Bo Dai, and Song. Discriminative embeddings of latent variable models for structured data. In International conference on machine learning, 2016.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, 2016.
Simon S. Du Kangcheng Hou, Barnabás Póczos, Ruslan Salakhutdinov, Ruosong Wang. and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. ArXiv, abs//1905.13192 2019.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with Py PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference on computer vision, 2016.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint 100X:://00200367,, 2015.
Sergey Ivanov and Evgeny Burnaev. Anonymous walk emheddings. arXiv preprint a80i: 1921, 2018.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 06096669990072. 2016.
Johannes Kliepera, Aleksandar Bojchevski, and Stephan Günnemann. Combining neural networks with personalized pagerank for classification on graphs. In International Conference Learning Representations, 2019. URL
2A9mm
Yujia Li, Daniel Tarlow, Mare Brockschmidr, and Richard Zemel. Gated graph sequence neural networks, arXiv preprint a5Xiv:151 151,0559, 2015.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov, Learning convolutional neural networks for graphs. In International conference machine learning. 2016.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lhhman graph kernels. Journal of Machine Learning Research, 2011.
Martin Simonovsky and Nikos Komodakis. Dynamic edge-conditioned filters in convolutional neural networks on graphs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2017.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. arXiv preprint arXiv: 1902.07133, 2019.
Zhang Xinyi and Lihui Chen. Capsule graph neural network. In International Conference on Learning Representations, 2019. URL URL.tttss://ppeeeeeee
net wttettfooummiio Btt.rummpmdddyyyBBReeee
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2019. URI. hhtp:httt////t httthhttss:://oeeee pttttps://pperreiiee. net./
Forum?id-ryee A5Km
Pinar Yanardag and SVN Vishwanathan. Deep graph kemels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015.
Manzil Zaheer, Satwik Kottur, Siamak Ravanhakhsh, Barnhhas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in neural information processing systems, 2017.

---

Under review as a conference paper at ICLR 2020
Matthew D Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In European conference on computer vision, 2014.
Muhan Zhang. Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirty- Seery---econdd AAAI Conference on Artificial Intelligence, 2018a.
Zhen Zhang, Mianzhi Wang, Yijian Xiang, Yan Huang. and Arye Nehorai. Retgk: Graph kemells based return probabilities random walks, In Advances in Neural Information Processing Systems, pages 3964 3974, 2018b.
10

---

Under review as a conference paper at ICLR 2020
A
COMPARISONS OF DIFFERENT LINEARIZATIONS
Table 5: Comparisons of different linearizations.
Method
Graph filtering
Set function
Efficiency
Performance
GLN
Linear
Linear
High
Low
GFN
Linear
Non-linear
High
High
GCN
Non-lincar
Lincar/Non-iiner
Low
High
Table 5 summarizes the comparisons between GCN and its linearized variants. The efficiency and performance concluded from our experiments on graph classification benchmarks. Noted that GNN with a linear graph filtering can be seen as GFN, but the reverse may not be true. General GFN can have non-linear graph filtering, e.g. when the feature extraction function y(G, X) is not linear map of X. Thus we use GFNlin in Table to denote such subtle difference.
B PROOFS
Here we provide the proof for Proposition |
Proof. According to claim 1 and definition 3 a GNN(G, X) with a linear graph filtering part, denoted by GNN (G, (G,X). X), can be written as follows.
GNN
(NNN"((G,)) (G, = To = -
=
where 0 is absorbed into the set function T.).. According to GFN's definition in Eq. 6 and general set function result from Zaheer al. (2017). we have
GFN X) = T = (?(G,
By setting 7G, [(G, X), we arrive at GNN (G, X) GFN
Here we provide the proof for Proposition 2
Proof. We show the existence of the mapping T by constructing it as follows. First, we assign unique ID to each the node, then we add its ID and neighbors' IDs in the end of node features. If there are edges with features, we also treat them nodes and apply the same above procedure. This procedure results in a set nodes with features that preserve the same original information (since
reconstruct the original graph).
We now show the existence of a set function that can mimic any graph functions operated on G, again, by constructing specific one. Since the set of nodes preserve the whole graph information, the set function can first reconstruct the graph by decoding the node's feature vectors. At every computation step, the set function find neighbors of each node in the set, and compute the aggregation function in exactly the same way as the graph function would do with the neighbors of a node. This procedure is repeated until the graph function produces its output.
Hence, the above constructed example proves the existence of M and a set function T such that VG E Cx.F(GG feasible but likely not optimal. A better solution is to have a set function that learns to adaptively leverage the graph structure as well as node attributes.
T(M( We also note that the specially constructed examples above are
C DETAILED STATISTICS OF DATASETS
Detailed statistics of the biological and social graph datasets listed in Table and respectively.
11

---

Under review as a conference paper at ICLR 2020
Table 6: Data statistics of Biological dataset
Dataset
MUTAG
NCT1
PROTEINS
D&D
ENZYMES
# graphs
188
4110
1113
1178
600
# classes
2
2
6
# features
3
Avg nodes
17.93
29.87
39.06
284.32
32.63
Avg edges
19.79
32.30
72.82
715.66
62.14
Table 7: Data statistics of Social dataset
Dataset
COLLAB
IMDB-B
IMDB-M
RE-MSK
RE-12K
# graphs
5000
1000
1500
4999
11929
# classes
3
11
# features
1
1
Avg nodes
74.49 2457.78
19.77
13.00
508.52
391.41
Avg # edges
96.53
65.94
594.87
456.89
D EXPERIMENTS ON GRAPH CONSTRUCTED FROM IMAGES (MNIST)
addition to the common graph benchmarks, we also consider image classification on MNIST where pixels are treated as nodes and eight nearest neighbors in the grid, with extra self-loop, are used to construct the graph.
For MNIST, train and evaluate the given train/test split. Additionally, since MNIST benefits more from deeper GCN layers, we parameterize our GCN model using residual network (He et al. 2016) with multiple GCN blocks, the number of blocks are kept the same for GCN and GFN, and varied according to the size of total receptive field. GFN utilizes the same multi-scale features as in Eq.
We report the accuracies under different total receptive field sizes (i.e. the number of hops a pixel could condition its computation on). Results in Table 88 show that, in all three different receptive field sizes, GCN with non-linear neighbor aggregation outperforms GFN with linear graph propagated features. This indicates that non-linear graph filtering is essential for performing well in this dataset. Note that our results are not directly comparable to traditional CNN's, as our GNN does not distinguish the neighbor pixel direction its parameterization, and global sum pooling of pixels does not leverage spatial information. For context, when using coordinates as features both GCN and GFN achieve nearly 99% accuracy.
Table 8: Test accuracies (%) on MNIST graphs.
Receptive GCN
size
3
91.47
87.73
5
95.16
91.83
7
96.14
92.68
This test on graphs constructed from image dataset (MNIST), the obser- vation that similarly configured GCN outperforms GFN by large margin, indicates the importance of non-linear graph filtering for this type of graph dataset.
E DETAILED PERFORMANCES WITH DIFFERENT FEATURES
Table show the performances under different graph features for GNNs and GFNs. It is evident that both model benefit significantly from graph features, especially GFNs.
F DETAILED PERFORMANCES WITH DIFFERENT ARCHITECTURE DEPTHS
Table 10 shows performance per datasets under different number of layers.
12

---

Under review as a conference paper at ICLR 2020
Table 9: Accuracies (%) under various augmented features.
A abbreviated for A' "x,A4 A and default node feature X is always used (if available) but not displayed to reduce clutter.
Datasct
Model
None
d
X
A
d, A
d, A d 4,A2.
GCN GFN
83.48
87.09
83.35
83.43
85.56
87.18
87.62
88.73
MUTAG
82.21
89.31
87.59
87.17
86.62
89.42
89.28
88.26
GCN
80.15
83.24
82.62
83.11
82.60
83.38
83.63
83.50
NCII
GFN
70.83
75.50
80.95
82.80
83.50
81.92
82.41
82.84
GCN
74,49
76.28
74.48
75.47
76.54
77.09
76.91
77.45
PROTEINS
GFN
74.93
76.63
76.01
75.74
76.64
76.37
76.46
77.09
GCN
79.29
78.78
78.70
77.67
78.18
78.35
78.79
79.12
DD
GFN
78.70
77.77
77.85
77.43
78.28
77.34
76.92
78.11
GCN
75.17
67.17
72.00
71,50
70.50
69.50
69.33
69.67
ENZYMES
GFN
74.67
70.00
71.50
72.33
70.83
68.50
71.00
69.33
GCN
39.69
82.14
76.62
76.98
77.22
82.14
82.24
82.20
COLLAB
GFN
31.57
80.36
76.40
77.08
77.04
81.28
81.62
81.26
GCN
51.00
73.00
70.30
71.10
72.20
73.50
73.80
73.70
IMDB-B
GFN
50.00
73.30
72.30
71.30
71.70
74.40
73.20
73.90
GCN
35.00
50.33
45.53
46.33
45.73
50.20
50.73
51.00
IMDB-M
GFN
33.33
51.20
46.80
46.67
46.47
51.93
51.93
51.73
GCN
28.48
56.99
54.97
57.43
56.55
56.67
56.75
57.01
RE-MSK
GFN
20.00
54.23
51.11
55.85
56.35
56.45
57.01
56.71
GCN
15.93
49.28
48.58
50.11
49.71
49.73
50.03
49.92
RE-MI2K
GFN
17.33
44.86
43.61
48.25
48.87
48.31
49.37
49.39
Table 10: Accuracies (%) under different number of Conv. layers. Flat denotes the collapsed GFN into a linear model (i.e. linearizing the set function).
Dataset
Method
Flat
3
4
5
GCN
88.32
90.89
87.65
88.31
MUTAG
GFN
82.85
90.34
89.39
88.18
87.59
87.18
GCN
75.62
81.41
83.04
82.94
83.31
NCII
GFN
68.61
81.77
83.09
82.85
82.80
83.09
GCN
76.91
76.99
77.00
76.19
75.29
PROTEINS
GFN
75.65
77.71
77.09
77.17
76.28
75.92
GCN 76.75
77.34
77.93
78.95
79.46
78.77
DD
GFN
78.44
78.78
79.04
78.45
76.32
GCN
67.67
69.67
67.67
66.83
66.00
ENZYMES
GFN
43.83
69.67
70.50
71.67
69.83
68. 17
GCN
80.36
81.86
81.40
81.90
81.78
COLLAB
GFN
75.72
81.24
82.04
81.36
82.18
81.72
GCN
72.60
72.30
73.30
73.80
73.40
IMDB-B
GPN
73.10
73.50
73.30
74.00
73.90
73.60
GCN 50.40
51.53
51.07
50.87
51.53
50.60
IMDB-M
GEN
51.73
52.13
51.93
51.87
51.40
GCN $2.97
54.05
56.49
56.83
56.73
56.89
RE-M5K
GFN
57.45
57.13
57.21
56.61
$7.03
GCN
44,91
48.87
49.45
49.52
49.61
RE-M12K
GEN
39.84
49.58
49.82
49.54
49.44
49.27
13

---

Under review as a conference paper at ICLR 2020
1.2
0.4
0.-
04-
04
Grnaber
02-
0.8
04
80
bauch
(a) COLLAB
(b) DD
(c) ENZYMES
GORDWNY
0.-
G2N224)
02-
Spach
Spach
(d) MUDT-MULTI
(e) MUTAG
(I) PROTEINS
0.-
0.-
67-
04
04-
0.3
GON
62
REDDIT-MULTI-SK
Figure 3: Training and test performance versus training epoch.
G MORE CURVES ON TRAINING TEST PERFORMANCE VS EPOCH
Figure 3 shows more training/test curves for both GCN and GFN. The conclusion is consistent with main text that GFN works well not because it is easier to optimize.
H COMPARISONS TO RETGK AND GNTK
Here we further compare our results to two recent work, namely RetGK (Zhang et al. (018b) and GNTK (Du al. 2019). RetGK proposes family of graph kernels based on return probabilities of random walks, with different instantiations: RetGK,, RetGK,,, and ReIGK,((M)) In their experiments, node attribute are divided into three types: non-attribute, discrete attributes, and continues attributes, and we compare to their reported results. GNTK leverages the connection between infinitely wide networks and kernels to construct an infinitely wide GNN using graph kernels. We also compare to their reported results.
is worth mentioning that these graph kernel based methods are typically quadratic the number of graphs and nodes, which makes them hard to scale to large datasets. The proposed GFN has linear complexity and even faster than typical GNNs, which makes our method really scalable to larger datasets.
The results on biological and social graphs are shown Table 11 and 12 respectively. We found that overall, despite the methodology differences, GFN still performs par with these methods averaged over compared datasets (with performance differences on some datasets but they are mostly within one standard deviation).
14

---

Under review as a conference paper at ICLR 2020
Table 11: Test accuracies (%) for biological graphs. The best results per dataset and average are highlighted. means the results are not available for a particular dataset.
Algorithm
MUTAG
NCI1
PROTEINS
D&D
ENZYMES
Average
(eiSK)(Dis)
90.3
84.5.102 83.510.2
75.810..
81.6-0.3
60.4.10.8
78.52 77.78
(eiSK;;(Dis)
1.0
75.2
81.0.0.5
59.1
RetGK,(Con)
76.2
70.0=
ReIGKr;(Con)
75.9=0.4
70.7=0.9
RetGK,(Con&Dis)
78.0
72.2-10.8
(eonKi:(Com&Dis))
77.3+-0.5
70.6+0..7
GNTK
90.00+
1.
75.6++4.2
GCN
87.2015.111
83.6511.69
75.65:13.24
79.12:1..07
66.50:6.91
78.42
GLN
82.85=12.15
68.61+2.31
75.65+44.43
76.75=55.00
43.83++5.16
69.54
GFN
90.84+7.22
82.77
76.46=4.06
70.17=5.58 78.62+5543
78.78=3.49
79.80
GFN-light
89.89+7.14
81.43+1.66
77.44+3.77
69.50=7.37
79.38
Table 12: Test accuracies (%) for social graphs. The best results dataset and in average are highlighted. means the results are available for a particular dataset.
Algorithm
COLLAB
IMDB-B
IMDB-M
RE-M5K
RE-M12K
Average
RetGK, (Non)
81.0++0.3
71.9+110
47.7++0.3
56.1+0.55
48.7+-0,2
61.08
RetGKrr(Non)
80.6++0.3
72.3+0.6
48.7+00.6
55,3++0.3
47.1+
60.8
(MC)(on)))
73.6110.3
71.0110.6
46.711.66
54.2:10.3
45,910.2
58.28
GNTK
83.611.0
76,9113.6
52.814.66
GCN
81.72.1..64
73.30
51.20115.13
56.81
49.31
62.47
GLN
75.72:12.51
73.10.13.18
50.40.15.61
52.97
39.84-10.95
58.41
GFN
81.50
73.00.14.35
51.80
57.5911.440
49.43.11.36
62.66
GFN-light
81.34
73.00+44.29
51.20=t5.71
17.11
49.75
62.48
I VARYING DATASET SIZE
To test the impact of dataset size, we take the largest graph dataset, RE-M12K, which has 1 11929 graphs. And then construct nine new datasets by randomly sampling the original dataset with different ratios, ranging from 10% to 100% of all graphs. We compute both training and test accuracies over 10 fold cross-validation for both our GFN and GCN, For each dataset size (I0 fold cross validation), we consider two ways to extract performance: (1) selecting best epoch averaged over 10 fold cross validation, or (2) selecting the last epoch (i.e. the 100-th epoch).
Figure shows the results. We can see that as data size increases, 1) it is harder for both models to overfit (training acccuracy decreases), but seems GCN still overfits more if trained longer (to the last epoch); 2) at the best epoch, both models performance almost identical, without significant gaps between them.
GRAPH VISUALIZATIONS
Figure and 7 show the random and mis-classified samples for MUTAG, PROTEINS, IMDB-B, and IMDB-M. respectively. In general, it is difficult to find the patterns of each class by visually examining the graphs. And the mis-classified patterns are not visually distinguishable, except for IMDB-B/IMDB-.. M datasets where there are some graphs seem ambiguous.
15

---

Under review as a conference paper at ICLR 2020
1,0
1,0
0.8-
0.8-
0.5-
0.5-
GCNita
GON
0.-
@CNDss0)
GCN000
GFN(ted)
GFNDel))
0.0
0.7
0.0
0.8
Traning
Traning
(a) Best epoch
(b) Last epoch.
Figure 4: Performances under varied dataset size. As dataset sizes increases, it becomes harder to overfit (especially for GFN), but GFN still performs as well as, if not better, than GCN.
A
O
(a) Random samples.
(b) Mis-classified samples by GFN.
1 D
2
(c) Random samples.
(d) Mis-classified samples by GCN.
Figure 5: Random and mis-classified samples from MUTAG. Each row represents (true) class.
C
10
O r
A
6
(a) Random samples
(b) Mis-classified samples by GFN.
H A
3
x
J
C
(c) Random samples.
(d) Mis-classified samples by GCN.
Figure 6: Random and mis-classified samples from PROTEINS, Each row represents (true) class.
16

---

Under review as a conference paper at ICLR 2020
(a) Random samples.
(b) Mis-classified samples by GFN.
(c) Random samples.
(d) cis-classified samples by GCN.
Figure 7: Random and mis-classified samples from IMDB-B. Each row represents (true) class.
(a) Random samples.
(b) Mis-classified samples by GFN.
(c) Random samples.
(d) Mis-classified samples by GCN.
Figure 8: Random and mis-classified samples from IMDB-M. M. Each row represents (true) class.
17


Reviews:
[{"review_id": "Hye94W7M5r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 paper dissects the importance of two parts in GCN: 1) nonlinear neighborhood aggregation; 2) nonlinear set function by linearizing the two parts and resulting in Graph Feature Network (GFN) and Graph Linear Network (GLN). It shows empirically that GFN achieves almost the same performance while GLN is much worse, suggesting the nonlinear graph neighborhood aggregation step may be unnecessary. Extensive ablation studies are conducted to single out the effects of various factors.\n\nThe paper studies an interesting problem and sets out a good plan of experiments to verify the hypotheses. The results are interesting: merely constructing graph neighborhood features alone is enough to get comparable performance with GCN since the nonlinearity in the set function is strong enough. The experiments are designed nicely: 1) it compares with various baselines on a variety of popular benchmarks; 2) ablation studies single out the importance of different graph features, such as degree, and multi-hop averages; 3) verifying whether the good performance GFN comes from easier optimization.\n\nThe paper is also clearly written, with clean notations, and well-structured sections.\n\nI think the experiment can be improved by comparing on larger, more complex datasets. Figure 1 seems to suggest GCN is overfitting compared to GFN due to its extra capacity--significantly better training accuracy but slightly worse test accuracy. It is usually the case that larger and more complex datasets require more sophisticated models. But the paper makes a good case for GFN in these datasets for the graph classification task.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HJgX4T6CtH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 paper presents a dissection analysis of graph neural networks by decomposing GNNs into two parts: a graph filtering function and a set function. Although this decomposition may not be unique in general, as pointed out in the paper, these two parts can help analyze the impact of each part in the GNN model. Two simplified versions of GNN is then proposed by linearizing the graph filtering function and the set function, denoted as GFN and GLN, respectively. Experimental results on benchmarks datasets for graph classification show that GFN can achieve comparable or even better performance compared to recently proposed GNNs with higher computational efficiency. This demonstrates that the current GNN models may be unnecessarily complicated and overkill on graph classification. These empirical results are pretty interesting to the research community, and can encourage other researchers to reflect on existing fancy GNN models whether it's worth having more complex and more computationally expensive models to achieve similar or even inferior performance. Overall, this paper is well-written and the contribution is clear. I would like to recommend a weak accept for this paper. If the suggestions below can be addressed in author response, I would be willing to increase the score.\n\n\nSuggestions for improvement:\n\n1) Considering the experimental results in this paper, it is possible that the existing graph classification tasks are not that difficult so that the simplified GNN variant can also achieve comparable or even better performance (easier to learn). This can be conjectured from the consistently better training performance but comparable testing performance of original GNN. Another possibility is that even the original GNN has larger model capacity, it is not able to capture more useful information from the graph structure, even on tasks that are more challenging than graph classification. However, this paper lacks such in-depth discussions;\n\n2) Besides the graph classification task, it would be better to explore the performance of the simplified GNN on other graph learning tasks, such as node classification, and various downstream tasks using graph neural networks. This can help demystify the question raised in the previous point; 3) The matrix \\tilde{A} in Equation 5 is not well explained (described as \"similar to that in Kipf and Welling (2016)\"). It would be more clear to directly point out that it is the adjacency matrix, as described later in the paper.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJg-ri4CYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 paper tries to study the importance of different components of GNNs. This paper studies two components 1) graph filtering: aggregation of neighboring features and 2) the aggregation function for the output.\n\nTo study this problem, this paper proposes two models, Graph Feature Network (GFN) and Graph Linear Network (GLN). GFN first uses the adjacency matrix to create several layers of features, then applies a multi-layer fully-connected neural network. GLN is a special case of GFN with the fully-connected neural network being linear.\n\nThis paper conducts experiments on graph classification task and finds GFN gives a reasonable performance, whereas GLN's performance is weaker.\n\n\n\nComments:\nThis paper studies an important problem in GNN, and the proposed method is interesting. However, I cannot accept the paper in the current form because of the following reasons.\n\n1. There is no theoretical analysis in the paper. For example, on some datasets, GFN, GLN, and GNN's performances are close while on other datasets, there are gaps. The current paper does not provide insight.\n\n2. GNN also contains non-linearity in the middle layers. However, the methodology in this paper cannot account for the importance of non-linearity in the middle layers.\n\n3. The experiment section ignores some recent results on graph classification tasks. See:\nhttps://arxiv.org/abs/1809.02670\nhttps://arxiv.org/abs/1905.13192", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to split the GNN operations into two parts and study the effects of each part. While two reviewers are positive about this paper, the other reviewer R1 has raised some concerns. During discussion, R1 responded and indicated that his/her concerns were not addressed in author rebuttal. Overall, I feel the paper is borderline and lean towards reject.
Decision: Reject