# Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization:
Cardinality, Minimum, Covering, and More

Fanchen Bu  Hyeonsoo Jo  Soo Yong Lee  Sungsoo Ahn  Kijung Shin

###### Abstract

Combinatorial optimization (CO) is naturally discrete, making machine learning
based on differentiable optimization inapplicable. Karalias & Loukas (2020)
adapted the probabilistic method to incorporate CO into differentiable
optimization. Their work ignited the research on unsupervised learning for CO,
composed of two main components: probabilistic objectives and derandomization.
However, each component confronts unique challenges. First, deriving
objectives under various conditions (e.g., cardinality constraints and
minimum) is nontrivial. Second, the derandomization process is underexplored,
and the existing derandomization methods are either random sampling or naive
rounding. In this work, we aim to tackle prevalent (i.e., commonly involved)
conditions in unsupervised CO. First, we concretize the targets for objective
construction and derandomization with theoretical justification. Then, for
various conditions commonly involved in different CO problems, we derive
nontrivial objectives and derandomization to meet the targets. Finally, we
apply the derivations to various CO problems. Via extensive experiments on
synthetic and real-world graphs, we validate the correctness of our
derivations and show our empirical superiority w.r.t. both optimization
quality and speed.

##  1 Introduction

Combinatorial optimization (CO) problems are discrete by their nature. Machine
learning methods are based on differentiable optimization (e.g., gradient
descent), and applying them to CO is non-trivial. In their pioneering work,
Karalias & Loukas (2020) adapted the probabilistic method (Erdős & Spencer,
1974; Alon & Spencer, 2016) to incorporate discrete CO problems into
differentiable optimization. Specifically, they proposed to evaluate CO
objectives on a distribution of discrete choices (i.e., in a probabilistic
manner), allowing for the differentiable optimization-based ML techniques to
be applied to CO problems. This ignited the line of research on unsupervised
(i.e., not supervised by solutions) learning for combinatorial optimization
(UL4CO).

There are two components in UL4CO: (1) construction of probabilistic
objectives and (2) derandomization to obtain the final discrete solutions.
However, the prior works on UL4CO share multiple limitations. First, although
some desirable properties of probabilistic objectives (e.g., desirable
objectives should be differentiable and align well with the original discrete
objectives) have been proposed, how to derive objectives satisfying such
properties is still unclear. At the same time, the derandomization process is
underexplored, without many practical techniques or theoretical discussions.
Specifically, the existing derandomization methods are either random sampling
or naive rounding. Random sampling, by its nature, may cost us a large number
of samplings (and good luck) to have good results. For naive rounding, the
performance may highly depend on the order of rounding and end up with
mediocre solutions. They only guarantee, at best, derandomized solutions are
no worse than the given continuous solutions w.r.t. the corresponding
probabilistic objectives. However, how to obtain stronger guarantees in an
efficient way has been an open problem.

Motivated by the limitations, in this work, we focus on objectives and
constraints that have not been systematically handled within the UL4CO
framework and are commonly involved in various CO problems. We study and
propose UCom2 (Usupervised Combinatorial Optimization Under Commonly-involved
Conditions). Specifically, our contributions are four-fold.

  * •

We concretize the targets for objective construction and derandomization with
theoretical justification (Sec. 3). We theoretically show that probabilistic
objectives that can be rephrased as an expectation are desirable, and propose
a fast and effective derandomization scheme with a quality guarantee stronger
than the existing ones.

  * •

We derive non-trivial objectives and derandomization for various prevalent
conditions to meet the targets (Sec. 4). We focus on conditions that are
mathematically hard to handle but commonly involved in CO problems, e.g.,
cardinality constraints, minimum, and covering.

  * •

We apply our derivations to different CO problems involving such prevalent
conditions (Sec. 5). For each problem, we analyze what conditions are involved
and derive objectives and derandomization by combining our derivations for the
involved conditions.

  * •

We show the empirical superiority of UCom2 via experiments (Sec. 6). Equipped
with our derivations, our method UCom2 achieves better optimization quality
and speed across different CO problems on both synthetic and real-world
graphs, outperforming various baselines.

Reproducibility. The code and datasets are available in the online appendix
(Bu et al., 2024).111https://github.com/ai4co/unsupervised-CO-ucom2

##  2 Preliminaries and Background

###  2.1 Preliminaries

Graphs. A graph $G=(V,E,W)$ is defined by a node set $V$, an edge set $E$, and
edge weights $W:E\to\mathbb{R}$. We let $n=|V|$ denote the number of nodes
(WLOG, $V=[n]\coloneqq\\{1,2,\ldots,n\\}$), and let $m=|E|$ denote the number
of edges.

Combinatorial optimization (CO). We consider CO problems on graphs with
discrete decisions on nodes. Each CO problem can be represented by a tuple
$(f,\mathcal{C},d)$ with (1) an optimization objective
$f:d^{n}\to\mathbb{R}_{+}$, (2) constraints defined by a feasible set
$\mathcal{C}\subseteq d^{n}$, and (3) a set of possible decisions $d$ (on each
$v\in V$). Given decisions $X_{v}\in d$ with $v\in V$, we have a full decision
$X\in d^{n}$.

For each graph $G=(V,E,W)$, we can use the optimization objective function $f$
to evaluate each full decision $X\in d^{n}$ on $G$ by $f(X;G)$, and we aim to
solve $\min_{X\in\mathcal{C}(G)}f(X;G)$. By default, we consider CO problems
with binary decisions (i.e., $d=\\{0,1\\}$).222We will discuss non-binary
cases in Sec. 4.5. Given $X\in\\{0,1\\}^{n}$, we call each node $v$ with
$X_{v}=1$ a chosen node, and call $V_{X}\coloneqq\\{v\in V:X_{v}=1\\}\subseteq
V$ the chosen subset (i.e., the set of chosen nodes).

###  2.2 Background: UL4CO

We shall introduce the background of unsupervised learning for combinatorial
optimization (UL4CO), including the overall pipeline and some existing
ideas/techniques.

####  2.2.1 The UL4CO Pipeline: Erdős Goes Neural

The UL4CO pipeline, Erdős Goes Neural (Karalias & Loukas, 2020), is based on
the probabilistic method (Erdős & Spencer, 1974) with three components:
objective construction, differentiable optimization, and derandomization.

Probabilistic objective construction. The high-level idea is to evaluate
discrete objectives on a distribution of decisions, which accepts continuous
parameterization. Specifically, given a CO problem
$(f:\\{0,1\\}^{n}\to\mathbb{R},\mathcal{C},d=\\{0,1\\})$, we first construct a
penalized objective
$f_{\mathrm{pen}}(X)=f(X)+\beta\mathbb{1}(X\notin\mathcal{C})$ with constraint
coefficient $\beta>0$. Then, a probabilistic objective
$\tilde{f}:[0,1]^{n}\to\mathbb{R}$ accepting probabilistic (and thus
continuous) inputs is constructed such that

$\tilde{f}(p)\geq\mathbb{E}_{X\sim p}f_{\mathrm{pen}}(X)=\mathbb{E}_{X\sim
p}f(X)+\beta\Pr\nolimits_{X\sim p}[X\notin\mathcal{C}].$

We see each $p\in[0,1]^{n}$ as a vector of probabilities, with $p_{v}$’s being
independent Bernoulli variables. Hence, we have $\begin{aligned}
\Pr\nolimits_{p}[X]&=\prod\nolimits_{v\in V_{X}}p_{v}\prod\nolimits_{u\in
V\setminus V_{X}}(1-p_{u}),\\\ \mathbb{E}_{X\sim
p}f(X)&=\sum\nolimits_{X\in\\{0,1\\}^{n}}\Pr\nolimits_{p}[X]f(X),\text{~{}and~{}}\\\
\Pr\nolimits_{X\sim
p}[X\notin\mathcal{C}]&=\sum\nolimits_{X\in\\{0,1\\}^{n}\setminus\mathcal{C}}\Pr\nolimits_{p}[X]=1-\sum\nolimits_{X\in\mathcal{C}}\Pr\nolimits_{p}[X].\end{aligned}$

######  Remark 1.

Assuming independent Bernoulli variables gives simplicity and tractability,
while other ways to model decision distributions, e.g., other distributions
(Karalias et al., 2022) and dependency between variables (Sanokowski et al.,
2023), are potential future directions.

Differentiable optimization. For differentiable optimization, we need to
ensure that $\tilde{f}$ is differentiable (w.r.t. $p$). At this moment, let us
assume we have constructed such a $\tilde{f}$. Then, given a graph $G$, we can
use differentiable optimization (e.g., gradient descent) to obtain optimized
probabilities $p_{\mathrm{o}}$ with (ideally) small
$\tilde{f}(p_{\mathrm{o}};G)$.

Derandomization. Finally, derandomization is used to obtain deterministic full
decisions. For each test instance $G$, the derandomization process transforms
each $p_{\mathrm{o}}\in[0,1]^{n}$ obtained by probabilistic optimization into
a discrete (i.e., deterministic) full decision $X_{p}\in\\{0,1\\}^{n}$.
Karalias & Loukas (2020) showed a quality guarantee of derandomization by
random sampling. See App. B for more details.

####  2.2.2 Local Derandomization

The theoretical quality guarantee by Karalias & Loukas (2020) is obtained by
random sampling, and we may need a large number of samplings (and good luck)
to have a good bound. Wang et al. (2022) further proved a deterministic (i.e.,
not relying on random sampling) quality guarantee by iterative rounding (i.e.,
a series of local derandomization along with a node enumeration). The
principle of iterative rounding involves two concepts: (1) local
derandomization of probabilities $p$ and (2) entry-wise concavity of
probabilistic objective $\tilde{f}$.

Local derandomization. Given $p\in[0,1]^{n}$, $i\in[n]$, and $x\in\\{0,1\\}$,
$\operatorname{der}(i,x;p)\in[0,1]^{n}$ is the result after $p_{i}$ being
locally derandomized as $x$, i.e.,

$\begin{cases}\operatorname{der}(i,x;p)_{i}=x,\\\
\operatorname{der}(i,x;p)_{j}=p_{j},\forall j\neq i.\end{cases}$

Entry-wise concavity. A probabilistic objective $\tilde{f}:[0,1]\to\mathbb{R}$
is entry-wise concave if $\forall p\in[0,1]^{n}$ and $i\in[n]$,

$p_{i}\tilde{f}(\operatorname{der}(i,1;p))+(1-p_{i})\tilde{f}(\operatorname{der}(i,0;p))\leq\tilde{f}(p)$.

Applying a series of local derandomization with an entry-wise concave
objective $\tilde{f}$ does not increase the objective. Notably, Karalias &
Loukas (2020) essentially proposed iterative rounding, and Wang et al. (2022)
first formalized a theoretical guarantee of iterative rounding with the
condition of entry-wise concavity. See App. B for more details.

##  3 Concretizing Targets: What Do We Need?

First, we concretize the targets for objective construction and
derandomization to guide our further derivations.

###  3.1 Good objectives: Expectations are all you need

Good properties. We summarize some known good properties of a probabilistic
objective $\tilde{f}$ (Karalias & Loukas, 2020; Wang et al., 2022): (P1)
$\tilde{f}:[0,1]^{n}\to\mathbb{R}$ accepts continuous inputs $p\in[0,1]^{n}$
(rather than discrete $X\in\\{0,1\\}^{n}$); (P2) $\tilde{f}$ is an upper bound
of the expectation of a penalized objective
$f+\beta\mathbb{1}(X\notin\mathcal{C})$ for some $\beta>0$; (P3) $\tilde{f}$
is differentiable w.r.t. $p$; (P4) $\tilde{f}$ is entry-wise concave w.r.t.
$p$; (P5) $\tilde{f}$ has the same minimum as $f$, i.e.,
$\min_{p}\tilde{f}(p)=\min_{X}f(X)$ and
$\arg\min_{p}\tilde{f}(p)=\arg\min_{X}f(X)$. The property (P5) has been
discussed (Karalias & Loukas, 2020; Karalias et al., 2022; Kollovieh et al.,
2024) but has not been explicitly formalized for UL4CO. With (P5), when we
minimize $\tilde{f}$, we also minimize the original objective $f$, which
avoids meaningless $\tilde{f}$, e.g., a constant function with a very high
value (which satisfies (P1)-(P4) but not (P5)).

######  High-level Target 1 (Good objectives).

Given an optimization objective $f:\\{0,1\\}^{n}\to\mathbb{R}$ and constraints
$X\in\mathcal{C}$, we aim to construct a good probabilistic objective
$\tilde{f}:[0,1]^{n}\to\mathbb{R}$ to satisfy all the good properties
(P1)-(P5).

Below, we show that a specific form of objectives satisfies all the good
properties. First, expectations are all you need, i.e., any probabilistic
objective that is the expectation of any discrete function satisfies
properties (P1), (P3), and (P4).

######  Theorem 1 (Expectations are all you need).

For any $g:\\{0,1\\}^{n}\to\mathbb{R}$, $\tilde{g}:[0,1]^{n}\to\mathbb{R}$
with $\tilde{g}(p)=\mathbb{E}_{X\sim p}g(X)$ is differentiable and entry-wise
concave w.r.t. $p$.

###### Proof.

See App. A for all the proofs. ∎

######  Remark 2.

Differentiability and entry-wise concavity are closed under addition. Hence, a
linear combination of expectations is also differentiable and entry-wise
concave. Also, probabilities are special expectations of indicator functions.
The differentiability of expectation may not hold when $p_{v}$’s are not
independent Bernoulli variables, e.g., when the expectation is taken with
Lovasz extension (Bach et al., 2013).

To further satisfy (P2) and (P5), we only need to find a tight upper bound
(TUB) of a penalized objective.

######  Definition 1 (Tight upper bounds).

Given $g\colon\\{0,1\\}^{n}\to\mathbb{R}$, we say
$\hat{g}\colon\\{0,1\\}^{n}\to\mathbb{R}$ is a tight upper bound (TUB) of $g$,
iff (i.e., if and only if) $\hat{g}(X)\geq g(X),\forall X$ with
$\min_{X}\hat{g}(X)=\min_{X}{g}(X)$ and
$\arg\min_{X}\hat{g}(X)=\arg\min_{X}{g}(X)$, where
$\arg\min_{X}g(X)=\\{X^{*}\colon g(X^{*})=\min_{X}{g}(X)\\}$.

######  Remark 3.

It is easy to see that $\hat{g}=g$ is always a TUB of $g$. When
$g=\mathbb{1}[X\notin\mathcal{C}]$ is an indicator function for the violation
of constraints $X\in\mathcal{C}$, the condition in Def. 1 is equivalent to
$\hat{g}(X)\geq 1,\forall X\notin\mathcal{C}$ and $\hat{g}(X)=0,\forall
X\in\mathcal{C}$.

To conclude, we propose the following concretized target to construct the
expectation of a tight upper bound.

######  Target 1 (Construct the expectation of a TUB).

Given $f:\\{0,1\\}^{n}\to\mathbb{R}$ with constraints $X\in\mathcal{C}$, let
$g(X)=\mathbb{1}(X\notin\mathcal{C})$, we aim to find
$\hat{f}_{1},\hat{f}_{2}:\\{0,1\\}^{n}\to\mathbb{R}$ such that $\hat{f}_{1}$
is a TUB of $f$ and $\hat{f}_{2}$ is a TUB of $g$, and to construct a
probabilistic objective $\tilde{f}(p)\coloneqq\mathbb{E}_{X\sim
p}\hat{f}_{1}(X)+\beta\mathbb{E}_{X\sim p}\hat{f}_{2}(X)$ with $\beta>0$.

###  3.2 Fast and effective derandomization: Do it in a greedy and incremental
manner

######  High-level Target 2 (Fast and effective derandomization).

We aim to propose a derandomization scheme that is fast in speed and effective
in generating high-quality solutions.

Greedy. To this end, we generalize greedy algorithms to greedy derandomization
and propose an incremental scheme to improve the speed. For greedy
derandomization, starting from $p_{\mathrm{cur}}=p_{\mathrm{o}}$, we repeat
the following steps:

(1) we greedily find the best local derandomization, i.e.,

$(i^{*},x^{*})\leftarrow\mathop{\mathrm{arg\,min}}_{(i,x)\in[n]\times\\{0,1\\}}\tilde{f}(\operatorname{der}(i,x;p_{\mathrm{cur}}))$;

(2) we conduct the best derandomization, i.e.,

$p_{\mathrm{cur}}\leftarrow\operatorname{der}(i^{*},x^{*};p_{\mathrm{cur}})$.

######  Theorem 2 (Goodness of greedy derandomization).

For any entry-wise concave $\tilde{f}$ and any $p_{\mathrm{o}}\in[0,1]^{n}$,
the above process of greedy derandomization can always reach a point where the
final $p_{\mathrm{final}}$ is (G1) discrete (i.e.,
$p_{\mathrm{final}}\in\\{0,1\\}^{n}$), (G2) no worse than $p_{\mathrm{o}}$
(i.e., $\tilde{f}(p_{\mathrm{final}})\leq\tilde{f}(p_{\mathrm{o}})$), and (G3)
a local minimum (i.e.,
$\tilde{f}(p_{\mathrm{final}})\leq\min_{(i,x)\in[n]\times\\{0,1\\}}\tilde{f}(\operatorname{der}(i,x;p_{\mathrm{final}}))$).

######  Remark 4.

Our two theorems are synergic. Specifically, Theorem 1 guarantees an entry-
wise concave probabilistic objective $\tilde{f}$, which is used as a condition
in Theorem 2.

Greedy derandomization improves upon the existing derandomization methods.
Specifically, random sampling (Karalias & Loukas, 2020) guarantees (G1), and
iterative rounding (Wang et al., 2022) guarantees (G1) and (G2). However,
challenges arise regarding the time complexity since a naive way requires $2n$
evaluations of $\tilde{f}$ at each step.

Incremental. To this end, we propose to conduct the derandomization in an
incremental manner to increase the speed, which gives the following target.
Our intuition is that, usually, the incremental differences are simpler than
the whole function, and the computation of incremental differences is easily
parallelizable.

######  Target 2 (Conduct incremental greedy derandomization).

We conduct greedy derandomization and improve the speed by deriving the
incremental differences (IDs)
$\Delta\tilde{f}(i,x,p_{\mathrm{cur}})\coloneqq\tilde{f}(\operatorname{der}(i,x;p_{\mathrm{cur}}))-\tilde{f}(p_{cur})$
for all the $(i,x)$ pairs, instead of evaluating the “whole” function, i.e.,
$\tilde{f}(\operatorname{der}(i,x;p_{\mathrm{cur}}))$’s.

##  4 Deriving Formulae to Meet the Targets

The targets in Sec. 3 provide us guidelines, while deriving objectives and
derandomization to meet those targets is nontrivial. In this work, we focus on
UCom2 (Usupervised Combinatorial Optimization Under Commonly-involved
Conditions) and baptize our method with the same name. For various conditions
that are commonly involved in different CO problems (see Sec. 5 and App. E),
we shall derive (1) TUB-based probabilistic objectives $\tilde{f}$ to meet
Target 1 and (2) incremental differences (IDs) of $\tilde{f}$ to meet Target
2. Some conditions were encountered in the existing works but were not
properly handled within the probabilistic UL4CO pipeline. See more discussions
in App. B.3.

We tackle each condition using the template below. Note that deriving TUB and
IDs for each condition requires distinct, non-trivial ideas.

Construct a probabilistic objective to meet Target 1: • (S1-1) We find a TUB
$\hat{f}$ for the condition i.e. Given an optimization objective $f$, we find
$\hat{f}$ s.t. $\hat{f}(X)\geq f(X),\forall X$ with
$\min_{X}\hat{f}(X)=\min_{X}f(X)$ and
$\arg\min_{X}\hat{f}(X)=\arg\min_{X}f(X)$ or Given a constraint
$X\in\mathcal{C}$, we find $\hat{f}$ s.t.
$\hat{f}(X)\geq\mathbb{1}(X\notin\mathcal{C}),\forall X$ with
$\hat{f}(X)=0,\forall X\in\mathcal{C}$ • (S1-2) After finding $\hat{f}$, we
derive $\tilde{f}(p)\coloneqq\mathbb{E}_{X\sim p}\hat{f}(X)$ Derive
derandomization to meet Target 2: • (S2) We derive the formula of IDs
$\Delta\tilde{f}(\operatorname{der}(i,x;p))$

