Demystifying Graph Neural Network Via Graph Filter Assessment
Authors: Yewen Wang
Ziniu Hu
Yusong Ye
Yizhou Sun
Venue:  (2020)
Keywords: Graph Neural Networks
Graph convolutional filter analysis
representational power

Abstract: Graph Neural Networks (GNNs) have received tremendous attention recently due to their power in handling graph data for different downstream tasks across different application domains. The key of GNN is its graph convolutional filters, and recently various kinds of filters are designed. However, there still lacks in-depth analysis on (1) Whether there exists a best filter that can perform best on all graph data; (2) Which graph properties will influence the optimal choice of graph filter; (3) How to design appropriate filter adaptive to the graph data. In this paper, we focus on addressing the above three questions. We first propose a novel assessment tool to evaluate the effectiveness of graph convolutional filters for a given graph. Using the assessment tool, we find out that there is no single filter as a `silver bullet' that perform the best on all possible graphs. In addition, different graph structure properties will influence the optimal graph convolutional filter's design choice. Based on these findings, we develop Adaptive Filter Graph Neural Network (AFGNN), a simple but powerful model that can adaptively learn task-specific filter. For a given graph, it leverages graph filter assessment as regularization and learns to combine from a set of base filters. Experiments on both synthetic and real-world benchmark datasets demonstrate that our proposed model can indeed learn an appropriate filter and perform well on graph tasks.

Under review as a conference paper at ICLR 2020
DEMYSTIFYING GRAPH NEURAL NETWORKS VIA GRAPH FILTER ASSESSMENT
Anonymous authors Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) have recently received tremendous attention due to their power in handling graph data for different downstream tasks across differ- ent application domains. Many GNN models have been proposed, which mainly differ in their graph filter design. However, most of these models believe there is best filter for all the graph data. Instead, we attempt to provide in-depth anal- ysis on (1) Whether there exists an optimal filter that performs the best on all graph data; (2) Which graph properties should be considered for finding the op- timal graph filter; and (3) How to design appropriate filters that adapt to given graph. In this paper, we focus on addressing the above three questions for the semi-supervised node classification task. We propose novel assessment tool, called Graph Filter Discriminant Score (GFD), for evaluating the effectiveness graph convolutional filters for given graph in terms of node classification. Using the assessment tool, we find out that there is no single filter as a "silver bullet" that performs the best all possible graphs, and graphs with different properties are in favor of different graph convolutional filters. Based on these findings, we develop Adaptive Filter Graph Neural Network (AFGNN), simple but powerful model that can adaptively learn data-specific filters. For a given graph, AFGNN leverages graph filter assessment as an extra loss term and learns to combine a set of base filters. Experiments on both synthetic and real-world benchmark datasets have demonstrated that our proposed model has the flexibility in learning an ap- propriate filter and consistently provides state-of-the-art performance across all the datasets.
INTRODUCTION
Graph Neural Networks (GNNs) are family of powerful tools for representation learning graph data, which has been drawing more and more attention over the past several years. GNNs can obtain informative node representations for graph of arbitrary size and attributes, and has shown great ef- fectiveness in graph-related down-stream applications, such as node classification (Kipf & Welling
2017). graph classification (Wu al. 2019b), graph matching (Bai al. 2019). recommendation systems Ying et al. 2018). and knowledge graphs (Schlichtkrull et al. 2018))
As GNNs have superior performance in graph-related tasks, the question as what makes GNNs so powerful is naturally raised. Note that GNNs adopt the concept of the convolution operation into graph domain. To obtain representation of specific node GNN, the node aggregates representations of its neighbors with convolutional filter. For a task related to graph topology, the convolutional filter can help GNN nodes to get better task-specific representations (Xu et al.) 2019). Therefore, it is the filter that makes GNNs powerful, and thus the key to designing robust and accurate GNNs to design proper graph convolutional filters.
Recently, many GNN architectures are proposed (Zhou al., 2018) with their own graph filter designs. However, none of them have properly answered the following fundamental questions of GNNs: (I) Is there a best filter that works for all graphs? (2) If not, what the properties of graph structure that will influence the performance of graph convolutional filttiss (3) Can we design an algorithm to adaptively find the appropriate fiteeforr a given graph?
In this paper, we focus on addressing the above three questions for semi-supervised node classifi- cation task. Inspired by studies in Linear Discriminant Analysis (LDA),, propose Graph Filter

---

Under review as a conference paper at ICLR 2020
Discriminant (GFD) Score metric measure the power of a graph convolutional filter in discrimi- nating node representations of different classes on a specific graph. We have analyzed all the existing GNNs' filters with this assessment method to answer the three aforementioned questions. We found that no single filter design can achieve optimal results on all possible graphs. In other words, for different graph data, we should adopt different graph convolutional filters achieve optimal perfor- mance. We then experimentally and theoretically analyze how graph structure properties influence the optimal choice of graph convolutional filters.
Based on all of our findings, we propose the Adaptive Filter Graph Neural Network (AF-GNN), which can adaptively learn a proper model for the given graph. We use the Graph Filter Discriminant Score (GFD) as an extra loss term to guide the network to learn a good data-specific filter, which a linear combination of a set of base filters. We show that the proposed Adaptive Filter can better capture graph topology and separate features on both real-world datasets and synthetic datasets.
We highlight our main contributions as follows:
Graph Filter Discriminant Score, to analyze the effective- ness of graph convolutional filters. Using this tool, we find that no best filter can work for all graphs, the optimal choice of a graph convolutional filter depends on the graph data.
We propose an assessment tool:
We propose Adaptive Filter Graph Neural Network that can adaptively learn proper filter for specific graph using the GFD Score as guidance.
We show that the proposed model can find better filters and achieve better performance compared to existing GNNs, on both real-word and newly created benchmark datasets.
2
PRELIMINARIES
Semi-Supervised Node Classification. Let Y be the class assignment vector for all the nodes in V. C indicates the total number of classes, and Y, (1....,, C'} indicates the class that node v belongs to. The goal of semi-supervised node classification is to learn a mapping function f
+ fI....,C7 using the labeled nodes, and predict the class labels for the unlabeled nodes, i.e., Y, f(v), by leveraging both node features X and graph structure A.
Graph Data Generator. Intuitively, semi-supervised node classification requires both node fea- tures (X) and the graph structure (A) to be correlated to the intrinsic node labels (Y) to some extent. To systematically analyze the performance of different GNN filters, test their performance under different graph data with different properties, i.e., graphs with different X, A, Y. Intuitively, both graph topology and node features have to be correlated with the node labels, if including both can enhance the performance of node classification task. To better understand the roles played by each component, we assume the graphical model to generate a graph data is as described in Fig. [[a).. To better disclose the relationship between different graph filters and properties of different graph data, we further make assumptions on how X and are generated when is given, as is difficult to obtain those properties from real-world data. Therefore, study simulated data to support thorough analysis. We now describe the generation Y. X|Y, and A|Y respectively.
Generating Y:
Each node is randomly assigned with class label with probability proportional to its class size. We assume each class e associated with n, nodes.
We assume that node features are sampled from a distribution determined by their corresponding labels. For example, we can sample node features class e from multivariate Gaussian distribution with the parameters conditioned on class (() (p(p()) E() For another example, we can sample node features of class e from circular distribution with radius re and noise noise, conditioned on c.
Generating Y:
Generating AYY: We follow the most classic class-aware graph generator, i.e. stochastic block model (SBM, Holland et al.) (1983)), to generate graph structure conditioned on class labels. SBM has several simple assumptions that (1) edges generated via Bernoulli distributions independently and (2) the parameter of the Bernoulli distribution is determined by the classes of the corresponding pair of nodes v, and Vy, i.e., A.y Y, Y, ~ Ber(py,x,), where py,,, is parameter determined by the two corresponding classes. In a simple two-class case, = P11 = P22 denotes the probability that the linked pair belongs to the same class, while q P12 P21 denotes the probability that
2

---

Under review as a conference paper at ICLR 2020
the linked pair belongs to different classes. We call ptg the "density of graph", which controls the overall connectivity of a graph, and we call Ip g the "density gap", which controls how closely the graph generated by SBM correlates with labels. We assume 2 in all the following sections. Degree Corrected SBM (DCSBM, Karrer & Newman (211T), which is a variation of SBM, adds another parameter y to control the "power-law coefficient " of degree distribution among nodes. Figure [b-e) demonstrates examples of synthetic graphs generated by SBM and DCSBM with different graph structure properties.
(a) Dependency of Y, X and A
(h) SBM: 0.3, 0.05
(c) SBM: = 0.1, (d) DCSBM: p 0.3, (c) DCSBM: p = 0.1, 0.02
q 0.05, 7 009 == 0.02, 0.6
Figure (a) shows dependency between Y, X and A. (b) and (c) are dense and sparse graph generated by SBM, which have uniform degree distribution. (d) and (e) are dense and sparse graph generated by DCSBM, which have power-law degree distribution.
Graph Convolutional Filters. By examining various GNN designs, we find that most of the GNN operators can fit into a unified framework, i.e., for the I-th layer:
H = (F( (-1W)
which describes the three-step process that involves: (1) graph convolutional operation (can also be regarded feature propagation feature smoothing) denoted as F(G) (2) linear trans- formation denoted by multiplying W. and (3) a non-linear transformation denoted by a-)). Clearly, the graph convolutional operation ((-))(( is the key step that helps GNNs to improve per- formance. Thus, design good GNN, powerful graph convolutional filter F(G) is crucial. We analyze the effectiveness of graph filters for existing GNNs in the following.
The work of GCN (Kipf & Welling 2017 first adopts the convolutional operation graphs and Here, À = A I is the self-augmented adjacency matrix, and D diag (di,.., ..., dmn) is the corresponding degree matrix, where d, = -ド Auj.
the filter F(g) D 1/2 AD
Some studies Wu et al. 2019a; Maehara 2019) use a filter F(g) = 1D-1/2 that is similar form to GCN's s filter, but with a pre-defined exponent greater than one. This would help node to obtain information from its further neighbors without redundant computation cost. Several other studies propose to use sampling to speed up GNN training (Chen et al. 2018b Hamilton et al., 2017
Chen et al. 2018ah), which can be considered
sparser version of GCN's filter.
Another set of GNNs consider using a learnable graph convolutional filter. For example, Xu et al. F(G) A+ cI where c is learnable parameter to augment self-loop skip connection. Graph Attention Networks( Velickovic et al.) 2018) proposes to assign attention weight to different nodes in neighborhood, which can be considered as a flex- ible learnable graph convolutional filter. Their graph filters applied on feature matrix X can be exp(a((a W x. W x,
(2019) and and Chhang et al. (2019) both propose
considered as: Vi,j. F(G) ΣLEN explata W [[ Aij. where NG is the neighborhood of node is learnable weight vector, and indicates concatenation.
ASSESSMENT TOOL FOR ANALYZING GRAPH CONVOLUTIONAL FILTERS
In this section, introduce a novel assessment tool for analyzing graph convolutional filters. We first review the Fisher score, which is widely used in Linear Diseriminant Analysis to quantify the linear separability of two sets of features. With the Fisher score, propose the Graph Filter Discriminant Score metric to evaluate the graph convolutional filter on how well it can separate nodes in different classes.
3

---

Under review as a conference paper at ICLR 2020
3.1 THE ASSESSMENT TOOL: GRAPH FILTER DISCRIMINANT SCORE
Fisher Score. When coming to non-graph data, the Fisher Score (Fisher 1936 is used to assess the linear separability between two classes. Given two classes of features (*) and X x the Fisher Score is defined as the ratio of the variance between the classes (inter-class distance) to the variance within the classes (inner-class distance) under the best linear projection w of the original feature:
(w (n 1)
J(X (1) x() = max WER" W (E + ΣG) w
(2)
where (1(9) and fe(5) denotes the mean vector of X (6) and X respectively, Σ and Σ6) denotes
(f) and X() respectively, and w denotes the linear projection vector which we rotation of the coordinate system, and the max operation is to find the best direction in which these two class of nodes are most separable. As the numerator of J indicates inter- class distance and the denominator of J indicates inner-class distance larger value of J indicates higher separability. Note that for given features, we can directly get the closed form solution of the optimal w. with which Fisher Score could be deformed as: ( (1) x)) = (μ (*) - 01)) ( (Σ() +
the variance of (+)
can understand
- - ()) The detailed proof is provided in appendix A.2
Graph Filter Diseriminant Score. As mentioned before, the key component that empowers GNNs is the graph convolutional filter F(G). Intuitively, an effective filter should make the rep- resentations of nodes in different classes more separable. Therefore, Scores of the node representations before and after applying the graph convolutional filter in or- der to evaluate this filter. For each pair of classes (i,J), we define their Fisher Difference as
propose to use Fisher
Fi. J ((F()))) (9) (F())x)() ((X(() x(()).
which is the difference of their Fisher Score of representations after applying the filter F(g) and their Fisher Score of initial representa- tions. We then define the GFD Score for the filter F(G) with respect to feature matrix X as follows:
EBFFD(i.)) GFD(F19).
+ my
Bi En + me)
where ne is the number of nodes in class c. Note that the GFD Score is a weighted sum of the Fisher Difference for each pair of classes. Intuitively, the larger the GFD score, the more effective is this corresponding filter to increase the separability of node features.
The Fisher Score can be extended to evaluate non-linearly separable data in addition to linearly separable data. We claim the rationale of such measure by showing that the graph convolution can actually help non-linearly separable data to be linearly separable if the graph filter is chosen properly for a given graph. As shown in Figure ad)~(d)) if we use a proper filter, the convolutional opera- tion can transform three circular distributions, which are non-linearly separable, into three linearly separable clusters. Moreover, as shown in Figure (h)) even if the original features of different classes are sampled from the same distribution, the proper graph convolutional filter can help to linearly separate the data. This phenomenon shows that if the graph structure (A) is correlated with the task (Y), proper filter alone is powerful enough empower GNNs with non-linearity. without any non-linear activation. This phenomenon is also supported by the promising result of SGC (Wul al., (2019a), which removes all the non-linear activations the GCN architecture. Therefore, we claim that the proposed GFD is a reasonable metric to evaluate a graph filter's 's effecttivnnsss, and good graph filter for a given graph should have a higher GFD score on that graph.
3.2 ASSESSING EXISTING GRAPH CONVOLUTIONAL FILTERS
With the help of the assessment tool, we now examine existing filters and try to answer the two fundamental questions: (1) Is there a best filter that works for all graphs? (2) If not, what are the properties of graph data that will influence the performance of graph convolutional filters?
The GFD Score we introduced in the above section can be applied to any filter on any given graph. From T we can see that most of the current GNNs fall into the following filter family: {{A)*), where the base Á is a normalized adjacency matrix, and k is the order of the filter. Note that there are some other variants of GNN filters that do not fall into this family, for example, GAT, but the analysis is similar. Without loss of generality, we focus on analyzing this filter family. The two main components of this filter family are the normalization strategy (A) and the order use (k). For
4

---

Under review as a conference paper at ICLR 2020
20
530
515
501
casc
6017
0:335
10:
45
4.15
230
2.8
482
103
6:22
6.355
6,02
C2651
Caes2
Ca063
(a) Fisher- = 0.00001
(b) Fisher = 0.0327
(c) Fisher = 1.6679
(d) Fisher = 64.5456
3.15
6:15
dass
3.10
0:13
dass2
319
t0:
0.007
48:
6:305
315
40213
40
4.2
o
3 n² glthgg
6 x3 0
.25
.2019
20305
0,00
6,00
(e) Fisher 0.00004
(I) Fisher 0.0069
(g) Fisher = 0.4281
(h) Fisher 17.8018
Figure 2: Each row corresponds to a graph. The i-th column corresponds to the feature distribution after applying filter (D-1/2 AD 1/2ji-1 Both graphs include three classes of same size and has structure generated by SBM (p = 0.6. q = 0.03). The first graph's s feature follows a circular distribution with radius 1, 0.9, 0.8 and Gaussian noise 0.02 for each class. The second graph's feature follows a circular distribution with radius- = and Gaussian noise = 0.02 for all classes
10F
1/2
are
101
ID-1AP (AU
10
0.30
-9.25
-0.20
-8:15
10 -0.05
0.00
2.4
0.6 0.
25
PowerLaw Coefticinnt (y)
Label Rabe in1/=2
Figure 3: How power law coefficient and label ratio influence the optimal choice of filter's normal- ization strategy. Detailed Parameters of graph generator are provided in Appendix AA.3
simplicity, we study the roles of these two components separately, using our assessing tool to show whether there exists an optimal choice of filter for different graph data. If an optimal choice does not exist, we determine the factors that will influence our choice of component.
Through the analysis, we choose SBM and DCSBM introduced previously generate the structures of synthetic graphs, and choose multivariate Gaussian distributions to generate features of synthetic graphs. We focusing on the structure properties that influence the optimal choice of filter. We enumerate the hyper-pann parameters to generate graphs with different structure properties, including the power law coefficient (y) that controls the power law degree distribution of the graph, label ratio (H)) that indicates how balance are the classes of this graph, density (25") that indicates the overall connectivity of the graph, and density gap (p--g) that indicates structural separability of the graph. As these properties are significant for real-world graphs, our generated synthetic graphs can cover a large range of possible graph properties, and representative for analyzing different filters.
Analyzing Filter's Normalization Strategy. We consider three normalization strategies, in- cluding row normalization D-1 A, column normalization AD-1, and symmetric normalization D 11122 AD 1122 We calculate GFD scores of these three graph filters for graphs generated with dif- ferent parameters. As shown in Figure no single normalization strategy is optimal for all graphs! ! Here we give empirical explanation this phenomenon. Note that, with the same order, each filter has the same receptive field, and different normalization strategies affect only on how to assign weights the neighboring nodes. The row normalization strategy simply takes the mean of features of the node's neighbors. Clearly, this would help to keep every node's new representations in the same range. On the contrary, column normalization and symmetric normalization, might keep a larger representation for higher-degree nodes. Using a base of the graph convolutional filter is similar to the PageRank algorithm. While a node propagates its features to neighbors, this normalization strategy takes its degree into account. Thus, column normalization can be helpful when the when node degree plays an important role for classification.
adjacency matrix as the
We also provide examples in Appendix A.3 to illustrate that each normalization and order will outperform others in some specific graph data, and none of single normalization order can be the hest choice.
5

---

Under review as a conference paper at ICLR 2020
30F
10
"Ai?"
7.0
CID
12
18001,3758 1023 125.22225.5111111 1753
Demuity Mpp QU/2)
Deesily Gap 184)
Figure 4:
How density and density gap influence the optimal choice of filter's order. Detailed Parameters of graph generator are provided in Appendix A.3
Symmetric normalization combines the properties from both the row normalization and the column normalization. Even in the case where row normalization and column normalization do not perform well, symmetric normalization still leads to promising performance.
We now examine which graph properties influence our choice of the optimal normalization strategy, which may vary per graph. We find that power law coefficient is an important factor that influences the choice of normalization. As shown in Figure when power-law coefficient y decreases (graph's extent of power-law grows), row normalization tends to have better performance. This is because row normalization helps to keep node representations in the same range, so that large representations of high degree nodes can be avoided. Therefore, it prevents nodes with similar degrees getting closer to each other and messing the classification tasks where node degrees are not important.
We also find that the label ratio (11) matters. As shown in Figure 3 when the size of cach class nz
becomes more imbalanced, column normalization tends to work better. This is because column normalization better leverages degree property during representation smoothing, as nodes in large- size classes tend have larger representation since they are more likely to have higher degree. This can help nodes within different classes become more separable.
We then analyze what would be the best order for filters. With a high- order filter, a node can obtain information from its further neighbors, and thus the amount of infor- mation it receives during the feature propagation increases. But do we always need more information under any circumstances? The answer is no. Still, we find that, for different graphs, the order that results in the best performance would be different"
Analyzing Filter's Order.
Since there is no best filter order for all the cases, we explore the factors that can influence the choice of order. We find that the density of graph and density gap between two classes have a big impact. As shown in Figure 4 when the density or density gap increases, the filter with higher order tends be better choice. We provide an intuitive explanation for this phenomenon as follows. Note that the feature propagation scheme is based on the assumption that nodes in the same class have closer connection. On one hand, when the density increases, the connections between nodes are closer. Therefore, high-order filters can help gather richer information and thus reduce the variance of the obtained new node representations, so it helps nodes the same class get smoother representations. On the other hand, when the density gap decreases, for node, the size of neighbors within the same class becomes similar to the size of neighbors within different classes. Thus conducting high-order graph convolution operations will mix the representations of all nodes regardless of classes, which will make node classification more difficult.
4 LEARNING TO FIND THE OPTIMAL GRAPH CONVOLUTIONAL FILTER
Based on previous analysis, we now answer the last question: Can we design an algorithm to adap- tively find the appropriate filter for a given graph? We develop simple but powerful model, the Adaptive Filter Graph Neural Network (AFGNN). For a given graph, AFGNNs can learn combine an effective filter from a set of filter bases, guided by GDF Scores.
Adaptive Filter Graph Neural Network (AFGNN), For simplicity, we only con- sider finding the optimal filter for one family of graph convolutional filters: F(G)
1I.D-1/AAD11/ AD-1/2 (D-1/2 AD- -- A.. (D-I AD-1. (Á
where l: is the maximum order. Note that, we also include the identity matrix, which serves as a kiip-connection, to maintain the original feature representation. Based on our previous analysis, for graphs that are not closely correlated to tasks (i.e., small density gap in SBM), the identity matrix will outperform all the other convolutional filters. We denote the above 3k 1 filters as

---

Under review as a conference paper at ICLR 2020
(g)) Farm (9), the [-th layer of AFGNN is defined as learnable linear combination of these filter bases:
3k+1
FAF)
Σ
a
(1)
F (g), where of (4) exp U
(3)
3k+1 j=1 exp( (1)))
1=1
where v:(1) is the learnable vector to combine base filters and ( is its noftmax-normalinn version.
Comparing to GNNs with fixed filters such GCN and SGC, our proposed AFGNN can adap- tively learn a filter based on any given graph. As we have shown that no single fixed filter can perform optimally for all graphs, we conclude that an adaptive filter has more capacity learn better representations. Comparing to other GNNs with learnable filters such as GAT, AFGNN is computationally cheaper and achieves similar or better performance on most existing benchmarks and our synthetic datasets (as shown in the experiment section). We leave expanding the base filter family and adding more complex filters such as GAT into our filter bases as future work.
Training Loss. To train this AFGNN model, we can simply optimize the whole model via any downstream tasks, i.e., node classification. However, as most of the semi-supervised node classi- fication datasets only contain limited training data, the enlarged filter space will make the model prone to over-fittin. Thus, we decide to add the GFD Score as an loss term into the training loss to guide the optimization of filter weights, i.e., vi()) and prevent overfitting:
- Σ CFD (H(-))
== Lex + ALFDD, where LOFD =
(4)
where Log is the cross-entropy loss of the node classification, and LOFD defined as the cumula- tive negation of GFD Score for the learned adaptive filter FAFGNN at each layer with respect to its imput representation (I-)), During the training, we minimize L to learn the proper model.
With a different choice of the weight for GFD loss, we can categorize our model into: AFGNN,: With x O, the model is only trained by LCE, which might be prone to over-fitting when data is not sufficient.
AFGNN;: With À 1, the model is trained by both LCx and LAED simultaneously.
AFGNN2:: This case is not exactly X = oo, and the training process is different from the other two cases. We implement the training iteratively: we optimize the combination of base filters by training only with GFD loss LGFD. D. then we optimize the linear transofrmation parameter W's with classification loss LCg. Note that the input feature (0)) = X is invariant, we can pre-train the optimal filter for first layer and fix it.
5 EXPERIMENTS
Dataset We first evaluate AFGNN on three widely used benchmark datasets: Cora, Citeseer, and Pubmed (Sen et al., 2008). As these datasets are not sensitive enough differentiate the models, we need more powerful datasets that can evaluate the pros and cons of each model. Based on our findings in section 3.2 we generate two synthetic benchmarks called SmalIGap and SmallRatio. SmallGap corresponds to the case in which the density gap of the graph is close to 1. This indicates that the graph structure does not correlate much to the task, thus I would be the best filter in this case. SmallRatio corresponds to the case in which the label ratio is small, i.c. the size of one class is clearly smaller than the other, and column normalization AD is the best normalization
Baselines and Settings. We compare against 5 baselines, including GCN, GIN, SGC, GFNN, and GAT. To make fair comparisons, for all the baseline GNNs, we set the number of layers (or orders) to be 2, and tune the parameters including learning rate, weight decay, and number of epoch: For all the benchmark datasets, we follow the data split _ For the synthetic dataset, we conduct 5-fold validaaai,,,,,,, randomly split the nodes into 5 groups of the same size, take one group as the training set, one as the validation set and the remaining three as the test set. Each time we pick
"The statistics of benchmark and parameters used to generate synthetic dataset are in Appendix A.6
"The details about baseline code and hyperparameters settings are provided in Appendix A.7
7

---

Under review as a conference paper at ICLR 2020
Dataset
GCN
GIN
SGC
GPNN
GAT
AFGNNo
AFGNNI
ARGNN
Cora
80.85.10.43
76.37:10.75
$1.14:10.05
80.42:10.70
82.90.: 0.01
6..22
81.16:10.48
81,40 0.03
Citeseer
71.19+0.00
67.85+00.52
71.91
71.15::0.55
72.20=0.07
60.58:0.911
71.32:0..85
71.80=0.01
Pubmed
79.08=0.23
74.23++1.76
78.50=0.00
79.12:+0.23
78.50=0.01
72.58+2.84
78.51=:0.14
79.20=0.01
SmallCiup
82.78:00.20
76.83:10.87
0..53:20.94
03.38:1:0300
85.26::0.00
90,85
99.91:10.04
99.95
SmallRatio
87.79=1.00
77.8243.40 40
87.14=0.19
83.75:+0.20
82.10=0.01
74.45+4..1
85.69+3.60
93.80=1.11
Table 1: Test accuracy of different models on both benchmark and synthetic datasets.
Graph Filters
Cora
Citeseer
Pubmed
SmallGap
SmallRatio
13.15
25.05
11.75
34.13
3.62
Cora- m000 a coo 1.000.00...0o 0.003 0.000 2,000
D- D-IA A
33.68
48.24
22,05
0.97
6.25
(D AA
58.48
67.53
37.70
18.17
10.50
Citeseer
AD-1
28.35
12.44
10.67
Pubmie woss 0o0 oss 0.00 c.02 coo
(AD -111
49.64
62.16
22.74
16.27
80.37
D 1/2 AD 11/2 1/22
31.87
47.20
20,09
0.97
8.51
SmallGap 0.242 o 132 bast 0335 0.131 0.12 2a01
(D 1/2 AD-1/332
54.76
65.50
34.61
17.58
49.69
SmallRatio
AFGNN AFGNN
8.50
Ap Ad
6-1020 to
d (--RAb--1n)
58.28
67.83
38.61
34.59
77.81
AFGNN
58.48
67.68
38.61
34.68
80.37
Table 2: Fisher Score after appying different filters on both bench- mark and synthetic datasets
Figure 5: Base filter combina- tion Learned by AFGNN
the model with highest validation accuracy and record its test accuracy. For each dataset, we run the experiment 10 times and compute the mean and standard deviation of recorded test accuracy.
Classification Performance. As shown in Table our proposed AFGNN model can consis- tently achieve competitive test accuracy. On Pubmed, SmalIGap, and SmallRatio, AFGNN can achieve the best results among all the baseline models. On Cora and Citeseer, though GAT out- performs our proposed model little bit, however, as shown in Table 7 GAT takes a longer time to train and converge, and has more memory cost as well. Also, when the given graph is simple, AFGNN, AFGNN1,
GAT would suffer unavoidable overfitting problem. We further compare AFGNN to examine the role of GFD loss. The AFGNN, performs quite poorly on all the datasets, implying that the larger search space of the filter without GFD loss is prone to over-fitting, while AFGNN, and AFGNN perform much better. Also, AGENN has superior performance com- pared AFGNN,, which indicates the GFD Score is indeed a very powerful assessment tool.
Graph Filter Discriminant Analysis. We are also interested to see whether the proposed method can indeed learn the best combination of filters from the base filter family. To do so, we calculate the GFD Score of the first-layer filter learned by AFGNN,- AFGNN,, AFGNN oo and the seven base filters on the test set for each dataset. For the AFGNN models, the filter is trained with the training set for each dataset. Table Ell and Figure 5 show the results, we can see that our proposed method can indeed learn a combined filter on all the datasets. Specifically, in all the benchmark datasets, the best base filter is (D-1 A)² and our proposed adaptive filter not only picks out the best base filter but also learns a better combination. For the two synthetic datasets, where I and AD-111 are the best filters, our algorithm can also learn to pick them out. We thereby conclude that the proposed GFD loss can help find an appropriate filter for a given dataset.
6 CONCLUSION
Understanding the graph convolutional filters GNNs very important, as it can help to determine whether GNN will work on given graph, and can provide important guidance for GNN design. In our paper, we focus on the semi-supervised node classification task. We first propose the Graph Filter Discriminant Score as assessment tool for graph convolutional filter evaluation, and then apply this GFD Score to analyze a family of existing filters as a case study. Using this tool, we learn that no single fixed filter can produce optimal results on all graphs. We then develop simple but powerful GNN model: Adapative Filter Graph Neural Network, which can learn to combine a
'Note that fisher score hefore applying filter is fixed value, therefore, to compare GFD of each filter, we only need compare Fisher Score after appying different filters.
8

---

Under review as a conference paper at ICLR 2020
family of filters and obtain task-specific powerful filter. We also propose to add the negative GFD Score as an extra component to the objective function, can act as a guidance for the model to learn more effective filter. Experiments show that our approach outperforms many existing GNNs on both benchmark and synthetic graphs.
REFERENCES
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neural network approach to fast graph similarity computation. In Proceedings of the Twelfth ACM Web Search and Data Mining, WSDM 2019, Melbourne, VIC, doi: 10.1145/329960.3299996/ URL
International Conference
Australia, February 11-15, 2019, pp. 384-392, 2019.
https://doi. http:/oi..rg////
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pp. 941-949, 2018a. 8a. URL http: http:ttpppppoocciigg... .mr.. wttp:/ddddnnn.....pssssss//////e wwt.ll/ppeeeee//eeee/eeo wttps////v///c/eeeeeeee html
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. CoRR, 00//1801.124477 2018b. URI. htt.tt:://xxxii.orr///aatt/
1801 10247
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019., pp. 257-266, 2019.
Ronald A Fisher. The use of multiple measurements in taxonomic problems. Annals of eugenics, (2):179-188, 1936.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-137 1983.
Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical review E, 83(1):016107, 2011.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017. URL
net/
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, ((Nov):2579-2605 2008.
Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv:1905.09550 2019.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling, Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-607. Springer, 2018.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-99 93, 2008.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3. 2018, Conference Track Proceedings, 2018.
ew. net forum? d= JXMp kCZ.

---

Under review as a conference paper at ICLR 2020
GNNs
Graph Convolutional Filters
GCN
Kipf & Welling
2017
F(g) D D- ".-AD-11 1/2 F(G) (D) (D- AD 1/2
1/2
SGC
Wu et al.
2019a
GPNN
(Machara 2019
F(G) (D 1/2 AD 1/22*
GIN
et 2019)
F(G) A +II
GAT
Velickovic et al.
2018
F(G) Q. where Q is parametric attention function of X and A
Table 3: A Summary of Graph Filters of Existing GNNs.
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.0715,, 2019a.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.0000 2019b.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka, How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019. URL http:s////penreveee.neeee/// het.eeewwweeeeeeeeeeeeeeeeeeeeee nwtp:/runffoodddcoooooo
Rex Ying, Ruining Hc, Kaifeng Chen, Pong Eksombatchai, William Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974 983. ACM, 2018.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: A review of methods and applications. arXiv preprint arXiv: 1812.881144444,, 2018.
A
APPENDIX
A.1 SUMMARY OF GRAPH FILTERS FOR EXISTING GNNs.
Table 3
summarized the graph filters for existing GNNs.
A.2 PROOF OF PROPOSITION
Proof According to the conclusions in linear discriminant analysis, the maximum separation occurs when w x (I() )
(,()). Note that, when we want to apply this fisher linear discriminant score in our problem, the linear transformation part in our classifier (and also the linear transformation part GNN) will help to find the best u. Thus, we can directly plug the optimum solution w" = ( m03) -1 (x) (و) into this formula, here is scalar. Then, we'll 'llll have:
(w (n( 1)²
O( x(0)
max
w E w (1 ΣG) y
((c(2()) +
()))) (w() n()))²² [c) Σら)) ( ((i1))
(AE + Σ0)
((n()) (10) (E - ((()) )1))) )
(n(0) - 1(0) (E + - (1((0 u(0
(p(0 -10 (00) Σ6) 1 (( - -1)
(5)
Thus we completed the proof.
10

---

Under review as a conference paper at ICLR 2020
A.3
No BEST FILTER FOR ALL GRAPHS
A.3.1 EXAMPLES OF "No BEST NORMALIZATION STRATEGY FOR ALL"
Figure 2 provides examples show there is no best normalization strategy for all graphs. For both examples, we fix the order of filter to be
in which normalization is better than the other two. The corre- sponding graph contains 2 classes of nodes with size 500. The graph structure is generated by DCSBM with p 0.3. q 0.05, power law coefficient 7 0.9. The features for two classes satisfy multivariate distribution with an identity co-variance matrix, and with mean (0.2,0.2) and (0,0) respectively. In this example, we can clearly see that with other two normalization strategy, some high-degree hubs show up in the upper right corner from both class, which is harmful for classification. We generate this example to illustrate the benefit of row normalization because row normalization would be very helpful for graph with power law degree distribution, which contains some nodes with unusually large degree (those nodes are called hubs), since can help avoid those hubs obtaining larger representations and thus be mis-classified.
The first row shows
The second row shows a case in which column normalization better than the other two. The corre- sponding graph contains 2 classes of nodes with size 900 and 100 respectively. The graph structure is generated by SBM with p = 0.3, = 0.2. The features for two classes satisfy multivariate distri- bution with identity co-variance matrix, and with mean (-0.2,-0.2) and (0.2.0.2) respectively. We generate this example to illustrate the benefit of column normalization because under this case, we should consider taking more degree information into consideration. Therefore, column normaliza- tion would be more helpful.
cless
025
class
class2
classs
3.16
64
0.00
2
6
(a) Initial Feature. GFD=0.0212
(b) Row-nomalized. GFD=12.3236
(c) Column-nomalized.
(d) Symmetric-nomalized.
GFD-0.1371
GFD=0.9343
0.2
0.2
cass2
0.1
0.33
dla22
sland
cass2
6:4
6:2
031
6
(e) Initial Feature.
(f) Row- nomalizel
(g) Column-nommlizen
(h) coumetric-nomalizer
GFD70.1266
0FD20.5820
GFD=32.6420
GFD=24.0931
Figure 6: Examples of "No Best Normalization Strategy for All"
A.3.2 EXAMPLES OF "No BEST ORDER FOR ALL"
Figure provides two examples to show there is no best order for all graphs. For both examples, we fix the normalization strategy to be row normalization, and varies order to be 2, 4. 6.
The first row shows case in which small order is better than the large ones. The corresponding graph contains classes of nodes with same size 500. The graph structure is generated by SBM with p- = 0.215, = 0.2. The features for two classes satisfy multivariate distribution with an identity co-variance matrix, and with mean (0.5,0.5) and (0,0) respectively.
The second row shows a case in which large order is better than the smaller ones. The corresponding graph contains 2 classes of nodes with same size 500. The graph structure is generated by SBM with p = 0.75, = 0.6. The features for two classes satisfy multivariate distribution with an identity co-variance matrix, and with mean (0.5,0.5) and (0,0) respectively.
11

---

Under review as a conference paper at ICLR 2020
clesi dlys2
3355
Cass
0.20
class
1250
coss2
5299
3.23
class
0225
clase2
3225
22200
1233
0236 8,50
0,26
0,80
0,300
02400
62900
62550
(a) Initial Feature. GFD=0.3493
(b) Orde==2.FFD-044355 (c) Order=4GFD=0..000 (d) Order=6.GFD=O
class
clasi clest
10
dass
class
05
daos
60
-05
-10
(e) Initial Feature. GFD=0.3691
(f) Order=2.GFD=4.666 (g) Order=4.
(h) Order=6.
GFD2=1..5277
GFD=14.7939
Figure 7: Examples of "No Best Order for All"
A.3.3 ILLUSTRATION OF GRAPH GENERATOR FOR CURVES IN SECTION 3.2
For the curves indicating how powerlaw coefficient influence the choice of normalization in Figure [ we generate the corresponding graphs structure by DCSBM with fixed p 0.3, = =0=00 0.2 and varies the powerlaw coefficient from -0.3 O. The graph contains two classes of nodes, and is of size 400 and 600 for each class respectively. The feature for each class satisfies multivariate normal distribution with identity co-variance matrix, and with mean (0,0) and (0.2,0.2).
For the curves indicating how label ratio influence the choice of normalization in Figure we generate the corresponding graphs structure by SBM with fixed p 0.3, q 0.1 and varies the label ratio. The graph contains total number of 1000 nodes in two classes. The feature for each class satisfies multivariate normal distribution with identity co-variance matrix, and with mean (0,0) and (0.5,0.5).
For the curves indicating how density influence the choice of normalization in Figure we generate the corresponding graphs structure by SBM with fixed density gap p/q 1.5 and varies the density by varying q. The graph contains two classes of node size 500. The feature for each class satisfies multivariate normal distribution with identity co-variance matrix, and with mean (0.0) and (0.5,0.5).
For the curves indicating how density gap influence the choice of normalization in Figure 4 we generate the corresponding graphs structure by SBM with fixed density p q 0.6 and varies the density gap. The graph contains two classes of node of size 500. The feature for each class satisfies multivariate normal distribution with identity co-variance matrix, and with mean (-0.2,-0.2) and (0.2,0.2).
A.4 FLOWCHART OF AFGNN FOR NODE CLASSIFICATION
The following flowchart (Figure 8 describes the process of how one-layer AFGNN tackle node classification task.
A.5 FEATURE PROPAGATION USING DIFFERENT FILTERS
We reduced the dimension of feature by t-SNE (Maaten & Hinton (200)). We annotate the filter and the GFD Score in title of each subfigure. Note that, identity also corresponds to the initial feature. The figure is the feature representation obtained after conduct graph convolution operation with the corresponding filter.
12

---

Under review as a conference paper at ICLR 2020
XJY
F(g)x
W
Softmax
Ypred
A|Y
F(g)
F(g)
(r(1) (T2) F(3) ...
learned
one AFGNN layer
Figure 8: Flowchart of 1-layer AFGNN for node classification.
(a) Identity:13.15
(b) AFGNN:58.28
(c) fow1:33.68
(d) row2:58.48
(e) col1:28.35
(f) co12:49.64
sym1:31.87
(h) sym2:54.76
Figure 9: Feature Visualization
A.6 DATASET
A.6.1 BENCHMARK DATASET
We use three benchmark dataset: Cora, Citeseer and Pubmed for the node classification task. Their statictics are in table4 Beside number of nodes, edges, classes, the dimension of feature, and the data split strategy, we also show the class rutio variance, which can indicates if this dataset is imbalance or not, density gap, which indicates dependency of structure and labels, and density, which indicates the overall connectivity of graph. We provide the degree distribution in Figure 10. and we can clearly find that these benchmark datasets has power law degree distribution.
Di of crp
14gre Detribe ofceneer
025
0.0
025
635
680
0.5
(a) Cora
(b) Citeseer
Figure 10: Degree Distribution of Benchmark Dataset
13

---

SBM Under review as a conference paper at ICLR 2020
Dataset
Cora
Citeseer
Pubmed
Nodes
2708
3327
19717
Edges
5429
4732
44338
Classes
6
3
Feature
1433
3703
500
Train
140
120
60
Validation
500
500
500
Test
1000
1000
1000
Ratio Variance
0.0052
0.0020
0,0079
Density Gap
0.013
0,0051
0,0006
Density
0.0068
0.0029
0.0004
Table 4: Statistics of Benchmark Dataset
Cora
Citeseer
Pubmed
GCN GIN SGC 81.0=0.0
81.5
70.3
79.0
71.910.1
78.9=0.0
GFNN 80.9
69.3+1.1
81.2
GAT
83.0+0.7
72.5+0.7
79.0=
Table 5: Baseline's Accuracy on Benchmark Dataset
A.6.2 SYNTHETIC DATASET
We also generated two synthetic datasets: SmalIGap and SmallRatio. For SmalIGap, we use SBM to generate two class network with 0.2 and q 0.199. The density gap p/q is very small in this case. They have the same number of nodes and both have 64 dimension features sampled from gaussian distributions with different mean and same variance. For SmallRatio, generate a two class network, which has 200 nodes for one class and 800 nodes for the other. This dataset called SmallRatio because nl m1/n2 0.25 small. Their 64 features are sampled from gaussian distributions with different mean and different variance. The detailed generation process and parameter can be found in our code.
A.7 MODEL HYPER PARAMETERS
For GCN, SGC, GFNN, GAT, we directly use their public implementations. For GIN, the initial code is not for node classification task, so we modify their code following Xu et al. (2019) to conduct experiments.
We tune the number of epochs based on convergence performance. For learning rate and weight de- cay, follows the parameter setting provides by the corresponding public implementations unless we find better parameters. The tuned parameters can be found in our code resource.
A.8 BASELINE ACCURACY ON BENCHMARK DATASET
We report the accuracy node classification task for baseline models on Cora, Citeseer, and Pubmed provided by corresponding literature. Since GIN (Xu et al. (019)) is not originally evaluated on node classification task, we do have the reported number here. The results Table
A.9 TIME AND MEMORY COST COMPARISON
Both AFGNN model and GAT model have learnable filter. We provide time and memory complexity comparison on benchmark datasets here to compare these two models.
As shown in Table 6 GAT's time cost is at least three times of AFGNN's time cost both Cora and Citeseer dataset. As shown in Table 7 AFGNN's memory cost on both Cora and Citeseer are half of GAT's memory cost. GAT does not have recorded time and memory cost for Pubmed dataset
14

---

Under review as a conference paper at ICLR 2020
Cora
Citeseer
Pubmed
time
num
total
time
num
total
time
num
total
AFGNNO
0.055
96.5
5.309
0.116
117.5
13.579
0.376
137.0
51.456
AFGNN1
0.086
129.3
11.1
0.136
155.4
21.177
0.379
136.1
51.62
AFGNN.c. (filter)
0.106
53
5.593
0.146
48
7.023
0.377
75.456
AFGNN oz (classification)
0.005
200
0,914
0.006
400
2.293
0.006
400
2.246
af (overall)
6.507
9.315
77.702
GAT
0.156
382.8
59.625
0.168
379.3
63.462
Table 6: Time Cost
Cora
Citeseer
Pubmed
AFGNNO
861
1369
1351
AFGNNI
863
1369
1351
AFGNN 20 GAT
863
1369
1351
1733
2345
Table 7: Memory(MB) Cost
precision classO
precision class
Fl classO
Fl class!
micro F1
macro F1
GCN
95.70=11.62
64.50:133.80
97.60-10.80
39.60125..77
95.52+1.24
63.64
SGC
94.30++0.45
21.70++33321
97.00++0000
9.50+114.74
94.34+0.36
53.32:47.51
GENN
98.40=11.50
76.20+125.57
98.80=0.60
72.10-24.60
97.42=1.10
85.40=12.32
GIN
95.90
62.00:135.49
97.60=10.66
38.80=25.49
95.20=0.97
68.
GAT
96.50+t0.67
85.00+:30.00
98.00=10.00
35.40=114.60
96.43=0.43
66.84+7.400
AFGNN,
95.00+0.777
53.90:+39.97
97.20=#0.40
19.90
94.62=0068
58.62:+9.89
AFGNN,
94.80+1.11
40.00++:8.99
97.40=1.80
16.80+27.15
94.84+1.23
57.09+13.88
AFGNN
98.20
83.40-L0.80
99.00110.00
1.60
97.38
88.22-L0.96
Table 8: Performance on OAG SmallRatio Dataset
because it requires too much memory cost and is able to run GPU, Therefore, AFGNN needs less time and memory cost than GAT.
A.10 SUPPLEMENTARY EXPERIMENT
generate real-world dataset with imbalanced classes to justify hard cases may exist in real- world datasets. We download a large scale academic graph called Open Academic Graph (OAG), and choose two fields that have large disparity in the number of papers: (1) "History of ideas", which consists of 1041 papers; (2) "Public history", which consists of 150 papers. Obviously this two classes are imbalanced, and fall the large label ratio gap problem. We run supplementary experiment on the generated OAG graph, the experiment setting remains the same experiment settings for synthetic graphs.
Table shows the experiment results. To evaluate the models, we compare their Fl score for each class, the weighted average Fl score (micro FI), and the average Fl score (macro Fl). Our AFGNN model shows superior performance on this dataset.
15


Reviews:
[{"review_id": "rygcY3OCFB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 is a very interesting study about GNN. Authors proposed to extend LDA as a discrimination evaluator for graph filleters. Also authors proposed Adaptive Filter Graph Neural Network to find the optimal filter within a limited family of graph convolutional filters. The whole study is novel, and beneficial for the community of graph neural network study. It provides a new way to understand and evaluate GNN.\n\nThere are some questions authors should clarify. And some writing errors to correct.\nEq (3) defines GFD for a pair of classes i and j. For a graph with more than two classes, the GFD will be the average of all pairs? Will class imbalance will have any impact on this GFD measure?  \nErrors:\n•\twe studies the roles of this two components \n•\tthere exist a best choice \n•\twe only consider to to find\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SklzDh7NcB", "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 introduces an assessment framework for an in-depth analysis of the effect of graph convolutional filters and proposes a novel graph neural network with adaptable filters based on the analysis. The assessment framework builts on the Fisher discriminant score of features and can also be used as an additional (regularization) term for choosing optimal filters in training. The assessment result shows that there is no single graph filter for all types of graph structures. Experiments on both synthetic and real-world benchmark datasets demonstrate that the proposed adaptive GNN can learn appropriate filters for different graph tasks. \n\nThe proposed analysis using the Fisher score is reasonable and interesting, giving us an insight into the role of graph filters. Even though the analysis is limited (using simple graph models and filter family) and the result is not surprising (given no free lunch theorem, there is very likely to be no single silver bullet fo graph filters), I appreciate the analysis and the result. But, I have some concerns as follows. \n\n1) The proposed GNN and the optimization process\nThe proposed method is to extend CNN to a simple linear combination of different filter bases with learnable weights, which I don't think is very novel. Adding the GFD score as an additional constraint term is interesting, but the way of optimizing the whole objective function is unclear. (In addition, I think calling it the \"regularization term\" is inadequate since the term actually involves data observation, rather than a prior on parameters only.) \nIn the case of AFGNN_inf, I don't think it is equivalent to applying infinite lamda. If lamda is infinite, L_CE needs to be completely ignored. This needs to be clarified. \nIn the case of AFGNN1, I don't clearly understand how the whole objective function is properly optimized with fixed data representation. Is it also iteratively optimized? I hope this is also clarified in more detail. \n\n2) Unconvincing experiments\nThe results on three real datasets do not show significant gains, and two of them are even worse than those of GAT. Furthermore, inductive learning (e.g., protein-protein interaction (PPI) dataset used in GAT) is not tested, which I think needs to be also evaluated. While two synthetic datasets (SmallGap and SmallRatio) created by the authors show significant improvement, these datasets appear to be extreme and unrealistic and look carefully selected in favor of the proposed method. I recommend the authors use for evaluation more realistic datasets that can be found in related research.  \n", "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 assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1gL4Eq0tr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "In this paper, the authors raise and address three questions about graph neural network: (1) Whether there is a best filter that works for all graphs. (2) Which properties of the graph will influence the performance of the graph filter. (3) How to design a method to adaptively find the optimal filter for a given graph.\nThe paper proposes an assessment method called the Graph Filter Discriminant Score based on the Fisher Score. It measures how well the graph convolutional filter discriminate node representations of different classes in the graph by comparing the Fisher score before and after the filter.\nBased on the GFD scores of different normalization strategy and different order of the graph filter in the experiments on synthetic data, the authors answer the first two questions: (1) There is no optimal normalization for all graphs. (2) row normalization performs better with lower power-law coefficient, but works worse with imbalanced label classes and large density gap.\nFor the third question, the authors propose a learnable linear combination of a limited family of graph convolutional filters as the layer of model AFGNN, which can learn the optimal arguments of the combination based on the FGD score.\nThe paper focuses on a significant topic and proposes an assessment tool for the graph filters. Based on that, it also introduces a model to choose filters from a family of filters for any specific graph.\nThe description of preliminaries is clear.\nThe observations of the impact of the graph properties on the filter choice are interesting and explanations are provided.\nThe results of the test accuracy on both bench mark and synthetic datasets demonstrate the good performance of the proposed model.\nIt is good that the paper provides proof for the claim that the graph convolutional can help the non-linear separable data to be linearly separable, so it is reasonable to use Fisher score. However, does this claim support the second term in equation (3), where the Fisher score is used to evaluate before the filters applied?\nThe presentation of the last paragraph of “graph filter discriminant score” in page 4 can be improved. The Figure references seem incorrect and confusing.\nThe analysis of the influence of label ratio seems not accurate enough.\nFor the GFD score comparison in Figure 4, why choose order 1,3,7 for density and different order 2,3,6 for density gap?\nWhat is the meaning of the symbol psi(l)?\nIt would be better if the explanation of the raining loss section is more detailed and clear.\nWhat is “AFGNN_P” in the experiment analysis?\nIt could be interesting to see the comparison of time between the proposed method and the GAT.\nFor the graph filter discriminate analysis, is it fair to compare the learned layer with the other base filter using the GFD score? Since the learned layer is picked with highest GFD score. Maybe one or two sentences on this will be helpful.\nThe writing of the paper must be improved. Too many typos and grammar problems will impair the presentation and the reader can be distracted.\nMinor comments:\nThe layout of the sub caption of Figure 1 can be improved.\nThe usage of capital letter in the phrase “density gap” is inconsistent.\n“As shown in figure” instead of “As is shown in figure”.\nMany sentences miss article.\nThere are many typos in the writing.\nFor example, “Note that for given (feature)”, “…make the representation of nodes in different (class) more separable.”, “Noted that there are some other (variant) of GNN filters that (does) not fall into…” in page 4.\n“Here we give (a) empirical explanation to this phenomenon”, “this normalization strategy (take) into account…”, “Thus even in the case that the other two (doesn’t) perform well…” in page 5.\n“…a very important factor that (influence) the choice of normalization strategy”, “when power-law coefficient (decrease)”, “when the (sizes) of each class (become) more imbalanced”,  “This is because column normalization better (leverage) …” , “in a similar manner (with) label ratio”, “when the density or density gap (increase)”, “high-order filters can help gather… and thus (makes) the representations…”, “when the density gap (increase)” in page 6.\nThese can be continued but it is obvious that this paper needs proofreading.\n", "extra_scores": {"experience_assessment": "I do not know much about 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 assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper investigates graph convolutional filters, and proposes an adaptation of the Fisher score to assess the quality of a convolutional filter. Formally, the defined Graph Filter Discriminant Score assesses how the filter improves the Fisher score attached to a pair of classes (considering the nodes in each class, and their embedding through the filter and the graph structure, as propositional samples), taking into account the class imbalance.

An analysis is conducted on synthetic graphs to assess how the hyper-parameters (order, normalization strategy) of the filter rule the GFD score depending on the graph and class features. As could have been expected there no single killer filter.

A finite set of filters, called base filters, being defined by varying the above hyper-parameters, the search space is that of a linear combination of the base filters in each layer. Three losses are considered: with and without graph filter discriminant score, and alternatively optimizing the cross-entropy loss and the GFD; this last option is the best one in the experiments.

As noted by the reviewers and other public comments, the idea of incorporating LDA ideas into GNN is nice and elegant. The reservations of the reviewers are mostly related to the experimental validation: of course getting the best score on each dataset is not expected; but the set of considered problems is too limited and their diversity is limited too (as demonstrated by the very nice Fig. 5).

The area chair thus encourages the authors to pursue this very promising line of research and hopes to see a revised version backed up with more experimental evidence. 
Decision: Reject