# Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 63 references that are in the map.
- First posted on arXiv 20 Feb 2025.

## Builds on (most cited first, 11 of 11)

- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Fair Correlation Clustering](https://mlsanity.com/paper/2002.02274/) (2020)
- [Efficient Decomposition of Image and Mesh Graphs by Lifted Multicuts](https://mlsanity.com/paper/1505.06973/) (2015)
- [DeepCut: Unsupervised Segmentation using Graph Neural Networks Clustering](https://mlsanity.com/paper/2212.05853/) (2022)
- [Correlation Clustering with Sherali-Adams](https://mlsanity.com/paper/2207.10889/) (2022)
- [Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering](https://mlsanity.com/paper/1712.05825/) (2017)
- [Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds](https://mlsanity.com/paper/2111.10699/) (2021)
- [Correlation Clustering and Biclustering with Locally Bounded Errors](https://mlsanity.com/paper/1506.08189/) (2015)
- [GASP, a generalized framework for agglomerative clustering of signed graphs and its application to Instance Segmentation](https://mlsanity.com/paper/1906.11713/) (2019)
- [A centrality measure for quantifying spread on weighted, directed networks](https://mlsanity.com/paper/2303.09684/) (2023)
- [ClusterFuG: Clustering Fully connected Graphs by Multicut](https://mlsanity.com/paper/2301.12159/) (2023)

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

- [Partial Optimality in the Preordering Problem](https://mlsanity.com/paper/2602.17346/) (2026)

## Abstract (arXiv)

The NP-hard maximum value preordering problem is both a joint relaxation and a hybrid of the clique partition problem (a clustering problem) and the partial ordering problem. Toward approximate solutions and lower bounds, we introduce a linear-time 4-approximation algorithm that constructs a maximum dicut of a subgraph and define local search heuristics. Toward upper bounds, we tighten a linear program relaxation by the class of odd closed walk inequalities that define facets, as we show, of the preorder polytope. We contribute implementations of the algorithms, apply these to the task of jointly clustering and partially ordering the accounts of published social networks, and compare the output and efficiency qualitatively and quantitatively.