The conditions to be tackled below have both theoretical and empirical values.
Specifically, they are mathematically hard to handle for probabilistic UL4CO,
and are commonly involved in many CO problems.

###  4.1 Cardinality constraints

Definition. We consider constraints $X\in\mathcal{C}$ with
$\mathcal{C}=\\{X:\lvert V_{X}\rvert\in C_{c}\\}$. Some typical cases are
$C_{c}=\\{k\\}$ or $C_{c}=\\{t\in\mathbb{N}\colon t\leq k\\}$ for some
$k\in\mathbb{N}$ (Buchbinder et al., 2014).

Given $p\in[0,1]^{n}$, $\lvert V_{X}\rvert=\sum_{i\in V}X_{i}$ (see Sec. 2)
follows a Poisson binomial distribution
$\operatorname{PoiBin}(p_{1},p_{2},\ldots,p_{n})$ with parameters
$(p_{i})_{i\in[n]}$ (Wang, 1993). The probability mass function (PMF) is for
each $0\leq t\leq n$,

$\Pr_{X\sim p}[\lvert V_{X}\rvert=t]=\sum_{V_{t}\subseteq V:\lvert
V_{t}\rvert=t}\prod_{i\in V_{t}}p_{i}\prod_{j\in V\setminus V_{t}}(1-p_{j})$.

(S1-1). We find $\hat{f}_{\mathrm{card}}(X;C_{c})\coloneqq\min_{k\in
C_{c}}\lvert\lvert V_{X}\rvert-k\rvert$, i.e., the minimum distance to the
feasible cardinality set $C_{c}$.

######  Lemma 1.

$\hat{f}_{\mathrm{card}}$ is a TUB of $\mathbb{1}[X\notin\mathcal{C}]$.

######  Remark 5.

We can directly compute $\Pr_{X\sim p}[\lvert V_{X}\rvert\notin C_{c}]$, but
the formula we use practically performs better, which distinguishes different
levels of violations. See similar ideas by, e.g., (Pogancic et al., 2019).

(S1-2). We derive
$\tilde{f}_{\mathrm{card}}(p;C_{c})\coloneqq\mathbb{E}_{X\sim
p}\hat{f}_{\mathrm{card}}(X;C_{c})=\sum_{t\in[n]\setminus C_{c}}\Pr_{X\sim
p}[\lvert V_{X}\rvert=t]\min_{k\in C_{c}}\lvert t-k\rvert$. The main technical
difficulty is computing the PMF of a Poisson binomial distribution, for which
we adopt a discrete-Fourier-transform-based method. The main formula of
$\Pr_{X\sim p}[\lvert V_{X}\rvert=t]$ (See Eq. (6) by Hong (2013)) is

$\frac{1}{n+1}\sum_{s=0}^{n}\exp(-\mathbf{i}\omega
st)\prod_{j=1}^{n}(1-p_{j}+p_{j}\exp(\mathbf{i}\omega s))$,

where $\mathbf{i}=\sqrt{-1}$ and $\omega=\frac{2\pi}{n+1}$. See App. C.1 for
more details.

(S2). We derive the IDs of $\tilde{f}_{\mathrm{card}}$, using the recursive
formula of the Poisson binomial distribution.

######  Lemma 2 (IDs of $\tilde{f}_{\mathrm{card}}$).

For any $p\in[0,1]^{n}$, $i\in[n]$, and $0\leq t\leq n$, let
$q_{s}\coloneqq\Pr_{X\sim p}[\lvert V_{X}\rvert=s]$ and
$q^{\prime}_{s}\coloneqq\Pr_{X\sim p}[\lvert
V_{X}\setminus\\{i\\}\rvert=s],\forall s$, we have

$\displaystyle q^{\prime}_{t}$
$\displaystyle=(1-p_{i})^{-1}\sum\nolimits_{s=0}^{t}q_{s}\left(\frac{p_{i}}{p_{i}-1}\right)^{t-s}\text{~{}(if~{}
$p_{i}\neq 1$)}$ (1)
$\displaystyle=(p_{i})^{-1}\sum\nolimits_{s=0}^{n-t-1}q_{t+s+1}\left(\frac{p_{i}-1}{p_{i}}\right)^{s}\text{~{}(if~{}
$p_{i}\neq 0$)}.$ (2)

Based on that, we have

$\begin{cases}\Delta\tilde{f}_{\mathrm{card}}(i,0,p;C_{c})=\sum_{t\in[n]\setminus
C_{c}}(q^{\prime}_{t}-q_{t})\min_{k\in C_{c}}\lvert t-k\rvert,\\\
\Delta\tilde{f}_{\mathrm{card}}(i,1,p;C_{c})=\sum_{t\in[n]\setminus
C_{c}}(q^{\prime}_{t-1}-q_{t})\min_{k\in C_{c}}\lvert t-k\rvert.\end{cases}$

######  Remark 6.

In practice, we always make sure each $p_{i}\in[\epsilon,1-\epsilon]$ for some
small $\epsilon>0$ for better numerical stability. We use Eq. (1) for
$p_{i}\leq 0.5$ and Eq. (2) for $p_{i}>0.5$.

Notes. Enforcing cardinality constraints (e.g., taking top-$k$) is easy, but
differentiable training with cardinality constraints is nontrivial. Other than
probabilistic-method UL4CO, Sinkhorn-related techniques (Sinkhorn & Knopp,
1967; Wang et al., 2023) are valid ways. See also App. B.3.

###  4.2 Minimum (or maximum) w.r.t. a subset

Definition. We consider constraints where we have a pairwise score function
(e.g., distance) $h:V\times V\to\mathbb{R}$ and we aim to compute
$f_{\mathrm{ms}}(X)\coloneqq\min_{v_{X}\in V_{X}}h(i,v_{X})$ for some $i\in V$
(e.g., the shortest distance to a set of points).

We fix $i\in V$ in the analysis below, and let $v_{1},v_{2},\ldots,v_{n}$ be a
permutation of $V=[n]$ such that $d_{1}\leq d_{2}\leq\cdots\leq d_{n}$, where
$d_{j}=h(i,v_{j}),\forall j\in[n]$.

(S1-1). We find $\hat{f}_{\mathrm{ms}}(X;i,h)\coloneqq\min_{v_{X}\in
V_{X}}h(i,v_{X})$, which is the original objective $f_{\mathrm{ms}}$.

######  Lemma 3.

$\hat{f}_{\mathrm{ms}}$ is a TUB of ${f}_{\mathrm{ms}}$.

(S1-2). We derive $\tilde{f}_{\mathrm{ms}}(p;i,h)\coloneqq\mathbb{E}_{X\sim
p}\hat{f}_{\mathrm{ms}}(X;i,h)$, by decomposing the objective into sub-terms.

######  Lemma 4.

For any $p\in[0,1]^{n}$, $\mathbb{E}_{X\sim
p}\hat{f}_{\mathrm{ms}}(X;i,h)=p_{v_{1}}d_{1}+(1-p_{v_{1}})p_{v_{2}}d_{2}+\cdots+(\prod_{j=1}^{n-1}(1-p_{v_{j}}))p_{v_{n}}d_{n}$.

(S2). We derive the IDs of $\tilde{f}_{\mathrm{ms}}$, by analyzing which sub-
terms are changed after one step of local derandomization.

######  Lemma 5 (IDs of $\tilde{f}_{\mathrm{ms}}$).

For any $p\in[0,1]^{n}$ and $j\in[n]$, let
$q_{j}\coloneqq(\prod_{k=1}^{j-1}(1-p_{v_{k}}))p_{v_{j}}$, the coefficient of
$d_{j}$ in $\tilde{f}_{\mathrm{ms}}$. Then

$\begin{cases}\Delta\tilde{f}_{\mathrm{ms}}(v_{j},0,p;i,h)=-q_{j}d_{j}+\frac{p_{v_{j}}}{1-p_{v_{j}}}\sum_{j^{\prime}>j}q_{j^{\prime}}d_{j^{\prime}},\\\
\Delta\tilde{f}_{\mathrm{ms}}(v_{j},1,p;i,h)=\sum_{j^{\prime}>j}q_{j^{\prime}}(d_{j}-d_{j^{\prime}}).\end{cases}$

######  Remark 7.

When $p_{v_{j}}=1$, we replace
$\frac{p_{v_{j}}}{1-p_{v_{j}}}\sum_{j^{\prime}>j}q_{j^{\prime}}d_{j^{\prime}}$
by $\sum_{j^{\prime}>j}(\prod_{1\leq i^{\prime}\leq i-1,i^{\prime}\neq
j}(1-p_{v_{i^{\prime}}}))p_{v_{i}}d_{j^{\prime}}$. Since we make sure each
$p_{i}\neq 1$ (see Rem. 6), this does not happen in practice.

###  4.3 Covering

Definition. We consider conditions where some $i\in V$ needs to be covered
(i.e., at least one neighbor of $i$ is chosen). Formally, the constraints are
$X\in\mathcal{C}$ with $\mathcal{C}=\\{X\colon\\{v_{X}\in
V_{X}\colon(v_{X},i)\in E\\}\neq\emptyset\\}$.

(S1-1). We find
$\hat{f}_{\mathrm{cv}}(X;i)\coloneqq\mathbb{1}(X\notin\mathcal{C})$, which is
the indicative function of the original constraint.

######  Lemma 6.

$\hat{f}_{\mathrm{cv}}$ is a TUB of $\mathbb{1}(X\notin\mathcal{C})$.

(S1-2). We drive $\tilde{f}_{\mathrm{cv}}(p;i)\coloneqq\mathbb{E}_{X\sim
p}\hat{f}_{\mathrm{cv}}(X;i)=\Pr_{X\sim p}[\\{v_{X}\in V_{X}\colon(v_{X},i)\in
E\\}\neq\emptyset]$, by decomposing the objective into sub-terms.

######  Lemma 7.

For any $p\in[0,1]^{n}$ and $i\in[n]$, $\Pr_{X\sim p}[\\{v_{X}\in
V_{X}\colon(v_{X},i)\in E\\}\neq\emptyset]=\prod_{v\in[n]\colon(v,i)\in
E}(1-p_{v})$.

(S2). We derive the IDs of $\tilde{f}_{\mathrm{cv}}$, by analyzing which sub-
terms are changed after one step of local derandomization.

######  Lemma 8 (IDs of $\tilde{f}_{\mathrm{cv}}$).

For any $p\in[0,1]^{n}$ and $i\in[n]$, if $(i,j)\notin E$, then
$\Delta\tilde{f}_{\mathrm{cv}}(j,0,p;i)=\Delta\tilde{f}_{\mathrm{cv}}(j,1,p;i)=0$;
if $(i,j)\in E$, then

$\begin{cases}\Delta\tilde{f}_{\mathrm{cv}}(j,0,p;i)=p_{j}\prod_{v\in
N_{i},v\neq j}(p_{v}-1),\\\
\Delta\tilde{f}_{\mathrm{cv}}(j,1,p;i)=-\tilde{f}_{\mathrm{cv}}(p;i).\end{cases}$

###  4.4 Cliques (or independent sets)

Definition. We consider conditions where the chosen nodes $V_{X}$ should form
a clique.333Equivalently, an independent set in the complement graph.
Formally, the constraints are $X\in\mathcal{C}$ with
$\mathcal{C}=\\{X\colon\binom{V_{X}}{2}\subseteq E\\}$.

(S1-1). We find
$\hat{f}_{\mathrm{cq}}(X)\coloneqq\lvert\\{(u,v)\in\binom{V_{X}}{2}\colon(u,v)\notin
E\\}\rvert$, the number of chosen node pairs violating the constraints.

######  Lemma 9.

$\hat{f}_{\mathrm{cq}}$ is a TUB of $\mathbb{1}[X\notin\mathcal{C}]$.

(S1-2). We derive $\tilde{f}_{\mathrm{cq}}(p)\coloneqq\mathbb{E}_{X\sim
p}\hat{f}_{\mathrm{cq}}(X)$, by decomposing the objective into sub-terms.

######  Lemma 10.

For any $p\in[0,1]^{n}$, $\mathbb{E}_{X\sim
p}\hat{f}_{\mathrm{cq}}(X)=\sum_{(u,v)\in\binom{V}{2}\setminus E}p_{u}p_{v}$.

(S2). We derive the IDs of $\tilde{f}_{\mathrm{cq}}$, by analyzing which sub-
terms are changed after one step of local derandomization.

######  Lemma 11 (IDs of $\tilde{f}_{\mathrm{cq}}$).

For any $p\in[0,1]^{n}$ and $i\in[n]$,

$\begin{cases}\Delta\tilde{f}_{\mathrm{cq}}(i,0,p)=-p_{i}\sum_{j\in[n],j\neq
i,(i,j)\notin E}p_{j},\\\
\Delta\tilde{f}_{\mathrm{cq}}(i,1,p)=(1-p_{i})\sum_{j\in[n],j\neq
i,(i,j)\notin E}p_{j}.\end{cases}$

Notes. (Karalias & Loukas, 2020) and (Min et al., 2022) essentially considered
the “cliques” conditions and derived similar formula of
$\tilde{f}_{\mathrm{cq}}(p)$. Our derivation of the IDs is novel, and we will
also extend this to non-binary cases, which were not discussed in existing
works. Moreover, our high-level targets and templates provide insights into
obtaining and interpreting the derivation in a principled way.

###  4.5 Non-binary decisions

Definition. We consider non-binary decisions, i.e., (potentially) more than
two decisions ($\lvert d\rvert\geq 2$), e.g., problems with partition or
coloring. Our theoretical analysis can be extended to non-binary cases. See
App. D.1 for more details.

###  4.6 Uncertainty

We also consider uncertainty in edge existence, i.e., edge probabilities
$P:E\to[0,1]$. Due to the generality of non-binary conditions and uncertainty,
the details of objective construction and derandomization will be deferred to
where each specific problem is analyzed in Sec. 5.

###  4.7 Notes and insights

Throughout the section, two commonly used ideas for constructing TUBs are: (1)
using a function itself (Lemmas 3 & 6), and (2) relaxing the binary “a
constraint is violated” to “the number of violations” (Lemmas 1 & 9).

Moreover, techniques commonly used in our derivations include (1) decomposing
objectives into sub-terms, and (2) analyzing which sub-terms are changed after
one step of local derandomization. Such “local decomposibility” allows us to
use linearity of expectation. See, e.g., similar ideas by Ahn et al. (2020)
and Jo et al. (2023). See App. G.3 for more discussions.

We acknowledge that we have not covered all conditions involved in CO, but we
expect that similar ideas would be applicable to some other conditions. See
App. E.5 for discussions on some conditions not fully covered in this work,
e.g., cycles and trees.

##  5 Applying the Derivations to CO Problems

In this section, we apply UCom2 to different CO problems (facility location,
maximum coverage, and robust coloring) with both theoretical values, NP-
hardness (Mihelic & Robic, 2004; Yanez & Ramirez, 2003), and real-world
implications. See App. E for the applications to four more problems (robust
$k$-clique, robust dominating set, clique cover, and minimum spanning tree).
Specifically, for each specific problem, we shall (1) check what conditions
are involved and (2) construct the probabilistic objective and derandomization
process by combining the analyses in Sec. 4.

• (1) Find the conditions involved in the optimization objective
($f=\sum_{i}f_{i}$) and the constraints ($X\in\bigcap_{i}\mathcal{C}_{i}$). •
(2) Construct the final objective:
$\sum_{i}\tilde{f}_{i}+\beta\sum_{j}\tilde{g}_{j}$ with constraint coefficient
$\beta>0$ by combining the probabilistic functions $\tilde{f}_{i}$’s and
$\tilde{g}_{i}$’s for the optimization objectives and constraints,
respectively.

###  5.1 Facility location

The facility location problem is abstracted from real-world scenarios, where
the goal is to find some good locations among candidate locations (Drezner &
Hamacher, 2004).

Definition. Given (1) a complete weighted graph $G=(V=[n],E=\binom{V}{2},W)$,
where the distance between each pair $(u,v)$ of nodes is $W(u,v)>0$, and
$W(v,v)=0,\forall v\in V$, and (2) the number $k$ of locations to choose, we
aim to find a subset $V_{X}\subseteq V$ such that (c1) $\lvert V_{X}\rvert=k$,
and (c2) $\sum_{v\in V}\min_{v_{X}\in V_{X}}W(v,v_{X})$ is minimized.

Involved conditions: (1) cardinality constraints and (2) minimum w.r.t. a
subset (see Secs. 4.1 & 4.2).

Details. Given $p\in[0,1]^{n}$ and $\beta>0$,

$\tilde{f}_{\mathrm{FL}}(p;G,k)=(\sum\nolimits_{v\in
V}\tilde{f}_{\mathrm{ms}}(p;v,W))+\beta\tilde{f}_{\mathrm{card}}(p;\\{k\\})$.

For $i\in[n]$ and $x\in\\{0,1\\}$, the ID is
$\Delta\tilde{f}_{\mathrm{FL}}(i,x,p;G,k)=\sum_{v\in
V}\Delta\tilde{f}_{\mathrm{ms}}(i,x,p;v,W)+\beta\Delta\tilde{f}_{\mathrm{card}}(i,x,p;\\{k\\})$.

###  5.2 Maximum coverage

The maximum coverage problem (Khuller et al., 1999) is a classical CO problem
with real-world applications, including public traffic management (Ali & Dyo,
2017), web management (Saha & Getoor, 2009), and scheduling (Marchiori &
Steenbeek, 2000).

Definition. Given (1) $m$ items (WLOG, assume the items are $[m]$), each with
weight $W_{j},\forall j\in[m]$, (2) a family of $n$ sets
$\mathcal{S}=\\{S_{1},S_{2},\ldots,S_{n}\\}$ with each $S_{i}\subseteq[m]$ and
(3) the number $k$ of sets to choose, we aim to choose
$\mathcal{S}_{X}\subseteq\mathcal{S}$ from the given sets such that (c1)
$\lvert\mathcal{S}_{X}\rvert=k$ and (c2) the total weights of the covered
items $\sum_{j\in T_{X}}W_{j}$ is maximized, where
$T_{X}\coloneqq\bigcup_{S_{i}\in\mathcal{S}_{X}}S_{i}$ is the set of covered
items.

Involved conditions: (1) cardinality constraints and (2) covering (see Secs.
4.1 & 4.3).

Details. Construct a bipartite graph
$G_{\mathcal{S}}=(V=\mathcal{S}\cup[m],E)$, where $(S_{i},j)\in E$ iff $j\in
S_{i}$. For $p\in[0,1]^{n}$ and $\beta>0$,

$\tilde{f}_{\mathrm{MC}}(p;\mathcal{S},k)=\sum_{j\in[m]}W_{j}\tilde{f}_{\mathrm{cv}}(p;j,G_{\mathcal{S}})+\beta\tilde{f}_{\mathrm{card}}(p;\\{k\\})$.

For $i\in[n]$ and $x\in\\{0,1\\}$, the ID is
$\Delta\tilde{f}_{\mathrm{MC}}(i,x,p;\mathcal{S},k)=\sum_{j\in[m]}W_{j}\Delta\tilde{f}_{\mathrm{cv}}(i,x,p;j,G_{\mathcal{S}})+\beta\Delta\tilde{f}_{\mathrm{card}}(i,x,p;\\{k\\})$.

###  5.3 Robust coloring

The robust coloring problem (Yanez & Ramirez, 2003) generalizes the coloring
problem (Jensen & Toft, 2011). It is motivated by real-world scheduling
problems where some conflicts can be uncertain, with notable applications to
supply chain management (Lim & Wang, 2005).

(a) FL: rand500

(b) MC: rand500

(c) FL: rand800

(d) MC: rand1000

Figure 1: The speed-quality trade-offs on facility location (FL) and maximum
coverage (MC). Running time ($x$-axis): smaller the better. Objective
($y$-axis): for FL, the smaller the better; for MC, the larger the better. For
MC, we reverse the $y$-axis so that the ideal point is always at the bottom
left corner.

Definition. Given (1) an uncertain graph $G=(V,E,P)$ and (2) the number $c$ of
colors, let $E_{h}\coloneqq\\{e\in E\colon P(e)=1\\}$ represent hard conflicts
which we must avoid, and let $E_{s}\coloneqq\\{e\in E\colon P(e)<1\\}$
represent soft conflicts which possibly happen, we aim to find a $c$-coloring
$X$ on $V$, where each node $v\in V$ has a color $X_{v}\in
d\coloneqq\\{0,1,\ldots,c-1\\}$, such that (c1) no hard conflicts are violated
(i.e., $X_{u}\neq X_{v},\forall(u,v)\in E_{h}$), and (c2) the probability that
no violated soft conflicts happen (i.e., $\prod_{e=(u,v)\in E_{s}\colon
X_{u}=X_{v}}(1-P(e))$) is maximized.

