Fast OBDD Reordering using Neural Message Passing on Hypergraph
Ordered binary decision diagrams (OBDDs) are an efficient data structure for representing and manipulating Boolean formulas. With respect to different variable orders, the OBDDs' sizes may vary from linear to exponential in the number of the Boolean variables. Finding the optimal variable order has been proved a NP-complete problem. Many heuristics have been proposed to find a near-optimal solution of this problem. In this paper, we propose a neural network-based method to predict near-optimal variable orders for unknown formulas. Viewing these formulas as hypergraphs, and lifting the message passing neural network into 3-hypergraph (MPNN3), we are able to learn the patterns of Boolean formula. Compared to the traditional methods, our method can find a near-the-best solution with an extremely shorter time, even for some hard examples.To the best of our knowledge, this is the first work on applying neural network to OBDD reordering.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Hypergraph-MLP: Learning on Hypergraphs without Message Passing
Hypergraphs are vital in modelling data with higher-order relations containing more than two entities, gaining prominence in machine learning and signal processing. Many hypergraph neural networks leverage message passin…
Node ClassificationRepresentation LearningHow Particle System Theory Enhances Hypergraph Message Passing
Hypergraphs effectively model higher-order relationships in natural phenomena, capturing complex interactions beyond pairwise connections. We introduce a novel hypergraph message passing framework inspired by interacting…
Node ClassificationHypergraph Node Representation Learning with One-Stage Message Passing
Hypergraphs as an expressive and general structure have attracted considerable attention from various research domains. Most existing hypergraph node representation learning techniques are based on graph neural networks,…
Representation LearningMessage Passing Neural Networks for Hypergraphs
Hypergraph representations are both more efficient and better suited to describe data characterized by relations between two or more objects. In this work, we present a new graph neural network based on message passing c…
Graph Neural NetworkHypergraph representationsNode ClassificationEquivariant Hypergraph Neural Networks
Many problems in computer vision and machine learning can be cast as learning on hypergraphs that represent higher-order relations. Recent approaches for hypergraph learning extend graph neural networks based on message …