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

Hoang NT; Takanori Maehara

Source-linked AI summary

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

Hoang NT, Takanori Maehara

arXiv:1905.09550v2May 23, 2019stat.MLcs.ITcs.LGmath.SP

TL;DR

The paper asks why graph neural networks work well for vertex classification when benchmark features may already contain sufficient task information. It develops a graph-signal-processing framework and concludes that GCN-based models primarily perform low-pass filtering and denoising, without nonlinear manifold learning. The analysis motivates simpler filtering-based designs and identifies noisy features and nonlinear feature spaces as important scope boundaries.

Problem
The paper investigates why graph neural networks work well for vertex classification and whether graph structure contributes beyond processing already informative features.
Method
The paper analyzes GCN, SGC, and a filtering baseline called gfNN using graph signal processing, graph Fourier analysis, and theoretical results on propagation matrices.
Results
The analysis indicates that graph convolution corresponds to low-pass filtering and denoising, while under Assumption 1 GCN, SGC, and gfNN have outcomes similar to models using true features.
Takeaways & Limitations
GCN-derived GNNs should be viewed primarily as denoising mechanisms, and simpler filtering-based approaches can provide similar performance while avoiding learning-phase adjacency multiplications.
Takeaways & Limitations
The conclusions depend on Assumption 1, and the analysis identifies noisy features and nonlinear feature spaces as settings where GCN and SGC might fail.

Abstract

from arXiv · show

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.

1 Introduction

The paper asks why graph neural networks work for vertex classification and analyzes them through graph signal processing. It argues that graph convolution primarily filters noisy features rather than performing nonlinear manifold learning.

Motivation: The study frames vertex classification around whether graph neural networks exploit graph structure beyond denoising informative feature vectors.This question follows observations that graph-convolution parameters may mainly contribute to overfitting and that simplified propagation models perform strongly.
Main theoretical result: Graph propagation matrices correspond to low-pass filtering, and their product with observed signals solves the true-signal denoising optimization problem.This analysis suggests that learning graph-convolution parameters is unnecessary.
Proposed framework: gfNN filters features with graph-filter matrices and then learns vertex labels using a machine-learning model.The framework separates graph-based filtering from label prediction and provides a simple realization in Figure 2.
Main theoretical result: Under Assumption 1, SGC, GCN, and gfNN achieve outcomes similar to corresponding neural networks using true features.Assumption 1 states that observed features contain low-frequency true features with task-sufficient information plus noise.
Implications: Under the stated assumptions, gfNN has similar high performance to GCN, while avoiding adjacency multiplications during learning and providing greater noise tolerance.The claimed speed advantage comes from excluding adjacency-matrix multiplications from the learning phase.
Limitations and scope: The analysis identifies noisy features and nonlinearly separable feature spaces as settings where GCN and SGC might fail.An artificial two-circles experiment is used to demonstrate the nonlinear-separability case.

2 Graph Signal Processing

The paper formulates graph data as signals on vertices and uses generalized graph Fourier analysis to characterize smoothness, frequency, and graph filtering. Graph filters operate by modifying signal components in the graph-frequency domain.

Graph signals: A graph signal is a vector defined on graph vertices, with variation and a ˜D-inner product measuring smoothness and importance.The inner product gives more importance to high-degree vertices, while larger γ makes that importance more uniform.
Graph Fourier analysis: Generalized eigenvectors are obtained by minimizing graph-signal variation subject to unit ˜D-norm and orthogonality constraints.The corresponding minimized variation defines each generalized eigenvalue.
Graph Fourier analysis: Generalized eigenvectors provide the graph Fourier basis, and generalized eigenvalues represent graph frequencies ordered by signal smoothness.Smaller generalized eigenvalues correspond to smoother generalized eigenvectors.
Graph Fourier analysis: The graph Fourier transform expands feature signals in the generalized eigenvector basis, and the inverse transform reconstructs the feature matrix.Each feature dimension is treated as a graph signal, with rows of the transformed matrix representing frequency components.
Graph filters: A graph filter maps each frequency component by multiplying it with h(λ), equivalently applying h(˜Lrw) in the spatial domain.The spatial-domain operator is defined through the Taylor expansion of the analytic filter function.

3 Empirical Evidence of Assumption 1

