Network cross-validation by edge sampling

While many statistical models and methods are now available for network analysis, resampling of network data remains a challenging problem. Cross-validation is a useful general tool for model selection and parameter tuning, but it is not directly applicable to networks since splitting network nodes into groups requires deleting edges and destroys some of the network structure. In this paper we propose a new network resampling strategy, based on splitting node pairs rather than nodes, that is applicable to cross-validation for a wide range of network model selection tasks. We provide theoretical justification for our method in a general setting and examples of how the method can be used in specific network model selection and parameter tuning tasks. Numerical results on simulated networks and on a statisticians’ citation network show that the proposed cross-validation approach works well for model selection.

• Publication year

  2016

• Venue

  Biometrika

• Publication date

  2016-12-14

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1093/biomet/asaa006arXiv 1612.04717
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Matrix completion from a computational statistics perspective

  2019cited by this paper
• A block model for node popularity in networks with community structure

  2018cited by this paper
• Edge Exchangeable Models for Interaction Networks

  2018cited by this paper
• Statistical Inference on Random Dot Product Graphs: a Survey

  2017cited by this paper
• Community detection and stochastic block models: recent developments

  2017cited by this paper
• A Semiparametric Two-Sample Hypothesis Testing Problem for Random Graphs

  2017cited by this paper
• Strong Consistency of Spectral Clustering for Stochastic Block Models

  2017cited by this paper
• Unperturbed: spectral analysis beyond Davis-Kahan

  2017cited by this paper
• Random networks, graphical models and exchangeability

  2017cited by this paper
• ENTRYWISE EIGENVECTOR ANALYSIS OF RANDOM MATRICES WITH LOW EXPECTED RANK.

  2017cited by this paper
• Cross-Validation With Confidence

  2017cited by this paper
• Random graph models for dynamic networks

  2016influential reference
• Prediction models for network-linked data

  2016cited by this paper
• Discussion of “Coauthorship and citation networks for statisticians”

  2016cited by this paper
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs

  2016cited by this paper
• Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression

  2016cited by this paper
• Stochastic Block Model and Community Detection in Sparse Graphs: A spectral algorithm with optimal rate of recovery

  2015cited by this paper
• Estimating the number of communities in networks by spectral methods

  2015cited by this paper
• Likelihood-based model selection for stochastic block models

  2015cited by this paper
• Estimating network edge probabilities by neighborhood smoothing

  2015cited by this paper
• 1-bit matrix completion under exact low-rank constraint

  2015cited by this paper
• Sparse random graphs: regularization and concentration of the Laplacian

  2015cited by this paper
• Concentration and regularization of random graphs

  2015cited by this paper
• Structure and inference in annotated networks

  2015cited by this paper
• Matrix completion by singular value thresholding: sharp bounds

  2015influential reference
• Achieving Optimal Misclassification Proportion in Stochastic Block Models

  2015cited by this paper
• Optimal Estimation and Completion of Matrices with Biclustering Structures

  2015cited by this paper
• Covariate-assisted spectral clustering

  2014cited by this paper
• How Many Communities Are There?

  2014cited by this paper
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries

  2014cited by this paper
• Universal Matrix Completion

  2014cited by this paper
• A goodness-of-fit test for stochastic block models

  2014cited by this paper
• On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models

  2014cited by this paper
• Coauthorship and Citation Networks for Statisticians

  2014cited by this paper
• Rate-optimal graphon estimation

  2014cited by this paper
• Network Cross-Validation for Determining the Number of Communities in Network Data

  2014influential reference
• Completing any low-rank matrix, provably

  2013cited by this paper
• Impact of regularization on spectral clustering

  2013cited by this paper
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel

  2013cited by this paper
• Hypothesis testing for automated community detection in networks

  2013cited by this paper
• A max-norm constrained minimization approach to 1-bit matrix completion

  2013cited by this paper
• Consistency of spectral clustering in stochastic block models

  2013influential reference
• Role of normalization in spectral clustering for stochastic blockmodels

  2013cited by this paper
• Nonparametric graphon estimation

  2013cited by this paper
• 1-Bit Matrix Completion

  2012cited by this paper
• Matrix estimation by Universal Singular Value Thresholding

  2012influential reference
• Co-clustering separately exchangeable network data

  2012cited by this paper
