Understanding GNNs for Boolean Satisfiability through Approximation Algorithms

Result code in 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>
Alternative codes found
RIV/68407700:21730/24:00379757
Result on the web
<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>

Result language
angličtina
Original language name
Understanding GNNs for Boolean Satisfiability through Approximation Algorithms
Original language description
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.
Czech name
—
Czech description
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
S - Specificky vyzkum na vysokych skolach

Publication year
2024
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
Proceedings of the 33rd ACM International Conference on Information and Knowledge Management
ISBN
979-8-4007-0436-9
ISSN
—
e-ISSN
—
Number of pages
9
Pages from-to
953-961
Publisher name
Association for Computing Machinery
Place of publication
New York
Event location
Boise, Spojené státy americké
Event date
Oct 21, 2024
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)