Graph Neural Networks with Learnable and Optimal Polynomial Bases
Polynomial filters, a kind of Graph Neural Networks, typically use a
predetermined polynomial basis and learn the coefficients from the training
data. It has been observed that the effectiveness of the model is highly
dependent on the property of the polynomial basis. Consequently, two natural
and fundamental questions arise: Can we learn a suitable polynomial basis from
the training data? Can we determine the optimal polynomial basis for a given
graph and node features?
  In this paper, we propose two spectral GNN models that provide positive
answers to the questions posed above. First, inspired by Favard's Theorem, we
propose the FavardGNN model, which learns a polynomial basis from the space of
all possible orthonormal bases. Second, we examine the supposedly unsolvable
definition of optimal polynomial basis from Wang & Zhang (2022) and propose a
simple model, OptBasisGNN, which computes the optimal basis for a given graph
structure and graph signal. Extensive experiments are conducted to demonstrate
the effectiveness of our proposed models. Our code is available at
https://github.com/yuziGuo/FarOptBasis.
Yuhe Guo, Zhewei Wei
# Graph Neural Networks with Learnable and Optimal Polynomial Bases

###### Abstract

Polynomial filters, a kind of Graph Neural Networks, typically use a predetermined polynomial basis and learn the coefficients from the training data. It has been observed that the effectiveness of the model is highly dependent on the property of the polynomial basis. Consequently, two natural and fundamental questions arise: Can we learn a suitable polynomial basis from the training data? Can we determine the optimal polynomial basis for a given graph and node features?

In this paper, we propose two spectral GNN models that provide positive answers to the questions posed above. First, inspired by Favard's Theorem, we propose the FavardGNN model, which learns a polynomial basis from the space of all possible orthonormal bases. Second, we examine the supposedly unsolvable definition of optimal polynomial basis from Wang & Zhang (2022) and propose a simple model, OptBasisGNN, which computes the optimal basis for a given graph structure and graph signal. Extensive experiments are conducted to demonstrate the effectiveness of our proposed models.

Machine Learning, Optimal Polynomial Bases, Favard-GNN, Favard-GNN, Optimal Polynomial Bases, Favard-GNN, Optimal Polynomial Bases, Favard-GNN, Optimal Polynomial Bases, Favard-GNN, Optimal Polynomial Bases, Favard-GNN, Optimal Polynomial Bases, Favard-GNN, Optimal Polynomial Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Fav-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Favard-GNN, Optimal Bases, Fav-GNN, Optimal Bases, Fav-GNN Optimal Bases, Favard-GNN, Optimal Bases, Fav-GNN Optimal Bases, Favard-GNN, Optimal Bases, Fav-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Fav-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Fav-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Fav-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Fav-GNN Optimal Bases, Fav-GNN Optimal Bases, Favard-GNN Optimal Bases, Fav-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Fav-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Fav-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Fav-GNN Optimal Bases, Fav-GNN Optimal Bases, Fav-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Fav-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Favard-GNN Optimal Bases, Fav-GNN Optimal Bases, Fav-GNN Optimal Bases, Favard-GNN Optimal Bases, Fav-GNN Optimal Bases, Favard-GNN Optimal Bases, Fav-GNN Optimal Bases, Fav-GNN Optimal Bases, Fav-GNN Optimal
als: the Three-term recurrences and its converse, Favard's Theorem. FavardGNN learns from the _whole space_ of possible orthonormal basis with \(2(K+1)\) extra parameters2. Secondly, we propose OptBasisGNN with **solvable optimal basis**. We solve the optimal basis raised by Wang & Zhang (2022) by avoiding the explicit solving of the weight function. Note that, although we write out the implicitly defined/solved polynomial series in the methodology section, we never need to solve it explicitly. Last but not least, we conduct **extensive experiments** to demonstrate the effectiveness of our proposed models.

Footnote 2: \(K\) is the truncated order of polynomial series.

## 2 Background and Preliminaries

### Background of Spectral GNNs

In this section, we provide some necessary backgrounds of spectral graph neural networks, and show how the choice of polynomial bases emerges as a problem. Notations used are summarized in Table 6 in Appendix A.

**Graph Fourier Transform.**  Consider an undirected and connected graph \(G=(V,E)\) with \(N\) nodes, its symmetric normalized adjacency matrix and laplacian matrix are denoted as \(\hat{P}\) and \(\hat{L}\), respectively, \(\hat{L}=I-\hat{P}\). _Graph Fourier Transform_, as defined in the spatial/spectral domain of graph signal processing, is analogous to the time/frequency domain Fourier Transform (Hammond et al., 2009; Shuman et al., 2013). One column in the representations of \(N\) nodes, \(X\in\mathbb{R}^{N\times d}\), is considered a _graph signal_, denoted as \(x\). The complete set of \(N\) eigenvectors of \(\hat{L}\), denoted as \(U\), who show varying structural frequency characteristics (Shuman et al., 2013), are used as _frequency components_. _Graph Fourier Transform_ is defined as \(\hat{x}:=U^{T}\underline{x}\), where signal \(x\) is projected to the frequency responses of all components. It is then followed by _modulation_, which suppresses or strengthens certain frequency components, denoted as \(\hat{x}^{\star}:=\operatorname{diag}\{\theta_{0},\cdots,\theta_{N-1}\}\hat{x}\). After modulation, _inverse Fourier Transform_: \(x^{\star}:=U\hat{x}^{\star}\) transforms \(\hat{x}^{\star}\) back to the spatial domain. The three operations form the process of _spectral filtering_: \(\left|\underline{U}\operatorname{diag}\{\theta_{0},\theta_{1},\ldots,\theta_{N -1}\}U^{T}x\left(\ref{eq:1}\right)\right|\).

