# Semi-Supervised Node Classification on Graphs: Markov Random Fields vs. Graph Neural Networks

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Dec 2020.

## Built on by (most cited first, 6 of 6)

- [A Survey on Graph Counterfactual Explanations: Definitions, Methods, Evaluation, and Research Challenges](https://mlsanity.com/paper/2210.12089/) (2022)
- [Neural Structured Prediction for Inductive Node Classification](https://mlsanity.com/paper/2204.07524/) (2022)
- [Graph Neural Networks Intersect Probabilistic Graphical Models: A Survey](https://mlsanity.com/paper/2206.06089/) (2022)
- [Watermarking Graph Neural Networks via Explanations for Ownership Protection](https://mlsanity.com/paper/2501.05614/) (2025)
- [Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations](https://mlsanity.com/paper/2503.18503/) (2025)
- [MAGIC: Topology-Aware Analytic Graph Few-Shot Class-Incremental Learning](https://mlsanity.com/paper/2610.04963/) (2026)

## Abstract (arXiv)

Semi-supervised node classification on graph-structured data has many applications such as fraud detection, fake account and review detection, user's private attribute inference in social networks, and community detection. Various methods such as pairwise Markov Random Fields (pMRF) and graph neural networks were developed for semi-supervised node classification. pMRF is more efficient than graph neural networks. However, existing pMRF-based methods are less accurate than graph neural networks, due to a key limitation that they assume a heuristics-based constant edge potential for all edges. In this work, we aim to address the key limitation of existing pMRF-based methods. In particular, we propose to learn edge potentials for pMRF. Our evaluation results on various types of graph datasets show that our optimized pMRF-based method consistently outperforms existing graph neural networks in terms of both accuracy and efficiency. Our results highlight that previous work may have underestimated the power of pMRF for semi-supervised node classification.