Automated Polynomial Filter Learning for Graph Neural Networks
Polynomial graph filters have been widely used as guiding principles in the
design of Graph Neural Networks (GNNs). Recently, the adaptive learning of the
polynomial graph filters has demonstrated promising performance for modeling
graph signals on both homophilic and heterophilic graphs, owning to their
flexibility and expressiveness. In this work, we conduct a novel preliminary
study to explore the potential and limitations of polynomial graph filter
learning approaches, revealing a severe overfitting issue. To improve the
effectiveness of polynomial graph filters, we propose Auto-Polynomial, a novel
and general automated polynomial graph filter learning framework that
efficiently learns better filters capable of adapting to various complex graph
signals. Comprehensive experiments and ablation studies demonstrate significant
and consistent performance improvements on both homophilic and heterophilic
graphs across multiple learning settings considering various labeling ratios,
which unleashes the potential of polynomial filter learning.
Wendi Yu, Zhichao Hou, Xiaorui Liu
# Automated Polynomial Filter Learning

###### Abstract.

Polynomial graph filters have been widely used as guiding principles in the design of Graph Neural Networks (GNNs). Recently, the adaptive learning of the polynomial graph filters has demonstrated promising performance for modeling graph signals on both homophilic and heterophilic graphs, owning to their flexibility and expressiveness. In this work, we conduct a novel preliminary study to explore the potential and limitations of polynomial graph filter learning approaches, revealing a severe overfitting issue. To improve the effectiveness of polynomial graph filters, we propose Auto-Polynomial, a novel and general automated polynomial graph filter learning framework that efficiently learns better filters capable of adapting to various complex graph signals. Comprehensive experiments and ablation studies demonstrate significant and consistent performance improvements on both homophilic and heterophilic graphs across multiple learning settings considering various labeling ratios, which unleashes the potential of polynomial filter learning.

Graph neural networks, automated learning, polynomial filter +
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics
+

Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
Footnote †: journal: Computer graphics

+
* We conduct a novel investigation to study whether existing approaches have fully realized the potential of graph polynomial filter learning. Surprisingly, we discover that graph polynomial filter learning suffers from a severe overfitting problem, which provides a potential explanation for its failures.
* To overcome the overfitting issue, we propose Auto-Polynomial, a novel and general automated polynomial filter learning framework to enhance the performance and generalization of polynomial graph spectral filters in GNNs.
* Comprehensive experiments and ablation studies demonstrate significant and consistent performance improvements on both homophilic and heterophilic graphs across multiple learning settings, which efficiently unleashes the potential of polynomial filter learning.

## 2. Preliminary

**Notations.** An undirected graph can be represented by \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) where \(\mathcal{V}=\{v_{1},...,v_{n}\}\) is the set of the nodes and \(\mathcal{E}=\{e_{1},...,e_{m}\}\) is the set of the edges. Suppose that the nodes are associated with the node feature matrix \(\mathbf{X}\in\mathbb{R}^{n\times d}\), where \(n\) denotes the number of nodes and \(d\) denotes the number of features per node. The graph structure of \(\mathcal{G}\) can be represented by the adjacency matrix \(\mathbf{A}\), and \(\hat{\mathbf{A}}=\mathbf{A}+\mathbf{I}\) denotes the adjacency matrix with added self-loops. Then the symmetrically normalized adjacency matrix and graph Laplacian matrix can be defined as \(\hat{\mathbf{A}}=\hat{\mathbf{D}}^{-\frac{1}{2}}\hat{\mathbf{A}}\hat{\mathbf{D }}^{-\frac{1}{2}}\) and \(\hat{\mathbf{L}}=\mathbf{I}-\hat{\mathbf{A}}=\mathbf{I}-\hat{\mathbf{D}}^{- \frac{1}{2}}\hat{\mathbf{A}}\hat{\mathbf{D}}^{-\frac{1}{2}}\) respectively, where \(\hat{\mathbf{D}}\) is the diagonal degree matrix of \(\hat{\mathbf{A}}\). Next, we will briefly introduce the polynomial graph filter as well as the concepts of homophilic and heterophilic graphs.

### Polynomial Graph Filter

Spectral-based GNNs operate graph convolutions in the spectral domain of the graph Laplacian. Many of these methods utilize polynomial graph spectral filters to achieve this operation. The polynomial graph signal filter can be formulated as follows:

\[\mathbf{Y}=\mathbf{U}diag[h(\lambda_{1}),\ldots,h(\lambda_{n})]\mathbf{U}^{ \top}\mathbf{X}=\mathbf{U}h(\mathbf{A})\mathbf{U}^{\top}\mathbf{X}\approx \sum_{k=1}^{K}\theta_{k}\hat{\mathbf{L}}^{k}\mathbf{X},\]

where \(\mathbf{X}\in\mathbb{R}^{n\times d}\) is the input signal and \(\mathbf{Y}\in\mathbb{R}^{n\times d}\) is the output signal after filtering. \(\hat{\mathbf{L}}=\mathbf{U}\mathbf{A}\mathbf{U}^{\top}\) denotes the eigendecomposition of the symmetric normalized Laplacian matrix \(\hat{\mathbf{L}}\), where \(\mathbf{U}\) denotes the matrix of eigenvectors and \(\mathbf{\Lambda}=diag[\lambda_{1},\ldots,\lambda_{n}]\) is the diagonal matrix of eigenvalues. \(h(\lambda)\) is an arbitrary filter function that can be approximated by various polynomials \(h_{\Theta}(\lambda)=\sum_{k=0}^{K}\theta_{k}\lambda^{k},\lambda\in[0,2]\), where the polynomial coefficients \(\Theta=\{\theta_{k}\}_{k=0}^{K}\) determine the shape and properties of the \(k\)-th order filter.

The filter approximation using polynomials has multiple unique advantages. First, the filtering operation represented by polynomial filters can be equivalently and efficiently computed in the spatial domain using simple recursive feature aggregations, i.e., \(\sum_{k=1}^{K}\theta_{k}\hat{\mathbf{L}}^{k}\mathbf{X}\), without resorting to expensive eigendecomposition that is infeasible for large-scale graphs. Second, the polynomial filters enable localized computations such that it only requires \(k\)-hop feature aggregation, and only \(k\) parameters are needed compared with the non-parametric filter \(h(\mathbf{\Lambda})=diag[h(\lambda_{1}),\ldots,h(\lambda_{n})]\). Most importantly, the polynomial filter is flexible and general to represent filters with various properties (Kang et al., 2017) such as low-pass filters, high-pass filters, band-pass filters, band-rejection filters, comb filters, etc. Generally, the polynomial graph filter can be written in the general form:

