p-Laplacian Based Graph Neural Networks

2021/11/14 by Guoji Fu, Fu, Guoji, Peilin Zhao +3 · 2 citations
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Topic Modeling

paper · pdf · doi:10.48550/arxiv.2111.07337

openalex publication_date 2021/11/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Deep Convolutional Networks on Graph-Structured Data
• Towards a theoretical foundation for Laplacian-based manifold methods
• A tutorial on spectral clustering
• Collective Classification in Network Data
• Inductive Representation Learning on Large Graphs
• Contextual Stochastic Block Models
• Pitfalls of Graph Neural Network Evaluation
• LanczosNet: Multi-Scale Deep Graph Convolutional Networks
• Simplifying Graph Convolutional Networks
• Fast Graph Representation Learning with PyTorch Geometric
• Revisiting Graph Neural Networks: All We Have is Low-Pass Filters
• FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling
• Detecting Functionality-Specific Vulnerabilities via Retrieving Individual Functionality-Equivalent APIs in Open-Source Repositories
• Geom-GCN: Geometric Graph Convolutional Networks
• Unifying Graph Convolutional Neural Networks and Label Propagation
• Understanding Graph Neural Networks from Graph Signal Denoising Perspectives
• Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs
• Graph neural networks: A review of methods and applications
• A Comprehensive Survey on Graph Neural Networks

Cited by

• PEANUT: Perturbations by Eigenvector Alignment for Attacking Graph Neural Networks Under Topology-Driven Message Passing
• Enhancing Robustness of Graph Neural Networks through p-Laplacian

Related

• Improving Your Graph Neural Networks: A High-Frequency Booster
• A Piece-wise Polynomial Filtering Approach for Graph Neural Networks
• GPatcher: A Simple and Adaptive MLP Model for Alleviating Graph Heterophily
• Rethinking Graph Regularization for Graph Neural Networks
• From Local to Global: Spectral-Inspired Graph Neural Networks