# p-Laplacian Based Graph Neural Networks

arXiv: https://arxiv.org/abs/2111.07337 · HTML: https://mlsanity.com/paper/2111.07337/

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 83 references that are in the map.
- First posted on arXiv 14 Nov 2021.

## Builds on (most cited first, 30 of 46)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [Few-Shot Learning with Graph Neural Networks](https://mlsanity.com/paper/1711.04043/) (2017)
- [Learning Convolutional Neural Networks for Graphs](https://mlsanity.com/paper/1605.05273/) (2016)
- [Diffusion-Convolutional Neural Networks](https://mlsanity.com/paper/1511.02136/) (2015)
- [Revisiting Graph Neural Networks: All We Have is Low-Pass Filters](https://mlsanity.com/paper/1905.09550/) (2019)

## Built on by (most cited first, 30 of 39)

- [SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations](https://mlsanity.com/paper/2306.10759/) (2023)
- [A Comprehensive Survey on Deep Graph Representation Learning](https://mlsanity.com/paper/2304.05055/) (2023)
- [EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networks](https://mlsanity.com/paper/2205.13892/) (2022)
- [From Continuous Dynamics to Graph Neural Networks: Neural Diffusion and Beyond](https://mlsanity.com/paper/2310.10121/) (2023)
- [Generalized Laplacian Positional Encoding for Graph Representation Learning](https://mlsanity.com/paper/2210.15956/) (2022)
- [A Survey of Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protection](https://mlsanity.com/paper/2205.10014/) (2022)
- [SLMRec: Distilling Large Language Models into Small for Sequential Recommendation](https://mlsanity.com/paper/2405.17890/) (2024)
- [Hypergraph Convolutional Networks via Equivalency between Hypergraphs and Undirected Graphs](https://mlsanity.com/paper/2203.16939/) (2022)
- [How Curvature Enhance the Adaptation Power of Framelet GCNs](https://mlsanity.com/paper/2307.09768/) (2023)
- [Unifying over-smoothing and over-squashing in graph neural networks: A physics informed approach and beyond](https://mlsanity.com/paper/2309.02769/) (2023)
- [Optimal Inference in Contextual Stochastic Block Models](https://mlsanity.com/paper/2306.07948/) (2023)
- [Sm: enhanced localization in Multiple Instance Learning for medical imaging classification](https://mlsanity.com/paper/2410.03276/) (2024)
- [MGNN: Graph Neural Networks Inspired by Distance Geometry Problem](https://mlsanity.com/paper/2201.12994/) (2022)
- [Understanding Oversmoothing in Diffusion-Based GNNs From the Perspective of Operator Semigroup Theory](https://mlsanity.com/paper/2402.15326/) (2024)
- [Total Variation Graph Neural Networks](https://mlsanity.com/paper/2211.06218/) (2022)
- [Design Your Own Universe: A Physics-Informed Agnostic Method for Enhancing Graph Neural Networks](https://mlsanity.com/paper/2401.14580/) (2024)
- [Provable Filter for Real-world Graph Clustering](https://mlsanity.com/paper/2403.03666/) (2024)
- [MaxCutPool: differentiable feature-aware Maxcut for pooling in graph neural networks](https://mlsanity.com/paper/2409.05100/) (2024)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Deep representation learning: Fundamentals, Perspectives, Applications, and Open Challenges](https://mlsanity.com/paper/2211.14732/) (2022)
- [Asymptotic generalization error of a single-layer graph convolutional network](https://mlsanity.com/paper/2402.03818/) (2024)
- [Towards Understanding Graph Neural Networks: An Algorithm Unrolling Perspective](https://mlsanity.com/paper/2206.04471/) (2022)
- [ASGNN: Graph Neural Networks with Adaptive Structure](https://mlsanity.com/paper/2210.01002/) (2022)
- [Fast Online Node Labeling for Very Large Graphs](https://mlsanity.com/paper/2305.16257/) (2023)
- [Differentiable Cluster Graph Neural Network](https://mlsanity.com/paper/2405.16185/) (2024)
- [Resolving Oversmoothing with Opinion Dissensus](https://mlsanity.com/paper/2501.19089/) (2025)
- [Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block model](https://mlsanity.com/paper/2503.01361/) (2025)
- [Hypergraphs with Edge-Dependent Vertex Weights: p-Laplacians and Spectral Clustering](https://mlsanity.com/paper/2208.07457/) (2022)
- [Revisiting Generalized p-Laplacian Regularized Framelet GCNs: Convergence, Energy Dynamic and Training with Non-Linear Diffusion](https://mlsanity.com/paper/2305.15639/) (2023)
- [SGFormer: Single-Layer Graph Transformers with Approximation-Free Linear Complexity](https://mlsanity.com/paper/2409.09007/) (2024)

## Abstract (arXiv)

Graph neural networks (GNNs) have demonstrated superior performance for semi-supervised node classification on graphs, as a result of their ability to exploit node features and topological information simultaneously. However, most GNNs implicitly assume that the labels of nodes and their neighbors in a graph are the same or consistent, which does not hold in heterophilic graphs, where the labels of linked nodes are likely to differ. Hence, when the topology is non-informative for label prediction, ordinary GNNs may work significantly worse than simply applying multi-layer perceptrons (MLPs) on each node. To tackle the above problem, we propose a new p-Laplacian based GNN model, termed as pGNN, whose message passing mechanism is derived from a discrete regularization framework and could be theoretically explained as an approximation of a polynomial graph filter defined on the spectral domain of p-Laplacians. The spectral analysis shows that the new message passing mechanism works simultaneously as low-pass and high-pass filters, thus making pGNNs are effective on both homophilic and heterophilic graphs. Empirical studies on real-world and synthetic datasets validate our findings and demonstrate that pGNNs significantly outperform several state-of-the-art GNN architectures on heterophilic benchmarks while achieving competitive performance on homophilic benchmarks. Moreover, pGNNs can adaptively learn aggregation weights and are robust to noisy edges.