Understanding GNNs for Boolean Satisfiability through Approximation Algorithms

• URL: http://arxiv.org/abs/2408.15418v1
• Date: Tue, 27 Aug 2024 21:47:09 GMT
• Title: Understanding GNNs for Boolean Satisfiability through Approximation Algorithms
• Authors: Jan Hůla, David Mojžíšek, Mikoláš Janota,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• GASE: Graph Attention Sampling with Edges Fusion for Solving Vehicle Routing Problems [6.084414764415137]
  We propose an adaptive Graph Attention Sampling with the Edges Fusion framework to solve vehicle routing problems. Our proposed model outperforms the existing methods by 2.08%-6.23% and shows stronger generalization ability.
  arXiv  Detail & Related papers  (2024-05-21T03:33:07Z)
• Batch Active Learning from the Perspective of Sparse Approximation [12.51958241746014]
  Active learning enables efficient model training by leveraging interactions between machine learning agents and human annotators. We study and propose a novel framework that formulates batch active learning from the sparse approximation's perspective. Our active learning method aims to find an informative subset from the unlabeled data pool such that the corresponding training loss function approximates its full data pool counterpart.
  arXiv  Detail & Related papers  (2022-11-01T03:20:28Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  We improve the theoretical and empirical performance of neural-network(NN)-based active learning algorithms for the non-parametric streaming setting. We introduce two regret metrics by minimizing the population loss that are more suitable in active learning than the one used in state-of-the-art (SOTA) related work.
  arXiv  Detail & Related papers  (2022-10-02T05:03:38Z)
• Simple Contrastive Graph Clustering [41.396185271303956]
  We propose a Simple Contrastive Graph Clustering (SCGC) algorithm to improve the existing methods. Our algorithm outperforms the recent contrastive deep clustering competitors with at least seven times speedup on average.
  arXiv  Detail & Related papers  (2022-05-11T06:45:19Z)
• Graph-Based Neural Network Models with Multiple Self-Supervised Auxiliary Tasks [79.28094304325116]
  Graph Convolutional Networks are among the most promising approaches for capturing relationships among structured data points. We propose three novel self-supervised auxiliary tasks to train graph-based neural network models in a multi-task fashion.
  arXiv  Detail & Related papers  (2020-11-14T11:09:51Z)
• Learning Connectivity of Neural Networks from a Topological Perspective [80.35103711638548]
  We propose a topological perspective to represent a network into a complete graph for analysis. By assigning learnable parameters to the edges which reflect the magnitude of connections, the learning process can be performed in a differentiable manner. This learning process is compatible with existing networks and owns adaptability to larger search spaces and different tasks.
  arXiv  Detail & Related papers  (2020-08-19T04:53:31Z)
• Towards Deeper Graph Neural Networks [63.46470695525957]
  Graph convolutions perform neighborhood aggregation and represent one of the most important graph operations. Several recent studies attribute this performance deterioration to the over-smoothing issue. We propose Deep Adaptive Graph Neural Network (DAGNN) to adaptively incorporate information from large receptive fields.
  arXiv  Detail & Related papers  (2020-07-18T01:11:14Z)
• Distributed Training of Graph Convolutional Networks [24.040921719350283]
  We show how to make inference in a distributed scenario where the underlying data graph is split among different agents. We then propose a distributed gradient descent procedure to solve the GCN training problem. Convergence to stationary solutions of the GCN training problem is also established under mild conditions.
  arXiv  Detail & Related papers  (2020-07-13T10:04:20Z)
• Learning the Travelling Salesperson Problem Requires Rethinking Generalization [9.176056742068813]
  End-to-end training of neural network solvers for graph optimization problems such as the Travelling Salesperson Problem (TSP) have seen a surge of interest recently. While state-of-the-art learning-driven approaches perform closely to classical solvers when trained on trivially small sizes, they are unable to generalize the learnt policy to larger instances at practical scales. This work presents an end-to-end neural optimization pipeline that unifies several recent papers in order to identify the principled biases, model architectures and learning algorithms that promote generalization to instances larger than those seen in training.
  arXiv  Detail & Related papers  (2020-06-12T10:14:15Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  We study a distributed variable for large-scale AUC for a neural network as with a deep neural network. Our model requires a much less number of communication rounds and still a number of communication rounds in theory. Our experiments on several datasets show the effectiveness of our theory and also confirm our theory.
  arXiv  Detail & Related papers  (2020-05-05T18:08:23Z)
• Binary Neural Networks: A Survey [126.67799882857656]
  The binary neural network serves as a promising technique for deploying deep models on resource-limited devices. The binarization inevitably causes severe information loss, and even worse, its discontinuity brings difficulty to the optimization of the deep network. We present a survey of these algorithms, mainly categorized into the native solutions directly conducting binarization, and the optimized ones using techniques like minimizing the quantization error, improving the network loss function, and reducing the gradient error.
  arXiv  Detail & Related papers  (2020-03-31T16:47:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.