summaries: The manuscript proposes a novel convolutional operator dubbed BankGCN, that given a node input signal, first projects it in different subspaces using a group of projection functions (one for each subspace), and then applies to each projection an adaptive filter.  As projection functions, the authors use Linear projections. The model was tested on the Graph classification task.

summaries: The authors introduce BankGCN, a graph convolutional network that learns (chebyshev) polynomial filters over the graph. BankGCN includes an initial subspace projection, and a cosine similarity regularization to encourage diverse filters. BankGCN is compared to a number of other graph networks on standard whole graph classification tasks.  The authors claim that most architectures of MPGCNs are limited in that they (1) focus on low frequency information and (2) lack a proper sharing scheme between filters, and that BankGCN addresses these two issues.

summaries: This paper proposes BankGCN, which simplifies spectral graph neural networks by utilizing an adaptive filter bank to extend the capabilities of GCNs beyond low-pass features. Compared to existing spectral graph convolutional networks, which have numerous free parameters, the proposed method reduces parameters by sharing learnable filters. The empirical study validates that BankGCN shows good performance on the graph classification task.

summaries: This paper proposes a new variant of GCN model, namely BankGCN, based on a novel graph convolutional operator. The main idea of BankGCN is to the sharing scheme among different filters to adaptively capture information from different frequencies. Through detailed discussion, BankGCN is claimed to be equivalent to the learnable message passing mechanism across K-hop neighborhood. Experiments on graph classification tasks over a collection of graph benchmark datasets demonstrate that BankGCN could outperform many state-of-the-art spectral-based GNNs.

abstractText: Graph convolutional networks have been a powerful tool in representation learning of networked data. However, most architectures of message passing graph convolutional networks (MPGCNs) are limited as they employ a single message passing strategy and typically focus on low-frequency information, especially when graph features or signals are heterogeneous in different dimensions. Then, existing spectral graph convolutional operators lack a proper sharing scheme between filters, which may result in overfitting problems with numerous parameters. In this paper, we present a novel graph convolution operator, termed BankGCN, which extends the capabilities of most MPGCNs beyond single ‘low-pass’ features and simplifies spectral methods with a carefully designed sharing scheme between filters. BankGCN decomposes multi-channel signals on arbitrary graphs into subspaces and shares adaptive filters to represent information in each subspace. The filters of all subspaces differ in frequency response and together form a filter bank. The filter bank and the signal decomposition permit to adaptively capture diverse spectral characteristics of graph data for target applications with a compact architecture. We finally show through extensive experiments that BankGCN achieves excellent performance on a collection of benchmark graph datasets.

authors:
Sami Abu-El-Haija
Bryan Perozzi
Amol Kapoor
Nazanin Alipourfard
Kristina Lerman
Hrayr Harutyunyan
Greg Ver Steeg
Aram Galstyan

title: Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing

venue: In Proc. 36th Int. Conf. Mach. Learn.,

authors:
Muhammet Balcilar
Renton Guillaume
Pierre Héroux
Benoit Gaüzère
Sébastien Adam
Paul Honeine

title: Analyzing the expressive power of graph neural networks in a spectral perspective

venue: In 9th Int. Conf. Learn. Rep.,

authors:
Filippo Maria Bianchi
Daniele Grattarola
Lorenzo Livi
Cesare Alippi

title: Graph neural networks with convolutional arma filters

venue: IEEE Trans. Pattern Anal. and Mach. Intell.,

authors:
Deyu Bo
Xiao Wang
Chuan Shi
Huawei Shen

title: Beyond low-frequency information in graph convolutional networks

venue: In Proc. 35th AAAI Conf. Artif. Intell.,

authors:
Joan Bruna
Wojciech Zaremba
Arthur Szlam
Yann LeCun

title: Spectral networks and locally connected networks on graphs

venue: In 2nd Int. Conf. Learn

authors:
Heng Chang
Yu Rong
Tingyang Xu
Wenbing Huang
Somayeh Sojoudi
Junzhou Huang
Wenwu Zhu

title: Spectral graph attention network with fast eigen-approximation

venue: In 30th ACM Int. Conf. Inf. Knowl. Manag.,

authors:
Eli Chien
Jianhao Peng
Pan Li
Olgica Milenkovic

title: Adaptive universal generalized pagerank graph neural network

authors:
Michaël Defferrard
Xavier Bresson
Pierre Vandergheynst

title: Convolutional neural networks on graphs with fast localized spectral filtering

venue: In Adv. Neural Inf. Process. Syst

authors:
Yushun Dong
Kaize Ding
Brian Jalaian
Shuiwang Ji
Jundong Li

title: Adagnn: Graph neural networks with adaptive frequency response filter

authors:
Vijay Prakash Dwivedi
Chaitanya K Joshi
Thomas Laurent
Yoshua Bengio
Xavier Bresson

title: Benchmarking graph neural networks

venue: arXiv preprint arXiv:2003.00982,

authors:
Matthias Fey
Jan E. Lenssen

title: Fast graph representation learning with PyTorch Geometric

venue: In ICLR Workshop on Representation Learning on Graphs and Manifolds,

authors:
Fernando Gama
Alejandro Ribeiro
Joan Bruna

title: Diffusion scattering transforms on graphs

venue: In 7th Int. Conf. Learn. Rep.,

authors:
Feng Gao
Guy Wolf
Matthew Hirn

title: Geometric scattering for graph data analysis

venue: In Proc. 36th Int. Conf. Mach. Learn., Long Beach, California,

authors:
Justin Gilmer
Samuel S. Schoenholz
Patrick F. Riley
Oriol Vinyals
George E. Dahl

title: Neural message passing for quantum chemistry

venue: In Proc. 34th Int. Conf. Mach. Learn.,

authors:
Will Hamilton
Zhitao Ying
Jure Leskovec

title: Inductive representation learning on large graphs

authors:
David K Hammond
Pierre Vandergheynst
Rémi Gribonval

title: Wavelets on graphs via spectral graph theory

venue: Appl. Comput. Harmon. Anal.,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In 2016 IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR),

authors:
Weihua Hu
Matthias Fey
Marinka Zitnik
Yuxiao Dong
Hongyu Ren
Bowen Liu
Michele Catasta
Jure Leskovec

title: Open graph benchmark: Datasets for machine learning on graphs

venue: In Adv. Neural Inf. Process

authors:
Kristian Kersting
Nils M. Kriege
Christopher Morris
Petra Mutzel
Marion Neumann

title: Benchmark data sets for graph kernels, 2016

authors:
Renata Khasanova
Pascal Frossard

title: Graph-based isometry invariant representation learning

authors:
Diederik P. Kingma
Jimmy Ba

venue: In 3rd Int. Conf. Learn

authors:
Thomas N. Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

venue: In 5th Int. Conf. Learn

authors:
Johannes Klicpera
Stefan Weißenberger
Stephan Günnemann

title: Diffusion improves graph learning

authors:
Junhyun Lee
Inyeop Lee
Jaewoo Kang

title: Self-attention graph pooling

authors:
Ron Levie
Federico Monti
Xavier Bresson
Michael M. Bronstein

title: CayleyNets: Graph convolutional neural networks with complex rational spectral filters

venue: IEEE Trans. Signal Process.,

authors:
Ron Levie
Wei Huang
Lorenzo Bucci
Michael M Bronstein
Gitta Kutyniok

title: Transferability of spectral graph convolutional neural networks

authors:
Qimai Li
Zhichao Han
Xiao-Ming Wu

title: Deeper insights into graph convolutional networks for semi-supervised learning

venue: In Proc. 32nd AAAI Conf. Artif. Intell.,

authors:
Shouheng Li
Dongwoo Kim
Qing Wang

title: Beyond low-pass filters: Adaptive feature propagation on graphs

venue: In ECML PKDD 2021 Joint Eur. Conf. Mach. Learn. Knowl. Discov. Databases,

