The optimization of expensive-to-evaluate black-box functions overcombinatorial structures is an ubiquitous task in machine learning, engineeringand the natural sciences. The combinatorial explosion of the search space andcostly evaluations pose challenges for current techniques in discreteoptimization and machine learning, and critically require new algorithmicideas. This article proposes, to the best of our knowledge, the first algorithmto overcome these challenges, based on an adaptive, scalable model thatidentifies useful combinatorial structure even when data is scarce. Ouracquisition function pioneers the use of semidefinite programming to achieveefficiency and scalability. Experimental evaluations demonstrate that thisalgorithm consistently outperforms other methods from combinatorial andBayesian optimization.