**Polynomial Approximated Filtering.**  In order to avoid time-consuming eigen-decomposition, a line of work approximate \(\theta_{i}\) by polynomial function of \(\lambda_{i}\), which is the \(i\)-th eigenvalue of \(\hat{L}\), i.e. \(\theta_{i}\approx h(\lambda_{i})\). Equation (1) then becomes a form that is easy for fast _localized_ calculation: \(U\operatorname{diag}\{h(\lambda_{0}),h(\lambda_{1}),\ldots,h(\lambda_{N-1})\}U^ {T}x=h(\hat{L})x\).

As listed in Introduction, various _polynomial bases_ have been utilized, denoted as \(h(\lambda)=\sum_{k=0}^{K}\alpha_{k}g_{k}(\lambda)\). The filtering process on the input signal \(x\) is then expressed as \(x\to z=\sum_{k=0}^{K}\alpha_{k}g_{k}(\hat{P})x\). When considering independent filtering on each channel of the node feature matrix \(X\) simultaneously, the **multichannel filtering** can be denoted as: \(X\to Z=\mathop{\parallel}\limits_{l\in[1,h]}\sum_{k=0}^{K}\alpha_{k,l}g_{k,l}( \hat{P})X_{:,l}\left(\ref{eq:2}\right)\).

For further simplicity, we equivalently use \(b(\hat{P})\) instead of \(h(\hat{L})\) in this paper, where \(b(\hat{P}):=h(I-\hat{P})\). Note that \(b(\cdot)\) is defined on the spectrum of \(\hat{P}\), and the \(i\)-th eigenvalue of \(\hat{P}\), denoted as \(\mu_{i}\), equals \(1-\lambda_{i}\).

### Orthogonal and Orthonormal Polynomials

In this section, we give a formal definition of orthogonal and orthonormal polynomials, which plays a central role in the choosing of polynomial bases (Simon, 2014).

**Inner Products.**  The inner product of polynomials is defined as \(\left\langle f,g\right\rangle:=\int_{a}^{b}f(x)g(x)w(x)\mathrm{d}x\), where \(f\), \(g\) and \(w\) are functions of \(x\) on interval \((a,b)\), and the _weight function_\(w\) should be non-negative to guarantee the positive-definiteness of inner-product space.

The definition of the inner products induces the definitions of _norm_ and _orthogonality_. The norm of polynomial \(f\) is defined as: \(\left\|f\right\|=\sqrt{\left\langle f,f\right\rangle}\), and \(f\) and \(g\) are orthogonal to each other when \(\left\langle f,g\right\rangle=\overline{0}\). Notice that the concept of inner product, norm, and orthogonality are all defined with respect to some weight function.

**Orthogonal Polynomials.**  A sequence of polynomials \(\{p_{n}(x)\}_{n=0}^{\infty}\) where \(p_{n}(x)\) is of exact degree \(n\), is called _orthogonal_ w.r.t. the positive weight function \(w(x)\), if, for \(m,n=0,1,2,\cdots\), there exists \(\left\langle p_{n},p_{m}\right\rangle=\delta_{mn}\|p_{n}\|^{2}(\|p_{n}\|^{2}\neq 0)\), where the inner product \(\left\langle f,g\right\rangle\) is defined w.r.t. \(w(x)\). When \(\|p_{n}\|^{2}=1\) for \(n=0,1,2,\cdots\), \(\{p_{n}(x)\}_{n=0}^{\infty}\) is known as **orthonormal** polynomial series.

When a weight function is given, the orthogonal or orthonor

Figure 1: Representation of \(h(\lambda)=\lambda^{2}+1\) by different bases.
mal series with respect to the weight function can be solved by _Gram-Schmidt process_.

_Remark 2.1_.: In this paper, the orthogonal/orthonormal polynomial bases we consider are truncated polynomial series, i.e. the polynomials that form a basis are of increasing order.

## 3 Learnable Basis via Favard's Theorem

Empirically, spectral GNNs with different polynomial bases vary in performance on different datasets, which leads to two observations: (1) the choice of bases matters; (2) whether a basis is preferred might be related to the input, i.e. different signals on their accompanying underlying graphs.

For the first observation, we notice that up to now, polynomial filters _pick_ polynomial bases from well-studied polynomials, e.g. Chebyshev polynomials, Bernstein polynomials, _etc_, which narrows down the range of choice. For the second observation, we question the reasonableness of fixing a basis during training. A related effort is made by JacobiConv (Wang et al., 2019), who adapt to a Jacobi polynomial series from the family of Jacobi polynomials via _hyperparameter tuning_. However, the range they choose from is discrete. Therefore, we aim at dynamically **learn** polynomial basis from the input from a **vast range**.

### Recurrence Formula for Orthonormal Bases