\[\mathbf{U}h(\mathbf{\Lambda})\mathbf{U}^{\top}\mathbf{X}\approx\mathbf{U}h_{ \Theta}(\mathbf{\Lambda})\mathbf{U}^{\top}=\sum_{k=0}^{K}\theta_{k}P_{k}( \mathbf{M}), \tag{1}\]

where \(\{\theta_{k}\}_{k=0}^{K}\) are the polynomial coefficients, \(\{P_{k}(x)\}_{k=0}^{K}\) are the polynomial basis, and \(\mathbf{M}\) is the basic matrix (e.g., normalized graph Laplacian matrix \(\hat{\mathbf{L}}\) or normalized adjacency matrix \(\hat{\mathbf{A}}\)). Among all the works based on polynomial filters, we will introduce the foundational ChebNet (Kang et al., 2017) and other improved models such as GPRGNN (Chen et al., 2017) and BernNet (Kang et al., 2017).

**ChebNet: Chebyshev polynomials.** ChebNet is a foundational work that uses the Chebyshev polynomials to approximate the graph spectral filter:

\[\sum_{k=0}^{K}\theta_{k}T_{k}(\frac{2\hat{\mathbf{L}}}{\lambda_{max}}- \mathbf{I}), \tag{2}\]

where \(\frac{2\hat{\mathbf{L}}}{\lambda_{max}}-\mathbf{I}\) denotes the rescaled Laplacian matrix, and \(\lambda_{max}\) is the largest eigenvalue of \(\hat{\mathbf{L}}\). The Chebyshev polynomial \(T_{k}(x)\) of order \(k\) can be computed by the stable recurrence relation \(T_{k}(x)=2xT_{k-1}(x)-T_{k-2}(x)\), with \(T_{0}(x)=1\) and \(T_{k}(x)=x\). The polynomial filter Eq. (2) can be regarded as a special case of the general form in Eq. (1) when we set \(P_{k}(x)=T_{k}(x)\) and \(\mathbf{M}=\frac{2\hat{\mathbf{L}}}{\lambda_{max}}-\mathbf{I}\).

**GPRGNN: Monomial polynomials.** GPRGNN approximates spectral graph convolutions by Generalized PageRank (Chen et al., 2017). The spectral polynomial filter of GPRGNN can be represented as follows:

\[\sum_{k=0}^{K}\theta_{k}\hat{\mathbf{A}}^{k}, \tag{3}\]

which is equivalent to the general form in Eq. (1) when we set \(P_{k}(x)=x^{k}\) and \(\mathbf{M}=\hat{\mathbf{A}}\).

**BernNet: Bernstein polynomials.** The principle of BernNet is to approximate any filter on the normalized Laplacian spectrum of a graph using K-order Bernstein polynomials. By learning the coefficients of the Bernstein Basis, it can adapt to different signals and get various spectral filters. The spectral filter of BernNet can be formulated as:

\[\sum_{k=0}^{K}\theta_{k}\frac{1}{2^{K}}\left(\begin{array}{c}K\\ k\end{array}\right)(2\mathbf{I}-\hat{\mathbf{L}})^{K-k}\hat{\mathbf{L}}^{k}, \tag{4}\]

which is equivalent to the general form in Eq. (1) when we set \(P_{k}(x)=\frac{1}{2^{K}}\left(\begin{array}{c}K\\ k\end{array}\right)(2-x)^{K-k}x^{k}\) and \(\mathbf{M}=\hat{\mathbf{L}}\).

In the aforementioned GNNs, the coefficients, i.e., \(\Theta\), determining the polynomial filters are treated as learnable parameters together with other model parameters that are learned by gradient descent algorithms based on the training loss. They have shown encouraging performance on both homophilic and heterophilic graphs since the filter can be adapted to model various types of graph signals whose proper assumptions are generally complex and unknown.
### Homophily and Heterophily

Graphs can be classified into homophilic graphs and heterophilic graphs based on the concept of node homophily (Zhou et al., 2017; Li et al., 2018; Li et al., 2019). In homophilic graphs, nodes with similar features or belonging to the same class tend to connect with each other. For example, in citation networks, papers in the same research field tend to cite each other (Beng et al., 2017). In other words, homophilic graphs usually satisfy the smoothness assumption that the graph signal is smooth over the edges. The majority of GNNs are under homophily assumption, and their manually designed low-pass filters filter out the high-frequency graph signal via simple neighborhood aggregation mechanisms that propagate the graph information. For instance, GCN (Girshick et al., 2015) uses the first-order Chebyshev polynomial as graph convolution, which is proven to be a fixed low-pass filter (Zhou et al., 2017). APPNP (Zhou et al., 2017) uses a Personalized Pagerank(PPR) to set fixed filter coefficients, which has been shown to surpass the high-frequency graph signals (Beng et al., 2017). Generally, these manually designed graph filters exhibit superior performance in various prediction tasks on homophilic graphs.

On the other hand, in heterophilic graphs, nodes with different features or belonging to different classes tend to connect with each other. For example, in dating networks, most users tend to establish connections with individuals of the opposite gender, exhibiting heterophily (Zhou et al., 2017). In molecular networks, protein structures are more likely to be composed of connections between different types of amino acids (Li et al., 2019). In order to quantify the degree of homophily of the graphs, Pei et al (Pei et al., 2019) have proposed a metric to measure the level of node homophily in graphs:

\[H(\mathcal{G})=\frac{1}{|\mathcal{V}|}\sum_{v\in\mathcal{V}}\frac{|\{u\in \mathcal{N}(v):y_{v}=y_{u}\}|}{|\mathcal{N}(v)|} \tag{5}\]

where \(\mathcal{N}(v)\) denotes the neighbour set of node \(v\), and \(y_{v}\) denotes the label of node \(v\). This metric \(H(\mathcal{G})\) measures the average probability that an edge connects two nodes of the same label over all nodes in \(\mathcal{V}\). When \(H(\mathcal{G})\to 1\), it indicates the graph is of high homophily since the edge always connects nodes with the same label, while \(H(\mathcal{G})\to 0\) indicates the graph is of high heterophily where edge always connect nodes with different labels. In fact, the proper prior knowledge of the heterophilic graphs is generally unknown. Therefore, those classic GNNs cannot perform well on heterophilic graphs since their expressive power is limited by fixed filters.