We fix $G$ and $c$ in the analysis below.

Involved conditions: (1) independent sets,444The nodes in each color group
should be an independent set. (2) uncertainty, and (3) non-binary decisions
(see Secs. 4.4 to 4.6).

Details. Regarding (c1), we extend the derivations in Sec. 4.4 to non-binary
cases. We use

$\hat{g}_{1}(X)\coloneqq\lvert\\{(u,v)\in E_{h}\colon X_{u}=X_{v}\\}\rvert$,

which is a TUB of $g_{1}(X)\coloneqq\mathbb{1}(X\notin\mathcal{C}_{1})$ with
$\mathcal{C}_{1}=\\{X\colon\text{(c1) is satisfied}\\}$, and use
$\tilde{g}_{1}(p)\coloneqq\mathbb{E}_{X\sim p}\hat{g}_{1}(X)$. Regarding (c2),
maximizing $\prod_{e=(u,v)\in E_{s}\colon X_{u}=X_{v}}(1-P(e))$ is equivalent
to minimizing

$f_{2}(X)=-\sum_{e=(u,v)\in E_{s}\colon X_{u}=X_{v}}\log(1-P(e))$.

With $\hat{f}_{2}(X)\coloneqq f_{2}(X)$ and
$\tilde{f}_{2}(p)\coloneqq\mathbb{E}_{X\sim p}\hat{f}_{2}(X)$, the final
objective is $\tilde{f}_{\mathrm{RC}}=\tilde{f}_{2}+\beta\tilde{g}_{1}$ with
constraint coefficient $\beta>0$.

######  Lemma 12.

$\hat{g}_{1}$ is a TUB of $g_{1}$ and $\hat{f}_{2}$ is a TUB of $f_{2}$.

###### Proof sketch.

We extend the ideas for independent sets in Sec. 4.4, especially Lemma 9. ∎

We derive each term in $\tilde{f}_{\mathrm{RC}}$ as follows.

######  Lemma 13.

For any $p\in[0,1]^{n\times c}$, $\tilde{f}_{2}(p)=\mathbb{E}_{X\sim
p}\hat{f}_{2}(X)$ and $\tilde{g}_{1}(p)=\mathbb{E}_{X\sim p}\hat{g}_{1}(X)$
with

$\mathbb{E}_{X\sim p}\hat{f}_{2}(X)=-\sum_{e=(u,v)\in
E_{s}}\sum_{r=0}^{c-1}p_{ur}p_{vr}\log(1-P(e))$,

and $\mathbb{E}_{X\sim p}\hat{g}_{1}(X)=\sum_{(u,v)\in
E_{h}}\sum_{r=0}^{c-1}p_{ur}p_{vr}$.

###### Proof sketch.

We extend the ideas in Lemma 10. ∎

We then derive the IDs of each term in $\tilde{f}_{\mathrm{RC}}$.

######  Lemma 14 (IDs of the terms in $\tilde{f}_{\mathrm{RC}}$).

For any $p\in[0,1]^{n\times c}$, $i\in[n]$, and $x\in d$,

$\Delta\tilde{g}_{1}(i,x;p)=\sum_{x^{\prime}\in
d\setminus\\{x\\}}p_{ix^{\prime}}\sum_{(i,j)\in
E_{h}}(p_{jx}-p_{jx^{\prime}})$, and
$\Delta\tilde{f}_{2}(i,x;p)=\sum_{x^{\prime}\in
d\setminus\\{x\\}}p_{ix^{\prime}}\sum_{(i,j)\in
E_{s}}(p_{jx^{\prime}}-p_{jx})\log(1-P(i,j))$.

###### Proof sketch.

We extend the ideas in Lemma 11. Changing $p_{i}$ only affects $j$ with
$(i,j)\in E_{*}$, and we compute the differences for each $j$. ∎

We finally get the overall IDs
$\Delta\tilde{f}_{\mathrm{RC}}=\Delta\tilde{f}_{2}+\beta\Delta\tilde{g}_{1}$.

Notes. When practitioners encounter new problems that involve the conditions
covered in this work, they can simply combine our derivations for the involved
conditions, just as we did in this section. Indeed, we believe many other CO
problems involve the conditions considered in this work.

##  6 Experiments

Through extensive experiments on various problems, we shall show the
effectiveness of UCom2.

###  6.1 Facility location and maximum coverage

We conduct experiments on the facility location problem and the maximum
coverage problem (Secs. 5.1 & 5.2). For the experimental settings, we mainly
follow an existing work (Wang et al., 2023), with additional datasets and
baselines. For fair comparisons, we consider inductive settings (training and
test sets are different) and use the same GNN architectures as Wang et al.
(2023). See App. G.1 for discussions on transductive settings. See App. F.1
for the detailed experimental settings.

Table 1: Results on facility location. Running time (time; normalized): the
smaller the better. Objective (obj; normalized): the smaller the better. In
each column, $\blacksquare$ indicates ranking the 1st, $\blacksquare$ the 2nd,
and $\blacksquare$ the 3rd.

Method | rand500 | rand800 | starbucks | mcd | subway | average |  average rank
---|---|---|---|---|---|---|---
obj$\downarrow$ |  time$\downarrow$ |  obj$\downarrow$ |  time$\downarrow$ |  obj$\downarrow$ |  time$\downarrow$ |  obj$\downarrow$ |  time$\downarrow$ |  obj$\downarrow$ |  time$\downarrow$ |  obj$\downarrow$ |  time$\downarrow$ |  obj$\downarrow$ |  time$\downarrow$ |  sum$\downarrow$
random | 1.43 | 263.29 | 1.51 | 125.65 | 1.86 | 461.54 | 1.64 | 122.45 | 1.52 | 119.40 | 1.61 | 240.34 | 11.6 | 13.6 |  25.2 [t]
greedy | 1.19 | 2.30 | 1.16 | 3.08 | 1.21 | 12.52 | 1.19 | 5.87 | 1.11 | 12.94 | 1.17 | 7.34 | 8.6 | 4.0 | 12.6
Gurobi | 1.07 | 133.68 | 1.26 | 65.47 | 1.07 | 197.08 | 1.51 | 63.88 | 2.63 | 69.08 | 1.51 | 105.84 | 9.0 | 11.8 | 20.8
SCIP | 1.73 | 103.55 | 2.35 | 100.34 | 19.76 | 154.83 | 55.10 | 247.91 | 55.01 | 366.47 | 26.79 | 194.62 | 15.8 | 12.8 | 28.6
CardNN-S | 1.14 | 15.29 | 1.06 | 8.45 | 1.62 | 36.98 | 1.16 | 11.99 | 1.08 | 10.14 | 1.21 | 16.57 | 7.4 | 5.4 | 12.8
CardNN-GS | 1.00 | 78.38 | 1.01 | 74.22 | 1.07 | 76.69 | 1.15 | 21.60 | 1.03 | 14.99 | 1.05 | 53.18 | 4.0 | 9.0 | 13.0
CardNN-HGS | 1.00 | 110.14 | 1.01 | 95.11 | 1.07 | 174.87 | 1.15 | 49.20 | 1.02 | 28.48 | 1.05 | 91.56 | 3.4 | 11.2 | 14.6
CardNN-noTTO-S | 1.43 | 2.23 | 1.55 | 1.05 | 3.34 | 3.90 | 3.90 | 1.00 | 3.54 | 1.00 | 2.75 | 1.84 | 14.0 | 1.6 | 15.6
CardNN-noTTO-GS | 1.14 | 31.39 | 1.15 | 27.18 | 1.52 | 15.73 | 1.26 | 8.03 | 1.23 | 2.21 | 1.26 | 16.91 | 8.8 | 4.8 | 13.6
CardNN-noTTO-HGS | 1.14 | 40.97 | 1.15 | 32.30 | 1.45 | 29.98 | 1.27 | 14.44 | 1.21 | 3.67 | 1.24 | 24.27 | 8.4 | 6.6 | 15.0
EGN-naïve | 1.10 | 86.45 | 1.14 | 44.66 | 1.14 | 232.44 | 1.66 | 24.53 | 1.47 | 60.13 | 1.30 | 89.64 | 8.6 | 10.6 | 19.2
RL-transductive | 2.32 | 329.11 | 2.24 | 157.07 | 10.24 | 3461.54 | 2.77 | 918.37 | 2.51 | 895.52 | 4.02 | 1152.32 | 14.6 | 15.6 | 30.2
RL-inductive | 1.70 | 329.17 | 1.85 | 157.35 | 2.72 | 577.00 | 2.55 | 153.08 | 2.36 | 149.28 | 2.24 | 273.18 | 13.2 | 15.0 |  28.2 [b]
UCom2-short | 1.05 | 1.00 | 1.03 | 1.00 | 1.03 | 1.00 | 1.05 | 1.31 | 1.04 | 1.77 | 1.04 | 1.89 | 4.2 | 1.4 |  5.6 [t]
UCom2-middle | 1.00 | 32.56 | 1.00 | 15.65 | 1.03 | 4.35 | 1.01 | 4.47 | 1.01 | 13.05 | 1.01 | 14.02 | 2.0 | 4.8 | 6.8
UCom2-long | 1.00 | 81.03 | 1.00 | 31.12 | 1.00 | 20.27 | 1.00 | 19.41 | 1.00 | 22.88 | 1.00 | 34.94 | 1.0 | 7.8 |  8.8 [b]

Table 2: Results on maximum coverage. Running time (time; normalized): smaller
the better. Objective (obj; normalized): the larger the better. In each
column, $\blacksquare$ indicates ranking the 1st, $\blacksquare$ the 2nd, and
$\blacksquare$ the 3rd.

Method | rand500 | rand1000 | twitch | railway | average |  average rank
---|---|---|---|---|---|---
obj$\uparrow$ |  time$\downarrow$ |  obj$\uparrow$ |  time$\downarrow$ |  obj$\uparrow$ |  time$\downarrow$ |  obj$\uparrow$ |  time$\downarrow$ |  obj$\uparrow$ |  time$\downarrow$ |  obj$\uparrow$ |  time$\downarrow$ |  sum$\downarrow$
random | 0.82 | 2666.67 | 0.79 | 727.27 | 0.52 | 369.23 | 0.96 | 315.79 | 0.77 | 1019.74 | 12.8 | 14.0 |  26.8 [t]
greedy | 0.98 | 1.00 | 0.99 | 1.00 | 1.00 | 1.06 | 1.00 | 1.00 | 0.99 | 1.02 | 7.3 | 1.3 | 8.5
Gurobi | 1.00 | 1333.89 | 1.00 | 363.94 | 1.00 | 1.00 | 1.00 | 158.87 | 1.00 | 464.42 | 3.3 | 8.8 | 12.0
SCIP | 0.97 | 1334.11 | 0.96 | 362.09 | 1.00 | 5.05 | 1.00 | 159.84 | 0.98 | 465.27 | 6.3 | 10.8 | 17.0
CardNN-S | 0.93 | 130.33 | 0.93 | 35.94 | 1.00 | 12.25 | 0.97 | 3.71 | 0.96 | 45.56 | 8.0 | 5.5 | 13.5
CardNN-GS | 0.99 | 448.11 | 1.00 | 169.55 | 1.00 | 25.38 | 1.00 | 23.21 | 1.00 | 166.56 | 4.3 | 9.0 | 13.3
CardNN-HGS | 0.99 | 618.22 | 1.00 | 248.33 | 1.00 | 47.28 | 1.00 | 35.86 | 1.00 | 237.42 | 3.3 | 10.5 | 13.8
CardNN-noTTO-S | 0.70 | 20.33 | 0.69 | 6.18 | 0.01 | 1.43 | 0.94 | 1.54 | 0.58 | 7.37 | 16.0 | 2.8 | 18.8
CardNN-noTTO-GS | 0.82 | 115.56 | 0.79 | 61.18 | 0.02 | 2.97 | 0.96 | 7.53 | 0.65 | 46.81 | 13.5 | 5.0 | 18.5
CardNN-noTTO-HGS | 0.82 | 132.56 | 0.79 | 75.15 | 0.19 | 3.62 | 0.96 | 12.14 | 0.69 | 55.87 | 12.3 | 6.5 | 18.8
EGN-naive | 0.92 | 1334.56 | 0.91 | 364.45 | 0.13 | 185.22 | 0.97 | 159.13 | 0.73 | 510.84 | 11.3 | 12.8 | 24.0
RL-transductive | 0.92 | 3333.33 | 0.82 | 909.09 | 0.95 | 2769.23 | 0.96 | 2368.42 | 0.91 | 2345.02 | 11.5 | 15.5 | 27.0
RL-inductive | 0.77 | 3334.00 | 0.77 | 909.64 | 0.59 | 464.48 | 0.96 | 397.08 | 0.77 | 1276.30 | 13.8 | 15.5 |  29.3 [b]
UCom2-short | 0.99 | 10.67 | 0.99 | 5.55 | 1.00 | 2.80 | 1.00 | 2.63 | 1.00 | 5.41 | 5.8 | 2.8 |  8.5 [t]
UCom2-middle | 1.00 | 168.44 | 1.00 | 23.76 | 1.00 | 17.58 | 1.00 | 10.75 | 1.00 | 55.13 | 3.8 | 6.5 | 10.3
UCom2-long | 1.00 | 333.56 | 1.00 | 222.85 | 1.00 | 29.77 | 1.00 | 21.11 | 1.00 | 151.82 | 2.3 | 9.0 |  11.3 [b]

Methods. We compare UCom2 with: (1) random: $k$ locations or sets are picked
uniformly at random; (2) greedy: deterministic greedy algorithms; (3-4) Gurobi
(Gurobi Optimization, LLC, 2023) and SCIP (Bestuzheva et al., 2021; Perron &
Furnon, 2023): the problems are formulated as MIPs and the two solvers are
used; (5) CardNN (Wang et al., 2023): a SOTA UL4CO method with three variants;
(6) CardNN-noTTO: CardNN directly optimizes on each test graph in test time,
and these are variants of CardNN without test-time optimization; (7) EGN-
naive: EGN (Karalias & Loukas, 2020) with a naive probabilistic objective
construction and iterative rounding; (8) RL: a reinforcement-learning method
(Kool et al., 2019). See App. G.2 for discussions on reinforcement learning.

Table 3: Results on robust coloring. Running time (time; in seconds): the
smaller the better. Objective (obj): the smaller the better. In each column,
$\blacksquare$ indicates ranking the 1st, and $\blacksquare$ the 2nd.

Method | collins, 18 colors | collins, 25 colors | gavin, 8 colors | gavin, 15 colors | krogan, 8 colors | krogan, 15 colors | ppi, 47 colors | ppi, 50 colors |  average rank
---|---|---|---|---|---|---|---|---|---
obj$\downarrow$ |  time$\downarrow$ |  obj$\downarrow$ |  time$\downarrow$ |  obj$\downarrow$ |  time$\downarrow$ |  obj$\downarrow$ |  time$\downarrow$ |  obj$\downarrow$ |  time$\downarrow$ |  obj$\downarrow$ |  time$\downarrow$ |  obj$\downarrow$ |  time$\downarrow$ |  obj$\downarrow$ |  time$\downarrow$ |  obj$\downarrow$ |  time$\downarrow$ |  sum$\downarrow$
greedy-RD | 115.33 | 300.34 | 23.42 | 300.79 | 66.51 | 300.53 | 7.36 | 301.46 | 117.47 | 300.06 | 0.87 | 301.24 | 4.16 | 301.31 | 1.23 | 301.24 | 2.88 | 3.25 |  6.13 [t]
greedy-GA | 114.36 | 188.21 | 22.20 | 243.93 | 66.51 | 398.90 | 7.36 | 540.62 | 117.47 | 941.35 | 0.87 | 1256.66 | 3.66 | 1416.38 | 1.23 | 1484.27 | 2.50 | 4.25 | 6.75
DC | 586.56 | 300.28 | 159.15 | 300.38 | 311.91 | 300.11 | 58.10 | 300.12 | 1065.52 | 300.07 | 1.76 | 300.46 | 43.35 | 300.13 | 6.72 | 300.76 | 5.00 | 2.50 | 7.50
Gurobi | 87.28 | 301.71 | 16.23 | 306.10 | 42.41 | 300.80 | 7.28 | 303.50 | 46.78 | 300.80 | 0.87 | 51.70 | 4.60 | 328.48 | 1.31 | 313.23 | 2.50 | 4.00 | 6.50
UCom2 (CPU) | 82.26 | 79.36 | 15.16 | 54.37 | 42.99 | 152.20 | 6.72 | 260.90 | 53.44 | 211.43 | 0.87 | 8.55 | 2.93 | 116.54 | 1.01 | 120.56 | 1.50 | 1.00 |  2.50 [t]
UCom2 (GPU) | 7.09 | 8.03 | 13.28 | 17.25 | 13.73 | 1.91 | 5.24 | 5.48 |  [b]

Datasets. We consider both synthetic and real-world graphs.

  * •

Random graphs: The number after “rand” represents the size of the random
graphs. Each group of random graphs contains 100 graphs from the same
distribution.

  * •

Real-world graphs: For facility location, each graph contains real-world
entities with locations (starbucks, mcd, subway). For maximum coverage, each
graph contains real-world sets (twitch, railway). Each group of real-world
graphs contains multiple graphs from the same source.

Speed-quality trade-offs. For several methods (including UCom2), we can grant
more running time to obtain better optimization quality. For UCom2, we use
test-time augmentation (Jin et al., 2023) on the test graphs by adding
perturbations into graph topology and features. UCom2-short does not test-time
augmentation, while the other two variants use different numbers of augmented
data.

Evaluation. For each group of datasets and each method, we report the average
optimization objective and running time over five trials. We also report the
overall objective, time, and ranks, averaged over all the groups of datasets.
The average rank “sum” (ARS) is the summation of the average ranks w.r.t.
objective and time. See App. F for the full results with standard deviations
and ablation studies.

Results. On both problems, UCom2 achieves the best trade-offs overall (Tables
1 & 2). On facility location, the top-$3$ methods w.r.t. ARS are the three
variants of UCom2. On maximum coverage, the three variants rank 1, 3, and 4
w.r.t. ARS, respectively. In Figure 1, we report the detailed trade-offs of
different methods on the random graphs, visually illustrating the best trade-
off overall by UCom2.

###  6.2 Robust coloring

We conduct experiments on the robust coloring problem (see Sec. 5.3) under
transductive settings directly optimizing probabilistic decisions $p$. See
App. F.1 for more details.

Methods. We compare UCom2 with four baseline methods. (1-2) Greedy-RD and
greedy-GA: both methods decide the colors following an enumeration of nodes,
where greedy-RD follows a random (RD) permutation of the nodes while greedy-GA
uses a genetic algorithm (GA) to learn the permutation;555Greedy-GA is the
method proposed by (Yanez & Ramirez, 2003) in the original paper of robust
coloring. (3) Deterministic coloring (DC): a deterministic greedy coloring
algorithm (Kosowski & Manuszewski, 2004) is used to avoid all the hard
conflicts, and it tries to avoid as many soft conflicts as possible; (4)
Gurobi: the problem is formulated as an MIP and the solver is used.

Datasets. We use four real-world uncertain graphs: (1) collins, (2) gavin, (3)
krogan, and (4) PPI.

Speed-quality trade-offs. We record the running time of UCom2 using only CPUs
and using GPUs. For UCom2, we use multiple initial probabilities. We make sure
that even with only CPUs, UCom2 uses less time than each baseline.

Evaluation. For each group of datasets and each method, we report the average
optimization objective and running time over five trials. The average ranks
are computed in the same way as for facility location and maximum coverage.

Results. As shown in Table 3, with the least running time, UCom2 consistently
achieves (1) better optimization quality than the two greedy baselines and DC
and (2) better optimization quality than Gurobi in most cases. This
superiority holds even when we only use CPUs for UCom2. When using GPUs, UCom2
is even faster.

###  6.3 Ablation studies

We analyze different components in UCom2 and show that (1) good probabilistic
objectives are helpful, (2) greedy derandomization is more effective than
iterative rounding, and (3) incremental derandomization improves the speed.
See App. F.3 for more details.

