# Total Variation Graph Neural Networks

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 52 references that are in the map.
- First posted on arXiv 11 Nov 2022.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding](https://mlsanity.com/paper/2002.01680/) (2020)
- [Revisiting Graph Neural Networks: All We Have is Low-Pass Filters](https://mlsanity.com/paper/1905.09550/) (2019)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [Graph Neural Networks with convolutional ARMA filters](https://mlsanity.com/paper/1901.01343/) (2019)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [A Unified View on Graph Neural Networks as Graph Signal Denoising](https://mlsanity.com/paper/2010.01777/) (2020)
- [Towards Sparse Hierarchical Graph Classifiers](https://mlsanity.com/paper/1811.01287/) (2018)
- [SpectralNet: Spectral Clustering using Deep Neural Networks](https://mlsanity.com/paper/1801.01587/) (2018)
- [Understanding Pooling in Graph Neural Networks](https://mlsanity.com/paper/2110.05292/) (2021)
- [Elastic Graph Neural Networks](https://mlsanity.com/paper/2107.06996/) (2021)
- [A Comprehensive Survey on Community Detection with Deep Learning](https://mlsanity.com/paper/2105.12584/) (2021)
- [Graph Neural Networks in TensorFlow and Keras with Spektral](https://mlsanity.com/paper/2006.12138/) (2020)
- [Trend Filtering on Graphs](https://mlsanity.com/paper/1410.7690/) (2014)
- [p-Laplacian Based Graph Neural Networks](https://mlsanity.com/paper/2111.07337/) (2021)
- [Higher-order Clustering and Pooling for Graph Neural Networks](https://mlsanity.com/paper/2209.03473/) (2022)

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

- [Rayleigh Quotient Graph Neural Networks for Graph-level Anomaly Detection](https://mlsanity.com/paper/2310.02861/) (2023)
- [Graph Pooling via Ricci Flow](https://mlsanity.com/paper/2407.04236/) (2024)
- [Robust Graph Neural Networks via Unbiased Aggregation](https://mlsanity.com/paper/2311.14934/) (2023)
- [A Comprehensive Graph Pooling Benchmark: Effectiveness, Robustness and Generalizability](https://mlsanity.com/paper/2406.09031/) (2024)
- [MaxCutPool: differentiable feature-aware Maxcut for pooling in graph neural networks](https://mlsanity.com/paper/2409.05100/) (2024)
- [Torch Geometric Pool: the PyTorch library for pooling in Graph Neural Networks](https://mlsanity.com/paper/2512.12642/) (2025)
- [VLSI Hypergraph Partitioning with Deep Learning](https://mlsanity.com/paper/2409.01387/) (2024)

## Abstract (arXiv)

Recently proposed Graph Neural Networks (GNNs) for vertex clustering are trained with an unsupervised minimum cut objective, approximated by a Spectral Clustering (SC) relaxation. However, the SC relaxation is loose and, while it offers a closed-form solution, it also yields overly smooth cluster assignments that poorly separate the vertices. In this paper, we propose a GNN model that computes cluster assignments by optimizing a tighter relaxation of the minimum cut based on graph total variation (GTV). The cluster assignments can be used directly to perform vertex clustering or to implement graph pooling in a graph classification framework. Our model consists of two core components: i) a message-passing layer that minimizes the ℓ1 distance in the features of adjacent vertices, which is key to achieving sharp transitions between clusters; ii) an unsupervised loss function that minimizes the GTV of the cluster assignments while ensuring balanced partitions. Experimental results show that our model outperforms other GNNs for vertex clustering and graph classification.