Technical Summary: Partial Optimality in the Preordering Problem

1. Problem Statement

The preordering problem is a combinatorial optimization task defined on a finite set $V$ with associated values $c_{ab} \in \mathbb{R}$ for every ordered pair $ab \in V^2$ ($a \neq b$). The objective is to find a preorder $\lesssim$ on $V$ (a reflexive and transitive binary relation) that maximizes the sum of values $\sum_{a \lesssim b, a \neq b} c_{ab}$.

This problem generalizes both clustering (where solutions are symmetric preorders/equivalence relations) and partial ordering (where solutions are anti-symmetric preorders). A preorder's symmetric subset defines a clustering, while its anti-symmetric subset defines a partial order over these clusters. The problem is known to be NP-hard, even when values are restricted to $\{-1, 1\}$.

The paper addresses the problem of partial optimality: efficiently deciding, for a subset of pairs $ab$, whether $a \lesssim b$ or $a \not\lesssim b$ holds in every optimal preorder, without necessarily solving the entire NP-hard instance.

2. Methodology

The authors build upon the framework of improving maps, a technique introduced by Shekhovtsov (2013, 2014) and applied by Shekhovtsov et al. (2015). The core idea is to construct maps $\sigma: X_V \to X_V$ from the set of feasible preorders to itself. If a map is "improving" (i.e., it does not decrease the objective function value for any feasible solution), then an optimal solution exists within the image of the map.

The methodology proceeds in three stages:

2.1 Constraint Propagation and Partial Characterizations

The authors define a partial characteristic function $\tilde{x}$, which assigns values $\{0, 1\}$ to a subset of pairs and $\ast$ (undecided) to others. They introduce the concept of maximally specific partial functions, where all pairs that are forced to be 0 or 1 by transitivity constraints are explicitly decided. They provide an efficient algorithm to compute the closure ($cl_V \tilde{x}$) of any partial function, ensuring that all implied constraints are propagated.

2.2 Partial Optimality Conditions

The paper derives new sufficient conditions under which specific pairs can be fixed to 0 or 1. These conditions are verified by constructing specific improving maps:

• Cut Conditions (Theorem 1 & Corollary 2): Based on elementary dicut maps ($\sigma_{\delta(U, V \setminus U)}$). These maps set all edges crossing a specific cut $(U, V \setminus U)$ to 0. Theorem 1 provides a condition involving the value $c_{ij}$ and the sum of positive values in the cut to guarantee that $x_{ij}=0$ in an optimal solution. Corollary 2 offers a simpler, efficiently decidable specialization.
• Join Conditions (Theorem 2): Based on elementary join maps ($\sigma_{ij}$) composed with dicut maps. These maps force $x_{ij}=1$ if certain transitivity paths exist. Theorem 2 establishes a condition where setting $x_{ij}=1$ is optimal, involving a comparison between $c_{ij}$ and the sum of negative values in specific path sets.
• Fixation Conditions (Theorem 3): A more general condition that fixes variables to 0 or 1 by comparing lower and upper bounds of the objective function on restricted subspaces. This theorem subsumes previous conditions (Corollaries 4 and 5) and allows for fixing variables even when global bounds are not tight, provided specific local bounds and map properties hold.

2.3 Algorithms

The authors propose efficient algorithms to apply these conditions:

• Cut Conditions: Solved via minimum $ij$-cut problems (max-flow), specifically using the push-relabel algorithm.
• Join Conditions: Formulated as a three-label energy minimization problem, solved heuristically using $\alpha\beta$-swap moves (Boykov et al., 2001).
• Fixation Conditions: Utilize approximate bounds derived from local search algorithms (greedy arc fixation/insertion) and edge-disjoint triple packings to estimate objective function bounds. Tight bounds are computed efficiently in specific cases where a feasible solution $x^+$ is known.

3. Key Contributions

1. New Partial Optimality Conditions: The paper proves new conditions (Theorems 1, 2, and 3) that generalize and subsume existing conditions from Böcker et al. (2009) and Weller et al. (2012).
2. Efficient Verification Algorithms: The authors provide polynomial-time algorithms to decide these conditions, leveraging max-flow, reachability analysis, and energy minimization heuristics.
3. Constraint Propagation Framework: A rigorous definition of maximally specific partial characteristic functions and an efficient closure algorithm to propagate constraints.
4. Empirical Validation: Extensive experiments on synthetic data and real-world social networks (Twitter and Google+).

4. Experimental Results

The algorithms were evaluated on synthetic instances and real social network ego networks.

• Synthetic Data:

  • Cut Conditions: Theorem 1 consistently fixes more variables to zero than Corollary 2 but requires significantly more computation time (two orders of magnitude).
  • Join Conditions: All join conditions are effective. Corollary 5 ($b=1$) fixes the most variables to one.
  • Joint Application: Applying conditions jointly (Cut + Join + Fixation) significantly increases the fraction of fixed variables. For "easy" instances (low noise parameter $\alpha$), all variables are fixed; for "hard" instances, fewer are fixed, but the fraction remains higher than with prior methods.
  • Runtime: The joint application scales polynomially with the number of vertices $|V|$ (observed exponents between 4.5 and 5.1).

• Real-World Data (Twitter/Google+):

  • The new conditions (Theorem 1 and Theorem 3) fix significantly more variables to zero than the state-of-the-art conditions from Böcker et al. (2009).
  • Specifically, Theorem 1 fixed a median of 29.6% of variables to zero compared to 16.7% for Corollary 2 on Twitter data.
  • While the runtime for the new conditions is longer, it remains polynomial and practical for the tested dataset sizes ($|V| \le 250$).

5. Significance and Claims

The paper claims that the proposed conditions and algorithms represent a state-of-the-art advancement in solving the preordering problem partially.

• Effectiveness: The primary contribution is the increased ability to decide that $a \not\lesssim b$ (fixing variables to 0) in an optimal preorder. The authors note that while fixing variables to 1 is also improved, the most significant gain is in identifying non-precedence relations.
• Generality: The conditions are shown to be strict generalizations of previous work, capable of fixing variables in cases where prior conditions (like Corollary 4 or 5) fail.
• Practicality: The methods terminate in polynomial time and provide partial solutions that are guaranteed to be extendable to an optimal solution. This allows for the reduction of the search space for exact solvers or the provision of high-quality partial solutions for applications in bioinformatics and social network analysis.

The authors maintain a modest tone, acknowledging that while the conditions improve the fraction of fixed variables, the problem remains NP-hard, and the algorithms are designed for partial resolution rather than solving the full instance exactly in all cases.