In recent years, many works have been actively exploring GNNs under heterophily. Some examples of heuristic approaches include MixHop (Beng et al., 2017), H2GCN (Li et al., 2019), and GCNII (Beng et al., 2017). For example, MixHop (Beng et al., 2017) is an exemplary method that aggregates messages from higher-order neighbors, thereby enabling the integration of information from different distances. Another notable approach is H2GCN (Li et al., 2019), which aims to address heterophily by separating the ego and neighbor embeddings. GCNII (Beng et al., 2017) adopts various residual connections and more layers to capture distant information in graphs. They all attempt to aggregate information from higher-order neighbors. There also exist multiple approaches inspired by polynomial graph filters (Beng et al., 2017; Li et al., 2019; Li et al., 2019). These polynomial graph filter learning approaches have better interpretability than heuristic methods, and they exhibit encouraging performance on some heterophilic graphs, owing to the flexibility and adaptivity to graph signals of various properties. However, there is no consistent performance advantage for either heuristic or graph polynomial filter learning approaches. Both types of methods sometimes underperform graph-agnostic MLPs.

## 3. Overfitting of Graph Polynomial Filter Learning

In this section, we design novel preliminary experiments to investigate the potential and limitations of polynomial graph filter learning in GNNs.

### Search of optimal polynomials

Theoretically speaking, polynomial-based GNNs have strong flexibility, adaptivity, and expressiveness as discussed in Section 2. Although they achieve encouraging performance in some cases, they often fail to show consistent improvement and advantages over simpler designs in practice. On one hand, polynomial-based GNNs do not exhibit notably better performance than manually designed GNNs such as APPNP (Zhou et al., 2017) and GCNII (Beng et al., 2017) on homophilic datasets even though these manually designed GNNs simply emulate low-pass filters and can be covered and approximated as special cases of polynomial-based GNNs. On the other hand, polynomial-based GNNs (Beng et al., 2017; Li et al., 2019; Li et al., 2019) tend to learn inappropriate polynomial weights and often exhibit inferior performance. For example, ChebNet performs noticeably worse than its simplified version, GCN (Girshick et al., 2015), which only utilizes the first two Chebyshev polynomials; The improved variants such as GPRGNN (Beng et al., 2017) and BernNet (Li et al., 2019) can not consistently outperform heuristically and manually designed alternatives such as H2GCN (Li et al., 2019); and they even underperform graph-agnostic MLPs in some cases.

The failures of polynomial-based GNNs are counterintuitive considering their strong expressively, which then leads to the following critical question: "**Have we achieved the full expressiveness and adaptivity of polynomial graph filter learning?**" To answer this question, we design a novel experiment to explore the full potential of polynomial filters, i.e., the best performance that the optimal polynomial filter can potentially achieve. Specifically, we choose the monomial polynomial (i.e., \(\sum_{k=0}^{K}\theta_{k}\hat{\mathbf{A}}^{k}\)) as designed in GPRGNN and perform a brute-force search to explore the optimal polynomial filter by a grid search on the polynomial coefficients \(\{\theta_{k}\}_{k=0}^{K}\) based on validation accuracy. We denote the GPRGNN with this optimal polynomial filter as GPRGNN-optimal. We compare the performance with the baseline GPRGNN whose polynomial coefficients are learnable parameters guided by training loss.

In detail, we evaluate the performance on semi-supervised node classification tasks on some classic homophilic and heterophilic datasets. In practice, it is computationally expensive to conduct an exhaustive brute-force search on the polynomial coefficients if the polynomial order \(K\) is large or the search granularity is fine since the search space will exponentially increase. To reduce the search space for this preliminary study, we set the polynomial order \(K=2\) so that we only need to do a grid search over 3 parameters in the range \(\{-0.9,-0.5,-0.2,-0.1,-0.05,0,0.05,0.1,0.2,0.5,0.9\}\). While this coarse search can not cover the whole search space, the results provide performance lower bounds for the optimal polynomial filter. For all models, we adopt the sparse splitting (10% training, 10% validation, and 80% testing) in both homophilic and heterophilic
datasets. We tune the hyperparameters such as learning rate and weight decay for GPRGNN following the original paper [5]. We run the experiments for 10 random data splits and report the mean and standard deviation. The comparison in Figure 1 shows the following observations:

* On homophilic datasets, i.e., Figure 1(a), GPRGNN underperforms GPRGNN-optimal on Cora and CiteSeer, and they achieve comparable performance on PubMed and Computers. Both of them outperform MLP significantly on all datasets. This demonstrates that GPRGNN can learn effective low-pass filters to model the graph signal for homophilic graphs, but it does not fully reach its maximum potential and is notably inferior to the optimal polynomial filter (GPRGNN-optimal) in some cases.
* On heterophilic datasets, i.e., Figure 1(b), GPRGNN exhibits significantly worse performance than GPRGNN-optimal, indicating that GPRGNN learns suboptimal filters. Moreover, GPRGNN does not show notably better performance than MLP, and it even underperforms MLP significantly on Cornell and Texas datasets while GPRGNN-optimal is consistently superior to MLP. This demonstrates that GPRGNN struggles to model the complex graph signal in heterophilic graphs and is far from achieving its theoretical learning potential as indicated by GPRGNN-optimal.
* GPRGNN exhibits unstable performance and high randomness. The learning process of GPRGNN is heavily influenced by the

Figure 1. The comparison between MLP, GPRGNN, and GPRGNN-optimal on homophilic and heterophilic datasets.

Figure 2. The training/validation/test accuracy of GPRGNN and GPRGNN-optimal in the training process.
randomness of weights initialization, data splitting and optimization process, leading to a large variance of the final results.

These observations reveal that GNNs based on the polynomial filters indeed have great potential, but the current learning approach is suboptimal, which prevents them from showcasing their optimal capacity. However, the reasons for such failures are unclear.

### Overfitting issue

In this section, we provide further insight into the failures of polynomial filter learning in GNNs and reveal one of the key obstacles to their success. Specifically, we compare the training process of GPRGNN and GPRGNN-optimal by measuring their training, validation, and testing accuracy during the training process. We adopt the same settings in Section 3.1, and only run one split. The training process as shown in Figure 2 provides the following observation:

* GPRGNN always achieves perfect training accuracy close to 100% on all datasets, but its validation performance and test performance are significantly lower. This reveals that the polynomial filter is flexible enough so that the training data can be perfectly fitted but the big generalization gap does not deliver satisfying performance on validation and test data.
* GPRGNN-optimal achieves lower training accuracy than GPRGNN, but its validation and test performance are notably better than GPRGNN. This indicates that GPRGNN suffers from a severe overfitting issue while the optimal polynomial filter can mitigate the overfitting and narrow down this generalization gap.