##  7 General Related Work: Learning for CO

We shall discuss more general related works, including other learning-based
methods for CO problems.

Reinforcement learning for CO. Typical techniques include reinforcement
learning (RL). The pioneers who applied RL to CO include (Bello et al., 2016)
and (Khalil et al., 2017). Most reinforcement-learning-for-combinatorial-
optimization methods focus on routing problems such as the traveling salesman
problem (TSP) and the vehicle routing problem (VRP) (Berto et al., 2023; Kool
et al., 2019; Kim et al., 2021; Delarue et al., 2020; Qiu et al., 2022; Nazari
et al., 2018; Ye et al., 2023a; Chalumeau et al., 2023; Luo et al., 2023;
Grinsztajn et al., 2023; Ye et al., 2024; Xiao et al., 2024), as well as
maximum independent sets (MIP) (Ahn et al., 2020; Qiu et al., 2022; Sun &
Yiming, 2023; Li et al., 2023b). See also some recent surveys on RL4CO
(Mazyavkina et al., 2021; Bengio et al., 2021; Cappart et al., 2023; Munikoti
et al., 2023) for more details. The existing RL-based methods still suffer
from efficiency issues. See the discussions by (Wang et al., 2022) and (Wang
et al., 2023). See also App. G.2 for more discussions.

Other machine-learning techniques for CO. Some other machine-learning
techniques have been proposed for CO. There is recent progress based on search
(Choo et al., 2022; Son et al., 2023; Li et al., 2023b), sampling (Sun et al.,
2023), graph-based diffusion (Sun & Yiming, 2023), generative flow networks
(Zhang et al., 2023), meta-learning (Qiu et al., 2022; Wang & Li, 2023), and
quantum machine learning (Ye et al., 2023b). Physics-inspired machine learning
has also been considered by researchers (Schuetz et al., 2022a; Aramon et al.,
2019; Schuetz et al., 2022b). There is also a line of research on
perturbation-based methods for CO (Pogancic et al., 2019; Berthet et al.,
2020; Paulus et al., 2021; Ferber et al., 2023).

##  8 Conclusion and Discussion

In this work, we study and propose UCom2 (Usupervised Combinatorial
Optimization Under Commonly-involved Conditions). Specifically, we concretize
the targets for probabilistic objective construction and derandomization (Sec.
3) with theoretical justification (Theorems 1 and 2), derive non-trivial
objectives and derandomization for various conditions (e.g., cardinality
constraints and minimum) to meet the targets (Sec. 4; Lemmas 1 to 11), apply
the derivations to different problems involving such conditions (Sec. 5), and
finally show the empirical superiority of our method via extensive experiments
(Sec. 6). For reproducibility, we share the code and datasets online (Bu et
al., 2024).

As discussed in Sec. 4.7, we have not covered all conditions involved in CO in
this work, while we believe that our high-level ideas are applicable to other
conditions and problems. The performance of UCom2 and general UL4CO on other
conditions (Min et al., 2023; Lachapelle et al., 2020) and hard instances (Xu
et al., 2007; Li et al., 2023a) are interesting topics for future exploration.

## Acknowledgments

The authors thank all the anonymous reviewers for their helpful comments.

The authors thank Dr. Runzhong Wang @ MIT, Federico Berto @ KAIST, Chuanbo Hua
@ KAIST, and Dr. Junyoung Park @ Qualcomm for constructive discussions.

Fanchen Bu gives special thanks to Prof. Jaehoon Kim @ KAIST, Dr. Hong Liu @
IBS, and Yuhao Yao @ Huawei from whom Fanchen Bu studied the probabilistic
method.

This work was supported by Institute of Information & Communications
Technology Planning & Evaluation (IITP) grant funded by the Korea government
(MSIT) (No. 2022-0-00871, Development of AI Autonomy and Knowledge Enhancement
for AI Agent Collaboration) (No. 2019-0-00075, Artificial Intelligence
Graduate School Program (KAIST)) (No. 2019-0-01906, Artificial Intelligence
Graduate School Program (POSTECH)).

## Impact Statement

This paper presents work whose goal is to advance the field of Machine
Learning, especially Machine Learning for Combinatorial Optimization. There
are many potential societal consequences of our work, none of which we feel
must be specifically highlighted here.

## References

  * Ahn et al. (2020) Ahn, S., Seo, Y., and Shin, J.  Learning what to defer for maximum independent sets.  In _ICML_ , 2020.
  * Ali & Dyo (2017) Ali, J. and Dyo, V.  Coverage and mobile sensor placement for vehicles on predetermined routes: A greedy heuristic approach.  In _WINSYS_ , 2017.
  * Alon & Spencer (2016) Alon, N. and Spencer, J. H.  _The probabilistic method_.  John Wiley & Sons, 2016.
  * Aramon et al. (2019) Aramon, M., Rosenberg, G., Valiante, E., Miyazawa, T., Tamura, H., and Katzgraber, H. G.  Physics-inspired optimization for quadratic unconstrained problems using a digital annealer.  _Frontiers in Physics_ , 7:48, 2019.
  * Bach et al. (2013) Bach, F. et al.  Learning with submodular functions: A convex optimization perspective.  _Foundations and Trends® in machine learning_ , 6(2-3):145–373, 2013.
  * Bello et al. (2016) Bello, I., Pham, H., Le, Q. V., Norouzi, M., and Bengio, S.  Neural combinatorial optimization with reinforcement learning.  In _ICLR_ , 2016.
  * Bengio et al. (2021) Bengio, Y., Lodi, A., and Prouvost, A.  Machine learning for combinatorial optimization: a methodological tour d’horizon.  _European Journal of Operational Research_ , 290(2):405–421, 2021.
  * Berthet et al. (2020) Berthet, Q., Blondel, M., Teboul, O., Cuturi, M., Vert, J.-P., and Bach, F.  Learning with differentiable pertubed optimizers.  In _NeurIPS_ , 2020.
  * Berto et al. (2023) Berto, F., Hua, C., Park, J., Kim, M., Kim, H., Son, J., Kim, H., Kim, J., and Park, J.  RL4CO: an extensive reinforcement learning for combinatorial optimization benchmark.  _arXiv:2306.17100_ , 2023.
  * Bestuzheva et al. (2021) Bestuzheva, K., Besançon, M., Chen, W.-K., Chmiela, A., Donkiewicz, T., van Doornmalen, J., Eifler, L., Gaul, O., Gamrath, G., Gleixner, A., et al.  The scip optimization suite 8.0.  _arXiv 2112.08872_ , 2021.
  * Billionnet (2005) Billionnet, A.  Different formulations for solving the heaviest k-subgraph problem.  _INFOR: Information Systems and Operational Research_ , 43(3):171–186, 2005.
  * Bomze et al. (1999) Bomze, I. M., Budinich, M., Pardalos, P. M., and Pelillo, M.  The maximum clique problem.  _Handbook of Combinatorial Optimization: Supplement Volume A_ , pp. 1–74, 1999.
  * Bu et al. (2024) Bu, F., Jo, H., Lee, S. Y., Ahn, S., and Shin, K.  Tackling prevalent conditions in unsupervised combinatorial optimization: Code and datasets.  https://github.com/ai4co/unsupervised-CO-ucom2, 2024.
  * Buchbinder et al. (2014) Buchbinder, N., Feldman, M., Naor, J., and Schwartz, R.  Submodular maximization with cardinality constraints.  In _SODA_ , 2014.
  * Cappart et al. (2023) Cappart, Q., Chételat, D., Khalil, E. B., Lodi, A., Morris, C., and Velickovic, P.  Combinatorial optimization and reasoning with graph neural networks.  _J. Mach. Learn. Res._ , 24:130–1, 2023.
  * Caprara et al. (2000) Caprara, A., Toth, P., and Fischetti, M.  Algorithms for the set covering problem.  _Annals of Operations Research_ , 98(1-4):353–371, 2000.
  * Ceccarello et al. (2017) Ceccarello, M., Fantozzi, C., Pietracaprina, A., Pucci, G., and Vandin, F.  Clustering uncertain graphs.  In _PVLDB_ , 2017.
  * Ceria et al. (1998) Ceria, S., Nobili, P., and Sassano, A.  A lagrangian-based heuristic for large-scale set covering problems.  _Mathematical Programming_ , 81:215–228, 1998.
  * Chalumeau et al. (2023) Chalumeau, F., Surana, S., Bonnet, C., Grinsztajn, N., Pretorius, A., Alexandre, L., and Barrett, T.  Combinatorial optimization with policy adaptation using latent space search.  In _NeurIPS_ , 2023.
  * Chen et al. (2019) Chen, X., Chen, M., Shi, W., Sun, Y., and Zaniolo, C.  Embedding uncertain knowledge graphs.  In _AAAI_ , 2019.
  * Choo et al. (2022) Choo, J., Kwon, Y.-D., Kim, J., Jae, J., Hottung, A., Tierney, K., and Gwon, Y.  Simulation-guided beam search for neural combinatorial optimization.  In _NeurIPS_ , 2022.
  * Delarue et al. (2020) Delarue, A., Anderson, R., and Tjandraatmadja, C.  Reinforcement learning with combinatorial actions: An application to vehicle routing.  In _NeurIPS_ , 2020.
  * Diaby (2006) Diaby, M.  The traveling salesman problem: a linear programming formulation.  _arXiv preprint cs/0609005_ , 2006.
  * Drakulic et al. (2023) Drakulic, D., Michel, S., Mai, F., Sors, A., and Andreoli, J.-M.  Bq-nco: Bisimulation quotienting for generalizable neural combinatorial optimization.  In _NeurIPS_ , 2023.
  * Drezner & Hamacher (2004) Drezner, Z. and Hamacher, H. W.  _Facility location: applications and theory_.  Springer Science & Business Media, 2004.
  * Erdős & Spencer (1974) Erdős, P. and Spencer, J.  _Probabilistic methods in combinatorics_.  Akadémiai Kindó, 1974.
  * Feige et al. (2001) Feige, U., Peleg, D., and Kortsarz, G.  The dense k-subgraph problem.  _Algorithmica_ , 29:410–421, 2001.
  * Ferber et al. (2023) Ferber, A. M., Huang, T., Zha, D., Schubert, M., Steiner, B., Dilkina, B., and Tian, Y.  Surco: Learning linear surrogates for combinatorial nonlinear optimization problems.  In _ICML_ , 2023.
  * Gaile et al. (2022) Gaile, E., Draguns, A., Ozoliņš, E., and Freivalds, K.  Unsupervised training for neural tsp solver.  In _LION_ , 2022.
  * Graham & Hell (1985) Graham, R. L. and Hell, P.  On the history of the minimum spanning tree problem.  _Annals of the History of Computing_ , 7(1):43–57, 1985.
  * Gramm et al. (2009) Gramm, J., Guo, J., Hüffner, F., and Niedermeier, R.  Data reduction and exact algorithms for clique cover.  _Journal of Experimental Algorithmics (JEA)_ , 13:2–2, 2009\.
  * Grinsztajn et al. (2023) Grinsztajn, N., Daniel, F.-B., Shikha, S., Bonnet, C., and Barrett, T.  Winner takes it all: Training performant RL populations for combinatorial optimization.  In _NeurIPS_ , 2023.
  * Guha & Khuller (1998) Guha, S. and Khuller, S.  Approximation algorithms for connected dominating sets.  _Algorithmica_ , 20:374–387, 1998.
  * Gurobi Optimization, LLC (2023) Gurobi Optimization, LLC.  Gurobi Optimizer Reference Manual, 2023.  URL https://www.gurobi.com.
  * Hong (2013) Hong, Y.  On computing the distribution function for the poisson binomial distribution.  _Computational Statistics & Data Analysis_, 59:41–51, 2013.
  * Hu et al. (2017) Hu, J., Cheng, R., Huang, Z., Fang, Y., and Luo, S.  On embedding uncertain graphs.  In _CIKM_ , 2017.
  * Jensen & Toft (2011) Jensen, T. R. and Toft, B.  _Graph coloring problems_.  John Wiley & Sons, 2011.
  * Jin et al. (2023) Jin, W., Zhao, T., Ding, J., Liu, Y., Tang, J., and Shah, N.  Empowering graph representation learning with test-time graph transformation.  In _ICLR_ , 2023.
  * Jo et al. (2023) Jo, H., Bu, F., and Shin, K.  Robust graph clustering via meta weighting for noisy graphs.  In _CIKM_ , 2023.
  * Karalias & Loukas (2020) Karalias, N. and Loukas, A.  Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs.  In _NeurIPS_ , 2020.
  * Karalias et al. (2022) Karalias, N., Robinson, J., Loukas, A., and Jegelka, S.  Neural set function extensions: Learning with discrete functions in high dimensions.  In _NeurIPS_ , 2022.
  * Khalil et al. (2017) Khalil, E., Dai, H., Zhang, Y., Dilkina, B., and Song, L.  Learning combinatorial optimization algorithms over graphs.  In _NeurIPS_ , 2017.
  * Khuller et al. (1999) Khuller, S., Moss, A., and Naor, J. S.  The budgeted maximum coverage problem.  _Information processing letters_ , 70(1):39–45, 1999.
  * Kim et al. (2021) Kim, M., Park, J., et al.  Learning collaborative policies to solve NP-hard routing problems.  In _NeurIPS_ , 2021.
  * Kollovieh et al. (2024) Kollovieh, M., Charpentier, B., Zügner, D., and Günnemann, S.  Expected probabilistic hierarchies, 2024.  URL https://openreview.net/forum?id=Q3Foe1fDjh.
  * Kool et al. (2019) Kool, W., Van Hoof, H., and Welling, M.  Attention, learn to solve routing problems!  In _ICLR_ , 2019.
  * Kosowski & Manuszewski (2004) Kosowski, A. and Manuszewski, K.  Classical coloring of graphs.  _Contemporary Mathematics_ , 352:1–20, 2004.
  * Lachapelle et al. (2020) Lachapelle, S., Brouillard, P., Deleu, T., and Lacoste-Julien, S.  Gradient-based neural dag learning.  In _ICLR_ , 2020.
  * Li et al. (2023a) Li, Y., Chen, X., Guo, W., Li, X., Luo, W., Huang, J., Zhen, H.-L., Yuan, M., and Yan, J.  HardSATGEN: Understanding the difficulty of hard sat formula generation and a strong structure-hardness-aware baseline.  In _KDD_ , 2023a.
  * Li et al. (2023b) Li, Y., Guo, J., Wang, R., and Yan, J.  T2T: From distribution learning in training to gradient search in testing for combinatorial optimization.  In _NeurIPS_ , 2023b.
  * Lim & Wang (2005) Lim, A. and Wang, F.  Robust graph coloring for uncertain supply chain management.  In _HICSS_ , 2005.
  * Luo et al. (2023) Luo, F., Lin, X., Liu, F., Zhang, Q., and Wang, Z.  Neural combinatorial optimization with heavy decoder: Toward large scale generalization.  In _NeurIPS_ , 2023.
  * Marchiori & Steenbeek (2000) Marchiori, E. and Steenbeek, A.  An evolutionary algorithm for large scale set covering problems with application to airline crew scheduling.  In _Workshops on Real-World Applications of Evolutionary Computation_ , 2000.
  * Mazyavkina et al. (2021) Mazyavkina, N., Sviridov, S., Ivanov, S., and Burnaev, E.  Reinforcement learning for combinatorial optimization: A survey.  _Computers & Operations Research_, 134:105400, 2021.
  * Mihelic & Robic (2004) Mihelic, J. and Robic, B.  Facility location and covering problems.  In _Proc. of the 7th International Multiconference Information Society_ , volume 500, 2004.
  * Min et al. (2022) Min, Y., Wenkel, F., Perlmutter, M., and Wolf, G.  Can hybrid geometric scattering networks help solve the maximum clique problem?  In _NeurIPS_ , 2022.
  * Min et al. (2023) Min, Y., Bai, Y., and Gomes, C. P.  Unsupervised learning for solving the travelling salesman problem.  In _NeurIPS_ , 2023.
  * Miryoosefi & Jin (2022) Miryoosefi, S. and Jin, C.  A simple reward-free approach to constrained reinforcement learning.  In _ICML_ , 2022.
  * Munikoti et al. (2023) Munikoti, S., Agarwal, D., Das, L., Halappanavar, M., and Natarajan, B.  Challenges and opportunities in deep reinforcement learning with graph neural networks: A comprehensive review of algorithms and applications.  _IEEE Transactions on Neural Networks and Learning Systems_ , 2023\.
  * Nazari et al. (2018) Nazari, M., Oroojlooy, A., Snyder, L., and Takác, M.  Reinforcement learning for solving the vehicle routing problem.  In _NeurIPS_ , 2018.
  * Papp et al. (2021) Papp, P. A., Martinkus, K., Faber, L., and Wattenhofer, R.  DropGNN: Random dropouts increase the expressiveness of graph neural networks.  In _NeurIPS_ , 2021.
  * Paulus et al. (2021) Paulus, A., Rolínek, M., Musil, V., Amos, B., and Martius, G.  CombOptNet: Fit the right np-hard problem by learning integer programming constraints.  In _ICML_ , 2021.
  * Perron & Furnon (2023) Perron, L. and Furnon, V.  Or-tools v9.7, 2023.  URL https://developers.google.com/optimization/.
  * Pettie & Ramachandran (2002) Pettie, S. and Ramachandran, V.  An optimal minimum spanning tree algorithm.  _Journal of the ACM (JACM)_ , 49(1):16–34, 2002\.
  * Pogancic et al. (2019) Pogancic, M. V., Paulus, A., Musil, V., Martius, G., and Rolinek, M.  Differentiation of blackbox combinatorial solvers.  In _ICLR_ , 2019.
  * Qiu et al. (2022) Qiu, R., Sun, Z., and Yang, Y.  DIMES: A differentiable meta solver for combinatorial optimization problems.  In _NeurIPS_ , 2022.
  * Rozemberczki et al. (2021) Rozemberczki, B., Allen, C., and Sarkar, R.  Multi-scale attributed node embedding.  _Journal of Complex Networks_ , 9(2):cnab014, 2021\.
  * Saha & Getoor (2009) Saha, B. and Getoor, L.  On maximum coverage in the streaming model & application to multi-topic blog-watch.  In _SDM_ , 2009.
  * Sanokowski et al. (2023) Sanokowski, S., Berghammer, W., Hochreiter, S., and Lehner, S. L.  Variational annealing on graphs for combinatorial optimization.  In _NeurIPS_ , 2023.
  * Schuetz et al. (2022a) Schuetz, M. J., Brubaker, J. K., and Katzgraber, H. G.  Combinatorial optimization with physics-inspired graph neural networks.  _Nature Machine Intelligence_ , 4(4):367–377, 2022a.
  * Schuetz et al. (2022b) Schuetz, M. J., Brubaker, J. K., Zhu, Z., and Katzgraber, H. G.  Graph coloring with physics-inspired graph neural networks.  _Physical Review Research_ , 4(4):043131, 2022b.
  * Shu et al. (2022) Shu, J., Xi, B., Li, Y., Wu, F., Kamhoua, C., and Ma, J.  Understanding dropout for graph neural networks.  In _TheWebConf (WWW)_ , 2022.
  * Sinkhorn & Knopp (1967) Sinkhorn, R. and Knopp, P.  Concerning nonnegative matrices and doubly stochastic matrices.  _Pacific Journal of Mathematics_ , 21(2):343–348, 1967.
  * Son et al. (2023) Son, J., Kim, M., Kim, H., and Park, J.  Meta-sage: Scale meta-learning scheduled adaptation with guided exploration for mitigating scale shift on combinatorial optimization.  In _ICML_ , 2023.
  * Straka (2017) Straka, M.  Poisson binomial distribution for python (github repository).  https://github.com/tsakim/poibin, 2017.
  * Sun et al. (2023) Sun, H., Goshvadi, K., Nova, A., Schuurmans, D., and Dai, H.  Revisiting sampling for combinatorial optimization.  In _ICML_ , 2023.
  * Sun & Yiming (2023) Sun, Z. and Yiming, Y.  DIFUSCO: Graph-based diffusion solvers for combinatorial optimization.  In _NeurIPS_ , 2023.
  * Viquerat et al. (2023) Viquerat, J., Duvigneau, R., Meliga, P., Kuhnle, A., and Hachem, E.  Policy-based optimization: Single-step policy gradient method seen as an evolution strategy.  _Neural Computing and Applications_ , 35(1):449–467, 2023.
  * Wang & Li (2023) Wang, H. and Li, P.  Unsupervised learning for combinatorial optimization needs meta-learning.  In _ICLR_ , 2023.
  * Wang et al. (2022) Wang, H. P., Wu, N., Yang, H., Hao, C., and Li, P.  Unsupervised learning for combinatorial optimization with principled objective relaxation.  In _NeurIPS_ , 2022.
  * Wang et al. (2023) Wang, R., Shen, L., Chen, Y., Yang, X., Tao, D., and Yan, J.  Towards one-shot neural combinatorial solvers: Theoretical and empirical notes on the cardinality-constrained case.  In _ICLR_ , 2023.
  * Wang (1993) Wang, Y. H.  On the number of successes in independent trials.  _Statistica Sinica_ , pp. 295–312, 1993.
  * Xiao et al. (2024) Xiao, Y., Wang, D., Li, B., Wang, M., Wu, X., Zhou, C., and Zhou, Y.  Distilling autoregressive models to obtain high-performance non-autoregressive solvers for vehicle routing problems with faster inference speed.  In _AAAI_ , 2024.
  * Xu et al. (2007) Xu, K., Boussemart, F., Hemery, F., and Lecoutre, C.  Random constraint satisfaction: Easy generation of hard (satisfiable) instances.  _Artificial intelligence_ , 171(8-9):514–534, 2007.
  * Yanez & Ramirez (2003) Yanez, J. and Ramirez, J.  The robust coloring problem.  _European Journal of Operational Research_ , 148(3):546–558, 2003.
  * Yannakakis (1988) Yannakakis, M.  Expressing combinatorial optimization problems by linear programs.  In _Proceedings of the twentieth annual ACM symposium on Theory of computing_ , pp. 223–228, 1988.
  * Ye et al. (2023a) Ye, H., Wang, J., Cao, Z., Liang, H., and Li, Y.  DeepACO: Neural-enhanced ant systems for combinatorial optimization.  In _NeurIPS_ , 2023a.
  * Ye et al. (2024) Ye, H., Wang, J., Liang, H., Cao, Z., Li, Y., and Li, F.  Glop: Learning global partition and local construction for solving large-scale routing problems in real-time.  In _AAAI_ , 2024.
  * Ye et al. (2023b) Ye, X., Yan, G., and Yan, J.  Towards quantum machine learning for constrained combinatorial optimization: a quantum qap solver.  In _ICML_ , 2023b.
  * Zhang et al. (2023) Zhang, D., Dai, H., Malkin, N., Courville, A., Bengio, Y., and Pan, L.  Let the flows tell: Solving graph combinatorial optimization problems with gflownets.  In _NeurIPS_ , 2023.
  * Zhong et al. (2015) Zhong, C., Malinen, M., Miao, D., and Fränti, P.  A fast minimum spanning tree algorithm based on k-means.  _Information Sciences_ , 295:1–17, 2015.

