Global Node Attentions via Adaptive Spectral Filters
Authors: Shouheng Li
Dongwoo Kim
Qing Wang
Venue:  (2021)
Keywords: Graph Representation learning
Graph Convolutional Network
Graph Fourier transform

Abstract: Graph neural networks (GNNs) have been extensively studied for prediction tasks on graphs. Most GNNs assume local homophily, i.e., strong similarities in local neighborhoods. This assumption limits the generalizability of GNNs, which has been demonstrated by recent work on disassortative graphs with weak local homophily. In this paper, we argue that GNN's feature aggregation scheme can be made flexible and adaptive to data without the assumption of local homophily. To demonstrate, we propose a GNN model with a global self-attention mechanism defined using learnable spectral filters, which can attend to any nodes, regardless of distance. We evaluated the proposed model on node classification tasks over six benchmark datasets. The proposed model has been shown to generalize well to both assortative and disassortative graphs. Further, it outperforms all state-of-the-art baselines on disassortative graphs and performs comparably with them on assortative graphs. 

Under review as a conference paper at ICLR 2021
GLOBAL NODE ATTENTIONS VIA ADAPTIVE SPECTRAL FILTERS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) have been extensively studied for prediction tasks on graphs. Most GNNs assume local homophily, i.e., strong similarities in local neighborhoods. This assumption limits the generalizability of GNNs, which has been demonstrated by recent work on disassortative graphs with weak local ho- mophily. In this paper, we argue that GNN's s feature aggregation scheme can be made flexible and adaptive to data without the assumption of local homophily. To demonstrate, propose GNN model with global self-attention mechanism defined using learnable spectral filters, which can attend to any nodes, regardless of distance. We evaluated the proposed model on node classification tasks over seven benchmark datasets. The proposed model has been shown to generalize well both assortative and disassortative graphs. Further, it outperforms all state-of- the-art baselines on disassortative graphs and performs comparably with them on assortative graphs.
INTRODUCTION
Graph neural networks (GNNs) have recently demonstrated great power in graph-related learning tasks, such as node classification (Kipf & Welling (017), link prediction (Zhang & Chen 2018) and graph classification (Lee et al. 2018). Most GNNs follow a message-passing architecture where, in each GNN layer, a node aggregates information from its direct neighbors indifferently. In this architecture, information from long-distanee nodes is propagated and aggregated by stacking multiple GNN layers together (Kipf & Welling 2017 Velickovic et al. 2018 Defferrard et al. (016).. However, this architecture underlies the assumption local homophily, i.e. proximity similar nodes. While this assumption seems reasonable and helps to achieve good prediction results on graphs with strong local homophily, such as citation networks and community networks (Pei et al. 2020), it limits GNNs' generalizability. Particularly, determining whether graph has strong local homophily not is challenge by itself. Furthermore, strong and weak local homophily can both exhibit in different parts of graph, which makes learning task more challenging.
Pei et al. 2020) proposed a metric to measure local node homophily based on how many neighbors of node from the same class. Using this metric, they categorized graphs assortative (strong local homophily) or disassortative (weak local homophily), and showed that classical GNNs such as GCN (Kipf & Welling 2017) and GAT (Velickovic et al. 2018)) perform poorly on disassortative graphs. Liu et al. (2020) further showed that GCN and GAT are outperformed by simple multi- layer perceptron (MLP) in node classification tasks on disassortative graphs. This is because the naive local aggregation of homophilic models brings in more noise than useful information for such graphs. These findings indicate that these GNN models perform sub-optimally when the fundamental assumption of local homophily does not hold.
Based on the above observation, we argue that a well-generalized GNN should perform well on graphs, regardless of their local homophily. Furthermore, since real-world graph can exhibit both strong and weak homophily in different node neighborhoods, a powerful GNN model should be able to aggregate node features using different strategies accordingly. For instance, in disassortative graphs where a node shares no similarity with any of its direct neighbors, such a GNN model should be able to ignore direct neighbors and reach farther find similar nodes, at least, resort to the node's 's attributes to make a prediction. Since the validity of the assumption about local homophily is often unknown, such aggregation strategies should be learned from data rather than decided upfront.

---