To summarize, polynomial filter learning in GNNs suffers from a severe overfitting problem that leads to poor generalization. This provides a plausible explanation for the failures of polynomial-based GNNs regardless of their powerful expressiveness.

## 4. Auto-polynomial

In this section, we introduce a novel and general automated polynomial filter learning approach to address the aforementioned overfitting issues and improve the effectiveness of graph polynomial filters.

### Automated polynomial filter learning

The polynomial coefficients in polynomial filters serve as key parameters that have a strong influence on the prediction of GNNs. Existing polynomial-based GNNs such as ChebNet, GPRGNN, and BernNet treat the polynomial coefficients the same as other model parameters, both of which are jointly learned through gradient descent algorithms such as Adam (Kingma and Ba, 2014) according to the training loss. Our preliminary study in Section 3 reveals the suboptimal of the widely used polynomial filter learning approach. This suboptimality is partially due to the severe overfitting problem since the filters are adjusted to perfectly fit the labels of training nodes that have a low ratio in the typical semi-supervised learning settings for graph deep learning (Kingma and Ba, 2014; Wang et al., 2015). On the other hand, our brute-force search on the polynomial filter based on the validation accuracy achieves consistently better performance and mitigates the overfitting issues. However, when the polynomial order \(K\) is large, it is not plausible to brute-force search the optimal polynomials by trial and error. This motivates us to develop a better automated learning approach for polynomial graph filter learning that mitigates the overfitting.

**Auto-Polynomial.** We propose Auto-Polynomial, a novel automated polynomial filter learning approach that learns the polynomial coefficients guided by the validation loss inspired by hyperparameter optimization (HPO) and automated machine learning (AutoML). Instead of treating polynomial coefficients the same as other model parameters, we consider these polynomial coefficients as hyperparameters. Let the polynomial coefficients \(\Theta=\{\theta_{k}\}_{k=0}^{K}\) represent GNNs with different filtering properties and \(w\) denotes other learnable weights in GNNs. The main idea behind Auto-Polynomial is to jointly optimize the coefficients \(\Theta\) and the weights \(w\) but with totally different targets. Formally, we model the automated polynomial filter learning as a bi-level optimization problem:

\[\begin{split}\min_{\Theta}&\mathcal{L}_{\textit{o}al }(w^{*}(\Theta),\Theta)\\ \text{s.t.}& w^{*}(\Theta)=\operatorname*{argmin}_{w}( \mathcal{L}_{train}(w,\Theta))\end{split} \tag{6}\]

where the lower-level optimization problem finds the best model parameters \(w^{*}(\Theta)\) based on training loss while the upper-level problem finds the optimal polynomial filter represented by \(\Theta\) based on validation loss. Guided by this bi-level optimization problem, the learned GNN model can not only fit the training data accurately but also enhance its performance on validation data, which helps improve generalization ability and alleviate the overfitting problem.

**Approximate Computation.** The bi-level problem can be solved by alternating the optimization between lower-level and upper-level problems. However, the optimal solution \(w^{*}(\Theta)\) in the lower-level problem has a complicated dependency on polynomial coefficients \(\Theta\) so that the meta-gradient of upper-level problem, i.e., \(\nabla_{\Theta}\mathcal{L}_{\textit{o}al}(w^{*}(\Theta),\Theta)\), is hard to compute. This complexity becomes even worse when the lower-level problem adopts multiple-step iterations. Therefore, we adopt a simplified and elegant method inspired by DARTS (DARTS, 2015) to approximate the gradient computation in problem (6):

\[\nabla_{\Theta}\mathcal{L}_{\textit{o}al}(w^{*}(\Theta),\Theta)\approx\nabla _{\Theta}\mathcal{L}_{\textit{o}al}(w-\xi\,\nabla_{w}\,\mathcal{L}_{train}(w, \Theta),\Theta) \tag{7}\]

where \(\xi\) denotes the learning rate for the lower-level optimization, and only one step gradient is used to approximate the optimal model \(w^{*}(\Theta)\). This approximation provides a reasonable solution since \(w\) will accumulate the update from all previous training iterations and its initial value \(w\) might not be too far away from the optima.

In particular, if we set \(\xi=0\), Equation (7) is equivalent to updating \(\Theta\) based on the current weights \(w\), which is a first-order approximation, a much simpler form of the problem. Although first-order approximation may not provide the best result, it can improve computational efficiency. If we use \(\xi>0\), then we can use chain rule to approximate Equation (7):

\[\nabla_{\Theta}\mathcal{L}_{\textit{o}al}\left(w^{\prime},\Theta\right)-\xi \nabla_{\Theta,w^{\prime}}^{2}\mathcal{L}_{train}(w,\Theta)\nabla_{w^{\prime}} \mathcal{L}_{\textit{o}al}\left(w^{\prime},\Theta\right) \tag{8}\]

where \(w^{\prime}=w-\xi\nabla_{w}\mathcal{L}_{\textit{train}}\left(w,\Theta\right)\) denotes the weights after one step gradient descent. In practice, we can apply the finite difference method (DARTS, 2015) to approximate the second term in Equation (8):

\[\begin{split}&\nabla_{\Theta,w}^{2}\mathcal{L}_{\textit{train}} \left(w,\Theta\right)\nabla_{w^{\prime}}\mathcal{L}_{\textit{o}al}\left(w^{ \prime},\Theta\right)\\ &\approx\frac{\nabla_{\Theta}\mathcal{L}_{train}\left(w^{+}, \Theta\right)-\nabla_{\Theta}\mathcal{L}_{train}\left(w^{-},\Theta\right)}{2 \xi}\end{split} \tag{9}\]
where \(\varepsilon\) denotes a small scalar in finite difference approximation, \(w^{+}=w+\varepsilon\nabla_{w^{\prime}}\mathcal{L}_{\mathit{real}}\left(w^{\prime}, \Theta\right)\), and \(w^{-}=w-\varepsilon\nabla_{w^{\prime}}\mathcal{L}_{\mathit{real}}\left(w^{ \prime},\Theta\right)\). In practice, we also introduce a hyper-parameter \(freq\) that specifies the update frequency of polynomial coefficients to further improve the efficiency by skipping this computation from time to time.

### Use cases

The proposed Auto-Polynomial is a general polynomial filter learning framework and it can be applied to various polynomial filter-based GNNs. In this section, we will introduce some representative examples to showcase its application.