##  Appendix A Proofs

Here, we provide proof for each theoretical statement in the main text.

######  Theorem 1 (Expectations are all you need).

For any $g:\\{0,1\\}^{n}\to\mathbb{R}$, $\tilde{g}:[0,1]^{n}\to\mathbb{R}$
with $\tilde{g}(p)=\mathbb{E}_{X\sim p}g(X)$ is differentiable and entry-wise
concave w.r.t. $p$.

###### Proof.

For any $p$ and $i$, we have

$\displaystyle\tilde{g}(p)$ $\displaystyle=\mathbb{E}_{X\sim p}g(X)$
$\displaystyle=\sum_{X\in\\{0,1\\}^{n}}\Pr\nolimits_{p}[X]g(X)$
$\displaystyle=\sum_{X}\prod_{v\in V_{X}}p_{v}\prod_{u\in[n]\setminus
V_{X}}(1-p_{u})g(X)$ $\displaystyle=\sum_{X\colon i\in V_{X}}\left(\prod_{v\in
V_{X},v\neq i}p_{v}\prod_{u\in[n]\setminus
V_{X}}(1-p_{u})\right)p_{i}g(X)+\sum_{X\colon i\notin V_{X}}\left(\prod_{v\in
V_{X}}p_{v}\prod_{u\in[n]\setminus V_{X},u\neq
i}(1-p_{u})\right)(1-p_{i})g(X)$ $\displaystyle=p_{i}\sum_{X\colon i\in
V_{X}}\prod_{v\in V_{X},v\neq i}p_{v}\prod_{u\in[n]\setminus
V_{X}}(1-p_{u})g(X)+(1-p_{i})\sum_{X\colon i\notin V_{X}}\prod_{v\in
V_{X}}p_{v}\prod_{u\in[n]\setminus V_{X},u\neq i}(1-p_{u})g(X)$
$\displaystyle=p_{i}\tilde{g}(\operatorname{der}(i,1;p))+(1-p_{i})\tilde{g}(\operatorname{der}(i,0;p))$
$\displaystyle\geq
p_{i}\tilde{g}(\operatorname{der}(i,1;p))+(1-p_{i})\tilde{g}(\operatorname{der}(i,0;p)),$

completing the proof on entry-wise concavity. Regarding differentiability,
since

$\mathbb{E}_{X\sim p}g(X)=\sum_{X\in\\{0,1\\}^{n}}\Pr\nolimits_{p}[X]g(X),$

it suffices to show that

$\Pr\nolimits_{p}[X]g(X)=\prod_{v\in V_{X}}p_{v}\prod_{u\in[n]\setminus
V_{X}}(1-p_{u})g(X)$

is differentiable w.r.t $p$ for each $X\in\\{0,1\\}^{n}$. Indeed, fix any $X$,
$\prod_{v\in V_{X}}p_{v}\prod_{u\in[n]\setminus V_{X}}(1-p_{u})g(X)$ is a
polynomial of $p_{i}$’s, and is thus differentiable w.r.t. $p$. ∎

######  Theorem 2 (Goodness of greedy derandomization).

For any entry-wise concave $\tilde{f}$ and any $p_{\mathrm{o}}\in[0,1]^{n}$,
the above process of greedy derandomization can always reach a point where the
final $p_{\mathrm{final}}$ is (G1) discrete (i.e.,
$p_{\mathrm{final}}\in\\{0,1\\}^{n}$), (G2) no worse than $p_{\mathrm{o}}$
(i.e., $\tilde{f}(p_{\mathrm{final}})\leq\tilde{f}(p_{\mathrm{o}})$), and (G3)
a local minimum (i.e.,
$\tilde{f}(p_{\mathrm{final}})\leq\min_{(i,x)\in[n]\times\\{0,1\\}}\tilde{f}(\operatorname{der}(i,x;p_{\mathrm{final}}))$).

###### Proof of Theorem 2.

First, we claim that for any non-discrete
$p_{\mathrm{cur}}\notin\\{0,1\\}^{n}$, we can always derandomize it through a
series of local derandomization while the value of $\tilde{f}$ does not
increase. This is guaranteed by the entry-wise concavity of $\tilde{f}$.
Specifically, since

$p_{i}\tilde{f}(\operatorname{der}(i,1;p))+(1-p_{i})\tilde{f}(\operatorname{der}(i,0;p))\leq\tilde{f}(p),\forall
p,i,$

we have

$\min(\operatorname{der}(i,1;p),\operatorname{der}(i,0;p))\leq\tilde{f}(p),\forall
p,i,$

which implies that we can always derandomize a non-discrete entry without
increasing the value of $\tilde{f}$. Therefore, if we greedily improve
$\tilde{f}$ via local derandomization, we can always terminate at a discrete
point, completing the proof for point (G1). Point (G2) holds since at each
step we make sure that the value of $\tilde{f}$ does not increase. Point (G3)
holds from the way we conduct local derandomization. Specifically, if the
current $p_{\mathrm{cur}}$ is not a local minimum, we can always find a
possible local derandomization step to proceed with the process while strictly
decreasing the value of $\tilde{f}$. ∎

######  Lemma 1.

$\hat{f}_{\mathrm{card}}$ is a tight upper bound of $\mathbb{1}[\lvert
V_{X}\rvert\notin C_{c}]$.

###### Proof.

When $X\notin C_{c}$, $\lvert V_{X}\rvert\neq k,\forall k\in C_{c}$, and thus
$\hat{f}_{\mathrm{card}}(X;C_{c})=\min_{k\in C_{c}}\lvert\lvert
V_{X}\rvert-k\rvert>0$ and thus $\hat{f}_{\mathrm{card}}(X;C_{c})\geq 1$ since
$\lvert V_{X}\rvert\neq k$ is an integer. When $X\in C_{c}$, $\exists k\in
C_{c},\lvert V_{X}\rvert=k$ and thus
$\hat{f}_{\mathrm{card}}(X;C_{c})=\min_{k\in C_{c}}\lvert\lvert
V_{X}\rvert-k\rvert=0$. ∎

######  Lemma 2 (IDs of $\tilde{f}_{\mathrm{card}}$).

For any $p,i,t$, let $q_{s}\coloneqq\Pr_{X\sim p}[\lvert V_{X}\rvert=s]$ and
$q^{\prime}_{s}\coloneqq\Pr_{X\sim p}[\lvert
V_{X}\setminus\\{i\\}\rvert=s],\forall s$,

$\displaystyle q^{\prime}_{t}$
$\displaystyle=(1-p_{i})^{-1}\sum_{s=0}^{t}q_{s}\left(\frac{p_{i}}{p_{i}-1}\right)^{t-s}\text{~{}(if~{}
$p_{i}\neq 1$)}$
$\displaystyle=(p_{i})^{-1}\sum_{s=0}^{n-t-1}q_{t+s+1}\left(\frac{p_{i}-1}{p_{i}}\right)^{s}\text{~{}(if~{}
$p_{i}\neq 0$)}.$

Based on that,

$\begin{cases}\Delta\tilde{f}_{\mathrm{card}}(i,0,p;C_{c})=\sum_{t\in[n]\setminus
C_{c}}(q^{\prime}_{t}-q_{t})\min_{k\in C_{c}}\lvert t-k\rvert,\\\
\Delta\tilde{f}_{\mathrm{card}}(i,1,p;C_{c})=\sum_{t\in[n]\setminus
C_{c}}(q^{\prime}_{t-1}-q_{t})\min_{k\in C_{c}}\lvert t-k\rvert.\end{cases}$

###### Proof.

Fix any $i\in[n]$ and any $p\in[0,1]^{n}$, we have

$\begin{cases}\Pr_{X\sim p}[\lvert V_{X}\rvert=0]=\Pr_{X\sim p}[\lvert
V_{X}\setminus\\{i\\}\rvert=0](1-p_{i})\\\ \Pr_{X\sim p}[\lvert
V_{X}\rvert=t]=\Pr_{X\sim p}[\lvert
V_{X}\setminus\\{i\\}\rvert=t](1-p_{i})+\Pr_{X\sim p}[\lvert
V_{X}\setminus\\{i\\}\rvert=t-1]p_{i},\forall t\\\ \Pr_{X\sim p}[\lvert
V_{X}\rvert=n]=\Pr_{X\sim p}[\lvert
V_{X}\setminus\\{i\\}\rvert=n-1]p_{i}\end{cases}.$ (3)

Let $q_{s}$ denote $\Pr_{X\sim p}[\lvert V_{X}\rvert=s]$ for each $s$ as in
the statement, and also let $\tilde{q}_{s}$ denote $\Pr_{X\sim p}[\lvert
V_{X}\setminus\\{i\\}\rvert=s]$. By Equation (3), if we start from
$q_{0}=\tilde{q}_{0}(1-p_{i})$, we have

$\tilde{q}_{0}=\frac{q_{0}}{1-p_{i}},\tilde{q}_{1}=\frac{q_{1}-p_{i}\tilde{q}_{0}}{1-p_{i}}=\frac{q_{1}(1-p_{i})-q_{0}p_{i}}{(1-p_{i})^{2}},\cdots,$

which satisfies
$\tilde{q}_{t}=(1-p_{i})^{-1}\sum_{s=0}^{t}q_{s}\left(\frac{p_{i}}{p_{i}-1}\right)^{t-s}$.
Now, if

$\tilde{q}_{t}=(1-p_{i})^{-1}\sum_{s=0}^{t}q_{s}\left(\frac{p_{i}}{p_{i}-1}\right)^{t-s}$

holds for all $t\leq T-1$, we aim to show that it also holds for $t=T$, which
shall prove the statement by mathematical induction. Indeed, we have

$\tilde{q}_{T}=\frac{q_{T}-p_{i}\tilde{q}_{T-1}}{1-p_{i}}=\frac{q_{T}-p_{i}(1-p_{i})^{-1}\sum_{s=0}^{T-1}q_{s}\left(\frac{p_{i}}{p_{i}-1}\right)^{T-1-s}}{1-p_{i}}=(1-p_{i})^{-1}\sum_{s=0}^{T}q_{s}\left(\frac{p_{i}}{p_{i}-1}\right)^{T-s},$

completing the proof. If we start from $q_{n}=\tilde{q}_{n-1}p_{i}$, we can
obtain the another term (i.e.,
$(p_{i})^{-1}\sum_{s=0}^{n-t-1}q_{t+s+1}\left(\frac{p_{i}-1}{p_{i}}\right)^{s}$)
in the statement in a similar way.

In practice, we use
$(1-p_{i})^{-1}\sum_{s=0}^{t}q_{t-s}\left(\frac{p_{i}}{p_{i}-1}\right)^{t-s}$
for $0\leq p_{i}\leq 0.5$ and
$(p_{i})^{-1}\sum_{s=0}^{n-t-1}q_{t+s+1}\left(\frac{p_{i}-1}{p_{i}}\right)^{s}$
for $0.5<p_{i}\leq 1$, which results in higher numerical stability. ∎

######  Lemma 3.

$\hat{f}_{\mathrm{ms}}$ is a tight upper bound of ${f}_{\mathrm{ms}}$.

###### Proof.

As mentioned in Rem. 3, since $\hat{f}_{\mathrm{ms}}={f}_{\mathrm{ms}}$,
$\hat{f}$ is a tight upper bound of ${f}_{\mathrm{ms}}$. ∎

######  Lemma 4.

For any $p\in[0,1]^{n}$, $\mathbb{E}_{X\sim
p}\hat{f}_{\mathrm{ms}}(X;i,h)=p_{v_{1}}d_{1}+(1-p_{v_{1}})p_{v_{2}}d_{2}+\cdots+(\prod_{j=1}^{n-1}(1-p_{v_{j}}))p_{v_{n}}d_{n}$.

###### Proof.

By the definition of expectation,

$\mathbb{E}_{X\sim p}\hat{f}_{\mathrm{ms}}(X;i,h)=\sum_{t}\Pr[\min_{v_{X}\in
V_{X}}h(i,v_{X})=d_{t}]d_{t},$

where $\min_{v_{X}\in V_{X}}h(i,v_{X})=d_{t}$ if and only if
$v_{t^{\prime}}\notin V_{x}$ for each $t^{\prime}<t$ and $v_{t}\in V_{x}$,
which has probability $(\prod_{j=1}^{t-1}(1-p_{v_{j}}))p_{v_{t}}$. Hence,

$\mathbb{E}_{X\sim
p}\hat{f}_{\mathrm{ms}}(X;i,h)=p_{v_{1}}d_{1}+(1-p_{v_{1}})p_{v_{2}}d_{2}+\cdots+(\prod_{j=1}^{n-1}(1-p_{v_{j}}))p_{v_{n}}d_{n}.$

∎

######  Lemma 5 (IDs of $\tilde{f}_{\mathrm{ms}}$).

For any $p\in[0,1]^{n}$ and $j\in[n]$, let
$q_{j}\coloneqq(\prod_{k=1}^{j-1}(1-p_{v_{k}}))p_{v_{j}}$, the coefficient of
$d_{j}$ in $\tilde{f}_{\mathrm{ms}}$. Then

$\begin{cases}\Delta\tilde{f}_{\mathrm{ms}}(v_{j},0,p;i,h)=-q_{j}d_{j}+\frac{p_{v_{j}}}{1-p_{v_{j}}}\sum_{j^{\prime}>j}q_{j^{\prime}}d_{j^{\prime}},\\\
\Delta\tilde{f}_{\mathrm{ms}}(v_{j},1,p;i,h)=\sum_{j^{\prime}>j}q_{j^{\prime}}(d_{j}-d_{j^{\prime}}).\end{cases}$

###### Proof.

When $p^{\prime}=\operatorname{der}(v_{j},0;p)$, we have

$\displaystyle\tilde{f}_{\mathrm{ms}}(p^{\prime};i,h)$
$\displaystyle=p^{\prime}_{v_{1}}d_{1}+(1-p^{\prime}_{v_{1}})p^{\prime}_{v_{2}}d_{2}+\cdots+(\prod_{s=1}^{n-1}(1-p^{\prime}_{v_{s}}))p^{\prime}_{v_{n}}d_{n}$
$\displaystyle=\sum_{s<j}\prod_{k=1}^{s-1}(1-p_{v_{k}})p_{v_{s}}d_{s}+0+\sum_{t>j}\prod_{1\leq
k\leq t-1,k\neq j}(1-p_{v_{k}})p_{v_{t}}d_{t}$
$\displaystyle=\sum_{s<j}q_{s}d_{s}+0+\sum_{j^{\prime}>j}\frac{1}{1-p_{v_{j}}}q_{j^{\prime}}d_{j^{\prime}}$
$\displaystyle=\sum_{s=1}^{n}q_{s}d_{s}-q_{j}d_{j}+\sum_{j^{\prime}>j}\frac{p_{v_{j}}}{1-p_{v_{j}}}q_{j^{\prime}}d_{j^{\prime}}$
$\displaystyle=\tilde{f}_{\mathrm{ms}}(p;i,h)-q_{j}d_{j}+\frac{p_{v_{j}}}{1-p_{v_{j}}}\sum_{j^{\prime}>j}q_{j^{\prime}}d_{j^{\prime}}.$

When $p^{\prime}=\operatorname{der}(v_{j},1;p)$, we have

$\displaystyle\tilde{f}_{\mathrm{ms}}(p^{\prime};i,h)$
$\displaystyle=p^{\prime}_{v_{1}}d_{1}+(1-p^{\prime}_{v_{1}})p^{\prime}_{v_{2}}d_{2}+\cdots+(\prod_{s=1}^{n-1}(1-p^{\prime}_{v_{s}}))p^{\prime}_{v_{n}}d_{n}$
$\displaystyle=\left(\sum_{s<j}\prod_{k=1}^{s-1}(1-p_{v_{k}})p_{v_{s}}d_{s}\right)+\prod_{k^{\prime}=1}^{j-1}(1-p_{v_{k}^{\prime}})d_{j}$
$\displaystyle=\left(\sum_{s<j}\prod_{k=1}^{s-1}(1-p_{v_{k}})p_{v_{s}}d_{s}\right)+\sum_{j^{\prime}\geq
j}\prod_{k^{\prime}=1}^{j^{\prime}-1}(1-p_{v_{k^{\prime}}})p_{v_{j^{\prime}}}d_{j}$
$\displaystyle=\sum_{s<j}q_{s}d_{s}+\sum_{j^{\prime}\geq
j}q_{j^{\prime}}d_{j}$
$\displaystyle=\sum_{s=1}^{n}q_{s}d_{s}+0+\sum_{j^{\prime}>j}q_{j^{\prime}}(d_{j}-d_{j^{\prime}})$
$\displaystyle=\tilde{f}_{\mathrm{ms}}(p;i,h)+\sum_{j^{\prime}>j}q_{j^{\prime}}(d_{j}-d_{j^{\prime}}).$

∎

######  Lemma 6.

$\hat{f}_{\mathrm{cv}}$ is a TUB of $\mathbb{1}(X\notin\mathcal{C})$.

###### Proof.

As mentioned in Rem. 3, since
$\hat{f}_{\mathrm{cv}}=\mathbb{1}(X\notin\mathcal{C})$,
$\hat{f}_{\mathrm{cv}}$ is a tight upper bound of
$\mathbb{1}(X\notin\mathcal{C})$. ∎

######  Lemma 7.

For any $p\in[0,1]^{n}$ and $i\in[n]$, $\Pr_{X\sim p}[\\{v_{X}\in
V_{X}\colon(v_{X},i)\in E\\}\neq\emptyset]=\prod_{v\in[n]\colon(v,i)\in
E}(1-p_{v})$.

