Diverse combinatorial optimization problems can be modeled as instances of the Pseudo-boolean Optimization (PBO) problem. The Predict-and-Search (PaS) framework is a powerful technique applied to Mixed Integer Linear Programming (MIP) that uses Graph Neural Networks (GNNs) to predict candidate variable values for guiding the search process of an optimization solver. Current PaS implementations rely on heuristically chosen labels during training and produce fast, good solutions, sacrificing optimality guarantees. We present Backbone-based Predict and Search (BackPaS), a specialized PaS framework for PBO. Our main contribution is redefining the GNN prediction task to identify backbones—literals fixed across all optimal solutions. Predicting these critical variables accelerates the search toward optimality if the network’s prediction is correct. BackPaS uses a specialized GNN architecture built on a literal-based bipartite graph to predict backbone membership and polarity, formulated as a multi-class classification problem. Then, a parameterized adaptive trust region incorporates these GNN predictions to adjust the solver’s search space. Empirically, we demonstrate that BackPaS effectively learns backbone patterns across PBO benchmarks, including Maximum Independent Set (MIS), Minimum Vertex Cover (MVC), and Combinatorial Auctions (CA). We trained the model on small instances for which we computed their backbones. When tested on much larger instances (up to \(6 \times \) the training size), our method achieves significant performance gains compared to the commercial solver Gurobi and the state-of-the-art PaS implementation ConPaS, substantially improving its anytime behavior and demonstrating strong generalization capabilities.