• Model selection for degree-corrected block models

  2012cited by this paper
• Asymptotic Normality of Maximum Likelihood and its Variational Approximation for Stochastic Blockmodels

  2012cited by this paper
• Universally Consistent Latent Position Estimation and Vertex Classification for Random Dot Product Graphs

  2012cited by this paper
• FAST COMMUNITY DETECTION BY SCORE

  2012cited by this paper
• Spectral Clustering of Graphs with General Degrees in the Extended Planted Partition Model

  2012cited by this paper
• Pseudo-likelihood methods for community detection in large sparse networks

  2012cited by this paper
• Consistency of community detection in networks under degree-corrected stochastic block models

  2011cited by this paper
• Spectral clustering and the high-dimensional stochastic blockmodel

  2010cited by this paper
• Rank Selection in Low-rank Matrix Approximations : A Study of Cross-Validation for NMFs

  2010cited by this paper
• Spectral Regularization Algorithms for Learning Large Incomplete Matrices

  2010cited by this paper
• Stochastic blockmodels and community structure in networks

  2010influential reference
• Bi-cross-validation of the SVD and the nonnegative matrix factorization

  2009cited by this paper
• Matrix Completion With Noise

  2009cited by this paper
• Variational Bayesian inference and complexity control for stochastic block models

  2009cited by this paper
• Matrix Completion from Noisy Entries

  2009cited by this paper
• The Power of Convex Relaxation: Near-Optimal Matrix Completion

  2009cited by this paper
• Stability selection

  2008cited by this paper
• Exact Matrix Completion via Convex Optimization

  2008cited by this paper
• CONSISTENCY OF CROSS VALIDATION FOR COMPARING REGRESSION PROCEDURES

  2007cited by this paper
• Fuzzy communities and the concept of bridgeness in complex networks.

  2007cited by this paper
• Workshop on Algorithms and Models for the Web Graph

  2007influential reference
• Graph limits and exchangeable random graphs

  2007cited by this paper
• Modeling homophily and stochastic equivalence in symmetric relational data

  2007cited by this paper
• Mixed Membership Stochastic Blockmodels

  2007cited by this paper
• Random Dot Product Graph Models for Social Networks

  2007cited by this paper
• Cluster Validation by Prediction Strength

  2005cited by this paper
• Rank, Trace-Norm and Max-Norm

  2005cited by this paper
• Convex Optimization

  2004cited by this paper
• Information-Theoretic Measures for Knowledge Discovery and Data Mining

  2003cited by this paper
• Finding the Number of Clusters in a Dataset

  2003cited by this paper
• The average distances in random graphs with given expected degrees

  2002cited by this paper
• Latent Space Approaches to Social Network Analysis

  2002cited by this paper
• Estimating the number of clusters in a dataset via the gap statistic

  2000influential reference
• Linear Model Selection by Cross-validation

  1993cited by this paper
• Model Selection Via Multifold Cross Validation

  1993cited by this paper
• On the evolution of random graphs

  1984cited by this paper
• The evolution of random graphs

  1984cited by this paper
• Stochastic blockmodels: First steps

  1983cited by this paper
• Representations for partially exchangeable arrays of random variables

  1981cited by this paper
• Computational Statistics and Data Analysis

  year unknowncited by this paper

• Regularized Joint Maximum Likelihood Estimation of Latent Space Item Response Models.

  2026cites this paper
• Optimal estimators and tests for reciprocal effects

  2026cites this paper
• Balanced Stochastic Block Model for Community Detection in Signed Networks

  2026cites this paper
• Adjacency Spectral Embeddings of Correlation Networks

  2026cites this paper
• How many asymmetric communities are there in multi-layer directed networks?

  2026cites this paper
• Overlapping Community Detection in Statistical Keyword Co-Occurrence Network by Mixed-SCORE

  2025cites this paper
• Joint estimation of asymmetric community numbers in directed networks

  2025cites this paper
• Simultaneous estimation of connectivity and dimensionality in samples of networks

  2025cites this paper
• On Optimal Tracking of Structural Changes in Time-Varying Networks

  2025cites this paper
• Strongly Consistent Community Detection in Popularity Adjusted Block Models

  2025cites this paper
