p-Laplacian Based Graph Neural Networks

Guoji FuPeilin ZhaoYatao Bian

article2022ICML53 citations

Develops a discrete regularization framework based on the $p$ -Laplacian to create graph neural networks that act as adaptive low-high-pass spectral filters, effectively handling heterophilic graphs and noisy topology where standard architectures fail.

Listen

Graph neural networks have become a leading approach for semi-supervised classification across complex systems, including social networks, biological interactomes, and molecular graphs. However, standard architectures rely heavily on the assumption of homophily—that connected nodes share identical or similar attributes and labels. In real-world environments with heterophily (where linked nodes possess different labels) or where graph structures contain noisy, misleading connections, traditional graph neural networks often experience severe performance degradation. In some instances, standard architectures perform substantially worse than simple multilayer perceptrons that ignore graph connectivity entirely.

The article develops and validates a generalized graph neural network framework, termed pGNN, based on discrete p-Laplacian regularization. The core objective is to formulate an adaptive message-passing mechanism capable of filtering information effectively across homophilic graphs, heterophilic networks, and topologies corrupted by noise.

To evaluate this framework, the authors conducted extensive transductive and inductive node classification experiments across 13 benchmark datasets (seven homophilic and six heterophilic networks), synthetic contextual stochastic block models with varying levels of homophily, and graphs with controlled rates of randomly injected edges (up to 100% random edges). The pGNN framework was systematically benchmarked against standard models, including multi-layer perceptrons, Graph Convolutional Networks, Graph Attention Networks, and generalized PageRank baselines.

The findings demonstrate substantial performance gains under challenging network conditions. First, on real-world heterophilic benchmarks, pGNN configurations significantly outperform conventional models; for example, on the Wisconsin dataset, pGNN achieves over 95% accuracy compared to approximately 62% for standard graph convolutional networks and 66% for graph attention networks. Second, on homophilic benchmarks, pGNN remains fully competitive with state-of-the-art architectures while outperforming baselines under limited supervision (e.g., 2.5% training splits). Third, in noise-stress evaluations with high edge-corruption rates, pGNN exhibits strong robustness, avoiding performance collapse and matching or exceeding independent node classification. Finally, theoretical and spectral analyses confirm that pGNN functions as an adaptive filter that dynamically concentrates aggregation weights to ignore non-informative edges.

These results demonstrate that organizations deploying machine learning on interconnected data do not need separate, specialized pipelines for homophilic and heterophilic topologies. The ability of pGNN to automatically prune misleading relationships reduces operational risks associated with noisy data and improves reliability in sparse-label environments.

Decision-makers should consider pGNN as a drop-in architectural replacement or plug-and-play enhancement for existing graph learning pipelines, particularly when graph quality is uncertain. When deploying the model, tuning the regularization parameter allows teams to balance reliance on graph structure versus raw node features. Before enterprise-scale implementation on massive networks, engineering teams should conduct pilot deployments and explore subgraph sampling methods to address the higher memory requirements typical of full-graph spectral methods.

Tencent bipartite graphs classification graph neural networks graph neural networks p-Laplacian graph convolutions

arXiv: 2111.07337 guoji-fu/pGNNs

Paper: Semi-Supervised Classification with Graph Convolutional Networks, Thomas N. Kipf et al. (2017). Its foundational GCN formulation makes the neighbor-aggregation mechanism clear before pGNN replaces fixed propagation with a p-Laplacian-based adaptive rule.
Paper: Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering, Michaël Defferrard et al. (2016). Its Laplacian-based spectral filtering provides the mathematical groundwork for understanding pGNN’s use of graph operators and frequency filtering.
Paper: Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs, Jiong Zhu et al. (2020). Its analysis of why conventional GNN designs fail under heterophily motivates the problem that pGNN’s adaptive aggregation addresses.
Paper: Geom-GCN: Geometric Graph Convolutional Networks, Hongbin Pei et al. (2020). Its geometric aggregation approach shows how earlier GNNs addressed heterophily, giving context for pGNN’s distinct operator-based solution.

No sufficiently relevant recommendations were found.

Cover for p-Laplacian Based Graph Neural Networks

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. 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. Moreover, 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 can 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 as low-high-pass filters, thus rendering pGNNs 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.

