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

Abstract

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.

arXiv comment12 pages, 5 figures, 2 tables

References in corpus (7)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Simplifying Graph Convolutional Networks
• Predicting multicellular function through multi-layer tissue networks
• Few-Shot Learning with Graph Neural Networks
• Irregularity-Aware Graph Fourier Transforms

Cited by in corpus (73)

• Graph Neural Networks: A Review of Methods and Applications
• Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning
• Graph Neural Networks with convolutional ARMA filters
• PairNorm: Tackling Oversmoothing in GNNs
• Benchmarking Graph Neural Networks
• SIGN: Scalable Inception Graph Neural Networks
• Graph Neural Networks Exponentially Lose Expressive Power for Node Classification
• Deep Learning on Graphs: A Survey
• EDITS: Modeling and Mitigating Data Bias for Graph Neural Networks
• RA-GCN: Graph Convolutional Network for Disease Prediction Problems with Imbalanced Data
• Towards Deeper Graph Neural Networks with Differentiable Group Normalization
• Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View
• Revisiting Over-smoothing in Deep GCNs
• AdaGNN: Graph Neural Networks with Adaptive Frequency Response Filter
• Rethinking pooling in graph neural networks
• Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification
• Self-supervised Consensus Representation Learning for Attributed Graph
• Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?
• Model Degradation Hinders Deep Graph Neural Networks
• Correlating sparse sensing for large-scale traffic speed estimation: A Laplacian-enhanced low-rank tensor kriging approach
• Continuous Graph Neural Networks
• Dirichlet Energy Constrained Learning for Deep Graph Neural Networks
• Robust Mid-Pass Filtering Graph Convolutional Networks
• Personalized Graph Signal Processing for Collaborative Filtering
• Graph-based Modeling of Online Communities for Fake News Detection
• Understanding over-squashing and bottlenecks on graphs via curvature
• Graph Neural Networks: Methods, Applications, and Opportunities
• Interpreting and Unifying Graph Neural Networks with An Optimization Framework
• Subgroup Generalization and Fairness of Graph Neural Networks
• Scalable Graph Neural Networks for Heterogeneous Graphs
• Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs
• New Benchmarks for Learning on Non-Homophilous Graphs
• Coupled Layer-wise Graph Convolution for Transportation Demand Prediction
• Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks
• Graph Representation Learning Beyond Node and Homophily
• Evaluating Deep Graph Neural Networks
• Beltrami Flow and Neural Diffusion on Graphs
• Geometry-enhanced graph neural network for learning the smoothness of glassy dynamics from static structure
• GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding
• Sampling methods for efficient training of graph convolutional networks: A survey
• Understanding Graph Neural Networks from Graph Signal Denoising Perspectives
• Geometric Scattering Attention Networks
• Dirichlet Graph Variational Autoencoder
• Differentially Private Federated Learning with Laplacian Smoothing
• Cold Brew: Distilling Graph Node Representations with Incomplete or Missing Neighborhoods
• SCE: Scalable Network Embedding from Sparsest Cut
• On Graph Neural Networks versus Graph-Augmented MLPs
• Self-Enhanced GNN: Improving Graph Neural Networks Using Model Outputs
• Network In Graph Neural Network
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks
• CorDEL: A Contrastive Deep Learning Approach for Entity Linkage
• DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting
• Spectral Graph Attention Network with Fast Eigen-approximation
• Maximum Entropy Weighted Independent Set Pooling for Graph Neural Networks
• $p$-Laplacian Based Graph Neural Networks
• Graph-based State Representation for Deep Reinforcement Learning
• Isometric Transformation Invariant and Equivariant Graph Convolutional Networks
• HighwayGraph: Modelling Long-distance Node Relations for Improving General Graph Neural Network
• BiGCN: A Bi-directional Low-Pass Filtering Graph Neural Network
• Message Passing in Graph Convolution Networks via Adaptive Filter Banks
• Stacked Graph Filter
• AViTMP: A Tracking-Specific Transformer for Single-Branch Visual Tracking
• SoGCN: Second-Order Graph Convolutional Networks
• Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs
• Graph Denoising with Framelet Regularizer
• Connecting Graph Convolutional Networks and Graph-Regularized PCA
• Meta-Aggregator: Learning to Aggregate for 1-bit Graph Neural Networks
• Hypergraph Neural Sheaf Diffusion: A Symmetric Simplicial Set Framework for Higher-Order Learning
• Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters
• Network representation learning: A macro and micro view
• Efficient Graph based Recommender System with Weighted Averaging of Messages
• SAS: A Simple, Accurate and Scalable Node Classification Algorithm
• Multi-hop Graph Convolutional Network with High-order Chebyshev Approximation for Text Reasoning