• Multiple Hypothesis Testing To Estimate The Number Of Communities in Stochastic Block Models

  2025cites this paper
• Latent space models for grouped multiplex networks

  2025cites this paper
• A Unified Framework for Community Detection and Model Selection in Blockmodels

  2025influential citation
• Network Model Averaging Prediction for Latent Space Models by K-Fold Edge Cross-Validation

  2025cites this paper
• Consistent Estimation of the Number of Communities in Non‐uniform Hypergraph Model

  2025influential citation
• A New Spectral‐Based Goodness‐of‐Fit for Stochastic Block Models With Strong Power

  2025cites this paper
• LOBSTUR: A Local Bootstrap Framework for Tuning Unsupervised Representations in Graph Neural Networks

  2025influential citation
• Network embedding for bipartite networks with applications in interlocking directorates in Chinese companies

  2025cites this paper
• A Goodness-of-Fit Test for Sparse Networks

  2025cites this paper
• BASIC: Bipartite Assisted Spectral-clustering for Identifying Communities in Large-scale Networks

  2025cites this paper
• Network Varying Coefficient Model

  2025cites this paper
• Dynamic spectral co-clustering of directed networks to unveil latent community paths in VAR-type models

  2025cites this paper
• Network Goodness-of-Fit for the Block-Model Family

  2025cites this paper
• Exploratory analysis of dynamic networks using latent functions

  2025cites this paper
• Detecting small clusters in the stochastic block model

  2025cites this paper
• Comprehensive overview of machine learning applications in MOFs: from modeling processes to latest applications and design classifications

  2025cites this paper
• Randomized Spectral Clustering for Large-Scale Multi-Layer Networks

  2025cites this paper
• Transfer Learning on Edge Connecting Probability Estimation under Graphon Model

  2025cites this paper
• Adaptive Bayesian Joint Latent Space Modeling via Cumulative Shrinkage

  2025cites this paper
• Bootstrap-based statistical inference on the eigenvalues of weighted networks

  2025cites this paper
• Transfer learning under latent space model

  2025cites this paper
• Two-sample test of stochastic block models via the maximum sampling entry-wise deviation

  2024cites this paper
• Community detection in stochastic block models via penalized variational estimation

  2024cites this paper
• Identifying Credit Card Fraud with Machine Learning: Evaluation of Algorithms and Oversampling Techniques

  2024cites this paper
• A General Latent Embedding Approach for Modeling Non-uniform High-dimensional Sparse Hypergraphs with Multiplicity

  2024cites this paper
• Network Embedding-based Directed Community Detection with Unknown Community Number

  2024cites this paper
• A Latent Space Model for Weighted Keyword Co-Occurrence Networks with Applications in Knowledge Discovery in Statistics

  2024cites this paper
• Optimizing the Induced Correlation in Omnibus Joint Graph Embeddings

  2024cites this paper
• Improved Monitoring and Classification of Engine Oil Condition through Two Machine Learning Techniques

  2024cites this paper
• Model-Based Co-Clustering in Customer Targeting Utilizing Large-Scale Online Product Rating Networks

  2024cites this paper
• Co-Factor Analysis of Citation Networks

  2024cites this paper
• Deep network embedding with dimension selection

  2024cites this paper
• GBTM: Community detection and network reconstruction for noisy and time-evolving data

  2024cites this paper
• Selecting the Number of Communities for Weighted Degree-Corrected Stochastic Block Models

  2024cites this paper
• Determining the Number of Communities in Sparse and Imbalanced Settings

  2024cites this paper
• Homophily-adjusted social influence estimation

  2024cites this paper
• GELT: A graph embeddings based lite-transformer for knowledge tracing

  2024cites this paper
• Environmental risk assessment and management of nuclear power plants based on big data analysis

  2024cites this paper
• Dynamic clustering for heterophilic stochastic block models with time-varying node memberships

  2024cites this paper
• Reduced Rank Spatio-Temporal Models

  2024cites this paper
• On Inference for Modularity Statistics in Structured Networks

  2024cites this paper
• Two-Sample Hypothesis Testing for Large Random Graphs of Unequal Size

  2024cites this paper
• Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals

  2024cites this paper
• Two-sample test of stochastic block models

  2023cites this paper
• Variational inference for the latent shrinkage position model

  2023cites this paper
