Quadratic programming (QP) problem reformulations have been studied for decades [Sherali and Tuncbilek(1995), Nemirovski and Shapiro(2006), Anstreicher(2009)], [Zheng et al.(2012)Zheng, Sun, Li, and Cui, Wu and Jiang(2017)], but rarely linked to Graph Theory. Indeed, typical reformulations focus on convexifying a non-convex QP problem, making the objective function differentiable, optimizing on the continuous domain while ensuring the final solution is binary, or adding regularizers and Lagrangian coefficients to optimize the dual problem. In this paper, we take SVM as an example to demonstrate that QP problems can also be reformulated using the same mechanism as P/NP problem reduction, overcoming speed and memory footprint limitations from other types of reformulation. We show that SVM is comparable to a soft weighted edge independent set problem where the amount of support vectors per class is balanced, thus it can also be reformulated as a maximum weighted clique problem (MWC) with the same class balancing constraint. After adapting the sequential minimal optimization (SMO) algorithm [Platt(1998), Fan et al.(2005)Fan, Chen, and Lin] to our new MWC formulation, we demonstrate that such reformulation leads to improved performance (7∼36 time faster to train, and sparser solution for comparable accuracy).