Cross-Validation for Network-Assisted Prediction

Thomas M. Menino Convention & Exhibition Center 

Cross-validation (CV) is a popular statistical learning technique used to select and evaluate prediction models. This work specifically concerns network-assisted prediction, where latent node positions are extracted from an observed network and further used to predict a node-level response, possibly combined with traditional node-level covariates. The difficulty for model evaluation in this very standard framework arises from the non-exchangeability of the network-connected observations. If one fits all the embeddings using the entire network and then evaluates the regression model via standard CV, training data will see test node connections ahead of time and thus have an "unfairly'' more accurate estimator of the training design. We first demonstrate that this leakage of test node information causes standard cross-validation to underestimate the true out-of-sample risk. We then propose Leave-One-Node-Out Cross-Validation (LONOCV), which corrects for this by refitting the embeddings with one node removed before evaluating the regression model on that node. Additionally, we derive an efficient rank-one update approximation that efficiently recomputes the leave-one-node-out embeddings from the full-network embeddings. Experiments on synthetic and real datasets confirm that LONOCV substantially improves both model selection and evaluation relative to standard cross-validation, at negligible additional computational cost.

Cross-validation

Network-assisted prediction

Network analysis

Model selection 

Section on Statistical Learning and Data Science