EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Lan Luo, Yuanhang Li, Chao Chen

Big Data and Cognitive Computing · 10.11.2026 · 10 (11) · 383

DOI: 10.3390/bdcc10110383 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Big Data and Cognitive Computing, online erschienen am 10.11.2026. Verfasst von Lan Luo und 2 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Luo, L., Li, Y., & Chen, C. (2026). CLIO: A Search-Guided Graph Neural Framework for Maximum Independent Set. Big Data and Cognitive Computing, 10(11), 383. https://doi.org/10.3390/bdcc10110383

Vancouver

Luo L, Li Y, Chen C. CLIO: A Search-Guided Graph Neural Framework for Maximum Independent Set. Big Data and Cognitive Computing. 2026;10(11):383. doi:10.3390/bdcc10110383

BibTeX
@article{Luo2026,
  author = {Luo, Lan and Li, Yuanhang and Chen, Chao},
  title = {CLIO: A Search-Guided Graph Neural Framework for Maximum Independent Set},
  journal = {Big Data and Cognitive Computing},
  year = {2026},
  volume = {10},
  number = {11},
  pages = {383},
  doi = {10.3390/bdcc10110383}
}
Kostenlos starten →