authors:
Yimeng Min
Frederik Wenkel
Guy Wolf

title: Scattering GCN: overcoming oversmoothness in graph convolutional networks

authors:
Sunil K Narang
Antonio Ortega

title: Perfect reconstruction two-channel wavelet filter banks for graph structured data

title: Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs

authors:
Nicolò Navarin
Wolfgang Erb
Luca Pasa
Alessandro Sperduti

title: Linear graph convolutional networks

venue: In 28th Eur. Symp. Artif. Neural Netw., Comput. Intell. Mach. Learn.,

authors:
Hoang NT
Takanori Maehara

title: Revisiting graph neural networks: All we have is low-pass filters

venue: arXiv preprint arXiv:1905.09550,

authors:
Hoang NT
Takanori Maehara
Tsuyoshi Murata

title: Adaptive stacked graph filter, 2021

authors:
Luca Pasa
Nicolò Navarin
Alessandro Sperduti

title: Polynomial graph convolutional networks, 2021

title: Automatic differentiation in PyTorch

venue: In Adv. Neural Inf. Process. Syst., Autodiff Workshop,

authors:
Hongbin Pei
Bingzhe Wei
Kevin Chen-Chuan Chang
Yu Lei
Bo Yang

title: Geom-gcn: Geometric graph convolutional networks

venue: In 8th Int. Conf. Learn. Rep. OpenReview.net,

authors:
David I. Shuman
Sunil K. Narang
Pascal Frossard
Antonio Ortega
Pierre Vandergheynst

title: The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains

venue: IEEE Signal Process. Mag.,

authors:
Yuichi Tanaka
Akie Sakiyama

title: m-channel oversampled graph filter banks

authors:
Jie Tang
Jimeng Sun
Chi Wang
Zi Yang

title: Social influence analysis in large-scale networks

venue: In Proc. 15th ACM SIGKDD Int. Conf. Knowl. Disc. Data Min.,

authors:
Dorina Thanou
David I Shuman
Pascal Frossard

title: Learning parametric dictionaries for signals on graphs

authors:
Nicolas Tremblay
Paulo Gonçalves
Pierre Borgnat

title: Design of graph filters and filterbanks

venue: In Cooperative and Graph Signal Processing,

title: Graph attention networks

venue: In 6th Int. Conf. Learn. Rep., Vancouver, BC,

authors:
Felix Wu
Amauri Souza
Tianyi Zhang
Christopher Fifty
Tao Yu
Kilian Weinberger

title: Simplifying graph convolutional networks

authors:
Zonghan Wu
Shirui Pan
Guodong Long
Jing Jiang
Chengqi Zhang

title: Beyond low-pass filtering: Graph convolutional networks with automatic filtering

venue: arXiv preprint arXiv:2107.04755,

authors:
Keyulu Xu
Weihua Hu
Jure Leskovec
Stefanie Jegelka

title: How powerful are graph neural networks

venue: In 7th Int. Conf. Learn. Rep., New Orleans, LA,

title: Representation learning on graphs with jumping knowledge networks

venue: In Proc. 35th Int. Conf. Mach. Learn.,

authors:
Hao Zhu
Piotr Koniusz

title: Simple spectral graph convolution

authors:
Jiong Zhu
Yujun Yan
Lingxiao Zhao
Mark Heimann
Leman Akoglu
Danai Koutra

title: Beyond homophily in graph neural networks: Current limitations and effective designs

title: 2020) from the film-director-actor-writer network

authors: Fey Lenssen

title: The network architecture consists of two layers

authors:
Dong et al
Pasa

