PaperlayerView exact revision on arXiv

Source-linked AI summary

Network cross-validation by edge sampling

Tianxi Li, Elizaveta Levina, Ji Zhu

arXiv:1612.04717v7stat.MEstat.ML

TL;DR

Network cross-validation is challenging because node-based data splitting deletes edges and damages network structure. The paper proposes edge cross-validation, which splits node pairs, reconstructs missing entries through low-rank matrix completion, and evaluates candidate models on held-out edges. Theoretical and numerical results indicate that the approach supports model selection and tuning across several network settings.

  • Problem

    Cross-validation is not directly applicable to networks because splitting nodes into groups requires deleting edges and destroys part of the network structure.

  • Method

    ECV randomly splits node pairs, completes the partially observed adjacency matrix using low-rank matrix completion, and fits candidate models on the reconstruction.

  • Results

    Theoretical analysis and numerical experiments show that ECV works well for model selection on simulated networks and a statistician citation network.

  • Takeaways & Limitations

    ECV provides a general strategy for network model selection and parameter tuning without assuming a specific parametric network model.

  • Takeaways & Limitations

    Theoretical guarantees and the main framework are tied to low-rank or approximately low-rank structure and the inhomogeneous Erdős–Rényi setting, while alternatives were not explored.

Abstract

from arXiv · show

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

1. INTRODUCTION

Network cross-validation is difficult because conventional data splitting assumes independent observations, whereas deleting network edges can destroy structure. The paper addresses this gap with edge cross-validation, which splits node pairs and uses low-rank structure to reconstruct the partially observed network.

  • Motivation: Cross-validation is widely used for model selection and parameter tuning, but network inference commonly lacks comparable general resampling tools.The need is especially important because networks offer many candidate models and often require tuning parameters for fitting.
  • Challenge: Conventional node-based splitting deletes edges and produces incomplete networks, making standard cross-validation difficult to apply.The classical procedure holds out data, fits on the remainder, evaluates held-out error, and selects the model or tuning value minimizing that error.
  • Model framework: Network analysis estimates the probability matrix M from a single adjacency matrix A under structural assumptions.For undirected networks, A and M are symmetric and unique edges are modeled as independent Bernoulli variables.
  • Contribution: The proposed ECV strategy splits node pairs rather than nodes, treats the remainder as partially observed, and applies low-rank matrix completion before model fitting.The method is designed without assuming a specific network model, using an approximately low-rank probability matrix instead.

2. THE EDGE CROSS-VALIDATION (ECV) ALGORITHM

ECV randomly holds out node pairs, completes the resulting partially observed adjacency matrix, and evaluates candidate models on the held-out entries. Its theoretical guarantees rely on low-rank structure and show that the completed network can concentrate around the true probability matrix at the same rate as the full adjacency matrix under stated conditions.

  • Model scope: ECV applies broadly to popular low-rank network models, including stochastic block, degree-corrected, random dot product, latent space, and graphon settings.The framework is presented for binary networks but is directly applicable to weighted networks, including the paper’s citation-network application.
  • ECV procedure: ECV randomly holds out node pairs independently, creating a partially observed network whose missing entries are missing completely at random.For undirected networks, node pairs (i, j) and (j, i) are treated as one pair.
  • ECV procedure: Low-rank matrix completion reconstructs a complete network before candidate models are fitted and losses are evaluated on held-out adjacency entries.The general procedure accepts a loss function, candidate models or tuning values, a training proportion, and repeated random splits.
  • Implementation: More computationally demanding 1-bit matrix completion is not pursued because cross-validation cost is paramount while accurate matrix imputation is secondary.The alternative assumes a smooth transformation of M is low rank and uses binomial deviance rather than least-squares loss.
  • Theory: Theorem 1 shows that the completed estimator has the same concentration rate around M as the full adjacency matrix when Kd/n ≤1.For d = O(log n), the stated requirement becomes K ≤(n/ log n).

3. EXAMPLES OF ECV FOR MODEL SELECTION