Luckily, the Three-term recurrences and Favard's theorem of orthonormal polynomials provide a _continuous_ parameter space to learn basis. Generally speaking, three-term recurrences states that every orthonormal polynomial series satisfies a very characteristic form of recurrence relation, and Favard's theorem states the converse.

**Theorem 3.1** (Three Term Recurrences for Orthonormal Polynomials).: _(Gautschi, 2004, p. 12) For orthonormal polynomials \(\{p_{k}\}_{k=0}^{\infty}\) w.r.t. weight function \(w\), suppose that the leading coefficients of all polynomials are positive, there exists the three-term recurrence relation:_

\[\sqrt{\beta_{k+1}}\,p_{k+1}(x)=(x-\gamma_{k})p_{k}(x)-\sqrt{\beta_{k}}\,p_{k- 1}(x),\]

\[p_{-1}(x):=0,\;p_{0}(x)=1/\sqrt{\beta_{0}},\]

\[\gamma_{k}\in\mathbb{R},\;\sqrt{\beta_{k}}\in\mathbb{R}^{+},\;k\geq 0 \tag{3}\]

_with \(\beta_{0}=\int w(x)\mathrm{d}x\)._

**Theorem 3.2** (Favard's Theorem; Orthonormal Case).: _(Favard, 1935), (Simon, 2005, p. 14) A polynomial series \(\{p_{k}\}_{k=0}^{\infty}\) who satisfies the recurrence relation in Equation (3) is orthonormal w.r.t. a weight function \(w\) that \(\beta_{0}=\int w(x)\mathrm{d}x\)._

By Theorem 3.2, any possible recurrences with the form (3) defines an orthonormal basis. By Theorem 3.1, such a formula covers the whole space of orthonormal polynomials. If we set \(\{\sqrt{\beta_{k}}\}\) and \(\{\gamma_{k}\}\) to be learnable parameters with \(\sqrt{\beta_{k}}>0(k\geq 0)\), any orthonormal basis can be obtained.

We put the more general _orthogonal_ form of Theorem 3.1 and Theorem 3.2 in Appendix B.1 to B.5. In fact, the property of three-term recurrences for orthogonal polynomials has been used multiple times in the context of current spectral GNNs to reuse \(g_{k}(\hat{P})x\) and \(g_{k-1}(\hat{P})x\) for the calculation of \(g_{k+1}(\hat{P})x\). Defferrard et al. (2016) owe the fast filtering of ChebNet to employing the three-term recurrences of _Chebyshev polynomials_ (the first kind, which is orthogonal w.r.t. \(\frac{1}{\sqrt{x^{2}-1}}\)): \(T_{k+1}(x)=2xT_{k}(x)-T_{k-1}(x)\). Similarly, JacobConv (Wang and Zhang, 2022) employs the three-term recurrences for _Jacobi polynomials_ (orthogonal w.r.t. to \((1-x)^{a}(1+x)^{b}\)). In this paper, however, we focus on orthonormal bases because they minimize the mutual influence of basis polynomials and the influence of the unequal norms of different basis polynomials.

### FavardGNN

Formulation of FavardGNN.We formally write the architecture of FavardGNN (Algorithm 2), with the filtering process illustrated in FavardFiltering (Algorithm 1). Note that the iterative process of Algorithm 1 (lines 3-5) follows exactly from Equation (3) in Favard's Theorem. The key insight is to treat the coefficients \(\beta,\gamma,\alpha\) in Equation (3) as learnable parameters. Since Theorem 3.1 and
Theorem 3.2 state that the orthonormal basis must satisfy the employed iteration and vice versa, it follows that the model can learn a suitable orthonormal polynomial basis from among all possible orthonormal bases.

Following convention, before FavardFiltering, an MLP is used to map the raw features onto the signal channels (often much less than the dimension of raw features). In regression problems, the filtered signals are directly used as predictions; for classification problems, they are combined by another MLP followed by a softmax layer.

Parallel Execution.Note that for convenience of presentation, we write the FavardFiltering Algorithm in a form of nested loops. In fact, the computation on different channels (the inner loop \(k\)) is conducted simultaneously. We put more concrete implementation in PyTorch-styled the pseudocode in Appendix C.1.

### Weaknesses of FavardGNN

However, there are still two main weaknesses of FavardGNN. Firstly, the orthogonality lacks interpretability. The weight function \(w\) can only be solved analytically in a number of cases (Geronimo and Van Assche, 1991). Even if the weight function is solved, the form of \(w\) might be too complicated to understand.

Secondly, FavardFiltering is not good in convergence properties: consider a simplified optimization problem \(\min\|Z-Y\|_{F}^{2}\) which has been examined in the context of GNN (Xu et al., 2021; Wang and Zhang, 2022), even this problem is non-convex w.r.t the learnable parameters in \(Z\). We will re-examine this problem in the experiment section.

## 4 Achieving Optimal Basis

Although FavardGNN has the potential to reach the whole space of orthonormal polynomial series, on the other hand, we still want to know: **whether there is an optimal and accessible basis** in this vast space.

Recently, Wang and Zhang (2022) raises a criterion for optimal basis. Since different bases are the same in expressiveness, this criterion is induced from an angle of optimization. However, Wang and Zhang (2022) believe that this optimal basis is unreachable. In this section, we follow this definition of optimal basis, and show how we can use exactly this optimal basis with \(O(K|E|)\) time complexity.

### A Criterion for Optimal Basis

We will firstly restate the related section of Wang and Zhang (2022) very briefly, with a more complete review put in Appendix E.

**Definition of Optimal Basis.** Wang and Zhang (2022) considers the squared loss \(R=\frac{1}{2}\|Z-Y\|_{F}^{2}\), where \(Y\) is the target signal. Since each signal channel contributes independently to the loss, the authors then consider the loss function channelwisely and ignore the index \(l\), that is, \(r=\frac{1}{2}\|z-y\|_{F}^{2}\), where \(z=\sum_{k=0}^{K}\alpha_{k}g_{k}(\hat{P})x\).

Since \(r\) is convex w.r.t. \(\alpha\). the gradient descents' convergence rate reaches optimal when the **Hessian matrix** is an identity matrix. The \((k_{1},k_{2})\) element of Hessian matrix is:

\[H_{k_{1}k_{2}}=\frac{\partial r}{\partial\alpha_{k_{1}}\alpha_{k_{2}}}=x^{T}g _{k_{2}}(\hat{P})g_{k_{1}}(\hat{P})x. \tag{4}\]

**Definition 4.1** (Optimal basis for signal \(x\)).: For a given graph signal \(x\), polynomial basis \(\{g_{k}\}_{k=0}^{K}\) is optimal in convergence rate when \(H\) given in (4) is an **identity matrix**.

Unachievable Algorithm Towards Optimal Basis.Wang and Zhang (2022) continue to rewrite Equation (4) by Riemann sum: \(H_{k_{1}k_{2}}=\int_{\mu=-1}^{1}g_{k_{1}}(\mu)g_{k_{2}}(\mu)f(\mu)d\mu\), where \(f(\mu)\) is given below (Remark 4.2), and Definition 4.1 is reached when \(\{g_{k}(\cdot)\}_{k=0}^{K}\) is orthonormal polynomial basis w.r.t. \(f(\cdot)\).

_Remark 4.2_.: The **exact form of the weight function** of optimal basis defined in Definition 4.1 is \(f(\mu)=\frac{\partial F(\mu)}{\partial\mu}\), where \(F(\mu):=\sum_{\mu_{i}\leq\mu}(U^{T}x)_{i}^{2}\).

Having write out the weight function \(f(\mu)\), the optimal basis is determined. Wang and Zhang (2022) think of a regular process for getting this optimal basis, which is unreachable since eigen-decomposition is unaffordable for large graphs. We summarize this process in Algorithm 3.

```
Input: Graph signal \(x\); Normalized graph adjacency \(\hat{P}\); Truncated polynomial order \(K\). Output: Optimal basis \(\{g_{k}(\cdot)\}_{k=0}^{K}\)
1\(U,\{\mu_{i}\}_{i=1}^{N}\leftarrow\) Eigen decomposition of \(\hat{P}\)
2 Calculate \(f(\mu)\) as descripted in E.1 Use Gram-Schmidt process and weight function \(f(\mu)\) to contruct an orthonormal basis \(\{g_{k}\}_{k=0}^{K}\)
```

**Algorithm 3**An Unreachable Algorithm for Getting Optimal Basis)