venue: (Li et al.,

heading: 1 INTRODUCTION

text:
In many application domains, structured data is supported by graphs or networks. To deal with such data, a collection of graph convolutional networks (GCNs), including MPGCNs and spectral GCNs, have been proposed by generalizing architectures used for data in the Euclidean domain, to the irregular graphs. Unfortunately, both types of architectures have implicit limitations when it comes to efficiently representing graph data information in terms of frequency filtering.
MPGCNs (Gilmer et al., 2017; Velikovi et al., 2018; Hamilton et al., 2017; Xu et al., 2019) built on diverse message passing (MP) schemes are much prevalent with their flexible and intuitive formulations of graph convolution. The message passing schemes in classical MPGCNs, however, mostly focus on the low frequency characteristics of the data. For example, GCN (Kipf & Welling, 2017) performs as Laplacian smoothing (Li et al., 2018), and the mean aggregator adopted in GraphSage (Hamilton et al., 2017) has naturally low-pass properties. However, in addition to low-frequency components, graph data may also carry rich information in the middle- and high-frequency ranges. There have been some recent attempts to complement low-pass features, either with predefined filters (Gao et al., 2019; Chang et al., 2021) or with other aggregation schemes (Abu-El-Haija et al., 2019; Zhu et al., 2020). Yet, they still have some limitations, such as the nonadaptiviy of predefined filters. The importance of different frequency components may vary with the target tasks, it is thus beneficial to be able to adapt the representation accordingly.
Spectral graph convolutional networks (Defferrard et al., 2016; Levie et al., 2018; Bianchi et al., 2021) are designed in the graph frequency domain directly and are much more powerful alternatives to process diverse spectral characteristics of graphs. The lack of proper sharing schemes between filters, however, renders these models redundant and even prone to overfitting.
We go beyond the above limitations and propose to build effective adaptive representations for graph data with diverse spectral properties. We design a novel graph convolution operator termed BankGCN that utilizes an adaptive filter bank to process graph data in the frequency domain, as presented in Fig. 1. BankGCN provides an effective implementation to simplify spectral methods
with a proper sharing scheme between filters with the help of signal decomposition. Firstly, we decompose multi-channel graph signals into a collection of subspaces through projection, in order to adaptively separate input data according to signal characteristics. Components in a subspace will then share a learnable filter that captures their particular frequency properties. Notably, representations are built on finite impulse response (FIR) filters with a universal design (Tremblay et al., 2018) that correspond to local message passing schemes in the spatial domain. Filters of all the subspaces together form a filter bank, and they are simultaneously learned from data together with subspace decomposition. The filter bank representation is regularized to favour diversity in the frequency responses, in order to properly capture various spectral components in the graph signals. The proposed convolution operator is stackable, and can be optimized together with other modules in the GCNs like graph pooling. We validate the proposed architecture through extensive experiments on various graph classification tasks. BankGCN is more powerful than most MPGCNs, such as GCN (Kipf & Welling, 2017), GraphSage (Hamilton et al., 2017), and GIN (Xu et al., 2019), in that it is able to exploit more diverse spectral characteristics than ‘low-pass’ features in the data and adapts to its heterogeneous properties with a group of learnable multi-hop message passing strategies. Furthermore, it outperforms its counterpart ChebNets (Defferrard et al., 2016) with a more compact architecture and achieves better generalization, and is superior to the most recent spectral method ARMA (Bianchi et al., 2021). It would be interesting to extend BankGCN to tasks like link prediction and applications into non-Euclidean data like 3-D point clouds.

heading: 2 RELATED WORK

text:
We briefly overview the main architectures for graph representation learning. We describe first existing message passing schemes, and then discuss several spectral methods.
Message Passing Graph Convolutional Networks. MPGCNs design graph convolution with a variety of message passing schemes in the spatial domain. For instance, messages are aggregated with the node-wise mean or max operation in a localized neighborhood in GraphSage (Hamilton et al., 2017), or based on attention scores in GAT (Velikovi et al., 2018). A more expressive scheme, GIN, is further proposed with summing features in a neighborhood followed by a multi-layer perceptrons (MLP) to approximate any injective function on multiset (Xu et al., 2019). However, these methods are typically constrained to a single one-hop message passing strategy that mostly captures ‘lowpass’ characteristics in the graph data. Klicpera et al. (2019) expand the MP range to multi-hop neighborhoods with graph diffusion operators. Besides, several methods are proposed to implement an equivalent high-order (polynomial) filter with the whole network to alleviate over-smoothing representation, including SGC (Wu et al., 2019), LGC (Navarin et al., 2020), GPR-GNN (Chien et al., 2021), SGF (NT et al., 2021), and S2GC (Zhu & Koniusz, 2021). However, a single equivalent filter may be limited when representing multi-channel signals with diverse frequency characteristics. Alternatively, a group of works attempt to complement the ‘low-pass’ features using different strategies, such as graph wavelet filters (Gao et al., 2019; Chang et al., 2021), a one-order high-pass filter (Bo et al., 2021) and an additional quadratic middle-pass filter (Wu et al., 2021), and other aggregation schemes (Abu-El-Haija et al., 2019; Zhu et al., 2020). Contrary to these methods, we employ a learnable filter bank with various frequency responses in a single layer to adaptively capture diverse spectral characteristics of signals rather than merely adding ‘high-pass’ features or specific components via predefined graph wavelets. Finally, in contrast with some works that further consider adaptive filters (Li et al., 2021; Dong et al., 2021; Pasa et al., 2021), BankGCN is a more powerful and compact design with polynomial filter banks to avoid eigen-decomposition and a further sharing scheme between filters to reduce free parameters. More detailed comparisons in App. F.
Filtering on Graphs and Spectral GCNs. Filtering and Graph Fourier Transform have been generalized to graph data via spectral graph theory (Shuman et al., 2013). Correspondingly, several spectral GCNs are derived from filtering in the graph frequency domain directly, as pioneered by Bruna et al. (2014). However, they rely on computationally expensive eigen-decomposition of the graph Laplacian. To avoid the eigendecomposition, similarly to dictionary learning methods (Thanou et al., 2014) in graph signal processing (GSP), the filters are built as polynomial or rational functions of eigenvalues of the graph Laplacian, such as Chebyshev polynomials in ChebNets (Defferrard et al., 2016) and TIGraNet (Khasanova & Frossard, 2017), Cayley polynomials in CayleyNets (Levie et al., 2018), and auto-regressive moving average (ARMA) filters (Bianchi et al., 2021). In contrast with these spectral convolution methods that focus on the implementation of filters with desirable prop-
erties, like localization and narrowband specialization, this paper focuses on the design of the filter bank in order to construct a simplified architecture with improved generalization.
Finally, there are several papers in graph signal processing literature about the design of graph filter banks for graph signal decomposition (Narang & Ortega, 2012; Tanaka & Sakiyama, 2014) and multiscale analysis (Hammond et al., 2011; Narang & Ortega, 2013). However, they usually work under a rigid constraint, e.g., perfect reconstruction, and thereby their produced (sparse) representations may not be flexible enough to adapt to diverse tasks in machine learning. In contrast, our method relaxes the perfect reconstruction condition and rather regularizes filters in a filter bank to be sufficiently different in the graph frequency domain.

heading: 3 PRELIMINARIES AND PROBLEMS

text:
In this paper, we consider data that is represented on undirected graphs. Each vertex of graphs is attributed a d-channel signal or feature. The node signal is typically multi-channel, i.e., d > 1, and with different spectral statistics along different dimensions, which we refer to heterogeneous signals in this paper. Notations and preliminaries on Graph Fourier Transform and filtering are introduced in App. A.
We first show how filtering can be implemented by messaging passing, which is used in many stateof-the-art graph representation learning methods. Filtering in the graph frequency domain and MP in the spatial domain is closely related (Shuman et al., 2013). Taking the most popular GCN (Kipf & Welling, 2017) as an example, according to its initial formation, the j-th channel of a filtered signal is
hj = d∑ i=1 (I +D− 1 2AD− 1 2 )Θxi = d∑ i=1 (2I − L)Θi,jxi = d∑ i=1 Θi,jUĝ(Λ)U ∗xi (1)
where Θ denotes learnable parameters, d indicates the dimension of signals, and ĝ(Λ) = 2I−Λ is a low-pass filter (NT & Maehara, 2019; Min et al., 2020). The renormalized version of GCN and the GIN can be formulated similarly. Please refer to (Balcilar et al., 2021) for their specific equivalent supports of ĝ(Λ). Besides, GraphSage uses the mean or max operator to aggregate information in neighborhoods. Although it is hard to explicitly formulate its corresponding frequency response, the element-wise mean operation is a low-pass operation by nature and the element-wise max operator performs as an envelope extraction that suppresses the high-frequency components.
Another line of works, spectral GCNs, are directly derived from spectral filtering. For the representative ChebNets and CayleyNets, the filters are defined as ĝ(λ) = ∑K k=0 θ
(k)Tk(λ) in the graph frequency domain with the Chebyshev polynomial or Cayley polynomial basis {Tk(·)} and correspondingly
hj = d∑ i=1 U K∑ k=0 Θ (k) i,j Tk(Λ)U ∗xi = d∑ i=1 Uĝij(Λ)U ∗xi, (2)
where K is the order of the polynomial filters and {Θ(k)} are learnable parameters. Notably, the above MPGCNs employ just a single kind of filter to handle all the channels of signals, and then takes different (linear) combinations of the filtered signals to obtain different channels of the output signals. Thereby, most MPGCNs are restricted in the number and types of filters and have a limited capacity in frequency-domain filtering. On the contrary, ChebNets and CayleyNets employ a different filter for each mapping from an input channel to an output channel and adopt a total of d × d′ K-order polynomial filters (d and d′ denote the respective number of channels of input and output signals) , as presented in Eq. 2. This naive design neglects the potential relationship between filters and fails to reduce redundancy. Consequently, they explore such a large number of learnable filters to process diverse frequency components of graph data at the expense of numerous free parameters, which sometimes leads to overfitting.

heading: 4 THE BANKGCN ALGORITHM

text: In this section, we first outline the framework of BankGCN, then present its main elements, and finally discuss connections with spectral methods.

heading: 4.1 GRAPH CONVOLUTION WITH ADAPTIVE FILTER BANKS

text:
Signals (features) supported on nodes of a graph are usually high-dimensional and composed of multiple spectral patterns. In other words, different signal channels vary differently over nodes, leading to diverse spectral characteristics. To handle the heterogeneous signals, we employ a filter bank composed of a set of filters with different frequency responses in the design of BankGCN. In order to further facilitate information processing, signal decomposition is adopted to explore latent relationships in the data.
For a multi-channel input node signal x(vm), we first adaptively decompose it into different subspaces and then employ different filters to deal with the signal components in each subspace separately. The decomposition aims to map the components of signals with similar characteristics into the same subspace in order to facilitate the subsequent adaptive filtering. This is implemented with learnable subspace projections. Mathematically, the input signal x(vm) is projected into s subspaces with a group of projection functions denoted by {f[p](·)}, r[p](vm) = f[p](x(vm)), p = 1, 2, . . . , s, ∀vm ∈ V. (3) Here, the subscript “[p]” indicates the terms belonging to the p-th subspace and r[p](vm) is the projected signal. The choices for projection functions will be introduced in Section 4.2. Subsequently, an adaptive filter g[p](·) is designed within each subspace to represent the spectral characteristics of the corresponding signal components,
h[p](vm) = (g[p] ∗ r[p])(vm), (4) where we reuse ‘*’ to denote the convolution between each channel of signal r[p] and the filter g[p].
The filtered signals h[p](vm), p = 1, 2, · · · , s, of all the subspaces are concatenated to produce the output features. A Rectified Linear Unit (ReLU) is then used as a non-linear activation function,
h(vl,m) = Concat(h[1](vl,m),h[2](vl,m), . . . ,h[s](vl,m)), (5)
x(vl+1,m) = ReLU(h(vl,m)), (6) where the subscript l indicates variables or parameters in the l-th layer to describe the forward propagation between different layers in a hierarchical architecture.
Specially, considering that some filters are only supported on medium-to-high frequency components that usually mean large signal variations in the spatial domain, we further introduce a shortcut in each subspace that corresponds to full-pass in the graph frequency domain in order to make the filtered signals stable. Correspondingly, the filtered signal h[p](vm) in each subspace becomes h[p](vm) = (g[p] ∗ r[p])(vm) + r[p](vm). (7) The shortcut can further facilitate back propagation of gradients, as for CNNs (He et al., 2016).
The proposed graph convolution operator is stackable, and the subspace mapping function in the following layers will further combine features from different subspaces in the preceding layers to enable information interaction between different channels.

heading: 4.2 SUBSPACE PROJECTION

text:
For the projection function f[p](·), there is a variety of design choices. Here, we take the linear mapping as an example, since it is simple yet able to decompose different channels of signals. Specifically, the d-channel 1 signal x(vm) is projected into s different subspaces with learnable matrices {W[p]}sp=1. For the sake of simplicity, all the subspaces have the same dimension in this paper. To increase flexibility, we further introduce a learnable bias b[p] for each subspace.
r[p](vm) = f[p](x(vm)) = W T [p]x(vm) + b[p], p = 1, 2, . . . , s. (8)
The introduction of subspace projection brings in two advantages: (i) it simplifies the learning process. Since the multi-channel graph signals have been decomposed, the filter in each subspace just needs to learn to capture spectral characteristics of the corresponding signal components; (ii) with low-dimensional subspaces, it limits the dimension of features output by the filter bank, and thereby reduces the number of free parameters and computation in the following layers.

heading: 4.3 FILTERS

text:
In order to handle graphs with arbitrary topologies and diverse signals, we adopt universal and adaptive filters to construct the filter bank.
For any function t : D = [0, 2]→ R, we can obtain a corresponding filter whose frequency response is ĝ[p](λ) = t(·), and its spatial construction is computed through IGFT (defined as Eq. S2 in App. A):
g[p](vm) = n∑ i=1 ĝ[p](λi)ui(vm), (9)
with ui, i = 1, · · · , n, the eigenvectors of the symmetric normalized graph Laplacian of a graph. Notably, we directly design the frequency response of the filter for the continuous range D = [0, 2] in which the spectrum of an arbitrary graph locates as introduced in Section A. In other words, given the discrete spectrum {λ0, λ1, . . . , λn} of an arbitrary graph, we have λi ∈ D and obtain the corresponding filter value on these specific discrete values ĝ[p](λi) = t(λi), for i = 1, 2, . . . , n. Thereby, the filter g[p](·) is adaptable to any graph even with different topologies, i.e., it is a universal form (Tremblay et al., 2018; Levie et al., 2019).
Furthermore, we constrain the filter to the K-order polynomial function space in order to avoid the computation-intense eigendecomposition of the graph Laplacian, similarly to parametric dictionary learning (Thanou et al., 2014) in GSP. It corresponds to an FIR filter. Mathematically, the frequency response of a filter can be represented as
ĝ[p](λ) = K∑ k=0 α (k) [p] Tk(λ), (10)
where {Tk} denotes a specific polynomial basis such as Chebyshev polynomials, and {α(k)[p] } indicates the corresponding coefficients. With {α(k)[p] } learnable, we obtain an adaptive filter whose frequency response adapts to the data and to the target task. Correspondingly, for the signal projected to the p-th subspace r[p](vm) and R[p] = [r[p](v1), r[p](v2), . . . , r[p](vn)]T , the filtered signal is calculated as
h[p](vm) = (r[p] ∗ g[p])(vm) = K∑
k=0
α (k) [p] (Tk(L)R[p]) T m. (11)
Equivalently, according to the relationship between frequency filtering and localized linear transforms in the spatial domain (Shuman et al., 2013), the filtering strategy corresponds to a message passing scheme within a K-hop neighborhood
h[p](vm) = cmmr[p](vm) + ∑
vo∈NK(vm)
cmor[p](vo), (12)
1 For the input signal with d = 1, we set s as the feature channels in the neural network in the first layer so that the signal is scaled differently in each subspace. In the following hidden layers, it can be used as the other cases to handle multi-channel features produced by previous layers in GCNs.
with
cmo = K∑ k=0 α (k) [p] (Tk(L))m,o ∀m, o ∈ {1, 2, . . . , n}. (13)
Specially, the induced K-hop message passing scheme is learned from the data and exploits the multi-hop topological information of graphs through polynomials of the graph Laplacian. Signal information is also taken into consideration through the learnable parameters {α(k)[p] } as well as in the subspace projection step. More importantly, it permits to represent features that do not only have “low-pass” properties and explores the frequency components in a data-driven manner.

heading: 4.4 DIVERSITY REGULARIZATION FOR FILTER BANKS

text:
The filters constituting a filter bank should ideally have diverse frequency responses so that the signal is decomposed through filtering into a series of signals with different frequency characteristics. In GSP, the filters are usually band-pass and divide the spectrum in different bands. Considering that strict band-pass filters are difficult to fit through polynomial functions, we relax this strict bandpass requirement and rather target filters with diverse frequency responses, which we call “diversity condition”. With the filter ĝ[p](λ) given as a K-order polynomial function, the regularization on the filter is imposed on the respective polynomial coefficients {α(k)[p] }p,k in Eq. 10. To achieve the diversity condition, we regularize the polynomial coefficients to be well distributed in the parameter space. Considering that the distances of the coefficient vectors of two scaled filters may still be large in terms of the Euclidean distance, we thereby take the cosine distance to measure the distance between the polynomial coefficients of filters. Specifically, the regularization term is:
Ω(α) = max p 6=q | < α[p],α[q] > | ‖α[p]‖2‖α[q]‖2 , (14)
where α[p] = [α (0) [p] , α (1) [p] , . . . , α (K) [p] ] T . The max function reflects the maximum similarity between the polynomial coefficients of any pair of filters in the filter bank. Through minimizing Eq. 14, the most similar filters will have different orientations in the parameter space. Thus, all the pairs of filters tend to be different. When {Tk(L)}k is an orthogonal basis such as Chebyshev polynomials, the diversity of polynomial coefficients {α[p]}p implies that filters defined as Eq. 10 are different in the graph frequency domain. More intuitively, the message passing schemes in the spatial domain induced by the filters are different with diverse {α[p]}p, as presented in Eq. 12 and Eq. 13. We can note that, if the filter is defined on the basis composed of rectangular pulse functions2, i.e.,
Tk(λ) =
{ 1 2kK+1 ≤ λ < 2(k+1) K+1
0 others , (15)
the ideal subband filter banks, whose filters have different passbands in GSP, just corresponds to the optimal solution to the regularization with Ω(α) = 0 in Eq. 14, when K ≥ s. With TΘ(G, Y ) generally representing a target function, the overall objective function is then formulated as
min Θ
TΘ(G, Y ) + γ Ω(α), (16)
where Y indicates ground truth labels, Θ denotes the parameter set including {α[p],W[p], b[p]}sp=1, and γ is a hyperparameter to adjust the contribution of regularization term. Like most popular graph convolution operators, BankGCN can be optimized via gradient-based methods together with modules such as graph pooling operators in GCNs. It achieves linear computational complexity with O(K|E|d) and constant learning complexity, similarly to most existing MPGCNs.

heading: 4.5 DISCUSSION

text:
BankGCN actually provides an effective simplification of existing polynomial-based spectral methods with parameter decomposition. With Θ = [Θ0; Θ1; . . . ; ΘK ] ∈ Rd×d ′×(K+1) representing the
2Note that this is not the case in this paper.
free parameters of the spectral methods adopting corresponding polynomial filters, BankGCN with a linear mapping as projection function actually provides a decomposition based approximation of Θ with
[W[1] ⊗α[1],W[2] ⊗α[2], . . . ,W[s] ⊗α[s]], (17) where ⊗ indicates outer product. This decomposition strategy allows for filter sharing to reduce potential redundancy of existing spectral methods. Multi-channel signals are first adaptively decomposed into various subspaces with {W[p]}p, and signal components within a subspace share a filter defined with α[p] to process corresponding characteristics. In addition, it permits to further control the relationship between filters with the diversity regularization as introduced in Section 4.4.
We further study the capacity of BankGCN in handling the spectrum of signals with a compact architecture.
Proposition 1. BankGCN can capture and preserve diverse frequency components of input graph signals, like its counterpart introduced in Eq. 2.
Proof. Please refer to App. B.
As demonstrated in Prop. 1 and its proof, a single filter g[p] in BankGCN together with signal projection is capable to explore and represent diverse frequency components of graph signals, as done in its counterpart with a group of filters {gij}i. This theoretically validates the effectiveness of BankGCN in reducing the number of filters and thereby potential redundancy in existing polynomial-based spectral architectures, while maintaining the capability of representing diverse spectral information.

heading: 5 EXPERIMENTS

text:
In this section, in order to evaluate models in learning representation of diverse spectral information of graph data, we resort to node classification and graph classification tasks.
Baselines. We compare BankGCN with several state-of-the-art graph convolution methods, including MPGCNs and spectral methods, as listed in Table 1 and Table 2. Furthermore, two simplifications of the proposed model (BankGCN-Diff and BankGCN-NR) are considered for ablation study. Please refer to App. C & D for details.
5.1 NODE CLASSIFICATION
We first evaluate the proposed model in node classification tasks on several heterophilic (i.e., neighbor nodes are dissimilar in labels/features) graph datasets, in order to validate the advantages of diverse frequency representation with filter banks. We follow the data split and evaluation procedure of (Pei et al., 2020; Zhu et al., 2020; Li et al., 2021), and describe the detail information of datasets and experimental settings in App. C. Results of baselines are cited from their respective publications if available, or recent public works (Zhu et al., 2020; Li et al., 2021). The metric β introduced by Pei et al. (2020) reveals the degree of homophily of graph data in datasets (Small β cor-
responding to strong heterophily). As presented in Table 1, BankGCN achieves the best performance on all the datasets. In contrast, the MPGCNs that rely on low-pass features, like GCN and GAT, perform worse. Notably, BankGCN still outperforms several of the most recent MPGCNs that improve on the over-smoothing issues, including a simplified GCN (SGC), improved aggregation schemes MixHop, GEOM-GCN and H2GCN, and adaptive filter based methods SGF and ASGAT.

heading: 5.2 GRAPH CLASSIFICATION

text:
We further evaluate the different models in graph classification tasks and study the components of BankGCN. Specially, for a fair and complete comparison, we consider two cases, (i) the same number of features, i.e., all of models with the same number of feature maps per hidden layer, and (ii) the same number of parameters, i.e., models with nearly the same number of free parameters per hidden layer, in Table 2 and Table 4 respectively. Experimental settings are presented in App. D.
As presented in Table 2, BankGCN outperforms all the MP baselines with nearly the same or even fewer number of parameters on TU-benchmarks. It further achieves better performance than its counterpart ChebNets with much fewer free parameters, i.e., about 1/(K + 1), and is also superior to the most recent spectral method ARMA on most datasets. As presented in Fig. 2, the learned filters have different frequency responses rather than only low-pass, some of them being high-pass and some focusing on middle-frequencies. With such a bank of filters, BankGCN handles the multichannel signals flexibly and thereby achieves the best performance on almost all the datasets.
We then go one step further to evaluate the adaptive filtering capabilities. As presented in Fig. 2, the learned filters have different frequency responses on various datasets as they are adapted to the data characteristics. As listed in Tables 2 and 3, the BankGCN (s = 1) employing one single adaptive filter still outperforms GCN with ‘low-pass’ filtering on most datasets; Furthermore, BankGCN is superior to its variant BankGCN-Diff that uses predefined filter banks on all the datasets. These validate the benefits of adaptive filtering to flexibly capture the spectral characteristics of data.
Study on the number of filters. Furthermore, we evaluate the adoption of filter banks rather than a single filter, and study the impact of the number of filters in the filter bank (equivalently s, the number of subspaces) on the classification performance. With a group of filters, the ability of convolution operators to handle information is enhanced. As presented in Table 2, BankGCN-Diff outperforms GCN with additional band-pass and high-pass filters on almost all the datasets, and BankGCN further improves the performance with adaptive filters. Furthermore, as s increases from 1 to 8, the performance of BankGCN is improved on most datasets, as listed in Table 3. These validate the benefits of using more than one filter. With s further increased into 16, the performance is degraded on several datasets. Given that the total dimension of all the subspaces is fixed, the dimension of each space decreases and the representation capacity of each subspace probably declines with the further growth of s.
Study on the order of filters. The order of polynomials determines the function space of filters. In the graph frequency domain, as demonstrated in Fig. 2, it can better realize the bandpass property
of filters using a larger K but at the cost of a greater risk of overfitting the spectrum of training data. In the spatial domain, the value of K corresponds to the message passing range, and a large K will affect the locality of signals. Thereby, a tradeoff is needed. As shown in Table 3, BankGCN with K = 2 achieves the best performance on most datasets. We notice that for the cases with complex node signals, like FRANKENSTEIN with 780-channel node attributes, a relatively large K is needed to exploit their various spectral characteristics; and the small K is preferred on simple datasets, such as the PROTEINS dataset with 3-channel node category features.
Study on the regularization. We further evaluate the effect of the proposed diversity regularization. The comparison of BankGCN-NR and BankGCN in Table 2 shows that the regularization improves the classification performance on almost all the datasets. On the FRANKENSTEIN dataset whose signal is composed of 780-channel attributes, the regularization is not helpful. We infer that the information in such high-channel signal is complex enough to induce different filters, as presented in Fig. 2(e). Fig. 2(a)-(c) show that the learned filters in a filter bank with regularization present better diversity in frequency response, than those without regularization. For example, the filters denoted by blue and red in Fig. 2(a) are with similar frequency responses, while they are more diverse in Fig. 2(b) and Fig. 2(c). This is further verified by the maximum similarity scores of the polynomial coefficients that define the filters Ω(α) = 0.997, 0.744, and 0.649 (computed as Eq. 14) for Fig. 2(a)-(c), respectively. More results and analysis are presented in App. E.
BankGCN still achieves the best performance on both CIFAR-10 and Ogbgmolhiv with all the models having a similar number of free parameters per hidden layer, as presented in Table 4. Furthermore, to evaluate the generalization of models, we construct a reduced CIFAR-10 (1000) dataset by taking 100 graphs per category to form the training set, while maintaining the validation and testing sets. BankGCN still performs best on the reduced CIFAR10 dataset and is among the models with
the least performance loss compared with the full dataset. Together with ROC-AUC being a measure of the generalization ability of a model, BankGCN performs well in the sense of generalization, especially when compared with its counterpart ChebNets. These further validate the effect of the proposed sharing scheme between filters for model simplification on improving generalization.

heading: 6 CONCLUSION

text: In this paper, we propose a novel graph convolution operator, termed BankGCN, constructed on an adaptive filter bank for graph representation learning. The filter bank is equivalent to a group of learnable message passing schemes in K-hop neighborhoods. Together with subspace decomposition, BankGCN explores a sharing scheme between filters to adaptively handle information of diverse spectral characteristics with significantly fewer parameters than its competitors, and achieves excellent performance on node classification and graph classification tasks. An interesting direction for future research resides in discussing the capacity of the proposed graph convolution operator in terms of graph isomorphism test. It may also be promising to employ BankGCN in a variety of tasks on non-Euclidean data like 3-D point cloud classification and segmentation.

heading: A NOTATIONS AND PRELIMINARIES

text:
In this paper, we consider data that is represented on undirected graphs. An input graph is described as G = (V, E), with V and E respectively denoting the set of vertices and the set of edges. We generally use capital letters for matrices and bold lowercase letters for vectors. The graph topology is characterized by the adjacency matrix A with a non-zero value (A)ij indicating the weight of the edge connecting vertices vi and vj . If available 3, the d-channel signals or attributes of nodes are represented as x(vm) ∈ Rd for ∀vm ∈ V , and X = [x(v1),x(v2), · · · ,x(vn)]T is for the whole graph G with n = |V| nodes. Specially, for vector features, xi(vm) indicates the i-th channel of the signal on vertex vm, and xi = [xi(v1), xi(v2), · · · , xi(vn)]T represents this signal on the whole graph. For the hierarchical structure of GCNs, we employ a subscript l to indicate variables or parameters belonging to the l-th layer. In most cases, we ignore l for clarity without causing confusion.
The Graph Fourier Transform (GFT) is defined based on the graph Laplacian matrix L (Shuman et al., 2013). We adopt the symmetric normalized graph Laplacian operator, i.e., L = I − D− 12AD− 12 with the diagonal degree matrix D defined as (D)ii = ∑ j(A)ij . The eigendecomposion of the Laplacian matrix is denoted by L = UΛU∗, where U = [u1,u2, . . . ,un] is composed of the eigenvectors uk, k = 1, · · · , n and Λ is a diagonal matrix with eigenvalues λ1, λ2, . . . , λn, with 0 = λ1 ≤ λ2 ≤ · · · ≤ λn ≤ 2. The eigenvalues {λk} construct the spectrum
3If node attributes are not available, we adopt the structural information like the one-hot encoding representation of node degree and the local clustering coefficient as node signals.
of the graph G 4, and the GFT of a signal x is calculated as the inner-product between each of its component xi and the eigenvectors {uk} (Shuman et al., 2013):
x̂i(λk) = n∑ m=1 xi(vm)u ∗ k(vm), (S1)
where ∗ indicates conjugate transpose and u∗k(vm) denotes the m-th element in u∗k. The Inverse Graph Fourier Transform (IGFT) is defined as
xi(vm) = n∑ k=1 x̂i(λk)uk(vm). (S2)
According to the convolution theorem, the convolution between the i-th channel of the signal xi(vm) and the corresponding filter g(vm) (with frequency response ĝ(λk) ) is defined as:
(xi ∗ g)(vm) = n∑
k=1
x̂i(λk)ĝ(λk)uk(vm) (S3)
Let us define ĝ(Λ) = diag([ĝ(λ1), ĝ(λ2), . . . , ĝ(λn)]). We have for xi(vm) that (xi ∗ g) = Uĝ(Λ)U∗xi. (S4)
Finally, a graph filter bank is composed of a set of filters {ĝi(Λ)} to decompose a graph signal into a series of signals with different frequency components (Narang & Ortega, 2012).

heading: B PROOF OF PROPOSITION 1

text:
Proof. For spectral methods with polynomial filters ĝ(λ) = ∑K
k=0 θ (k)Tk(λ), the j-th channel
(j = 1, 2, . . . , d′) of the output signal is
hj = d∑ i=1 gij ∗ xi = d∑ i=1 Uĝij(Λ)U ∗xi
= d∑ i=1 U K∑ k=0 Θ (k) i,j Tk(Λ)U ∗xi = U d∑ i=1 K∑ k=0 Θ (k) i,j Tk(Λ)x̂i.
(S5)
Thereby, the spectrum of output signal is a linear transform of the K-order polynomial expansion of input signals {Tk(Λ)x̂i}i,k
ĥj = K∑ k=0 d∑ i=1 Θ (k) i,j Tk(Λ)x̂i. (S6)
For BankGCN, we assume that the j-th channel (j = 1, 2, . . . , d′) of the output signal corresponds to the q-th channel of the filtered signal in the p-th subspace, and we have
hj = (g[p] ∗ r[p]q) = (g[p] ∗ ( d∑
i=1
(W[p])i,qxi + b[p]q1))
= U( K∑ k=0 α (k) [p] d∑ i=1 (W[p])i,qTk(Λ)U ∗xi + [p]q),
(S7)
where r[p]q denotes the q-th channel of the projected signal R[p] in the p-th subspace, b[p]q indicates the q-th element in b[p], 1 denotes a constant vector with value 1, and [p]q represents a vector independent on input signals. Correspondingly, the spectrum of hj is
ĥj = K∑ k=0 d∑ i=1 α (k) [p] (W[p])i,qTk(Λ)x̂i + [p]q. (S8)
According to Eq. S6 and Eq. S8, BankGCN can capture and preserve diverse frequency components of input graph signals, like its counterpart introduced in Eq. 2
4In analogy to classical Fourier analysis, eigenvalues provide a corresponding notion of frequency and lead to frequency filtering.

heading: C EXPERIMENTAL SETTINGS ON NODE CLASSIFICATION

text:
We evaluate the models on four heterophilic graph datasets (Pei et al., 2020; Tang et al., 2009), including Texas, Wisconsin, Cornell, and Actor. Texas, Wisconsin, Cornell are three subdatasets from WebKB. In these datasets, nodes represent web pages with their 1703-dimensional bag-ofwords representation as node features, and hyperlinks between the web pages form edges. Actor is a dataset preprocessed by Pei et al. (2020) from the film-director-actor-writer network (Tang et al., 2009). The graph in the dataset represents the co-occurrence (connection) of actors (nodes) on the same Wikipedia page. There are five categories on all these datasets.
We follow the data split and evaluation procedure of previous methods (Pei et al., 2020; Zhu et al., 2020; Li et al., 2021). Specifically, 48%:32%:20% of nodes per class are split into training, validation and test sets, and 10 such random splits on each dataset are provided by Pei et al. (2020); Fey & Lenssen (2019). The network architecture consists of two layers. We select the following hyper-parameters through grid-search: number of feature maps of the hidden layer ∈ {32, 64, 128}, learning rate∈ {0.02, 0.04}, weight decay ∈ {5e−4, 1e−3}, and s ∈ {4, 8, 16}. In addition, the dropout is 0.5 only in the hidden layer, and s is set as 1 for the output layer.
We compare BankGCN with several state-of-the-art graph convolution methods. For the MPGCNs, we consider GCN (Kipf & Welling, 2017), GraphSage (Hamilton et al., 2017), GAT (Velikovi et al., 2018), MixHop (Abu-El-Haija et al., 2019), SGC (Wu et al., 2019), GEOM-GCN (Pei et al., 2020), H2GCN (Zhu et al., 2020), SGF (NT et al., 2021), and ASGAT (Li et al., 2021). Regarding spectral GCNs, we compare with its counterpart ChebNets (Defferrard et al., 2016) that also adopts Chebyshev polynomial filters, and the most recent spectral method ARMA (Bianchi et al., 2021).

heading: D EXPERIMENTAL SETTINGS ON GRAPH CLASSIFICATION

text:
Datasets and data splits. For TU datasets (Kersting et al., 2016), we conduct experiments on seven widely used public benchmark graph classification datasets, including ENZYMES, D&D, PROTEINS, NCI1, NCI109, MUTAGENICITY, and FRANKENSTEIN 5. We adopt node categorical features (one-hot encoding) and node attributes as node signals, depending on availability on the datasets, which are usually heterogeneous in different dimensions. Specifically, node attributes are adopted on FRANKENSTEIN, node categorical features and node attributes (normalized in range [0, 1]) on ENZYMES, and node categorical features on the other datasets. The statistics and properties of the datasets are summarized in Table S1. According to (Lee et al., 2019), we use stratified sampling to randomly split each dataset into training, validation and test sets with a ratio of 8:1:1. The trained model with the best validation performance is selected for test. In order to alleviate the impact of data partition and network initialization, we conduct 20 random runs with different data splits and network initializations on each dataset, and report the mean accuracy with standard deviation of these 20 test results.
We further adopt two large benchmark datasets, CIFAR-10 (Dwivedi et al., 2020) and Ogbg-molhiv (Hu et al., 2020), in the experiments. The graph version of CIFAR-10 is composed from the superpixels of images, and RGB intensities and normalized coordinates form node signals. Ogbg-molhiv is a molecule graph dataset, with 9-dimensional node features including atomic number, chirality, and additional atom features. We divide data on these two datasets in accordance with (Dwivedi et al., 2020) and (Hu et al., 2020), respectively. Similarly, results are achieved with 3 runs on CIFAR-10 and 10 runs on Ogbg-molhiv in order to alleviate the impact of network initialization.
Network architectures. In the experiments, we adopt a similar architecture to (Xu et al., 2018), and the network consists of four convolution layers, one graph-level readout module and one prediction module for all the datasets. Specifically, the graph convolution layer is designed as introduced in Section 4 or defined by various baseline models. An l2 normalization function is utilized in each convolution layer to stabilize and accelerate the training process, as in (Hamilton et al., 2017). A graph-level readout module then aggregates the graph features from all the convolution layers to generate the graph representation hG . It consists of node-wise mean and maximum operators (or mean operator on Ogbg-molhiv as in (Hu et al., 2020)), represented by ω(·).
hG = Concat(ω(Xl)|l = 1, 2, 3, 4). (S9) 5Datasets could be downloaded from https://ls11-www.cs.tu-dortmund.de/staff/morris/graphkerneldatasets
Table S1: Dataset statistics and properties (L indicates node categorical features and A denotes node attributes).
ENZ D&D PROT NCI1 NCI109 MUTA FRAN CIFAR-10 Ogbg-molhiv
Avg |V| 32.63 284.32 39.06 29.87 29.68 30.32 16.90 117.63 25.51 Avg |E| 62.14 715.66 72.82 32.30 32.13 30.77 17.88 564.86 27.47 Node feature L+A L L L L L A A A Dim(feat) 3+18 89 3 37 38 14 780 5 9 #Classes 6 2 2 2 2 2 2 10 2 #Graphs 600 1,178 1,113 4,110 4,127 4,337 4,337 60,000 41,127
Finally, a prediction module composed of a linear fully connected layer and a softmax layer makes the prediction of the category of the input graph. The cross-entropy (represented as TΘ(G, Y )) is adopted as the loss function, which together with the regularization Ω(α) for diversity condition composes the objective function: TΘ(G, Y ) + γ Ω(α) (S10) where Θ denotes all the free parameters and Y indicates ground truth categorical labels.
In more details, we consider two versions of the architectures in the experiments in order to evaluate the models under the same number of features and the same number of parameters, respectively. For the first case, all of models have the same number of feature maps per hidden layer, whereas models are composed of nearly the same number of parameters per hidden layer for the latter case. We consider the first version with TU datasets in Table 2 with 64 feature maps per hidden layer, and the second version in Table 4 with nearly 16,500 and 65,800 free parameters per layer for all the models on CIFAR-10 and Ogbg-molhiv, respectively.
Configurations. We implement the proposed models in Pytorch (Paszke et al., 2017) with geometric package (Fey & Lenssen, 2019), and optimize all of the models with the Adam optimizer (Kingma & Ba, 2015) on workstations with GPU GeForce GTX 1080 Ti for TU datasets as well as CIFAR-10 and with GPU RTX 2080 Ti for Ogbg-molhiv. In more details, for TU datasets, the learning rate is 0.001 and the batch size is 64. The number of training epochs is set as 500, and early stopping is employed with patience 30. Finally, we obtain the following optimal hyper-parameters through grid search: weight decay ∈ {0, 1e−5, 1e−4} and γ ∈ {0, 0.1, 10}. For CIFAR-10 and Ogbg-molhiv, the batch size is increased to 256 due to their large scale. Similarly to (Dwivedi et al., 2020), we adopt a dynamic learning rate that is initialized as 0.001 and decays by 0.1 when validation loss is not improved for 20 epochs until the minimum learning rate 1e−5. The number of training epochs is 500 with early stoping (patience 50). The other settings are the same as TU datasets.
For the polynomial basis in the filter design of BankGCN, we adopt the widely used Chebyshev polynomials. T0(λ) = 1, T1(λ) = λ, Tk(λ) = 2λTk−1 − Tk−2. (S11) The graph Laplacian is adopted as L̃ = L− I for numerical stability, similarly to (Defferrard et al., 2016).
Baselines. We compare BankGCN with several state-of-the-art graph convolution methods. For the MPGCNs, we consider GCN (Kipf & Welling, 2017), GraphSage (Hamilton et al., 2017) with mean aggregation, GAT (8-heads) (Velikovi et al., 2018), and GIN using SUM-MLP (2 layers) that achieves the best performance (Xu et al., 2019). Regarding spectral GCNs, we compare with its counterpart ChebNets (Defferrard et al., 2016) that also adopts Chebyshev polynomial filters, and the most recent spectral method ARMA (1-stack) (Bianchi et al., 2021). For a fair comparison, the results of baseline models are obtained with the same configurations as BankGCN using the public versions provided in the pytorch-geometric package (Fey & Lenssen, 2019), with their respective optimal hyper-parameters (weight decay) selected by grid search.
Ablation Study. Furthermore, we consider two simplifications of the proposed model for ablation study. First, BankGCN-Diff adopts a predefined filter bank. The filter bank consists of a lowpass filter, a high-pass filter, and band-pass filters from graph diffusion wavelets as used by Gama et al. (2019); Min et al. (2020). The specific frequency responses of these filters are presented in
Table S2: Ablation study on the diversity regularization with BankGCN (K = 2, s = 8).
ENZY DD NCI1 PROT NCI109 MUTA FRAN
γ = 0 65.83 ± 6.66 77.03 ± 4.08 81.89 ± 1.95 75.36 ± 4.68 81.03 ± 1.95 82.44 ± 1.69 67.82 ± 2.30 γ = 0.01 66.50 ± 6.39 77.54 ± 3.21 81.63 ± 2.33 75.49 ± 4.07 81.27 ± 2.16 82.87 ± 1.94 67.71 ± 1.96 γ = 0.1 68.00 ± 5.23 78.09 ± 2.18 82.06 ± 1.75 75.67 ± 4.19 81.34 ± 1.92 82.83 ± 1.87 67.68 ± 2.10 γ = 1 66.42 ± 6.20 77.97 ± 3.57 81.81 ± 1.97 76.29 ± 4.84 81.00 ± 2.21 82.95 ± 1.44 67.76 ± 1.65 γ = 10 66.75 ± 5.90 78.14 ± 2.81 82.06 ± 2.10 75.31 ± 4.64 81.54 ± 2.13 82.89 ± 1.61 67.20 ± 1.67 γ = 100 67.08 ± 5.42 77.75 ± 3.26 81.81 ± 2.18 75.98 ± 4.40 81.14 ± 1.94 82.44 ± 1.71 67.52 ± 1.83
Appendix D. Second, BankGCN-NR removes the diversity regularization from BankGCN with γ = 0.
BankGCN-Diff adopts a predefined filter bank that consists of a low-pass filter, a high-pass filter, and band-pass filters from graph diffusion wavelets as used in (Gama et al., 2019; Min et al., 2020). The specific frequency responses of these filters are
ψl,0(T ) = I − T, ψh,0(T ) = I − T ′ ψl,1(T ) = T (I − T ), ψh,1(T ) = T ′(I − T ′) ψl,2(T ) = T
2(I − T 2), ψh,2(T ) = T ′2(I − T ′2) ψl,3(T ) = T
4(I − T 4), ψh,3(T ) = T ′4(I − T ′4) (S12) with two diffusion operators:
T = (1−D− 12AD− 12 )/2, T ′ = (1 +D− 12AD− 12 )/2. (S13) Their frequency responses can be easily derived with the relationship between the diffusion operators and the graph Laplacian. Specifically, ψl,0 and ψh,0 are respective low-pass and high-pass filters, and the others are band-pass filters.

heading: E MORE EXPERIMENTAL RESULTS AND ANALYSIS

text:
More Ablation Results about the Diversity Regularization. In Table S2, we consider the values of γ ∈ {0, 0.01, 0.1, 1, 10, 100} to adjust its contribution in the objective function (Eq. 16). The regularization improves the classification performance on almost all the datasets. Mostly, the best performance is achieved with γ = 0.1 or γ = 10, and thereby we consider γ ∈ {0, 0.1, 10} in adjusting the contribution of regularization in the experiments. As illustrated in Fig. S1(a)-(f), the learned filters in a filter bank with regularization present better diversity in terms of frequency response than those without regularization on NCI109 and ENZYMES datasets. For example, the filters denoted by blue and red in Fig. S1(a) are with similar frequency responses, while they are more diverse in Fig. S1(b) and Fig. S1(c). Besides, the filters indicated by gray and purple in Fig. S1(d)-(f) show similar results. These are further verified with the maximum similarity scores of the polynomial coefficients that define the filters Ω(α) = 0.997, 0.744, and 0.649 (computed as Eq. (18)) for Fig. S1(a)-(c), and Ω(α) = 0.899, 0.714, and 0.705 for Fig. S1(d)-(f), respectively.
More illustration results. We provide more illustration results in Fig. S2 to demonstrate adaptive filter banks with different numbers of filters. With the increase of the s, BankGCN is more flexible to decompose the signal into components with different spectral characteristics. Furthermore, as shown in Fig. S3, the frequency responses of the learned filters in a filter bank vary with the datasets and the layers in the neural networks. These demonstrate the necessity and benefit of adopting learnable rather than predefined filters.

heading: F MORE COMPARISONS WITH RELATED WORKS

text:
Message Passing Graph Convolutional Networks. MPGCNs design graph convolution with a variety of message passing schemes in the spatial domain. For instance, messages are aggregated with the node-wise mean or max operation in a localized neighborhood in GraphSage (Hamilton et al., 2017), or based on attention scores in GAT (Velikovi et al., 2018). A more expressive scheme, GIN,
N C
I1 09
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
|̂g [ p ]( λ )|
(a) γ = 0.
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.0
0.5
1.0
1.5
2.0
|̂g [ p ]( λ )|
(b) γ = 0.1.
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.0
0.5
1.0
1.5
2.0
|̂g [ p ]( λ )|
(c) γ = 10.
E N
Z Y
M E
S
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
|̂g [ p ]( λ )|
(d) γ = 0.
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
|̂g [ p ]( λ )|
(e) γ = 0.1.
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
|̂g [ p ]( λ )|
(f) γ = 10.
FR A
N K
E N
ST E
IN
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.0
0.5
1.0
1.5
2.0
|ĝ [ p ]( λ
)|
(g) γ = 0.
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.0
0.5
1.0
1.5
2.0
2.5
|ĝ [ p ]( λ
)|
(h) γ = 0.1.
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.0
0.5
1.0
1.5
2.0
2.5
|ĝ [ p ]( λ
)|
(i) γ = 10.
Figure S1: Comparisons of the frequency responses of the learned filters of BankGCN (K = 2, s = 8) under different regularization strengths on different datasets.
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.0
0.2
0.4
0.6
0.8
1.0
|̂g [ p] (λ
)|
(a) s = 1.
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
|ĝ [ p]
(λ )|
(b) s = 4.
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.0
0.5
1.0
1.5
2.0
|ĝ [ p]
(λ )|
(c) s = 8.
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
|̂g [ p] (λ
)|
(d) s = 16.
Figure S2: Illustrations of the frequency responses of the learned filters of BankGCN (K = 2, γ = 10) in the first layer of networks with different number of subspaces (s) on NCI109.
N C
I1 09
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.0
0.5
1.0
1.5
2.0
|ĝ [ p ]( λ
)|
(a) Layer-1.
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.0
0.2
0.4
0.6
0.8
1.0
1.2
1.4
1.6
|ĝ [ p ]( λ
)|
(b) Layer-2.
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
|ĝ [ p ]( λ
)|
(c) Layer-3.
E N
Z Y
M E
S
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
|ĝ [ p ]( λ
)|
(d) Layer-1.
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
|ĝ [ p ]( λ
)|
(e) Layer-2.
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.0
0.5
1.0
1.5
2.0
|ĝ [ p ]( λ
)|
(f) Layer-3.
FR A
N K
E N
ST E
IN
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.0
0.5
1.0
1.5
2.0
|ĝ [ p ]( λ
)|
(g) Layer-1.
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.0
0.2
0.4
0.6
0.8
1.0
1.2
|ĝ [ p ]( λ
)|
(h) Layer-2.
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
λ
0.0
0.5
1.0
1.5
2.0
|ĝ [ p ]( λ
)|
(i) Layer-3.
Figure S3: Illustrations of the frequency responses of the learned filters of BankGCN (K = 2, s = 8) in the different layers of networks on different datasets.
is further proposed with summing features in a neighborhood followed by a multi-layer perceptrons (MLP) to approximate any injective function on multiset (Xu et al., 2019). However, these methods are typically constrained to a single one-hop message passing strategy that mostly captures ‘lowpass’ characteristics in the graph data. Klicpera et al. (2019) expand the MP range to multi-hop neighborhoods with graph diffusion operators. Besides, several methods are proposed to implement a high-order (polynomial) filter with the whole network. For example, SGC (Wu et al., 2019) corresponds to a fixed polynomial filter, and LGC (Navarin et al., 2020), GPR-GNN (Chien et al., 2021), SGF (NT et al., 2021), and S2GC (Zhu & Koniusz, 2021) further realizes an adaptive filter with diverse motivations. Alternatively, a group of methods attempt to complement the ‘low-pass’ features of GCN using different strategies. For instance, Scattering GCN (Min et al., 2020) resorts to geometric scattering transform (Gao et al., 2019) to complement the ‘low-pass’ features of GCN (Kipf & Welling, 2017) with ‘band-pass’ features, a one-order high-pass filter is adopted as the complement (Bo et al., 2021), and SpGAT (Chang et al., 2021) employs predefined graph wavelet filters. Besides, MixHop (Abu-El-Haija et al., 2019) explores linear mixing of neighborhood information to further realize difference operators, which can capture high-frequency information, and H2GCN (Zhu et al., 2020) additionaly aggregates information from high-order neighborhoods. Contrary to these methods, we employ a learnable filter bank with various frequency responses to adaptively capture diverse spectral characteristics of signals rather than merely adding ‘high-pass’ features or specific components via predefined graph wavelets. Finally, some works further consider adaptive filters (Li et al., 2021; Dong et al., 2021; Pasa et al., 2021), but BankGCN is a more powerful and compact design with polynomial filter banks to avoid eigen-decomposition and a further consideration of the sharing scheme between filters to reduce free parameters. For instance, AdaGNN (Dong et al., 2021) implements an equivalent filter for each channel of input signals through the whole network, while BankGCN can realize it within a single convolution operator. Furthermore, the filter space of BankGCN with K-order polynomial filters is larger than AdaGNN, since the K-order filter in AdaGNN is obtained by multiplying K one-order filters. The expressive capacity can be further enhanced by stacking multiple BankGCN layers.