###### Proof.

We decompose the event $\\{v_{X}\in V_{X}\colon(v_{X},i)\in
E\\}\neq\emptyset=\bigwedge_{v\colon(v,i)\in E}(v\notin V_{X})$. Since the
subevents $v\notin V_{X}$ are mutually independent,

$\Pr\nolimits_{X\sim p}[\\{v_{X}\in V_{X}\colon(v_{X},i)\in
E\\}\neq\emptyset]=\prod_{v\in[n]\colon(v,i)\in E}(1-p_{v}).$

∎

######  Lemma 8 (IDs of $\tilde{f}_{\mathrm{cv}}$).

For any $p\in[0,1]^{n}$ and $i\in[n]$, if $(i,j)\notin E$, then
$\Delta\tilde{f}_{\mathrm{cv}}(j,0,p;i)=\Delta\tilde{f}_{\mathrm{cv}}(j,1,p;i)=0$;
if $(i,j)\in E$, then

$\begin{cases}\Delta\tilde{f}_{\mathrm{cv}}(j,0,p;i)=p_{j}\prod_{v\in
N_{i},v\neq j}(p_{v}-1),\\\
\Delta\tilde{f}_{\mathrm{cv}}(j,1,p;i)=-\tilde{f}_{\mathrm{cv}}(p;i).\end{cases}$

###### Proof.

If $(i,j)\notin E$, the value of $p_{j}$ does not affect
$\tilde{f}_{\mathrm{cv}}(p;i)$ since $p_{j}$ is not involved in the value of
$\tilde{f}_{\mathrm{cv}}(p;i)$. When $(i,j)\in E$, if
$p^{\prime}=\operatorname{der}(j,0;p)$,

$\prod_{v\in N_{i}}(1-p^{\prime}_{v})=\prod_{v\in N_{i},v\neq
j}(1-p_{v})=\tilde{f}_{\mathrm{cv}}(p;i)-p_{j}\prod_{v\in N_{i},v\neq
j}(1-p_{v});$

if $p^{\prime}=\operatorname{der}(j,1;p)$,

$\prod_{v\in N_{i}}(1-p^{\prime}_{v})=0.$

∎

######  Lemma 10.

For any $p\in[0,1]^{n}$, $\mathbb{E}_{X\sim
p}\hat{f}_{\mathrm{cq}}(X)=\sum_{(u,v)\in\binom{V}{2}\setminus E}p_{u}p_{v}$.

###### Proof.

By linearity of expectation and double counting,

$\hat{f}_{\mathrm{cq}}(X)=\sum_{(u,v)\in\binom{V_{X}}{2}}\mathbb{1}[(u,v)\notin
E]=\sum_{(u,v)\notin E}\mathbb{1}[(u,v)\in\binom{V_{X}}{2}].$

Then we take the expectation and use the mutual independency among $v\in
V_{X}$’s to get

$\mathbb{E}_{X\sim p}[\hat{f}_{\mathrm{cq}}(X)]=\sum_{(u,v)\notin
E}\Pr[(u,v)\in\binom{V_{X}}{2}]=\sum_{(u,v)\notin E}p_{u}p_{v}.$

∎

######  Lemma 11 (IDs of $\tilde{f}_{\mathrm{cq}}$).

For any $p\in[0,1]^{n}$ and $i\in[n]$,

$\begin{cases}\Delta\tilde{f}_{\mathrm{cq}}(i,0,p)=-p_{i}\sum_{j\in[n],j\neq
i,(i,j)\notin E}p_{j},\\\
\Delta\tilde{f}_{\mathrm{cq}}(i,1,p)=(1-p_{i})\sum_{j\in[n],j\neq
i,(i,j)\notin E}p_{j}.\end{cases}$

###### Proof.

When $p^{\prime}=\operatorname{der}(i,0;p)$,

$\tilde{f}_{cq}(p^{\prime})=\sum_{(u,v)\in\binom{V}{2}\setminus
E}p^{\prime}_{u}p^{\prime}_{v}=\sum_{(u,v)\in\binom{V}{2}\setminus E,u\neq
i,v\neq i}p_{u}p_{v}=\tilde{f}_{cq}(p)-p_{i}\sum_{j\in[n],j\neq i,(i,j)\notin
E}p_{j}.$

When $p^{\prime}=\operatorname{der}(i,1;p)$,

$\tilde{f}_{cq}(p^{\prime})=\sum_{(u,v)\in\binom{V}{2}\setminus E,u\neq
i,v\neq i}p_{u}p_{v}+\sum_{(i,j)\in\binom{V}{2}\setminus
E}p_{j}=\tilde{f}_{cq}(p)+(1-p_{i})\sum_{j\in[n],j\neq i,(i,j)\notin E}p_{j}.$

∎

######  Lemma 12.

$\hat{g}_{1}$ is a TUB of $g_{1}$ and $\hat{f}_{2}$ is a TUB of $f_{2}$.

###### Proof.

When $X\notin\mathcal{C}_{1}$, at least one edge in $E_{h}$ is violated, i.e.,
$\hat{g}_{1}(X)\geq 1$. When $X\in\mathcal{C}_{1}$, no edge in $E_{h}$ is
violated, i.e., $\hat{g}_{1}(X)=0$.

$\hat{f}_{2}=f_{2}$ is a TUB of itself. ∎

######  Lemma 13.

For any $p\in[0,1]^{n\times c}$, $\tilde{f}_{2}(p)=\mathbb{E}_{X\sim
p}\hat{f}_{2}(X)=-\sum_{e=(u,v)\in
E_{s}}\sum_{r=0}^{c-1}p_{ur}p_{vr}\log(1-P(e))$ and
$\tilde{g}_{1}(p)=\mathbb{E}_{X\sim p}\hat{g}_{1}(X)=\sum_{(u,v)\in
E_{h}}\sum_{r=0}^{c-1}p_{ur}p_{vr}$.

###### Proof.

We have

$\displaystyle\mathbb{E}_{X\sim p}\hat{f}_{2}(X)$
$\displaystyle=\mathbb{E}_{X\sim p}-\sum_{e=(u,v)\in E_{s}\colon
X_{u}=X_{v}}\log(1-P(e))$ $\displaystyle=\mathbb{E}_{X\sim p}-\sum_{e=(u,v)\in
E_{s}}\mathbb{1}(X_{u}=X_{v})\log(1-P(e))$ $\displaystyle=-\sum_{e=(u,v)\in
E_{s}}\Pr\nolimits_{X\sim p}[X_{u}=X_{v}]\log(1-P(e))$
$\displaystyle=-\sum_{e=(u,v)\in E_{s}}\sum_{r=0}^{c-1}\Pr\nolimits_{X\sim
p}[\text{both $u$ and $v$ have color $r$}]\log(1-P(e))$
$\displaystyle=-\sum_{e=(u,v)\in
E_{s}}\sum_{r=0}^{c-1}p_{ur}p_{vr}\log(1-P(e))$

and

$\displaystyle\mathbb{E}_{X\sim p}\hat{g}_{1}(X)$
$\displaystyle=\mathbb{E}_{X\sim p}\lvert\\{(u,v)\in E_{h}\colon
X_{u}=X_{v}\\}\rvert$ $\displaystyle=\mathbb{E}_{X\sim p}\sum_{(u,v)\in
E_{h}}\mathbb{1}(X_{u}=X_{v})$ $\displaystyle=\sum_{(u,v)\in
E_{h}}\Pr\nolimits_{X\sim p}[X_{u}=X_{v}]$ $\displaystyle=\sum_{(u,v)\in
E_{h}}\Pr\nolimits_{X\sim p}[\text{both $u$ and $v$ have color $r$}]$
$\displaystyle=\sum_{(u,v)\in E_{h}}\sum_{r=0}^{c-1}p_{ur}p_{vr}.$

∎

######  Lemma 14 (IDs of the terms in $\tilde{f}_{\mathrm{RC}}$).

For any $p\in[0,1]^{n\times c}$, $i\in[n]$, and $x\in d$,
$\Delta\tilde{g}_{1}(i,x;p)=\sum_{x^{\prime}\in
d\setminus\\{x\\}}p_{ix^{\prime}}\sum_{(i,j)\in
E_{h}}(p_{jx}-p_{jx^{\prime}})$ and
$\Delta\tilde{f}_{2}(i,x;p)=\sum_{x^{\prime}\in
d\setminus\\{x\\}}p_{ix^{\prime}}\sum_{(i,j)\in
E_{s}}(p_{jx^{\prime}}-p_{jx})\log(1-P(i,j))$.

###### Proof.

When $p^{\prime}=\operatorname{der}(i,x;p)$,

$\displaystyle\tilde{g}_{1}(\operatorname{der}(i,x;p))$
$\displaystyle=\sum_{(u,v)\in
E_{h}}\sum_{r=0}^{c-1}p^{\prime}_{ur}p^{\prime}_{vr}$
$\displaystyle=\sum_{(u,v)\in
E_{h}}\sum_{r=0}^{c-1}p^{\prime}_{ur}p^{\prime}_{vr}$
$\displaystyle=\sum_{(u,v)\in E_{h},u\neq i,v\neq
i}\sum_{r=0}^{c-1}p_{ur}p_{vr}+\sum_{(i,j)\in E_{h}}p_{jx}$
$\displaystyle=\tilde{g}_{1}(p)+(1-p_{ix})\sum_{(i,j)\in
E_{h}}p_{jx}-\sum_{x^{\prime}\in
d\setminus\\{x\\}}p_{ix^{\prime}}\sum_{(i,j)\in E_{h}}p_{jx^{\prime}}$
$\displaystyle=\tilde{g}_{1}(p)+\sum_{x^{\prime}\in
d\setminus\\{x\\}}p_{ix^{\prime}}\sum_{(i,j)\in
E_{h}}(p_{jx}-p_{jx^{\prime}}),$

where $1-p_{ix}=\sum_{x^{\prime}\in d\setminus\\{x\\}}p_{ix^{\prime}}$ has
been used. Similarly,

$\displaystyle\tilde{f}_{2}(\operatorname{der}(i,x;p))$
$\displaystyle=-\sum_{e=(u,v)\in
E_{s}}\sum_{r}p^{\prime}_{ur}p^{\prime}_{vr}\log(1-P(e))$
$\displaystyle=-\sum_{e=(u,v)\in E_{s},u\neq i,v\neq
i}\sum_{r}p^{\prime}_{ur}p^{\prime}_{vr}\log(1-P(e))-\sum_{e=(i,j)\in
E_{s}}p_{jx}\log(1-P(e))$
$\displaystyle=\tilde{f}_{2}(p)-(1-p_{ix})\sum_{(i,j)\in
E_{s}}p_{jx}\log(1-P(i,j))+\sum_{x^{\prime}\in
d\setminus\\{x\\}}p_{ix^{\prime}}\sum_{(i,j)\in
E_{s}}p_{jx^{\prime}}\log(1-P(i,j))$
$\displaystyle=\tilde{f}_{2}(p)+\sum_{x^{\prime}\in
d\setminus\\{x\\}}p_{ix^{\prime}}\sum_{(i,j)\in
E_{s}}(p_{jx^{\prime}}-p_{jx})\log(1-P(i,j)).$

∎

##  Appendix B Additional Details on the Background

We would like to provide some additional details on the background (Section
2.2).

###  B.1 On the “Differentiable Optimization” in the Pipeline (Section 2.2.1)

One can directly optimize a probabilistic decision $p$ on each test instance
$G_{\mathrm{test}}$, i.e., aim to find
$p^{*}\approx\mathop{\mathrm{arg\,min}}_{p}\tilde{f}(p;G_{\mathrm{test}})$.
One can also train an encoder (e.g., a graph neural network) parameterized by
parameters $\theta$ on a training set $\mathcal{D_{\mathrm{train}}}$ to learn
to output “good” (probabilistic) decisions for each training instance, i.e.,
aim to find
$\theta^{*}\approx\mathop{\mathrm{arg\,min}}_{\theta}\sum_{G\in\mathcal{D}_{\mathrm{train}}}\tilde{f}(\operatorname{ENCODER}(G;{\theta});G)$.
Such a trained encoder can be applied to each test instance
$G_{\mathrm{test}}$ and output a (probabilistic) decision
$p=\operatorname{ENCODER}(G_{\mathrm{test}};{\theta})$. Training such an
encoder is optional, but if trained well, it can save time for unseen cases
since we do not need to optimize $p$ for each test instance from
scratch.666See some related discussions at
https://github.com/Stalence/erdos_neu. Even when using such an encoder, one
can still further directly optimize the probabilistic decisions on each test
instance. See more discussions on inductive settings and transductive settings
in Appendix G.1.

###  B.2 Formal Theoretical Results in the Existing Works

Here, we would like to provide the detailed formal theoretical results in the
existing works by (Karalias & Loukas, 2020) and (Wang et al., 2022). Recall
that (Karalias & Loukas, 2020) showed a quality guarantee by random sampling.

######  Theorem 3 (Theorem 1 by (Karalias & Loukas, 2020)).

Assume that $f$ is non-negative.777We can always ensure this for any bounded
$f$ by adding a sufficiently large positive constant to $f$. Fix any
$\beta>\max_{X\in\mathcal{C}}f(X;G)$, $\epsilon>0$, and $t\in(0,1]$ such that
$(1-t)\epsilon<\beta$. For each $p\in[0,1]^{n}$, if $\tilde{f}(p;G)<\beta$,
then $\Pr_{X\sim p}[f(X;G)<\epsilon\land X\in\mathcal{C}]\geq t$.

Recall that (Wang et al., 2022) further proposed iterative rounding. Also,
recall the following definitions: given a probability decision
$p\in[0,1]^{n}$, an index $i\in[n]$, and $x\in\\{0,1\\}$, let
$\operatorname{der}(i,x;p)$ denoted the result after the $i$-th entry of $p$
being locally derandomized as $x$. Formally,
$\operatorname{der}(i,x;p)_{i}=x$, and
$\operatorname{der}(i,x;p)_{j}=p_{j},\forall j\neq i$. A probabilistic
objective $\tilde{f}$ is entry-wise concave if
$p_{i}\tilde{f}(\operatorname{der}(i,1;p);G)+(1-p_{i})\tilde{f}(\operatorname{der}(i,0;p);G)\leq\tilde{f}(p;G),\forall
G,p,i$.

######  Theorem 4 (Theorem 1 by (Wang et al., 2022)).

If $\tilde{f}(p)\geq\mathbb{E}_{X\sim p}f(X)+\beta\Pr_{X\sim
p}[X\notin\mathcal{C}],\forall p$ and $\tilde{f}$ is entry-wise concave and
non-negative with
$\beta>\max(\tilde{f}(p_{\mathrm{init}}),\max_{X\in\mathcal{C}}f(X))$, then
for any permutation $\pi:[n]\to[n]$, starting from
$p_{\mathrm{cur}}=p_{\mathrm{init}}$ and for $i\in[n]$ doing (1)
$x^{*}\leftarrow\mathop{\mathrm{arg\,min}}_{x\in\\{0,1\\}}\tilde{f}(\operatorname{der}(\pi(i),x;p_{\mathrm{cur}}))$
and (2)
$p_{\mathrm{cur}}\leftarrow\operatorname{der}(i,x^{*};p_{\mathrm{cur}})$ will
finally give a discrete $p_{\mathrm{final}}\in\mathcal{C}$ such that
$f(p_{\mathrm{final}})<\tilde{f}(p_{\mathrm{init}})$.

###  B.3 Prevalent Conditions in Existing Works

As mentioned in Section 4, several conditions have been encountered in
existing works. Here, for each condition analyzed in Section 4, we shall
discuss how the existing works try to handle it.

Cardinality constraints. (Wang et al., 2023) specifically considered
cardinality constraints. However, they used optimal transport soft top-$k$
instead of the probabilistic-method UL4CO we focus on in this work. Also, our
derivation is more general since it can handle general cardinality constraints
other than choosing a specific number of entities (i.e., top-$k$). (Wang et
al., 2023) claimed that cardinality constraints cannot be handled in the EGN
pipeline, but this work shows that cardinality constraints can actually be
properly handled by our derivations. (Karalias & Loukas, 2020) used iterative
re-scaling to impose cardinality constraints. However, the operation involves
clamping which may cause gradient vanishing and it is only guaranteed that the
summation of the probabilities is within the desired range (i.e., cardinality
constraints). However, this does not mean the whole distribution represented
by the probabilities is within the desired range.888For example, if there are
$n=10$ nodes and we want to choose $k=2$ nodes. After re-scaling we might get
probabilities $(\frac{1}{5},\frac{1}{5},\ldots,\frac{1}{5})$ with summation
exactly equal to $2$, but $\Pr[\text{exactly $2$ nodes are
chosen}]=\binom{10}{2}\times(\frac{1}{5})^{2}\times(\frac{4}{5})^{8}\approx
0.302$ is far lower than $1$.

Minimum (maximum) w.r.t. a subset. (Wang et al., 2023) also encountered such a
condition in the facility location problem which they considered. They used
the $\operatorname{softmin}$ to approximate the $\min$ operation, which indeed
provides an upper bound. However, the result of $\operatorname{softmin}$ is
not entry-wise concave, and thus fails to satisfy the good property required
by (Wang et al., 2022), while our derivation satisfies all the good
properties.

Covering. (Wang et al., 2023) also encountered such a condition in the maximum
coverage problem which they considered. They used $\min(1,\sum_{v\in
N_{i}}p_{v})$ as an approximation for the probability of $i$ being covered,
where $N_{i}=\\{v\colon(v,i)\in E\\}$. In other words, they used
$\max(0,1-\sum_{v\in N_{i}}p_{v}))$ to approximate the probability that $i$ is
not covered. As we have shown, the probability that $i$ is not covered is
exactly $\prod_{v\in N_{i}}(1-p_{v})$. However, $\max(0,1-\sum_{v\in
N_{i}}p_{v}))$ is not an upper bound of $\prod_{v\in N_{i}}(1-p_{v})$ but a
lower bound. Therefore, the derivation by (Wang et al., 2023) does not satisfy
the conditions required for the probabilistic-method UL4CO pipeline and thus
does not satisfy the good properties.

Cliques (or independent sets). (Karalias & Loukas, 2020) also considered the
maximum clique problem, while our high-level targets provide insights into
interpreting the derivation. Our derivation of incremental differences is
novel, and we also showed how we can extend this to non-binary cases.

Other problems. Recently, UL4CO on the traveling salesman problem (TSP) has
also been considered (Gaile et al., 2022; Min et al., 2023), but their
derivation does not satisfy the conditions required for the probabilistic-
method UL4CO pipeline (see Section 2.2.1). We see the potential application of
probabilistic-method UL4CO on TSP by seeing the conditions in TSP as a
combination of (1) non-binary decisions and (2) cardinality constraints, both
of which are already covered in this work. Specifically, if we aim to put $n$
nodes in a cycle as the solution, then this can be understood as (1) deciding
a position $X_{v}\in\\{0,1,\ldots,n-1\\}$ for each node $v\in[n]$ such that
(2) each position contains exactly one node. See similar ideas in the
(integer) linear programming formulations of TSP (Diaby, 2006; Yannakakis,
1988).

##  Appendix C Additional technical details

Here, we provide some additional technical details that are omitted in the
main text.

###  C.1 Computation of the Poisson Binomial Distribution

Here, we provide some implementation details on the computation of the Poisson
binomial distribution, which is used in Section 4.1. We mainly follow the
original paper (Hong, 2013) and an existing implementation online (Straka,
2017).

The main formula is

$\Pr_{X\sim p}[\lvert
V_{X}\rvert=t]=\frac{1}{n+1}\sum_{s=0}^{n}\exp(-\mathbf{i}\omega
st)\prod_{j=1}^{n}(1-p_{j}+p_{j}\exp(\mathbf{i}\omega s)),$

where $\mathbf{i}=\sqrt{-1}$ and $\omega=\frac{2\pi}{n+1}$. See the original
paper (Hong, 2013) for more technical details.

##  Appendix D Additional Theoretical Results

Here, we provide additional theoretical results.

###  D.1 Additional Results on Non-Binary Decisions

Here, we provide the details of our theoretical results regarding non-binary
decisions.