As a result, Wang and Zhang (2022) come up with a compromised method that allows the model to choose from the family of orthogonal Jacobi bases, who have "_flexible enough weight functions_", i.e. \((1-\mu)^{a}(1+\mu)^{b}\), determined by two hyper-parameters \(a\) and \(b\). However, still, a very small fraction of possible weight functions are covered, possibly without the optimal weight function in Remark 4.2.
```
0: Normalized graph \(\hat{P}\); Solved basis vectors \(v_{0},\cdots,v_{k}\) (\(k\geq 0\))
0:\(v_{k+1}\)
1: Step 1: \(v_{k+1}^{*}\leftarrow\hat{P}v_{k}\)
2: Step 2: \(v_{k+1}^{\perp}\leftarrow v_{k+1}^{*}-\sum_{i=0}^{k}\langle v_{k+1}^{*},v_{i} \rangle v_{i}\)
3: Step 3: \(v_{k+1}\gets v_{k+1}^{\perp}/\|v_{k+1}^{\perp}\|\)
4return\(v_{k+1}\)
```

**Algorithm 4**ObtainNextBasisVector (Raw Version)

### From Polynomial Basis to Vector Basis

In this section, we show that the optimal bases given in Definition 4.1 can be solved efficiently in \(O(K|E|)\). Instead of following the three-step convention of Algorithm 3, we use the optimal bases **without** explicitly solving the \(f(\mu)\) and \(\{g_{k}(\mu)\}_{k=0}^{K}\) as pre-steps of polynomial filtering.

The key insight of our method is to consider the inner product space of vectors rather than that of polynomials. We shift our attention from solving orthonormal polynomial basis \(g_{k}(x)\) (w.r.t. a specific weight function) to orthonormal vector basis \(g_{k}(\hat{P})x\). Thus, we avoid the need to solve for the _inaccessible weight function_ in the habitual procedure 3, making the optimal polynomial series attainable.

