Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network
Authors: Jannik Irmai
Maximilian Moeller
Bjoern Andres
Venue: Accepted by TMLR ()

Abstract: 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.

Published in Transactions on Machine Learning Research (01/2026)
Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network
Jannik Irmai
jannikk wrw.aaddnairwdddeeeeeeee de
TU Dresden, Dept. of Computer Science, Dresden, Germany
Maximilian Mocller
massinkkan.mmollee@kkkkuuunn
KU Lewven, Dept. of Computer Science, Leuven, Belgium
Bjoern Andres
TÚ Dresden, Dept. of Computer Science, Dresden, Germany Center for Scalable Data Analytics and AI, Lesdenn/Leipzig
Reviewed on OpenReview: https: openreview. pet/forum? id- cBsUnw7C03
Abstract
The NP-hard maximum value preordering problem is both a joint relaxation and hybrid of the clique partition problem (a clustering problem) and the partial ordering problem. Toward approximate solutions and lower bounds, introduce a linear-time 4-approximation algorithm that constructs maximum dicut of 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 algorithus,, 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.
1 Introduction
We set out to find a binary relation on the set of accounts of social network. Here, the notion that one account follows, likes or reacts to another account need neither be symmetric nor asymmetric. In particular, following j does not need to imply that j follows i, nor does necessarily imply that j does not follow i. Clustering does not capture the asymmetrie subsets of the relation on the social network because the equivalence relation that characterizes the clustering is symmetric. Similarly, partial ordering does not capture the symmetric subset of the relation because partial orders are antisymmetric. Like in clustering and partial ordering, we work with the assumption" that the relation on the social network is transitive, i.e., if follows j and j follows &o then follows k. Unlike in clustering and partial ordering, we do not assume symmetry or antisymmetry. To model our assumption, we apply the preordering problem:
Definition 1.1. Wakabayashi (1998) Given a finite V and a (value) Ci E R. for every pair ij of distinct i.j E V, the (mazimum value) preordering problem consists in finding a preorder S on so as to maximize the sum of the (values) Gj of those pairs ij V with i j for which i j.
If preorder is symmetric, it is equivalence relation and therefore characterizes a clustering. If preorder is antisymmetric, it is partial order. In fact, the preordering problem is a. joint relaxation of the clique partition problem (a clustering problem) and the partial ordering problem. Moreover, every preorder defines, and is characterized by, a clustering and a partial order: A clustering is defined by the symmetric subset
Source code available attps://githul com/ Saaaniiirmm//prrrrrrringg segeeordriing-problen problem
2hhi assumption simplifies and possibly contradicts reality, and quantify the deviation empirically.

---