Notations. With non-binary decisions $d=\\{0,1,\ldots,c-1\\}$, we use
$p\in[0,1]^{n\times c}$ with $\sum_{r=0}^{c-1}p_{ir}=1,\forall i\in[n]$ to
represent the probabilities of possible decisions, where each
$p_{ir}=\Pr[X_{i}=r]$. Now, $\operatorname{der}(i,x;p)$ is the result after
the $i$-th row of $p$ being locally derandomized w.r.t. its $x$-th entry,
i.e., $\begin{cases}\operatorname{der}(i,x;p)_{ix}=1,\\\
\operatorname{der}(i,y;p)_{iy}=0,\forall y\neq x,\text{~{}and~{}}\\\
\operatorname{der}(i,x;p)_{jz}=p_{jz},\forall j\neq i,\forall z.\end{cases}$

Theoretical analysis on non-binary cases. Our theoretical results (Thms. 1 &
2) can be extended to non-binary cases.999See App. D.1 for the detailed
statements, where we also extend the theoretical results in the existing works
by (Karalias & Loukas, 2020) and (Wang et al., 2022) to non-binary cases. With
non-binary decisions, a probabilistic objective $\tilde{f}:[0,1]^{n\times
c}\to\mathbb{R}$ is entry-wise concave if

$\sum_{r\in
d}p_{ir}\tilde{f}(\operatorname{der}(i,r;p))\leq\tilde{f}(p),\forall
p\in[0,1]^{n\times c},i\in[n]$,

and the process of greedy derandomization is:
$\begin{cases}\text{(1)
$(i^{*},x^{*})\leftarrow\mathop{\mathrm{arg\,min}}_{(i,x)\in[n]\times
d}\tilde{f}(\operatorname{der}(i,x;p_{\mathrm{cur}}))$ and}\\\ \text{(2)
$p_{\mathrm{cur}}\leftarrow\operatorname{der}(i^{*},x^{*};p_{\mathrm{cur}})$.}\end{cases}$

######  Theorem 5 (Expectations are all you need (non-binary version)).

For any function $g:d^{n}\to\mathbb{R}$, $\tilde{g}:[0,1]^{n\times
c}\to\mathbb{R}$ with $\tilde{g}(p)=\mathbb{E}_{X\sim p}g(X)$ is
differentiable and entry-wise concave, where $\mathbb{E}_{X\sim
p}g(X)=\sum_{X\in d^{n}}\Pr_{p}[X]g(X)$ with
$\Pr_{p}[X]=\prod_{v\in[n]}p_{vX_{v}}$.

###### Proof.

For any $p$ and $i$, we have

$\displaystyle\tilde{g}(p)$ $\displaystyle=\mathbb{E}_{X\sim p}g(X)$
$\displaystyle=\sum_{X\in d^{n}}\Pr_{p}[X]g(X)$ $\displaystyle=\sum_{X\in
d^{n}}\prod_{v\in[n]}p_{vX_{v}}g(X)$ $\displaystyle=\sum_{X\in
d^{n}}(\prod_{v\in[n]\setminus\\{i\\}}p_{vX_{v}})p_{iX_{i}}g(X)$
$\displaystyle=\sum_{r\in d}\sum_{X\colon
X_{i}=r}(\prod_{v\in[n]\setminus\\{i\\}}p_{vX_{v}})p_{iX_{i}}g(X)$
$\displaystyle=\sum_{r\in d}\sum_{X\colon
X_{i}=r}(\prod_{v\in[n]\setminus\\{i\\}}p_{vX_{v}})p_{ir}g(X)$
$\displaystyle=\sum_{r\in d}p_{ir}\sum_{X\colon
X_{i}=r}(\prod_{v\in[n]\setminus\\{i\\}}p_{vX_{v}})g(X)$
$\displaystyle=\sum_{r\in
d}p_{ir}\sum_{X}(\prod_{v\in[n]\setminus\\{i\\}}p_{vX_{v}})\mathbb{1}(X_{i}=r)g(X)$
$\displaystyle=\sum_{r\in d}p_{ir}\tilde{g}(\operatorname{der}(i,r;p))$
$\displaystyle\geq\sum_{r\in d}p_{ir}\tilde{g}(\operatorname{der}(i,r;p)),$

completing the proof on entry-wise concavity. Regarding differentiability,
since $\mathbb{E}_{X\sim p}g(X)=\sum_{X\in d^{n}}\Pr_{p}[X]g(X)$, it suffices
to show that $\Pr_{p}[X]g(X)=\sum_{X\in d^{n}}\prod_{v\in[n]}p_{vX_{v}}g(X)$
is differentiable w.r.t $p$ for each $X\in\\{0,1\\}^{n}$. Indeed, fix any $X$,
$\sum_{X\in d^{n}}\prod_{v\in[n]}p_{vX_{v}}g(X)$ is a polynomial of
$p_{ir}$’s, and is thus differentiable. ∎

With non-binary decisions, the process of greedy derandomization is extended
as follows:
$\begin{cases}\text{(1)
$(i^{*},x^{*})\leftarrow\mathop{\mathrm{arg\,min}}_{(i,x)\in[n]\times
d}\tilde{f}(\operatorname{der}(i,x;p_{\mathrm{cur}}))$ and}\\\ \text{(2)
$p_{\mathrm{cur}}\leftarrow\operatorname{der}(i^{*},x^{*};p_{\mathrm{cur}})$.}\end{cases}$

######  Theorem 6 (Goodness of greedy derandomization (non-binary version)).

Theorem 2 still holds in non-binary cases, i.e., with $\\{0,1\\}$ being
replaced by any non-binary $d$. Specifically, for any entry-wise concave
$\tilde{f}$ and $p_{\mathrm{init}}$, the above process can always reach a
point where the final $p_{\mathrm{final}}$ is (1) discrete (i.e.,
$p_{\mathrm{final}}\in d^{n}$), (2) no-worse than $p_{\mathrm{init}}$ (i.e.,
$\tilde{f}(p_{\mathrm{final}})\leq\tilde{f}(p_{\mathrm{init}})$), and (3) is a
local minimum (i.e., $\tilde{f}(p_{\mathrm{final}})=\min_{(i,x)\in[n]\times
d}\tilde{f}(\operatorname{der}(\pi(i),x;p_{\mathrm{final}}))$).

###### Proof.

See the proof for Theorem 2. It is easy to see that the reasoning still holds
with $\\{0,1\\}$ being replaced by any non-binary $d$. ∎

We also extend the theoretical results in the existing works (Karalias &
Loukas, 2020; Wang et al., 2022) to non-binary cases.

Recall the theoretical results (Theorem 3) by (Karalias & Loukas, 2020).

Theorem 3 (Theorem 1 by (Karalias & Loukas, 2020)) Assume that $f$ is non-
negative. Fix any $\beta>\max_{X\in\mathcal{C}}f(X;G)$, $\epsilon>0$, and
$t\in(0,1]$ such that $(1-t)\epsilon<\beta$. If
$\tilde{f}(p_{\mathrm{init}};G)<\beta$, then $\Pr_{X\sim
p_{\mathrm{init}}}[f(X;G)<\epsilon\land X\in\mathcal{C}]\geq t$.

We extend Theorem 3 to non-binary cases.

######  Theorem 7 (Non-binary extension of Theorem 3).

Assume that $f$ is non-negative. Fix any $\beta>\max_{X\in\mathcal{C}}f(X;G)$,
$\epsilon>0$, and $t\in(0,1]$ such that $(1-t)\epsilon<\beta$. If
$\tilde{f}(p_{\mathrm{init}};G)<\beta$, then $\Pr_{X\sim
p_{\mathrm{init}}}[f(X;G)<\epsilon\land X\in\mathcal{C}]\geq t$.

###### Proof.

We shall follow the main idea in the original proof of Theorem 3 by (Karalias
& Loukas, 2020), which is based on Markov’s inequality. The key point is that
the reasoning still holds when the decisions are non-binary. Specifically, we
can define a probabilistic penalty function
$\hat{f}(X;G)={f}(X;G)+\beta\mathbb{1}(X\in\mathcal{C})$. Since
$\beta>\max_{X\in\mathcal{C}}f(X;G)$, we have $\hat{f}(X;G)<\epsilon$ if and
only if $f(X;G)<\epsilon$ and $X\in\mathcal{C}$. Therefore, using Markov’s
inequality, we have

$\displaystyle\Pr\nolimits_{X\sim
p_{\mathrm{init}}}[(f(X;G)<\epsilon)\land(X\in\mathcal{C})]$
$\displaystyle=\Pr\nolimits_{X\sim p_{\mathrm{init}}}[\hat{f}(X;G)<\epsilon]$
$\displaystyle>1-\frac{1}{\epsilon}\mathbb{E}_{X\sim
p_{\mathrm{init}}}[\hat{f}(X;G)]$
$\displaystyle=1-\frac{1}{\epsilon}\mathbb{E}_{X\sim
p_{\mathrm{init}}}[{f}(X;G)+\beta\mathbb{1}(X\in\mathcal{C})]$
$\displaystyle>1-\frac{1}{\epsilon}(\beta)$ $\displaystyle>t.$

∎

Recall the theoretical results (Theorem 4) by (Wang et al., 2022).

Theorem 4 (Theorem 1 by (Wang et al., 2022)) If
$\tilde{f}(p)\geq\mathbb{E}_{X\sim p}f(X)+\beta\Pr_{X\sim
p}[X\notin\mathcal{C}],\forall p$ is entry-wise concave and non-negative with
$\beta>\max(\tilde{f}(p_{\mathrm{init}}),\max_{X\in\mathcal{C}}f(X))$, then
for any permutation $\pi:[n]\to[n]$, starting from
$p_{\mathrm{cur}}=p_{\mathrm{init}}$ and for $i\in[n]$ doing (1)
$x^{*}\leftarrow\mathop{\mathrm{arg\,min}}_{x\in\\{0,1\\}}\tilde{f}(\operatorname{der}(\pi(i),x;p_{\mathrm{cur}}))$
and (2)
$p_{\mathrm{cur}}\leftarrow\operatorname{der}(i,x^{*};p_{\mathrm{cur}})$ will
finally give a discrete $p_{\mathrm{final}}\in\mathcal{C}$ such that
$f(p_{\mathrm{final}})\leq\tilde{f}(p_{\mathrm{init}})$.

We shall show that Theorem 4 can be extended to non-binary cases.

######  Theorem 8 (Non-binary extension of Theorem 4).

If $\tilde{f}(p)\geq\mathbb{E}_{X\sim p}f(X)+\beta\Pr_{X\sim
p}[X\notin\mathcal{C}],\forall p$ is entry-wise concave and non-negative with
$\beta>\max(\tilde{f}(p_{\mathrm{init}}),\max_{X\in\mathcal{C}}f(X))$, then
for any permutation $\pi:[n]\to[n]$, starting from
$p_{\mathrm{cur}}=p_{\mathrm{init}}$ and for $i\in[n]$ doing (1)
$x^{*}\leftarrow\mathop{\mathrm{arg\,min}}_{x\in
d=\\{0,1,2,\ldots,c-1\\}}\tilde{f}(\operatorname{der}(\pi(i),x;p_{\mathrm{cur}}))$
and (2)
$p_{\mathrm{cur}}\leftarrow\operatorname{der}(i,x^{*};p_{\mathrm{cur}})$ will
finally give a discrete $p_{\mathrm{final}}\in\mathcal{C}$ such that
$f(p_{\mathrm{final}})\leq\tilde{f}(p_{\mathrm{init}})$.

###### Proof.

We shall follow the main idea in the original proof of Theorem 4 by (Wang et
al., 2022), where the key idea was that entry-wise concavity ensures that
local derandomization does not increase the objective. This key idea still
holds with non-binary decisions. First, since after the series of local
derandomization, for each $i$, it is locally derandomized exactly once, the
final derandomized result should be discrete. Regarding
$p_{\mathrm{final}}\in\mathcal{C}$ and
$f(p_{\mathrm{final}})\leq\tilde{f}(p_{\mathrm{init}})$, we claim that “local
derandomization does not increase the objective”. Specifically, since
$\tilde{f}$ is entry-wise concave, i.e.,

$\sum_{r\in
d}p_{ir}\tilde{f}(\operatorname{der}(i,r;p);G)\leq\tilde{f}(p;G),\forall
G,p,i,$

and $\sum_{r\in d}p_{ir}=1$, we have

$\min_{r\in d}\tilde{f}(\operatorname{der}(i,r;p);G)\leq\sum_{r\in
d}p_{ir}\tilde{f}(\operatorname{der}(i,r;p);G)\leq\tilde{f}(p;G),\forall
G,p,i.$

Hence, indeed, “local derandomization does not increase the objective”, and
the final

${f}(X;G)+\beta\mathbb{1}(X\notin\mathcal{C})\leq\tilde{f}(p_{\mathrm{init}})<\beta,$

which implies that ${f}(X;G)\leq\tilde{f}(p_{\mathrm{init}})$ and
$\mathbb{1}(X\notin\mathcal{C})=0$, i.e., $X\in\mathcal{C}$, completing the
proof. ∎

##  Appendix E Additional Problems

The robust $k$-clique problem generalizes the maximum $k$-clique problem
(Bomze et al., 1999) and it can be seen as an uncertain variant of the
heaviest $k$-subgraph problem (Feige et al., 2001; Billionnet, 2005).

###  E.1 Robust $k$-Clique

Definition. Given (1) an uncertain graph $G=(V,E,P)$, and (2)
$k\in\mathbb{N}$, we aim to find a subset of nodes $V_{X}\subseteq V$ such
that (c1) $\lvert V_{X}\rvert=k$, (c2) $V_{X}$ forms a clique, and (c3)
$\Pr[\text{all the edges between nodes in $V_{X}$ exist}]$ is maximized.

Involved conditions: (1) cardinality constraints, (2) cliques, and (3)
uncertainty (see Sections 4.1, 4.4 & 4.6).

Details. Regarding conditions (c1)-(c2), we can directly use the derivations
for them. Regarding condition (c3), fix any $V_{X}$, the probability that all
the edges between nodes in $V_{X}$ exist is

$\prod_{(u,v)\in\binom{V_{c}}{2}\cap E}P_{uv}.$

Maximizing the probability is equivalent to minimizing

$f_{1}(X)\coloneqq-\sum_{(u,v)\in\binom{V_{c}}{2}\cap E}\log P_{uv}.$

We let $\hat{f}_{1}(X)\coloneqq f_{1}(X)$ and let

$\tilde{f}_{1}(p)\coloneqq\mathbb{E}_{X\sim p}\hat{f}_{1}(X)=-\sum_{(u,v)\in
E}p_{u}p_{v}\log P_{uv}.$

The final objective is

$\tilde{f_{\mathrm{RQ}}}(p)=\tilde{f}_{1}(p)+\beta_{1}\tilde{f}_{\mathrm{cq}}(p)+\beta_{2}\tilde{f}_{\mathrm{card}}(p;\\{k\\})$

with constraint coefficients $\beta_{1},\beta_{2}>0$.

Regarding the incremental differences, we only need to derive the incremental
differences of $\tilde{f}_{1}$, which is

$\Delta\tilde{f}_{1}(i,1,p)=(p_{i}-1)\sum_{v\colon(i,v)\in E}p_{v}\log
P_{iv},$

and

$\Delta\tilde{f}_{1}(i,0,p)=-p_{i}\sum_{v\colon(i,v)\in E}p_{v}\log P_{iv}.$

###  E.2 Robust Dominating Set

The robust dominating set problem generalizes the minimal dominating set
problem (Guha & Khuller, 1998) and can also be seen as an uncertain version of
set covering (Caprara et al., 2000).

Definition. Given (1) an uncertain graph $G=(V,E,P)$, and (2)
$k\in\mathbb{N}$, we aim to find a subset of nodes $V_{X}\subseteq V$ such
that (c1) $\lvert V_{X}\rvert=k$, (c2) $V_{X}$ is a dominating set in the
underlying deterministic graph, that is, for each $v\in V$, either $v\in
V_{X}$ or $v$ has a neighbor in $V_{X}$, and (c3) the probability that $V_{X}$
is indeed a dominating set when considering the edge uncertainty, i.e.
$\Pr[\bigwedge_{v\in V\setminus V_{X}}\bigvee_{u\in V_{X}}A_{uv}]$ is
maximized. For each edge $(u,v)\in E$, $A_{u}v$ is the event that $(u,v)$
exists under edge certainty, which happens with probability $P_{uv}$.

Involved conditions: (1) cardinality constraints, (2) covering, and (3)
uncertainty (see Sections 4.1, 4.3, & 4.6).

Details. Regarding conditions (c1), we can directly use the derivations for
it. Specifically, $\tilde{f}_{1}(p)=\tilde{f}_{\mathrm{card}}(p;\\{k\\})$.

Conditions (c2) and (c3) can be combined together. We first add self-loops on
each node $v\in V$ (so that each node $v$ can cover $v$ itself), and then
consider the condition as $X\in\mathcal{C}$ with

$\mathcal{C}=\\{X\colon\text{each node $v\in V$ is covered}\\}.$

Then we define $\hat{f}_{2}(X)$ as the expected number of nodes that are not
covered (when taking the edge uncertain into consideration). It is easy to see
that $\hat{f}_{2}(X)\geq\mathbb{1}(X\notin\mathcal{C}),\forall
X\in\\{0,1\\}^{n}$. Note that here the uncertainty comes from the edge
probabilities while the decisions are discrete. The formula of $\hat{f}_{2}$
is

$\hat{f}_{2}(X)=\sum_{i\in V}\Pr[\text{$i$ is not covered}]=\sum_{i\in
V\setminus V_{X}}\prod_{v\in N_{i}}(1-P_{iv}),$

where $N_{i}=\\{v\in V\colon(i,v)\in E\\}$ is the neighborhood of $i$. We then
define $\tilde{f}_{2}(p)=\mathbb{E}_{X\sim p}\hat{f}_{2}(X)$, and its formula
is

$\tilde{f}_{2}(p)=\sum_{i\in V}\Pr[i\notin V_{X}]\prod_{v\in
N_{i}}(1-P_{iv})=\sum_{i\in V}(1-p_{i})\prod_{v\in N_{i}}(1-P_{iv}).$

Combining all the conditions, the final probabilistic objective is

$\tilde{f}_{\mathrm{RDS}}(p)=\tilde{f}_{2}(p)+\beta\tilde{f}_{1}(p)$

with constraint coefficient $\beta>0$.

Regarding the incremental differences, we only need to derive the incremental
differences of $\tilde{f}_{2}$, which is

$\Delta\tilde{f}_{2}(i,1,p)=(p_{i}-1)\prod_{v\in N_{i}}(1-P_{iv})$

and

$\Delta\tilde{f}_{2}(i,0,p)=-p_{i}\prod_{v\in N_{i}}(1-P_{iv}).$

###  E.3 Clique Cover

The clique cover problem (Gramm et al., 2009) is a classical NP-hard
combinatorial problem. We consider its decision version, which is NP-complete.

Definition. Given (1) a graph $G=(V,E)$ and (2) $c\in\mathbb{N}$, we aim to
partition the nodes into $c$ groups, such that each group forms a clique.

Involved conditions: (1) cliques and (2) non-binary decisions (see Sections
4.4 & 4.5).

Details. This is basically the non-binary extension of the “cliques”
condition. For each $r\in d=\\{0,1,2,\ldots,c-1\\}$, the condition holds for
group-$r$ if the group is either empty or forms a clique. The group-$r$ is
empty with probability $\prod_{i\in V}(1-p_{ir})$, and we can use

$\tilde{f}_{\mathrm{cq}}(p_{\cdot,r})\geq\Pr\nolimits_{X\sim
p}[\text{group-$r$ does not form a clique}],$

where ${p}_{\cdot,r}\in[0,1]^{n}$ with $({p}_{\cdot,r})_{j}=p_{j,r}$. Then the
violation probability

$\displaystyle\Pr[\text{violation}]$ $\displaystyle=\Pr[\text{not
empty}\land\text{does not form a clique}]$ $\displaystyle\leq\Pr[\text{not
empty}]+\Pr[\text{does not form a clique}].$

Therefore, we can have the final probabilistic objective

$\tilde{f}_{\mathrm{cc}}(p)=\sum_{r=0}^{c-1}1-\prod_{i\in
V}(1-p_{ir})+\tilde{f}_{\mathrm{cq}}(p_{\cdot,r}).$

If we create a complete graph $K_{V}$ with self-loops on $V$, then

$\prod_{i\in V}(1-p_{ir})=\tilde{f}_{\mathrm{cv}}(p_{\cdot,r};v,K_{V})$

