Understanding GNNs for Boolean Satisfiability through Approximation Algorithms

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61988987%3A17610%2F24%3AA25038EX" target="_blank" >RIV/61988987:17610/24:A25038EX - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21730/24:00379757

Výsledek na webu

<a href="https://arxiv.org/pdf/2408.15418" target="_blank" >https://arxiv.org/pdf/2408.15418</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3627673.3679813" target="_blank" >10.1145/3627673.3679813</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Understanding GNNs for Boolean Satisfiability through Approximation Algorithms

Popis výsledku v původním jazyce

The paper deals with the interpretability of Graph Neural Networks in the context of Boolean Satisfiability. The goal is to demystify the internal workings of these models and provide insightful perspectives into their decision-making processes. This is done by uncovering connections to two approximation algorithms studied in the domain of Boolean Satisfiability: Belief Propagation and Semidefinite Programming Relaxations. Revealing these connections has empowered us to introduce a suite of impactful enhancements. The first significant enhancement is a curriculum training procedure, which incrementally increases the problem complexity in the training set, together with increasing the number of message passing iterations of the Graph Neural Network. We show that the curriculum, together with several other optimizations, reduces the training time by more than an order of magnitude compared to the baseline without the curriculum. Furthermore, we apply decimation and sampling of initial embeddings, which significantly increase the percentage of solved problems.

Název v anglickém jazyce

Understanding GNNs for Boolean Satisfiability through Approximation Algorithms

Popis výsledku anglicky

The paper deals with the interpretability of Graph Neural Networks in the context of Boolean Satisfiability. The goal is to demystify the internal workings of these models and provide insightful perspectives into their decision-making processes. This is done by uncovering connections to two approximation algorithms studied in the domain of Boolean Satisfiability: Belief Propagation and Semidefinite Programming Relaxations. Revealing these connections has empowered us to introduce a suite of impactful enhancements. The first significant enhancement is a curriculum training procedure, which incrementally increases the problem complexity in the training set, together with increasing the number of message passing iterations of the Graph Neural Network. We show that the curriculum, together with several other optimizations, reduces the training time by more than an order of magnitude compared to the baseline without the curriculum. Furthermore, we apply decimation and sampling of initial embeddings, which significantly increase the percentage of solved problems.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2024

Kód důvěrnosti údajů

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

Název statě ve sborníku

Proceedings of the 33rd ACM International Conference on Information and Knowledge Management

ISBN

979-8-4007-0436-9

ISSN

—

e-ISSN

—

Počet stran výsledku

9

Strana od-do

953-961

Název nakladatele

Association for Computing Machinery

Místo vydání

New York

Místo konání akce

Boise, Spojené státy americké

Datum konání akce

21. 10. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—