Binarizing Physics-Inspired GNNs for Combinatorial Optimization

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F25%3A00385907" target="_blank" >RIV/68407700:21230/25:00385907 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.3233/FAIA251038" target="_blank" >https://doi.org/10.3233/FAIA251038</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3233/FAIA251038" target="_blank" >10.3233/FAIA251038</a>

Result language

angličtina

Original language name

Binarizing Physics-Inspired GNNs for Combinatorial Optimization

Original language description

Physics-inspired graph neural networks (PI-GNNs) have been utilized as an efficient unsupervised framework for relaxing combinatorial optimization problems encoded through a specific graph structure and loss, reflecting dependencies between the problem’s variables. While the framework has yielded promising results in various combinatorial problems, we show that the performance of PI-GNNs systematically plummets with an increasing density of the combinatorial problem graphs. Our analysis reveals an interesting phase transition in the PI-GNNs’ training dynamics, associated with degenerate solutions for the denser problems, highlighting a discrepancy between the relaxed, real-valued model outputs and the binary-valued problem solutions. To address the discrepancy, we propose principled alternatives to the naive strategy used in PI-GNNs by building on insights from fuzzy logic and binarized neural networks. Our experiments demonstrate that the portfolio of proposed methods significantly improves the performance of PI-GNNs in increasingly dense settings.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA24-11664S" target="_blank" >GA24-11664S: Relational Reinforcement Learning for Science Acceleration</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2025

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

28th European Conference on Artificial Intelligence, 25-30 October 2025, Bologna, Italy – Including 14th Conference on Prestigious Applications of Intelligent Systems (PAIS 2025)

ISBN

978-1-64368-631-8

ISSN

0922-6389

e-ISSN

1879-8314

Number of pages

8

Pages from-to

2017-2024

Publisher name

IOS Press

Place of publication

Amsterdam

Event location

Bologna

Event date

Oct 27, 2025

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—