Published in Transactions on Machine Learning Research (01/2026)
Figure 1: Depicted on the left is a Twitter ego-network from Leskovec Mcauley (2012). Depicted on the right a preorder on the accounts of this network consisting clustering (gray circles) and a partial order on the set of clusters (black edges). This preorder is an optimal solution to the instance of the preordering problem (Definition 1.1) defined such that Cj = 1 if the pair ij exists in the network, and Cij -1 otherwise.
of the preorder (an equivalence relation). A strict partial order on the set of clusters is well-defined by the asymmetric subset of the preorder. (An example is depicted in Figure 1.) Thus, the preordering problem is also a hybrid of a clustering problem and a partial ordering problem.
In this article, we define algorithms for the preordering problem. To obtain approximate solutions and lower bounds, we introduce linear-time 4-approximation algorithm and local search heuristics. To obtain upper bounds, we consider a linear program (LP) relaxation that we tighten by the class of odd closed walk inequalities that define facets, the algorithms we discuss, apply these to social networks from Fink et al. (2023) and Leskovec & Mcauley (2012) with up to 10" edges and compare the output and efficiency qualitatively and quantitatively.
show, of the preorder polytope. We contribute implementations of
2 Related work
The preordering problem is formulated by Wakabayashi (1998) who establishes NP-hardness even for values in ((IV))) and discusses the complexity of many specializations. Her hardness result for the general problem is strengthened by Weller et al. (2012) who prove NP-hardness even for values in 1-1, A local search algorithm that greedily decides whether or not to relate pairs is introduced by Böcker et al. (2009). We reproduce this algorithm in Section 4.2. The geometry of the preorder polytope is discussed briefly by Gurgel (1992).
Closely related to preordering but studied independently in the literature is the transitivity editing problem Jacob et al. (2008); Böcker et al. (2009); Weller et al. (2012). Given digraph, the objective is to find a minimum set of ares to be added or removed so as to make the digraph transitive. This problem is equivalent to the preordering problem with values Gj-- = 1 if ij is an are in the digraph, and Gj = -1 otherwise. Even this restriction to values in {-1, is NP-hard Weller et al. (2012). The transitivity editing problem is studied predominantly from the perspective of parammeer tractability; efficient algorithms for the case where the total number of ares to be added removed is bounded are developed by Böcker et al. (2009);
Weller et al. (2012).
Preordering is related to correlation clustering Emanuel & Fiat (2003); Bansal et al. (2004); Demaine et al. (2006), more specifically, to maximum value weighted correlation clustering for complete graphs, which is also known as clique partitioning Grötschel & Wakabayashi (1989), where values Cj are associated with unordered pairs {i,j), and the task is to find an equivalence relation on V so as to maximize the sum of the values of those pairs {i,j} for which ~ j. This problem is more specific than preordering in that equivalence relations are precisely the symmetric preorders. The complexity and hardness of approximation of correlation clustering have been studied extensively (Swamy, 2004; Charikar al., 2005; Chawla et al., 2015; Veldt, 2022; Cohon-Addad et al., 2022; Klein et al., 2023). In particular, it is known that clique partitioning cannot be approximated to within n=-e unless P = NP for n the number of elements and any >>0 0 (Bachrach et al., 2013; Zuckerman, 2007). Much work has been devoted also to the study of the clique partitioning polytope Grötschel & Wakabayashi (1990b:a); Deza et al. (1991; 1992); Chopra & Rao (1995); Bandelt al. (1999); Oosten al. (2001); Sørensen (2002); Letchford & Sorensen (2025). Correlation clustering has many applications, including community detection in social networks (Brandes et al., 2008;
2

---

Published in Transactions on Machine Learning Research (01/2026)
Figure Depicted on the left is an instance of the preordering problem with [V| 5. The value Ciy is written next to the are from i to j. and ares that not depicted have value of 0. Depicted in the middle is optimal solution to the preordering problem. The value of this solution is P(c) = 14. The upper bound is B(c)= = 17 and thus, the transitivity index is T(c)= I7'
14 Depicted on the right is the same preorder as a
partial order on clusters (equivalence classes). Here and in all subsequent figures, partial orders are depicted by their unique transitive reduction. E.g., the are (2,4) is not shown because is implied by the arcs (2,3) and (3, 4).
Voldt et al., 2018) and image analysis (Yarkony et al., 2012; Beier et al., 2015; Aftalo et al., 2023; Abbas & Swoboda, 2023). Variants that emphasize local errors are studied by Puleo Milenkovic (2016); Kalhan et al. (2019); Ahmadian et al. (2020).
Preordering is related also to partial ordering (Müller, 1996) where the task is to find partial order S V so to maximize the sum of the values of those pains ij for which i S j. Partial ordering is more specific than preordering in that partial orders are precisely the antisymmetric preorders. The polyhedral geometry of partial orders is studied by Müller (1996). Also this problem has received less attention so far than even more constrained problems, like the linear ordering problem (Grötschel et al., 1984; Martí & Reinelt, 2011; Ceberio al., 2015), the closely related rank aggregation problem (Ailon al., 2008; Schalekamp Zuylen, 2009) and the feedback are set problem on tournament graphs (Karpinski & Schudy, 2010). The geometry of several order polytopes is studied by Doignon & Fiorini (2001); Doignon & Rexhep (2016). The understanding of the computational complexity of finding maximum value order for various types of orders is improved by Hudry (2008; 2012) who shows that some problems remain NP-hard for restricted value functions.
A joint relaxation of correlation clustering and linear ordering is the bucket ordering problem, sometimes called the weak ordering problem, that asks for both clustering and a linear order on the clusters (Gurgel & Wakabayashi, 1997; Fiorini, 2003; Fiorini & Fishburn, 2004; Fiorini, 2006). This problem has been applied to the tasks of dating archeological sites (Gionis et al., 2006), finding consensus among voters Aledo et al. (2018; 2021) and constructing user recommendations (Jurewicz et al., 2023).
3 Preordering problem
Throughout this article, consider some finite, non-empty set V, c.g., the accounts of social network. For simplicity and conciseness, let V,, denote the set of all n-tuples of pairwise distinct elements of V. Refer to the elements of and V2 as nodes and arcs, respectively.
We cast the preordering problem (Definition 1.1) with respect to and values e: V/2 + as an integer linear program (ILP):
max
Σ CizTta VEVV/
(1)
subject to Fij E {0,1}
Fi A ijk E V/3
(2)
Tij + Tikk <
(3)
An example depicted in Figure 2. Let P(c) denote the objective value of an optimal solution. For convenience, define Iy and c₂ = 0 for all E V. Note that the map from to S. == = E V2 215 1} is bijection from the feasible solutions of the ILP (1)-(3 to the set of preorders V. Indeed, the objective
3

---

Published in Transactions on Machine Learning Research (01/2026)
value of feasible solution z the ILP (1)-(3) is equal to the value of Sa according to Definition 1.1. See Appendix A.1 for further details.
Theorem 3.1 (Weller et al. (2012)). The preordering problem is NP-hord even for c: V/2 (-1,1}.
In the context of clustering, it is well-known that clique partitions are precisely the complements of unions of cuts. The following lemma states analogously that prcorders are preciscly the complements of unions of directed cuts (diculs):
Lemma 3.2. An are subset A V2 is preorder if and only if V2 A is the union of dicuts, i.e., A USES 6(5) for some S cV where 8(5) = (ij E V22 E S.j & $) denotes the dicut in V2 defined by S.
Proof. If. Let V2 \ A = USES 8(5) for some S C 2V. Suppose is not a preorder, i.e. there exist i, k E V such that jjkjk E A but ik & A. By definition of A, there cxists S E S such that ij. jk & 8(S) and ik E 8(S). By definition of directed cuts, ik E 6(5) implies i E S and & S. With this, ij $ 8(S) implies j E while jk & 8(5) implies j & S, contradiction.
Only if. Let A C V be a preorder. For i EV, define S = (je i A} and let S = (S, C [ViiEV). We show that V2 A A=Uses ö(S) holds. Firstly, suppose ij Usess 8(S), i.e., there exists k E V such that áj E 8(S)). By definition this implies ki E A and kj & A. As A is a preorder it follows that ij & A. Secondly, suppose ij E A. For any k E V it holds that i E S₁ iff ki E A iff kj E A iff j E St. Therefore ij & ((x)) for all & E V and in particular ij & USES 8(S), which proves the claim.
Next, we introduce a notion to quantify the transitivity of a value function c. Clearly, the sum of all positive values an upper bound to the preordering problem. Let
P(c) T(c) B(c)
with B(c) Σ Cj
(4)
OjEV2 53200
denote the proportion of the optimal value to the upper bound. We call it the transitivily index. quantifies how transitive the values are. If there exists transitive relation that contains all pairs with positive value and no pair with negative value, then P(c) B(c), hence T(c) 1. If no such relation exists, then T(c) 1. As the empty relation is transitive, P(c) 2 O, and thus, T(c) [0, for all V/2 - R. In the context of social networks, the transitivity index can be interpreted as a mcasure for how homogencous the information flow is. If the transitivity index is high, the information flow is homogeneous: If a receives information from and receives information from the also receives information form c. the index is low, the flow of information is less structured.
4 Algorithms
In this section, we describe algorithms for solving the preordering problem and for efficiently computing upper bounds. The input size of an instance of the preordering problem [V/ E O(VV))). Nevertheless, we may state the time complexity of an algorithm as function of [V..
4.1 Linear-time 4-approximation via max-dicut
We exploit connection between directed cuts and preorders to obtain 4-approximation algorithm for the preordering problem. For a directed graph (digraph) D (V,E) and a node subset S C V, the directed cut (dicut) defined by S is the edge subset 5(S) (ij E i S.j & S}. Notice that any dicut is transitive because it does not contain any consecutive edges. Given edge weights w: E + Rzo, the mazimum directed cut problem (maz-dicut) consists in finding dicut of maximum weight. Max-dicut admits simple randomized 4-approximation: By assigning each node with probability 1 to S, the probability that any given edge ij E E is contained in the cut (namely if i E S and j e S, each with probability $)). Therefore, the expected value of such a randomly chosen dicut is 1 Eijer Wi where Enjr Way is a trivial upper bound the max-dicut problem. This algorithm can be de-randomized (Halperin & Zwick, 2001; Bar-Noy & Lampis, 2012) as detailed in Appendix A.2 to obtain Algorithm that runs in time ((V
4

---

Published in Transactions on Machine Learning Research (01/2026)
Figure 3: Depicted is instance of the preordering problem with [V] Solid and dashed ares indicate values of +1 and -1, respectively. Here, P(c) 1, B(e) and T(c) 3.
Theorem 4.1. There exists a 4-approzimation algorithm for the preordering problem with time complerity O(IV)).
Proof. For any instance of the preordering problem given by V and c: V2 + R, let E {ij E V/2 Ct > 0} and edge weights Way = Cay for all ij E be the digraph that consists of all ares with positive value. Algorithm finds dicut 8(S) with value Eiee((s) Waj 2 Eijer Wiy. As 8(S) does not contain any two consecutive edges, x E 10,1)% with Tij = 1 if and only if ij E 8(S) is feasible for the instance of the preordering problem. Also,
(V.F) with
Σ CoTT =
Σ STER(S)
Σ Bij B(c) iEE
Wij 2
DEV
i.e., is 4-approximate solution. The computations described above and Algorithm are executed in time (((V13).
Remark 4.2. An immediate consequence of the proof of Theorem 4.1 is that T(c) 2 1 holds for all c: V/2 - IR By the example Figure 3, there exists a c: V22 + with T(c) 3" e: V/2 R with T(e) 3.
1 We do not know whether there exist
Remark 4.3. Every dicut is also a partial order and, thus, the partial ordering problem also admits a 4- approximation.
4.2 Greedy arc fixation (Böcker et al., 2009)
Böcker et al. (2009) propose an algorithm that fixes are labels groedily, one are at a time. The decision which are to fix and what label is based on the induced cost of these decisions: Excluding an are ij from the preorder (i.e., setting Tzy 0) implies that for every V \ {i.}} most one of the ares ik, kj can be included in the preorder. If both these ares have positive value, at least the smaller of the two values
Algorithm 1: Greedy max-dieut approximation
Input: Digraph D = (V, F), weights we E + R20
S = 5 0
9. = Σ JEEEEEE Wiy
JeeeSee WH VIEV
while SUS
E argmax [g:| (SVS))))
if g. 2
S= S (i)
= My
GjEV:ijer
gj = 9) Wii
VjEV: E
else
5 Š {i}
= + Wy
ijEV: VjEV:WEC
9 = g; + Wij
return 8(S)

---

Published in Transactions on Machine Learning Research (01/2026)
-2
Figure 4: For the instance of the preordering problem depicted above the optimal objective value is 4. The greedy are fixation algorithm may, in this order, fix 01, 10, 12, 02, 03, 13 to 1 and then fix the remaining arcs to yielding a solution with objective value 0. We note that this solution obtained if the algorithm breaks ties unfavorably. However, there exist more complex instances where the algorithm still fails come within factor of 4 of the optimal objective value (ef. Appendix A.3).
is *lost." R by excluding ij from the preorder. In total, the induced cost for excluding ij from the preorder is computed as
ice(is) max (0, ctj)
Σ
max min, cki)]
KEV
Similarly, the induced cost of inscrting an are ij into the preorder (i.c., sctting Diy = 1) is given by
ici(ij) max -ci) +
Σ kEV)E
(max(0, minfer., -kkj } + max min minf -ck)))
The greedy algorithm by Bücker et al. (2009) starts with all ares being unlabeled and iteratively selects an unlabeled are ij for which max (ice(ij), ici(is) is maximal. It labels Tij = O if ice(ij) 2 ici(is), and Tij = otherwise. After labeling a are ij, its value Cú is set to +oo if xiy = 1 and -oo otherwise. This ensures convergence to a fcasible solution. We term this algorithm greedy are fization. We note that Böcker et al. (2009) suggest to include a lower bound on the disagreement. on the instance excluding the nodes i and j the computation of the induced costs ice and ici. We do not use such additional bounds as these have led worse solutions and longer computation times in our experiments.
In total, the greedy are fixation algorithm consists of VV2l iterations. By maintaining a priority queue sorted by the induced costs, an are with maximal induced cost can be queried in time Ollog [V]) After fixing an are ij, only the induced costs of the ares incident to i and j change. For a single are, this change can be computed in constant time. And the changed induced cost can be updated in the priority queue in time O(log([V))) This results in time of (oVV]oog [V]) per iteration and in a total runtime of O(V1 log (V]).
While the greedy are fixation algorithm performs well in practice (see Section 5), it does not guarantee any approximation factor. This is shown by the example in Figure 4 that illustrates that the solution computed by the greedy are fixation algorithm can be off by an arbitrary factor.
4.3 Greedy arc insertion
Next, we define greedy algorithm for the preordering problem that starts from any feasible solution (e.g., the identity relation) and greedily inserts pairs into the relation without violating transitivity. While conceptually similar to greedy additive edge contraction (Keuper et al., 2015) and agglomerative clustering (Bailoni et al., 2022), specific combinatorial challenges arisc from the preordering problem: Firstly, there are up to ((VV1)) edge insertions in preordering, in contrast to at most O(VV) edge contractions in clustering (because the number of clusters decreases by one in every iteration). Secondly, in each iteration, O(V)?) ares need to be considered to potentially be added to the relation. Adding any one are can result in ((VV)2 additional ares that need to be added satisfy transitivity. A naive implementation of this algorithm would require ((IV)*) operations per iteration. Below, describe more efficient inplementation: Suppose V/2 {0,1) is a

---

Published in Transactions on Machine Learning Research (01/2026)
feasible solution to the preordering problem, and let ij V2. By setting Zi 1, all ares ke with zki = zze need to be set to 1 as well in order to satisfy transitivity. The amount by which the total value changes can thus be calculated as
gij = Σ
Cke (1 - Ixtt Ihs Zze
(5)
R
where Osz (1 Fxe) ensures that only values of ares that are currently labeled are considered. We call this value the gain from setting ij to 1. By representing æ, e, and g as matrices, the gain matrix g can be caleulated by two matrix multiplications
g g= x= (1
(6)
where denotes element-wise multiplication. With this, each iteration can be performed with only 0([V)*) operations. Furthermore, the matrix multiplication can be carried out in parallel GPU, In our imple- mentation of this algorithm, we do not utilize GPU parallelization but instead use sequential method that exploits the sparsity of the 01-matrix x.
4.4 Greedy moving
The greedy are insertion algorithm never removes an are from feasible solution. Removing are from preorder can result in relation that is not preorder and thus not a feasible solution. Removing a dicut from a preorder results in another preorder (by Lemma 3.2) and thus maintains feasibility. However, finding a dicut of minimum cost (in order to maximize the objective of the solution obtained by removing the cut) is well-known to be NP-hard (Karp, 1972). Below, we define O(V)?) operations that may remove ares from the preorder such that the difference in value resulting from each operation can be calculated efficiently.
Move up (down): Remove a node i E V from its current equivalence class and place it immediato above (below) the equivalence class the partial order. That is, set Tji (Iiz = 0) for all j E V {i) with Tiy 25z 1.
Move equivalence class: Move a node i E V from its current equivalence class to the equivalence class of node jE V (i). That is, set Fik = Tikk, Tki = Tki for all k KEV' (t).
Remove arcs from transitive reduction: Remove are from the transitive reduction of the partial
order of equivalence classes. That is, for an are ij E V22 such that = 0 V ækj = 0 for all
k: E V \ {i,j), set Tyg - for all i' E V with Far = xzi = 0 and all j' E V with Tzy" = I3 1.
We implement algorithm, termed greedy moving, that, in each iteration, performs optimal of the moves described above, an are insertion according to section 4.3. The operation that increases the objective value maximally can be found in O([V)), similarly to section 4.3.
4.5 Linear programming
In order to obtain an upper bound on the optimal value of the preordering problem and thus upper bound on the transitivity index T from (4), we consider the LP relaxation fo the ILP (1)-(3) obtained by replacing
(2) with
Zij [0, 1]
Vij E 1/2
(7)
This bound can be strengthened by adding lincar incqualities to the formulation that are satisfied by all binary solutions and cut off fractional solutions. Particularly powerful are inequalities that induce facets of the preorder polytope, i.e., the convex hull of the feasible solutions to the preordering problem. Polytopes of several closely related problems have been studied extensively, as discussod in Section Müller (1996) introduce the class of odd closed walk inequalities for the partial order polytope. We adapt these the preorder polytope follows.
7

---

Published in Transactions on Machine Learning Research (01/2026)
Definition 4.4. Let k 2 odd and fO....,k- 1] - V. The odd closed walk inequality with respect to is defined below where the additions + and i 2 are modulo k.
Σ (Fewr 22rw12) - k- 2
(8)
Müller (1996) proves validity of the odd closed walk inequalities for the partial order polytope by showing that they are obtained by adding certain triangle inequalities (3) and bax inequalities 0 S Tij for several ij E V/2 and rounding down the right-hand side. As triangle and box inequalities are valid also for the proorder polytope, the odd closed walk incqualities are valid for the preorder polytope as well. Morcover:
Lemma 4.5. Every inequality that induces a facet of the partial order polytope and valid for the preorder polylope also induces a facel of the preorder polylope.
Proof. As every partial order preorder, the partial order polytope contained in the preorder polytope. Thus, for any inequality that is valid for both polytopes, the dimension of the induced face of the preorder polytope is greater than equal to the dimension of the induced face of the partial order polytope. Since the partial order polytope is full-dimensional (Müller, 1996, Theorem 3.1), so is the preorder polytope, and, in particular, they have the same dimension. Together, any inequality that induces facet of the partial order polytope, i.e., a face of co-dimension 1, and is valid for the preorder polytope, induces a face of the proorder polytope of co-dimension at most 1, and, therefore, defines a facet.
Theorem 4.6. Let 2 3 odd and let v: 1o...,,-111 + V injective (i.e., u defines a simple cycle). Then the odd closed walk inequality (8) defines a facet of the preorder polytope.
Proof. Müller (1996) shows that if the odd closed walk a cycle (i.c., every node is visited at most once) then the correspouding odd closed walk inequality defines a facet of the partial order polytope (Müller, 1996, Theorem 4.2). Together with Lemma 4.5 the theorem follows.
While the number of odd closed walk incqualities is exponential in [V], , the separation problem can be solved in polynomial time (Mäller, 1996). This implies that also the T.P (1), (3), (8), (7) can be solved in polynomial time (Grötschel et al., 1981).
5 Experiments
We apply the algorithms defined in Section 4 to instances of the preordering problem from social networks. We solve LPs and ILPs with Gurobi Optimization, LLC (2024) in such way that triangle inequalities (3) and odd closed walk inequalities (8) are not emunerated in advance but are only added to the system if they become violated throughout the exccution the solver. All experiments are performed on an Intel Core 19-12900KF Genl2 x 24 and an NVIDIA GeForce RTX 4080 Super. We abbreviate the algorithms as follows:
ILP: Gurobi applied to the system (1)-(3)
LP: Gurobi applied to the system (1), (3), (7)
OCW: Gurobi applied to the system (1), (3), (7), (8)
GDC: Greedy max-dicut approximation (Section 4.1)
GAF: Greedy are fixation (Section 4.2)
GAT: Greedy are insertion (Section 4.3)
GM: Greedy moving (Section 4.4)
X+Y: Algorithm Y initialized with the output of X
5.1 Ego networks
In this section we consider ego networks of Twitter and Google+ (Leskovec & Mcauley, 2012). The ego network corresponding to given account consists of one node for each account that the given account
8

---

Published in Transactions on Machine Learning Research (01/2026)
10a
Method
Objective / [
0.565 (0.068)
0.8
Objective / |
0.548 (0.062)
10a
0.273 (0.137
0.6
Runtime
(S5)
0.364 (0.146)
0.4
10
Method
Runtime [s]
0.147 (2.209)
0.2
10-3
0.570 (8.734)
(M
0.236 (1.964)
14
(M,S)
0
50
100
150
200
250
(M
0.390 (2.094)
[V]
Figure 5: Shown above are objective values normalized by the number of edges (left) and runtimes (middle)
for those 435 Twitter instances for which the preorder (S), partial order ($), and clustering (~) problems are solved to optimality within a time limit of s00s. Here, (>, denotes successive clustering and partial ordering. Corresponding medians are reported in the tables on the right with the interquartile range in parentheses.
follows. Directed edges between accounts i and j indicate that follows j. The Twitter dataset consists of 973 ego networks with up to 247 nodes and 17930 edges. The Google+ dataset consists of 132 ego networks with up to 4938 nodes and 1614977 edges. We define instances of the preordering problem for each social network with values Cij- =1 1 if the edge ij is in the network and Gıj = -1 otherwise, for all ij E V2. With these values, B(c)= E
5.1.1 Comparison of preordering, clustering and partial ordering
We compare solutions to the preordering problem with those obtained by solving a clustering and a partial ordering problem. Additionally, and for a comparison, compute preorders by first computing clustering and then computing partial order the obtained clusters. This successive approach is in contrast to the joint clustering and partial ordering using the preordering problem. In order to compute solutions to the clustering and partial ordering problem, we add additional inequalities to the system (1)-(3): For clustering, we add symmotry constraints Zijz = F5 for all ij E V2. For partial ordering we add antisymmetry constraints Tij + æjj < 1 for ij E V22
Results for six ego networks are shown in Figure 6 and compared quantitatively in Table The first network, for instance, has |E| 54 edges and admits preorder of value 52. This preorder disagroes with two of the edges. Its transitivity index is T(c) 34 zs 0.963. The optimal clustering and partial ordering disagree with 14 and 20 edges, respectively. Not every social network has such a high transitivity index. The fourth 27 x 0.529, and the objective values of the optimal network, for example, has a transitivity index of T(c) = 5T solutions to the clustering (20) and partial ordering (26) problems are not much smaller than the value of the omtimal preorder (27).
Objective values and runtimes for the 434 out of 973 instances that have been solved within time limit of 500s are visualized in Figure 5. The objective values are highest for the preordering problem and lowest for the clustering problem. The values obtained by the successive approach are significantly smaller than those obtained by solving the preordering problem directly. This can be understood as an advantage of solving a joint clustering and partial ordering problem over solving these problems successively. On average, the runtime of the clustering problem the lowest, while that the partial ordering problem is the highest. The runtime of successive clustering and partial ordering is only marginally greater than that of just clustering because the instance of the partial ordering problem on clusters is much smaller than the instance of the partial ordering problem individual accounts.
9

---

Published in Transactions on Machine Learning Research (01/2026)
734493
15053535
13
16
10
3
16
104321108
126067398
10
215824411
6
1011500853443222119988
Figure 6: Depicted above in the left column are the ego networks from Table 1. Next to these networks, from left to right, are an optimal preorder, optimal clustering and optimal partial order. Disagreements with the social network edges minus the objective value stated in Table 1. It can be observed that the preorder has less disagreement compared to the clustering and partial order. For the network at the top, for instance, the preorder has only two disagreeing ares while the clustering has 14 disagreeing ares and the partial order has 20 disagreeing arcs.
highlighted by red arcs. The total number of disagreements is precisely the number of
10

---

Published in Transactions on Machine Learning Research (01/2026)
0.6
100
Method
Median 7 gap Opt
Instances
0.4
GDC
0.095 (0.065)
2
T gap
GDC+GAI
0.017 (0.016)
16
50
GDC+GM
0.030 (0.041)
38
0.2
GAF
0.029 (0.038)
GAF+GAI
0.025 (0.037)
53
GAF+GM
0.021 (0.039)
0
0.5
GDC GDC+GAI GDC+GM
GAF GAF+GAI GAF+GM
Fraction of LP gap closed
Figure Shown on the left is the fraction of the LP gap that is closed by including odd closod walk inequalities. On average, 30.4% of the gap closed. This evaluation is restricted those 313 instances from the Twitter dataset for which the optimal solution is computed within 500s time limit and the canonical LP bound is not tight. Shown in the middle are the differences between the lower bounds computed by the heuristic algorithms and the LP bound on all 973 instances. The table on the right reports the corresponding medians differences with the interquartile range in parentheses, as well as the number of instances for which an optimal solution was found.
5.1.2 Optimal solutions and bounds
Within the time limit of s00 the ILP algorithm finds optimal solutions to the instances of the preordering problem for 499 out of 973 Twitter ego networks. For these instances, the average transitivity index T is 0.580. For 186 of these instances, the LPP bound according Section 4.5 is tight. For the 313 instances for which the LP bound is not tight, the gap between the LP bound and the optimal solution is reduced by 30.4% on average by the odd closed walk inequalities; cf. Figure 7 (left).
We compute feasible solutions that are not guaranteed to be optimal with the heuristic algorithms GDC, GDC+GAI, GDC+GM, GAF, GAF+GAI, GAF+GM. The values of these feasible solutions are lower bounds on the transitivity index. Complementary to this, LP computes upper bounds on the transitivity index. Differences between these lower and upper bounds are shown in Figure (right). On average, GAF+GM comes closest to the LP bound with median difference of 0.0210. Still, for example, 121 instances, the solution computed by GDC+GAT is strictly better than that of GAF+GM.
On those 474 instances for which the ILP could not be solved to optimality, the median gap after the time limit of 500s is reached is 0.146. the upper bound computed with OCW 0.068. While il NP-hard compute the transitivily index exactly, this result shows that it can be estimated closely polynomial time for these instances. Morcover, this shows that the discussed heuristic algorithms together with the bounds obtained by OCW can result in much better solutions than those found by canonical ILP solver within the time limit.
contrast to this, the median gap between the best lower bound and
Table 1: Numerical results for the six ego networks depicted in Figure 6. Reported are the number of nodes ((V) and edges ([E)), the optimal values of the prcordering (2), clustering (~) and partial ordering (<) problems, and the corresponding normalized objective values (note that S/ E| is the transitivity index T))
Platform ID
[V]
E
</|EI
~/|EE|
S/|
Twitter
734493
9
34
0.963
0.741
0.630
Twitter
15053535
18
26
23
12
19
0.885
0.462
0.731
Twitter
104324908
13
77
62
34
51
0.805
0.442
0.662
Twitter
126067398
14
51
27
20
26
0.529
0.392
0.510
Twitter
215824411
10
40
35
24
28
0.875
0.600
0.700
Google+
10156008534482221999888
19
107
92
24
87
0.885
0.224
0.813
11

---

Published in Transactions on Machine Learning Research (01/2026)
GDC
10a
GDC+GAT
GDC+GM
10
Method
GAF
Runtime [s]
GAF+GAI
GDC
2.285-10'
0.857
100
GAF+GM
GDC+GAI
1.070-10
1.276
GDC+GM
4.814-10"
1.700
10
GAF
8.545-10"
1.519
CAF+GAL
9.272-10"
1.515
10-2
GAF+GM
3.401-10"
1.689
10
10
10
10
10
IV2
Figure 8: Runtimes of six hcuristic algorithms as a function of input size [V2]. Results are shown for runs terminating within 100s. The fit. lines are of the form a [V2 with coefficients a and x stated in the table. For example, for GDC, is close to which is expected as its asymptotic runtime is linear in [V/] (Theorem 4.1).
5.1.3 Efficiency of heursitic algorithms
We analyze the empirical runtime of the heuristic algorithms on the much larger Google+ ego networks. The largest network contains [V] = 4,938 nodes, which results in an instance the preordering problem of size V/2 = 24,378,906. The runtimes are shown in Figure 8. The fastest algorithm is GDC. This expected as its runtime is linear in the input size (cf. Section 4.1). Even for the largest instance, it terminates in less than second. The GDC+GAI algorithm, which runs GDC first and then GAI, also terminates within the time limit for all instances. In practice, GAI is much faster than GF and GAF because it may insert multiple ares per iteration leading to fewer iterations overall. While the algorithm GAF+GM, on average, computes slightly better solutions than GDC+GAL, algorithm GDC+GAI is significantly faster on large instances. The average lower bound on the transitivity index computed by GDC+GAI 0.61, i.., the Google+ ego networks exhibit. a slightly higher transitivity compared to the Twilter ego nelworks.
5.2 Twitter interaction network of the 117th US Congress
In this section we perform a qualitative analysis on a Twitter network of members of the 117th Congress of the United States. This netw has been published by Fink et al. (2023) who have measured for each pair of Twitter accounts of Members of Congress the reaction likelihood, i.e., the fraction of times the first account has reacted to contribution of the second account. The thusly obtained digraph consists of 475 nodes and 13,289 directed edges with non-zero likelihood. In contrast to the ego networks from the previous section, this network is not anonymized. This allows us to qualitatively interpret the results. We construct an instance of the preordering problem by defining are values e to be the reaction likelihood minus 0.01. With this, the are values reward ares from to j to be part the preorder if reacts on more than 0.01 of the contributions of j and penalizes it otherwise. The value 0.01 is a subjective choice that was made order obtain a prcorder that reveals some interesting structure. Values too large or too small lead very sparse or very dense preorders, both of which offer little opportunity to draw conclusions.
For this instance of the preordering problem, the optimal solution value is P(c) 11.875 and optimal solution is depicted in Figure 9 in the appendix. It is found by our ILP algorithm in 4.9s. The upper bound is B(c) = 15.017, which results in a transitivity index T(c) 0.791. In the visualization of the preorder in Figure 9, nodes are arranged in layers and all ares are directed from left to right. The further a node is to the left, the more the corresponding account reacts to others. The further a node is the right, the more reactions the corresponding account gets from others. One can see that accounts react more to accounts from members of the same political party (Table 2 in the appendix). There are two layers with particularly
12

---

Published in Transactions on Machine Learning Research (01/2026)
many nodes. This is expected dicuts are transitive (cf. Section 4.1). However, there are many nodes not contained in the two large layers (i.e., the optimal solution is not close to a dieut). This is an indication that the interactions exhibit non-trivial transitivity. The node with the most incoming ares (i.e., the account that gets the most reactions) is that of Kevin McCarthy (labeled with a in Figure 9), the Republican minority leader in the House of Representatives of the 117th US Congress. There is cluster of three accounts that is isolated from the rest (labeled with in Figure 9). These accounts belong to Tom Carper, Chris Coons and Lisa Blunt Rochester, who are the three Members of Congress from Delaware. The node labeled with in Figure 9 corresponds to the account of Bernie Sanders, who is party independent member and thus expected to have fewer incoming arcs. Overall, the preorder exhibits few clusters containing more than one account. This is expected because a cluster indicates that accounts within the cluster react to one another and that all accounts in this cluster react to and receive reactions from the same accounts outside this cluster, which is rare.
If we require the preorder to be symmetric (i.e., an equivalence relation/chustering). the optimal value is 5.256. This value being much smaller than P(c) 11.875 suggests that preorders are better fit to this network than equivalence relations.
6 Conclusion
The NP-hard preordering problem is both joint relaxation and hybrid of the clique partitioning problem, from which the symmetry constraint is dropped, and the partial ordering problem, from which the antisym- metry constraint is dropped. A 4-approximation, computable in linear time, is given by the maximum dicut of the subgraph of all ares with a positive value. Complementary to a local search algorithm by Böcker et al. (2009) that we call greedy arc fization, heuristics that we call greedy arc insertion and greedy moving are defined analogously to algorithms known for clustering. The IT.P formulation (3) of the preordering problem tightened by odd closed walk inequalities that define facets of the preordering polytope.
In an application of the preordering problem and the algorithms described above to the task of jointly clustering and ordering the accounts of the social networks published by Fink et al. (2023) and Leskovec & Mcauley (2012), we observe qualitatively that preorders output by the algorithms differ from equivalence relations found by clustering, partial orders found by partial ordering, and preorders found by successive clustering and partial ordering. In addition, we observe quantitatively that high-quality solutions are found in practice by greedy are fixation despite not providing any approximation guarantee. Alternatively, first constructing 4-approximation in the form of a dicut and then performing a local search by greedy are insertion initialized with the dicut also finds high-quality solutions. Comparing upper and lower bounds, we observe that substantial fraction of the LP gap is closed by adding odd closed walk inequalities.
Broader Impact Statement
This paper presents work whose goal is to advance the field of machine learning. The algorithms we introduce can be applied to social networks, including networks of individuals. They output relations that are transitive. The assumption that social network is transitive simplifies and possibly contradicts reality. Working with this assumption is potentially roversill In particular, the algorithms we deline can be applied to identify the part of relation on a social network that is not transitive. This can potentially serve as a basis for influencing a social network to become more or less transitive, which can have ethical implications.
References
Ahmed Abbas and Paul Swoboda. ClusterFuG: Clustering Fully connected Graphs by Multicut. In JCML, 2023. URL https://proceedings. www...prre//..../. w2taa//bs22/bbbba2aaaa. abbas23a.
Amit Aflalo, Shai Bagon, Tamar Kashti, and Yonina Eldar. DeepCut: Unsupervised Segmentation using
Graph Neural Networks Clustering. In ICCVW, 2023. doi: 1L110//CCCWW0733.2222000000
Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Fair Correlation Clustering. Tn AISTATS, 2020. URL https::/proceedingss mlr, www.a........leieee pwwps//1ss///eepppp/ https//vv1///aaaaaaaaae
13

---

Published in Transactions on Machine Learning Research (01/2026)
Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering, Journal of the ACM, 55(5):1-22 27, 2008. doi: 10.145//4111999441551..
Juan A Aledo, José A Gámez, and Alejandro Rosete. Approaching rank aggregation problems by using evolution strategies: The case of the optimal bucket order problem. European Journal of Operational Research, 270(3))982-998 2018. doi: 10.10166/j.eor:2018.00 201........................
Juan A Aledo, José A Gámez, and Alejandro Rosete. A highly scalable algorithm for weak rankings aggre- gation. Information Sciences, 570:144-171, 2021. doi: 10.1016//..ms.202..00 04.0444.............
Yoram Bachrach, Pushmeet Kohli, Vladimir Kolmogorov, and Morteza Zadinoghaddam. Optimal Coalition Structure Generation in Cooperative Graph Games. In AAAI, 2013. doi: 10.1609/aaee vitaa..2771..880
Alberto Bailoni, Constantin Pape, Nathan Hütsch, Steffen Wolf, Thorsten Beier, Anna Kreshuk, and Fred A. Hamprecht. GASP, generalized framework for agglomerative clustering of signed graphs and its appli- cation to Instance Segmentation. In CVPR, 2022. doi: 10.1109/CV 277F556888.022201112
Hans-Jürgen Bandelt, Maarten Oosten, Jeroen HGC Rutten, and Frits CR Spieksma. Lifting theorems and facet charactorization for class of clique partitioning incqualitics. Operations Research Letters, 24(5): 235-243, 1999. doi: 10.1016/S0167-100 (0.001///0000733377999)002222222
Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation Clustering, Machine learning, 56:89 113, 2004. doi: 10.1023/BBa.
Amotz Bar-Noy and Michael Lampis. Online maximum directed cut. Journal of Combinatorial Optimization, 24:52-64 64, 2012. doi: 10.1007/s10688---00008811
Thorsten Beier, Fred A Hamprecht, and Jörg H Kappes. Fusion moves for correlation clustering, In CVPR, 2015. doi: CtV09//CPR.1515.0
Sebastian Böcker, Sebastian Briesemeister, and Gunnar W Klau. On optimal comparability editing with ap- plications to molecular diagnostics. BMC Bioinformatics, 10:1 9, 2009. doi: 10.1188/171-22000-0001--33
Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Gorke, Martin Hoefer, Zoran Nikoloski, and Dorothea Wagner. On Modularity Clustering. IEEE Transactions on Knowledge and Data Engineering, 20(2):172- 188, 2008. doi: 10.1109/KKDE.207..0
Josu Ceberio, Alexander Mendiburu, and Jose A Lozano. The linear ordering problem revisited. European Journal of Operational Research, 241(3):686-66) (6116666666666,6 2015. doi: 20.01//...jor.2144......
Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information.
Journal of Computer and System Sciences, 71(3):360 383, 2005. doi: 11110/6/ijcss.20041000.00..
Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev. Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs. In STOC, 2015. doi: (T.45//77463992277
Sunil Chopra and Mendu R Rao. Facets of the k- k-partition polytope. Discrete Applied Mathematics, 61(1): 27-48, 1995. doi:
Vincent Cohen-Addar Euiwoong Lee, and Alantha Newmnn. Correlation Clustering with Sherali-Adams. In FOCS, 2022. doi: 10.1109/FOCS54455.. 20......2200006...
Erik D. Demaine, Dotan Emanuel, Amos Fiat, and Nicole Immorlica. Correlation clustering in general weighted graphs. Theoretical Computer Science, (2-3):1122-187, 2006. doi: t0.10016/..ts..200005...
Michel Deza, Martin Grötschel, and Monique Laurent. Complete descriptions of small multicut polytopes. In P. Gritzman and B. Sturmfels (ods.), Applied geometry and discrete mathematics, number 4 in DIMACS series in discrete mathenatics and theoretical computer science, pp. 221-2522 AMS, 1991. doi: 10.1090/ dimacs/004.
14

---

Published in Transactions on Machine Learning Research (01/2026)
Michel Deza, Martin Grötschel, and Monique Laurent. Clique- Web Facets for Multicut Polytopes. Mothe-
17.4.981. malics of Operalions Research, 114000011- 1992. doi: 10. 1..44117771
Jean-Paul Doignon and Samuel Fiorini. Facets of the weak order polytope derived from the induced partition
projection. STAM journal on discrete mathematics, 15(1):112-12) 2001. doi: 10.1137 (18895488110369995
Jean-Paul Doignon and Selim Rexhep, Primary facets of order polytopes. Journal of Mathematical Psychol- 0gy, 75:231-245 -225, 2016. doi: 10.1006/..mp.2216.07.00
John Ellson, Emden R. Gansner, Eleftherios Koutsofias, Stephen C. North, and Gordon Woodhull, Graphviz and dynagraph - static and dynamic graph drawing tools. In Michael Jünger and Petra Mutzel (eds.), 6.
Gruph Drawing Software, pp. 127 148. Springer, 2004. doi:
Dotan Emanuel and Amos Fiat. Correlation Clustering - Minimizing Disagroements on Arbitrary Weighted
Graphs. In ESA, 2003. doi: 00.007799669--54--396666 21.
Christian G Fink, Kelly Fullin, Guillermo Guticrrez, Nathan Omodt, Sydney Zinnecker, Gina Sprint, and Sean McCulloch. A centrality measure for quantifying spread on weighted, directed networks. Physica A: Statistical Mechanics and its Applications, 626(129083), 2023. doi: p..1066j.physa.20000 2003.22983......
Samuel Fiorini. A combinatorial study of partial order polytopes. Europenn Journal of Combinatorics, 24 (2):149 159, 2003, doi: (0.0016/00195-669((00
Samuel Fiorini. 0, 1/2-Cuts and the Linear Ordering Problem: Surfaces That Define Facets. STAM Journal on Discrete Mathematics, 20(4):893 912, 2006.
Samuel Fiorini and Peter C Fishburn. Weak order polytopes. Discrete Mathematics, 275(1-3):111-127, 2004. doi: 110010//00022-555(3300000000
Aristides Gionis, Heikki Mannila, Kai Puolamäki, and Antti Ukkonen. Algorithms for discovering bucket orders from data. In KDD, 2006. doi: 10.1145/1150402215546..
Martin Grötschel and Yoshiko Wakabayashi. A cutting plane algorithm for clustcring problem. Mothe- matical Programming, 45(1-3):59 96, 1989. doi: 10.5555/31 11155/3311255.512888888
Martin Grötschel and Yoshiko Wakabayashi. Composition of Facets of the Clique Partitioning Polytope. Rainer Bodendiek and Rudolf Henn (eds.). Topics in Combinatorics and Graph Theory: Essays in Honour 31.
of Gerhard Ringel, pp. 271-284 Physica, 1990a. doi: 1110077977--3362-466000-
Martin Grötschel and Yoshiko Wakabayashi. Facets of the clique partitioning polytope. Mathematical Programming, 47:367-387, 1990b. doi: 10.1007/BF01580070
Martin Grötschel, László Lovész, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:169-197, 1981. doi: 10.1007/BF02579277
Martin Grötschel, Michael Jünger, and Gerhard Reinelt. A Cutting Plane Algorithm for the Linear Ordering Problem. Operations Research, (2(6)) 1984. doi: 10.
Maria Angela Gurgel. Poliedros de grafos transitivos. PhD thesis, Universidade de São Paulo, 1992. doi:
Maria Angela Gurgel and Yoshiko Wakabayashi. Adjacency of vertices of the complete pre-order polytope. Discrete Mothematics,
172, 1997. doi:
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL https: http://ww..bbb// com.
Eran Halperin and Uri Zwick. Combinatorial approximation algorithms for the maximum directed cut problem. In SODA, 2001. doi: 055555/36541133651
Olivier Hudry. Na-haeds results for the aggregation of linear orders into median orders. Annols of Operations Research, 163:63 88, 2008. doi: 10.1007/510479-000-053
15

---

Published in Transactions on Machine Learning Research (01/2026)
Olivier Hudry. On the computation of median linear orders, of median complete preorders and of median weak orders. Mathematical Social Sciences, 64(1):2-10, 2012. doi:
22200.06.004..4 .06.004.
Juby Jacob, Marcel Jentsch, Dennis Kostka, Stefan Bentink, and Rainer Spang. Detecting hierarchical structure in molecular characteristies of discase using transitive approximations of directed graphs. Bioin- formatics, 2477)9995-1001 2008.
Mateusz Maria Jurewiez, Graham W Taylor, and Leon Dercaynski. The Catalog Problem: Clustering and Or- dering Variable-Sized Sets. In ICML, 2023. URL https://proceed/i mlr, pptess/v002jrrrric222333 html.
Sanchit Kalhan, Konstantin Makarychev, and Timothy Zhou. Correlation clustering with local ob- jectives. NewrIPS, 2019. URL https://procedding nwwrinuurpp... wwtpcccppppppiieeee /ttpp////pppeeieee/p/p////////// 7860772065500377/haa044666666000
pdf.
Richard M. Karp. Reducibility among Combinatorial Problems, pp. 85-103. Springer US, 1972. doi: 10.
1007/978-1144644-2000
Marek Karpinski and Warren Schudy. Faster algorithms for feedback are set tournament, Kemeny rank aggregation and betweennoss tournament. In International Symposium Algorithms and Computation (ISAAC), 2010. doi: 00.00779978-3-642-177111
Margret Keuper, Evgeny Levinkov, Nicolas Bonneel, Guillaune Lavoué, Thomas Brox, and Bjoern Andres. Efficient decomposition of image and mesh graphs by lifted multicuts. In JCCV, 2015. doi: 10.1109/ICCV. 2015.204.
Philip N Klein, Claire Mathieu, and Hang Zhou. Correlation clustering and two-edge-connectedd augmentation for planar graphs. Algorithmica, 85(10):3024 3057, 2023.
Jure Leskovec and Julian Mcauley. Learning to discover social circles in ego networks.
In NewrIPS, 2012. URL
wwttsseerrrscpppppeeeeeeeeeeeeee cc/paper hac//pppr_fiiless_eeeeeeeeepeeee wwwes/paaeee//ee / 15314f00669949111100006666eeee pdf.
Adam N. Letchford and Michael M. Sørensen. New facets of the clique partitioning polytope. Operations Research Letters, 59:107242, 2025. doi: 10.1016/..0112225.11722
Rafael Martí and Gerhard Reinelt. The linear ordering problem: enact and heuristic methods in combinatorial oplimizalion. Springer, 2011. doi: 10.10779978-3--4221677-3
Rudolf Müller. On the partial order polytope of digraph. Mathematical Programming, 73(1):31 1996. doi: 10. (1007/BFF2500097
Maarten Oosten, Jeroen HGC Rutten, and Frits CR Spieksma. The elique partitioning problem: facets and patching facets. Networks: An International Journal, 38(4):209 226, 2001. doi: 10.1002/nett10000
Gregory Pulco and Olgica Milenkovic. Correlation clustering and biclustoring with locally bounded crrors. In ICML, 2016. URL https: https::/proceeedings. wttp://www....eee/////ee/ooooooo html.
Frans Schalekamp and Anke Zuylen. Rank aggregation: Together we' we're strong. In Workshop on Algoritlm Engineering and Experiments (ALENEX), 2009. doi: 10.1187/19771161177888.
Michael M Sørensen. A note on wlbque-web facets for multicut polytopes. Mathematics of Operations Research, 27(4):740-742, 2002. doi: 10. 20177mmorr.27.4.74000
Chaitanya Swamyy Correlation clustering: maximizing agreements via semidefinite programming, In SODA, 2004. doi: 00.5555/982792.9888
Nate Veldt. Correlation clustering via strong triadic closure labeling: Fast approximation algorithms and practical lower bounds. In ICML, 2022. URL https://proceedingg.nt mlr pttpppeee////////aa.222222 html.
16

---

Published in Transactions on Machine Learning Research (01/2026)
Nate Veldt, David F Gleich, and Anthony Wirth. A correlation clustering framework for community detec- tion. In WWW, 2018. doi: 10.1165/3178876331661000
Yoshiko Wakabayashi. The complexity of computing medians of relations. Resenhas do Institulo de Matemática Estatística da Universidade de São Paulo, 3(3):323-344 -449, 1998.
Mathias Weller, Christian Komusiewicz, Rolf Niedermeier, and Johannes Uhlmann. On making directed graphs transitive. Journal of Compuler and System Sciences, 78(2):559 574, 2012. doi: 10.1016/j.jcss.
2011.07.001.
Julian Yarkony, Alexander Ihler, and Charless C Fowlkes. Fast planar correlation clustering for image segmentation. In ECCV, 2012. doi:
3-777783-662-3338--3333 41.
David Zuckerman. Linear Degree Extractors and the Inapproximabiiity of Max Clique and Chromatic Number. Theory of Computing, 3(1):103-125) 2007. doi: 20000///TC.2000.00033303
A Appendix
A.1 Discussion of reflexivity
The feasible solutions to the ILP formulation (1)-(3 of the preordering problem preciscly the character- istic vectors of the reflerive reductions of the preorders on V. There are two main reasons for preference of this formulation over a version that would use the characteristic vectors of the preorders directly.
Firstly, we are interested in approximating solutions to the proordering problem. The quality of an approx- imation algorithm is usually defined as the maximum multiplicatiiee error this algorithm commits over all instances of the problem. By assigning values also to the reflexive pairs and requiring a solution A V2 to be reflexive and transitive, the total value of every solution includes all values of transitive pairs. In particular, changing the values of the reflexive pairs merely shifts the values of all solutions by the same amount. Shifting the values of all solutions by a constant amount does not change the set of optimal so- lutions. However, it affects the ratio of values of solutions and thus how well one solution approximates another solution. Restricting our attention to the reflexive reductions preorders is further justified by a lemma proven by Wakabayashi (1998) stating that the decision version of the problem is NP-complete for the reflexive version if and only if it NP-complete for the irreflexive version.
Secondly, the convex hull of the characteristic vectors of transitive and reflexive relations is polytope contained in a dimennsill subspace of gV² (namely the subspace defined by the equalities za 1 for E V). By restricting the polytope to the space R2/2 (i.c., the convex hull of the fcasible solutions to the ILP (1) (3)), this complication is avoided.
A.2 Derandomization of the max-dicut algorithm
It is well known that the randomized 4-approximation algorithm for max-dicut can be derandomized (Halperin & Zwick, 2001; Bar-Noy & Lampis, 2012). For completeness, we reproduce the derandomiza- tion due to Theorem 3 Bar-Noy & Lampis (2012) below. Additionally, we show that this algorithm can be implemented run in O(IV)).
Let G (V, F)) be directed graph with edge weights w E Rzo- Tn the following, let S, V with S = 0. They define the partial dicut {ij E E' i S.j E S). We denote the expected value of the dicut that is obtained by randomly assigning elements in V \ (S S) to either S or S by Egg- It holds that
Egs
Σ
Wif +
Σ
Wij
2
BEE: iESJES
UEE FHES. JEV(SSU)
Σ
Wij
Σ
Wij
2
4
MEBUES, (SUS)
ijE::
(SUB)
17

---

Published in Transactions on Machine Learning Research (01/2026)
For l E (SSUS)), let on denote the change in the expected value after assigning is to S. A simple calculation yields
Wkj
Wik
=
Egs
2
2
jE
FE tEE
KjEE
E
Wkj
Σ
Wik
4
4
JEV(SU(E) KjEE
(EV((SU())SS); ikE
and
ESSUiR]
Ess -9
If gi is non-negative, assigning to S does not decrease the expected value; otherwise, assigning & to S does not decrease the expected value.
When assigning all elements randomly, the expected value is Egs = Eijer 4 By iteratively assigning elements & V \ (SUS) Š) to S 3 based on the sign of gks a dicut is obtained with value least Esa and, therefore, a 4-approximation to the max-dicut problem.
Algorithm implements this algorithm with two additional improvements: Firstly, in each iteration, the clement & E (SU S) for which Igxl is greatest is selected. This maximizes the expected value after assigning k. Secondly, the values Instead, they are computed once for S = S = 9, and after each iteration, these values are updated. With this, each itcration runs in time O(VV) instead of O((V?) that would be required compute all values according to the formula above.
for E V \ (S U) are not computed from scratch in each iteration.
A.3 Example instance
In this section we describe an instance of the preordering problem where the greedy are fixation algorithm (cf. Section 4.2) does not achieve a 4-approximation. In contrast Figure 4, on this instance no ties occur throughout the execution of the algorithm and thus unfavorable tic-breaking. The are values of such an instance given by the matrix below.
0
9976
20009
-10060
-20099
10033
-
-9908
0
10025
- 199665
9996
6
10049
-10048
10018
19971
20025
19943
-9914
10076
19984
10014
9950
-91
-99988
10021
0
19933
20025
10086
9947
-00332
10035
This matrix was generated by uniformly sampling values from (-2,-1,0,1,2) in order to obtain difficult instance and then scaling these values by 10000 and adding uniformly sampled noise from {-100,.... 100}
in order to obtain unique values. The optimal preorder has objective value of 50130. The preorder found by the greedy are fixation algorithm has an objective value 10280, yiclding an approximation ratio
of 4.88 > 4. The greedy are fixation algorithm performs the following sequence of fixations: I = 0.
((,,4) = 0, T{0,1} = 0, F(5.2] = 0, T33.1) = 0, (s..1) = 0, o = 0, T(3,4] = 0, x = 0, I[5.0) = O.
x[s.3} 0, x[2.1] 0, 4[2.5} = 1, 4{4.2] = 0, 211.3) = 1, 213,0) = 0, 2[1,5) = 1, I(4.1) = 0, z(1,0) =
(224)) 0, 1(455) 1(0.3 0, F[2.0] 1, 2(0.5) 1, 2(12) 1, F 1, I(2.3) 1. ((35))
(1.4) 1, 214.0)
=1. =1.Each fixation the unique best fixation and no ties occur.
18

---

Published in Transactions on Machine Learning Research (01/2026)
A.4 Preorder of the 117th US Congress
Party
Democrats
Republicans
Other
Democrats
409
49
0
Republicans
53
531
0
Other
18
3
0
Table 2: The number in row and column B the number of ares the preorder depicted Figure 9 from members of party to party B.
19

---

Published in Transactions on Machine Learning Research (01/2026)
Figure 9: Preorder of Twitter accounts of members of the 117th US Congress. Each node corresponds to cluster of accounts and the size of the node is proportional to the size of the cluster (most clusters contain just single account.). The color of the node corresponds to the party membership (Democrats: blue, Republicans: red, Other: gray), where clusters with mixed membership have a mixed color. The depicted edges are those of the transitive reduction of the partial order on the clusterings. The layout is computed using the dot algorithm implemented Graphviz (Ellson et al., 2004).
20


Reviews:
[{"review_id": "YN5mTYgkZF", "reviewer": "Reviewer_1iLa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduced and implemented algorithms for the preordering problem.\n\nStrengths:\n- In-depth with proof\n\nWeaknesses:\n- Crowded figures\n- No comparison of all algorithms together", "claims_and_evidence_yn": "Yes", "claims_explanation": "Each theorem has a proof and there are empirical results.", "audience_yn": "Yes", "audience_explanation": "This paper shows the efficiency of the algorithms introduced, which can lead to further discussion.", "requested_changes": "- Figures 6 and 9 are cluttered, maybe move them to appendix\n- Maybe include a table with the number of optimal solutions found for all algorithms (5.1.2) \n- Labels on figure 6", "broader_impact_concerns": "There are no broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Xn6Yujr5XO", "reviewer": "Reviewer_Msff", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposed algorithms to resolve the preordering problem. The paper detailed the proposed algorithms and evaluated them on the ego networks of Twitter and Google+. The results show the algorithms could solve the problem effectively. \n\nStrengths\n1. The algorithms are well-written, and the experiments on the proposed algorithms are comprehensive. \n2. The ablation study of the combination of algorithms are good.\n\nWeaknesses\n\n1. There is no comparison to others' work; how do the algorithms compare to the state-of-the-art methods?\n2. It is hard to connect the paper to the applications, e.g. in the social network, why solving preordering problems is important, what is the consequence if the accuracy is not high enough. Those connections could further strengthen the paper.", "claims_and_evidence_yn": "Yes", "claims_explanation": "N/A", "audience_yn": "Yes", "audience_explanation": "Yes, solving social network problem is important in the machine learning, especially large-scale network and has to solve it with a limited time.", "requested_changes": "1. See weaknesses.  Especially, the comparison to other works. \n2. Is it possible to evaluate the algorithms' performance without time constraints? My concern is that is it possible one algorithm just can not find a good solution in the short time but it could lead to a better solution later.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Szgs54p2Ta", "reviewer": "Reviewer_D6Ey", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies algorithms for the maximum value preordering problem. The authors present (a) a simple randomization-based lower bound with a 4-approximation guarantee, (b) an LP-based relaxation strengthened with odd closed walk inequalities to provide tighter upper bounds, and (c) several heuristic approaches, including a previously published baseline and two new greedy variants. The paper includes the necessary proofs, such as the relationship between preorders and dicuts, and provides clear arguments for the approximation guarantees. Beyond the theoretical contributions, the paper offers detailed empirical evaluation on real-world social network data from Google+, Twitter ego networks, and the Twitter interaction network of members of the 117th U.S. Congress, comparing runtimes and solution quality across algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The claims are supported by both theoretical proofs and empirical results. The paper provides clear arguments for the 4-approximation guarantee and for the relationship between preorders and dicuts, and it cites prior hardness results appropriately. The empirical evaluation on large social network datasets (Twitter, Google+, U.S. Congress) is detailed and shows that the heuristics perform well and that the LP relaxation with odd-closed walk inequalities improves the quality of the upper bound.", "audience_yn": "Yes", "audience_explanation": "The paper systematically analyzes several algorithms for the maximum value preordering problem including a randomized algorithm for a lower bound and an approximate upper bound using linear programming, apart from 3 greedy algorithms including 2 proposed ones. These algorithms are described in detail with theoretical evidence where needed. Additionally, the paper provides empirical evidence about performance and runtime for each of the methods and several combinations of the methods as well. The depth of analysis and detailed explanation of the method makes it an interesting paper for TMLR's audience subject to the requested changes being made.", "requested_changes": "Changes required for acceptance:\n- While the paper provides distribution plots (e.g., Figure 5), the results section would benefit from a clear summary table reporting average/median objective values, transitivity indices, and runtimes across all ego networks. This would make the empirical comparison between preorder, clustering, and partial order easier to interpret at a glance, and also support claims such as \"The objective values are highest for the preordering problem and lowest for the clustering problem\".\n- In section 5.1.1, it would be good to quantify the amount of disagreement between the solutions of each method. The general messaging of the paper based on Figure 6, is that preorder has less disagreements than clustering and partial ordering, but concrete evidence would give more evidence to support this claim.\n- In section 5.1.2, report quantitative metrics in addition to the results shown in Figure 7. The data in the plot does provide some evidence but the granularity of the figure and how close the different methods makes it challenging to directly interpret the data.\n- In section 5.2, a) justify why 0.01 is a fair choice (eg. by analyzing mean/median proportion of interactions, 10th percentile, etc.) for penalizing arcs, b) quantify how often party members are connected to other members of their/other parties to support statements such as \"one can see that accounts react more to accounts from members of the same political party\", c) explain why it is reasonable for most clusters to only contain one account in the preorder\n\nMinor changes:\n- For consistency in metrics across the paper, it would be good to only report the performance normalized by |E| (eg. table 1)\n- Define \"reaction likelihood\" in section 5.2", "broader_impact_concerns": "The broader impact statement is generally sufficient, but one point worth emphasizing is the risk of misinterpretation when applying these methods to political or social datasets. Enforcing preorder structures can exaggerate hierarchy, partisanship, or suggest influence chains that are not truly causal. It would help if the authors clearly state that preorders are a modeling assumption rather than ground-truth evidence about social interactions.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)