Binary quadratic programming (BQP) is a class of combinatorial optimization problems comprising binary variables, quadratic objective functions and linear/non-linear constraints. In this paper, we propose a unified framework to reformulate any BQP problem with linear constraints to a new BQP problem defined on a graph. This framework relies on the concept of stars in the graph and partitioning the quadratic costs into in-star and out-of-star interactions. We exploit the star-based structure of the new reformulation to develop a decomposition-based column generation algorithm. In our computational experiments, we evaluate the performance of our methodology on different applications with different quadratic structures in which the quadratic component of the problem is dealt with in the column generation master problem and in its subproblem. Results suggest that the framework outperforms the state-of-the-art solver in almost all the instances having zero out-of-star interactions both in terms of dual bound and computational time.