# Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs

Shouheng Li
The Australian National University
Canberra, Australia
<EMAIL_ADDRESS>&Dongwoo Kim
Pohang University of Science and Technology
Pohang, South Korea
&Qing Wang
The Australian National University
Canberra, Australia

###### Abstract

Graph neural networks (GNNs) have been extensively studied for prediction
tasks on graphs. As pointed out by recent studies, most GNNs assume local
homophily, i.e., strong similarities in local neighborhoods. This assumption
however limits the generalizability power of GNNs. To address this limitation,
we propose a flexible GNN model, which is capable of handling any graphs
without being restricted by their underlying homophily. At its core, this
model adopts a node attention mechanism based on multiple learnable spectral
filters; therefore, the aggregation scheme is learned adaptively for each
graph in the spectral domain. We evaluated the proposed model on node
classification tasks over eight benchmark datasets. The proposed model is
shown to generalize well to both homophilic and heterophilic graphs. Further,
it outperforms all state-of-the-art baselines on heterophilic graphs and
performs comparably with them on homophilic graphs.

††footnotetext: ECML-PKDD 2021, Bilbao, Spain

##  1 Introduction

Graph neural networks (GNNs) have recently demonstrated great power in graph-
related learning tasks, such as node classification [12], link prediction [42]
and graph classification [15]. 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-distance
nodes is propagated and aggregated by stacking multiple GNN layers together
[12, 37, 4]. However, this architecture underlies the assumption of local
homophily, i.e. proximity of similar nodes. While this assumption seems
reasonable and helpful to achieve good prediction results on homophilic graphs
such as citation networks [25], it limits GNNs’ generalizability to
heterophilic graphs. Heterophilic graphs commonly exist in the real-world, for
instance, people tend to connect to opposite gender in dating networks, and
different amino acid types are more likely to form connections in protein
structures [44]. Moreover, determining whether a graph is homophilic or not is
a challenge by itself. In fact, strong and weak homophily can both exhibit in
different parts of a graph, which makes a learning task more challenging.

Pei et al. [25] proposed a metric to measure local node homophily based on how
many neighbors of a node are from the same class. Using this metric, they
categorized graphs as homophilic (strong homophily) or heterophilic (weak
homophily), and showed that classical GNNs such as GCN [12] and GAT [37]
perform poorly on heterophilic graphs. Liu et al. [19] further showed that GCN
and GAT are outperformed by a simple multi-layer perceptron (MLP) in node
classification tasks on heterophilic 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 homophily does not hold.

Based on the above observation, we argue that a well-generalized GNN should
perform well on graphs regardless of homophily. Furthermore, since a 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 heterophilic 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 to find
similar nodes, or at least, resort to the node’s attributes to make a
prediction. Since the validity of the assumption about homophily is often
unknown, such aggregation strategies should be learned from data rather than
decided upfront.

To circumvent this issue, in this paper, we propose a novel GNN model with
attention-based adaptive aggregation, called ASGAT. Most existing attention-
based aggregation architectures perform self-attention to the local
neighborhood of a node [37]. Unlike these approaches, 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 a 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
information from frequency components and thus aggregate both local
information and global structure into node representations.

To further improve the generalizability of our model, instead of using
predefined spectral kernels, we propose to use multi-layer perceptrons (MLP)
to learn 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 [14, 40, 13]. They
are mostly low-pass filters, which means that these models implicitly treat
high-frequency components as “noises” and have them discarded [24, 33, 9, 2].
However, this may hinder the generalizability of models since high-frequency
components can carry meaningful information about local discontinuities, as
analyzed in [33]. Our model overcomes these limitations using node attentions
derived from fully learnable spectral filters.

To summarize, the main contributions of this work are as follows:

  1. 1.

We show that high-frequency components carry important information on
heterophilic graphs which can be used to improve prediction performance.

  2. 2.

We propose a generalized GNN model which performs well on both homophilic and
heterophilic graphs, regardless of graph homophily.

  3. 3.

We exhibit that multi-headed attention produced by multiple spectral filters
work better than attention obtained from a single filter, as it enables
flexibility to aggregate features from different frequency components.

We conduct extensive experiments to compare ASGAT with well-known baselines on
node classification tasks. The experimental results show that ASGAT
significantly outperforms the state-of-the-art methods on heterophilic graphs
where local node homophily is weak, and performs comparably with the state-of-
the-art methods on homophilic graphs where local node homophily is strong.
This empirically verifies that ASGAT is a general model for learning on
different types of graphs.††Our open-sourced code is available at
https://github.com/seanli3/asgat.

##  2 Preliminaries

Let ${\mathcal{G}}=(V,E,A,\bm{x})$ be an undirected graph with $N$ nodes,
where $V$, $E$, and $A$ are the node set, edge set, and adjacency matrix of
${\mathcal{G}}$, respectively, and $\bm{x}:V\mapsto\mathbb{R}^{m}$ is a graph
signal function that associates each node with a feature vector. The
normalized Laplacian matrix of ${\mathcal{G}}$ is defined as
${\bm{L}}={\bm{I}}-{\bm{D}}^{-1/2}{\bm{A}}{\bm{D}}^{-1/2}$, where
${\bm{D}}\in{\mathbb{R}}^{N\times N}$ is the diagonal degree matrix of
${\mathcal{G}}$. In spectral graph theory, the eigenvalues
$\Lambda=\text{diag}(\lambda_{1},...,\lambda_{N})$ and eigenvectors ${\bm{U}}$
of ${\bm{L}}={\bm{U}}\Lambda{\bm{U}}^{H}$ are known as the graph’s spectrum
and spectral basis, respectively, where ${\bm{U}}^{H}$ is the Hermitian
transpose of ${\bm{U}}$. The graph Fourier transform of $\bm{x}$ is
$\bm{\hat{x}}={\bm{U}}^{H}\bm{x}$ and its inverse is
$\bm{x}={\bm{U}}\hat{\bm{x}}$.

The spectrum and spectral basis carry important information on the
connectivity of a graph [33]. Intuitively, lower frequencies correspond to
global and smooth information on the graph, while higher frequencies
correspond to local information, discontinuities and possible noise [33]. One
can apply a spectral filter and use graph Fourier transform to manipulate
signals on a graph in various ways, such as smoothing and denoising [31],
abnormally detection [21] and clustering [38]. Spectral convolution on graphs
is defined as the multiplication of a signal ${\bm{x}}$ with a filter
$g(\Lambda)$ in the Fourier domain, i.e.

$g({\bm{L}})\bm{x}=g({\bm{U}}\Lambda{\bm{U}}^{H})\bm{x}={\bm{U}}g(\Lambda){\bm{U}}^{H}\bm{x}={\bm{U}}g(\Lambda)\hat{\bm{x}}.$
(1)

When a spectral filter is parameterized by a scale factor, which controls the
radius of neighbourhood aggregation, Equation 1 is also known as the Spectral
Graph Wavelet Transform (SGWT) [9, 33]. For example, Xu et al. [40] uses a
small scale parameter $s<2$ for a heat kernel, $g(s\lambda)=e^{-\lambda s}$,
to localize the wavelet at a node.

##  3 Proposed Approach

Figure 1: Illustration of a spectral node attention layer on a three-hop ego
network of the central node $v$ from the CiteSeer dataset. Node classes are
indicated by shape and color. Passing the graph through two learned 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 $v$ according to attention scores. 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 embeddings 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.

Graph neural networks (GNNs) learn lower-dimensional embeddings of nodes from
graph structured data. In general, given a node, GNNs iteratively aggregate
information from its neighbor nodes, and then combine the aggregated
information with its own information. An embedding of node $v$ at the $l$th
layer of GNN is typically formulated as

$\displaystyle{\bm{m}}_{v}$
$\displaystyle=\text{aggregate}(\\{{\bm{h}}^{(l-1)}_{u}|u\in{\mathcal{N}}_{v}\\})$
$\displaystyle{\bm{h}}^{(l)}_{v}$
$\displaystyle=\text{combine}({\bm{h}}^{(l-1)}_{v},{\bm{m}}_{v}),$

