BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation

By Mingguo He, Zhewei Wei, Zengfeng Huang, Hongteng Xu. Neural Information Processing Systems, 2021

355 citations recorded by the source corpus.

Many representative graph neural networks, e.g., GPR-GNN and ChebNet, approximate graph convolutions with graph spectral filters. However, existing work either applies predefined filter weights or learns them without necessary constraints, which may lead to oversimplified or ill-posed filters. To overcome these issues, we propose BernNet, a novel graph neural network with theoretical support that provides a simple but effective scheme for designing and learning arbitrary graph spectral filters. In particular, for any filter over the normalized Laplacian spectrum of a graph, our BernNet estimates it by an order-$K$ Bernstein polynomial approximation and designs its spectral property by setting the coefficients of the Bernstein basis. Moreover, we can learn the coefficients (and the corresponding filter weights) based on observed graphs and their associated signals and thus achieve the BernNet specialized for the data. Our experiments demonstrate that BernNet can learn arbitrary spectral filters, including complicated band-rejection and comb filters, and it achieves superior performance in real-world graph modeling tasks. Code is available at https://github.com/ivam-he/BernNet.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/bbed89eee0a43baf17dd5eab8354deecadda8acf

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Zi-Chao Gao
2. Sitao Luan
3. Muhan Zhang
4. Doina Precup
5. Mingde Zhao
6. Chenqing Hua
7. Jiajin Li
8. Shuyuan Zhang

Citations in the corpus

• Revisiting Heterophily For Graph Neural Networks (2022, methodology): “We compare these approaches with several baselines and SOTA GNN models: MLP with 2 layers (MLP-2), GAT [40], APPNP [20], GPRGNN [8], H2GCN [45], MixHop [1], GCN+JK [19, 42, 26], GAT+JK [40, 42, 26], FAGCN [4], GraphSAGE [15], Geom-GCN [35] and BernNet [16].”
• How Powerful are Spectral Graph Neural Networks (2022, methodology): “Theoretically, it still has the same time complexity O(Kmd) as APPNP and GPRGNN, where K is the degree of the polynomial, m is the number of edges in the graph, and d is the number of node feature dimensions, while BernNet’s time complexity is O(K2md).”
• Rethinking Graph Neural Networks for Anomaly Detection (2022, background): “Unfortunately, most of the current GNNs are low-pass filters (Nt & Maehara, 2019; Wu et al., 2019) or adaptive filters (Def-ferrard et al., 2016; He et al., 2021; Dong et al., 2021; Levie et al., 2018) that are neither guaranteed to be band-pass nor spectral-localized (Balcilar et al., 2020).”
• Language is All a Graph Needs (2023, methodology): “…(He et al., 2023), we select those top-ranked GNNs from the two corresponding benchmarks with 60%/20%/20% train/val/test splits, including Snowball, RevGAT, etc. (Abu-El-Haija et al., 2019; Pei et al., 2020; Wu et al., 2019; He et al., 2021; Bo et al., 2021; Chen et al., 2020b; Luan et al., 2022).”