**Optimal Vector Basis.** Following Wang and Zhang (2022), we consider \(x\to z=\sum_{k=0}^{K}\alpha_{k}g_{k}(\hat{P})x\) on one channel. Instead of taking \(\sum_{k=0}^{K}\alpha_{k}g_{k}(\hat{P})=b(\hat{P})\) as a whole, we now regard \(\left\{v_{k}|v_{k}:=g_{k}(\hat{P})x\right\}_{k=0}^{K}\) as a _vector basis_. Thus, the filtered signal \(z\) is a linear combination of \(\{v_{k}\}_{k=0}^{K}\).

By Definition 4.1, the optimal basis is achieved when

\[v_{k_{2}}^{T}v_{k_{1}}=x^{T}g_{k_{2}}(\hat{P})g_{k_{1}}(\hat{P})x=\delta_{k_{1 }k_{2}},\]

which is equivalent to finding a vector basis \(\{v_{k}\}_{k=0}^{K}\) that satisfies two conditions: **Condition 1**: Orthonormality. **Condition 2**: Polynomials with **increasing order**, that is, for \(k=0,1,\ldots,K\), there exists a polynomial \(g_{k}\) so that \(v_{k}=g_{k}(\hat{P})x\), where \(g_{k}(\cdot)\) is of order \(k\).

```
0: Normalized graph \(\hat{P}\); **Two** solved basis vectors \(v_{k-1},v_{k}\) (\(k\geq 0\))
0:\(v_{k+1}\)
1: Step 1: \(v_{k+1}^{*}\leftarrow\hat{P}v_{k}\) // \(g_{k+1}^{*}(\mu):=\mu g_{k}(\mu)\)
2: Step 2: \(v_{k+1}^{\perp}\gets v_{k+1}^{*}-\langle v_{k+1}^{*},v_{k}\rangle v_{k}- \langle v_{k+1}^{*},v_{k-1}\rangle v_{k-1}\) // \(g_{k+1}^{*}(\mu):=\) \(g_{k+1}^{*}(\mu)-\langle v_{k+1}^{*},v_{k}\rangle g_{k}(\mu)-\langle v_{k+1}^{* },v_{k-1}\rangle g_{k-1}(\mu)\)
3: Step 3: \(v_{k+1}\gets v_{k+1}^{\perp}/\|v_{k+1}^{\perp}\|\) // \(g_{k+1}(\mu):=g_{k+1}^{*}(\mu)/\|v_{k+1}^{*}\) return\(v_{k+1}\)
```

**Algorithm 5**ObtainNextBasisVector (In comment, we write the the \((k+1)\)-th optimal basis polynomial \(g_{k+1}(\cdot)\) based on \(g_{k}(\cdot)\) and \(g_{-1}(\cdot)\) that is implicitly used, but never solved explicitly.)

[MISSING_PAGE_POST]

