Network cross-validation by edge sampling

1. INTRODUCTION

• Network inference is often lacking, leaving model selection and tuning difficult; cross-validation offers a general, relatively model-free framework for these tasks.In ordinary cross-validation, models are fitted on training folds and compared by their errors on held-out data.Source: §1 · pp. 1–2

Notation and model

• The framework treats unique edges as independent Bernoulli observations with probability matrix M, the target of network-structure estimation.For undirected networks, the adjacency and probability matrices are symmetric.Source: §1 · p. 2, Notation and model · p. 2

2. THE EDGE CROSS-VALIDATION (ECV) ALGORITHM

• Under the exchangeable model assumption, held-out edge values are independent of training values, and the reconstructed network concentrates around the true model at the full adjacency matrix's rate.The held-out pairs are sampled regardless of their observed edge values, making missing entries completely at random.Source: §1 · p. 2, The ECV procedure · p. 4

1. INTRODUCTION

• ECV applies to directed and undirected, binary and weighted networks, with examples spanning latent dimension selection, block-model comparison, spectral-clustering regularization, and graphon smoothing.The framework is presented for binary networks but is directly applicable to weighted networks.Source: §1 · p. 2, Notation and model · p. 2

Notation and model

• The low-rank assumption covers stochastic-block-model variants and random dot product graphs; smooth graphon models can typically be approximated by low-rank matrices.The method works with the best low-rank approximation for graphon settings.Source: Notation and model · pp. 3–4

2. THE EDGE CROSS-VALIDATION (ECV) ALGORITHM

• ECV randomly holds out node pairs and applies low-rank matrix completion to reconstruct a full network before fitting relevant models.For undirected networks, each pair and its reverse are treated as one pair.Source: §1 · p. 2, The ECV procedure · p. 4
• ECV fits candidate models on the completed network, evaluates their losses on held-out edges, and selects the candidate with the smallest average loss.The procedure can use repeated random splits or K-fold cross-validation when many splits are computationally costly.Source: The ECV procedure · p. 4

Network recovery by matrix completion

• The practical completion method uses a rank-truncated SVD of the observed-entry matrix, offering low computational cost and running on networks of size 10^4–10^5 on a laptop.More sophisticated completion methods are possible, but the authors prioritize low cost because cross-validation is computationally intensive and imputation accuracy is secondary.Source: Network recovery by matrix completion · p. 5
• Truncating completed entries to [0,1] improves Frobenius-norm estimation, but the authors observed no substantial improvement in model-selection performance.When binary input is needed for subsequent fitting, a binary matrix can be produced from the truncated estimate using a standard link-prediction method such as thresholding at 0.5.Source: Network recovery by matrix completion · p. 5
• For binary networks, rescaling a zero-filled estimate by 1/p is a simple alternative, but ECV with matrix completion performs better and is more robust to p, while zero filling fails for weighted networks.For stochastic block models, this rescaling approach is equivalent to ECV using the specified matrix completion; beyond block models, the approaches differ.Source: Network recovery by matrix completion · pp. 5–6
• The authors do not pursue 1-bit matrix completion (Davenport et al., 2014; Cai & Zhou, 2013; Bhaskar & Javanmard, 2015) because it is more computationally demanding than Frobenius-norm completion.This approach uses binomial deviance and assumes a smooth transformation of the probability matrix is low rank; the projection latent space model is a special case.Source: Network recovery by matrix completion · p. 6

Theoretical justification