Experiments on citation-network datasets test whether features are low-frequency and task-informative. Performance generally peaks using a small low-frequency portion of the spectrum and remains relatively robust to added Gaussian noise.

Dataset evidence: On Cora, Citeseer, and Pubmed, 2-layer MLP accuracy tends to peak within the top 20% of normalized-Laplacian frequency components.The experiment incrementally reconstructs features with additional frequency components before training the MLP.
Noise robustness: Low-frequency regions remain relatively robust after adding Gaussian noise, indicating a strong denoising effect.The tested noise levels were σ = 0, 0.01, and 0.05.
Dataset evidence: Adding more frequency components decreases performance after the informative low-frequency components, while Gaussian noise further worsens classification accuracy.This pattern supports the assumption that task-relevant true features are concentrated at low frequencies.
Model comparison: The performance gap between graph neural networks and a simple MLP is larger when high-frequency components provide no useful classification information.In Cora, high-frequency components only decrease classification accuracy, so gfNN outperforms the simple MLP.

4 Multiplying Adjacency Matrix is Low Pass Filtering

The paper shows that multiplying adjacency-derived propagation matrices performs low-pass filtering, while self-loops strengthen this effect. This filtering also approximates an optimization-based estimate of low-frequency true features.

4 Multiplying Adjacency Matrix is Low Pass Filtering: Multiplying propagation matrices corresponds to applying a low-pass filter to graph signals.The paper identifies adjacency propagation as low-pass filtering rather than a learned graph-convolution operation.
4 Multiplying Adjacency Matrix is Low Pass Filtering: Adding self-loops strengthens low-pass filtering by shrinking graph Laplacian eigenvalues toward zero.Theorem 3 states that all generalized eigenvalues decrease monotonically as the self-loop parameter γ increases.
4 Multiplying Adjacency Matrix is Low Pass Filtering: The self-loop parameter γ cannot be too large because concentrating all eigenvalues near zero makes low-frequency components uninformative.
4 Multiplying Adjacency Matrix is Low Pass Filtering: The optimal low-frequency feature estimate is ¯X = (I + ˜Lrw)^−1X, whose filter h′(λ) = (1 + λ)^−1 is approximated by h(λ) = 1 −λ.The paper derives h(λ) = 1 −λ as the first-order Taylor approximation of the optimization-based filter.

5 Bias-Variance Trade-off for Low Pass Filters

Under the paper’s low-frequency signal and white-noise assumptions, repeated adjacency multiplication trades increasing bias for decreasing variance. With suitable conditions and a selected number of multiplications, the resulting estimation achieves ˜O(√ϵ) accuracy.

5 Bias-Variance Trade-off for Low Pass Filters: The observed features are modeled as low-frequency true features plus white Gaussian noise.The true features have frequency at most 0 ≤ϵ ≪1, while graph-Fourier coefficients of the noise are independent identically distributed normal variables.
5 Bias-Variance Trade-off for Low Pass Filters: Filtering introduces a bias term and a variance term from the filtered noise.
5 Bias-Variance Trade-off for Low Pass Filters: The bias increases by O(√ϵ), while the variance decreases as O(1/deg^k/2) when random-walk returns typically scale as O(1/deg^k).Filtering improves estimation when the true-feature maximum frequency is much smaller than the noise-to-signal ratio.
5 Bias-Variance Trade-off for Low Pass Filters: The monotone shrinking result strengthens prior work by covering all eigenvalues rather than only the maximum eigenvalue.
5 Bias-Variance Trade-off for Low Pass Filters: Under Corollary 6 conditions, choosing k = k∗ yields an estimation error of ˜O(√ϵ).The stated choice is k∗ = O(log(log(1/δ)ρ/ϵ)) when the return-probability bound holds through k∗.

6 Graph Filter Neural Network

The section analyzes graph-filtered features followed by perceptron learning, then compares this framework theoretically with GCN and SGC. It concludes that low-frequency true features yield solutions close to optimal, while GCN can overfit noise and SGC inherits one-layer perceptron limitations.

