Title: DEMYSTIFYING GRAPH NEURAL NETWORKS VIA GRAPH FILTER ASSESSMENT

Abstract: Graph Neural Networks (GNNs) have recently received tremendous attention due to their power in handling graph data for different downstream tasks across different application domains. Many GNN models have been proposed, which mainly differ in their graph filter design. However, most of these models believe there is a best filter for all the graph data. Instead, we attempt to provide in-depth analysis 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 optimal graph filter; and (3) How to design appropriate filters that adapt to a given graph. In this paper, we focus on addressing the above three questions for the semi-supervised node classification task. We propose a novel assessment tool, called Graph Filter Discriminant Score (GFD), for evaluating the effectiveness of graph convolutional filters for a 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 on 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), a 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 appropriate filter and consistently provides state-of-the-art performance across all the datasets.
Graph Neural Networks (GNNs) are a family of powerful tools for representation learning on graph data, which has been drawing more and more attention over the past several years. GNNs can obtain informative node representations for a graph of arbitrary size and attributes, and has shown great effectiveness in graph-related down-stream applications, such as node classification (Kipf & Welling, 2017), graph classification (Wu et al., 2019b), graph matching (Bai et 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 to what makes GNNs so powerful is naturally raised. Note that GNNs adopt the concept of the convolution operation into graph domain. To obtain a representation of a specific node in a GNN, the node aggregates representations of its neighbors with a 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 is to design proper graph convolutional filters.
Recently, many GNN architectures are proposed (Zhou et al., 2018) with their own graph filter designs. However, none of them have properly answered the following fundamental questions of GNNs: (1) Is there a best filter that works for all graphs? (2) If not, what are the properties of graph structure that will influence the performance of graph convolutional filters? (3) Can we design an algorithm to adaptively find the appropriate filter for a given graph?
In this paper, we focus on addressing the above three questions for semi-supervised node classification task. Inspired by studies in Linear Discriminant Analysis (LDA), we propose a Graph Filter

:

Discriminant (GFD) Score metric to measure the power of a graph convolutional filter in discriminating 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 to achieve optimal performance. 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 a an extra loss term to guide the network to learn a good data-specific filter, which is 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:

• We propose an assessment tool: Graph Filter Discriminant Score, to analyze the effectiveness 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 Adaptive Filter Graph Neural Network that can adaptively learn a proper filter for a 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 v ∈ {1, • • • , C} indicates the class that node v belongs to. The goal of semi-supervised node classification is to learn a mapping function f : V → {1, • • • , C} using the labeled nodes, and predict the class labels for the unlabeled nodes, i.e., Ŷv = f (v), by leveraging both node features X and graph structure A.

Graph Data Generator. Intuitively, semi-supervised node classification requires both node features (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, we 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. 1 (a).

To better disclose the relationship between different graph filters and properties of different graph data, we further make assumptions on how X and A are generated when Y is given, as it is difficult to obtain those properties from real-world data. Therefore, we study simulated data to support a thorough analysis. We now describe the generation of Y , X|Y , and A|Y respectively.

Generating Y : Each node is randomly assigned with a class label with probability proportional to its class size. We assume each class c is associated with n c nodes.

Generating X|Y : We assume that node features are sampled from a distribution determined by their corresponding labels. For example, we can sample node features of class c from a multivariate Gaussian distribution with the parameters conditioned on class c: X (c) ∼ N (µ (c) , Σ (c) ). For another example, we can sample node features of class c from a circular distribution with radius r c and noise noise c conditioned on c.

Generating A|Y : 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 are 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 i and v j , i.e., A ij |Y i , Y j ∼ Ber(p YiYj ), where p YiYj is a parameter determined by the two corresponding classes. In a simple two-class case, p = p 11 = p 22 denotes the probability that the linked pair belongs to the same class, while q = p 12 = p 21 denotes the probability that the linked pair belongs to different classes. We call p+q 2 the "density of graph", which controls the overall connectivity of a graph, and we call |p -q| the "density gap", which controls how closely the graph generated by SBM correlates with labels. We assume p ≥ q in all the following sections. Degree Corrected SBM (DCSBM, Karrer & Newman (2011) ), which is a variation of SBM, adds another parameter γ to control the "power-law coefficient" of degree distribution among nodes. Figure 1 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 l-th layer:

EQUATION

which describes the three-step process that involves: (1) a graph convolutional operation (can also be regarded as feature propagation or feature smoothing) denoted as F(G)H (l-1) , (2) a linear transformation denoted by multiplying W , and (3) a non-linear transformation denoted by σ(•). Clearly, the graph convolutional operation F(G)H (l-1) is the key step that helps GNNs to improve performance. Thus, to design a good GNN, a 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 on graphs and use the filter F(G) = D-1/2 Ã D-1/2 . Here, Ã = A + I is the self-augmented adjacency matrix, and D = diag( d1 , ..., dn ) is the corresponding degree matrix, where di = n j=1 Ãij .

Some studies (Wu et al., 2019a; Maehara, 2019) use a filter F(G) = ( D-1/2 Ã D-1/2 ) k that is similar in form to GCN's filter, but with a pre-defined exponent k greater than one. This would help a 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., 2018a) ), which can be considered as a sparser version of GCN's filter.

Another set of GNNs consider using a learnable graph convolutional filter. For example, Xu et al.

(2019) and Chiang et al. (2019) both propose to use F(G) = A+ I where is a learnable parameter to augment self-loop skip connection. Graph Attention Networks (Velickovic et al., 2018) proposes to assign attention weight to different nodes in a neighborhood, which can be considered as a flexible learnable graph convolutional filter. Their graph filters applied on a feature matrix X can be considered as: ∀i, j,

F(G) ij = exp(σ(α[W Xi||W Xj ])) k∈N i exp(σ(α[W Xi||W X k ])) A ij

, where N i is the neighborhood of node i, α is a learnable weight vector, and || indicates concatenation.

3. ASSESSMENT TOOL FOR ANALYZING GRAPH CONVOLUTIONAL FILTERS:

In this section, we introduce a novel assessment tool for analyzing graph convolutional filters. We first review the Fisher score, which is widely used in Linear Discriminant Analysis to quantify the linear separability of two sets of features. With the Fisher score, we propose the Graph Filter Discriminant Score metric to evaluate the graph convolutional filter on how well it can separate nodes in different classes.

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 X (i) and X (j) , 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:

EQUATION

where µ (i) and µ (j) denotes the mean vector of X (i) and X (j) respectively, Σ (i) and Σ (j) denotes the variance of X (i) and X (j) respectively, and w denotes the linear projection vector which we can understand as a rotation of the coordinate system, and the max w operation is to find the best direction in which these two class of nodes are most separable. As the numerator of J indicates interclass distance and the denominator of J indicates inner-class distance a 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:

J(X (i) , X (j) ) = (µ (i) -µ (j) ) (Σ (i) + Σ (j) ) -1 (µ (i) -µ (j)

). The detailed proof is provided in appendix A.2.

Graph Filter Discriminant Score. As mentioned before, the key component that empowers GNNs is the graph convolutional filter F(G). Intuitively, an effective filter should make the representations of nodes in different classes more separable. Therefore, we propose to use Fisher Scores of the node representations before and after applying the graph convolutional filter in order to evaluate this filter. For each pair of classes (i, j), we define their Fisher Difference as j) , which is the difference of their Fisher Score of representations after applying the filter F(G) and their Fisher Score of initial representations. We then define the GFD Score for the filter F(G) with respect to feature matrix X as follows:

F D(i, j) = J F(G)X (i) , F(G)X (j) -J X (i) , X (

GF D F(G), X = i =j βijF D(i, j), βij = ni + nj k =t (n k + nt)

where n c 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 2 (a)∼(d), if we use a proper filter, the convolutional operation can transform three circular distributions, which are non-linearly separable, into three linearly separable clusters. Moreover, as shown in Figure 2 (e)∼(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 ), a proper filter alone is powerful enough to empower GNNs with non-linearity, without any non-linear activation. This phenomenon is also supported by the promising result of SGC (Wu et al., 2019a) , which removes all the non-linear activations in the GCN architecture. Therefore, we claim that the proposed GFD is a reasonable metric to evaluate a graph filter's effectiveness, and a 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 Table 3 , we can see that most of the current GNNs fall into the following filter family:

{( Â) k },

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 ( Â) and the order to use (k). For 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 to 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-parameters to generate graphs with different structure properties, including the power law coefficient (γ) that controls the power law degree distribution of the graph, label ratio ( n1 n2 ) that indicates how balance are the classes of this graph, density ( p+q 2 ) that indicates the overall connectivity of the graph, and density gap (|p -q|) 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 are representative for analyzing different filters.

Analyzing Filter's Normalization Strategy. We consider three normalization strategies, including row normalization D -1 A, column normalization AD -1 , and symmetric normalization D -1/2 AD -1/2 . We calculate GFD scores of these three graph filters for graphs generated with different parameters. As shown in Figure 3 , no single normalization strategy is optimal for all graphs. 1 Here we give an empirical explanation to 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 to 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 column-normalized adjacency matrix as the 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. 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 3 , when power-law coefficient γ 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 ( n1 n2 ) matters. As shown in Figure 3 , when the size of each class becomes more imbalanced, column normalization tends to work better. This is because column normalization better leverages degree property during representation smoothing, as nodes in largesize classes tend to have larger representation since they are more likely to have higher degree. This can help nodes within different classes become more separable. Analyzing Filter's Order. We then analyze what would be the best order for filters. With a highorder filter, a node can obtain information from its further neighbors, and thus the amount of information 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 1 .

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 to be a 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 a 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 in the same class get smoother representations. On the other hand, when the density gap decreases, for a 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 adaptively find the appropriate filter for a given graph? We develop a simple but powerful model, the Adaptive Filter Graph Neural Network (AFGNN). For a given graph, AFGNNs can learn to combine an effective filter from a set of filter bases, guided by GDF Scores.

Adaptive Filter Graph Neural Network (AFGNN). For simplicity, we only consider finding the optimal filter for one family of graph convolutional filters:

F(G) = {I, D-1/2 Ã D-1/2 , • • • , ( D-1/2 Ã D-1/2 ) k , D-1 Ã, • • • , ( D-1 Ã) k , Ã D-1 , • • • , ( Ã D-1 ) k },

where k is the maximum order. Note that, we also include the identity matrix, which serves as a skip-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

F base 1 (G), • • • , F base 3k+1 (G)

, the l-th layer of AFGNN is defined as a learnable linear combination of these filter bases:

F AF GN N (G) (l) = 3k+1 i=1 α (l) i F base i (G), where α (l) i = exp(ψ (l) i ) 3k+1 j=1 exp(ψ (l) j ) (3)

where ψ (l) is the learnable vector to combine base filters and α (l) is its softmax-normalized version.

Comparing to GNNs with fixed filters such as GCN and SGC, our proposed AFGNN can adaptively 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 to 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 classification datasets only contain limited training data, the enlarged filter space will make the model prone to over-fitting. 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., ψ (l) and to prevent overfitting:

L = L CE + λL GF D , where L GF D = - L l GF D F AF GN N (G) (l) , H (l-1) (4)

where L CE is the cross-entropy loss of the node classification, and L GF D is defined as the cumulative negation of GFD Score for the learned adaptive filter F AF GN N (G) (l) at each layer with respect to its input representation H (l-1) . 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 0 : With λ = 0, the model is only trained by L CE , which might be prone to over-fitting when data is not sufficient. AFGNN 1 : With λ = 1, the model is trained by both L CE and L GF D simultaneously.

AFGNN ∞ : This case is not exactly λ = ∞, 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 L GF D , then we optimize the linear transofrmation parameter W l s with classification loss L CE . Note that the input feature H (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 to 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 SmallGap 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.e. the size of one class is clearly smaller than the other, and column normalization AD -1 is the best normalization2 .

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 epochs3 . For all the benchmark datasets, we follow the data split convention 2 . For the synthetic dataset, we conduct 5-fold cross-validation, 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. Classification Performance. As is shown in Table 1 , our proposed AFGNN ∞ model can consistently achieve competitive test accuracy. On Pubmed, SmallGap, and SmallRatio, AFGNN ∞ can achieve the best results among all the baseline models. On Cora and Citeseer, though GAT outperforms our proposed model a little bit, however, as shown in Table 6 ,7, GAT takes a longer time to train and converge, and has more memory cost as well. Also, when the given graph is simple, GAT would suffer unavoidable overfitting problem. We further compare our AFGNN 0 , AFGNN 1 , AFGNN ∞ to examine the role of GFD loss. The AFGNN 0 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 1 and AFGNN ∞ perform much better. Also, AGFNN ∞ has superior performance compared to AFGNN 1 , 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 0 , AFGNN 1 , AFGNN ∞ 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 2 4 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 Ã) 2 , 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 ( Ã D-1 ) 2 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 in GNNs is very important, as it can help to determine whether a GNN will work on a 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 an 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 a simple but powerful GNN model: Adapative Filter Graph Neural Network, which can learn to combine a A.3 NO BEST FILTER FOR ALL GRAPHS A.3.1 EXAMPLES OF "NO BEST NORMALIZATION STRATEGY FOR ALL"

Figure 6 provides two examples to show there is no best normalization strategy for all graphs. For both examples, we fix the order of filter to be 2.

The first row shows a case in which row normalization is better than the other two. The corresponding 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 γ = -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 a graph with power law degree distribution, which contains some nodes with unusually large degree (those nodes are called hubs), since it can help avoid those hubs obtaining larger representations and thus be mis-classified.

The second row shows a case in which column is better than the other two. The corresponding graph contains 2 classes of nodes with size 900 and 100 respectively. The graph structure is generated by SBM with p = 0.3, q = 0.2. The features for two classes satisfy multivariate distribution with an 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 normalization would be more helpful. Figure 7 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 a case in which small order is better than the large ones. The corresponding graph contains 2 classes of nodes with same size 500. The graph structure is generated by SBM with p = 0.215, q = 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, q = 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. For the curves indicating how powerlaw coefficient influence the choice of normalization in Figure 3 , we generate the corresponding graphs structure by DCSBM with fixed p = 0.3, q = 0.2 and varies the powerlaw coefficient from -0.3 to 0. 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 3 , we generate the corresponding graphs structure by SBM with fixed p = 0.3, q = 0.1 and varies the label ratio. The graph contains a 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 4 , 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 of 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 a 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 (2008) ). 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 once with the corresponding filter. 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 ratio variance, which can indicates if this dataset is imbalance or not, density gap, which indicates the dependency of structure and labels, and density, which indicates the overall connectivity of a graph. We provide the degree distribution in Figure 10 , and we can clearly find that these benchmark datasets has power law degree distribution. 

A.10 SUPPLEMENTARY EXPERIMENT:

We generate a real-world dataset with imbalanced classes to justify hard cases may exist in realworld datasets. We download a large scale academic graph called Open Academic Graph (OAG), and choose two fields that have a 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 in the large label ratio gap problem. We run supplementary experiment on the generated OAG graph, the experiment setting remains the same as experiment settings for synthetic graphs.

Table 8 shows the experiment results. To evaluate the models, we compare their F1 score for each class, the weighted average F1 score (micro F1), and the average F1 score (macro F1). Our AFGNN ∞ model shows superior performance on this dataset.

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 a single normalization or order can be the best choice.

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

Note that fisher score before applying filter is a fixed value, therefore, to compare GFD of each filter, we only need to compare Fisher Score after appying different filters.

Figures and Tables:

Figure 1: (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.

Figure2: Each row corresponds to a graph. The i-th column corresponds to the feature distribution after applying filter ( D-1/2 Ã D-1/2 ) i-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 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 = 1 and Gaussian noise = 0.02 for all classes.

Figure 3: How power law coefficient and label ratio influence the optimal choice of filter's normalization strategy. Detailed Parameters of graph generator are provided in Appendix A.3.

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.

Figure 5: Base filter combination 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.

Figure 6: Examples of "No Best Normalization Strategy for All"

Figure 7: Examples of "No Best Order for All" A.3.3 ILLUSTRATION OF GRAPH GENERATOR FOR CURVES IN SECTION 3.2

Figure 8: Flowchart of a 1-layer AFGNN for node classification.

Figure 9: Feature Visualization

Figure 10: Degree Distribution of Benchmark Dataset

Each time we pick Test accuracy of different models on both benchmark and synthetic datasets.

Table content: <table><tr><td>Dataset</td><td>GCN</td><td/><td>GIN</td><td>SGC</td><td>GFNN</td><td>GAT</td><td>AFGNN0</td><td>AFGNN1</td><td>AFGNN∞</td></tr><tr><td>Cora</td><td>80.85±0.43</td><td colspan="2">76.37±0.75</td><td>81.14±0.05</td><td>80.42±0.70</td><td>82.90± 0.01</td><td>61.22±1.61</td><td>81.16±0.48</td><td>81.40 ±0.03</td></tr><tr><td>Citeseer</td><td>71.19±0.60</td><td colspan="2">67.85±0.52</td><td>71.91±0.01</td><td>71.15±0.55</td><td>72.20±0.07</td><td>60.58±0.91</td><td>71.32±0.85</td><td>71.80±0.01</td></tr><tr><td>Pubmed</td><td>79.08±0.23</td><td colspan="2">74.23±1.76</td><td>78.50±0.00</td><td>79.12±0.23</td><td>78.50±0.01</td><td>72.58±2.84</td><td>78.51±0.14</td><td>79.20±0.01</td></tr><tr><td>SmallGap</td><td>82.78±0.20</td><td colspan="2">76.83±0.87</td><td>74.53±0.94</td><td>83.38±0.30</td><td>85.26±0.07</td><td>90.85±3.24</td><td>99.91±0.04</td><td>99.95±0.01</td></tr><tr><td>SmallRatio</td><td>87.79±1.05</td><td colspan="2">77.82±3.40</td><td>87.14±0.19</td><td>83.75±0.20</td><td>82.10±0.01</td><td>74.45±4.81</td><td>85.69±3.69</td><td>93.80±1.11</td></tr><tr><td colspan="2">Graph Filters</td><td>Cora</td><td>Citeseer</td><td>Pubmed</td><td>SmallGap</td><td>SmallRatio</td><td/><td/></tr><tr><td>I</td><td/><td>13.15</td><td>25.05</td><td>11.75</td><td>34.13</td><td>3.62</td><td/><td/></tr><tr><td colspan="2">D-1 Ã</td><td>33.68</td><td>48.24</td><td>22.05</td><td>0.97</td><td>6.25</td><td/><td/></tr><tr><td colspan="2">( D-1 Ã) 2</td><td>58.48</td><td>67.53</td><td>37.70</td><td>18.17</td><td>10.50</td><td/><td/></tr><tr><td colspan="2">Ã D-1</td><td>28.35</td><td>43.99</td><td>12.44</td><td>0.97</td><td>10.67</td><td/><td/></tr><tr><td colspan="2">( Ã D-1 ) 2</td><td>49.64</td><td>62.16</td><td>22.74</td><td>16.27</td><td>80.37</td><td/><td/></tr><tr><td colspan="2">D-1/2 Ã D-1/2</td><td>31.87</td><td>47.20</td><td>20.09</td><td>0.97</td><td>8.51</td><td/><td/></tr><tr><td colspan="2">( D-1/2 Ã D-1/2 ) 2</td><td>54.76</td><td>65.50</td><td>34.61</td><td>17.58</td><td>49.69</td><td/><td/></tr><tr><td colspan="2">AFGNN0</td><td>19.72</td><td>34.84</td><td>12.02</td><td>34.29</td><td>8.50</td><td/><td/></tr><tr><td colspan="2">AFGNN1</td><td>58.28</td><td>67.83</td><td>38.61</td><td>34.59</td><td>77.81</td><td/><td/></tr><tr><td colspan="2">AFGNN∞</td><td>58.48</td><td>67.68</td><td>38.61</td><td>34.68</td><td>80.37</td><td/><td/></tr></table>

Fisher Score after appying different filters on both benchmark and synthetic datasets

Table content: <table/>

Performance on OAG SmallRatio Dataset because it requires too much memory cost and is not able to run on GPU. Therefore, AFGNN needs less time and memory cost than GAT.

Table content: <table><tr><td/><td/><td/><td>Cora</td><td/><td/><td>Citeseer</td><td/><td/><td>Pubmed</td></tr><tr><td/><td/><td>time</td><td>num</td><td>total</td><td>time</td><td>num</td><td>total</td><td>time</td><td>num</td><td>total</td></tr><tr><td colspan="2">AFGNN0</td><td>0.055</td><td>96.5</td><td>5.309</td><td colspan="6">0.116 117.5 13.579 0.376 137.0 51.456</td></tr><tr><td colspan="2">AFGNN1</td><td colspan="2">0.086 129.3</td><td>11.1</td><td colspan="5">0.136 155.4 21.177 0.379 136.1</td><td>51.62</td></tr><tr><td colspan="2">AFGNN∞(filter)</td><td>0.106</td><td>53</td><td>5.593</td><td>0.146</td><td>48</td><td>7.023</td><td>0.377</td><td>200</td><td>75.456</td></tr><tr><td colspan="3">AFGNN∞(classification) 0.005</td><td>200</td><td>0.914</td><td>0.006</td><td>400</td><td>2.293</td><td>0.006</td><td>400</td><td>2.246</td></tr><tr><td colspan="2">AFGNN∞(overall)</td><td>-</td><td>-</td><td>6.507</td><td>-</td><td>-</td><td>9.315</td><td>-</td><td>-</td><td>77.702</td></tr><tr><td>GAT</td><td/><td colspan="6">0.156 382.8 59.625 0.168 379.3 63.462</td><td>-</td><td>-</td><td>-</td></tr><tr><td/><td/><td/><td colspan="3">Table 6: Time Cost</td><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td colspan="4">Cora Citeseer Pubmed</td><td/><td/></tr><tr><td/><td/><td colspan="2">AFGNN 0</td><td>861</td><td>1369</td><td>1351</td><td/><td/><td/></tr><tr><td/><td/><td colspan="2">AFGNN 1</td><td>863</td><td>1369</td><td>1351</td><td/><td/><td/></tr><tr><td/><td/><td colspan="3">AFGNN ∞ 863</td><td>1369</td><td>1351</td><td/><td/><td/></tr><tr><td/><td/><td colspan="2">GAT</td><td>1733</td><td>2345</td><td>-</td><td/><td/><td/></tr><tr><td/><td/><td/><td colspan="4">Table 7: Memory(MB) Cost</td><td/><td/><td/></tr><tr><td/><td colspan="4">precision class0 precision class1</td><td colspan="2">F1 class0</td><td colspan="2">F1 class1</td><td colspan="2">micro F1</td><td>macro F1</td></tr><tr><td>GCN</td><td colspan="2">95.70±1.62</td><td colspan="2">64.50±33.80</td><td colspan="6">97.60±0.80 39.60±25.97 95.52±1.24 68.64±13.24</td></tr><tr><td>SGC</td><td colspan="2">94.30±0.45</td><td colspan="2">21.70±33.21</td><td colspan="6">97.00±0.00 9.50±14.74 94.34±0.36 53.32±7.51</td></tr><tr><td>GFNN</td><td colspan="2">98.40±1.50</td><td colspan="2">76.20±25.57</td><td colspan="6">98.80±0.60 72.10±24.60 97.42±1.10 85.40±12.32</td></tr><tr><td>GIN</td><td colspan="2">95.90±1.45</td><td colspan="2">62.00±35.49</td><td colspan="6">97.60±0.66 38.80±25.49 95.20±0.97 68.12±12.92</td></tr><tr><td>GAT</td><td colspan="2">96.50±0.67</td><td colspan="2">85.00±30.00</td><td colspan="6">98.00±0.00 35.40±14.60 96.43±0.43 66.84±7.40</td></tr><tr><td>AFGNN 0</td><td colspan="2">95.00±0.77</td><td colspan="2">53.90±39.97</td><td colspan="6">97.20±0.40 19.90±19.52 94.62±0.68 58.62±9.89</td></tr><tr><td>AFGNN 1</td><td colspan="2">94.80±1.17</td><td colspan="2">40.00±48.99</td><td colspan="6">97.40±0.80 16.80±27.15 94.84±1.23 57.09±13.88</td></tr><tr><td>AFGNN ∞</td><td colspan="2">98.20±0.40</td><td colspan="2">83.40±0.80</td><td colspan="6">99.00±0.00 77.80±1.60 97.38±0.18 88.22±0.96</td></tr></table>

Peer review (iclr2020):
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. The 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. Based 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. For 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. The 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. The description of preliminaries is clear. The observations of the impact of the graph properties on the filter choice are interesting and explanations are provided. The results of the test accuracy on both bench mark and synthetic datasets demonstrate the good performance of the proposed model. It 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? The presentation of the last paragraph of “graph filter discriminant score” in page 4 can be improved. The Figure references seem incorrect and confusing. The analysis of the influence of label ratio seems not accurate enough. For the GFD score comparison in Figure 4, why choose order 1,3,7 for density and different order 2,3,6 for density gap? What is the meaning of the symbol psi(l)? It would be better if the explanation of the raining loss section is more detailed and clear. What is “AFGNN_P” in the experiment analysis? It could be interesting to see the comparison of time between the proposed method and the GAT. For 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. The writing of the paper must be improved. Too many typos and grammar problems will impair the presentation and the reader can be distracted. Minor comments: The layout of the sub caption of Figure 1 can be improved. The usage of capital letter in the phrase “density gap” is inconsistent. “As shown in figure” instead of “As is shown in figure”. Many sentences miss article. There are many typos in the writing. For 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. “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. “…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. These can be continued but it is obvious that this paper needs proofreading.