CLIO: A Search-Guided Graph Neural Framework for Maximum Independent Set

We study learning-augmented combinatorial optimization in the absence of externally supplied labels. We propose CLIO (Contrastive Learning with Iterative Optimization), a search-guided graph neural framework for the maximum independent set (MIS) problem. CLIO is designed around a closed-loop optimization paradigm: graph reduction simplifies the instance, a graph neural network (GNN) produces heuristic node scores, and a local deep search (LDS) procedure enforces feasibility and improves the candidate solution. Critically, the solution returned by LDS is converted into instance-specific pseudo-labels,which are then used to update the GNN through supervised and contrastive objectives. In this way, CLIO learns to solve an unlabeled MIS instance without requiring optimal solutions, external expert decisions, or reward engineering. The contribution of this work is therefore not a single neural architecture, but an integrated neuro-symbolic solving framework that enables label-free adaptation on a per-instance basis. Experiments compare CLIO with greedy and search heuristics, GNN-only and search-only variants, and time-limited solver references. In the ablation study on PPI graphs, the full framework achieved the highest average solution size among the methods except for the variant without graph reduction. LDS contributed the most to solution quality improvement; the closed loop contributed 0.1% and the contrastive loss contributed 0.4% to solution quality improvement, while graph reduction significantly reduced runtime. The current evidence demonstrates that search-generated pseudo-labels provide a viable learning signal for neural combinatorial optimization when no labeled data are available.