for any $v\in V$. Hence, we have

$\tilde{f}_{\mathrm{CC}}(p)=\sum_{r=0}^{c-1}1-\tilde{f}_{\mathrm{cv}}(p_{\cdot,r};v,K_{V})+\tilde{f}_{\mathrm{cq}}(p_{\cdot,r}),$

and the incremental differences can be handled by those of
$\tilde{f}_{\mathrm{cv}}$ and $\tilde{f}_{\mathrm{cq}}$.

###  E.4 Minimum Spanning Tree

The minimum spanning tree problem (Graham & Hell, 1985) is a classical
combinatorial problem. Notably, it is not theoretically difficult and we have
fast algorithms (Pettie & Ramachandran, 2002; Zhong et al., 2015) for the
problem. But it is still interesting to see that our method can be applied to
such a problem.

Definition. Given a graph $G=(V,E,W)$, we aim to find a subset of edges to
form a connected tree (i.e., without cycles) containing all the nodes such
that the total edge weights in the tree are minimized. Instead of considering
choosing edges, we consider the decisions on nodes. Specifically, we put the
nodes into different layers. Let $c\leq n$ be the number of layers, it is a
non-binary problem, where each node $v$ is put into layer-$X_{v}$ with
$X_{v}\in d=\\{0,1,2,\ldots,c-1\\}$. For each node $v_{\ell}$ in layer
$\ell>0$, it would be connected to a parent $v_{prev}$ in the previous
layer-$(\ell-1)$ so that the edge weight of $(v_{\ell},v_{prev})$ is
minimized. The conditions are: (c1) each node is either in layer-$0$, or it
can find a parent in the previous layer, and (c2) the total edge weights are
minimized.

Involved conditions: (1) minimum (maximum) w.r.t. a subset, (2) covering and
(3) non-binary decisions (see Sections 4.2, 4.3, and 4.5).

Details. Regarding (c1), we let $\hat{f}_{1}$ be the number of nodes for which
(c1) is violated. For each node $i$, it is in layer-$0$ with probability
$p_{v0}$ and it can find at least one parent with probability

$\displaystyle\sum_{\ell=1}^{c-1}\Pr[\text{$i$ is in
layer-$\ell$}]\Pr[\text{at least one of $i$'s neighbors is in
layer-$(\ell-1)$}]$ $\displaystyle=\sum_{\ell=1}^{c-1}p_{i\ell}(1-\prod_{v\in
N_{i}}(1-p_{v,\ell-1}))$
$\displaystyle=\sum_{\ell=1}^{c-1}p_{i\ell}(1-\tilde{f}_{\mathrm{cv}}(p{\cdot,\ell-1};i)),$

where ${p}_{\cdot,\ell-1}\in[0,1]^{n}$ with
$({p}_{\cdot,\ell-1})_{j}=p_{j,\ell-1}$. Again, $N_{i}=\\{v\in V\colon(i,v)\in
E\\}$ is the neighborhood of $i$. Note how the idea of “covering” is used
here. Therefore, the probability that (c1) is violated for the node $i$ is

$1-p_{i0}-\sum_{\ell=1}^{c-1}p_{i\ell}(1-\tilde{f}_{\mathrm{cv}}(p{\cdot,\ell-1};i)).$

Now we are ready to compute

$\tilde{f}_{1}(p)=\mathbb{E}_{X\sim p}\hat{f}_{1}(X)=\sum_{i\in
V}(1-p_{v0}-\sum_{\ell=1}^{c-1}p_{v\ell}(1-\tilde{f}_{\mathrm{cv}}(p{\cdot,\ell-1};i))).$

Regarding (c2), we use the idea of “minimum (maximum) w.r.t. a subset”. For a
spanning tree, the total edge weights are

$\sum_{i\in V\colon\text{$i$ not the root}}W(i,\text{the parent of $i$}).$

Note that in a minimum spanning tree, each non-root node should have a single
parent. For each node $i$, the expected $W(i,\text{the parent of $i$})$ is

$\sum_{\ell=1}^{c-1}p_{i\ell}\tilde{f}_{\mathrm{ms}}({p}_{\dot{,}\ell-1};i,W),$

where ${p}_{\cdot,\ell-1}\in[0,1]^{n}$ with
$({p}_{\cdot,\ell-1})_{j}=p_{j,\ell-1}$. The idea of “minimum (maximum) w.r.t.
a subset” has been used, where we consider the nodes being chosen into
layer-$(\ell-1)$. Therefore, we have

$\tilde{f}_{2}(p)=\sum_{i\in
V}\sum_{\ell=1}^{c-1}p_{i\ell}\tilde{f}_{\mathrm{ms}}({p}_{\cdot,\ell-1};i,W).$

Combining the conditions, the final probabilistic objective is

$\tilde{f}_{\mathrm{MST}}(p)=\tilde{f}_{2}(p)+\beta\tilde{f}_{1}(p)$

with constraint coefficient $\beta>0$. The incremental differences can be
handled by those of $\tilde{f}_{\mathrm{cv}}$ and $\tilde{f}_{\mathrm{ms}}$.

###  E.5 On cycles and trees

Cycles. As discussed in Appendix B.3, CO problems involving cycles can be
handled as follows. The conditions that nodes should form a cycle can be seen
as a combination of (1) non-binary decisions and (2) cardinality constraints.
Specifically, if we aim to put $n$ nodes in a cycle, then this can be
understood as (1) deciding a position $X_{v}\in\\{0,1,\ldots,n-1\\}$ for each
node $v\in[n]$ such that (2) each position contains exactly one node.

Trees. In MST (and other CO problems involving trees), an implicit condition
is acyclicity (Lachapelle et al., 2020). In our way of organizing nodes into
sequences of layers, acyclicity is naturally satisfied. However, this might be
tricky if we also need to decide how each node chooses its parent(s) and
child(ren). For MST, this is deterministic in the sense that each non-root
node should always choose the closest node in the above layer as its only
parent, so that the total distance is minimized. In general, we may need
additional decisions (parameters) for the choice of edges.

We acknowledge that we do not have in-depth empirical results for problems on
cycles and trees (e.g., TSP and MST) in this work. However, many advanced
heuristics are available for TSP, and there are fast exact algorithms for MST.
Based on our preliminary experiments, we suspect that a general framework like
probabilistic-method-based UL4CO (at least in its current stage) cannot be
empirically comparable to them, even with our proposed schemes. Hence, from a
practical standpoint, we found it less prioritized to develop new methods for
such problems, which was also why we focused on the conditions and problems in
this work. Note that we do not intend to imply that constraints for TSP and
MST are less important. Instead, we suspect that addressing TSP and MST
effectively enough to be practical requires sophisticated and potentially
complex designs tailored specifically for such problems, which is beyond the
scope of this work. The further exploration on problems involving cycles and
trees (and other conditions that cannot be trivially covered using the
derivations in this work) is one of our future directions.

##  Appendix F Complete Experimental Settings and Results

Here, we provide detailed experimental settings and some additional
experimental results.

###  F.1 Detailed Experimental Settings

Here, we provide some details of the experimental settings.

####  F.1.1 Hardware

All the experiments are run on a machine with two Intel Xeon® Silver 4210R (10
cores, 20 threads) processors, a 256GB RAM, and RTX2080Ti (11GB) GPUs. For the
methods using GPUs, a single GPU is used.

####  F.1.2 Facility Location

Here, we provide more details about the settings of the experiments on the
facility location problem. For the experiments on facility location and
maximum coverage, we mainly follow the settings by (Wang et al., 2023) and use
their open-source implementation.101010https://github.com/Thinklab-SJTU/One-
Shot-Cardinality-NN-Solver

Datasets. We consider both random synthetic graphs and real-world graphs:

  * •

Rand500: We follow the way of generating random graphs by (Wang et al., 2023).
We generate 100 random graphs, where each graph contains 500 nodes. Each node
$v$ has a two-dimensional location $(x_{v},y_{v})$, where $x_{v}$ and $y_{v}$
are sampled in $[0,1]$, independently, uniformly at random.

  * •

Rand800: The rand800 graphs are generated in a similar way. The only
difference is that each rand800 graph contains 800 nodes.

  * •

Starbucks: The Starbucks datasets were used by (Wang et al., 2023). We quote
their descriptions as follows: The datasets are built based on the project
named Starbucks Location Worldwide 2021
version,111111https://www.kaggle.com/datasets/kukuroo3/starbucks-locations-
worldwide-2021-version which is scraped from the open-accessible Starbucks
store locator webpage.121212https://www.starbucks.com/store-locator We analyze
and select 4 cities with more than 100 Starbucks stores, which are London (166
stores), New York City (260 stores), Shanghai (510 stores), and Seoul (569
stores). The locations considered are the real locations represented as
latitude and longitude.

  * •

MCD: The MCD (McDonald’s) dataset is available
online.131313https://www.kaggle.com/datasets/mdmdata/mcdonalds-locations-
united-states. The dataset contains the locations of MCD branches in the
United States. We divide the dataset into multiple sub-datasets by state,
where each sub-dataset contains branches in the same state. We use the data
from 8 states with the most ranches: CA (1248 branches), TX (1155 branches),
FL (889 branches), NY (597 branches), PA (483 branches), IL (650 branches), OH
(578 branches), and GA (442 branches).

  * •

Subway: The Subway dataset is available
online.141414https://www.kaggle.com/datasets/thedevastator/subway-the-fastest-
growing-franchise-in-the-worl Similar to the MCD dataset, it contains the
locations of subway branches in the United States. We also divide the dataset
into multiple sub-datasets by state, where each sub-dataset contains branches
in the same state. We use the data from 8 states with the most ranches: CA
(2590 branches), TX (21994 branches), FL (1490 branches), NY (1066 branches),
PA (865 branches), IL (1110 branches), OH (1171 branches), and GA (852
branches).

  * •

For the real-world datasets, we use min-max normalization to make sure that
each coordinate of each node (location) is also in $[0,1]$ as in the random
graphs.

Inductive settings. We follow the settings by (Wang et al., 2023). For random
graphs, the model is trained and tested on random graphs from the same
distribution, but the training set and the test set are disjoint. For real-
world graphs, the model is trained on the rand500 graphs.

Methods. We consider both traditional methods and machine-learning methods:

  * •

Random: Among all the locations, $k$ locations are picked uniformly at random;
240 seconds are given on each test graph.

  * •

Greedy: deterministic greedy algorithms. We use the implementation of (Wang et
al., 2023).

  * •

Gurobi (Gurobi Optimization, LLC, 2023) and SCIP (Bestuzheva et al., 2021;
Perron & Furnon, 2023): The problems are formulated as MIPs and the two
solvers are used; the time budget is set as 120 seconds, but the programs
sometimes do not terminate until more time is used.

  * •

CardNN (Wang et al., 2023): Three variants proposed in the original paper. We
use the implementation of the original authors.

  * •

CardNN-noTTO: In addition to training, CardNN also directly optimizes on each
test graph in test time, and this is a variant of CardNN without test-time
optimization. We use the implementation of the original authors.

  * •

EGN-naive: EGN (Karalias & Loukas, 2020) with a naive objective construction
and iterative rounding, which was used by (Wang et al., 2023) as a baseline
method. We use the derivation and implementation by (Wang et al., 2023).

  * •

RL: A reinforcement-learning method (Kool et al., 2019). We adapt the
implementation by (Berto et al., 2023).151515https://github.com/kaist-
silab/rl4co

Speed-quality trade-offs. For the proposed method UCom2, we use test-time
augmentation (Jin et al., 2023) on the test graphs by adding perturbations
into both graph topology and features to obtain additional data. Specifically,
we use edge dropout (Papp et al., 2021; Shu et al., 2022) and add Gaussian
noise into features. The noise scale and the edge dropout ratios are both 0.2,
which we do not fine-tune. The three variants of UCom2 are obtained by using
different numbers of additional augmented data and taking the best objective.
Specifically, the “short” version uses only the original test graphs, the
“middle” version uses less time than CardNN-GS, and the “long” version uses
less time than CardNN-HGS.

Evaluation. Given locations $(x_{v},y_{v})$’s for the nodes $v\in V$, if the
final selected $k$ nodes are $v_{1},v_{2},\ldots,v_{k}$, the final objective
is $\sum_{v\in V}\min_{i\in[k]}\operatorname{dist}(v_{i},v)$, where the
distance metric $\operatorname{dist}$ is the Euclidean squared distance used
by (Wang et al., 2023). We choose $k=30$ locations in each graph, except for
the rand800 graphs where we choose $k=50$ locations.

Hyperparameter fine-tuning. For the proposed method UCom2 and the method
CardNN by (Wang et al., 2023), we conduct hyperparameter fine-tuning. For
UCom2, we fine-tune the learning rate (LR) and constraint coefficient (CC).
For CardNN, we fine-tune the training learning rate (LR)161616CardNN uses
(possibly) different learning rates for training and test-time optimization.
and the Gumbel noise scale $\sigma$. For random graphs, we choose the best
hyperparameter setting w.r.t. the objective on the training set, because the
distribution of the training set and the distribution of the test set are the
same. For real-world graphs, we choose the smallest graph in each group of
datasets as the validation graph, and we choose the best hyperparameter
setting w.r.t. the objective on the validation graph. There is no specific
reason to choose the smallest, and we just want to have a deterministic way to
choose validation graphs.

We make sure that the number of candidate combinations (which is 15) is the
same for both methods. Our hyperparameter search space is as follows:

  * •

For UCom2: $\text{LR}\in\\{1e-1,1e-2,1e-3,1e-4,1e-5\\}$ and
$\text{CC}\in\\{1e-1,1e-2,1e-3\\}$

  * •

For CardNN: $\text{LR}\in\\{1e-1,1e-2,1e-3,1e-4,1e-5\\}$ and
$\sigma\in\\{0.01,0.15,0.25\\}$

Notably, after our fine-tuning, the performance of CardNN is at least the same
and usually better than the performance using the hyperparameter settings in
the open-source code of CardNN provided by the original authors. The best
hyperparameter settings for each dataset are:

  * •

Rand500:

    * –

UCom2: $\text{LR}=1e-1$, $\text{CC}=1e-1$

    * –

CardNN: $\text{LR}=1e-4$, $\sigma=0.25$

  * •

Rand800:

    * –

UCom2: $\text{LR}=1e-2$, $\text{CC}=1e-2$

    * –

CardNN: $\text{LR}=1e-4$, $\sigma=0.25$

  * •

Starbucks:

    * –

UCom2: $\text{LR}=1e-1$, $\text{CC}=1e-1$

    * –

CardNN: $\text{LR}=1e-4$, $\sigma=0.15$

  * •

MCD:

    * –

UCom2: $\text{LR}=1e-3$, $\text{CC}=1e-1$

    * –

CardNN: $\text{LR}=1e-5$, $\sigma=0.25$

  * •

Subway:

    * –

UCom2: $\text{LR}=1e-1$, $\text{CC}=1e-1$

    * –

CardNN: $\text{LR}=1e-5$, $\sigma=0.01$

####  F.1.3 Maximum Coverage

Here, we provide more details about the settings of the experiments on the
maximum coverage problem.

Datasets. We consider both random synthetic graphs and real-world graphs:

  * •

Rand500: We follow the way of generating random graphs by (Wang et al., 2023).
Each item has a random weight chosen uniformly at random between $1$ and
$100$. Each set contains a random number of items, and the number of items is
chosen uniformly at random between $10$ and $30$. Each rand500 dataset
contains 500 sets and 1000 items.

  * •

Rand1000: The rand1000 graphs are generated in a similar way. The only
difference is that each rand1000 dataset contains 1000 sets and 2000 items.

  * •

Twitch: The Twitch datasets were used by (Wang et al., 2023). We quote their
descriptions as follows: This social network dataset is collected by
(Rozemberczki et al., 2021) and the edges represent the mutual friendships
between streamers. The streamers are categorized by their streaming language,
resulting in 6 social networks for 6 languages. The social networks are DE
(9498 nodes), ENGB (7126 nodes), ES (4648 nodes), FR (6549 nodes), PTBR (1912
nodes), and RU (4385 nodes). The objective is to cover more viewers, measured
by the sum of the logarithmic number of viewers. We took the logarithm to
enforce diversity because those top streamers usually have the dominant number
of viewers.

  * •

Railway: The railway datasets (Ceria et al., 1998) are available
online.171717https://plato.asu.edu/ftp/lptestset/rail. The data were collected
from real-world crew membership in Italian railways. We have three datasets:
(1) rail507 with 507 sets and 63009 items, (2) rail516 with 516 sets and 47311
items, and (3) rail582 with 582 sets and 55515 items.

Inductive settings. We follow the settings by (Wang et al., 2023). For random
graphs, the model is trained and tested on random graphs from the same
distribution, but the training set and the test set are disjoint. For real-
world graphs, the model is trained on the rand500 graphs.

Methods. See the method descriptions above for the facility location problem
in Appendix F.1.2.

Speed-quality trade-offs. See the descriptions above for the facility location
problem in Appendix F.1.2.

Evaluation. Let $w_{j}$’s denote the weights of the items. The final objective
is the summation of the weights of the covered items. An item $j$ is covered
if at least one set containing $j$ is chosen. This is the term $\sum_{j\in
T_{X}}W_{j}$ in Section 5.2.

Hyperparameter fine-tuning. The overall fine-tuning principles are the same as
in the experiments on the facility location problem. See Appendix F.1.2.

Our hyperparameter search space is as follows:

  * •

For UCom2: $\text{LR}\in\\{1e-1,1e-2,1e-3,1e-4,1e-5\\}$ and
$\text{CC}\in\\{10,100,500\\}$

  * •

For CardNN: $\text{LR}\in\\{1e-1,1e-2,1e-3,1e-4,1e-5\\}$ and
$\sigma\in\\{0.01,0.15,0.25\\}$

The best hyperparameter settings for each dataset are:

  * •

Rand500:

    * –

UCom2: $\text{LR}=1e-5$, $\text{CC}=500$

    * –

CardNN: $\text{LR}=1e-5$, $\sigma=0.15$

  * •

Rand1000:

    * –

UCom2: $\text{LR}=1e-5$, $\text{CC}=500$

    * –

CardNN: $\text{LR}=1e-5$, $\sigma=0.15$

  * •

Twitch:

    * –

UCom2: $\text{LR}=1e-1$, $\text{CC}=10$

    * –

CardNN: $\text{LR}=1e-4$, $\sigma=0.01$

  * •

Railway:

    * –

UCom2: $\text{LR}=1e-5$, $\text{CC}=10$

    * –

CardNN: $\text{LR}=1e-5$, $\sigma=0.15$

####  F.1.4 Robust Coloring

Here, we provide more details about the settings of the experiments on the
robust coloring problem.

Datasets. We use four real-world uncertain graphs (Hu et al., 2017; Ceccarello
et al., 2017; Chen et al., 2019). They are available
online.181818https://github.com/Cecca/ugraph/tree/master/Reproducibility/Data;
https://github.com/stasl0217/UKGE/tree/master/data Some basic statistics of
the datasets are as follows:

  * •

Collins: $n=1004$ nodes and $m=8323$ edges; a deterministic greedy coloring
algorithm uses 18 colors for the hard conflicts, and 36 colors for all the
conflicts.

  * •

Gavin: $n=1727$ nodes and $m=7534$ edges; a deterministic greedy coloring
algorithm uses 7 colors for the hard conflicts, and 16 for all the conflicts.

  * •

Krogan: $n=2559$ nodes $m=7031$ edges; a deterministic greedy coloring
algorithm uses 8 colors for the hard conflicts, and 25 for all the conflicts.

  * •

PPI: $n=1912$ nodes $m=22749$ edges; a deterministic greedy coloring algorithm
uses 47 colors for the hard conflicts, and 53 for all the conflicts.

We take the largest connected component of each dataset. For each dataset, the
$20\%$ edges with the highest edge weights are chosen as the hard conflicts.

Methods. We consider four baseline methods:

  * •

Greedy-RD: The method first samples a random permutation of nodes, and then
following the permutation, for each node, greedily chooses the best coloring
to (1) avoid all the hard conflicts and (2) optimizes the objective; 300
seconds are given on each test graph.

  * •

Greedy-GA: This is the method proposed by (Yanez & Ramirez, 2003) in the
original paper of robust coloring. The difference between greedy-RD and
greedy-GA is that greedy-GA uses a genetic algorithm (GA) to learn a good
permutation instead of randomly sampling permutations; in the GA algorithm,