• Turning hazardous volatile matter compounds into fuel by catalytic steam reforming: An evolutionary machine learning approach

  2023cites this paper
• Community models for networks observed through edge nominations

  2023cites this paper
• Statistical Network Analysis: Past, Present, and Future

  2023cites this paper
• Applications of dual regularized Laplacian matrix for community detection

  2023cites this paper
• Clustered Graph Matching for Label Recovery and Graph Classification

  2023cites this paper
• Moran's I Lasso for models with spatially correlated data

  2023cites this paper
• A Spike-and-Slab Prior for Dimension Selection in Generalized Linear Network Eigenmodels

  2023cites this paper
• A Random Graph-based Autoregressive Model for Networked Time Series

  2023cites this paper
• Intelligent monitoring of water quality based on image analytics.

  2023cites this paper
• of the Bernoulli Society for Mathematical Statistics and Probability Volume Twenty Nine Number Four November 2023

  2023cites this paper
• Semiparametric Modeling and Analysis for Longitudinal Network Data

  2023cites this paper
• Spectral co-clustering in multi-layer directed networks

  2023cites this paper
• Crying over spilled milk? A network analysis of aversive well-being comparison, brooding rumination and depressive symptoms.

  2023cites this paper
• A matrix completion bootstrap method for estimating scale-free network degree distribution

  2023cites this paper
• On the Estimation of the Number of Communities for Sparse Networks

  2023cites this paper
• Subsampling in Large Graphs Using Ricci Curvature

  2023influential citation
• A Network Analysis of Cardiovascular Risk Factors in Patients With Heart Disease: The Role of Socioeconomic Status and Sex

  2023cites this paper
• Special invited paper: The SCORE normalization, especially for heterogeneous network and text data

  2023cites this paper
• Stock co-jump networks

  2023cites this paper
• Privacy-Preserving Community Detection for Locally Distributed Multiple Networks

  2023cites this paper
• Detection of Temporal Shifts in Semantics Using Local Graph Clustering

  2023cites this paper
• Variational Inference: Posterior Threshold Improves Network Clustering Accuracy in Sparse Regimes

  2023influential citation
• Subsampling-based modified Bayesian information criterion for large-scale stochastic block models

  2023influential citation
• Two-sample test of sparse stochastic block models

  2023cites this paper
• Independence testing for inhomogeneous random graphs

  2023cites this paper
• Distribution-Free Matrix Prediction Under Arbitrary Missing Pattern

  2023cites this paper
• SIMPLE-RC: Group Network Inference with Non-Sharp Nulls and Weak Signals

  2022cites this paper
• Multiple Hypothesis Testing To Estimate The Number of Communities in Sparse Stochastic Block Models

  2022cites this paper
• Optimal Estimation of the Number of Network Communities

  2022cites this paper
• Tensor Completion for Causal Inference with Multivariate Longitudinal Data: A Reevaluation of COVID-19 Mandates

  2022cites this paper
• Stochastic Block Smooth Graphon Model

  2022cites this paper
• Discussion of “Cocitation and Coauthorship Networks of Statisticians”

  2022cites this paper
• The SCORE normalization, especially for highly heterogeneous network and text data

  2022cites this paper
• Network resampling for estimating uncertainty

  2022influential citation
• Identifiability and parameter estimation of the overlapped stochastic co-block model

  2022cites this paper
• On the efficacy of higher-order spectral clustering under weighted stochastic block models

  2022cites this paper
• Signed Network Embedding with Application to Simultaneous Detection of Communities and Anomalies

  2022cites this paper
• Fallacy of data‐selective inference in modelling networks

  2022cites this paper
• Identifying peer influence in therapeutic communities adjusting for latent homophily

  2022influential citation
• Lost in the shuffle: Testing power in the presence of errorful network vertex labels

  2022cites this paper
• Linear Regression with Centrality Measures

  2022cites this paper
• Joint Spectral Clustering in Multilayer Degree-Corrected Stochastic Blockmodels

  2022cites this paper
• Consistent estimation of the number of communities via regularized network embedding

  2022cites this paper
• Hypothesis testing for equality of latent positions in random graphs

  2021cites this paper
• An Annotated Graph Model with Differential Degree Heterogeneity for Directed Networks

  2021cites this paper