• With p ≥ C1 log n/n, d ≥ C2 log n, and Kd/n ≤ 1, the completed matrix’s spectral error concentrates at the same order as the full adjacency matrix, with probability at least 1−3n^-δ.Theorem 1 assumes a rank-K probability matrix and independently sampled edges and node pairs.Source: Theoretical justification · pp. 6–7
• For moderately sparse networks with d = O(log n), the rank requirement relaxes to K ≤ n/log n because replacing missing entries by zeros adds little to the overall error.Although the estimator is noisier for sparse networks, the complete- and incomplete-network noise bounds have the same order when p is constant.Source: Theoretical justification · p. 7
• When Kd ≤ n, the completed matrix can be treated as sampled from the same model in spectral-norm concentration, supporting model-estimation consistency and model selection.The passage states that, under many specific models, consistency is attainable at the rate obtained using the original adjacency matrix.Source: Theoretical justification · p. 7

Model-free rank estimators

• The rank K represents latent-space dimension in generic low-rank models, and rank selection compares each candidate completion with the adjacency matrix on held-out entries.The rank constraint may be unknown, motivating its selection before applying ECV.Source: Model-free rank estimators · p. 7
• Held-out loss can be sum of squared errors, binomial deviance for binary networks, or negative AUC for link prediction using thresholded completion values.AUC evaluates link prediction across thresholds; perfect prediction has AUC 1 and random guessing has AUC 0.5.Source: Model-free rank estimators · p. 7
• For each of N repetitions, ECV samples node pairs independently with probability p, fits each candidate rank on training pairs, averages held-out losses, and selects the rank with minimum average loss.The candidate ranks run from 1 to Kmax.Source: Model-free rank estimators · p. 8
• The authors report that imputation error and AUC work well for rank estimation, and that for block models they usually perform comparably to likelihood-based methods.With squared-error loss, the method is a network analogue of the tuning strategy of Mazumder et al. (2010).Source: Model-free rank estimators · p. 8
• Assumptions 1 and 2 require a regular low-rank probability matrix and bounded coherence; incoherence prevents eigenvector mass concentrating on few coordinates, and applies to SBMs under stated restrictions.The paper also notes these assumptions may be relaxed with a stronger condition on network density.Source: Model-free rank estimators · p. 8
• Under Assumptions 1 and 2, if expected degree λ_n grows faster than n^(1/3) log^(4/3)n, squared-error ECV has P(Khat < K) → 0 for random dot product graphs.The paper presents this as the first model-selection guarantee for the random dot product graph model.Source: Model-free rank estimators · p. 9

Model selection for block models

• The fitting procedure uses spectral clustering on the Laplacian, with row normalization before clustering for the degree-corrected model.The authors note that the fitting method is not crucial to model selection and use this simple, fast, common method.Source: Model selection for block models · p. 9
• For these undirected models, ECV samples node pairs and includes both edge directions; L2 loss worked slightly better in practice than binomial deviance.The probability estimate is scaled by the training proportion to account for missing edges.Source: Model selection for block models · pp. 9–10
• Algorithm 3 compares both block-model families for K = 1,…,Kmax and selects the family and K with the lowest average held-out loss.It evaluates losses on the node pairs excluded from each training split and averages them across replications.Source: Model selection for block models · p. 10
• Under Assumption 3 and λ_n/log n → ∞, Algorithm 3 with L2 loss has P(K_hat < K) → 0 when selecting K for a known stochastic block model.This is a one-sided guarantee: it rules out asymptotic underestimation, not all selection errors.Source: Model selection for block models · pp. 10–11
• For binomial deviance, the same guarantee requires λ_n n^-2/3 → ∞ and all entries of B0 positive, stronger conditions than for L2 loss.The authors characterize the result as a trade-off: parametric ECV gains better rates at the cost of additional model assumptions.Source: Model selection for block models · p. 11

Parameter tuning in graphon estimation

• For graphon estimation, ECV selects a rank for matrix completion in each split, then chooses the neighborhood-smoothing tuning parameter minimizing average prediction error.The true probability matrix need not have known rank or be low rank; for a smooth graphon, a low-rank matrix can approximate it reasonably well.Source: Parameter tuning in graphon estimation · p. 11
• ECV also applies to tuning network regularization in spectral clustering.This application is shown in Supplementary Material B·2.Source: Parameter tuning in graphon estimation · p. 11

