Automated Polynomial Filter Learning
for Graph Neural Networks

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

where $\frac{2{\tilde{{\mathbf{L}}}}}{\lambda_{max}}-{\mathbf{I}}$ denotes the rescaled Laplacian matrix, and $\lambda_{max}$ is the largest eigenvalue of ${\tilde{{\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{\tilde{{\mathbf{L}}}}}{\lambda_{max}}-{\mathbf{I}}$.

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

which is equivalent to the general form in Eq. (1) when we set $P_{k}(x)=x^{k}$ and ${\mathbf{M}}={\tilde{{\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:

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

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:

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., $\bigtriangledown_{\Theta}\mathcal{L}_{val}(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 (Liu et al., 2018) to approximate the gradient computation in problem (6):

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.

Case 1: Auto-GPRGNN. In GPRGNN (Chien et al., 2021), 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 (He et al., 2021), 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.

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}_{val}$ 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}_{val}$ 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.

Baselines. We compare the proposed Auto-Polynomial, including use cases Auto-GPRGNN and Auto-BernNet, with 7 baseline models: MLP, GCN (Kipf and Welling, 2016), ChebNet (Defferrard et al., 2016), APPNP (Klicpera et al., 2019), GPRGNN (Chien et al., 2021), BernNet (He et al., 2021) and H2GCN (Zhu et al., 2020a). For GPRGNN¹¹1https://github.com/jianhao2016/GPRGNN and BernNet²²2https://github.com/ivam-he/BernNet, 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 (Fey and Lenssen, 2019).

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 (Sen et al., 2008; Namata et al., 2012), and the Amazon co-purchase graph Computers (McAuley et al., 2015). We also use 4 heterophilic benchmark datasets, including Wikipedia graphs such as Chameleon and Squirrel(Rozemberczki et al., 2021), and webpage graphs such as Texas and Cornell from WebKB³³3http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-11/www/wwkb. We summarize the dataset statistics in Table 1.

Hyperparameter settings. For APPNP, we set its propagation step size $K=10$ and optimize the teleport probability $\alpha$ over $\left\{0.1,0.2,0.5,0.9\right\}.$ 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 $\left\{0.002,0.005,0.01,0.05\right\}.$ For H2GCN, we follow the settings in (Zhu et al., 2020b). We search the embedding round $K$ over $\left\{1,2\right\}.$ 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 $\left\{0.01,0.05\right\}$ and weight decay over $\left\{0,0.0005\right\}$. We search the learning rate $\xi$ over $\left\{0,0.05\right\}$ 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 $\left\{0.002,0.01,0.05\right\}$, and weight decay over $\left\{0,0.0005\right\}$. We select the best performance according to the validation accuracy.

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 (Chien et al., 2020), or a higher fraction on both the homophilic and heterophilic datasets (Pei et al., 2020; Chen et al., 2020; He et al., 2021). 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.

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 (Zhu et al., 2020a). 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.

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 ratio over $\left\{5\%,\ 10\%,\ 20\%,\ 30\%\right\}$, 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-Polymonial 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 heterohpilic 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.