Under review as a conference paper at ICLR 2021
To circumvent this issue, in this paper, we propose novel GNN model with global self-attention mechanism, called GNAN. Most existing attention based aggregation architectures perform self- attention the local neighborhood of node (Velickovic et al. 2018), which may add local noises in aggregation. Unlike these works, we aim to design an aggregation method that can gather informative features from both close and far-distant nodes. To achieve this, we employ graph wavelets under relaxed condition of localization, which enables us to learn attention weights for nodes in the spectral domain. In doing so, the model can effectively capture not only local information but also global structure into node representations.
To further improve the generalizability of our model, instead of using predefined spectral kerness, we propose to use multi-layer perceptrons (MLP) to learn the desired spectral filters without limiting their shapes. Existing works on graph wavelet transform choose wavelet filters heuristically, such as heat kernel, wave kernel and personalized page rank kernel (Klicpera et al. 2019b Xu et al. 2019, Klicpera al., 2019a). They are mostly low-pass filters, which means that these models implicitly treat nigh-frrequene components as "noises" and have them discarded (Shuman et al. 2013 Hammond et al. 2011] Chang et al. 2020). However, this may hinder the generalizability of models since high-frequency components can carry meaningful information about local discontinuities, as analyzed in (Shuman et al., 2013). Our model overcomes these limitations by incorporating fully learnable spectral filters into the proposed global self-attention mechanism.
From a computational perspective, learning global self-attention may impose high computational overhead, particularly when graphs are large. We alleviate this problem from aspects. First, we sparsify nodes according to their wavelet coefficients, which enables attention weights to be distributed across the graph sparsely. Second, we observed that spectral filters learned by different MLPs tend to converge to be of similar shapes. Thus, we use a single MLP to reduce redundancy among filters, where each dimension in the output corresponds one learnable spectral filter. In addition to these, following (Xu et al., 2019;; Klicpera et al., 2019b), we use fast algorithm to efficiently approximate graph wavelet transform, which has computational complexity O(p [F]), where p is the order of Chebyshev polynomials and |E] is the number of edges in graph.
To summarize, the main contributions of this work are as follows:
1. We propose a generalized GNN model which performs well on both assortative and disas- sortative graphs, regardless of local node homophily.
2. We exhibit that GNN's aggregation strategy be trained via fully learnable spectral filter, thereby enabling feature aggregation from both close and far nodes.
3. We show that, unlike commonly understood, higher-frequency on disassortative graphs provides meaningful information that helps improving prediction performance.
We conduct extensive experiments compare GNAN with well-known baselines on node classifica- tion tasks. The experimental results show that GNAN significantly outperforms the state-of-the-an methods on disassortative graphs where local node homophily is weak, and performs comparably with the state-of-the thrt--rrt methods on assortative graphs where local node homophily is strong. This empirically verifies that GNAN is general model for learning on different types of graphs.
PRELIMINARIES
G= (V, EV, be an undirected graph with N nodes, where V, E, and A are the node set, edge set, and adjacency matrix of G, respectively, and æ : V + RT a graph signal function that associates each node with feature vector. The normalized Laplacian matrix of G is defined as 1- 11/2, where D E N is the diagonal degree matrix of G. In spectral graph theory, the eigenvalues = diag(A (Ai,..,, AN) and eigenvectors U of L = U are known as the graph's spectrum and spectral basis, respectively, where U is the Hermitian transpose of U. The graph Fourier transform æ is = U x and its inverse x = U
The spectrum and spectral basis carry important information on the connectivity of a graph (Shuman et al. 2013). Intuitively, lower frequencies correspond to global and smooth information on the graph. while higher frequencies correspond to local information, discontinuities and possible noise (Shuman
et al. 2013). One can apply a spectral filter g as in Equation I and use graph Fourier transform to manipulate signals graph in various ways, such as smoothing and denoising (Schaub &
2

---

Under review as a conference paper at ICLR 2021
Adaptive spectral filters via MLP
Aggregation via global attention
Multi-head concatenation
Original input graph
filter-1
filter-K
Figure 1: Illustration of spectral node attention layer 3-hop ego network of the central node from the CITESEER dataset. Node classes are indicated by shape and color. Passing the graph through two learned spectral filters (adaptive spectral filters) place attention scores on nodes, including node v itself. Nodes with positive attention scores are presented in color. Node features are aggregated for node according to attention scores (aggregation via global attention). The low-pass filter attend to local neighbors (filter 1), while the high-pass filter skips the first hop and attend the nodes in the second hop (filter K). The resulting embecdings from multiple heads are then concatenated before being sent to the next layer (multi-head concatenation). Note that we have visualized learned filters from experiments.
Segarra 2018), abnormally detection (Miller et al. 2011) and clustering (Wai et al. 2018). Spectral convolutions on graphs is defined the multiplication signal with filter g(A) in the Fourier domain, i.e.
g()x (UAUU" Ug(A)U" Ugg(A) Ug(A)a
(1)
When spectral filter is parameterized by a scale factor, which controls the radius of neighbourhood aggregation, Equation is also known the Spectral Graph Wavelet Transform (SGWT) (Hammond
et al. 2011 Shuman et al., 2013). For example, Xu et al. (201) uses small scale parameter s < to localize the wavelet node.
heat kernel, (SA)
PROPOSED APPROACH
Graph neural networks (GNNs) learn lower- diver-dimesiooall embeddings of nodes from graph structured data. In general. given node, GNNs iteratively aggregate information from its neighbor nodes, and then combine the aggregated information with its own information. An embedding of node the kth layer of GNN is typically formulated as
m. aggregate (h (k-1) E Nc
h (k) combine(h (k-1) m.),,
where No is the set of neighbor nodes of node m. is the aggregated information from the neighbors, and 1 (k) is the embedding of the node at the kth layer (he (0) æ.). The embedding h" of the node e at the final layer is then used for some prediction tasks. In most GNNs, No is restricted to a set of
one-hop neighbors of node Therefore, one needs to stack multiple aggregation layers in order to collect the information from more than one-hop neighborhood within this architecture.
Adaptive spectral filters. Instead of stacking multiple aggregation layers, we introduce spectral attention layer that rewires graph based spectral graph wavelets. A spectral graph wavelet th node is modulation in the spectral domain of signals centered around the node v, given by an N d-dimensional vector
2/ U 5..
(2)
3

---

Under review as a conference paper at ICLR 2021
where g(-) is spectral filter and 6, is one-hot vector for node
The common choice of a spectral filter is heat kernel. A wavelet coefficient You computed from heat kernel be interpreted the amount of energy that node has received from node u in its local neighborhood. In this work, instead of using pre-defined localized kernels, we use multi- layer perceptrons (MLP) learn spectral filters. With learnable spectral kernels, we obtain wavelet coefficients
ab. = Uddia((LP((A)UU
(3)
Similar to that of a heat kernel, the wavelet coefficient with a learnable spectral filter You can be understood as the amount of energy that is distributed from node to node u, under the conditions regulated by the spectral filter. Note that we use the terminology wavelet and spectral filter inter- changeably as we have relaxed the wavelet definition from (Hammond et al., 2011) so that learnable spectral filters in our work are not necessarily localized in the spectral and spatial domains. Eqquatin 3) requires the -eceopoccooooiiionnn of Laplacian matrix, which is expensive and infeasible for large graphs. We follow Xu et al. 2019); Klicpera et al. (2019b) to approximate graph wavelet transform using Chebyshev polynomials (Shuman al. 2013) (see Appendix A for details).
Global self-attention. Unlike the previous work (Xu et al. 20199) where wavelet coefficients are directly used to compute node embeddings, normalize wavelet coefficients through softmax layer
a, softmax((5.).
where a, R.N is an attention weight vector. With attention weights, update layer is then formalized as
h (k)
Σ anah (k-1) w(k)
where (kk) is a weight matrix shared across all nodes in the kth layer and is ELU nonlinear activation. Unlike heat kernel, the wavelet coefficient with a learnable spectral kernel is not localized. Hence, our work can actively aggregate information from far-distant nodes. Note that the update layer not divided into aggregation and combine steps in our work. Instead, we compute the attention ave directly from spectral filter.
Sparsified node attentions. With predefined localized spectral filters such as heat kernel, most of wavelet coefficients are zero due to their locality. In our work, spectral filters are fully learned from data, and consequently attention weights obtained from Iearnable spectral filters do not impose any sparsity. This means that to perform an aggregation operation graph, which time consuming with large graphs. From our experiments, we observe that most of attention weights are negligible after softmax. Thus, we consider two sparsification techniques:
need to retrieve all possible nodes
1. Discard the entries of wavelet bases that are below threshold f, i.e.
Yon 1-00
thu >
(5)
otherwise.
The threshold can be easily applied on all entries of wavelet bases. However, it offers little guarantee on attention sparsity since attention weights may vary, depending on the learning process of spectral filters and the characteristics of different datasets, as will be further discussed in Section 4.2
2. Keep only the largest & entries of wavelet bases for each node, i.e.
on
if tho topk Vop otherwise,
where topK is a partial sorting function that returns the largest entries from a set of wavelet bases (P....... VeN) }. This technique guarantees attention sparsity such that the embedding each node can be aggregated from at most k other nodes. However, it takes more computational overhead to sort entries since topK has time complexity of O(N + k log N).
4

---

Under review as a conference paper at ICLR 2021
Table I:
Dataset statistics, We categorize the datasets into assortative and disassortative based on their homophily (3).
Category
Dataset
#Nodes
#Edges
#Classes
#Features
Density
B
CORA
2,708
5,429
1,433
1.44c-3
0.83
Assortative
CITESEER
3,327
4,732
3,703
8. 8.23c-4
0.71
PUBMED
19,717
44,338
3
500
2.28e-4
0.79
CORNELL
183
298
1.703
1.68e-2
0.11
TEXAS
183
325
5
1,703
1.77e-2
0,06
Disassortative
WISCONSIN
251
515
5
1,703
1.49e-2
0.16
CHAMELRON
2277
36101
2,325
1.21e-2
0.25
The resulting v from either of the above techniques is then fed into the softmax layer to compute attention weights. The experiments for comparing these techniques will be discussed Section 4.2
We adopt multi-head attention to model multiple spectral filters. Each attention head aggregates node information with a different spectral filter, and the aggregated embedding is concatenated before being sent the next layer. We allocate an independent MI.P for each of attention heads; however, found independent MLPs tend to learn spectral filters of similar shapes. Hence, we adopt a single MLP: E V where M is the number of attention heads, and each column of the output corresponds to one adaptive spectral filter.
We name the multi-head spectral attention architecture global node attention network (GNAN). The design of GNAN is easily generalizable, and many existing GNNs can be expressed as special cases of GNAN (see [Appendxx Dj. Figure Iillustrates how GNAN works with two attention heads learned from the CITESEER dataset. As shown in the illustration, the MLP learns adaptive filters such as low-band pass and high-band pass filters. low-band pass filter assigns high attention weights in local neighborhoods, while high-band pass filter assigns high attention weights far-distant nodes, which cannot be captured by a one-hop aggregation scheme.
4 EXPERIMENTS
To evaluate the performance of our proposed model, conduct experiments on node classification tasks with assortative graph datasets, where the labels of nodes exhibit strong homophily, and disassortative graph datasets, where the local homophily is weak and labels of nodes represent their structural roles. To quantify the assortativeness of graphs, we use the metric 3 introduced by Pei et al. (2020).
8
1 V
Σ
B, and B, Hu E Nole(u) {(u)
[N
NEV
where ((v) refers to the label of node 3 measures the homophily of graph, and B, measures the homophily node the graph. A graph has strong local homophily 3 is large and vice versa.
4.1 EXPERIMENTAL SETUP
Baseline methods. We evaluate two variants of GNAN which only differ in the method used for sparsification: one adopts Equatiinn 5ccalled GNAN-T, and the other adopts (qquatinnn called GNAN-K. We compare both variants against 11 benchmark methods: vanilla GCN (Kipf & Welling 2017] and its simplified version SGC (Wu al. 2019: two spectral methods, one using the Cheby- shev polynomial spectral filters (Defferrard et al. 2016) and the other using the auto-regressive moving average (ARMA) filters (Bianchi et al. 2019); the graph attention model GAT (Velickovic et al. 2018); APPNP which allows adaptive neighbourhood aggregation using personalized page rank Kliepera et al. 2019a): three sampling-basse based approaches, GraphSage (Hamilton et al. (017). FastGCN Chen et al. (2018) and ASGCN (Huang et al.) 2018); and Geom-GCN which targets prediction on disassortative graphs (Pei et al. (2020). We also include MLP in the baselines since
performs better than many GNN-based methods on disassortative graphs (Liu al., 2020
5

---

Under review as a conference paper at ICLR 2021
Table Micro-FI results for node classification. The proposed model consistently outperforms the other variants of GNN on disassortative graphs and performs comparably on assortative graphs.
Method
CORA
CITESEER
PUBMED
CORNELL
TEXAS
WISCONSIN
CHAMELEON
GCN
8744 0.2
78.5 0.5
87.8 - 0.2
59.2 3.2
64.1 + 4.9
64.1 i 6.3
67.6
Chehyshev
88.2 + 0.2
7.4
89.3 + 0.3
9.4
79.7 5.0
82.5 + 2.8
66.0 2.3
ARMA
85.2+22 2.5
7
8.73+5.7
74.9
82.2 2.12+5.1
78.4 +5.4+4.0
62.1 +36
GAT
87.6 0.3
77.7
0.1
3.3
60.0 5.7
62.0+5522
64.9
SGC
87.2 0.3
78.8
0.3
4.6
5.1
51.8
33.7
GraphSAGE
86.3
77.4
89.2 0.5
67.3
82.7
77.6 4.6
51.1 + 0.5
APPNP
8.34
77.6 0.6
86.0 0.3
70.3 9.3
79.5
81.2 2.5
45.3 + 1.6
FastGCN
86.1
78.1
86.0 0.8
72.7
68.4
68.8 5.4
42.8 + 2.4
ASGCN
8.4
77.9
88.0
73.0
08.1 7.7
66.3 + 6.5
49.5 + 1.5
Geom-GCh
86.3
81.
89.1 0.1
75.4
73.5
80.4
68.0
MI.P
72.1+
74.9 +
88.6 + 0.2
81.4 6.3
79.2 + 6.1
82.7 + 4.5
48.5
GNAN-T*
87.5 0.5 0.5
79.0 + 1.1
89.9 0.9
82.7 8.3
85.1 + 5.7
85.9 1 3.8
66.1 3.1
G
87.2 0.3 0.3
79.3 1 0.6
88.7 1 0.5
8144 1 10.1
82.4 + 5.1
86.3 3.7
68.7 : 2.8
Datasets. We evaluate our model and the baseline methods on node classification tasks over three citation networks: CORA, CITESEER and PUBMED (Sen et al.) 2008), three webgraphs from the WebKB da WISCONSIN, TEXAS and CORNELL, and another webgraph from Wikipedia called CHIMMELEN (Rozemberezki et al. 2019p. We divide these datasets into two groups, assortative and disassortative, based on their 3. The details of these datasets are summarized in Table
Hyper-parameter settings. For the citation networks, we follow the experimental setup for node classification from (Hamilton et al.) 2017 Huang et al., 2018 Chen et al., 2018) and report the results averaged on 10 runs. For the webgraphs, we run each model on the 10 splits provided by (Pei et al., (020) and take the average, where each split uses 60%, 20%, and 20% nodes of each class for training, validation and testing, respectively. The results we report on GCN and GAT are better than Pei et al. (2020) due converting the graphs to undirected before training Fl uses node embeddings pre-trained from different methods such as Isomap (Tenenbaum et al. 2000), Poincare (Nickel & Kiela, 2017) and struc2vee (Ribeiro et al. 2017). We hereby report the best micro-F1 results among all variants for Geom-GCN.
Geom-
We use the best-performing hyperparameters specified in the original papers of baseline methods. For hyperparameters not specified in the original papers, we use the parameters from (Fey & Lenssen 2019). We report the test accuracy results from epochs with the smallest validation loss and highest validation accuracy. Early termination is adopted for both validation loss and accuracy, and the training thus stopped when neither of validation loss and accuracy improve for 100 consecutive epochs. We use two-layer GNAN where multi-head's filters are learned using MLP of 2 hidden layers and then approximated by Chebyshev polynomials. Each layer of the MLP consists of a linear function and ReLU activation. To avoid overfitting, dropout is applied in each GNAN layer both attention weights and inputs equally.
4.2 RESULTS AND DISCUSSION
We use two evaluation metries to evaluate the performance of node classification tasks: micro-FI and macro-F1. The results with micro-F1 are summarized in Table 2, and the results with macro-Fl are provided in Table in the appendix. Overall, on assortative citation networks, GNAN performs comparably with the -tate-of-the-art methods, ranking first PUBMED and second on CORA and CITESEER terms of micro-Fl scores. On disassortative graphs, GNAN outperforms all the state- of-the-art methods by margin of at least 2.4% and MLP by margin of at least 1.3%. These results indicate that GNAN can learn spectral filters adaptively based on different characteristics of graphs.
Although our model GNAN performs well on both assortative and disassortative graphs, it is unclear how GNAN performs on disassortative nodes whose neighbors are mostly of different classes in an assortative graph. Thus, report average classification accuracy disassortative nodes at different levels of B, in Figure 2 for the assortative graph datasets CITESEER and PUBMED. The
httes://geenarreeeen/////omoiiss httrrroootcctthhoooeoeoe htw.hhhhoettt 11 1eeeeooo1//w////// www/wwwb.

---

Under review as a conference paper at ICLR 2021
(a) CiteSeer
(b) PubMed
1.0
1.0
GCN
Micro-F1 (accuracy)
GAT
0.8
0.8
SGC
Cheby
0.6-
0.6
APPNP
ARMA
0.4
0.4
GNAN
0.2
0.2
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.2
0.3
0.4
0.5
Bv
Figure 2: Micro-FI results for classification accuracy on disassortative nodes (3, 0.5). GNAN shows better accuracy on classifying disassortative nodes than the other methods.
nodes are binned into five groups based on 3g. For example, all nodes with 0.3 < 3. S 0.4 belong to the bin 0.4. We have excluded CORA from the report since it has very few nodes with low S...
The results in Figure 2 show that all GNNs based on local aggregation schemes perform poorly when 3, low. One may argue that the performance on disassortative graphs might improve by stacking multiple GNN layers together to obtain information from far-distant nodes. However, it turns out that this approach introduces an oversmoothing problem in local aggregation- based GNNs (Li et al.) 2018). On the other hand, GNAN outperforms the other GNN-based methods on disassortative nodes, suggesting that adaptive spectral filters reduce local noise in aggregation while allowing far-distant nodes to be attended to.
The two variants of GNAN use slightly different sparsification techniques to speed up computation. For each node GNAN-T uses threshold é to eliminate low Vee.. (Equation 5), thereby sparsifying the resulting attention matrix. However, & cannot control the level of sparsification precisely. In comparison, GNAN-K keeps the l largest 6.. (Equation 6); therefore it guarantees a certain level of sparsification. Nonetheless, GNAN-K requires partial sorting which adds overhead of (n llog N). To further analyze the impact of attention sparsity on runtime, we plot the density of an attention matrix with respect to both & (Figure 3a 3n) and / (Figure 3 dd) The results are drawn from two datasets: the disassortative dataset CHAMELEON and the assortative dataset CORA. As expected, GNAN-K shows stable growth in the attention density as the value of ie increases. GNAN-T, on the other hand, demonstrates fluctuation in density with and reaches the lowest density at & = le 9 and t le 6 for CoRdand CHAMELEON, respectively. We observe that the attention weights tend to converge to similar small values on all nodes when goes beyond 0.001 in both datasets. To study how efficiency is improved via sparsification, we also plot the training time averaged over 500 epochs Figure 3] It shows that the model GNAN runs much faster when attention weights are well- sparsifiddd In experiments, are achieved on & < 20 for GNAN-K and f < le for GNAN-T. Thus, the model GNAN not only runs faster, but also performs better when attention weights well-sparsified.
Attention sparsificattin..
find the best results
Frequency range ablation. To understand how adaptive spectral filters contribute to GNAN's performance disassortative graphs, we conduct ablation study on spectral frequency ranges. We first divide the entire frequency range (0 ~ 2) into a set of predefined sub-ranges exclusively, and then manually set the filter frequency responses zero for each sub-range at a time in order to check the impact of each sub-range on the performance of classification. By doing so, the frequencies within selected sub-range do not contribute to neither node attention nor feature aggregation. therefore helping to reveal the importance of the sub-range. We consider three different lengths of sub-ranges, i.e., step=1.0, step=0.5, and step=0.25. The results of frequency ablation on the three assortative graphs are summarized in Figure 4 The results for step=1.0 reveal the importance of high- gegh-fre range (1 ~ 2) on node classification of disassortative graphs. The performances are significantly dropped by ablating high-frequency range on all datasets. Further investigation at the finer-leve sub-ranges (step=0.5) shows that sub-range 0.5 ~ 1.5 has the most negative impact on performance, whereas the most important sub-range varies across different datasets at the finest level (step=0.25). This finding matches our intuition that low low-pass filters used in GNNs underlie the local node homophily assumption in similar way naive local aggregation. We suspect the choice of
7

---

Under review as a conference paper at ICLR 2021
(a) GNAN-K on Chameleon
(b) GNAN-T on Chameleon
120
120
100%
Attention density
Time/epoch (ms)
100%
Time/epoch (ms)
110
110
Density
80%
Runtime per epoch
Density
80%
100
60%
60%
90
40%
40%
-60
80
20%
20%
-70
70
0%
0%
10a
10-
10
10a
1c-09
1c:07
16:03
k
(c) GNAN-K on Cora
(d) GNAN-T on Cora
100%
-200
100%
200
80%-
180
80%
180
Density
Density
60%
160
60%-
160
40%
140
40%
140
20%
20%
120
100
0%
0%
10a
10a
1s:08 1e-06
1e-04
k
t
Figure 3: Attention matrix density and training runtime with respect to k and t. Attention matrix is effectively sparsified by both k and I, which improves runtime efficiency. Note that the density is not monotonically increasing for GNAN-T since the threshold is applied to the "learnable" attention weights. When all values of th are below the density becomes 100% result of the softmax normalization.
low-pass filters also relates to oversmoothing issues in spectral methods (Li et al. 2018 but we leave it for future work.
Attention head ablation. In GNAN, each head uses a spectral filter to produce attention weights. To delve the importance of a spectral filter, we further follow the ablation method used by (Michel ablate one more filters by manually setting their attention weights to zeros. We then measure the impact on performance using micro-F1. If the ablation results in a large decrease in performance, the ablated filters are considered important. We observe that all attention heads (spectral filters) in GNAN are of similar importance, and only all attention heads combined produce the best performance. Please check Appendix C for the detailed results.
ct al. 2019). Specifically,
RELATED WORK
Graph neural networks have been extensively studied recently. We categorize work relevant to ours into three perspectives and summarize the key ideas.
Attention on graphs. Graph attention networks (GAT) (Velickovic al. 2018) was the first to introduce attention mechanisms on graphs. GAT assigns different importance scores to local neighbors via attention mechanism. Similar to other GNN variants, long-distance information propagation in GAT is realized by stacking multiple layers together. Therefore, GAT suffers from the oversmoothing issue (Zhao & Akoglu 2020). Zhang al. (2020) improve GAT by incorporating both structural and feature similarities while computing attention scores.
Spectral graph filters and wavelets. Some GNNs also use graph wavelets to extract information from graphs. [u et al.] (2019) applied graph wavelet transform defined by SShuaan et al. (2013) in GNNs. Klicpera et al. (2019b) proposed a general GNN argumentation using graph difrusion kernels to rewire the nodes. Donnat et al.) (2018) used heat wavelet to learn node embeddings in unsupervised ways and showed that the learned embeddings closely capture structural similarities between nodes. Other spectral filters used in GNNs can also be viewed as special forms of graph wavelets (Kipf & Welling 2017] Defferrard et al. 2016 Bianchi et al. 2019). Coincidentally. Chang et al. (2020) also noticed useful information carried by figgffreuuency components from graph Laplacian. Similarly, they attempted to utilize such components using node attentions. However, they resorted to the traditional choice of heat kernels and applied such kernels separately to low-frequency
8

---

Under review as a conference paper at ICLR 2021
Cornell
Texas
Wisconsin
(a) 2-layer GNAN, step = 1.0
(b) 2-layer GNAN step = 0.5
(c) 2-layer GNAN, step = 0.25
Micro-F1
0.8
0.8
0.8
0.6
0.6
0.6
no ablation
0.0
1.0
0.0
0.5
1.0
1.5
-2
0.25
0.5
0.75
1.0
1.25
1.5
1.75-2 2.0
1.75
0.0
0.5
1.0
1.5
0.25
0.75
0
1.25
1.5 1.5-1.16
1.0
Ablated frequency range
(d) 1-layer GNAN, step
1.0
(e)
1-layer GNAN, step 0.5
(f) 1-layer GNAN, step 0.25
Micro-F1
0.8
0.8
0.8
0.6
0.6
0.6
no ablation
0.0
1.0-2.0
0.5
0.5
1.0
1.0
1.5 2
0.25
75
0
1.25
1.5 1.511.75
1.5
1.75
2.0
1.0 10011
1.75-
0.0
0.5
7.75
1.25
Ablated frequency range
Figure 4: Micro-F1 with respect to an ablated frequency range on disassortative graphs. We divide the frequency range into set of sub-ranges with different lengths. The results (a) and (d) reveal the importance of beghffreyyency range (1 ~ 2). Further experiments show that there is a subtle difference in the most important range across datasets, but it ranges between (0.75 1.25).
and high-freee feeh-frequency components divided by a hyperparameter. In addition to this, their work did not link fegh-freyenncy components disassortative graphs
Prediction on disassortative graphs. Pei et al. (2020) have drawn attention to GCN and GAT's poor performance on disassortative graphs very recently. They tried to address the issue by essentially pivoting feature aggregation to structural neighborhoods from continuous latent space learned by unsupervised methods. Another attempt to address the issue was proposed by Liu et al. (2020). They proposed to sort locally aggregated node embeddings along one-dimensional space and used one-dimensional convolution layer to aggregate embeddings a second time. By doing so, non-local but similar nodes can be attended to.
Although our method shares some similaritics in motivation with the aforementioned work, it is fundamentally different in several aspects. To the best of our knowledge, learn spectral filters as part of supervised training on graphs. It is also the first architecture we know that computes node attention weights purely from learned spectral filters. As result, in contrast to commonly used heat kernel, our method utilizes high-frequency components of a graph, which helps prediction on disassortative graphs
method is the first to
CONCLUSION
In this paper, we study the node classification tasks on graphs where local node homophily weak. We argue the assumption of local homophily is the cause of poor performance on disassortative graphs. In order design more generalizable GNNs, we suggest that more flexible and adaptive feature aggregation scheme is needed. To demonstrate, we have introduced the global node attention network (GNAN) which achieves flexible feature aggregation using learnable spectral graph filters. By utilizing the full graph spectrum adaptively via the learned filters, GNAN is able aggregate features from nodes that are close and far. For node classification tasks, GNAN outperforms all benchmarks on disassortative graphs, and performs comparably graphs, GNAN also performs better for nodes with weak local homophily. Through our analysis, we find the performance gain is closely linked to the higher end of the frequency spectrum.
assortative graphs On assortative

---

Under review as a conference paper at ICLR 2021
REFERENCES
Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional ARMA filters. CoRR, abs/1901.01144 2019.
Heng Chang, Yu Rong, Tingyang Xu, Wenbing Huang, Somayeh Sojoudi, Junzhou Huang, and Wenwu Zhu. Spectral graph attention network. CoRR, 0bs/2200.00450, 2020.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering, In Advances in Neural Information Processing Systems (NewrIPS), pp. 3837-3845, 2016.
Claire Domnat, Marinka Zitnik. David Hallac, and Jure Leskovec. Learning structural node embeddings via diffusion wavelets. In Proceedings of 24th ACM International Conference of Knowledge Discovery Data Mining (KDD). pp. 1320-1329, 2018.
Matthias Fey and Jan Eric Lenssen, Fast graph representation learning with pytorch geometric. CoRR, abs/1903.02428, 2019.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Balaji Krishnapuram, Mohak Shah, Alexander J. Smola, Charu C. Aggarwal, Dou Shen, and Rajeev Rastogi (eds.), Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Son Francisco, CA, USA, August 13-17, 2016, pp. 855-864. ACM, 2016. doi: 1 R..114/9999922.299999
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 1024-1034, 2017.
David K. Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 2011. ISSN 10635203. doi: 10. 10166 20tch.20000.. 2010.04.005.
Wen-bing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representa- tion learning. In Samy Bengio, Hanna Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa Bianchi, and Roman Garnett (eds.). Advances Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018, Montréal, Canada, pp. 4563-4572, 2018.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th International Conference on Learning Representations (ICLR), 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In Proceedings of the 7th International Conference on Learning Representations (ICLR), 201 9a.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. In Advances Neural Information Processing Systems (NeurIPS), pp. 13333-13345, 2019b.
John Boaz Lee, Ryan Rossi, Xiangnan Kong. Graph classification using structural attention. In Proceedings of the 24th ACM International Conference on Knowledge Discovery & Data Mining (KDD), pp- 2018
Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence. and Kilian Q Weinberger (eds.). Advances in Neural Information Processing Systems 27; Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pp. 2177-2185, 2014.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In Proceedings of the 32nd Conference Artificial Intelligence (AAAI), pp. 3538-3545, 2018.
Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks. CoRR, abs/2005. 14612, 2020.
10

---

Under review as a conference paper at ICLR 2021
Paul Michel, Omer Levy, and Graham Neubig. Are sixteen heads really better than one? In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Bue, Emily B. Fox, and Roman Gamett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 14014-14024, 2019.
B. A. Miller, M. S. Beard, and N. T. Bliss. Matched filtering for subgraph detection in dynamic networks. In 2011 IEEE Statistical Signal Processing Workshop (SSP), pp. 509-512, 2011.
Edoardo Di Napoli, Eric Polizzi, and Yousef Saad, Efficient estimation of eigenvalue counts an interval. Numer. Linear Algebra Appl., 23(4))674-692, 2016. doi: 10. 10400///a.2048.
Maximilian Nickel and Douwe Kiela. Poincaré embeddings for learming hicrarchical representations. In Advances in Neural Information Processing Systems, 2017.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang. Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: online learning of social representations. In Sofus A. Macskassy, Claudia Perlich, Jure Leskovec, Wei Wang, and Rayid Ghani (eds.), The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14, New York, NY, USA August 24- 27, 2014. pp. 701-710. ACM, 2014. doi: 10.1 1444/622333.26227333
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, ptc, and node2vec. In Yi Chang, Chengxiang Zhai, Yan Liu, and Yoelic Maarck (ods.). Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, WSDM 2018, Marina Del Rey, CA, USA, February 5-9, 2018, pp. 459-467. ACM, 2018. doi:
10.1145/31596522315555
Leonardo F.R. Ribeiro. Pedro H.P. Saverese, and Daniel R. Figueiredo. Strue2vec: Learning node representations from structural identity. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2017. ISBN 9781450348874. doi: 10.1 145/3097983.3098006
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. CoRR, abs/1909.13022 2019.
Akic Sakiyama, Kana Watanabe, and Yuichi Tanaka. Spectral Graph Wavelets and Filter Banks with Low Approximation Error. IEEE Transactions on Signal and Information Processing over Networks, 2(3):230-244 2016. ISSN 2373776X. doi: 10. 109/TSIPN 201....13........1333.000.
Michael T. Schaub and Santiago Segarra. Flow smoothing and denoising: Graph signal processing in the edge- space. In 2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pp. 735-739, 2018.
Prithviraj Sen, Galileo Namata, Mustafa Bilgie, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification network data, Al Magazine, 29(3):93-100 1006 2008
David I. Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis networks and other irregular domains. IEEE Signal Process. Mag., 30(3)883-98, 2013.
Jian Tang. Meng Qu, and Qiaozhu Mei. PTE:
predictive text embedding through large-scale heterogeneous text networks. In Longbing Cao, Chengqi Zhang, Thorsten Joachims, Geoffrey I. Webb, Dragos D. Margineantu, and Graham Williams (eds.), Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015, pp. 1165-1174 ACM, 2015a. doi: 10. 20.1145/2783258..0 2773337
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. LINE: large-scale information network embedding, In Aldo Gangemi, Stefano Leonardi, and Alessandro Panconesi (eds.). Proceedings of the 24th International Conference on World Wide Web, WWW 2015, Florence, Italy, May 18-22, 2015, pp. 1067 1077. ACM, 2015b. doi: 10.1 1el.1144/73377.2271111
J. B. Tenenbaum. V. De Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 2000. ISSN 00368075. doi: 10.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In Proceedings of the 6th International Conference on Learning Representations (ICLR), 2018.
11

---

Under review as a conference paper at ICLR 2021
H. Wai, S. Segarra, A. Ozdaglar, A. Scaglione, and A. Jadbabaie. Community detection from low-rank excitations of graph filter. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4044 4048, 2018.
Felix Amauri H. Souza Tianyi Zhang, Christopher Fifty, and Kilian Q. Weinberger. Simplifying graph convolutional networks. Proceedings of the 36th International Conference on Machine Learning (ICML), volume 97, pp. 6861-6871, 2019.
Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu, and Xueqi Cheng. Graph wavelet neural network. Proceedings of the 7th International Conference on Learning Representations (ICLR), 2019.
Zhang, Yaokang Zhu, Jun Wang, and Jie Zhang. Adaptive structural fingerprints for graph attention networks. In Proceedings of the 8th International Conference on Learning Representations (ICLR), 2020.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle. Kristen Grauman, Nicolò Cesa- Biaachi, and Roman Gameet (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018, Montréal, Canada, pp. 5171-5181, 2018.
Lingxiao Zhao and Leman Akoglu. Paimorm: Tackling oversmoothing in gnns, In Proceedings of the 8th International Conference Learning Representations (ICLR), 2020.
12

---

Under review as a conference paper at ICLR 2021
APPENDIX
A GRAPH SPECTRAL FILTERING WITHOUT EIGEN-DECOMPOSITIO
Chebyshev polynomials approximation has been the de facto approximation method for avoiding eigen- decomposition in spectral graph filters. It has been commonly used in previous works Hammond ct al. (201) 1); Sakiyama al. (2016): Xu et al. (219)) We hereby use it to opproximate[Equationn 3] In fact. other approxima- tion methods also be used for the purpose, such the Jackson- -hekbchhh polynomials (Napoli et al. 2016
we will leave for future study. Briefly, in Chebyshev polynomial approximation. the graph signal liltered
by a filter g( (L) is approximated as ğ(L), and represented as a sum recursive polynomials (Sakiyama et al. 2016):
ū(L)x = {1
12
Σ
(8)
where To LL) 2(L 1) Amaz Ti(L) =4[]==4--- ((L-1)fi-/Amaa) (L), and
8
mi
2)
Amar
G
cos
cos
m=1
for 0, ..... P. where p is the approximation order, is the number of sampling points and is normally =-++1
In Equation 3 MLP is used to produce the filter responses so we have g = MLP in Equation 9 The above equation is differentiable so the parameters in MLP can be learned by gradient decent from the loss function. The above approximation has time complexity of O(p x [F]),, so that the complexity for Eqqation i also O(p |E]) Please note, while Chebyshev polynomials are mentioned in both our method and ChevNet, however they are used fundamentally different ways: ChevNet uses the simplified Chebysher polynomials as the polynomial filter directly, while we use as a method to approximate the filtering operation. Naturally, approximation error reduces while a larger is used, which is also why we have > 12 in our model.
B FURTHER EXPERIMENT RESULTS
We provide the macro-FI scores the classification task in Table 3 The proposed model outperforms the other models on disassortative graphs and performs comparable the assortative graphs.
Table 3: Macro-F1 for node classification task.
Method
CORA
CITESEER
PUBMED
CORNELL
TEXAS
WISCONSIN
CHAMELEON
GCN
86.0 0.3
72.0 + 1.6
86.8 0.2
24.1 9.1
34.0 5.7
37.6 9.2
Chebyshev
86.8 0.3
74.11:.0
8.3
13.6
64.1
12.4
62.9 7.7
65.9 2.4
ARMA
80.2 6.8
0.4
81.6 13.9
48.5
69.1
12.3
53.3
60.7 1 6.3
GAT
86.4 0.4
+
8.1
2.
6.8
30.0
SGC
86.0 0.3
74.7
0.3
2.5
7.5
6.3
31.3 4.4
GraphSAGE
85.2 0.1
74.2+
8.6
49.2 10.9
6.6
63.7 12.4
51.6 0.4
APPNP
$7.0
7.
0.3
39.6
6.8
5.78
44.0
FasIGCN
0.5
72.0
8.
47.6
7.5
41.8 1 10.6
40.3
ASGCN
0..
7..4+004
8..9
54.3 11.3
45.2
43.4 11.3
48.6 1.4
Geom-GCN
85.1
76.9
0.1
2.5
3.5
88.1 0.2
63.0
61.7 15.2
54.6 11.3
GNAN-T
0.4
74111.
89.2 + 1.0
66.6 + 15.3
72.0 = 10.6
63,5 + 7.0
65.7 3.4
GNAN-K*
87.2 0.3
79.3 0.6
87.9 1 0.8
64.3 20.1
66.3
13.1
64.6 1 6.2
68.5 2.2.1
C ABLATION STUDY ON FILTERS
We provide the detailed version of Figure (c) and (f) in Figure
We further ablated attention head to check the importance each head classification.
A Ablating all but one spectral filter. GNAN, each head uses a filter to produce spectral attention weights. To delve the importance of filter. we follow the ablation method used by (Michel et al. 2019). Specifically. we ablate one more filters by manually setting the attention scores to zeros. We then measure the impact on performance using micro-F1. If the ablation results in large decrease in performance, the ablated fitlerbank(s)
13

---

Under review as a conference paper at ICLR 2021
Micro-F1 (accuracy)
(a) 2-layer GNAN, step = 0.25
Legends
0.8
Cornell
Texas
Wisconsin
0.6
0.25
025-0.5
0.5
0.5-
0.75-1.0 1.0
1.0 1.25
1 1.5
1.5
-
0.25
0.5
0.0
Ablated frequency range
Micro-F1 (accuracy)
(b) 1-layer GNAN, step = 0.25
0.8
0.6
0.0 0.25
0.5
0.5
0.75 1.0
1.0
1.25
1.25 1.5
1.5-
1.75-2.0
0.25
1.0
Ablated frequency range
Figure 5: Full details of the performances on frequency ablation at 0.25 level.
considered important. The results are summarized in Table 4a All attention head (filters) in GNAN are of similar importance, and only all heads combined produces the hest performance.
Ablating only spectral filter. We then examine performance differences by ablating filter only keeping all other fitlerbanks Table 4b) Different with above, ablating just one fitlerbank only decreases performance by a small margin. Moreover, ablating some fitlerbanks does not impact prediction performance at all. This is an indicator of potential redundancies in the filters. We leave the redundancy reduction in the model for future work.
Table 4: Ablation study on attention head (filter). We use 12 attention heads for CORA and PUBMED,
and 14 heads for CITESBER.
(a) Test accuracy by keeping only one filter
Dataset
CUra
-2.10%
-2.10%
-1.30%
-1.50%
-2.10%
-1.30%
CITESBER
-1.8%
-1.9%
4.30%
-4.40%
4.40%
5.00%
4.30%
(b) Test accuracy by ablating only filter
Head
CORA
0.00%
0.00%
-0 1.300%
0.00%
-0.40%
0.00%
0.00%
0.00%
-0.40%
-0 11.40%
0.00%
-0.40%
CITESEER
-0.20%
-0.30%
-0.0%
-0.0%
0040%
00.00
-0.80%
0.008
-0.00%
0.00%
-.50%
-0.50%
0.00%
0.00%
-0.80%
-0.80%
0.00%
4080%
-0.70%
.080%
0,00%6
D CONNECTIONS TO OTHER METHODS
In this section, show GNAN has strong connection existing models, and many GNNs can be expressed as special case of GNAN under certain conditions.
D.1 CONNECTION TO GCN
GCN (Kipf & Welling 2017) layer he expressed as
14

---

Under review as a conference paper at ICLR 2021
ReLU( Σ
where aeu the elements from the uth row symmetric adjacency matrix
À D 1/2 11/AAD AD 1/2
where
A= A+ IN, Dov Σ Avu
So that
{1 if evu E 0 if emu E
Den
Therefore, GCN can be viewed a case of Equation with ReLU and deu ava
D.2 CONNECTION TO POLYNOMIAL. FILTERS
Polynomial filters localize in node's s K K-hopp neighbors utilizing K-order polynomials (Defferard et al. 2016). most of them takes the following form:
K-1
(A) = Σ O&A*
km0
where 0x is a learnable polynomial coefficient for each order. Thus a GNN layer using a polynomial filter becomes
ReLU Uga U0o(A) hw)
which be expressed using Equation with (K) IN.
ReLU and avu (Ugo(A)U In comparison, our method MLP leam the spectral filters instcad using a polynomial filter. Also, method, coefficients after sparsification and normalization are used as directly as attentions.
D.3 CONNECTION TO GAT
Our method is inspired by and closely related to GAT (Velickovic et al. 2018). To demonstrate the connection, we firstly define matrix & where each column &e is the transformed feature vector of node concatenated with feature vector of another node (including node itself) in the graph
du o WWh Wh.]
(10)
GAT multiplies each column of & with learnable weight vector and masks the result with the adjacency A hefore feeding the nonlinear function LeakyRelu and softmax calculate attention The masking can expressed as a Hadamard product with the adjacency matrix which the congruent a graph wavelet transform with the filter g(A) = I A:
A A
D =
(11)
And the GAT attention vector for node become
softmax(LeakyReL.U) Φe. 2 (b)))
(12)
where th is wthh row of after applying Equation with f 0, ② denotes Hadamard product, as of (Velickovic et al. 2018).
In comparison with our method, GAT incorporate node features in the attention score calculation, while node attentions in methods purely computed from the graph wavelet transform. Also, attentions in GAT are masked by A, which means the attentions restricted node e's 1-hop neighhours only.
15

---

Under review as a conference paper at ICLR 2021
D.4 CONNECTION TO SKIP-GRAM METHODS
Skip-gram models natural language processing are shown be equivalent to form matrix factorization
(Levy & Goldberg 2014). Recently Quu et al. 2018) proved that many Skip-Gram Negative Sampling (SGNS) models used in node embedding, including Deep Walk (Perozzi et al. 2014), LINE (Tang et 20155), PTE (Tang)
et al. 2015a), and node2vec (Grover & Leskovee 2016), are essentially factorizing implicit matrices closely related to the normalized graph Laplacian. The implicit matrices be presented graph wavelet transforms
on the graph Laplacian. For simplicity, we hereby use DeepWalk, generalized form of LINE and PTE, an
example. QQu et al. (2018) shows Welk effectively factorizes the matrix
vol(g)
log
P"D
P
D
log(()
(13)
where vol = E. Dev is the sum of node degrees, P = D- A is the random walk matrix, T is the skip-gram window size and b is the parameter for negative sampling. We know
LD D tut AJU" D
So Equation ca be written using graph Laplacian as:
log
vol(g)
Eu-
log(())
T
Or, after cigen-decomposition.cc as:
M = log
vol(g) Tb
D u CI- (T-
(14)
where U STT= AYU", denoted as bb.g. is wavelet transform with the filter Bag Meg(A) =E (1 - X)
Therefore, Walk can be special of Equation 4 where:
g/o
if k
a,
if v + u
voli Assigning H W = I, K and (X) log(
D XD²). We have
T6
h FACTORIZE(((a:))
(15)
where FACTORIZE is a matrix factorization operator of choice. Qiu et al. 2018) uses SVD in generalized
SGNS model, where the decomposed matrix Ua and Σg from M = U. is used to obtain the node embedding UdVEa
16


Reviews:
[{"review_id": "tZ4mRgfd_Yc", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work propose a new GNN architecture to help GNN break its limitation on only working over homophilic networks. The technical is to use introduce graph global attention. \n\nI think the paper is written okay. The motivation is clear. The solution is reasonable. However, I have following criticisms:\n1. This work has limited novelty. Observing that GCN cannot work well over heterophilic networks is not a new idea and observation. Using attention to capture the features from far-away nodes is natural but not novel. I do not think that it is reasonable to argue against other works, e.g. [1] that adopts the above idea by saying they are not expressive enough. Expressiveness sometimes may lead to model overfitting. Actually, ChevNet [2] can also capture far-aways nodes and be expressive enough. Why does it not work well? I guess that it is due to some overfitting issue. Moreover, if I understand it correctly, the limited difference between this work and [3] is most likely the global attention, which has very limited contribution. \n\n2. Although the work claims everywhere to tend to decrease the complexity, when computing the global attention, one still needs to do computation for every pair of nodes, which is of course not scalable for even medium-sized graphs. \n\n3. The heterophilic networks used for evaluation are very small with only several hundred nodes. Why not try larger ones, say actor, Cham. in [4]? I guess the computational issue comes from the global attention. \n\n[1] Non-Local Graph Neural Networks.\n[2] Convolutional neural networks on graphs with fast localized spectral filtering.\n[3] Graph wavelet neural network\n[4] Geom-gcn: Geometric graph convolutional networks.\n\n\n---post-discussion update----\nI would like to thank the authors for preparing the rebuttal and attending our discussion. However, I still think the complexity is a concern of this work. I do not think that Eq. (3) can be implemented within the complexity that the authors claimed. Moreover, if the authors use another way to compute the attention scores, that way should be very clearly stated instead of written in a different form. Given the high complexity, I cannot clearly see the advantage of this work in comparison to [1], as the non-local attention has been proposed in [1] already.\n\n[1] Non-Local Graph Neural Networks.", "extra_scores": {}, "extra_text": {}}, {"review_id": "PiW8rBImfGT", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "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": "I liked this paper quite a lot. Although this paper does not belong to my area of expertise, I was able to understand the paper clearly because of its lucid exposition. Experimentally, the authors show a novel GNN design with an attention module that has comparable performance to the MLP and outperforms other GNN designs. I believe that this will be a valuable contribution to many practical problems.\n\nUnfortunately, this work does not have any theoretical results, and evaluating the experimental results is outside my range of expertise. Therefore I would like to defer this paper to my fellow reviewers.", "extra_scores": {}, "extra_text": {}}, {"review_id": "PR5MVY4JryT", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Main Idea\n\nIn this paper, the authors study the problem of GCN for disassortative graphs. The authors proposed the GNAN method to allow attention on distant nodes indeed of limiting to local neighbors. The authors generalized the idea of graph wavelet with MLP to generate the attention score and utilized it to generate multiple attention heads. The authors carried out experiments on several real-world networks (4 assortative and 3 disassortative) with comparison to several state-of-art GCN methods.\n\nStrength:\nThe authors study a very interesting problem of GCN/graph embedding or disassortative graphs.\nThe proposed method is well motivated with solid theoretical motivation from graph wavelets. The proposed model is very intuitive generalization of graph wavelet methods.\nThe empirical evaluation is very thorough on seven networks with comparison to about 10 baselines of different kinds.\n\nWeakness:\nThough the authors mentioned the use of sparsification of attention for speed-up, however, it mentioned that t is set to zero. It is interesting to see how scalable the proposed method is as it needs to have global attention to possibly all nodes. An empirical comparison of running time would be very helpful.\n The authors only carry out experiments on three disassortative which are all very small. It would be interesting to see more experiments on disassortative graphs. Alternatively, it would be interesting to have an experiment on synthetic graphs where the \\beta can be controlled and varied smoothly to see how it affects the performance of different algorithms.\nThe authors picked only node classification of evaluation tasks. It is interesting to see how the disassortative could impact other tasks like graph reconstruction and link prediction. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a GNN that uses global attention based on graph wavelet transform for more flexible and data-dependent GNN feature aggregation without the assumption of local homophily.

Three reviewers gave conflicting opinions on this paper. The reviewer claiming rejection questioned the novelty of the paper and the complexity of the global attention mentioned in the paper. Even through the authors' responses and subsequent private discussions, concerns about complexity and novelty were not completely resolved.


Considering the authors' claim that the core contribution of this paper is to design fully learnable spectral filters without compromising computational efficiency, it is necessary to consider why it is meaningful to perform global attention based on graph wavelet transform in the first place. In terms of complexity, although the wavelet coefficient can be efficiently calculated using the Chebyshev polynomials mentioned by the authors, in the attention sparsification part, n log n is required **for each node** in sorting, resulting in complexity of n^2 or more. There may still be an advantage of complexity over using global attention in a message-passing architecture, but it will be necessary to clarify and verify that, given that the proposed method uses an approximation that limits global attention within K hops.

Also, this paper modifies the graph wavelet transform in graph theory, which requires a deeper discussion. For example, as the authors mentioned, the original wavelet coefficient psi_uv can be interpreted as the amount of energy that node v has received from node u in its local neighborhood. The psi_uv defined by the learnable filter as shown in Equation 3 has a different meaning from the original wavelet coefficient. There is insufficient insight as to whether it is justifiable to use this value as an attention coefficient.

Overall, the paper proposes potentially interesting ideas, but it seems to require further development for publication.
Decision: Reject