1. Introduction
2. Preliminaries and Background
3. p-Laplacian based Graph Neural Networks
3.1. p-Laplacian Regularization Framework
3.2. p-Laplacian Message Passing and p GNN Architecture
4. Spectral Views of p-Laplacian Message Passing
5. Empirical Studies
6. Conclusion
Acknowledgements
Reproducibility Statement
References
Appendix
A. Related Work
B. Discussions and Future Work
C. Additional Theorems
C.1. Theorem 4 (Upper-Bounding Risk of p GNN)
C.2. Theorem 5 (p-Orthogonal Theorem (Luo et al., 2010))
C.3. Theorem 6 (p-Eigen-Decomposition of ∆p)
C.4. Theorem 7 (Bounds of p-Eigenvalues)
D. Proof of Theorems
D.1. Proof of Theorem 1
D.2. Proof of Theorem 2
D.3. Proof of Theorem 3
D.4. Proof of Theorem 4
D.5. Proof of Theorem 6
D.6. Proof of Theorem 7
D.7. Proof of Proposition 1
E.2. Dataset Statistics
E.3. Hyperparameter Settings
F. Additional Experiments
F.1. Experimental Results on Homophilic Benchmark Datasets
F.2. Experimental Results of Aggregation Weight Entropy Distribution
F.3. Experimental Results on cSBM
F.4. Experimental Results on Graphs with Noisy Edges
F.5. Experimental Results of Integrating p GNNs with GCN and JKNet
F.6. Experimental Results of p GNNs on PPI Dataset for Inductive Learning
F.7. Experimental Results on OGBN arXiv Dataset
F.8. Running Time of p GNNs
F.9. Experimental Results on Benchmark Datasets for 64 Hidden Units
F.10. Training Curves for p = 1
F.11. Visualization Results of Node Embeddings

Knowls