where ${\mathcal{N}}_{v}$ is the set of neighbor nodes of node $v$,
${\bm{m}}_{v}$ is the aggregated information from the neighbors, and
${\bm{h}}^{(l)}_{v}$ is the embedding of node $v$ at the $l$th layer
(${\bm{h}}^{(0)}_{v}={\bm{x}}_{v}$). The embedding ${\bm{h}}^{(L)}_{v}$ of
node $v$ at the final layer is then used for some prediction tasks. In most
GNNs, ${\mathcal{N}}_{v}$ is restricted to a set of one-hop neighbors of node
$v$. 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 a spectral attention layer that rewires a graph based on spectral
graph wavelets. A spectral graph wavelet $\bm{\psi}_{v}$ at node $v$ is a
modulation in the spectral domain of signals centered around the node $v$,
given by an $N$-dimensional vector

$\displaystyle\bm{\psi}_{v}={\bm{U}}g(\Lambda){\bm{U}}^{H}\delta_{v},$ (2)

where $g(\cdot)$ is a spectral filter and $\delta_{v}$ is a one-hot vector for
node $v$.

The common choice of a spectral filter is a heat kernel. A wavelet coefficient
$\psi_{vu}$ computed from a heat kernel can be interpreted as the amount of
energy that node $v$ 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) to learn spectral filters. With learnable spectral kernels,
we obtain the inverse graph wavelet transform

$\displaystyle\bm{\psi}_{v}={\bm{U}}\text{diag}(\text{MLP}(\Lambda)){\bm{U}}^{H}\delta_{v}.$
(3)

Unlike a low-pass heat kernel, where the wavelet coefficients can be
understood as the amount of energy after heat diffusion, the learned
coeffcients $\psi_{vu}$ do not always correspond to energy diffusion. In
spectral imaging processing, lower frequency components preserve an image’s
background, while higher frequency components are useful to detect object
edges or outlines. Similarly, in spectral graph theory, lower-frequency
components carry smoothly changing signals. Therefore a low-pass filter is a
reasonable choice to extract features and denoise a homophilic graph. In
contrary, higher-frequency components carry abruptly changing signals, which
correspond to the discontinuities and "opposite attraction" characteristics of
heterophilic graphs. Since $\text{MLP}(\Lambda)$ is learned in training, it
can learn a low-pass filter which works as a diffusion operator, while in
other cases, especially on heterophilic graphs, it converges to a high-pass
filer at most times (section 4).

Note that we use the terminology wavelet and spectral filter interchangeably
as we have relaxed the wavelet definition from [9] so that learnable spectral
filters in our work are not necessarily localized in the spectral and spatial
domains.

###### Remark 1

Equation 3 requires the eigen-decomposition of a Laplacian matrix, which is
expensive and infeasible for large graphs. To address this computational
issue, one may use well-studied methods such as Chebyshev [9, 40, 14] and
Auto-Regressive Moving-Average (ARMA) [11, 18] to efficiently compute an
approximate the graph filtering of MLP in Equation 3.

Attention mechanism. Unlike the previous work [40] where the output of inverse
graph wavelet transform are directly used to compute node embeddings, we
normalize the output through a softmax layer

$\displaystyle{\bm{a}}_{v}=\text{softmax}(\bm{\psi}_{v}),$ (4)

where ${\bm{a}}_{v}\in\mathbb{R}^{N}$ is an attention weight vector. With
attention weights, an update layer is then formalized as

$\displaystyle{\bm{h}}^{(l)}_{v}=\sigma\left(\sum_{u=1}^{N}{a}_{vu}{\bm{h}}^{(l-1)}_{u}{\bm{W}}^{(l)}\right),$
(5)

where ${\bm{W}}^{(l)}$ is a weight matrix shared across all nodes at the $l$th
layer and $\sigma$ is ELU nonlinear activation.

Note that the update layer is not divided into aggregation and combine steps
in our work. Instead, we compute the attention ${a}_{vv}$ directly from a
spectral filter. Unlike heat kernel and other spectral filters, the output of
inverse graph wavelet transform with a learnable spectral kernel are not
always localized. Hence, the model can adaptively aggregate information from
both close and far-distant nodes, depending on their attention weights.

Sparsified node attentions. With predefined localized spectral filters such as
a heat kernel, most of wavelet coefficients are zero due to their locality. In
our work, spectral filters are fully learned from data, consequently attention
weights obtained from learnable spectral filters do not impose any sparsity.
This means that to perform an aggregation operation we need to retrieve all
possible nodes in a graph, which is not efficient. From our experiments, we
observe that most attention weights are negligible after softmax. Thus, we
consider a sparsification technique to keep only the largest $k$ entries of
Equation 3 for each node, i.e.

$\displaystyle\bar{{\psi}}_{vu}=\begin{cases}{\psi}_{vu}&\quad\text{ if
}{\psi}_{vu}\in\text{topK}(\\{\psi_{v0},...,\psi_{vN}\\},k)\\\
-\infty&\quad\text{ otherwise},\end{cases}$ (6)

where topK is a partial sorting function that returns the largest $k$ entries
from a set of wavelet bases $\\{\psi_{v0},...,\psi_{vN}\\}$. This technique
guarantees attention sparsity such that the embedding of each node can be
aggregated from at most $k$ other nodes with a time complexity trade-off of
$O(N+k\log N)$. The resulting $\bar{\psi}$ is then fed into the softmax layer
to compute attention weights.

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 sent to the next layer. To
reduce redundancy, we adopt a single
MLP$:{\mathbb{R}}^{N}\rightarrow{\mathbb{R}}^{N\times M}$, 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 as a _adaptive spectral
graph attention network_ (ASGAT). The design of ASGAT is easily generalizable,
and many existing GNNs can be expressed as special cases of ASGAT (see
Appendix D). Figure 1 illustrates how ASGAT works with two attention heads
learned from the CiteSeer dataset. As shown in the illustration, the MLP
learns adaptive filters such as low-pass and high-pass filters. A low-pass
filter assigns high attention weights in local neighborhoods, while a high-
pass filter assigns high attention weights on far-distant but similar nodes,
which cannot be captured by a traditional hop-by-hop aggregation scheme.

##  4 Experiments

To evaluate the performance of our proposed model, we conduct experiments on
node classification tasks with homophilic graph datasets, and heterophilic
graph datasets. Further ablation study highlights the importance of
considering the entire spectral frequency.

###  4.1 Experimental Setup

Table 1: Micro-F1 results for node classification. The proposed model
consistently outperforms the GNN methods on heterophilic graphs and performs
comparably on homophilic graphs. Results marked with $\dagger$ are obtained
from Pei et al. [25]. Results marked with ${\ddagger}$ are obtained from Zhu
et al. [44].

