Model selection, via penalized likelihood type criteria, is a standard task\nin many statistical inference and machine learning problems. Progress has led\nto deriving criteria with asymptotic consistency results and an increasing\nemphasis on introducing non-asymptotic criteria. We focus on the problem of\nmodeling non-linear relationships in regression data with potential hidden\ngraph-structured interactions between the high-dimensional predictors, within\nthe mixture of experts modeling framework. In order to deal with such a complex\nsituation, we investigate a block-diagonal localized mixture of polynomial\nexperts (BLoMPE) regression model, which is constructed upon an inverse\nregression and block-diagonal structures of the Gaussian expert covariance\nmatrices. We introduce a penalized maximum likelihood selection criterion to\nestimate the unknown conditional density of the regression model. This model\nselection criterion allows us to handle the challenging problem of inferring\nthe number of mixture components, the degree of polynomial mean functions, and\nthe hidden block-diagonal structures of the covariance matrices, which reduces\nthe number of parameters to be estimated and leads to a trade-off between\ncomplexity and sparsity in the model. In particular, we provide a strong\ntheoretical guarantee: a finite-sample oracle inequality satisfied by the\npenalized maximum likelihood estimator with a Jensen-Kullback-Leibler type\nloss, to support the introduced non-asymptotic model selection criterion. The\npenalty shape of this criterion depends on the complexity of the considered\nrandom subcollection of BLoMPE models, including the relevant graph structures,\nthe degree of polynomial mean functions, and the number of mixture components.\n