Knowl 1 — p-Laplacian regularization yields adaptive graph message passing
model/method
For an undirected weighted graph with adjacency weights $W_{ij}=W_{ji}\ge 0$ , degree matrix $D$ with $D_{ii}=\sum_j W_{ij}$ , and node signals $F_i\in\mathbb{R}^c$ , define the edge gradient by $(\nabla F)([i,j])=\sqrt{W_{ij}/D_{jj}}F_j-\sqrt{W_{ij}/D_{ii}}F_i$ . Its $p$ -variation is $S_p(F)=\frac12\sum_{i,j=1}^N\|(\nabla F)([i,j])\|_2^p$ , and the graph $p$ -Laplacian is $\Delta_pF=-\frac12\operatorname{div}(\|\nabla F\|_2^{p-2}\nabla F)$ , where divergence is the negative adjoint of the gradient. This operator satisfies $\langle F,\Delta_pF\rangle=S_p(F)$ ; at $p=2$ it is the normalized Laplacian $I-D^{-1/2}WD^{-1/2}$ , while it is generally nonlinear for $p\ne2$ . The paper minimizes the regularized objective $\mathcal{J}_p(F)=S_p(F)+\mu\sum_i\|F_i-X_i\|_2^2$ , where $X_i$ are input features and $\mu>0$ trades graph variation against fidelity to those features. For $p>1$ , it constructs an iterative update from this objective: at iteration $k$ , set $M_{ij}^{(k)}=W_{ij}\|\sqrt{W_{ij}/D_{ii}}F_i^{(k)}-\sqrt{W_{ij}/D_{jj}}F_j^{(k)}\|_2^{p-2}$ , $\alpha_{ii}^{(k)}=(\sum_j M_{ij}^{(k)}/D_{ii}+2\mu/p)^{-1}$ , and $\beta_{ii}^{(k)}=(2\mu/p)\alpha_{ii}^{(k)}$ ; set $M_{ij}^{(k)}=0$ when the edge-gradient norm is zero. Starting from $F^{(0)}=X$ , update $F_i^{(k+1)}=\alpha_{ii}^{(k)}\sum_j\frac{M_{ij}^{(k)}}{\sqrt{D_{ii}D_{jj}}}F_j^{(k)}+\beta_{ii}^{(k)}X_i$ . Thus the edge-dependent aggregation weights change with the current signal rather than being fixed by the graph alone.
Knowl 2 — pGNN uses a learned feature map followed by p-Laplacian propagation
model/method
For node features $X\in\mathbb{R}^{N\times c}$ and $L$ classes, pGNN first forms hidden representations $F^{(0)}=\operatorname{ReLU}(X\Theta^{(1)})$ , with $h$ hidden units and $\Theta^{(1)}\in\mathbb{R}^{c\times h}$ . It then performs $K$ p-Laplacian propagation steps, $F^{(k+1)}=\alpha^{(k)}D^{-1/2}M^{(k)}D^{-1/2}F^{(k)}+\beta^{(k)}F^{(0)}$ , for $k=0,\ldots,K-1$ . Here $D$ is the graph degree matrix; $M_{ij}^{(k)}=W_{ij}\|\sqrt{W_{ij}/D_{ii}}F_i^{(k)}-\sqrt{W_{ij}/D_{jj}}F_j^{(k)}\|_2^{p-2}$ ; and the diagonal entries of $\alpha^{(k)}$ and $\beta^{(k)}$ are $(\sum_j M_{ij}^{(k)}/D_{ii}+2\mu/p)^{-1}$ and $(2\mu/p)\alpha_{ii}^{(k)}$ , respectively. The final class-probability matrix is $Z=\operatorname{softmax}(F^{(K)}\Theta^{(2)})$ , where $\Theta^{(2)}\in\mathbb{R}^{h\times L}$ and softmax is applied row-wise. The input-derived residual $\beta^{(k)}F^{(0)}$ retains the learned node features while the adaptive graph weights determine how much neighbor information each node uses.
Knowl 3 — p-Laplacian message passing approximates a polynomial spectral filter
theoretical result
In the paper's p-spectral construction, a p-eigenvector $u\in\mathbb{R}^N$ with eigenvalue $\lambda$ satisfies $(\Delta_pu)_i=\lambda\varphi_p(u_i)$ , where $\varphi_p(t)=|t|^{p-2}t$ . A $K$ -step p-Laplacian message-passing process is shown to approximate a polynomial graph filter on this spectral domain: $g_\theta\star X\approx\sum_{k=0}^{K-1}\theta_k\Delta_p^{\,k}X$ , with coefficients $\theta_k$ defining the polynomial and $X$ the node-signal matrix. This interpretation explains propagation as spectral filtering rather than merely repeated neighbor aggregation; for $p=2$ , the construction reduces to filtering based on the ordinary graph Laplacian.
Knowl 4 — Local signal variation determines whether propagation is low-pass or low-high-pass
theoretical result
For a connected graph, the spectral analysis characterizes the p-Laplacian propagation filter at node $i$ according to the local embedding variation $v_i=\|\nabla F(i)\|_2$ . A low-high-pass filter gives greater weight to low and high frequencies than to frequencies near the cutoff; a low-pass filter emphasizes low frequencies. At $p=2$ , propagation is low-high-pass regardless of $v_i$ . For $p>2$ , the stated threshold is $2^{(p-1)/(p-2)}$ : variation at or below this threshold yields low-high-pass behavior, while larger variation yields low-pass behavior. For $1\le p<2$ , the threshold is $2(2\sqrt{N_{q}})^{1/(p-2)}$ , where $q$ is the node attaining $\max_{j,l}|u_j^{(l)}|/\sqrt{D_{jj}}$ over nodes $j$ and p-eigenvectors $u^{(l)}$ , and $N_q$ is its degree; at $p=1$ , the paper substitutes the minimum node degree $N_{\min}$ for $N_q$ . Below this degree-dependent threshold the filter is low-pass, and above it the filter is low-high-pass. This gives pGNN a local, signal-dependent way to use low-high-pass behavior for heterophilic structure and low-pass behavior for smoother structure.
Knowl 5 — The regularization-derived iteration decreases its objective under suitable settings
theoretical result
Let $\mathcal{J}_p(F)=S_p(F)+\mu\sum_i\|F_i-X_i\|_2^2$ be the p-Laplacian regularization objective, and initialize the iterative update at $F^{(0)}=X$ . For any $p>1$ , the paper establishes that there exists a positive choice of $\mu$ , depending on the input features $X$ , graph $G$ , and $p$ , for which each p-Laplacian message-passing step satisfies $\mathcal{J}_p(F^{(k+1)})\leq\mathcal{J}_p(F^{(k)})$ . The authors consequently state convergence of the iteration for suitable settings; the guarantee is conditional on choosing an appropriate $\mu$ , not a claim that every value works.
Knowl 6 — pGNN outperforms graph baselines on the evaluated heterophilic benchmarks
empirical result
The transductive node-classification experiments used 60%/20%/20% train/validation/test splits on six heterophilic datasets and averaged accuracy over 100 runs. The best reported pGNN variants achieved 48.86% on Chameleon ( $p=1$ ), 33.75% on Squirrel ( $p=1$ ; the $p=2.5$ variant scored 33.79%), 40.62% on Actor ( $p=1$ ), 95.37% on Wisconsin ( $p=1$ ), 87.96% on Texas ( $p=2$ ), and 82.16% on Cornell ( $p=1$ ). For comparison, an MLP using features alone scored 48.02%, 33.80%, 39.68%, 93.56%, 79.50%, and 80.30% on those datasets, respectively. The pGNN results substantially exceed most graph-based baselines on these benchmarks and are close to the MLP on Squirrel, where graph topology provides little useful signal.
Knowl 7 — pGNN remains competitive with established GNNs on homophilic benchmarks
empirical result
On seven homophilic transductive node-classification benchmarks, evaluated with 2.5% training, 2.5% validation, and 95% testing data over 100 runs, the best pGNN result for each dataset was 78.93% on Cora ( $p=2$ ), 63.80% on CiteSeer ( $p=1.5$ ), 84.45% on PubMed ( $p=2.5$ ), 85.03% on Computers ( $p=1.5$ ), 90.91% on Photo ( $p=1.5$ ), 92.28% on CS ( $p=2$ ), and 94.93% on Physics ( $p=2$ ). The corresponding strongest non-pGNN comparison scores were 79.58%, 64.10%, 84.80%, 84.32%, 90.48%, 91.54%, and 94.93%, respectively. Thus pGNN is not uniformly best on these homophilic datasets, but matches or exceeds the strongest comparison on several of them and remains close on the rest; the much lower MLP scores on these benchmarks indicate that graph information is useful in this setting.
Knowl 8 — Synthetic and edge-corruption experiments support adaptation to unreliable topology
empirical result
On sparse-split contextual stochastic block model (cSBM) graphs with 5,000 nodes, 2,000 features, and heterophily parameter $\phi$ ranging from $-1$ to $1$ , pGNN performed strongly when topology was informative even under heterophily: at $\phi=-1$ , the $p=2$ model scored 98.37% accuracy versus 97.26% for GPRGNN; at $\phi=-0.75$ , it scored 96.32%. When topology was nearly uninformative, performance stayed near feature-only prediction: at $\phi=0$ , the $p=1$ model scored 61.80% and the MLP scored 61.70%. Separately, the authors corrupted real graphs by adding random edges and removing the same number of original edges, with random-edge rate $r=\#\text{random edges}/\#\text{all edges}$ . At $r=1$ on Computers, pGNN with $p=2$ scored 67.17% (standard deviation 1.63), compared with 66.11% (2.70) for the MLP and 8.95% (6.90) for GCN. At $r=1$ on Wisconsin, pGNN with $p=1$ scored 95.97% (2.27), compared with 93.56% (3.14) for the MLP and 64.21% (4.49) for GCN. These experiments indicate that pGNN can retain useful feature-based performance when edges are uninformative or heavily corrupted.
Knowl 9 — The pGNN prediction risk is bounded by feature error, graph diffusion, and feature noise
theoretical result
For a $d$ -regular graph, suppose observed features satisfy $X^*=X+\epsilon$ , where $\epsilon$ is feature noise, and the ground-truth labels obey $y=\sigma(X^*)$ for an $L$ -Lipschitz prediction function $\sigma$ . The paper's risk theorem bounds the pGNN's average absolute prediction error by three contributions: the feature-only prediction error from applying $\sigma$ to the observed features $X$ ; an $L$ -scaled term measuring the cumulative p-Laplacian diffusion of node features through the propagation iterations; and an $L$ -scaled term measuring the magnitude of $\epsilon$ . The per-node propagation and residual weights control these contributions through $\mu$ : smaller $\mu$ gives more weight to graph diffusion but also more exposure to feature noise, while larger $\mu$ makes predictions rely more on the original features. The theorem therefore formalizes why a larger $\mu$ is appropriate when graph topology is not helpful, and a smaller $\mu$ may help when graph diffusion is informative.
Knowl 10 — Known limitations include large-graph memory cost and caveats at p=1
limitation
The authors identify relatively high space cost compared with GraphSAGE as a restriction of pGNN, especially on extremely large graphs, and leave integration with subgraph-sampling methods as future work. They also recommend $p>1$ in practice: for scalar-valued signals, the $p=1$ operator can be discontinuous at zero edge variation and can make the stationary condition problematic. They note that $p=1$ may still work for multi-channel signals under the stated condition that the node embeddings are not vectors with only one nonzero coordinate.