| $\text{Homophily}\xLeftrightarrow{\hskip 170.71652pt}\text{Heterophily}$
---|---
| Cora | Pubmed | CiteSeer | Chameleon | Squirrel | Wisconsin | Cornell | Texas
$\beta$ | 0.83 | 0.79 | 0.71 | 0.25 | 0.22 | 0.16 | 0.11 | 0.06
#Nodes | 2,708 | 19,717 | 3,327 | 2,277 | 5,201 | 251 | 183 | 183
#Edges | 5,429 | 44,338 | 4,732 | 36,101 | 217,073 | 515 | 298 | 325
#Features | 1,433 | 500 | 3,703 | 2,325 | 2,089 | 1,703 | 1,703 | 1,703
#Classes | 7 | 3 | 6 | 5 | 5 | 5 | 5 | 5
GCN | $87.4\pm 0.2$ | $87.8\pm 0.2$ | $78.5\pm 0.5$ | ${59.8\pm 2.6}^{\ddagger}$ | ${36.9\pm 1.3}^{\ddagger}$ | $64.1\pm 6.3$ | $59.2\pm 3.2$ | $64.1\pm 4.9$
ChevNet | $88.2\pm 0.2$ | $89.3\pm 0.3$ | ${79.4}\pm 0.4$ | $66.0\pm 2.3$ | $39.6\pm 3.0$ | $82.5\pm 2.8$ | $76.5\pm 9.4$ | $79.7\pm 5.0$
ARMANet | $85.2\pm 2.5$ | $86.3\pm 5.7$ | $76.7\pm 0.5$ | $62.1\pm 3.6$ | $47.8\pm 3.5$ | $78.4\pm 4.6$ | $74.9\pm 2.9$ | $82.2\pm 5.1$
GAT | $87.6\pm 0.3$ | $83.0\pm 0.1$ | $77.7\pm 0.3$ | ${54.7\pm 2.0}^{\ddagger}$ | ${30.6\pm 2.1}^{\ddagger}$ | $62.0\pm 5.2$ | $58.9\pm 3.3$ | $60.0\pm 5.7$
SGC | $87.2\pm 0.3$ | $81.1\pm 0.3$ | $78.8\pm 0.4$ | $33.7\pm 3.5$ | $46.9\pm 1.7$ | $51.8\pm 5.9$ | $58.1\pm 4.6$ | $58.9\pm 6.1$
GraphSAGE | $86.3\pm 0.6$ | $89.2\pm 0.5$ | $77.4\pm 0.5$ | $51.1\pm 0.5$ | ${41.6\pm 0.7}^{\ddagger}$ | $77.6\pm 4.6$ | $67.3\pm 6.9$ | $82.7\pm 4.8$
APPNP | $\textbf{88.4}\pm 0.3$ | $86.0\pm 0.3$ | $77.6\pm 0.6$ | $45.3\pm 1.6$ | $31.0\pm 1.6$ | $81.2\pm 2.5$ | $70.3\pm 9.3$ | $79.5\pm 4.6$
Geom-GCN | $86.3\pm 0.3$ | $89.1\pm 0.1$ | $\textbf{81.4}\pm 0.3$ | $60.9^{\dagger}$ | $38.1^{\dagger}$ | $64.1^{\dagger}$ | $60.8^{\dagger}$ | $67.6^{\dagger}$
$\text{H}_{2}\text{GCN}$ | $88.3\pm 0.3$ | $89.1\pm 0.4$ | $78.4\pm 0.5$ | $59.4\pm 2.0$ | $37.9\pm 2.0$ | $86.5\pm 4.4$ | $82.2\pm 6.0$ | $82.7\pm 5.7$
MLP | $72.1\pm 1.3$ | $88.6\pm 0.2$ | $74.9\pm 1.8$ | $45.7\pm 2.7$ | $28.1\pm 2.0$ | $82.7\pm 4.5$ | $81.4\pm 6.3$ | $79.2\pm 6.1$
Vanilla ASGAT | $-$ | $-$ | $-$ | $-$ | $-$ | $\textbf{86.9}\pm 4.2$ | $\textbf{84.6}\pm 5.8$ | $82.2\pm 3.2$
ASGAT-Cheb | $87.5\pm 0.5$ | $\textbf{89.9}\pm 0.9$ | $79.3\pm 0.6$ | $\textbf{66.5}\pm 2.8$ | $\textbf{55.8}\pm 3.2$ | $86.3\pm 3.7$ | $82.7\pm 8.3$ | $\textbf{85.1}\pm 5.7$
ASGAT-ARMA | $87.4\pm 1.1$ | $88.3\pm 1.0$ | $79.2\pm 1.4$ | $65.8\pm 2.2$ | $51.4\pm 3.2$ | $84.7\pm 4.4$ | ${83.2}\pm 5.5$ | $79.5\pm 7.7$

Baseline methods.  An exact computation of Equation 3 requires to compute the
eigenvectors of the Laplacian matrix, which is often infeasible due to a large
graph size. To overcome this issue, we approximate graph wavelet transform
response of MLP with Chebyshev polynomial, dubbed as ASGAT-Cheb, and ARMA
rational function, dubbed as ASGAT-ARMA. We also report the results from the
exact computation of eigenvectors whenever possible, which is dubbed as
vanilla ASGAT.

We compare all variants against 10 benchmark methods, they are vanilla GCN
[12] and its simplified version SGC [39]; two spectral methods: ChevNet [4]
and ARMANet [1]; the graph attention model GAT [37]; APPNP, which also adopts
adaptive aggregation [13]; the neighbourhood-sampling method GraphSage [8];
Geom-GCN [25] and $\text{H}_{2}\text{GCN}$ [44], both also target prediction
on heterophilic graphs. We also include MLP in the baselines since it performs
better than many GNN methods on some heterophilic graphs [19].

Datasets. We evaluate our model and the baseline methods on node
classification tasks over three citation networks: Cora, CiteSeer and Pubmed
[32], three webgraphs from the WebKB
dataset††http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-11/www/wwkb/:
Wisconsin, Texas and Cornell, and webgraphs from Wikipedia called Chameleon
and Squirrel [29].

To quantify the homophily of graphs, we use the metric $\beta$ introduced by
Pei et al. [25],

$\beta=\frac{1}{N}\sum_{v\in V}\beta_{v}\text{\; and \;
}\beta_{v}=\frac{|\\{u\in{\mathcal{N}}_{v}|\ell(u)=\ell(v)\\}|}{|{\mathcal{N}}_{v}|},$
(7)

where $\ell(v)$ refers to the label of node $v$. $\beta$ measures the degree
of homophily of a graph, and $\beta_{v}$ measures the homophily of node $v$ in
the graph. A graph has strong local homophily if $\beta$ is large and vice
versa. Details of these datasets are summarized in Table 1.

Hyper-parameter settings.  For citation networks, we follow the experimental
setup for node classification from [8, 10, 3] and report the results averaged
on 10 runs. For webgraphs, we run each model on the 10 splits provided by [25]
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. [25] as a result of
converting the graphs to undirected before training
††https://openreview.net/forum?id=S1e2agrFvS. Geom-GCN uses node embeddings
pre-trained from different embedding methods such as Isomap [36], Poincare
[23] and struc2vec [28]. We report the best micro-F1 results among all three
variants for Geom-GCN.

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 and Lenssen [6]. 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,
thus training is stopped when neither validation loss or accuracy improve for
100 consecutive epochs. For ASGAT, we use a two-layer architecture where
multi-headed filters are learned using a MLP of 2 hidden layers. Each layer of
the MLP consists of a linear function and a ReLU activation. To avoid
overfitting, dropout is applied in each ASGAT layer on both attention weights
and inputs equally. Results for vanilla ASGAT are only reported for small
datasets where eigen-decomposition is feasible.

###  4.2 Results and Discussion

We use two evaluation metrics to evaluate the performance of node
classification tasks: micro-F1 and macro-F1. The results with micro-F1 are
summarized in Table 1. Overall, on homophilic citation networks, ASGAT
performs comparably with the state-of-the-art methods, ranking first on Pubmed
and second on Cora and CiteSeer in terms of micro-F1 scores. On heterophilic
graphs, ASGAT outperforms all other methods by a margin of at least $2.4\%$ on
3 out of 4 datasets. These results indicate that ASGAT generalizes well on
different types of graphs. The results with macro-F1 are summarized in Table
2. Macro-F1 scores have not been reported widely in the literature yet. Here,
we report the macro-F1 since the heterophilic graphs have imbalanced class
distributions than the homophilic graphs. As the results show, ASGAT
outperforms all other methods across all heterophilic graphs in macro-F1. The
difference between the two approximation methods is not significant. Except
for a few cases, the difference is largely attributed to hyperparameters
choices. The vanilla ASGAT gives more consistent results than the
approximations although the difference seems marginal.

Although ASGAT performs well on both homophilic and heterophilic graphs, it is
unclear how ASGAT performs on heterophilic neighbourhoods of an homophilic
graph where nodes are mostly of different classes. Thus, we report an average
classification accuracy on nodes at different levels of $\beta_{v}$ in Figure
2 on the homophilic graphs CiteSeer and Pubmed. The nodes are binned into five
groups based on $\beta_{v}$. For example, all nodes with $0.3<\beta_{v}\leq
0.4$ belong to the bin at $0.4$. We have excluded Cora from the report since
it has very few heterophilic neighbourhoods.