Graph Filter Neural Network: The graph-filter neural network applies a graph filter to features before training a multilayer perceptron on the filtered representation.The section describes this as applying a filter ˜A^k_rw and then learning with h_MLP.
Graph Filter Neural Network: Graph filtering followed by a multilayer perceptron obtains a solution similar to the optimal one when true data has low maximum frequency.The result holds under the stated assumptions and a choice of filter order k from Corollary 6.
Comparison with GCN: A two-layer GCN has performance similar to an MLP on true features, and MLP, GCN, and gfNN converge to the same performance as ϵ and Z approach zero.The equality is stated specifically in the limit ϵ → 0 and Z → 0.
Comparison with GCN: gfNN is faster than GCN because it excludes graph use during training, while GCN can overfit noise that first-order low-pass filtering cannot remove.The paper states that the inner weight W1 may then be trained using noisy features.
Comparison with SGC: Degree-2 SGC is a gfNN with a one-layer perceptron, so its performance resembles that perceptron applied to true features.Consequently, SGC cannot solve problems when the true features are non-separable.

7 Experiments

The experiments test noise tolerance and expressive power across real-world benchmarks and a synthetic two-circles dataset. GCN, SGC, and gfNN are comparable on most benchmarks, while SGC fails on the nonlinear two-circles task and is more noise tolerant than GCN.

Experimental setup: The experiments include white-noise tests on real-world datasets and an artificial two-circles dataset with a 5-nearest-neighbor graph.The two experiments respectively examine feature-noise robustness and failure on complex feature spaces.
Implementation: The reported model settings use Adam with learning rate 0.2, 50 epochs, and 32 hidden units for GCN, MLP, and gfNN.Other hyperparameters are set similarly to SGC.
Noise robustness: As noise increases, GCN, logistic regression, and MLP increasingly overfit, whereas gfNN and SGC remain comparably noise tolerant.The features receive white noise N(0, δ2) with δ in the range (0.01, 0.05).
Expressiveness: SGC is unable to classify the 500-sample two-circles dataset from graph-filtered features.The experiment evaluates whether graph filtering provides nonlinear manifold learning.
Benchmark performance: GCN, SGC, and gfNN achieve similar performance on most benchmark graph datasets.Table 2 reports average test accuracy on randomized train/validation/test splits, with f1-micro used for Reddit.
Interpretation: The authors interpret the comparable benchmark results as evidence that current benchmark datasets have relatively simple feature spaces.This interpretation accompanies the comparison among SGC, GCN, and gfNN.

8 Discussion

The discussion identifies limits of GCN-based architectures and argues that their graph-convolution layers should be viewed as denoising mechanisms. It recommends reconsidering stacked GCN designs when feature spaces are complex.

Related limitations: Prior analyses reported that backpropagation did not improve accuracy or detectability in a simple GCN, while many layers can hurt performance with little labeled data.These findings are presented as related work on GCN limitations.
Supported scope: The paper identifies noisy features and nonlinear feature spaces as two cases where GCN and SGC might fail.The authors state that GNN use is supported when low-frequency true features contain sufficient task information.
Interpretation: GCN-based GNNs are interpreted as performing noise filtering and learning from denoised data.This discussion frames the graph-convolution operation through the paper’s graph-signal-processing analysis.
Design implication: Simply stacking GCN layers may increase overfitting and design complexity without increasing expressiveness beyond a simple MLP.The paper contrasts this design trend with treating GCN layers as denoising mechanisms.

A Proofs

The appendix supplies proofs for spectral properties, denoising bounds, and nonlinear activation behavior used in the paper’s theoretical analysis. The excerpts mainly document proof steps rather than state complete theorem conclusions.

Spectral proofs: Theorem 3 uses positive-semidefinite generalized eigenvalues and the Courant–Fisher–Weyl min-max principle to establish a shrinking result.The proof compares generalized eigenvalues for γ1 and γ2.
Denoising bounds: The proof of Lemma 5 substitutes X = X̄ + Z and bounds the resulting terms using earlier lemmas.The cited excerpts include a Parseval-identity step and a bound from Lemma 9.
Graph-walk interpretation: One proof invokes the interpretation of an entry of Ã2k as the probability that a random walk moves from i to j in 2k steps.This connects the matrix expression to graph-walk behavior.
Proof dependencies: Additional proof excerpts invoke Lipschitz continuity, Lemma 5, and results from prior work as intermediate steps.These excerpts do not provide complete standalone theorem statements.
Activation analysis: Lemma 10 states that sufficiently low-frequency X admits a Y with frequency at most √ϵ while controlling the distance between σ(X) and Y.Its proof constructs Y by truncating frequency components greater than √ϵ.