**Case 1: Auto-GPRGNN.** In GPRGNN (Girani et al., 2017), the weights of Generalized PageRank (GPR), i.e., polynomial coefficients \(\Theta\) in Equation (3), are trained together with the model parameters \(w\). The GPR weights \(\Theta\) can be adaptively learned during the training process to control the contribution of the node features and their propagated features in different aggregation layers. GPR provides a flexible way to model various graph signals. However, our preliminary study in Section 3 has shown that GPRGNN can not learn effective filters and faces a serious overfitting problem for the learning of polynomial coefficients. Moreover, its performance is very sensitive to the initialization of filters, data split, and random seeds. The proposed Auto-Polynomial framework can help mitigate these problems. Instead of learning two types of parameters simultaneously, we treat the training of the model parameter \(w\) and the GPR weight \(\Theta\) as the lower-level and upper-level optimization problems in Equation (6), respectively. In this work, we denote GPRGNN using Auto-Polynomial as Auto-GPRGNN.

**Case 2: Auto-BernNet.** In BernNet (Han et al., 2017), the coefficients of the Bernstein basis \(\Theta\) can be learned end-to-end to fit any graph filter in the spectral domain. The training process of BernNet is slightly different from GPRGNN since BernNet specifies an independent learning rate for the polynomial coefficients. To some extent, the learning of polynomial coefficients \(\Theta\) is slightly distinguished from the learning of model parameters \(w\), which improves the model performance. However, this learning method still has not really brought out the potential of BernNet, and faces the problem of overfitting, especially under semi-supervised learning on heterophilic data. Applying the proposed Auto-Polynomial method to BernNet can ease this problem. We can regard the Bernstein basis coefficients \(\Theta\) in BernNet as hyperparameters and optimize them in the Auto-Polynomial bi-level optimization problem. Analogously, we refer to BernNet with Auto-Polynomial as Auto-BernNet.

### Implementation

In this section, we demonstrate the implementation details of Auto-Polynomial and present the learning procedure in Algorithm 1.

```
Input:\(\Theta\): coefficients of polynomial filter \(\xi\): learning rate for the lower-level approximation \(\eta_{0}\): learning rate of polynomial filter \(\eta_{1}\): learning rate of model parameters \(w\): model parameters, \(freq\): frequency to update \(\Theta\) Output: Graph polynomial filter with coefficients \(\Theta\) for\(i\gets 1\)to\(Iteration\)do (Update \(\Theta\)): if\(i\not=\theta\)then \(w^{\prime}_{i}\gets w_{i}-\xi\nabla_{w_{i}}\mathcal{L}_{train}(w_{i}, \Theta_{i})\), \(w^{\prime}_{i}\gets w_{i}+\varepsilon\nabla_{w^{\prime}_{i}}\mathcal{L}_{ \mathit{real}}\left(w^{\prime}_{i},\Theta_{i}\right)\), \(w^{\prime}_{i}\gets w_{i}-\varepsilon\nabla_{w^{\prime}_{i}}\mathcal{L}_{ \mathit{real}}\left(w^{\prime}_{i},\Theta_{i}\right)\), \(\nabla^{2}_{\Theta_{i},w_{i}}\mathcal{L}_{train}(w_{i},\Theta_{i})\nabla_{w^{ \prime}_{i}}\mathcal{L}_{\mathit{real}}\left(w^{\prime}_{i},\Theta_{i}\right)\leftarrow\) Equ. (9) \(\nabla_{\Theta_{i}}\mathcal{L}_{\mathit{real}}\left(w^{*}_{i}(\Theta_{i}), \Theta_{i}\right)\leftarrow\) Equ. (8) \(\Theta_{i+1}\leftarrow\Theta_{i}-\eta_{0}\nabla_{\Theta_{i}}\mathcal{L}_{ \mathit{real}}(w^{*}_{i},\Theta_{i})\) else \(\Theta_{i+1}\leftarrow\Theta_{i}\)  end if (Update \(w\)): \(w_{i+1}=w_{i}-\eta_{1}\nabla_{w_{i}}\mathcal{L}_{train}(w_{i},\Theta_{i+1})\);  end while
```

**Algorithm 1**Auto-Polynomial Learning Algorithm

Bi-level update.The whole procedure of Auto-Polynomial includes two main steps: updating the polynomial coefficients \(\Theta\) and updating the model parameters \(w\). To update \(\Theta\), we perform gradient descent with \(\nabla_{\Theta}\mathcal{L}_{\mathit{real}}\) to enhance the generalization ability of polynomial filter learning. To reduce memory consumption and increase efficiency, we first employ the finite difference method to compute the second-order term in Equation (9) and then obtain an approximation of \(\nabla_{\Theta}\mathcal{L}_{\mathit{real}}\) as Equation (8). In practice, we introduce a hyper-parameter \(freq\) to specify the update frequency of polynomial coefficients, so as to further improve the algorithm efficiency in necessary. In other words, \(\Theta\) can be updated only once in every \(freq\) iterations of model update. To update \(w\), we utilize \(\nabla_{\Theta}\mathcal{L}_{train}\) to update the model parameters \(w\) by fitting the labels of training nodes. Through this alternating update process, we ultimately obtain appropriate polynomial coefficients and model parameters to improve the GNNs' graph modeling and generalization abilities.

**Complexity analysis.** The bi-level optimization problem in Auto-Polynomial can be solved efficiently. To be specific, we assume that the computation complexity of the original model is \(O(C)\), where \(C\) is a known constant. Then the model complexity after applying Auto-Polynomial is \(O(\frac{freq+4}{freq}C)\), as we need 4 extra forward computation when updating \(\Theta\). Therefore, the computational complexity of Auto-Polynomial is at most 5 times bigger than the backbone GNN model but it can be effectively reduced by choosing a larger \(freq\). In terms of memory cost, Auto-Polynomial does not increase the memory cost significantly no matter how large \(freq\) is. The computation time and memory cost will be evaluated in Section 5.

## 5. Experiment

In this section, we provide comprehensive experiments to validate the effectiveness of Auto-Polynomial under semi-supervised learning and supervised learning settings on both heterophilic and homophilic datasets. Further ablation studies are presented to investigate the influence of training set ratio and update frequency on the model performance.

### Baselines and Datasets