The results in Figure 2 show that all models except ASGAT perform poorly when
$\beta_{v}$ is low. One may argue that the performance on heterophilic 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 [17] which actually degrades performance. On the other
hand, the better performance of ASGAT on heterophilic nodes suggests the
adaptive spectral filters reduce noise aggregated locally while allowing far-
distant nodes to be attended to.

Attention sparsification. The restriction on top $k$ entries in Equation 6
guarantees a certain level of sparsification. Nonetheless, ASGAT requires a
partial sorting which adds an overhead of $O(n+k\log N)$. To further analyze
the impact of attention sparsity on runtime, we plot the density of an
attention matrix with varying $k$ in Figure 3 along with its running time. The
results are drawn from two datasets: the heterophilic dataset Chameleon and
the homophilic dataset Cora. As expected, ASGAT shows a stable growth in the
attention density as the value of $k$ increases. It also shows that ASGAT runs
much faster when attention weights are well-sparsified. In our experiments, we
find the best results are achieved on $k<20$.

Frequency range ablation. To understand how adaptive spectral filters
contribute to ASGAT’s performance on heterophilic graphs, we conduct an
ablation study on spectral frequency ranges. We first divide the entire
frequency range $(0\sim 2)$ into a set of predefined sub-ranges exclusively,
and then manually set the filter frequency responses to 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 a 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 homophilic graphs
are summarized in Figure 4.

The results for step=$1.0$ reveal the importance of high-frequency range
$(1\sim 2)$ on node classification of heterophilic graphs. The performance is
significantly dropped by ablating high-frequency range on all datasets.
Further investigation at the finer-level sub-ranges (step=$0.5$) shows that
ablating sub-range $0.5\sim 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-pass
filters used in GNNs underlie a homophily assumption in a similar way as naive
local aggregation. We suspect the choice of low-pass filters also relates to
oversmoothing issues in spectral methods [17], but we leave it for future
work.

Attention head ablation. In ASGAT, 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 et al. [20]. Specifically, we ablate
one or 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 ASGAT are
of similar importance, and only all attention heads combined produce the best
performance. Please check Appendix C for the detailed results.

Figure 2: Micro-F1 results for classification accuracy on heterophilic nodes
($\beta_{v}\leq 0.5$). ASGAT shows better accuracy on classifying heterophilic
nodes than the other methods. Figure 3: Attention matrix density and training
runtime with respect to $k$. Attention matrix sparsified by keeping the top
$k$ elements at each row, which effectively improves runtime efficiency.

Time complexity. In vanilla ASGAT, eigen-decomposition is required for
Equation 3 which has a time complexity of $O(N^{3})$. ASGAT-Cheb and ASGAT-
ARMA avoid eigen-decomposition and are able to scale to large graphs as their
time complexities are $O(R\times|E|)$ and $O((P\times T+Q)\times|E|)$
respectively, where $R$, $P$ and $Q$ are polynomial orders that are normally
less than $30$, $T$ is the number of iterations that is normally less than
$50$. Therefore, both ASGAT-Cheb and ASGAT-ARMA scale linearly with the number
of edges $|E|$. Readers can refer to Appendix B for a more detailed
introduction of these two methods. Secondly, partial sorting used in the
attention sparsification of Equation 6 requires $O(N+k\log N)$. Lastly,
Equation 4 is performed on a length-$k$ vector for $N$ rows; therefore, a time
complexity of $O(k\times N)$ is needed. In practice, we have $R\sim P\sim
T\sim Q\sim k\ll N\ll|E|$ for most graphs, therefore, for a model with $M$
heads, the overall time complexity is $O(M\times R\times|E|)$ for ASGAT-Cheb
and $O(M\times(P\times T+Q)\times|E|)$ for ASGAT-ARMA.

Figure 4: Micro-F1 with respect to ablated frequency sub-ranges on
heterophilic graphs. We divide the frequency range into a set of sub-ranges
with different lengths. The results (a) and (d) reveal the importance of high-
frequency range $(1\sim 2)$. Further experiments show that there is a subtle
difference in the most important range across datasets, but it ranges between
$(0.75\sim 1.25)$.

##  5 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) [37] was the first to
introduce attention mechanisms on graphs. GAT assigns different importance
scores to local neighbors via an 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
[43]. Zhang et al. [41] 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. Xu et al. [40] applied graph wavelet
transform defined by Shuman et al. [33] to GNNs. Klicpera et al. [14] proposed
a general GNN argumentation using graph diffusion kernels to rewire the nodes.
Donnat et al. [5] 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 [12, 4, 1]. Coincidentally, Chang et
al. [2] also noticed useful information carried by high-frequency components
from a 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 and high-
frequency components divided by a hyperparameter. In addition to this, their
work did not link high-frequency components to heterophilic graphs.

Prediction on heterophilic graphs. Pei et al. [25] have drawn attention to GCN
and GAT’s poor performance on heterophilic graphs very recently. They try to
address the issue by essentially pivoting feature aggregation to structural
neighborhoods from a continuous latent space learned by unsupervised methods.
Another attempt to address the issue was proposed by Liu et al. [19]. They
proposed to sort locally aggregated node embeddings along a one-dimensional
space and used a one-dimensional convolution layer to aggregate embeddings a
second time. By doing so, non-local but similar nodes can be attended to. Very
recently, Zhu et al. [44] showed a heuristic combination of ego-, neighbor and
higher-order embedding improves GNN performance on heterophilic graphs.
Coincidentally, they also briefly mentioned the importance of higher-frequency
components on heterophilic graphs, but they did not provide an empirical
analysis.

Although our method shares some similarities in motivation with the
aforementioned work, it is fundamentally different in several aspects. To the
best of our knowledge, our method is the first architecture we know that
computes multi-headed node attention weights purely from learned spectral
filters. As a result, in contrast to commonly used heat kernel, our method
utilizes higher-frequency components of a graph, which helps prediction on
heterophilic graphs and neighbourhoods. m

##  6 Conclusion

In this paper, we study the node classification tasks on graphs where local
homophily is weak. We argue the assumption of homophily is the cause of poor
performance on heterophilic graphs. In order to design more generalizable
GNNs, we suggest that a more flexible and adaptive feature aggregation scheme
is needed. To demonstrate, we have introduced the adaptive spectral graph
attention network (ASGAT) which achieves flexible feature aggregation using
learnable spectral graph filters. By utilizing the full graph spectrum
adaptively via the learned filters, ASGAT is able to aggregate features from
nodes that are close and far. For node classification tasks, ASGAT outperforms
all benchmarks on heterophilic graphs, and performs comparably on homophilic
graphs. On homophilic graphs, ASGAT 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.

## Acknowledgement

This work was partly supported by the National Research Foundation of
Korea(NRF) grant funded by the Korea government(MSIT) (No. 2020R1F1A1061667).