Algorithm 33: Provability Based on \(\
rence in the comment of Algorithm 5, which can be written as:

\[\overline{\|v_{k+1}^{\perp}\|}g_{k+1}(\mu) =\mu g_{k}(\mu)-\langle v_{k+1}^{*},v_{k}\rangle g_{k}(\mu)\] \[-\ \langle v_{k+1}^{*},v_{k-1}\rangle g_{vk-1}(\mu). \tag{5}\]

Now, we confirm that, Equation (5) is consistent with the recurrence formula given in Equation (3). We show \(\overline{\|v_{k}^{\perp}\|}=\langle v_{k+1}^{*},v_{k-1}\rangle\) (6) in Appendix B.6.

### Formulation of OptBasisGNN

We show the procedure of OptBasisFiltering in Algorithm 6, which is the core part of the complete OptBasisGNN. Other parts of OptBasisGNN are MLP layers and softmax layers, same as in FavardGNN (Algorithm 2). The process of calculating the next basis vector and filtering on all channels are conducted in parallel. Please check the Pytorch-style pseudo-code in Appendix C.2.

Relation to FavardGNN.OptBasisGNN is a **particular case** of FavardGNN. FavardGNN is possible to reach the whole space of orthonormal bases, among all these bases, while OptBasis is the one that promises optimal convergence property.

```
Input: Input signals \(X\) with \(d\) channels; Normalized Graph \(\hat{P}\); Order \(K\) Learnable Parameters:\(\alpha\) Output: Filtered signals \(Z\) \(v_{-1}\gets 0\) for\(l=0\)to\(d-1\)do \(x\gets X_{:,l}\), \(v_{0}\gets x/\|x\|\), \(z\leftarrow\alpha_{0,l}v_{0}\) for\(k=0\)to\(K\)do \(v_{k+1}\leftarrow\)ObtainNextBasisVector(\(\hat{P}\),\(v_{k}\), \(v_{k-1}\)) \(z\gets z+\alpha_{k+1,l}v_{k+1}\) \(Z_{:,l}\gets z\) returnZ
```

**Algorithm 6**OptBasisFiltering

### Scale Up OptBasisGNN

Scaling up GNNs on large graphs is a challenging and important problem. One way to scale up GNN models is to decouple feature propagation and transformation (Chen et al., 2020; Wu et al., 2019; He et al., 2022). Similarly, we scale up OptBasisGNN by (1) drop the MLP layer before OptBasisFiltering, thus, the basis vectors for each channel are fixed; (2) **preprocess** the whole set of basis vectors (denote as \(V\in R^{d\times(K+1)\times N}\)) on CPU, and (3) conduct **batch training**: for each batch of nodes \(\mathcal{B}\), move the corresponding segment of basis vectors \(V[:,:,\mathcal{B}]\) to GPU.

## 5 Experiments

In this section, we conduct a series of comprehensive experiments to demonstrate the effectiveness of the proposed methods. Experiments consist of node classification tasks on small and large graphs, the learning of multi-channel filters, and a comparison of FavardGNN and OptBasisGNN.

### Node Classification

Experimental Setup.We include medium-sized graph datasets conventionally used in preceding graph filtering works, including three heterophilic datasets (Chameleon, Squirrel, Actor) provided by Pei et al. (2020) and two citation datasets (PubMed, Citeseer) provided by Yang et al. (2016) and Sen et al. (2008). For all these graphs, we take a \(60\%/20\%/20\%\) train/validation/test split proportion following former works, e.g. Chien et al. (2021). We report our results of twenty runs over random splits with random initialization seeds. For baselines, we choose sota spectral GNNs. For other experimental settings, please refer to Appendix D.1. Besides, for evaluation of OptBasisGNN, please also check the results in the scalability experimental section (Section 5.2).

Results.As shown in Table 1, FavardGNN and OptBasisGNN outperform most strong baselines. Especially, in Chameleon, Squirrel and Actor, we see a big lift. The vast selection range and learnable nature of FavardGNN and the optimality of convergence provided by OptBasisGNN both enhance the performance of polynomial filters, and their performances hold flat.

### Node Classification on Large Datasets

Experimental Setup.We perform node classification tasks on two large citation networks: ogbn-arxiv and ogbn-papers100M (Hu et al., 2020), and five large non-homophilic networks from the LINKX datasets (Lim et al., 2021). Except for Penn94, Genius and Twitch-Gamers, all other mentioned datasets use the scaled version of OptBasisGNN.

For ogbn datasets, we run repeating experiments on the given split with ten random model seeds, and choose baselines following the scalability experiments in ChebNetII (He et al., 2022). For LINKX datasets, we use the five given splits to align with other reported experiment results for Penn94, Genius, Twitch-Gamer and Pokec. For Wiki dataset, since the splits are not provided, we use five random splits. For baselines, we choose spectral GNNs as well as top-performing spatial models reported in Lim et al. (2021), including LINK, LINKX, GCNII (Chen et al., 2020) and MixHop (Abu-El-Haija et al., 2019). For more detailed experimental settings, please refer to Appendix D.1.

Results.As shown in Table 2 and Table 3, On Penn94, Genius and Twitch-gamer, our two models achieve compa
rable results to those of the sota spectral methods. On ogbn datasets as well as Pokec and Wiki with tens or hundreds of edges, we use the scaled version of OptBasisGNN with batch training. We do not conduct FavardGNN on these datasets, since the basis vectors of FavardGNN are cannot be precomputed. Notably, on Wiki dataset, the largest non-homophilous dataset, our method surpasses the second top method by nearly one percent, this demonstrates the effectiveness of our scaled-up version of OptBasisGNN.

### Learning Multi-Channel Filters from Signals

Experimental Setup. We extend the experiment of learning filters in He et al. (2021) and Balcilar et al. (2021). The differences are twofold: First, we consider the case of _multi-channel_ input signals and learn filters _channelwisely_. Second, the _only_ learnable parameters are the coefficients \(\alpha\). Note that the optimization target of this experiment is identical to how the optimal basis was derived by Wang and Zhang (2022) (See Section 4.1).

We put the practical backgro

\begin{table}
\begin{tabular}{l c c c c c} \hline \hline Dataset & Chamleon & Squierl & Actor & Citeseer & Pubned \\ \(\|V\|\) & 2.277 & 5.201 & 7,600 & 3,327 & 19,717 \\ \(\mathcal{H}(\mathcal{O})\) & 23 & 22 & 22 & -74 & 80 \\ \hline MLP & \(46.59\pm 1.84\) & \(31.01\pm 1.18\) & \(40.18\pm 0.55\) & \(76.52\pm 0.89\) & \(86.14\pm 0.25\) \\ GCN & \(60.81\pm 2.95\) & \(45.87\pm 0.8\) & \(33.26\pm 1.15\) & \(79.85\pm 0.78\) & \(86.79\pm 0.31\) \\ DehNet & \(59.51\pm 1.25\) & \(40.81\pm 0.42\) & \(37.42\pm 0.58\) & \(79.33\pm 0.57\) & \(87.82\pm 0.24\) \\ ARRA & \(60.21\pm 1.00\) & \(36.27\pm 0.62\) & \(37.67\pm 0.54\) & \(80.04\pm 0.55\) & \(86.93\pm 0.24\) \\ APPNP & \(52.15\pm 1.79\) & \(35.71\pm 0.78\) & \(39.76\pm 0.49\) & \(80.47\pm 0.73\) & \(88.13\pm 0.33\) \\ GPRCNN & \(67.49\pm 1.38\) & \(50.43\pm 1.89\) & \(39.91\pm 0.62\) & \(80.13\pm 0.84\) & \(88.46\pm 0.31\) \\ BernNet & \(68.53\pm 1.68\) & \(51.39\pm 0.92\) & \(41.71\pm 1.12\) & \(80.08\pm 0.75\) & \(88.51\pm 0.39\) \\ CheNeill & \(71.37\pm 1.01\) & \(57.72\pm 0.59\) & \(41.75\pm 1.07\) & \(80.53\pm 0.79\) & \(88.93\pm 0.29\) \\ JacobConv & \(74.26\pm 1.08\) & \(57.38\pm 1.25\) & \(41.17\pm 0.64\) & \(80.78\pm 0.79\) & \(89.62\pm 0.41\) \\ \hline FavardGNN & \(72.32\pm 1.90\) & \(63.49\pm 1.47\) & \(43.05\pm 0.53\) & \(81.89\pm 0.63\) & \(90.90\pm 0.27\) \\ OptBasisGNN & \(74.26\pm 0.74\) & \(63.62\pm 0.76\) & \(42.39\pm 0.52\) & \(80.58\pm 0.82\) & \(90.30\pm 0.19\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: **Experimental results.**_Accuracies \(\pm\)\(95\%\) confidence intervals_ are displayed for each model on each dataset. The best-performing two results are highlighted. The results of GPRCNN are taken from He et al. (2021). The results of BernNet, ChebNetII and JacobiConv are taken from original papers. The results of FavardGNN and OptBasisGNN are the average of repeating experiments over 20 cross-validation splits.

\begin{table}
\begin{tabular}{l c c c c} \hline \hline Dataset & Penn4 & Genius & Twitch-Gamers & Palace & Wiki \\ \(\|V\|\) & 41.554 & 421,961 & 168,114 & 1,632,803 & 1,925,342 \\ \(\|E\|\) & 1,562,229 & 984,979 & 6,797,557 & 30,622,564 & 303,543,860 \\ \(\mathcal{H}(\mathcal{O})\) & 470 & 618 & 545 & 445 & 389 \\ \hline MLP & \(73.61\pm 0.40\) & \(86.68\pm 0.09\) & \(60.92\pm 0.07\) & \(62.37\pm 0.02\) & \(37.38\pm 0.21\) \\ GCN & \(82.47\pm 0.27\) & \(87.42\pm 0.31\) & \(62.18\pm 0.26\) & \(75.45\pm 0.17\) & OOM \\ GCN & \(82.92\pm 0.59\) & \(90.24\pm 0.09\) & \(63.39\pm 0.61\) & \(78.94\pm 0.11\) & OOM \\ MiHoP & \(83.47\pm 0.71\) & \(90.58\pm 0.16\) & \(65.64\pm 0.27\) & \(81.07\pm 0.16\) & \(49.15\pm 0.26\) \\ INNC & \(80.79\pm 0.49\) & \(73.56\pm 0.14\) & \(64.85\pm 0.21\) & \(80.54\pm 0.03\) & \(57.11\pm 0.26\) \\ LINNK & \(84.71\pm 0.52\) & \(90.77\pm 0.27\) & \(660.06\pm 0.19\) & \(82.04\pm 0.07\) & \(59.80\pm 0.41\) \\ GPRCNN & \(83.54\pm 0.32\) & \(90.15\pm 0.30\) & \(62.59\pm 0.38\) & \(80.74\pm 0.22\) & \(58.73\pm 0.34\) \\ BernNet & \(83.26\pm 0.29\) & \(90.47\pm 0.33\) & \(64.27\pm 0.31\) & \(81.67\pm 0.17\) & \(50.92\pm 0.29\) \\ ChebNeill & \(84.86\pm 0.33\) & \(90.85\pm 0.32\) & \(65.03\pm 0.27\) & \(82.33\pm 0.28\) & \(60.09\pm 0.39\) \\ \hline FavardGNN & \(84.92\pm 0.41\) & \(90.29\pm 0.14\) & \(64.26\pm 0.12\) & - & - \\ OrblasisGNN & \(84.85\pm 0.39\) & \(90.83\pm 0.31\) & \(65.17\pm 0.16\) & \(82.83\pm 0.04\) & \(61.85\pm 0.03\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: **Experimental results of large-scale datasets (non-homophilous).**_Accuracies \(\pm\) standard errors_ are displayed for each model on each dataset. The best-performing two results are highlighted. Results of BernNet and ChebNet are taken from He et al. (2022). Other results are from Lim et al. (2021). **Note that** for the large Pokec and Wiki datasets, we use the _scaled-up_ version of OptBasisGNN, which is introduced in Section 4.4.

\begin{table}
\begin{tabular}{l c c c c} \hline \hline Original Image & Y: Band Reject & Y: Low Pass & \multirow{2}{*}{C: Band Reject} \\  & Cx: Low Pass & & & & \\ \hline \hline \multirow{4}{*}{} & & & & & \\ \cline{2-5}  & & & & \\ \cline{2-5}  & & & & \\ \cline{2-5}  & & & & & \\ \hline \hline \end{tabular}
\end{table}
Table 4: Illustration of our multichannel filter learning experiment.

\begin{table}
\begin{tabular}{l c c c c} \hline \hline Dataset & Penn4 & Genius & Twitch-Gamers & Palace & Wiki \\ \(\|V\|\) & 41.554 & 421,961 & 168,114 & 1,632,803 & 1,925,342 \\ \(\|E\|\) & 1,562,229 & 984,979 & 6,797,557 & 30,62,564 & 303,543,860 \\ \(\mathcal{H}(\mathcal{O})\) & 470 & 618 & 545 & 445 & 389 \\ \hline MLP & \(73.61\pm 0.40\) & \(86.68\pm 0.09\) & \(60.92\
periment in YCbCr color space. Each \(100\times 100\) image is considered as a grid graph with input node signals on three channels: Y, Cb and Cr. Each signal might be filtered by complex filtering operations defined in (He et al., 2021). As shown in Table 4, using different filters on each channel results in different combination effects. We create a synthetic dataset with 60 samples from 15 original images. More about the synthetic dataset are in Appendix D.2.

Following He et al. (2021), we use input signals \(X\) and the true filtered signals \(Y\) to supervise the learning process of \(\alpha\). The optimization goal is to minimize \(\frac{1}{2}\|Z-Y\|_{2}^{2}\), where \(Z\) is the output multi-channel signal defined in Equation (2). During training, we use an Adam optimizer with a learning rate of \(0.1\) and a weight decay of \(5\mathrm{e}{-4}\). We allow a maximum of \(500\) epochs, and stop iteration when the difference of losses between two epochs is less than \(1\mathrm{e}{-4}\).

For baselines, we choose the Monomial basis, Bernstein basis, Chebyshev basis (with Chebyshev interpolation) corresponding to GPRGNN, BernNet and ChebNetII, respectively. We also include arbitrary orthonormal basis learned by Favard for comparison. Note that, we learn _different filters on each channel for all baseline basis_ for fairness.

**Results.** We exhibit the mean MSE losses with standard errors of the 60 samples achieved by different bases in Table 5. Optbasis, which promises the best convergence property, demonstrates an overwhelming advantage. A special note is needed that, the Monomial basis has _not finished converging_ at the maximum allowed \(500\)th epoch. In Section 5.4, we extend the maximum allowed epochs to 10,000, and use the slowly-converging Monomial basis curve as a counterpoint to the non-converging Favard curve.

Particularly, in Figure 2, we visualize the converging process on **one sample**. Obviously, OptBasis show **best convergence property** in terms of both the fastest speed and smallest MSE error. Check Appendix D.2 for more samples.

### Non-Convergence of FavardGNN

Notably, in Figure 2, an obvious _bump_ appeared near the \(130\)th epoch. We now re-examine the non-convergence problem of FavardGNN (Section 3.3). We rerun the multi-channel filter learning task by canceling early stopping and stretching the epoch number to 10,000. As shown in Figure 3 (left), the curve of Favard bump several times. In contrast with Favard is the Monomial basis, though showing an inferior performance in Table 5, it converges slowly but stably. We observe a similar phenomenon with a node classification setup in Figure 3 (right) (See Appendix D.3 for details). Still, very large bumps appear. Such a phenomenon might seem contradictory to the outstanding performance of FavardGNN in node classification tasks. We owe the good performances in Table 1 and 2 to the early stop mechanism.

## 6 Conclusion

In this paper, we tackle the fundamental challenges of basis learning and computation in polynomial filters. We propose two models: FavardGNN and OptBasisGNN. FavardGNN learns arbitrary basis from the whole space of orthonormal polynomials, which is rooted in classical theorems in orthonormal polynomials. OptBasisGNN leverages the optimal basis defined in Wang and Zhang (2022) efficiently, which was thought unsolvable. Extensive experiments are conducted to demonstrate the effectiveness of our proposed models. An interesting future direction is to derive a convex and easier-to-optimize algorithm for FavardGNN.

Figure 3: Drop of loss in 10,000 epochs. _Left_: MSE loss of regression task on one sample. _Right_: Cross entropy loss of classification problem on the Chameleon dataset. Models based on Monomial basis converge slowly, but stably. while FavardGNNs don’t converge. For the convergence curve for OptBasis, please check Figure 2. It converges much faster than Monomial Basis.

\begin{table}
\begin{tabular}{l l l l l l} \hline \hline BASIS & OptBasis & ChebII & Bernstein & Favard & Monomial \\ \hline MSE & **0.0058** & \(0.1501\) & \(0.4231\) & \(0.3175\) & \(3.9076\) \\ \(\pm\) STDV & \(\pm\)**0.0157** & \(\pm\) 0.2433 & \(\pm\) 0.4918 & \(\pm\) 0.2840 & \(\pm\) 2.9263 \\ \hline \hline \end{tabular}
\end{table}
Table 5: Experimental results of the multichannel filtering learning task. _MSE loss \(\pm\) standard errors_ of the 60 samples achieved by different bases are exhibited.

Figure 2: Convergence rate of minimizing \(\frac{1}{2}\|Z-Y\|_{2}^{2}\) on one sample. _Sample message_: The true filters for this sample are low-pass(Y) / band-reject(Cb) / band-reject(Cr). _Legends_: ChebII means using Chebyshev polynomials combined with interpolation on chebynodes as in ChebNetII (He et al., 2022). Favard means the bases are learned as FavardGNN. In 500 epochs, the experimental groups of the Monomial basis and Bernstein basis did not converge. OptBasis achieves the smallest MSE error in the shortest time.