Stability selection

• In ECV stability selection, the most frequently selected model across 20 replications is returned, while numerical parameters can be averaged across replications.Frequent selection is generally more robust to different tasks and to choices of p and N, though averaging may work better in some situations.Source: Stability selection · pp. 11–12

Model selection under block models

• ECV selects the correct degree-corrected block model more often than Chen & Lei (2018) in all settings, with especially large gains in harder cases.Results are based on 200 replications and use L2 loss; stability selection improves performance when single cross-validation is already working reasonably well.Source: Table 1 · p. 12, Model selection under block models · p. 13
• When the true block model is known, ECV is a clear winner over Chen & Lei (2018) for selecting the number of communities, but model-based methods are more effective overall.The comparison covers simulations and additional model-based methods, with details in the Supplementary Material.Source: Model selection under block models · p. 13

Tuning nonparametric graphon estimation

• For n = 500, ECV usually picks the best τ for low-rank block Graphon 1 and avoids bad τ ranges, achieving competitive error on non-low-rank Graphon 2.The reported error is normalized Frobenius error, summarized by the median over 200 replications with a bootstrap 95% confidence interval; stability selection is unnecessary for this tuning task.Source: Tuning nonparametric graphon estimation · p. 13

5. COMMUNITY DETECTION IN A STATISTICIAN CITATION NETWORK

• The dataset covers 3,607 authors and 3,248 papers published from 2003–2012 in four top statistics journals.It was compiled by Ji & Jin (2016) and includes paper titles, authors, years, citations, and DOIs.Source: §5 · p. 13
• Weight thresholding produced an uninterpretable, unrealistically large estimated number of communities, so the analysis uses mutual-citation counts rather than binary edges.The weighted undirected author network is formed by summing mutual citations; the authors note that ECV can switch between binary and weighted networks.Source: §5 · p. 14
• Iteratively removing authors with fewer than 15 mutual citations leaves a core network of 706 authors, with individual citation counts from 15 to 703 and a median of 30.The core is displayed in Figure 2, where node size and color encode citation counts.Source: §5 · p. 14, Figure 2 · p. 15
• For weighted-network community detection, the authors apply spectral clustering to the Laplacian and use model-free Algorithm 2 to determine the number of communities.The passage states that the block model is not defined for weighted networks, while the Laplacian remains well-defined.Source: §5 · p. 14

6. DISCUSSION

• Randomly leaving out entries and applying matrix completion may support other resampling methods, including bootstrap-like samples from a single network realization.The authors plan to investigate this bootstrap direction.Source: §6 · p. 15
• Future work could extend cross-validation beyond the inhomogeneous Erdös-Rényi model to alternatives such as Crane & Dempsey (2018) or Lauritzen et al. (2018).Source: §6 · p. 15
• The authors also leave ECV extensions for settings with additional node features, as in Li et al. (2019) and Newman & Clauset (2016), for future work.Source: §6 · p. 16

• The references include Chen and Lei’s work on network cross-validation for choosing the number of communities.Source: Network cross-validation 17 · p. 17
• The bibliography also cites work on matrix completion with biclustering structures and on stochastic blockmodels.Source: Network cross-validation 17 · p. 17

A.1. Proof of Theorem 1