## References

  * Bianchi et al. [2019] Bianchi, F.M., Grattarola, D., Livi, L., Alippi, C.: Graph neural networks with convolutional ARMA filters. CoRR abs/1901.01343 (2019)
  * Chang et al. [2020] Chang, H., Rong, Y., Xu, T., Huang, W., Sojoudi, S., Huang, J., Zhu, W.: Spectral graph attention network. CoRR abs/2003.07450 (2020)
  * Chen et al. [2018] Chen, J., Ma, T., Xiao, C.: Fastgcn: 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), URL https://openreview.net/forum?id=rytstxWAW
  * Defferrard et al. [2016] Defferrard, M., Bresson, X., Vandergheynst, P.: Convolutional neural networks on graphs with fast localized spectral filtering. In: Advances in Neural Information Processing Systems (NeurIPS), pp. 3837–3845 (2016)
  * Donnat et al. [2018] Donnat, C., Zitnik, M., Hallac, D., Leskovec, J.: Learning structural node embeddings via diffusion wavelets. In: Proceedings of the 24th ACM International Conference of Knowledge Discovery & Data Mining (KDD), pp. 1320–1329 (2018)
  * Fey and Lenssen [2019] Fey, M., Lenssen, J.E.: Fast graph representation learning with pytorch geometric. CoRR abs/1903.02428 (2019)
  * Grover and Leskovec [2016] Grover, A., Leskovec, J.: node2vec: Scalable feature learning for networks. In: Krishnapuram, B., Shah, M., Smola, A.J., Aggarwal, C.C., Shen, D., Rastogi, R. (eds.) Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, pp. 855–864, ACM (2016), doi:10.1145/2939672.2939754, URL https://doi.org/10.1145/2939672.2939754
  * Hamilton et al. [2017] Hamilton, W.L., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. In: Guyon, I., von Luxburg, U., Bengio, S., Wallach, H.M., Fergus, R., Vishwanathan, S.V.N., Garnett, R. (eds.) Advances in 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), URL http://papers.nips.cc/paper/6703-inductive-representation-learning-on-large-graphs
  * Hammond et al. [2011] Hammond, D.K., Vandergheynst, P., Gribonval, R.: Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis (2011), ISSN 10635203, doi:10.1016/j.acha.2010.04.005
  * Huang et al. [2018] Huang, W., Zhang, T., Rong, Y., Huang, J.: Adaptive sampling towards fast graph representation learning. In: Bengio, S., Wallach, H.M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., Garnett, R. (eds.) Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada, pp. 4563–4572 (2018), URL http://papers.nips.cc/paper/7707-adaptive-sampling-towards-fast-graph-representation-learning
  * Isufi et al. [2017] Isufi, E., Loukas, A., Simonetto, A., Leus, G.: Autoregressive Moving Average Graph Filtering. IEEE Transactions on Signal Processing 65(2), 274–288 (2017), ISSN 1053587X, doi:10.1109/TSP.2016.2614793
  * Kipf and Welling [2017] Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. In: Proceedings of the 5th International Conference on Learning Representations (ICLR) (2017)
  * Klicpera et al. [2019a] Klicpera, J., Bojchevski, A., Günnemann, S.: Predict then propagate: Graph neural networks meet personalized pagerank. In: Proceedings of the 7th International Conference on Learning Representations (ICLR) (2019a)
  * Klicpera et al. [2019b] Klicpera, J., Weißenberger, S., Günnemann, S.: Diffusion improves graph learning. In: Advances in Neural Information Processing Systems (NeurIPS), pp. 13333–13345 (2019b)
  * Lee et al. [2018] Lee, J.B., Rossi, R.A., Kong, X.: Graph classification using structural attention. In: Proceedings of the 24th ACM International Conference on Knowledge Discovery & Data Mining (KDD), pp. 1666–1674 (2018)
  * Levy and Goldberg [2014] Levy, O., Goldberg, Y.: Neural word embedding as implicit matrix factorization. In: Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N.D., Weinberger, K.Q. (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), URL http://papers.nips.cc/paper/5477-neural-word-embedding-as-implicit-matrix-factorization
  * Li et al. [2018] Li, Q., Han, Z., Wu, X.: Deeper insights into graph convolutional networks for semi-supervised learning. In: Proceedings of the 32nd Conference on Artificial Intelligence (AAAI), pp. 3538–3545 (2018)
  * Liu et al. [2019] Liu, J., Isufi, E., Leus, G.: Filter Design for Autoregressive Moving Average Graph Filters. IEEE Transactions on Signal and Information Processing over Networks 5(1), 47–60 (2019), ISSN 2373776X, doi:10.1109/TSIPN.2018.2854627
  * Liu et al. [2020] Liu, M., Wang, Z., Ji, S.: Non-local graph neural networks. CoRR abs/2005.14612 (2020), URL https://arxiv.org/abs/2005.14612
  * Michel et al. [2019] Michel, P., Levy, O., Neubig, G.: Are sixteen heads really better than one? In: Wallach, H.M., Larochelle, H., Beygelzimer, A., d’Alché-Buc, F., Fox, E.B., Garnett, R. (eds.) Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 14014–14024 (2019), URL http://papers.nips.cc/paper/9551-are-sixteen-heads-really-better-than-one
  * Miller et al. [2011] Miller, B.A., Beard, M.S., Bliss, N.T.: Matched filtering for subgraph detection in dynamic networks. In: 2011 IEEE Statistical Signal Processing Workshop (SSP), pp. 509–512 (2011)
  * Napoli et al. [2016] Napoli, E.D., Polizzi, E., Saad, Y.: Efficient estimation of eigenvalue counts in an interval. Numer. Linear Algebra Appl. 23(4), 674–692 (2016), doi:10.1002/nla.2048, URL https://doi.org/10.1002/nla.2048
  * Nickel and Kiela [2017] Nickel, M., Kiela, D.: Poincaré embeddings for learning hierarchical representations. In: Advances in Neural Information Processing Systems (2017), ISSN 10495258
  * NT and Maehara [2019] NT, H., Maehara, T.: Revisiting graph neural networks: All we have is low-pass filters. CoRR abs/1905.09550 (2019), URL http://arxiv.org/abs/1905.09550
  * Pei et al. [2020] Pei, H., Wei, B., Chang, K.C., Lei, Y., Yang, B.: Geom-gcn: Geometric graph convolutional networks. In: 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, OpenReview.net (2020), URL https://openreview.net/forum?id=S1e2agrFvS
  * Perozzi et al. [2014] Perozzi, B., Al-Rfou, R., Skiena, S.: Deepwalk: online learning of social representations. In: Macskassy, S.A., Perlich, C., Leskovec, J., Wang, W., Ghani, R. (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.1145/2623330.2623732, URL https://doi.org/10.1145/2623330.2623732
  * Qiu et al. [2018] Qiu, J., Dong, Y., Ma, H., Li, J., Wang, K., Tang, J.: Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In: Chang, Y., Zhai, C., Liu, Y., Maarek, Y. (eds.) 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/3159652.3159706
  * Ribeiro et al. [2017] Ribeiro, L.F., Saverese, P.H., Figueiredo, D.R.: Struc2vec: Learning node representations from structural identity. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2017), ISBN 9781450348874, doi:10.1145/3097983.3098061
  * Rozemberczki et al. [2019] Rozemberczki, B., Allen, C., Sarkar, R.: Multi-scale attributed node embedding. CoRR abs/1909.13021 (2019), URL http://arxiv.org/abs/1909.13021
  * Sakiyama et al. [2016] Sakiyama, A., Watanabe, K., Tanaka, Y.: Spectral Graph Wavelets and Filter Banks with Low Approximation Error. IEEE Transactions on Signal and Information Processing over Networks 2(3), 230–245 (2016), ISSN 2373776X, doi:10.1109/TSIPN.2016.2581303
  * Schaub and Segarra [2018] Schaub, M.T., Segarra, S.: 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)
  * Sen et al. [2008] Sen, P., Namata, G., Bilgic, M., Getoor, L., Gallagher, B., Eliassi-Rad, T.: Collective classification in network data. AI Magazine 29(3), 93–106 (2008)
  * Shuman et al. [2013] Shuman, D.I., Narang, S.K., Frossard, P., Ortega, A., Vandergheynst, P.: The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Process. Mag. 30(3), 83–98 (2013)
  * Tang et al. [2015a] Tang, J., Qu, M., Mei, Q.: PTE: predictive text embedding through large-scale heterogeneous text networks. In: Cao, L., Zhang, C., Joachims, T., Webb, G.I., Margineantu, D.D., Williams, G. (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.1145/2783258.2783307, URL https://doi.org/10.1145/2783258.2783307
  * Tang et al. [2015b] Tang, J., Qu, M., Wang, M., Zhang, M., Yan, J., Mei, Q.: LINE: large-scale information network embedding. In: Gangemi, A., Leonardi, S., Panconesi, A. (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.1145/2736277.2741093, URL https://doi.org/10.1145/2736277.2741093
  * Tenenbaum et al. [2000] Tenenbaum, J.B., De Silva, V., Langford, J.C.: A global geometric framework for nonlinear dimensionality reduction. Science (2000), ISSN 00368075, doi:10.1126/science.290.5500.2319
  * Velickovic et al. [2018] Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., Bengio, Y.: Graph attention networks. In: Proceedings of the 6th International Conference on Learning Representations (ICLR) (2018)
  * Wai et al. [2018] Wai, H., Segarra, S., Ozdaglar, A.E., Scaglione, A., Jadbabaie, A.: Community detection from low-rank excitations of a graph filter. In: 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4044–4048 (2018)
  * Wu et al. [2019] Wu, F., Jr., A.H.S., Zhang, T., Fifty, C., Yu, T., Weinberger, K.Q.: Simplifying graph convolutional networks. In: Proceedings of the 36th International Conference on Machine Learning (ICML), vol. 97, pp. 6861–6871 (2019)
  * Xu et al. [2019] Xu, B., Shen, H., Cao, Q., Qiu, Y., Cheng, X.: Graph wavelet neural network. In: Proceedings of the 7th International Conference on Learning Representations (ICLR) (2019)
  * Zhang et al. [2020] Zhang, K., Zhu, Y., Wang, J., Zhang, J.: Adaptive structural fingerprints for graph attention networks. In: Proceedings of the 8th International Conference on Learning Representations (ICLR) (2020)
  * Zhang and Chen [2018] Zhang, M., Chen, Y.: Link prediction based on graph neural networks. In: Bengio, S., Wallach, H.M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., Garnett, R. (eds.) Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada, pp. 5171–5181 (2018)
  * Zhao and Akoglu [2020] Zhao, L., Akoglu, L.: Pairnorm: Tackling oversmoothing in gnns. In: Proceedings of the 8th International Conference on Learning Representations (ICLR) (2020)
  * Zhu et al. [2020] Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., Koutra, D.: Beyond homophily in graph neural networks: Current limitations and effective designs. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., Lin, H. (eds.) Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual (2020), URL https://proceedings.neurips.cc/paper/2020/hash/58ae23d878a47004366189884c2f8440-Abstract.html

## Appendix

##  Appendix A Further Experiment Results & Hyperparameter Details

Macro-F1. We provide the macro-F1 scores on the classification task in Table
2. The proposed model outperforms the other models on heterophilic graphs and
performs comparable on the homophilic graphs.

Table 2: Macro-F1 for node classification task. The proposed model
consistently outperforms other methods on heterophilic graphs and performs
comparably on homophilic graphs.

| $\text{Homophily}\xLeftrightarrow{\hskip 170.71652pt}\text{Heterophily}$
---|---
| Cora | Pubmed | CiteSeer | Chameleon | Squirrel | Wisconsin | Cornell | Texas
GCN | $86.0\pm 0.3$ | $86.8\pm 0.2$ | $72.0\pm 1.6$ | $-$ | $-$ | $37.6\pm 9.2$ | $24.1\pm 9.1$ | $34.0\pm 5.7$
ChevNet | $86.8\pm 0.3$ | $88.7\pm 0.3$ | $74.1\pm 1.0$ | $65.9\pm 2.4$ | $38.6\pm 3.2$ | $52.9\pm 7.7$ | $53.6\pm 17.6$ | $64.1\pm 12.4$
ARMANet | $80.2\pm 6.8$ | $81.6\pm 13.9$ | $66.4\pm 0.4$ | $60.7\pm 6.3$ | $47.3\pm 3.7$ | $53.3\pm 7.1$ | $48.5\pm 9.3$ | $69.1\pm 12.3$
GAT | $86.4\pm 0.4$ | $81.6\pm 0.1$ | $69.2\pm 1.0$ | $-$ | $-$ | $30.0\pm 5.2$ | $19.0\pm 2.8$ | $26.5\pm 6.8$
SGC | $86.0\pm 0.3$ | $79.8\pm 0.3$ | $74.7\pm 1.2$ | $31.3\pm 4.4$ | $45.3\pm 1.8$ | $35.9\pm 6.3$ | $21.9\pm 8.5$ | $23.2\pm 7.5$
GraphSAGE | $85.2\pm 0.1$ | $88.7\pm 0.6$ | $74.2\pm 0.6$ | $51.6\pm 0.4$ | $-$ | $63.7\pm 12.4$ | $49.2\pm 10.9$ | $62.9\pm 9.6$
APPNP | $\textbf{87.0}\pm 0.4$ | $84.8\pm 0.3$ | $70.2\pm 1.4$ | $44.0\pm 1.8$ | $29.0\pm 2.0$ | $55.8\pm 5.7$ | $39.6\pm 16.6$ | $61.0\pm 8.8$
Geom-GCN | $85.1\pm 0.3$ | $88.5\pm 0.1$ | $76.9\pm 0.5$ | $-$ | $-$ | $-$ | $-$ | $-$
$\text{H}_{2}\text{GCN}$ | $86.7\pm 0.4$ | $88.2\pm 0.4$ | $72.1\pm 1.9$ | $59.1\pm 1.8$ | $37.5\pm 3.2$ | $66.9\pm 11.8$ | $57.3\pm 12.4$ | $59.0\pm 6.6$
MLP | $67.2\pm 2.5$ | $88.1\pm 0.2$ | $67.6\pm 3.5$ | $44.3\pm 3.0$ | $26.6\pm 2.5$ | $54.6\pm 11.5$ | $63.0\pm 12.3$ | $61.7\pm 15.2$
Vanilla ASGAT | $-$ | $-$ | $-$ | $-$ | $-$ | $\textbf{67.0}\pm 10.0$ | $67.7\pm 8.8$ | $66.1\pm 8.0$
ASGAT-Cheb | $86.9\pm 0.3$ | $\textbf{89.2}\pm 1.0$ | $\textbf{79.3}\pm 0.6$ | $\textbf{68.5}\pm 2.1$ | $\textbf{55.8}\pm 3.3$ | $64.6\pm 6.2$ | $66.6\pm 15.3$ | $\textbf{72.0}\pm 10.6$
ASGAT-ARMA | $86.0\pm 1.2$ | $87.9\pm 1.3$ | $75.1\pm 2.0$ | $65.8\pm 2.2$ | $50.9\pm 3.3$ | $63.1\pm 10.3$ | $\textbf{68.2}\pm 10.0$ | $60.8\pm 16.3$

Sparsification parameter $k$. We hereby show how the sparsification parameter
$k$ in Equation 6 influences node classification peformance on a homophilic
graph (Cora) and a heterophilic graph (Chameleon) in Figure 5. The performance
on Cora increases with $k$ and stabilizes at $6<k<20$, with the exception of
$k=11$. In comparison, the performance on Chameleon is more sensitive to $k$,
as the prediction accuracy fluctuates when $k>1$. The sensitivity to $k$ can
be partially explained by the lack of homophilic communities on heteraphic
graphs.

Figure 5: Micro-F1 score with respect to the sparsification parameter $k$.

Hyperparameter details. The optimal hyperparameters for ASGAT are obtained by
grid search. For all the benchmark datasets, we set the polynomial order R=15
for ASGAT-Cheb, and P=12, Q=18 and T=30 for ASGAT-ARMA. The ranges of grid
search for other hyperparameters are summarised in Table 3.

Table 3: The grid search space for the hyperparameters. Hyperparameter | Range
---|---
Learning rate | 1e-4, 5e-4, 1e-3, 5e-3, 1e-2, 5e-2
Hidden size | 32, 64, 128, 256, 512
Weight decay | 1e-5, 1e-4, 1e-3
Heads | 2 - 18
Dropout | 0.1, 0.2, 0.4, 0.6, 0.8
k (in Equation 6) | 3 - 18

##  Appendix B Graph Spectral Filtering Without Eigen-decomposition

Graph filtering is an active research field. Polynomial approximator and
rational approximator are the two most well-known classes that are commonly
used to approximate eigen-decomposition in graph filtering. While ASGAT is
agnostic to approximation techniques, the technique used has a slight impact
on prediction performance due to errors in approximating Equation 3. It is
also worth noting that, although not discussed in this paper, there exist
other approximation methods like Jackson-Chebychev polynomials [22]. Below, we
briefly discuss two approaches: Chebyshev and ARMA, which we have used in the
experiment.

###  B.1 Chebyshev Polynomial Approximation

Chebyshev polynomials approximation is the de-facto method for graph Fourier
transform and is commonly used in previous works [9, 30, 40]. In Chebyshev
polynomial approximation, a graph signal $\bm{x}$ filtered by a filter
$g({\bm{L}})$ is represented as a sum of recursive polynomials [30]:

$g({\bm{L}})\bm{x}=\Big{\\{}\frac{1}{2}c_{0}+\sum_{i=1}^{p}c_{i}\bar{T}_{i}({\bm{L}})\Big{\\}}\bm{x}$
(8)

where $\bar{T}_{0}({\bm{L}})=1$,
$\bar{T}_{1}({\bm{L}})=2({\bm{L}}-1)/\lambda_{\max}$,
$\bar{T}_{i}({\bm{L}})=4({\bm{L}}-1)\bar{T}_{i-1}({\bm{L}})/\lambda_{\max}-\bar{T}_{i-2}({\bm{L}})$,
and

$\displaystyle c_{i}=\frac{2}{S}\sum_{m=1}^{S}$
$\displaystyle\cos\Big{(}\frac{\pi i(m-\frac{1}{2})}{S}\Big{)}\cdot$ (9)
$\displaystyle
g\Big{(}\frac{\lambda_{\max}}{2}\Big{(}\cos\Big{(}\frac{\pi(m-\frac{1}{2})}{S}+1\Big{)}\Big{)}\Big{)}$

for $i=0,...,R$, where $R$ is the approximation order, $S$ is the number of
sampling points and is normally set to $S=R+1$.

In Equation 3, MLP is used to produce filter responses, i.e., $g=\text{MLP}$.
The parameters in MLP are learned by gradient decent from a loss function via
the Chebychev approximation. The above approximation has a time complexity of
$O(R\times|E|)$. Naturally, approximation error reduces while a larger $R$ is
used, which is also why we have $R>12$ in our model. Please note, while
Chebyshev polynomials are mentioned in both our method and ChevNet, they are
used in fundamentally different ways: ChevNet uses the Chebyshev polynomials
with a small $R$ value as a polynomial filter directly, while we refer to its
traditional usage in graph signal processing as a method to approximate the
eigen-decomposition operation. Since approximation error reduces when a larger
$R$ is used, we thus uses $R>12$ in our implementation.

###  B.2 Auto-Regressive Moving-Average (ARMA) Rational Approximation

As a rational filter, ARMA is known to be more accurate than Chebyshev
polynomials [11, 18]. In ARMA, a spectral graph filter $g(L)$ is defined as a
rational function:

$\tilde{g}(\Lambda)=\frac{\sum_{q=0}^{Q}b_{q}\Lambda^{q}}{1+\sum_{p=1}^{P}a_{p}\Lambda^{p}}$
(10)

where $P$ and $Q$ are the hyper-parameters of polynomial order. $a_{p}$ and
$b_{q}$ are computed by minimizing

$\min_{a_{p},b_{q}}\Big{|}\Big{|}\tilde{g}(\Lambda)-g(\Lambda)\Big{|}\Big{|}^{2}$
(11)

Equation 11 is solved iteratively with the maximum number of iterations $T$.
There are different methods to calculate the filtered graph signals after
obtaining $a_{p}$ and $b_{q}$, we adopt the conjugate gradient method in the
implementation, where the filtered graph signal $\bm{y}$ is obtained by
solving the linear system [18]

$\sum^{P}_{p=0}a_{p}L_{p}\bm{y}=\sum_{q=0}^{Q}b_{q}L^{q}\bm{x}$ (12)

This ARMA filter has three hyper-parameters $P$, $Q$ and $T$. Its time
complexity is $O((P\times T+Q)\times|E|)$ which linearly scales with $|E|$.
ARMA filters are slightly less efficient than Chebyshev.

##  Appendix C Ablation study on filters

We provide further details for Figure 4 (c) and Figure 4 (f) in Figure 6.

Figure 6: Full details of the performances on frequency ablation at 0.25
level.

We further ablated attention heads to check the importance of each head in the
prediction tasks. Specifically, we ablate one or more attention heads by
manually setting the 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 head(s) is considered important. We
conduct two types of ablation following the method used by Michel et al. [20].

Ablating all but one spectral filter. To understand how each attention head
performs, we keep only one attention head and ablate all others. The results
are summarized in 4(a). We notice that ablating any head results in a decrease
in prediction performance. While the accuracy decrease varies per head, the
variance is small, indicating all attention head in ASGAT are of similar
importance, and only all heads combined produces the best performance.

Ablating only one attention head. We then examine performance differences by
ablating one head only and keeping all other heads 4(b). Different from the
above, ablation of some heads individually only results in a small performance
decrease, while performance is intact when other heads are ablated
individually. This is an indicator of potential redundancies in the attention
heads. We leave the redundancy reduction in the model for future work.

Table 4: Ablation study on attention head. We use 12 attention heads for Cora
and Pubmed, and 14 heads for CiteSeer.

(a) Test accuracy by keeping only one head

Dataset Head | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Cora | -2.10% | -2.10% | -1.30% | -2.10% | -1.50% | -2.10% | -2.10% | -2.10% | -1.40% | -1.50% | -2.10% | -1.30% | - | -
CiteSeer | -1.8% | -2.0% | -1.7% | -1.7% | -1.8% | -1.8% | -1.7% | -1.9% | -1.7% | -1.9% | -1.7% | -1.7% | -1.9% | -1.9%
Pubmed | -4.30% | -4.40% | -4.40% | -5.40% | -4.30% | -5.40% | -5.40% | -5.40% | -4.30% | -4.30% | -4.30% | -5.40% | - | -

(b) Test accuracy by ablating only one head

Dataset Head | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Cora | 0.00% | 0.00% | -0.30% | 0.00% | -0.40% | 0.00% | 0.00% | 0.00% | -0.40% | -0.40% | 0.00% | -0.40% | - | -
CiteSeer | -0.20% | -0.30% | -0.70% | -0.70% | -0.40% | -0.60% | -0.80% | 0.00% | -0.60% | 0.00% | -0.80% | -0.50% | 0.00% | 0.00%
Pubmed | -0.80% | -0.80% | -0.70% | 0.00% | -0.80% | 0.00% | 0.00% | 0.00% | -0.70% | -0.80% | -0.80% | 0.00% | - | -

##  Appendix D Connections to Other Methods

In this section, we show ASGAT has strong connection to existing models, and
many GNNs can be expressed as a special case of ASGAT under certain
conditions.

###  D.1 Connection to GCN

A GCN [12] layer can be expressed as

${\bm{h}}_{v}^{(l)}=\operatorname{ReLU}(\sum^{N}_{u=1}\hat{a}_{vu}{\bm{h}}_{u}^{(l-1)}{\bm{W}}^{(l)})$

where $\hat{a}_{vu}$ is the elements from the $v$-th row of the symmetric
adjacency matrix

$\hat{{\bm{A}}}=\tilde{{\bm{D}}}^{-1/2}\tilde{{\bm{A}}}\tilde{{\bm{D}}}^{-1/2}\quad\text{where}\quad\tilde{A}={\bm{A}}+{\bm{I}}_{N},\;\tilde{{D}}_{vv}=\sum_{u=1}^{N}\tilde{{A}}_{vu}$

So that

$\hat{a}_{vu}=\begin{cases}1&\text{if}\;e_{vu}\in E\\\ 0&if\;e_{vu}\notin
E\end{cases}$

Therefore, GCN can be viewed as a case of Equation 5 with
$\sigma=\operatorname{ReLU}$ and $a_{vu}=\hat{a}_{vu}$

###  D.2 Connection to Polynomial Filters

Polynomial filters localize in a node’s $K$-hop neighbors utilizing $K$-order
polynomials [4], most of them takes the following form:

$g_{\theta}(\Lambda)=\sum^{K-1}_{k=0}\theta_{k}\Lambda^{k}$

where $\theta_{k}$ is a learnable polynomial coefficient for each order. Thus
a GNN layer using a polynomial filter becomes

${\bm{h}}^{(l)}_{v}=\operatorname{ReLU}(\sum_{u=1}^{N}{\bm{U}}g_{\theta}(\Lambda){\bm{U}}^{T}{\bm{h}}_{u}^{(}l-1))$

which can be expressed using Equation 5 with ${\bm{W}}^{(k)}={\bm{I}}_{N}$,
$\sigma=\operatorname{ReLU}$ and
$a_{vu}=({\bm{U}}g_{\theta}(\Lambda){\bm{U}}^{T})_{vu}$. In comparison, our
method uses a MLP to learn the spectral filters instead of using a polynomial
filter. Also, our method introduces an attention mechanism on top of the
filtering response.

###  D.3 Connection to GAT

Our method is inspired by and closely related to GAT [37]. To demonstrate the
connection, we firstly define a matrix $\Phi$ where each column
$\bm{\phi}_{v}$ is the transformed feature vector of node $v$ concatenated
with feature vector of another node (including node $v$ itself) in the graph.

$\bm{\phi}_{v}^{(l)}=||_{j=0}^{N}[{\bm{W}}{\bm{h}}_{v}^{(l-1)}||{\bm{W}}{\bm{h}}_{u}^{(l-1)}],$
(13)

where ${\bm{W}}$ is a shared weight matrix, $h_{v}^{(l-1)}$ and
$h_{u}^{(l-1)}$ are the representation for node $v$ and $u$ from the layer
$l-1$. GAT multiplies each column of $\Phi$ with a learnable weight vector
$\bm{\alpha}$ and masks the result with the adjacency ${\bm{A}}$ before
feeding it to the nonlinear function $\operatorname{LeakyRelu}$ and
$\operatorname{softmax}$ to calculate attention scores. The masking can be
expressed as a Hadamard product with the adjacency matrix ${\bm{A}}$ which is
the congruent of a graph wavelet transform with the filter
$g(\Lambda)={\bm{I}}-\Lambda$:

$\Psi={\bm{A}}={\bm{D}}^{\frac{1}{2}}{\bm{U}}({\bm{I}}-\Lambda){\bm{U}}^{T}{\bm{D}}^{\frac{1}{2}}$
(14)

The GAT attention vector for node $v$ becomes

${\bm{a}}_{v}=\operatorname{softmax}(\operatorname{LeakyReLU}(\bm{\alpha}^{T}\bm{\phi}_{v}\odot\bm{\bar{\psi}}_{v}))$
(15)

where $\bm{\bar{\psi}}_{v}$ is the $v$-th row of $\Psi$, $\odot$ denotes the
Hadamard product, as in Velickovic et al. [37].

In comparison with our method, GAT incorporates node features in the attention
score calculation, while node attentions in our methods are purely computed
from the graph wavelet transform. Attentions in GAT are restricted to node
$v$’s one-hop neighbours only.

###  D.4 Connection to Skip-gram methods

Skip-gram models in natural language processing are shown to be equivalent to
a form of matrix factorization [16]. Recently Qiu et al. [27] proved that many
Skip-Gram Negative Sampling (SGNS) models used in node embedding, including
DeepWalk [26], LINE [35], PTE [34], and node2vec [7], are essentially
factorizing implicit matrices closely related to the normalized graph
Laplacian. The implicit matrices can be presented as graph wavelet transforms
on the normalized graph Laplacian. For simplicity, we use DeepWalk, a
generalized form of LINE and PTE, as an example. Qiu et al. [27] shows
DeepWalk effectively factorizes the matrix

$\log\left(\frac{\operatorname{vol}({\mathcal{G}})}{K}(\sum_{r=1}^{K}{\bm{P}}^{r}){\bm{D}}^{-1}\right)-\log(b)$
(16)

where $\operatorname{vol}({\mathcal{G}})=\sum_{v}{D}_{vv}$ is the sum of node
degrees, ${\bm{P}}={\bm{D}}^{-1}{\bm{A}}$ is the random walk matrix, $K$ is
the skip-gram window size (number of hops) and $b$ is the parameter for
negative sampling. We know that

${\bm{P}}={\bm{I}}-{\bm{D}}^{-\frac{1}{2}}{\bm{L}}{\bm{D}}^{\frac{1}{2}}={\bm{D}}^{-\frac{1}{2}}{\bm{U}}({\bm{I}}-\Lambda){\bm{U}}^{T}{\bm{D}}^{\frac{1}{2}}.$

So Equation 16 can be written using normalized graph Laplacian as:

$\log\left(\frac{\operatorname{vol}({\mathcal{G}})}{K}{\bm{D}}^{-\frac{1}{2}}\sum_{r=1}^{K}({\bm{I}}-{\bm{L}})^{r}{\bm{D}}^{\frac{1}{2}}\right)-\log(b).$

Or, after eigen-decomposition, as:

${\bm{M}}=\log\left(\frac{\operatorname{vol}({\mathcal{G}})}{Tb}{\bm{D}}^{-\frac{1}{2}}{\bm{U}}\sum_{r=1}^{K}({\bm{I}}-\Lambda)^{r}{\bm{U}}^{T}{\bm{D}}^{\frac{1}{2}}\right),$
(17)

where ${\bm{U}}\sum_{r=1}^{T}({\bm{I}}-\Lambda)^{r}{\bm{U}}^{T}$, denoted as
$\bm{\psi}_{sg}$, is a wavelet transform with the filter
$g_{sg}(\lambda)=\sum_{r=1}^{K}(1-\lambda)^{r}$. Therefore, DeepWalk can be
seen a special case of ASGAT by substituting MLP in Equation 3 with $g_{sg}$,
and $a_{v}u$ in Equation 5 with

$\displaystyle\bm{a}_{vu}=\begin{cases}{\psi}_{vu}&\quad\text{ if }d_{vu}\leq
K\\\ 0&\quad\text{ if }otherwise\end{cases}$

where $d_{vu}$ is the shortest distance between node $v$ and $u$. Assigning
${\bm{H}}={\bm{W}}={\bm{I}}$, $K=1$ and
$\sigma(X)=\log(\frac{\operatorname{vol}({\mathcal{G}})}{Tb}{\bm{D}}^{-\frac{1}{2}}{\bm{X}}{\bm{D}}^{\frac{1}{2}})$.
We have

${\bm{h}}^{\prime}_{v}=\operatorname{FACTORIZE}(\sigma(\bm{a_{v}}))$ (18)

where $\operatorname{FACTORIZE}$ is a matrix factorization operator of choice.
Qiu et al. [27] uses SVD in a generalized SGNS model, where the decomposed
matrix ${\bm{U}}^{\prime}$ and $\bm{\Sigma}^{\prime}$ from
${\bm{M}}={\bm{U}}^{\prime}\bm{\Sigma}^{\prime}{\bm{V}}^{\prime}$ is used to
obtain the node embedding
${\bm{h}}_{v}={\bm{U}}^{\prime}\sqrt{\bm{\Sigma}^{\prime}}$.

##  Appendix E Heat Kernel

Table 5 shows micro-F1 scores after substituting MLP in Equation 3 with a low-
pass heat kernel $g(\Lambda)=e^{-s\Lambda}$, where $s$ is a scaling parameter.
Results are reported for each dataset on the best performing $s$. While an
explicit heat kernel performs comparably on homophilic graphs (see Table 1),
it fails to perform well on heterophilic graphs due to its incapability to
capture high-frequency components. This results confirm the importance of an
adaptive wavelet kernel for model generalization to heterophilic graphs.
Vanilla ASGAT-Heat in this table uses the exact eigen-decomposition thus the
results are only reported for datasets where eigen-decomposition is feasible.
ASGAT-Heat-Chev uses the Chebyshev polynomial approximation described in
subsection B.1.

Table 5: Micro-F1 for node classification task with a low-pass heat kernel

| Vanilla ASGAT-Heat | ASGAT-Heat-Chev
---|---|---
Cora | $-$ | $85.5\pm 0.2$
CiteSeer | $-$ | $77.4\pm 0.8$
Chameleon | $-$ | $63.1\pm 2.1$
Wisconsin | $54.1\pm 5.1$ | $54.7\pm 4.6$
Cornell | $58.9\pm 3.1$ | $59.2\pm 3.2$
Texas | $58.6\pm 6.5$ | $58.6\pm 5.8$