Revisiting Graph Neural Networks: All We Have is Low-Pass Filters

By Hoang NT, Takanori Maehara. 2019

526 citations recorded by the source corpus.

Graph neural networks have become one of the most important techniques to solve machine learning problems on graph-structured data. Recent work on vertex classification proposed deep and distributed learning models to achieve high performance and scalability. However, we find that the feature vectors of benchmark datasets are already quite informative for the classification task, and the graph structure only provides a means to denoise the data. In this paper, we develop a theoretical framework based on graph signal processing for analyzing graph neural networks. Our results indicate that graph neural networks only perform low-pass filtering on feature vectors and do not have the non-linear manifold learning property. We further investigate their resilience to feature noise and propose some insights on GCN-based graph neural network design.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

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

In Computer Vision and Pattern Recognition

Citations in the corpus

A Survey on Oversmoothing in Graph Neural Networks (2023, background): “This is related to several issues impairing the performance of deep GNNs in realistic graph-learning settings: graph bottlenecks (Alon & Yahav, 2021), over-squashing (Topping et al., 2021; Deac et al., 2022), and over-smoothing (Li et al., 2018; Nt & Maehara, 2019; Oono & Suzuki, 2020).”
Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods (2021, background): “Indeed, a wide range of GNNs operate as low-pass graph filters [53, 71, 6] that smooth features over the graph topology, which produces similar representations and thus similar predictions for neighboring nodes.”
Deep Learning on Graphs: A Survey (2018, unknown): “Maehara [72] enhanced this result by showing that the low-pass filtering operation did not equip GCNs with a nonlinear manifold learning ability, and further proposed GFNN model to remedy this problem by adding a MLP after the graph convolution layers.”
Beyond Low-frequency Information in Graph Convolutional Networks (2021, background): “Some recent studies (NT and Maehara 2019; Xu et al. 2019a) show that the smoothness of signals, i.e., low-frequency information, are the key to the success of GNNs.”
Amalgamating Knowledge from Heterogeneous Graph Neural Networks (2021, background): “Graph neural networks (GNNs) have achieved unprecedented advances in recent years, showing promising performance in handling graph data lying in the non-Euclidean domain [16, 37, 53, 44, 6, 41, 19, 23, 36, 13, 18, 25, 42].”
SIGN: Scalable Inception Graph Neural Networks (2020, background): “(2019); (ii) GCN aggregation schemes (2) have been essentially shown to learn low-pass filters NT and Maehara (2019) while still performing on par with models with more complex aggregation functions in the task of semi-supervised node classification Shchur et al.”
Revisiting Heterophily For Graph Neural Networks (2022, background): “Generally, the Laplacian matrices (Lsym, Lrw, L̂sym, L̂rw) can be regarded as HP filters [11] and affinity matrices (Asym, Arw, Âsym, Ârw) can be treated as LP filters [34, 14].”
Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning (2021, background): “Some recent works try to improve GNNs in different directions, such as simplifying the computational complexity [37], [38], training with adversarial scheme [39], applying to large-scale graphs [40], [41], [42], and introducing novel operators [8], [43].”
PairNorm: Tackling Oversmoothing in GNNs (2019, methodology): “We start by establishing a connection between graph convolution and an optimization problem, that is graph-regularized least squares (GRLS), as shown by NT & Maehara (2019).”
Benchmarking Graph Neural Networks (2023, methodology): “However, tracking progress is often challenging in the absence of a community-standard benchmark as models that are evaluated on traditionally-used datasets with inconsistent experimental comparisons make it difficult to differentiate complex, simple and graph-agnostic architectures (Hoang and Maeha”
AM-GCN: Adaptive Multi-channel Graph Convolutional Networks (2020, background): “For example, [15] shows that GCNs actually perform the Laplacian smoothing on node features, [20] and [30] prove that topological structures play the role of low-pass filtering on node features.”