• Lemma 1 bounds adjacency-matrix concentration when n max_ij p_ij ≤ d and d ≥ C0 log n.The result is attributed to Lei & Rinaldo (2014), with the same concentration also obtained by Chin et al. (2015) and Le et al. (2017).Source: A. PROOFS · p. 19
• Lemma 2 controls discrepancy for a bounded low-rank matrix under uniform missingness when p ≥ C1 log n/n, with probability at least 1 − n^-δ.The missingness mask is treated as an Erdős–Rényi adjacency matrix, and the lemma generalizes prior matrix-completion results to this uniform missing mechanism.Source: A. PROOFS · p. 20
• Lemma 3 provides a concentration bound for independent bounded matrix entries, with the constant depending on δ and σ.The proof of Theorem 1 uses this result to control the sampling fluctuation G ◦ W.Source: A. PROOFS · pp. 21–22
• Theorem 1’s proof applies to directed and undirected networks, combining concentration arguments to establish its bounds.The proof notes that the adjacency-matrix concentration result applies to both network types, so it does not use the symmetry of the network matrix.Source: A. PROOFS · pp. 22–23
• The Frobenius-norm bound (4) follows directly from (1) because rank(Â − M) ≤ 2K.Source: A. PROOFS · p. 23

Proofs for block models

• With expected degree λ_n ≥ C log(n), stochastic-block-model clustering recovers all but O(nλ_n^-1) nodes in each community with probability tending to one.Recovery is up to a permutation of block labels.Source: Proofs for block models · p. 23
• Under Assumptions 3 and A1 and expected degree λ_n ≥ C log(n), degree-corrected clustering misclassifies at most O(nλ_n^-1/2) nodes per community with probability tending to one.Recovery is up to a permutation of block labels; A1 requires degree parameters bounded below by a positive constant.Source: Proofs for block models · p. 23
• For both L2 and binomial deviance losses, ECV selects K over any smaller K′ with probability tending to one; the deviance result additionally requires ρ_n^-1 = o(n^2/3).The proof uses independence of test entries from training entries, conditional on the data; the comparison is stated explicitly for L2 and analogously for binomial deviance.Source: Proofs for block models · pp. 25, 30
• The authors correct Eldridge et al. (2017) by requiring ∥H∥ < λt/2 in Lemma 8, rather than the insufficient implicit condition ∥H∥ < λt.The correction addresses a gap in their formula (10).Source: Proofs for block models · p. 31
• Lemma 9 extends Eldridge et al. (2017) to random dot product graphs, providing entrywise eigenvector concentration that is tighter than the bound obtainable directly from Lemma 6.The lemma’s eigenvectors are unique up to an orthogonal transformation when eigenvalues have multiplicity greater than 1.Source: Proofs for block models · pp. 31–32
• The proof shows that the validation loss for any rank K′ < K exceeds that for K with probability tending to 1, so P(Khat < K) → 0.For K′ = K − 1, the comparison is established under n^1/3 log^4/3 n = o(nρ_n); the proof extends the bound to K′ < K − 1.Source: Proofs for block models · pp. 32, 34

Rank estimation for general directed networks

• The task is to select latent dimension K in a directed random dot product graph model M = XY^T; the authors note no obvious competitor because NCV is designed for block models.ECV can use either AUC or SSE loss, with average or mode stability selection.Source: Rank estimation for general directed… · pp. 36–37
• Simulations set the true rank to K = 3 or K = 5, vary node count n, and compare candidate ranks 1 through 8 using independently generated Bernoulli edges.The edge-probability matrix is formed from two random matrices and normalized to [0, 1].Source: Rank estimation for general directed… · p. 37
• With sufficiently large samples, all ECV versions estimate rank well; AUC-based ECV is more accurate than SSE-based ECV, especially for smaller samples, and stability selection adds little.The reported rank frequencies are summarized over 200 replications.Source: Rank estimation for general directed… · p. 37, Table 3 · p. 37

Tuning regularized spectral clustering