Coverage note — Omitted supplementary plug-in experiments combining pGNN with GCN or JKNet, PPI and OGBN-Arxiv evaluations, and runtime and embedding visualizations; these are secondary extensions or diagnostics rather than the core regularization, spectral, and heterophily/noisy-topology findings captured here.

References

1.Abu-El-Haija, S., Perozzi, B., Al-Rfou, R., and Alemi, A. A. Watch your step: Learning node embeddings via graph attention. In Bengio, S., Wallach, H. M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 31, NeurIPS 2018, December 3-8, 2018, Montreal, Canada, pp. 9198–9208, 2018.
2.Abu-El-Haija, S., Kapoor, A., Perozzi, B., and Lee, J. N-GCN: multi-scale graph convolution for semi-supervised node classification. In Globerson, A. and Silva, R. (eds.), Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI 2019, Tel Aviv, Israel, July 22-25, 2019, volume 115 of Proceedings of Machine Learning Research, pp. 841–851. AUAI Press, 2019.
3.Amghibech, S. Eigenvalues of the discrete p-laplacian for graphs. Ars Combinatoria, 67:283–302, 2003.
4.Atwood, J. and Towsley, D. Diffusion-convolutional neural networks. In Lee, D. D., Sugiyama, M., von Luxburg, U., Guyon, I., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 29, NeurIPS 2016, December 5-10, 2016, Barcelona, Spain, pp. 1993–2001, 2016.
5.Bach, F. and Jordan, M. Learning spectral clustering. Advances in Neural Information Processing Systems, NIPS 2004, 16(2):305–312, 2004.
6.Battaglia, P. W., Hamrick, J. B., Bapst, V., Sanchez-Gonzalez, A., Zambaldi, V. F., Malinowski, M., Tacchetti, A., Raposo, D., Santoro, A., Faulkner, R., Gulc¸ehre, C¸ ., Song, H. F., Ballard, A. J., Gilmer, J., Dahl, G. E., Vaswani, A., Allen, K. R., Nash, C., Langston, V., Dyer, C., Heess, N., Wierstra, D., Kohli, P., Botvinick, M., Vinyals, O., Li, Y., and Pascanu, R. Relational inductive biases, deep learning, and graph networks. CoRR, abs/1806.01261, 2018.
7.Belkin, M. and Niyogi, P. Towards a theoretical foundation for laplacian-based manifold methods. Journal of Computer and System Sciences, 74(8):1289–1308, 2008.
8.Belkin, M., Matveeva, I., and Niyogi, P. Regularization and semi-supervised learning on large graphs. In The 17th Annual Conference on Learning Theory, COLT 2004, Banff, Canada, July 1-4, 2004, volume 3120, pp. 624–638, 2004.
9.Belkin, M., Niyogi, P., and Sindhwani, V. On manifold regularization. In Cowell, R. G. and Ghahramani, Z. (eds.), Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, AISTATS 2005, Bridgetown, Barbados, January 6-8, 2005. Society for Artificial Intelligence and Statistics, 2005.
10.Bruna, J., Zaremba, W., Szlam, A., and LeCun, Y. Spectral networks and locally connected networks on graphs. In The 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, 2014.
11.Buhler, T. and Hein, M. Spectral clustering based on the graph p-laplacian. In Danyluk, A. P., Bottou, L., and Littman, M. L. (eds.), Proceedings of the 26th Annual International Conference on Machine Learning, ICML 2009, Montreal, Quebec, Canada, June 14-18, 2009, volume 382 of ACM International Conference Proceeding Series, pp. 81–88. ACM, 2009.
12.Chen, J., Ma, T., and Xiao, C. Fastgcn: Fast learning with graph convolutional networks via importance sampling. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings, 2018.
13.Chien, E., Peng, J., Li, P., and Milenkovic, O. Adaptive universal generalized pagerank graph neural network. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
14.Defferrard, M., Bresson, X., and Vandergheynst, P. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems 29, NeurIPS 2016, December 5-10, 2016, Barcelona, Spain, pp. 3837–3845, 2016.
15.Deshpande, Y., Sen, S., Montanari, A., and Mossel, E. Contextual stochastic block models. In Bengio, S., Wallach, H. M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 31, NeurIPS 2018, December 3-8, 2018, Montreal, Canada, pp. 8590–8602, 2018.
16.Duvenaud, D., Maclaurin, D., Aguilera-Iparraguirre, J., Gomez-Bombarelli, R., Hirzel, T., Aspuru-Guzik, A., and Adams, R. P. Convolutional networks on graphs for learning molecular fingerprints. In Cortes, C., Lawrence, N. D., Lee, D. D., Sugiyama, M., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 28, NeurIPS 2015 December 7-12, 2015, Montreal, Quebec, Canada, pp. 2224–2232, 2015.
17.Fey, M. and Lenssen, J. E. Fast graph representation learning with pytorch geometric. CoRR, abs/1903.02428, 2019.
18.Fu, G., Hou, Y., Zhang, J., Ma, K., Kamhoua, B. F., and Cheng, J. Understanding graph neural networks from graph signal denoising perspectives. CoRR, abs/2006.04386, 2020.
19.Gama, F., Bruna, J., and Ribeiro, A. Stability properties of graph neural networks. IEEE Transactions on Signal Processing, 68:5680–5695, 2020.
20.Garg, V. K., Jegelka, S., and Jaakkola, T. S. Generalization and representational limits of graph neural networks. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 3419–3430. PMLR, 2020.
21.Grandvalet, Y. and Bengio, Y. Semi-supervised learning by entropy minimization. In Advances in Neural Information Processing Systems 17, NIPS 2004, December 13-18, 2004, Vancouver, British Columbia, Canada, pp. 529–536, 2004.
22.Hamilton, W. L., Ying, Z., and Leskovec, J. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems 30, NeurIPS 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 1024–1034, 2017.
23.Hein, M. Uniform convergence of adaptive graph-based regularization. In The 19th Annual Conference on Learning Theory, COLT 2006, Pittsburgh, PA, USA, June 22-25, 2006, volume 4005, pp. 50–64, 2006.
24.Henaff, M., Bruna, J., and LeCun, Y. Deep convolutional networks on graph-structured data. CoRR, abs/1506.05163, 2015.
25.Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems 33, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
26.Huang, Q., He, H., Singh, A., Lim, S., and Benson, A. R. Combining label propagation and simple models outperforms graph neural networks. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
27.Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
28.Klicpera, J., Bojchevski, A., and Gunnemann, S. Predict then propagate: Graph neural networks meet personalized pagerank. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
29.Li, G., Muller, M., Thabet, A. K., and Ghanem, B. Deep-gcns: Can gcns go as deep as cnns? In 2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019, Seoul, Korea (South), October 27 - November 2, 2019, pp. 9266–9275. IEEE, 2019.
30.Li, Q., Han, Z., and Wu, X. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence, AAAI 2018, New Orleans, Louisiana, USA, February 2-7, 2018, pp. 3538–3545, 2018.
31.Liao, R., Zhao, Z., Urtasun, R., and Zemel, R. S. Lanczosnet: Multi-scale deep graph convolutional networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
32.Liu, F., Chakraborty, S., Li, F., Liu, Y., and Lozano, A. C. Bayesian regularization via graph laplacian. Bayesian Analysis, 9(2):449–474, 2014.
33.Liu, J. and Han, J. Spectral clustering. In Aggarwal, C. C. and Reddy, C. K. (eds.), Data Clustering: Algorithms and Applications, pp. 177–200. CRC Press, 2013.
34.Liu, X., Jin, W., Ma, Y., Li, Y., Liu, H., Wang, Y., Yan, M., and Tang, J. Elastic graph neural networks. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 6837–6849. PMLR, 2021.
35.Loukas, A. What graph neural networks cannot learn: depth vs width. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
36.Luo, D., Huang, H., Ding, C. H. Q., and Nie, F. On the eigenvectors of p-laplacian. Machine Learning, 81(1):37–51, 2010.
37.Marcheggiani, D. and Titov, I. Encoding sentences with graph convolutional networks for semantic role labeling. In Palmer, M., Hwa, R., and Riedel, S. (eds.), Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, EMNLP 2017, Copenhagen, Denmark, September 9-11, 2017, pp. 1506–1515. Association for Computational Linguistics, 2017.
38.Nadler, B., Srebro, N., and Zhou, X. Semi-supervised learning with the graph laplacian: The limit of infinite unlabelled data. Advances in Neural Information Processing Systems, NIPS 2009, 22:1330–1338, 2009.
39.Niepert, M., Ahmed, M., and Kutzkov, K. Learning convolutional neural networks for graphs. In Balcan, M. and Weinberger, K. Q. (eds.), Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 2014–2023. JMLR.org, 2016.
40.Niyogi, P. Manifold regularization and semi-supervised learning: some theoretical analyses. Journal of Machine Learning Research, 14(1):1229–1250, 2013.
41.NT, H. and Maehara, T. Revisiting graph neural networks: All we have is low-pass filters. CoRR, abs/1905.09550, 2019.
42.Oono, K. and Suzuki, T. Graph neural networks exponentially lose expressive power for node classification. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
43.Page, L., Brin, S., Motwani, R., and Winograd, T. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
44.Pei, H., Wei, B., Chang, K. C., Lei, Y., and Yang, B. Geom-gcn: Geometric graph convolutional networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
45.Rozemberczki, B., Allen, C., and Sarkar, R. Multi-scale attributed node embedding. Journal of Complex Networks, 9(2), 2021.
46.Satorras, V. G. and Estrach, J. B. Few-shot learning with graph neural networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
47.Sen, P., Namata, G., Bilgic, M., Getoor, L., Gallagher, B., and Eliassi-Rad, T. Collective classification in network data. AI Magazine, 29(3):93–106, 2008.
48.Shchur, O., Mumme, M., Bojchevski, A., and Gunnemann, S. Pitfalls of graph neural network evaluation. CoRR, abs/1811.05868, 2018.
49.Sindhwani, V., Niyogi, P., Belkin, M., and Keerthi, S. Linear manifold regularization for large scale semi-supervised learning. In Proceedings of the 22nd ICML Workshop on Learning with Partially Classified Training Data, volume 28, 2005.
50.Slepcev, D. and Thorpe, M. Analysis of p-laplacian regularization in semi-supervised learning. CoRR, abs/1707.06213, 2017.
51.Smola, A. J. and Kondor, R. Kernels and regularization on graphs. In Scholkopf, B. and Warmuth, M. K. (eds.), Computational Learning Theory and Kernel Machines, 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings, volume 2777 of Lecture Notes in Computer Science, pp. 144–158. Springer, 2003.
52.Thekumparampil, K. K., Wang, C., Oh, S., and Li, L. Attention-based graph neural network for semi-supervised learning. CoRR, abs/1803.03735, 2018.
53.van der Maaten, L. and Hinton, G. Visualizing data using t-sne. Journal of Machine Learning Research, 9(86):2579–2605, 2008.
54.van Engelen, J. E. and Hoos, H. H. A survey on semi-supervised learning. Machine Learning, 109(2):373–440, 2020.
55.Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks. In ` 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, 2018.
56.Velickovic, P., Fedus, W., Hamilton, W. L., Lio, P., Bengio, Y., and Hjelm, R. D. Deep graph infomax. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
57.Verma, S. and Zhang, Z. Stability and generalization of graph convolutional neural networks. In The 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pp. 1539–1548, 2019.
58.von Luxburg, U. A tutorial on spectral clustering. Statistics and Computing, 17(4):395–416, 2007.
59.Wang, H. and Leskovec, J. Unifying graph convolutional neural networks and label propagation. CoRR, abs/2002.06755, 2020.
60.Wu, F., Jr., A. H. S., Zhang, T., Fifty, C., Yu, T., and Weinberger, K. Q. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 6861–6871, 2019.
61.Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Yu, P. S. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning System, 32(1):4–24, 2021.
62.Xinyi, Z. and Chen, L. Capsule graph neural network. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
63.Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K., and Jegelka, S. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmassan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 5449–5458. PMLR, 2018.
64.Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2017 New Orleans, LA, USA, May 6-9, 2019, Conference Track Proceedings, 2019.
65.Ying, Z., You, J., Morris, C., Ren, X., Hamilton, W. L., and Leskovec, J. Hierarchical graph representation learning with differentiable pooling. In Bengio, S., Wallach, H. M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 31, NeurIPS 2018, December 3-8, 2018, Montreal, Canada, pp. 4805–4815, 2018.
66.Ying, Z., Bourgeois, D., You, J., Zitnik, M., and Leskovec, J. Gnnexplainer: Generating explanations for graph neural networks. In Advances in Neural Information Processing Systems 32, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 9240–9251, 2019.
67.Zeng, H., Zhou, H., Srivastava, A., Kannan, R., and Prasanna, V. K. Graphsaint: Graph sampling based inductive learning method. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
68.Zhou, D. and Scholkopf, B. Regularization on discrete spaces. In The 27th DAGM Symposium, Vienna, Austria, August 31 - September 2, 2005, volume 3663, pp. 361–368, 2005.
69.Zhou, D., Bousquet, O., Lal, T. N., Weston, J., and Scholkopf, B. Learning with local and global consistency. In Thrun, S., Saul, L. K., and Scholkopf, B. (eds.), Advances in Neural Information Processing Systems 16, NIPS 2003, December 8-13, 2003, Vancouver and Whistler, British Columbia, Canada, pp. 321–328. MIT Press, 2003.
70.Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., and Sun, M. Graph neural networks: A review of methods and applications. AI Open, 1:57–81, 2020.
71.Zhou, X. and Belkin, M. Semi-supervised learning by higher order regularization. In Gordon, G. J., Dunson, D. B., and Dud´ık, M. (eds.), Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2011, Fort Lauderdale, USA, April 11-13, 2011, volume 15 of JMLR Proceedings, pp. 892–900. JMLR.org, 2011.
72.Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., and Koutra, D. Beyond homophily in graph neural networks: Current limitations and effective designs. In Advances in Neural Information Processing Systems 33, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
73.Zhu, J., Rossi, R. A., Rao, A., Mai, T., Lipka, N., Ahmed, N. K., and Koutra, D. Graph neural networks with heterophily. In 35th AAAI Conference on Artificial Intelligence, AAAI 2021, Virtual Event, February 2-9, 2021, pp. 11168–11176. AAAI Press, 2021.
74.Zhu, X., Ghahramani, Z., and Lafferty, J. D. Semi-supervised learning using gaussian fields and harmonic functions. In Fawcett, T. and Mishra, N. (eds.), Machine Learning, Proceedings of the Twentieth International Conference, ICML 2003, August 21-24, 2003, Washington, DC, USA, pp. 912–919. AAAI Press, 2003.
75.Zitnik, M. and Leskovec, J. Predicting multicellular function through multi-layer tissue networks. Bioinform., 33 (14):i190–i198, 2017.

Citation

MLA

Fu, G., et al. “$p$-Laplacian Based Graph Neural Networks”. International Conference on Machine Learning, vol. 162, 2022, pp. 6878–917, https://proceedings.mlr.press/v162/fu22e.html.

APA

Fu, G., Zhao, P., & Bian, Y. (2022). $p$-Laplacian Based Graph Neural Networks. International Conference on Machine Learning, 162, 6878–6917. https://proceedings.mlr.press/v162/fu22e.html

Chicago

Fu, G., P. Zhao, and Y. Bian. 2022. “$p$-Laplacian Based Graph Neural Networks”. International Conference on Machine Learning 162: 6878–6917. https://proceedings.mlr.press/v162/fu22e.html.

Harvard

Fu, G., Zhao, P. and Bian, Y. (2022) “$p$-Laplacian Based Graph Neural Networks”, International Conference on Machine Learning. PMLR, pp. 6878–6917. Available at: https://proceedings.mlr.press/v162/fu22e.html.

Vancouver

1. Fu G, Zhao P, Bian Y (2022) $p$-Laplacian Based Graph Neural Networks. In: International Conference on Machine Learning. PMLR, pp 6878–6917

BibTeX

@InProceedings{pmlr-v162-fu22e,
  title = 	 {$p$-{L}aplacian Based Graph Neural Networks},
  author =       {Fu, Guoji and Zhao, Peilin and Bian, Yatao},
  booktitle = 	 {Proceedings of the 39th International Conference on Machine Learning},
  pages = 	 {6878--6917},
  year = 	 {2022},
  editor = 	 {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
  volume = 	 {162},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {17--23 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v162/fu22e/fu22e.pdf},
  url = 	 {https://proceedings.mlr.press/v162/fu22e.html},
  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. Moreover, 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 $^p$GNN, 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 as low-high-pass filters, thus making $^p$GNNs are effective on both homophilic and heterophilic graphs. Empirical studies on real-world and synthetic datasets validate our findings and demonstrate that $^p$GNNs significantly outperform several state-of-the-art GNN architectures on heterophilic benchmarks while achieving competitive performance on homophilic benchmarks. Moreover, $^p$GNNs can adaptively learn aggregation weights and are robust to noisy edges.}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

p-Laplacian Based Graph Neural Networks

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — p-Laplacian regularization yields adaptive graph message passing

Knowl 2 — pGNN uses a learned feature map followed by p-Laplacian propagation

Knowl 3 — p-Laplacian message passing approximates a polynomial spectral filter

Knowl 4 — Local signal variation determines whether propagation is low-pass or low-high-pass

Knowl 5 — The regularization-derived iteration decreases its objective under suitable settings

Knowl 6 — pGNN outperforms graph baselines on the evaluated heterophilic benchmarks

Knowl 7 — pGNN remains competitive with established GNNs on homophilic benchmarks

Knowl 8 — Synthetic and edge-corruption experiments support adaptation to unreliable topology

Knowl 9 — The pGNN prediction risk is bounded by feature error, graph diffusion, and feature noise

Knowl 10 — Known limitations include large-graph memory cost and caveats at p=1

References

Citation

BibTeX

Source Code

Access the Paper