The paper develops ECV for model selection by completing partially observed adjacency matrices and evaluating candidate models on held-out entries. It establishes one-sided theoretical guarantees and applies the method to rank selection and block-model community selection.

  • General ECV procedure: Model-free rank selection chooses the candidate rank minimizing averaged held-out loss across repeated random splits.The loss is averaged over repetitions before selecting the smallest minimizing rank.
  • General ECV procedure: ECV randomly holds out node pairs, completes the adjacency matrix at candidate ranks, and evaluates predictions using losses on held-out entries.The procedure supports squared-error, binomial-deviance, and link-prediction losses, including negative AUC for binary networks.
  • Theoretical guarantees: Under the random dot product graph model, P( K̂ < K) →0 when the expected degree satisfies λ_n/(n^1/3 log^4/3 n) →∞.This theorem assumes the low-rank and incoherence conditions stated for the model-free setting.
  • Theoretical guarantees: Theorem 2 provides the first model-selection guarantee under the random dot product graph model, according to the authors.The guarantee is one-sided: it controls under-selection rather than over-selection.
  • Block-model selection: For stochastic block models, ECV selects the number of communities with P( K̂ < K) →0 when λ_n/log n →∞ under L2 loss.The analysis uses spectral clustering for fitting stochastic and degree-corrected block models.
  • Block-model selection: The binomial deviance guarantee requires stronger expected-degree conditions than the L2 guarantee, and L2 performs better empirically in the reported comparisons.The paper attributes this difference in part to binomial deviance instability near 0.

4. NUMERICAL PERFORMANCE EVALUATION

Simulations evaluate ECV for block-model selection and graphon tuning. ECV is especially effective for harder block-model settings and successfully avoids poor tuning ranges in graphon estimation.

  • 4·1. Model selection under block models: ECV and stability-selection variants are compared with the method of Chen and Lei (2018) across 200 simulated replications.The comparison uses L2 loss; binomial deviance results are reported in supplementary material.
  • 4·1. Model selection under block models: ECV selects the correct degree-corrected block model more accurately than Chen and Lei’s method across all reported settings.The advantage becomes especially large as model selection becomes harder.
  • 4·1. Model selection under block models: For selecting the number of communities, ECV is the stronger of the two cross-validation methods, although model-based methods perform better overall.
  • 4·2. Tuning nonparametric graphon estimation: In graphon tuning, ECV usually selects the best τ for a low-rank piecewise-constant graphon and avoids bad τ values for a smoother non-low-rank graphon.The procedure is stable, so stability selection is unnecessary; errors are normalized Frobenius errors summarized over 200 replications.
  • 4·2. Tuning nonparametric graphon estimation: The graphon experiments show that the tuning constant can substantially change estimation error and that ECV can select it effectively.

5. COMMUNITY DETECTION IN A STATISTICIAN CITATION NETWORK

The paper applies ECV to a weighted author-citation network to detect research communities. The analysis focuses on the network core and uses spectral clustering because block models do not directly handle weighted networks.

  • Data and network construction: The dataset covers 3,607 authors and 3,248 papers published from 2003 to 2012 in four major statistics journals.
  • Data and network construction: The authors construct a weighted undirected author network whose edge weights are mutual citation counts.The largest connected component contains 2,654 authors.
  • Data and network construction: Thresholding the citation weights to binary produces unrealistically large community-count estimates, so the weighted network is analyzed instead.
  • Core extraction: The analysis focuses on the citation-network core, obtained by repeatedly deleting nodes with fewer than 15 mutual citations and their incident edges.
  • Community detection: For the weighted network, spectral clustering is applied through the Laplacian, and the model-free ECV procedure determines the number of communities.

6. DISCUSSION

The discussion identifies extensions of the edge-resampling framework and boundaries of the paper’s theoretical setting. Future work includes bootstrap-like resampling and alternatives to the inhomogeneous Erdős–Rényi model.

  • Scope and future work: The paper’s framework assumes conditionally independent upper-triangular adjacency entries given M.A separate experiment investigates robustness when this independence assumption is violated.
  • Scope and future work: The authors propose studying whether randomly held-out entries followed by matrix completion can generate bootstrap-like samples from one network realization.
  • Scope and future work: Cross-validation under alternatives to the inhomogeneous Erdős–Rényi model is identified as an unexplored direction.
  • Scope and future work: Questions involving additional node features are left for future work.