• ECV offers a data-driven alternative for selecting τ without model assumptions, balancing regularization’s improved concentration against the added noise from larger τ.The regularization considered replaces the usual normalized graph Laplacian with one computed from a regularized adjacency matrix.Source: Tuning regularized spectral clustering · p. 38
• The proposed loss compares edge partitions using co-clustering difference or normalized mutual information, offering a possible network-specific cross-validation loss for clustering.The authors note that choosing a cross-validation loss for network clustering is difficult and present this as one of several reasonable options.Source: Tuning regularized spectral clustering · p. 38
• For each τ, ECV completes matrices with held-out entries removed, estimates cluster labels, and compares the resulting edge partitions with those from the full adjacency matrix.The partitions group unordered node pairs by their cluster labels; a larger co-clustering difference indicates a worse τ choice.Source: Tuning regularized spectral clustering · pp. 38–39
• All data-driven methods achieved near-optimal clustering accuracy; DKest and ECV with average-based stability selection performed best, while unregularized accuracy was below 0.5.The comparison used 200 replications of sparse degree-corrected block-model networks with n = 600, K = 3, and average degree λ = 5.Source: Tuning regularized spectral clustering · p. 39, Figure 4 · p. 39

Additional model selection results under the block models

• Simulations varied sparsity, community-size balance, and the out-in ratio across three configurations: (n = 600, K = 3), (n = 600, K = 5), and (n = 1200, K = 5).Expected average degree λ ranged from 15 to 40; t controlled community-size balance and β the between- versus within-block probability ratio.Source: Additional model selection results… · p. 40
• Comparisons used 200 replications and tested ECV and Chen & Lei (2018) network CV, each with ordinary and stable selection; results reported use L2 loss.Stable selection returns the most frequent choice across 20 independent repetitions; the authors observed better performance with L2 loss than binomial deviance for both methods.Source: Additional model selection results… · p. 40
• Across degree-corrected and stochastic block models, stability selection improves performance and ECV performs better overall than network CV.The stochastic block model setting is easier, but the general pattern is similar to the degree-corrected setting.Source: Additional model selection results… · p. 41, Table 4 · p. 41, Table 5 · p. 42

Selecting the number of communities

• All ECV variants match or outperform Chen & Lei (2018) across configurations; stability selection improves ECV, with averaging better than mode, while mode is typically more accurate for Chen & Lei.The pattern remains similar when varying t or β; comparisons use degree-corrected block models, and results are reported as correct-estimation rates over 200 replications.Source: Table 8 · p. 45, Selecting the number of communities · p. 45, Table 9 · p. 46
• Wang & Bickel (2017) and Le & Levina (2015) usually perform perfectly and outperform cross-validation for large K in sparse networks, but rely on the true model and cannot handle other tasks.Cross-validation may remain useful under model misspecification; ECV selection can be interpreted as the block-model-family choice optimal for link prediction on the observed network.Source: Selecting the number of communities · p. 46, Table 11 · p. 47
• For the stochastic block model, ECV with AUC loss has difficulty when communities are perfectly separated (β = 0), plausibly because many ties affect AUC.The authors characterize β = 0 as an unrealistic scenario.Source: Selecting the number of communities · p. 47, Table 12 · p. 48

The impact of training proportion p and replication number N

• Small p provides too little training data and very large p leaves too little test data; increasing N generally helps, while stability selection makes performance more robust to p and N.Performance was similar for p > 0.85 across the considered N values; the paper uses p = 0.9 and N = 3 in its examples.Source: The impact of training proportion p… · p. 48, Figure 5 · p. 49, Figure 6 · p. 49

Comparison of different matrix completion algorithms

• HardImpute improves matrix-completion accuracy but takes longer, while ECV and ECV-h yield essentially the same model-selection results, suggesting adequate completion suffices for selection.The timing comparison is for reference because the implementations differ (Fortran for hardImpute and R for algorithm (2)).Source: Table 13 · p. 50, Comparison of different matrix… · p. 50

Simulation example of networks with dependent edges

• As edge dependence ρ increases, only Chen & Lei (2018) without stability selection degrades in overall model selection; ECV and both stability-selected methods remain unchanged.The experiment also evaluates community-count estimation under dependent edges; ρ ranges from 0 to 0.5.Source: Table 14 · p. 51, Simulation example of networks with… · p. 51, Table 15 · p. 51