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. 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.  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. 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.
references.authors: Sami Abu-El-Haija Bryan Perozzi Amol Kapoor Nazanin Alipourfard Kristina Lerman Hrayr Harutyunyan Greg Ver Steeg Aram Galstyan
references.title: Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing
references.venue: In Proc. 36th Int. Conf. Mach. Learn.,
references.authors: Muhammet Balcilar Renton Guillaume Pierre Héroux Benoit Gaüzère Sébastien Adam Paul Honeine
references.title: Analyzing the expressive power of graph neural networks in a spectral perspective
references.venue: In 9th Int. Conf. Learn. Rep.,
references.authors: Filippo Maria Bianchi Daniele Grattarola Lorenzo Livi Cesare Alippi
references.title: Graph neural networks with convolutional arma filters
references.venue: IEEE Trans. Pattern Anal. and Mach. Intell.,
references.authors: Deyu Bo Xiao Wang Chuan Shi Huawei Shen
references.title: Beyond low-frequency information in graph convolutional networks
references.venue: In Proc. 35th AAAI Conf. Artif. Intell.,
references.authors: Joan Bruna Wojciech Zaremba Arthur Szlam Yann LeCun
references.title: Spectral networks and locally connected networks on graphs
references.venue: In 2nd Int. Conf. Learn
references.authors: Heng Chang Yu Rong Tingyang Xu Wenbing Huang Somayeh Sojoudi Junzhou Huang Wenwu Zhu
references.title: Spectral graph attention network with fast eigen-approximation
references.venue: In 30th ACM Int. Conf. Inf. Knowl. Manag.,
references.authors: Eli Chien Jianhao Peng Pan Li Olgica Milenkovic
references.title: Adaptive universal generalized pagerank graph neural network
references.authors: Michaël Defferrard Xavier Bresson Pierre Vandergheynst
references.title: Convolutional neural networks on graphs with fast localized spectral filtering
references.venue: In Adv. Neural Inf. Process. Syst
references.authors: Yushun Dong Kaize Ding Brian Jalaian Shuiwang Ji Jundong Li
references.title: Adagnn: Graph neural networks with adaptive frequency response filter
references.venue: In 30th ACM Int. Conf. Inf. Knowl. Manag.,
references.authors: Vijay Prakash Dwivedi Chaitanya K Joshi Thomas Laurent Yoshua Bengio Xavier Bresson
references.title: Benchmarking graph neural networks
references.venue: arXiv preprint arXiv:2003.00982,
references.authors: Matthias Fey Jan E. Lenssen
references.title: Fast graph representation learning with PyTorch Geometric
references.venue: In ICLR Workshop on Representation Learning on Graphs and Manifolds,
references.authors: Fernando Gama Alejandro Ribeiro Joan Bruna
references.title: Diffusion scattering transforms on graphs
references.venue: In 7th Int. Conf. Learn. Rep.,
references.authors: Feng Gao Guy Wolf Matthew Hirn
references.title: Geometric scattering for graph data analysis
references.venue: In Proc. 36th Int. Conf. Mach. Learn., Long Beach, California,
references.authors: Justin Gilmer Samuel S. Schoenholz Patrick F. Riley Oriol Vinyals George E. Dahl
references.title: Neural message passing for quantum chemistry
references.venue: In Proc. 34th Int. Conf. Mach. Learn.,
references.authors: Will Hamilton Zhitao Ying Jure Leskovec
references.title: Inductive representation learning on large graphs
references.venue: In Adv. Neural Inf. Process. Syst
references.authors: David K Hammond Pierre Vandergheynst Rémi Gribonval
references.title: Wavelets on graphs via spectral graph theory
references.venue: Appl. Comput. Harmon. Anal.,
references.authors: Kaiming He Xiangyu Zhang Shaoqing Ren Jian Sun
references.title: Deep residual learning for image recognition
references.venue: In 2016 IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR),
references.authors: Weihua Hu Matthias Fey Marinka Zitnik Yuxiao Dong Hongyu Ren Bowen Liu Michele Catasta Jure Leskovec
references.title: Open graph benchmark: Datasets for machine learning on graphs
references.venue: In Adv. Neural Inf. Process
references.authors: Kristian Kersting Nils M. Kriege Christopher Morris Petra Mutzel Marion Neumann
references.title: Benchmark data sets for graph kernels, 2016
references.venue: URL http://graphkernels.cs.tu-dortmund. de
references.authors: Renata Khasanova Pascal Frossard
references.title: Graph-based isometry invariant representation learning
references.venue: In Proc. 34th Int. Conf. Mach. Learn.,
references.authors: Diederik P. Kingma Jimmy Ba
references.title: Adam: A method for stochastic optimization
references.venue: In 3rd Int. Conf. Learn
references.authors: Thomas N. Kipf Max Welling
references.title: Semi-supervised classification with graph convolutional networks
references.venue: In 5th Int. Conf. Learn
references.authors: Johannes Klicpera Stefan Weißenberger Stephan Günnemann
references.title: Diffusion improves graph learning
references.venue: In Adv. Neural Inf. Process. Syst
references.authors: Junhyun Lee Inyeop Lee Jaewoo Kang
references.title: Self-attention graph pooling
references.venue: In Proc. 36th Int. Conf. Mach. Learn.,
references.authors: Ron Levie Federico Monti Xavier Bresson Michael M. Bronstein
references.title: CayleyNets: Graph convolutional neural networks with complex rational spectral filters
references.venue: IEEE Trans. Signal Process.,
references.authors: Ron Levie Wei Huang Lorenzo Bucci Michael M Bronstein Gitta Kutyniok
references.title: Transferability of spectral graph convolutional neural networks
references.authors: Qimai Li Zhichao Han Xiao-Ming Wu
references.title: Deeper insights into graph convolutional networks for semi-supervised learning
references.venue: In Proc. 32nd AAAI Conf. Artif. Intell.,
references.authors: Shouheng Li Dongwoo Kim Qing Wang
references.title: Beyond low-pass filters: Adaptive feature propagation on graphs
references.venue: In ECML PKDD 2021 Joint Eur. Conf. Mach. Learn. Knowl. Discov. Databases,
references.authors: Yimeng Min Frederik Wenkel Guy Wolf
references.title: Scattering GCN: overcoming oversmoothness in graph convolutional networks
references.venue: In Adv. Neural Inf. Process
references.authors: Sunil K Narang Antonio Ortega
references.title: Perfect reconstruction two-channel wavelet filter banks for graph structured data
references.venue: IEEE Trans. Signal Process.,
references.authors: Sunil K Narang Antonio Ortega
references.title: Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs
references.venue: IEEE Trans. Signal Process.,
references.authors: Nicolò Navarin Wolfgang Erb Luca Pasa Alessandro Sperduti
references.title: Linear graph convolutional networks
references.venue: In 28th Eur. Symp. Artif. Neural Netw., Comput. Intell. Mach. Learn.,
references.authors: Hoang NT Takanori Maehara
references.title: Revisiting graph neural networks: All we have is low-pass filters
references.venue: arXiv preprint arXiv:1905.09550,
references.authors: Hoang NT Takanori Maehara Tsuyoshi Murata
references.title: Adaptive stacked graph filter, 2021
references.venue: URL https://openreview.net/forum?id=6VPl9khIMz
references.authors: Luca Pasa Nicolò Navarin Alessandro Sperduti
references.title: Polynomial graph convolutional networks, 2021
references.venue: URL https://openreview.net/forum?id=uqD-un_Mzd-
references.authors: Adam Paszke
references.title: Automatic differentiation in PyTorch
references.venue: In Adv. Neural Inf. Process. Syst., Autodiff Workshop,
references.authors: Hongbin Pei Bingzhe Wei Kevin Chen-Chuan Chang Yu Lei Bo Yang
references.title: Geom-gcn: Geometric graph convolutional networks
references.venue: In 8th Int. Conf. Learn. Rep. OpenReview.net,
references.authors: David I. Shuman Sunil K. Narang Pascal Frossard Antonio Ortega Pierre Vandergheynst
references.title: The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains
references.venue: IEEE Signal Process. Mag.,
references.authors: Yuichi Tanaka Akie Sakiyama
references.title: m-channel oversampled graph filter banks
references.venue: IEEE Trans. Signal Process.,
references.authors: Jie Tang Jimeng Sun Chi Wang Zi Yang
references.title: Social influence analysis in large-scale networks
references.venue: In Proc. 15th ACM SIGKDD Int. Conf. Knowl. Disc. Data Min.,
references.authors: Dorina Thanou David I Shuman Pascal Frossard
references.title: Learning parametric dictionaries for signals on graphs
references.venue: IEEE Trans. Signal Process.,
references.authors: Nicolas Tremblay Paulo Gonçalves Pierre Borgnat
references.title: Design of graph filters and filterbanks
references.venue: In Cooperative and Graph Signal Processing,
references.authors: Petar Velikovi
references.title: Graph attention networks
references.venue: In 6th Int. Conf. Learn. Rep., Vancouver, BC,
references.authors: Felix Wu Amauri Souza Tianyi Zhang Christopher Fifty Tao Yu Kilian Weinberger
references.title: Simplifying graph convolutional networks
references.venue: In Proc. 36th Int. Conf. Mach. Learn.,
references.authors: Zonghan Wu Shirui Pan Guodong Long Jing Jiang Chengqi Zhang
references.title: Beyond low-pass filtering: Graph convolutional networks with automatic filtering
references.venue: arXiv preprint arXiv:2107.04755,
references.authors: Keyulu Xu Weihua Hu Jure Leskovec Stefanie Jegelka
references.title: How powerful are graph neural networks
references.venue: In 7th Int. Conf. Learn. Rep., New Orleans, LA,
references.authors: Keyulu Xu
references.title: Representation learning on graphs with jumping knowledge networks
references.venue: In Proc. 35th Int. Conf. Mach. Learn.,
references.authors: Hao Zhu Piotr Koniusz
references.title: Simple spectral graph convolution
references.venue: In 9th Int. Conf. Learn. Rep.,
references.authors: Jiong Zhu Yujun Yan Lingxiao Zhao Mark Heimann Leman Akoglu Danai Koutra
references.title: Beyond homophily in graph neural networks: Current limitations and effective designs
references.venue: In Adv. Neural Inf. Process. Syst
references.authors: Pei
references.title: 2020) from the film-director-actor-writer network
references.authors: Fey Lenssen
references.title: The network architecture consists of two layers
references.authors: Hu
references.title: 2020), in the experiments. The graph version of CIFAR-10 is composed from the super
references.authors: Min
references.title: 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
references.authors: Dong et al Pasa
references.title: 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
references.venue: (Li et al.,
sections.heading: 1 INTRODUCTION
sections.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.
sections.heading: 2 RELATED WORK
sections.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.
sections.heading: 3 PRELIMINARIES AND PROBLEMS
sections.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.
sections.heading: 4 THE BANKGCN ALGORITHM
sections.text: In this section, we first outline the framework of BankGCN, then present its main elements, and finally discuss connections with spectral methods.
sections.heading: 4.1 GRAPH CONVOLUTION WITH ADAPTIVE FILTER BANKS
sections.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.
sections.heading: 4.2 SUBSPACE PROJECTION
sections.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.
sections.heading: 4.3 FILTERS
sections.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.
sections.heading: 4.4 DIVERSITY REGULARIZATION FOR FILTER BANKS
sections.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.
sections.heading: 4.5 DISCUSSION
sections.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.
sections.heading: 5 EXPERIMENTS
sections.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.
sections.heading: 5.2 GRAPH CLASSIFICATION
sections.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.
sections.heading: 6 CONCLUSION
sections.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.
sections.heading: A NOTATIONS AND PRELIMINARIES
sections.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).
sections.heading: B PROOF OF PROPOSITION 1
sections.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.
sections.heading: C EXPERIMENTAL SETTINGS ON NODE CLASSIFICATION
sections.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).
sections.heading: D EXPERIMENTAL SETTINGS ON GRAPH CLASSIFICATION
sections.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.
sections.heading: E MORE EXPERIMENTAL RESULTS AND ANALYSIS
sections.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.
sections.heading: F MORE COMPARISONS WITH RELATED WORKS
sections.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.