Source-linked AI summary
Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
Nikolaos Karalias, Andreas Loukas
TL;DR
Neural networks remain difficult to train for combinatorial optimization without labels, while supervised and reinforcement-learning approaches have important drawbacks. This paper introduces an unsupervised probabilistic framework that guarantees low-cost valid integral solutions and achieves competitive results on maximum clique and local graph clustering.
Problem
Neural combinatorial optimization remains challenging without labels, whose acquisition can be computationally infeasible, while direct supervision may generalize poorly and reinforcement learning is harder to train.
Method
A graph neural network learns a distribution over node subsets using a probabilistic penalty loss, after which sequential deterministic decoding produces valid integral solutions.
Results
The framework achieves competitive results against neural baselines, discrete algorithms, and mathematical solvers on maximum clique and local graph clustering.
Takeaways & Limitations
The framework provides a mathematically principled approach for solving constrained combinatorial problems on graphs in an unsupervised way.
Takeaways & Limitations
Unsupervised learning does not eliminate all sources of bias in the learning pipeline.
Abstract
from arXiv · showhide
Combinatorial optimization problems are notoriously challenging for neural networks, especially in the absence of labeled instances. This work proposes an unsupervised learning framework for CO problems on graphs that can provide integral solutions of certified quality. Inspired by Erdos' probabilistic method, we use a neural network to parametrize a probability distribution over sets. Crucially, we show that when the network is optimized w.r.t. a suitably chosen loss, the learned distribution contains, with controlled probability, a low-cost integral solution that obeys the constraints of the combinatorial problem. The probabilistic proof of existence is then derandomized to decode the desired solutions. We demonstrate the efficacy of this approach to obtain valid solutions to the maximum clique problem and to perform local graph clustering. Our method achieves competitive results on both real datasets and synthetic hard instances.
1 Introduction
Neural approaches to combinatorial optimization remain difficult without labels, while unsupervised methods face degenerate relaxations and optimization obstacles. The proposed framework uses a probabilistic loss and deterministic decoding to obtain valid, low-cost solutions, with competitive results on graph problems.
- Motivation: Neural combinatorial optimization remains challenging, and supervised approaches require costly labels or demonstrations while reinforcement learning is harder to train.Labels for hard instances may be computationally infeasible, and direct supervision can generalize poorly.
- Framework: At inference, conditional expectation sequentially and deterministically decodes a discrete solution satisfying the certificate.This replaces direct random sampling with deterministic recovery.
- Motivation: Unsupervised learning avoids labels but commonly relies on continuous relaxations, correction terms, or auxiliary losses to address degenerate solutions and difficult optimization.The framework is motivated by the need for a more principled differentiable objective.
- Framework: The framework trains a GNN with a probabilistic penalty loss to produce a distribution over node subsets whose support contains low-cost feasible solutions.The learned distribution provides a certificate of existence for a valid integral solution.
- Evaluation: The method is evaluated on maximum clique and constrained min-cut for local graph clustering, achieving competitive results against neural, discrete, and mathematical-programming baselines.It outperforms CBC and remains competitive with Gurobi on larger instances.
2 Related work and background
Prior work spans supervised neural solvers, reinforcement learning, and unsupervised differentiable approaches for combinatorial optimization. This paper distinguishes its framework by combining unsupervised end-to-end training with guarantees of integral, constraint-satisfying solutions through the probabilistic method.
- Neural approaches for combinatorial optimization: Supervised neural methods for combinatorial optimization often require large datasets of solved hard instances, creating costly and potentially biased training-data requirements.The cited literature includes pointer networks, solver integrations, and other neural approaches.
- Neural approaches for combinatorial optimization: Reinforcement learning avoids labels but can be sample inefficient, unstable to train, and dependent on poor gradient estimates or initialization.These issues are reported across RL approaches to classical combinatorial problems.
- Neural approaches for combinatorial optimization: The paper's approach combines unsupervised differentiable end-to-end training with guarantees that solutions are integral and satisfy problem constraints.It avoids continuous relaxations, regularization, heuristic correction, and polynomial-time reductions.
- Background: the probabilistic method: The probabilistic method proves the existence of objects with desired combinatorial properties and has also supported algorithms in computer science and combinatorial optimization.The paper repurposes this nonconstructive proof strategy for neural optimization.
- Background: the probabilistic method: The learned probabilistic strategy extends the classic conditional-expectation idea from randomized constructions to higher-quality graph optimization solutions.A GNN learns the node probabilities instead of using naive coin flips, and the argument incorporates constraints.
3 The Erd˝os probabilistic method for deep learning
The framework represents candidate node sets probabilistically, trains a GNN using a differentiable certificate loss, and deterministically decodes a solution. Penalty terms and probability rescaling extend the guarantee to constrained problems.
- Problem formulation: The problem is formulated over weighted graphs, with feasible solutions represented as node sets belonging to a family of sets satisfying a desired property.This formulation includes maximum clique and minimum vertex cover.
- Framework: The method constructs a GNN distribution over sets, trains it to make a low-cost valid solution probable, and recovers that solution by conditional expectation.These are the framework's three stated steps.
- Framework: The distribution is parameterized by independent Bernoulli variables, with one probability p_i for each node v_i.This simple distribution makes relevant probability estimates tractable.
- Unconstrained loss: A differentiable surrogate loss acts as a certificate: if ℓ(D; G) is sufficiently small, the distribution contains with positive probability a set whose cost is at most that loss.The certificate follows from a tail-probability condition and can use an upper bound when the expectation is not closed-form.
- Probabilistic penalty loss: Constraints are incorporated by adding a penalty for infeasible sets, producing a loss whose guarantee covers both low cost and constraint satisfaction.The probabilistic penalty uses f_p(S; G) = f(S; G) + 1_{S ∉ Ω}β, with β a scalar.
- Special case of linear box constraints: For linear box constraints, probabilities are rescaled iteratively to satisfy the constraint in expectation before applying the probabilistic loss and decoding procedure.Theorem 2 transfers the unconstrained guarantee after successful rescaling.
- Deterministic decoding: Conditional expectation deterministically selects nodes one at a time by comparing conditional expected costs, while the penalty version preserves the theorem's guarantee.Monte Carlo sampling is presented as an alternative but is not the desired deterministic procedure.
4 Case studies
The case studies apply the framework to maximum clique and constrained minimum cut, deriving probabilistic losses with certified solution properties and practical decoding procedures. The losses support efficient computation and connect constrained cuts to local graph clustering and conductance.
- Maximum clique: The maximum clique case identifies a largest mutually adjacent node set, with weighted optimization generalizing cardinality to weighted graphs.For simple graphs, weight and cardinality formulations yield the same minimum.
- Maximum clique: With probability at least t, the learned distribution contains a clique S* whose weight satisfies w(S*) > γ − ϵ.The guarantee assumes positive γ and β with maxS w(S) ≤ γ ≤ β and edge weights wij ≤ 1.
- Maximum clique: The clique loss can be evaluated in linear time in the number of graph edges, and valid cliques can be decoded sequentially while maintaining the clique constraint.A probability-ordered sweep adds nodes only when the resulting set remains a clique.
- Graph partitioning: The constrained minimum-cut case minimizes cut weight subject to partition constraints involving node degrees and set volume.The problem is NP-hard and is a volume-balanced partitioning formulation connected to graph conductance.
- Graph partitioning: The constrained-cut loss is linear in the number of edges on sparse graphs, while decoding can use sampling or a derandomized procedure that guarantees a cut no larger than the probabilistic certificate.The linear volume constraint can be enforced by stopping before the constraint is violated.
5 Empirical evaluation
The evaluation tests Erdős’ GNN on maximum clique and local graph partitioning across real-world and synthetic hard instances. It remains competitive with neural, discrete, and solver baselines while maintaining valid constraints, though performance degrades on larger out-of-distribution clique instances.
- Methods: Erdős’ GNN is compared with neural networks, discrete algorithms, and integer-programming solvers under time-budgeted or repeated-run protocols.The maximum-clique comparison includes three neural methods, three discrete algorithms, and two solvers; partitioning compares two neural and four discrete methods.
- Evaluation setup: The evaluation covers maximum clique and local graph partitioning on real-world datasets and challenging RB synthetic instances.Clique experiments include IMDB, COLLAB, TWITTER, and RB graphs; partitioning uses FACEBOOK, TWITTER, and SF-295.
- Maximum clique: Erdős’ GNN always respected constraints and was competitive with RUN-CSP and the best solver, particularly when optimizing for speed on real-world clique datasets.On Twitter, smooth-relaxation methods violated constraints in at least 78% of instances, whereas Erdős’ GNN did not.
- Maximum clique: On hard RB clique instances, Erdős’ GNN exceeded RUN-CSP on training and test distributions but underperformed on larger out-of-distribution graphs.Both neural approaches fell behind the greedy algorithm and Gurobi for quality, while the gap narrowed on larger graphs because of Gurobi’s computational complexity.
- Local graph partitioning: Erdős’ GNN outperformed all previous algorithms by a considerable margin on local graph partitioning evaluated by conductance.The probabilistic-loss GNN achieved better conductance across all datasets, while Gurobi performed poorly except on the smallest graphs.
6 Conclusion
The paper presents a probabilistically grounded framework for unsupervised constrained combinatorial optimization on graphs. It guarantees solution quality through a probabilistic argument, while future work targets faster decoding and more complex constraints.
- Conclusion: The framework uses a probabilistic argument to guarantee the quality of solutions to constrained combinatorial problems on graphs.The authors describe this as a mathematically principled approach to unsupervised combinatorial optimization.
- Conclusion: Future work will investigate accelerating sequential decoding and extending the framework to constraints involving trees or paths.Current support covers constraints where node order is not necessarily important, such as clique, cover, and independent set.
- Conclusion: The framework is presented as a step toward solving combinatorial optimization problems in an unsupervised way.The authors connect this direction to further use of combinatorics and algorithmic theory in deep learning.
7 Broader impact
The paper discusses potential societal benefits and risks of applying deep learning to combinatorial optimization. It emphasizes that the field is nascent and that unsupervised learning may reduce label bias without eliminating all pipeline bias.
- Potential benefits and risks: Combinatorial optimization through deep learning could improve productivity in manufacturing and transportation while also creating risks of worker displacement.The paper also notes possible applications in medicine and chemistry.
- Bias considerations: Unsupervised learning avoids labeled instances and therefore lacks label bias, but it does not eliminate all sources of bias in the learning pipeline.
- Potential risks: Combinatorial optimization is also widely applied in military operations, creating an additional context for assessing its broader impact.The authors remain cautiously optimistic that positive effects will outweigh negative ones.
B.1 Datasets
The study uses multiple graph datasets summarized by their sizes, edge counts, reduction times, and evaluation-set counts. Dataset preparation includes restricting Facebook graphs for computational efficiency and constructing an RB test set to resemble the training distribution.
- Dataset statistics: Table 4 summarizes average nodes, average edges, maximum-clique reduction time, and the number of test graphs for each dataset.
- Dataset preprocessing: The Facebook dataset was restricted to graphs with at most 15,000 nodes, retaining 70 of its 100 available graphs to speed computation and training.
- RB dataset: The RB test set was generated to resemble the unavailable original training set, with training graphs ranging from 50–500 nodes and test graphs from 50–475 nodes.Training cliques had sizes 5–25, whereas test cliques had sizes 10–25.
- Data availability: All datasets other than the RB test set are publicly available.
B.2 Neural network architecture
The experiments use graph neural networks with random-node features and task-specific decoding or sampling procedures. The framework’s learning and decoding stages are both important: Erdős’ GNN preserves clique validity, while learned probabilities produce larger cliques than random assignments.
- Architecture and inputs: Both Erdős’ GNN and neural baselines receive a one-hot encoding of a randomly selected graph node as input.Local clustering networks use six GIN layers followed by a multi-head GAT layer, with skip connections and batch normalization.
- Evaluation protocol: For local clustering, each graph is evaluated from d randomly selected seeds, with d = 10, 30, and 100 for SF-295, TWITTER, and FACEBOOK, respectively.The reported values are means and standard deviations over seed-level conductances.
- Local clustering procedure: The local partitioning formulation searches feasible volume intervals and returns the set with the smallest identified conductance.
- Local clustering procedure: For neural methods and Gurobi, randomized volume intervals are generated within each seed’s receptive field; returned sets have controlled volume and contain the seed.L1 and L2 GNN obtain sets by sampling from their output distributions.
- Constraint violation: Erdős’ GNN always respected the clique constraint, whereas penalized continuous-relaxation baselines struggled on COLLAB and TWITTER.
- Constraint violation: Conditional-expectation decoding is crucial because it ensures that the clique constraint remains satisfied.
- Importance of learning: On Twitter, cliques decoded from trained-GNN probabilities were significantly larger than those decoded from random uniform probabilities.Table 6 compares approximation ratios under the same sequential decoding procedure.
C.2 Local graph partitioning
The local graph-partitioning evaluation compares Erdős’ GNN with Gurobi under matched local constraints and time budgets. On large Facebook graphs, Erdős’ GNN found substantially lower-conductance sets while running faster, although Gurobi timing excludes instance-construction costs.
- Solver comparison: Gurobi was rerun with three time budgets, with the largest exceeding Erdős’ GNN’s running time by approximately one order of magnitude.
- Optimization formulation: The integer-programming formulation uses binary variables x_i for set membership, a target volume, and a required seed node.The target volumes are restricted to values attainable within the neural networks’ fixed receptive fields.
- Results: On FACEBOOK graphs averaging 7k nodes, Erdős’ GNN found sets with more than 6× smaller conductance and was 6× faster than Gurobi.
- Timing caveat: Reported Gurobi time budgets cover optimization only, while constructing the problem and constraints adds costs that become especially pronounced on larger graphs.The paper reports total time in seconds per graph.
D.1 Proof of Theorem 1
The proof constructs probabilistic losses for constrained graph optimization, showing that low loss implies a valid integral solution with controlled probability. It then specializes this framework to maximum clique and min-cut by rescaling node probabilities and deriving expected objective values.
- Constrained probabilistic guarantee: The constrained proof adds a penalty β for infeasible sets, so loss below ε implies existence of a valid solution with cost ε.The penalty is chosen above the maximum feasible objective value, and the constrained event becomes equivalent to the penalized loss event.
- Constrained probabilistic guarantee: Markov’s inequality bounds the probability that a sampled set is both feasible and below the target cost.The theorem follows after combining the penalized probability expression with the resulting inequality.
- Probability rescaling: The network’s predicted node probabilities are iteratively rescaled until the constraints hold in expectation, with convergence enforced by expanding the set of clamped variables.The recursion terminates when all remaining probabilities are below one or the active set reaches all vertices.
- Probability rescaling: Hoeffding’s inequality and a union bound combine sampling guarantees for the constrained and unconstrained events.The threshold is parameterized by b and δ, and the resulting guarantee is positive when the sample count is sufficiently large.
- Maximum clique: For maximization, translating the objective as f(S; G) = γ − w(S) yields a sampled solution satisfying γ − ε < w(S*) with controlled probability.The bound requires γ to upper-bound w(S) and β to upper-bound the translated loss.
- Maximum clique and min-cut: For maximum clique, complement-graph edge weight measures infeasibility, while for min-cut the expected cut is derived from independent Bernoulli node assignments.The min-cut loss is then defined from the expected cut after probability rescaling; Theorem 2 completes the corresponding guarantee.