Network cross-validation 17

This section comprises references to prior work on network models, community detection, matrix completion, cross-validation, and related statistical methods.

  • References: Several cited works address community detection and spectral methods for stochastic block models and related networks.
  • References: The references also cover matrix completion, including noisy, binary, convex, and low-rank matrix-completion methods.
  • References: The cited literature includes foundational network models such as Erdős–Rényi and stochastic block models.

A. PROOFS

The proofs establish concentration and recovery guarantees under independent-edge network models, then use these results to justify community recovery and model-selection consistency for ECV splits.

  • Proof setup: The analysis models adjacency entries as independent Bernoulli variables with probability matrix M, whose rank and structural assumptions govern estimation.For undirected networks, the adjacency and probability matrices are symmetric, with unique edges independent.
  • Concentration tools: Concentration lemmas control adjacency and partially observed matrix errors using spectral, Frobenius, and max-norm arguments under logarithmic sparsity conditions.The proof combines random-matrix concentration with bounds for uniformly missing entries and low-rank matrices.
  • Community recovery: For each ECV split under the stochastic block model, spectral clustering recovers all but O(nλ_n^-1) nodes per community with probability tending to one.The guarantee assumes expected node degree λ_n ≥ C log(n), and recovery is up to permutation of block labels.
  • Community recovery: For the degree-corrected block model, spherical spectral clustering leaves at most O(nλ_n^-1/2) misclassified nodes per community with probability tending to one.This result requires the degree-parameter lower bound in Assumption A1 and the same logarithmic expected-degree condition.
  • Technical correction: The proofs impose the corrected perturbation condition ∥H∥ < λ_t/2 because the previously implicit condition ∥H∥ < λ_t was insufficient.The correction is identified as differing from the original statement in Eldridge et al. (2017).

B. ADDITIONAL DISCUSSIONS OF THE METHOD AND EMPIRICAL RESULTS

The paper applies ECV across rank estimation, regularized spectral-clustering tuning, community-number selection, model selection, matrix completion, and dependent-edge settings. Across simulations, ECV generally performs well, with stability selection often improving results and model-based methods retaining advantages in harder correctly specified cases.

  • Rank estimation: ECV estimates rank for directed random dot product graphs by evaluating candidate ranks after matrix completion.The method uses the general ECV algorithm with a candidate grid of ranks for this task.
  • Additional empirical findings: AUC-based ECV estimates K more accurately than SSE-based ECV, while improved matrix completion increases completion quality without changing model-selection results materially.The AUC advantage is reported for smaller sample sizes; hardImpute improves matrix completion at greater computational cost, but selection results are essentially the same.
  • Regularized spectral-clustering tuning: Regularization substantially improves sparse spectral clustering, and all data-driven methods achieve close-to-optimal clustering accuracy.In the reported setting, Davis–Kahan estimation and ECV with average stability selection perform best, followed closely by the other ECV variants.
  • Community-number selection: Across degree-corrected and stochastic block-model settings, stability selection improves ECV, and ECV performs better overall for selecting the number of communities.The average stability-selection variant is better than the mode variant in the reported comparisons.
  • Community-number selection: All ECV variants perform as well as or better than Chen & Lei (2018) across configurations that vary average degree, t, and β.The comparison concerns community-number estimation under balanced communities and fixed or varying network parameters.
  • Model selection: Model-based methods outperform cross-validation when K is large and networks are sparse, while ECV remains applicable beyond the assumed block-model family.The authors note that the model-based methods rely on the true model, whereas ECV selection can be interpreted through link prediction for the observed network.
  • Limitations: The AUC-based ECV variant has difficulty with perfectly separated communities, apparently because many ties affect the AUC.This issue is reported for β = 0 under the stochastic block model, characterized as an unrealistic scenario.
  • Dependent edges: ECV remains stable under the tested dependent-edge perturbation, whereas Chen & Lei (2018) without stability selection degrades as dependence increases.The robustness experiment examines violations of the conditional edge-independence assumption.
Loading 1612.04717v7…