**Baselines.** We compare the proposed Auto-Polynomial, including use cases Auto-GPRGNN and Auto-BernNet, with 7 baseline
models: MLP, GCN (Zhu et al., 2017), ChebNet (Chen et al., 2017), APPNP (Zhu et al., 2017), GPRGNN (Chen et al., 2017), BernNet (Chen et al., 2017) and H2GCN (Chen et al., 2017). For GPRGNN1 and BernNet2, we use their the officially released code. For H2GCN, we use the Pytorch version of the original code. For other models, we used the implementation of the Pytorch Geometric Library (Han et al., 2017).

Footnote 1: [https://github.com/jianhao2016/GPRGNN](https://github.com/jianhao2016/GPRGNN)

**Datasets.** We conduct experiments on the most commonly used real-world benchmark datasets for node classification. We use 4 homophilic benchmark datasets, including three citation graphs including Cora, Citeseer and PubMed (Zhu et al., 2017; Zhu et al., 2017), and the Amazon copurchase graph Computers (Zhu et al., 2017). We also use 4 heterophilic benchmark datasets, including Wikipedia graphs such as Chameleon and Squirrel(Chameleon and Squirrel, 2017), and webpage graphs such as Texas and Cornell from WebKB3. We summarize the dataset statistics in Table 1.

Footnote 2: [https://github.com/jianhao2016/GPRGNN](https://github.com/jianhao2016/GPRGNN)

**Hyperparameter settings.** For APPNP, we set its propagation step size \(K=10\) and optimize the teleport probability \(\alpha\) over \(\{0.1,0.2,0.5,0.9\}\). For ChebNet, we set the propagation step \(K=2\). For GPRGNN, we set its polynomial order \(K=10\). For BernNet, we set the polynomial order \(K=10\) and tune the independent learning rate for propagation layer over \(\{0.002,0.005,0.01,0.05\}\). For H2GCN, we follow the settings in (Zhu et al., 2017). We search the embedding round \(K\) over \(\{1,2\}\). For all models except H2GCN, we use 2 layer neural networks with 64 hidden units and set the dropout rate 0.5. For Auto-GPRGNN and Auto-BernNet, we use 2-layer MLP with 64 hidden units and set the polynomial order \(K=10\). We search the meta learning rate \(\eta_{0}\) of Auto-Polynomial over \(\{0.01,0.05\}\) and weight decay over \(\{0,0.0005\}\). We search the learning rate \(\xi\) over \(\{0,0.05\}\) and the polynomial weights are randomly initialized. For all models, we adopted an early stopping strategy of 200 epochs with a maximum of 1000 epochs. We use the Adam optimizer to train the models. We optimize learning rate over \(\{0.002,0.01,0.05\}\), and weight decay over \(\{0,0.0005\}\). We select the best performance according to the validation accuracy.

### Semi-supervised node classification

**Experimental settings.** In semi-supervised learning setting, we randomly split the datasets into training/validation/test sets with the ratio of 10%/10%/80%. We run each experiment 10 times with random splits and report the mean and variance of the accuracy. Note that the data split for semi-supervised learning in the literature is quite inconsistent since existing works usually use different ratios for the homophilic and heterophilic datasets (Chen et al., 2017), or a higher fraction on both the homophilic and heterophilic datasets (Chen et al., 2017; Zhu et al., 2017; Zhu et al., 2017). To be fair, we use a consistent ratio for both the homophilic and the heterophilic datasets, which can truly reflect the adaptability of the polynomial filters on different datasets.

**Performance analysis.** The performance summarized in Table 2 shows the following major observations:

* For homophilic datasets, all GNN models outperform MLP significantly, indicating that the structure information of homophilic graphs can be learned and captured easily. Moreover, Auto-GPRGNN and Auto-BernNet can achieve the best performance in most cases, demonstrating Auto-Polynomial's superior capability in polynomial graph filter learning.
* For heterophilic datasets, some baselines such as GCN, ChebNet and GPRGNN fail to learn effective polynomial filters and they even underperform graph-agnostic MLP. However, Auto-GPRGNN and Auto-BernNet can outperform all baselines by a significant margin. For instance, Auto-GPRGNN improves over GPRGNN by 14%, 16%, 5%, and 31% on Chameleon, Cornell, Squirrel, and Texas datasets, respectively. Auto-BernNet improves over BernNet by 2%, 4%, 8%, and 4% on Chameleon, Cornell, Squirrel, and Texas datasets, respectively. Moreover, Auto-polynomial effectively reduces the standard deviations in most cases. Especially, Auto-GPRGNN archives a standard deviation 10% lower than GPRGNN on the Texas dataset. These comparisons clearly indicate that Auto-Polynomial is capable of learning polynomial filters more effectively and mitigating the overfitting issue.

### Supervised node classification

**Experimental settings.** In supervised learning setting, we randomly split the datasets into training/validation/test sets with the ratio of 48%/32%/32%, following the high ratio in the work (Chen et al., 2017). We run each experiment 10 times with random splits and report the mean and variance of the test accuracy.

**Performance analysis.** The performance summarized in Table 3 shows the following major observations:

* For homophilic datasets, most of the models performed well with small standard deviations, which shows that the existing GNNs are capable of learning proper filters for homophilic graphs. Moreover, Auto-GPRGNN and Auto-BernNet improves their backbone models, GPRGNN and BernNet, indicating that Auto-Polynomial helps them learn better polynomial filters.
* For heterophilic datasets, most of the baselines perform poorly with large standard deviations, which shows that they cannot learn heterophilic graph information well. Models using polynomial filters such as ChebNet, GPRGNN, and BernNet achieve better performance, while Auto-GPRGNN and Auto-BernNet achieve the best or second-best performance in most cases and their standard deviations are smaller in most cases. Especially, Auto-GPRGNN achieves a standard deviation 12% lower than GPRGNN on the Texas dataset. These results indicate the effectiveness of Auto-Polynomial in graph polynomial filter learning.

### Ablation study

In this section, we provide ablation studies on the labeling ratio and polynomial update frequency.

**Labeling ratio.** From the results in semi-supervised and supervised settings in Table 2 and Table 3, it appears that the improvement from Auto-Polynomial is more significant on semi-supervised tasks (low labeling ratio), as compared to supervised tasks (high labeling ratio). This phenomenon motivates the study of how the labeling ratio impacts the effectiveness of our proposed framework. To this end, we fix the validation set ratio at 10%, vary the training set
\begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline  & MLP & ChebNet & GCN & APPNP & H2GCN & GPRGNN & BernNet & Auto-GPRGNN & Auto-BernNet \\ \hline Cora & 64.79\(\pm\)0.70 & 81.37\(\pm\)0.93 & 83.11\(\pm\)1.05 & **84.71\(\pm\)0.53** & 82.84\(\pm\)0.69 & 84.37\(\pm\)0.89 & 84.27\(\pm\)0.81 & 84.71\(\pm\)1.19 & 84.66\(\pm\)0.60 \\ Citeseer & 64.90\(\pm\)0.94 & 71.56\(\pm\)0.86 & 71.67\(\pm\)1.31 & 72.70\(\pm\)0.80 & 72.61\(\pm\)0.67 & 72.17\(\pm\)0.71 & 72.08\(\pm\)0.63 & 72.76\(\pm\)1.18 & **72.85\(\pm\)0.94** \\ PubMed & 84.64\(\pm\)0.41 & 87.17\(\pm\)0.31 & 86.40\(\pm\)0.22 & 86.63\(\pm\)0.36 & 86.71\(\pm\)0.25 & 86.42\(\pm\)0.34 & **86.94\(\pm\)0.18** & 86.69\(\pm\)0.31 & 86.81\(\pm\)0.41 \\ Computers & 76.80\(\pm\)0.88 & 86.17\(\pm\)0.58 & 86.79\(\pm\)0.63 & 85.76\(\pm\)0.44 & 84.99\(\pm\)0.54 & 85.79\(\pm\)1.00 & 86.84\(\pm\)0.57 & 86.74\(\pm\)0.61 & **87.61\(\pm\)0.48** \\ Chameleon & 38.61\(\pm\)0.14 & 49.14\(\pm\)1.66 & 51.65\(\pm\)1.35 & 42.13\(\pm\)2.06 & 50.69\(\pm\)1.60 & 41.25\(\pm\)4.44 & 54.11\(\pm\)1.16 & 55.34\(\pm\)2.93 & **56.12\(\pm\)1.13** \\ Cornell & 66.28\(\pm\)5.97 & 54.21\(\pm\)5.90 & 48.83\(\pm\)5.42 & 63.38\(\pm\)5.28 & 63.52\(\pm\)6.38 & 42.83\(\pm\)5.92 & 63.79\(\pm\)5.30 & 58.55\(\pm\)7.44 & **67.03\(\pm\)4.49** \\ Squirrel & 26.58\(\pm\)1.37 & 32.73\(\pm\)0.82 & **36.98\(\pm\)1.03** & 29.70\(\pm\)1.31 & 29.69\(\pm\)0.80 & 28.83\(\pm\)0.50 & 26.75\(\pm\)4.49 & 33.16\(\pm\)2.83 & 34.48\(\pm\)1.29 \\ Texas & 71.62\(\pm\)4.23 & 70.74\(\pm\)5.10 & 58.18\(\pm\)5.11 & 68.45\(\pm\)7.35 & 75.00\(\pm\)3.42 & 41.96\(\pm\)12.59 & 71.62\(\pm\)5.26 & 73.85\(\pm\)2.64 & **75.47\(\pm\)3.18** \\ \hline \hline \end{tabular}
\end{table}
Table 1. Statistics of real-world datasets

\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline  & \multicolumn{3}{c}{Cora} & \multicolumn{3}{c}{Chameleon} \\ \cline{2-9} Method & Test Acc & Running Time (S) & Memory Cost (MB) & Test Acc & Running Time (S) & Memory Cost (MB) \\ \hline GPRGNN & 84.70\(\pm\)0.47 & 1.04 & 49.67 & 40.03\(\pm\)4.31 & 1.13 & 64.43 \\ Auto-GPRGNN (\(freq\)=1) & 84.35\(\pm\)0.47 & 4.18 & 66.94 & 54.96\(\pm\)2.29 & 5.92 & 88.29 \\ Auto-GPRGNN (\(freq\)=2) & 84.51\(\pm\)1.03 & 2.71 & 66.94 & 53.71\(\pm\)1.89 & 3.79 & 88.29 \\ Auto-GPRGNN (\(freq\)=3) & 84.65\(\pm\)0.73 & 2.25 & 66.94 & 52.71\(\pm\)3.46 & 3.38 & 88.29 \\ Auto-GPRGNN (\(freq\)=4) & 84.76\(\pm\)0.96 & 2.00 & 66.94 & 53.23\(\pm\)3.37 & 2.90 & 88.29 \\ Auto-GPRGNN (\(freq\)=5) & 83.94\(\pm\)0.79 & 1.91 & 66.94 & 52.91\(\pm\)2.35 & 2.66 & 88.29 \\ \hline \hline \end{tabular}
\end{table}
Table 4. Efficiency of GPRGNN and Auto-GPRGNN on Cora and Chameleon. \(freq\) denotes the filter update frequency.

\begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline Statistics & Cora & Citeseer & Pubmed & Computers & Chameleon & Cornell & Squirrel & Texas \\ \hline Features & 1433 & 3703 & 500 & 767 & 2325 & 1703 & 2089 & 1703 \\ Nodes & 2708 & 3327 & 19717 & 13752 & 2277 & 183 & 5201 & 183 \\ Edges & 5278 & 4552 & 44324 & 245861 & 31371 & 277 & 198353 & 279 \\ Classes & 7 & 6 & 5 & 10 & 5 & 5 & 5 \\ \(h\) & 0.83 & 0.72 & 0.8 & 0.8 & 0.25 & 0.3 & 0.22 & 0.06 \\ \hline \hline \end{tabular}
\end{table}
Table 1. Statistics of real-world datasets

Figure 3. Results under different ratios on 3 heterophilic datasets and 1 homophilic dataset.

\begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline  & MLP & ChebNet & GCN & APPNP & H2GCN & GPRGNN & BernNet & Auto-GPRGNN & Auto-BernNet \\ \hline Cora & 76.20\(\pm\)1.83 & 86.67\(\pm\)1.99 & 86.59\(\pm\)1.31 & 88.70\(\pm\)0.93 & 87.36\(\pm\)1.11 & 88.79\(\pm\)1.37 & 86.53\(\pm\)1.26 & **89.05\(\pm\)1.09** & 88.70\(\pm\)0.93 \\ Citeseer & 74.76\(\pm\)1.26 & 77.44\(\pm\)1.77 & 77.43\(\pm\)1.42 & 79.43\(\pm\)1.75 & **82.78\(\pm\)1.21** & 78.95\(\pm\)1.93 & 78.58\(\pm\)1.82 & 79.76\(\pm\)0.89 & 79.82\(\pm\)1.55 \\ PubMed & 86.51\(\pm\)0.82 & 88.76\(\pm\)0.58 & 87.04\(\pm\)0.60 & 89.10\(\pm\)0.89 & 87.72\(\pm\)0.46 & 88.09\(\pm\)0.51 & 88.25\(\pm\)0.52 & **89.10\(\pm\)0.54** & 88.38\(\pm\)0.45 \\ Computers & 83.07\(\pm\)0.74 & **89.11\(\pm\)0.61** & 87.71\(\pm\)0.73 & 86.58\(\pm\)0.44 & 89.04\(\pm\)0.61 & 87.04\(\pm\)2.71 & 86.55\(\pm\)0.54 & 88.56\(\pm\)0.54 & 88.71\(\pm\)0.71 \\ Chameleon & 47.62\(\pm\)1.41 & 60.68\(\pm\)2.22 & 61.90\(\pm\)2.19 & 25.65\(\pm\)2.48 & 59.58\(\pm\)2.07 & 62.54\(\pm\)2.77 & 65.71\(\pm\)1.57 & 67.38\(\pm\)1.44 & **68.07\(\pm\)1.48** \\ Cornell & 87.03\(\pm\)3.78 & 77.57\(\pm\)0.65 & 60.27\(\pm\)11.53 & 88.65\(\pm\)5.64 & 87.36\(\pm\)5.82 & 87.03\(\pm\)4.95 & 83.24\(\pm\)4.32 & **91.08\(\pm\)5
ratio over {5%, 10%, 20%, 30%}, and adjust the test set ratio accordingly. We evaluate the performance on three representative heterophilic datasets (Chameleon, Squirrel and Texas), and one homophilic dataset (Cora). We compare the proposed Auto-GPRGNN and Auto-BernNet with the original GPRGNN and BernNet, following the hyperparameter settings in Section 5.1. The results under different ratios on four datasets are shown in Figure 3, and we can have the following observations:

* Auto-GPRGNN and Auto-BernNet can achieve significant improvements in heterophilic graphs compared to the original GPRGNN and BernNet. This suggests that the Auto-Polynomial framework can help the polynomial filters effectively adapt to heterophilic graphs.
* The improvements of Auto-Polynomial over the backbone models are even more obvious under lower labeling ratios. This shows that when there are not enough labeled samples available, the proposed Auto-Polynomial framework can offer greater advantages in addressing the overfitting issues and enhancing the model's generalization ability.

**Update frequency.** In practical implementation, we introduce a hyper-parameter \(freq\) to control the update frequency of polynomial coefficients and thus improve the efficiency of our models. To investigate the influence of update frequency on the efficiency and performance of Auto-Polynomial, we vary the frequency at which Auto-GPRGNN updates \(\Theta\) and examine the the resulting changes in performance, training time and memory cost. We conduct the experiments on both homophilic dataset (Cora) and heterophilic dataset (Chameleon). The results presented in Table 4 provide the following observations:

* On the homophilic dataset (Cora), reducing the update frequency of Auto-GPRGNN almost does not impact the performance, validating the stability of Auto-Polynomial.
* On the heterophilic dataset (Chameleon), Auto-GPRGNN outperforms GPRGNN by significantly and is not very sensitive to the update frequency. This indicates that Auto-Polynomial can greatly enhance the model's efficiency by using an appropriate update frequency, with negligible sacrifice in performance.
* The memory usage of Auto-GPRGNN is approximately 1.3 times that of GPRGNN. However, this increase in memory usage can be deemed acceptable, given the significant improvement achieved by Auto-GPRGNN.

To summarize, Auto-Polynomial provides an effective, stable, and efficient framework to improve the performance and generalization of polynomial filter learning.

## 6. Related Work

**Polynomial Graph Filter.** Polynomial graph filters have been widely used as the guiding principles in the design of spectral-based GNNs starting from the early development of ChebNet (Chen et al., 2020). It has gained increasing attention recently due to its powerful flexibility and expressiveness in modeling graph signals with complex properties. For instance, some representative works including ChebNet (Chen et al., 2020), GPRGNN (Chen et al., 2020) and BernNet (Chen et al., 2020) utilize Chebyshev basis, Monomial basis, and Bernstein basis, respectively, to approximate the polynomial filters whose coefficients can be learned adaptively to model the graph signal. Therefore, these polynomial-based approaches exhibit encouraging results in graph signal modeling on both homophilic and heterophilic graphs. In this work, we design novel experiments to explore the potential and limitations of graph polynomial learning approaches, and we propose Auto-Polynomial, a general automated learning framework to improve the effectiveness of any polynomial-based GNNs, making this work a complementary effort to existing works.

**AutoML on GNNs.** Automated machine learning (AutoML) (Chen et al., 2020) has gained great attention during the past few years due to its great potential in automating various procedures in machine learning, such as data augmentation (Chen et al., 2020; Chen et al., 2020), neural architecture searching (NAS) (Wang et al., 2020; Wang et al., 2020), and hyper-parameter optimization (HPO) (Chen et al., 2020; Chen et al., 2020). Recent works have applied AutoML to GNN architecture search using various search strategies such as random search (Chen et al., 2020; Chen et al., 2020; Chen et al., 2020; Chen et al., 2020), reinforcement learning (Chen et al., 2020; Wang et al., 2020; Wang et al., 2020), evolutionary algorithms (Chen et al., 2020; Chen et al., 2020; Chen et al., 2020), and differentiable search (Wang et al., 2020; Wang et al., 2020; Wang et al., 2020). However, these works mainly focus on the general architecture search and none of them provides an in-depth investigation into the polynomial filter learning. Moreover, these methods require a vast search space and complex learning algorithms, which can be time-consuming and resource-intensive. Different from existing works, this work provides a dedicated investigation into polynomial graph filter learning and proposes the first automated learning strategy to significantly and consistently improve the effectiveness of polynomial filter learning with a highly efficient learning algorithm.

## 7. Conclusion

In this work, we conduct a novel investigation into the potential and limitations of the widely used polynomial graph filter learning approach in graph modeling. Our preliminary study reveals the suboptimality and instability of the existing learning approaches, and we further uncover the severe overfitting issues as a plausible explanation for its failures. To address these limitations, we propose Auto-Polynomial, a novel and general automated polynomial graph filter learning framework to improve the effectiveness and generalization of any polynomial-based GNNs, making this work orthogonal and complementary to existing efforts in this research topic. Comprehensive experiments and ablation studies demonstrate the significant and consistent improvements of Auto-Polynomial in various learning settings. This work further unleashes the potential of polynomial graph filter-based graph modeling.
