Graphon Cross-Validation: Assessing Models on Network Data
Authors: Huimin Cheng
Yongkai Chen
Ping Ma
Wenxuan Zhong
Venue: ICLR 2026 Poster (2026)
Keywords: Graphon
Link prediction
Cross-Validation
Graph imputa- tion
Selection consistency
Primary area: learning on graphs and other geometries & topologies

Abstract: Graphon models have emerged as powerful tools for modeling complex network structures by capturing connection probabilities among nodes. A key challenge in their application lies in accurately characterizing the graphon function, particularly with respect to parameters that govern its smoothness, which significantly impact the estimation accuracy. In this article, we propose a novel graphon cross-validation method for selecting tuning parameters and estimation approaches.
Our method is both theoretically sound and computationally efficient.
We show that our proposed cross-validation score is asymptotically parallel to the estimation error. Through extensive simulations and real-world applications, we demonstrate that our method consistently delivers superior computational efficiency and accuracy.

Published as a conference paper at ICLR 2026
GRAPHON CROSS- POOS-VALIDATION!. ASSESSING MODELS ON NETWORK DATA
Huimin Cheng"
Yongkai Chen'
Department of Biostatistics
Department of Statistics
Boston University
Harvard University
Boston, MA, USA
Cambridge, MA, USA yongkaichenf fas hww.ara. edu
huimin23@bu.c edu
Ping Ma
Wenxuan Zhong'
Department of Statistics University of Georgia Athens, GA, USA pi Singm@uuga.ee edu
Department of Statistics
University of Georgia Athens, GA, USA wenxuan@uga.edm edu
ABSTRACT
Graphon models have emerged powerful tools for modeling complex network structures by capturing connection probabilities among nodes. key challenge in their application lies in accurately characterizing the graphon function, partie- ularly with respect to parameters that govern its smoothness, which significantly impact the estimation accuracy. In this article, propose novel graphon cross- validation method for selecting tuning parameters and estimation approaches. Our method is both theoretically sound and computationally efficient. We show that our proposed rross-valiatiion score is asymptotically parallel to the estimation error, and the selected model asymptotically converges to the optimal model. Through extensive simulations and real-world applications, we demonstrate that our method consistently delivers superior computational efficiency and accuracy.
INTRODUCTION
Graphon models represent cutting-edge statistical and machine-learning techniques for describing intricate network structures. In these models, the presence of an edge between nodes i and j hinges on a probability, independently determined by a measurable symmetric graphon function f across the unit square (Lovász and Szegedy 2006). The graphon function f, the key to the model, gauges the probability of node connections. Accurately estimating f poses significant challenge to the models' general application. The efficacy of existing estimation methods is intrinsically linked to the precise calibration of tuning parameters. For instance, the accuracy of the graphon function estimated using the port-and-smoothe
(SAS) method (Chan and Airoldi| 2014) or the neighborhood siighborhood-smoothing (NS) method (Zhang et al. 2017) is heavily contingent on the chosen size of the neighborhood. This parameter is analogous to the bandwidth in kernel smoothing and is crucial for the estimation process. As depicted in Figure D varying the neighborhood size parameter can result in markedly different estimates of the graphon function, highlighting the sensitivity of the model to this tuning parameter.
Cross-validation validation (CV) is widely regarded as the gold standard for parameter tuning and model selection by dividing the dataset into subsets, training the model on a portion of the data, and then testing it on the remaining data. The primary goal of cross-validation to assess how well a model generalizes new, unseen data. Yet, when applied network data, traditional CV encounters fundamental obstacle: it assumes the independence of observations-a condition that is invariably violated by the interconnected nature of network nodes. Consequently, the standard practice of random sampling on nodes falls short, calling for an alternative approach to data splitting, which is critical the integrity of the model validation process.
"quual contribution. Corresponding author.

---

Published as a conference paper at ICLR 2026
True
Low
Medium
Large
Figure 1: From left to right, we present the healmap of true graphon probability matrix, the estimated graphon probability matrix (under low, medium, and large hyperparameters).
In graphon models, where edges are presumed to follow an independent Bernoulli distribution, the method of edge sampling takes particular importance compared to node sampling. Common practices involve randomly removing edges and using the remaining graph for training. However, direct edge sampling can change the network's 's inherent topology and connectivity, thereby altering neighborhood structure, which introduces a significant bias the estimation of the graphon function. In addition, direct edge sampling may lead to a sampling bias when the network partitioned into training and testing sets, potentially resulting in different distributions. Such bias has profound implications: may trigger an inaccurate estimation of the standard deviation, distort confidence intervals, and undermine hypothesis testing reliant on exact margins of error. Ultimately, it may elevate prediction error, thereby impairing the model's predictive efficacy. (2220a proposes imputing entries of matrix A corresponding to reserved node pairs using matrix completion algorithm. However, critical condition of this approach that P must be a low-rank matrix, which can be violated in dense networks. Furthermore, while theoretical guarantees exist for specific models like the Stochastic Block Model and the Random Dot Product Graph Model within the graphon model class, they lacking for the broader category. Additionally, the computational cost of iteratively conducting matrix completion is prohibitively expensive, hindering the general applicability of the proposed algorithm in practical settings.
response, [Li al.
To face these challenges, this paper introduces perturbation- -baed sampling method that innovatively splits data into training and testing sets. This method judiciously applies controlled perturbations to the network edges, thereby ensuring that training and validation data remain representative of the network's comprehensive distribution. Our condition is that the graphon function's 's smoothness not compromised by such perturbations, allowing for more faithful estimation of the true graphon. The method is versatile, accommodating varying degrees of sparsity and complexity within the network. We rigorously validate our approach against standard edge sampling methods, employing a series of experiments that underscore both theoretical and practical merit.
MODEL SETUP
Network analysis was originally developed to map out the relationships or connections between various entities, which can represent either samples features. network G (V, E) is composed of vertex set V = {o.li- = 1,2,.... .2....,n) n)} and an edge set & = {11, uy) fy are connected). Let (()) be an indicator function that maps subset {-} to one and all other elements to zero. Mathematically network can be represented by a
binary matrix, say A, with the (i.j)th entry aij, where ag ((E)) This matrix A is generally referred to as the adjacency matrix.
In this article, we assume that the asjs are independent and follow Bernoulli distributions with mean Pij respectively, i.e.,
0ij Ber(pis),
Model is known as the inhomogeneous random graph model (Soderberg 2002 van der Hofstad 2013 Ghoshdastidar al. 2020). Clearly, Pij not estimable unless we impose specific constraint. Consequently, we further assume:
Pij = f( My).
where f: [0, 1] x [0, + [0, 1] is referred to as the graphon function and the function is smooth. Here, μ4 and My represent latent parameters associated with vertices v, and By, respectively. Without loss of generality, we further assume that of is bounded symmetric function, and additionally, μ4 for 1 I i independently and identically distributed from uniform distribution interval [o, 1].
2

---

Lemma 1. If A follows graphon model with E(A) = P, we can deduce that the value of any entry in [k] is mutually independent of the node connectivity for node pairs in the validation set Sk- Published as a conference paper at ICLR 2026
Clearly, is neither unique identifiable as ff and s4, confounding with each other (Diaconis and Janson 2007). Thus, instead of estimating f. researchers usually focus on the estimation of the probability matrix P [pty]. The combined model described by ! and 2 is commonly referred to as the graphon model. Graphon model is a general non-parametric model (Chan and Airoldi 2014) which encompasses a variety of model classes, each with its own conditions Common model classes include piecewise constant graphons, piecewise linear graphons, and smooth graphons. Model selection involves choosing the appropriate class that best captures the underlying structure of the graph data.
Given f's inherent smoothness, researchers commonly embrace the concept of neighborhood smooth- ing methods, often utilized in spatial analysis, to gauge Pij by capitalizing on adjacent node val- ues. Noteworthy methodologies in this domain encompass the neighborhood smoothing (NS) method (Zhang et al., (017), which amalgamates nodes sharing common neighbors, and the sort- and-smoothing (SAS) method (Chan and Airoldi 2014), which pool nodes with akin degrees. Both techniques center on identifying neighboring nodes within network, requiring the establishment of a neighbor. The parameters that define the neighbor usually gauge the accuracy of the estimates.
GRAPHON CROSS- VALIDATION WITH RANDOM IMPUTATION
Let P(M A) be the estimated probability matrix of observing A given model M M, where M represents the candidate pool of models. The performance of the model M can be assessed via the mean squared error
1 II)((MIA)))) - PI L(M)- n(n 1) [P(MIA)
Given M, the model M. E .M that minimizes ((M represents the ideal choice one would like to make given the observed A and is referred to as the optimal model. Given the need for edge sampling methods that preserve the network's 's structural integrity while minimizing the introduction of biases, we propose the K folf cross-validation with a random imputation method. The general idea of this approach is to treat the edges in the validation set missing values that need be randomly imputed before model training.
We randomly partition the set {(1,, my) V V. {} into K subsets S,, Sk. where each subset contains approximately =(n-1) node pairs. This partitioning ensures that the subsets are of 2K
approximately equal size and that each node pair has an equal chance of being included in any of the subsets. Let A [R. denote the set of observed entries azj for node pairs within Sg. For the kth fold validation, we generate the training adjacency matrix A ll-)), of which the iýth entry is
A [-A kl
{{
asj if Uz) & Sx bij otherwise,
where bys are independently identically sampled from the Bernoulli distribution with mean O. This equation defines how the training adjacency matrix is constructed by incorporating the observed training entries aij and randomly imputed entries byy. serves as tuning parameter and remains fixed as a constant throughout our procedure. The selection of 0 is discussed in Section S.4
We have the following Lemma:
More precisely, given P. we have that 1 is distributed according Bernoulli distribution with parameter wg0 (1 Wy)Pss where wk represents the proportion of number of node pairs in Sk
and Pij represents the linking probability for (V,, Uz))
Lemma I ensures the independence between A k] and A given P. which follows directly from the independence of the edges. It also demonstrates that despite the training set and the original graph holding different distributions, their distribution can be mapped to each other through an affine transformation. Let pl-k denote the nodes connecting probability matrix of the n X n adjacency
matrix A [- We have
pl w00111 (1 Wx)PP,
(5)
3

---

Published as a conference paper at ICLR 2026
where 1 is the ones vector. The proof of Lemma
| provided in the Appendix.
Equation 5) implies that with the kth fold training data A i-k and model M, we can obtain predictor of as follows:
PM(M) P(M w60112
(6)
W/
where P(M[Al--)) is the estimate of P( computed based on method M or model M with the training data A Al-M), Let p!) (M) denote the predicted probability for validation node pairs (vi; vy) Se. It is evident that Pij (M) corresponds to the (i. entry of (M)(M). Therefore, M can be selected if it minimizes the following prediction error:
K
2
Vx
Σ
(
(M) (M) a.j)?
n(n
k= (H..P))..
In practice, p (M) may exceed one or fall below zero due to computational or measurement errors.
In such cases, we truncate the estimated P.j (M) to ensure it lies within the interval [0, 1]. Given a
set of candidate models M, we select the optimal model My which minimizes Vx (M). The detailed algorithm for the proposed K-fold cross- validation is provided in the Appendix Algorithm D1
Computational cost. To evaluate a set of [M] candidate hyperparameters on an n-node network using K-fold cross-validation, the total computational complexity of our CV-imputation method is O(IM) (I.Mi-KKCessee (n) +n²)), n))), where Cestm (n) denotes the cost of the specific graphon estimator (e.g., NS, ICE). The detailed analysis can be found in Section S.8, Existing graphon estimation method usually have Cestim greater than n². So the cost is mainly dominated by the graphon estimation method itself rather than by CV-imputation itself. In contrast, the competing ECV method has complexity O[LM] (KCestim (n) + KT mc (n))) where (n) is the matrix completion complexity. The critical difference between our CV-imputation and ECV is the additional overhead per fold: Our method adds simple (n²)) cost for imputation and transformation. ECV adds much larger (n)) cost for matrix completion, which typically O(n") for a full SVD. Thus our method more computationally efficient than ECV. For very large networks, practical way to scale CV- imputation is to combine it with network subsampling: (1) extract a structurally representative subgraph using network sampling methods (e.g.. Metropolis-Hastinne
random walk Hu and Lau (201),, survature-based sampling Wu et al. (2023)), ), (2) apply CV-imputation on this subgraph to tune hyperparameters, and (3) fit the full network using the selected hyperparameter.
THEORETICAL JUSTIFICATION
A set of potential graphon estimates is denoted by P(M where M M. The CV-imputation score crafted to fine-tune M to select the best estimate from this set. In this section, we offer asymptotic justifications for the CV-imputation score.
We aim to demonstrate that Vx (M) approximates I(M) uniformly up to a constant by postulating assumptions the maximum K-fold optimism bias:
15k5K nnn -) P(MIA) - -Pa(a
(k(M) = sup
where || || denotes the Frobenius norm. The optimism bias quantifies the maximum prediction bias between the full-sam tull-sample estimate and the estimate obtained after data splitting and imputation. Then, under the following conditions:
Condition 1. There exists a positive constant a > O such that for any M E M and any E > 0, there exist a constant ōn and an integer Ko such that
(1 10((M)
P
2 50
Se
AK 2 Ko.
K K
show that
4

---

Published as a conference paper at ICLR 2026
Theorem 1. As + and K oc.
Vx(M) L(M) - A AA -0 ( k V Ka
1
uniformly, where m(n-1) Pis(1 - -Pi)). and V denotes the operator that returns the largest of two values.
Theorem suggests that the validation score Vx (M) is a consistent estimator of L(M) + A with an rate of K V Ka. Note that A does not depend M, the validation score function (-(-) and the loss function L(-) asymptotically parallel in probability. Thus, the probability that the minimizer of Vx 7x((M MM approximately minimizes L(M) is high within a neighborhood of Mo- Theorem Tesemntillllll establishes the consistency of the CV-imputation score, ensuring that the score for each candidate model is close to its true loss up to constant. The proof of Theorem | is provided in the appendix.
It is worth noting that Condition T specifies that the maximum K- optimism bias is bounded by polynomial rate of K~a The polynomial order a is determined by the complexity of the underlying graphon model and the efficiency of the estimation methods. For instance, in the case of an
model (Erdos and Renyi 1959) where f Hg) = P, we have the simple averaging estimator and letting K x n. Unlike many assumptions that are not verifiable, Qk(M) can be verified computationally. as both P(M and Ps (M) are accessible from the data. In Figure S.3 in the Appendix, the validation of Condition is provided. Further discussion of Condition 1| can be found in Section SS.O
when using
EMPIRICAL STUDIES
To compare the empirical performance of our method to the edge cross-validation method proposed in Li et al. 2020a), we investigate their performance using data generated from four graphon models introduced in (Chan and Airoldi 2014). Figure 2 Jillustrates the probability matrices P of 200 nodes generated for Graphons 1 to 4. Graphons 1 and generate dense networks, while Graphons and 4 yield sparse networks. Graphons 1, 3, and 4 produce low-rank probability matrices, while Graphon produces full-rank probability matrices. All results are averaged over 100 replications. The experiments are conducted on a machine equipped with a 40-core CPU and 192 GB of RAM. The implemtation issues or our methods are detailed in Section S.4 in the Appendix.
Graphon
(Low Rank)
Graphon 2
(High Rank) Graphon 3
(Low Rank)
Graphon
(Low Rank)
p = 0. 0.95
0.29
F 0.13
1-CXPX-M00 +131
mm (en (snstroz) ) (2)0)-))) 0se0)te)) [oo]l 6aM(4]]
2
Figure 2: The heatmaps generated by Graphons to are displayed from right.
To evaluate the empirical performance of our method, we it to select the tuning parameter for four state-of-the-art graphon estimation methods: (1) neighborhood smoothing (NS) method (Zhang et al. 2017). (2) sort-and-smooth (SAS) method (Chan and Airoldi 2014). (3) universal singular value thresholding (USVT) method (Chatterjec) 2015). and (4) iterative connecting probability estimation method (ICE) QQin et al. 2021). All four methods make different conditions about the underlying model. In each of these estimation methods, the parameter M, although with different meanings, governs the trade-off between goodness-of-fe and model complexity. For instance, in the NS method, M represents the neighborhood size, while in the SAS method, it denotes the number of blocks. We apply our method with the selected tuning parameter to the synthetic datasets generated from the four aforementioned graphon functions. This enables to compare the estimated graphons with the true underlying graphon functions and assess the performance of our method in recovering the underlying structure of the graphons using the mean squared error (MSE) measurement denoted by L(M).
5

---

Published as a conference paper at ICLR 2026
In Table we present the estimation accuracy measured by L(M) for 200. The table illustrates that for all five estimation methods, our method and ECV select M resulting in lower MSE values compared to the default selection. This underscores the significance of tuning M for all five estimation methods. Moreover, CV-imputation method consistently selects models with smaller MSE values compared to those chosen by ECV for all five methods and all synthetic datasets.
Table 1:
The mean + standard deviation of MSE across 100 replicates are calculated using M selected by CV-i impuuattiinn, ECV, and default selection. To facilitate comparison, all values are multiplied by 100. Note that ICE does not have a default model setup, so the default ICE results are not shown in this table.
Graphon ID
Graphon
Graphon 2
Graphon 3
Graphon 4
CV-imputation (NS)
0.51 = 0.07
2.13 +: 0.15
0.79 = 0.07
1.05 - 0.06
ECV (NS)
9.15 1 19.25
3.82 1 0.21
3.07
0.95
1.06 1 0.10
Delault NS (M=1)
39.05 1 3.33
2.75 1. 0.16
0.74 0.04
1.06 1 0.10
CV-impulation (USVT)
0.28 0.03
2.99 1 0.19
0.61 0.10
0.75 0.05
ECV (USVT)
0.60
0.09
5,06
+ 0.27
1.18 0.02
1.08 + 0.74
Default USVT (M=0.01)
0.60
0.09
5.06
+ 0.25
1.18
0.02
2.79 +: 0.26
CV-imputation (SAS)
1.69 = 0.11
8,43
0.22
12.77 + 0.20
1.49 + 0.10
BCV (SAS)
1.72 = 0.12
8,47
12,86 = 0.23
1,53 0.11
Delauli SAS (M-lgg)
1.93 0.15
8.77
0.23
13.64 1 0.60
1.89 0.14
CV-imputation (ICE)
0,31 0.03
2.69 + 0.24
0.50
0.06
0.82 = 0.06
BCV (ICE)
0.32 0.05
3.05
0.35
0.53 1 0.06
0.86 1 0.06
Figure provides comparison of the end-to-end computational cost between our method (CV-imputation) and ECV. Here, the reported CPU time includes both the cost of fitting the graphon estimators (NS, USVT, SAS, ICE) and the cross-validation overhead (fold construction, masking, pre- diction on validation edges, and loss aggregation). It is clear that our method consistently outperforms ECV in terms of speed across all tested configurations. To isolate estimator fitting overhead from the cross-valls valss-valiotionn mechanism itself, Figure S.7 further reports the cross- valissvviiiaiion-nnn runtime (with the graphon estimation time subtracted out). The pooss-validation-onn results show that CV-imputation also remains substantially faster than ECV at this level, confirming that the observed speedup is indeed driven by our CV-imputation scheme.
To evaluate the consistency of our model selection method as network size increases, we compare mean square validation error Vx() (t) and mean squared error (MSE) L(.). Both errors are standardized L-min(L) using the function max( (z) for better visualization. In Figure we focus on the performance of CV-imputation for the NS estimator. Additional plots for the other three estimation methods are provided in Figure S.4 Figure [S.] and Figure [S.6] in the supplementary materials. We examine the influence of parameter M ranging from 0.5 to 5 with increment of 0.5. The number of nodes in the network ranges from 50 to 200 in steps of 50 to allow for an evaluation of performance as the network size increases towards asymptotic levels.
Figure 4 demonstrates that the model selected by our method rapidly converges to the optimal model M.. When n 50, the model selected by our method aligns with the optimal model selected by MSE for Graphons| and 2, a pattern that holds across all graphons when = 200. Similar trends were observed for all the other methods. These simulations demonstrate that CV-imputation maintains rank consistency in model selection for any given estimation approach.
Similar traditional cross-validation (CV) techniques, CV-imputation offers a model-agnostic measure for assessing a model's generalization to new data. The term "agnostic" in this context indicates that our method is unbiased towards any specific model or estimation technique. It functions independently of particular conditions or methods and can be universally applied, irrespective of the underlying model structure or estimation process.
The upper panel of Figure demonstrates the consistent superiority of our method over ECV across various graphon configurations, with more pronounced benefits observed for smaller network sizes (n). It is important to note that Figure 5 evaluates the method selection task, choosing which estimation method (NS, USVT, SAS, or ICE) with its optimally tuned hyperparameter should be used, rather than hyperparameter tuning for single method. Notably, at = 200, our method achieves 100% accuracy rate in selecting the best candidate model - that is, the one with the lowest estimation Mean Squared Error (MSE) among all estimators obtained by the five given estimation methods. Here,

---

Published as a conference paper at ICLR 2026
Graphon
Graphon 2
Graphon
Graphon 4
Time (seca)
(sens)
Time (6908)
Time (seus)
NS
80
0-
60
100
190
200
00
100
150
200
60
100
100
800
100
150
200
60-
Time (oocss
(sece)
Time (saca)
Time (sece)
USVT
80-
40
0
01
50
100
100
200
00
100
100
800
00
100
1.00
200
00
100
150
200
Time (secs)
Time (secs)
Time (68c5)
15
SAS
10-
1.50
80
Tinee (sees)
80-
Time (seos)
86
Time (secs)
80
ICE
80-
40-
16
80
100
190
90
100
100
800
60
1.50
200
100
100
200
CV-imputation
ECV
Figure 3: The plots display the average computational time (in seconds) for Graphons 1 to 4 with n (50, 100, 150, 200). arranged from left to right. The panel from top to bottom corresponds to the NS method, the USVT method, the SAS method, and the ICE method, respectively.
n=50
n=100
n=150
n=200
Graphon
300
200
Naihtochood
Naightohooddd
Kelg Moothooodo
Nelp toorfood
Graphon
1.00
1.0
Graphon
Weightchhodd
Weighoohood
Neggbootooo
nelgtorrood
Graphon
Nelghtchood S
Naihtonood Sae
Naigtboroood Stee
Nelgtooroood Stas
CV-imputation
MSE
for CV-imputation (red) and MSE (black) under varying values of the tuning parameters for the NS method. vary neighborhood parameter M from 0.5 5 with increments of 0.5, while number nodes n ranges from to 200 with an increment 50. Each row corresponds to specific graphon function listed in Figure
Figure 4: Plotted here the
7

---

Published as a conference paper at ICLR 2026
Graphon
Graphon
Graphon
Graphon
1.40
1.00
1.00
0.75
0.55
0.00
0.00
0.00
2.00
120
Number
Number
nodes
(190)
Trne spece
Time tsecal
Time baecel
100
200
100
150
120
CV-imputation
ECV
Figure 5: Method selection performance across different graphon designs. The plots display average selection accuracy and computational time (in seconds) for Graphons 4, arranged from left to right. The top panel illustrates CV-imputation's 's model selection accuracy as increases from 50 to 200 in steps of 50, while the bottom panel shows the corresponding computational time. Here, accuracy is defined as the percentage of cases where the model with the smallest mean squared error (MSE) selected from the top-tuned estimators obtained using NS, SAS, USVT, and ICE, respectively.
"accuracy" denotes the percentage of cases where our method successfully identifies the optimal candidate model. This indicates that our method is particularly efficient for model selection compared to ECV. Furthermore, the lower panel of Figure displays the computational efficiency of our method in relation ECV. The reported time measures only the computational cost of the method selection step itself, excluding the time spent on hyperparameter tuning for each individual method. Our approach consistently outperforms ECV in terms of speed across all configurations. These results collectively highlight the effectiveness and efficiency of our approach for model selection.
CASE STUDY: MODEL SELECTION IN LINK PREDICTION
We applied our method to four networks: the drug-disease co-occurrence network with 280 nodes and 952 edges; the political blogs network, consisting of 1,222 nodes and 16,714 edges (Adamic and Glance 2005); the coauthorship network for seientists in network science, which contains 1,589 nodes and 2,742 edges (Newman 2006); and the yeast protein-protein interaction network, comprising 2,617 nodes and 11,855 edges (Von Mering et al. 2002). These example networks vary in size, including moderate-sized networks suitable for detailed analysis and larger networks that illustrate real-world computational challenges. Analyzing these networks allows us to evaluate the capability of CV-imputation to accurately identify existing connections and potentially uncover new insights.
For all networks, we used both CV-imputation and ECV to first tune each estimation method to obtain the optimal Mimeehod, and then compared across the aforementioned candidate estimation methods-NSs ICE, SAS, and USVT-to identify the best graphon estimate My- Since NS and ICE are highly computationally intensive, we did not include them as candidate methods for large networks with over 1,000 nodes.
6.1 MODERATE SIZE NETWORK: TEXT CO-OCCURRENCE NETWORK FOR COVID-19
In this study, the abstracts of 5,496 publications were retrieved from the Medline database using "COVID-19" as the query term and time window of January 2020, April 30, 2020. After conducting data cleaning and entity annotation procedures, we identified entities related to drugs or diseases and constructed co-oceurrence network consisting of 280 nodes and 952 edges The network is sparse, with density of only 0.02. The co-occurrence network, depicted in Figure B(a), highlights two central nodes: COVID-19 and hydroxychloroquine. what follows, we show our estimation results using neighborhood smoothing method (Zhang et al. 2017) for variable neighbourhood size.
'The generated data can be freely downloaded from the following website:
8

---

Published as a conference paper at ICLR 2026
(a)
[b]
(c)
Covid-19
Hydevschoo Bauuhe
0.75
Accuracy
Score
3.00
0.5
0.5
1.0
1.5
2.0
Tuning Parameter M
Tap q predictions
OV-mmoutation
+ ECV
Default
Figure 6: (a) Discase-drug co-oceurrence network with red and green nodes representing diseases and drugs, respectively. (b) CV-imputation score and ECV score with different models M. (c) Accuracy of CV-imputation and ECV for different q.
Figure g () illustrates the relationship between the average prediction error of K-fold cross-validation (CV) and the neighborhood size parameter M, ranging from 0.2 to 2. The minimum average prediction error L(M) occurs M 1.2, contrasting with ECV, which achieves its minimum at
M = 0.4.
To evaluate the empirical performance of the CV-imputation method against ECV, we utilize testing data extracted from articles published between May 1, 2020, and May 15, 2020. A predicted link deemed correct if it also exists in the testing network. Figure 5(c) illustrates the proportion of the correctly predicted links among the top predicted links with q ranging from 10 to 50, for M = 1.2 (selected by CV-imputation) and M = 0.4 (selected by ECV) respectively. Generally, as more predicted links are included, the accuracy tends to decrease. However, our method consistently outperforms ECV in terms of prediction accuracy. Furthermore, our method boasts computational cost of 56.76 seconds, which is more efficient than the 71.82 seconds required for ECV, as it eliminates the need for the time-consuming matrix completion step. Remarkably, among all current unlinked node pairs, the third highest predicted probability corresponds ledipasvir, a drug primarily developed for treating hepatitis C virus infections. Our findings suggest potential repurposing of ledipasvir to treat COVID-19. Recent research findings support our discovery, indicating that ledipasvir, when combined with sofosbuvir, exhibits significant potential to inhibit SARS-CoV-2 replication (Pirzada et al. 202T). This medical condition was further confirmed by a recently completed phase-3 clinical trial. This particular application underscores the importance of our approach in drug repurposing efforts.
link between COVID-19 19 and
6.2 LARGE SIZE NETWORKS: POLITICAL BLOGS NETWORK, COAUTHORSHIP NETWORK, AND PROTFIN ICTERN NETWORK.
To evaluate the prediction accuracy, we randomly sampled 10% of the node pairs from each network, with the connectivity of the sampled node pairs used as testing data to assess link prediction accuracy and computational efficiency. Three large networks: the political blogs network (PolBlog), the coau- thorship network for scientists in network science (NetSci), and the yeast protein- interaction network (Yeast) were compared on the area under the curve (AUC) metric, and the average time taken in minutes metric.
As shown in Table 2. CV-imputation significantly outperforms the ECV method for the PolBlog and NetSci networks while demonstrating comparable prediction accuracy for the Yeast network. Moreover, since CV-imputation eliminates the highly computationally intensive matrix completion step in each fold, it substantially reduces computational costs, making it significantly more efficient.
Table 2: AUC (average standard deviation) and computational time in minutes (average + standard deviation) of CV-imputation and ECV, over 100 replications.
PolBlog
NetSei
Yeast
AUC
CV-iputaatinn
0.88 + 0.01
0.72 = 0.01
0.80 = 0.02
BCV
0.80 + 0.02
0.70 + 0.01
0.80 = 0.02
Time (seconds)
CVimputation
56.90 + 0.13
51.01 + 3.96
240.90 +: 16.22
BCV
258.65 2.11
771.23
10.00
6021.12
18.72

---

Published as a conference paper at ICLR 2026
7 CONCLUSIONS AND DISCUSSIONS
Our proposed method, denoted as CV-imputation, offers several key advantages that make it valuable tool for analyzing network data. Firstly, CV-imputation versatile as it does not assume any specific form for the graphon function, making it broadly applicable across different types of networks. This flexibility enables researchers to apply CV-imputation to various network structures without conforming to specific model.
Moreover, CV-imputation is supported by rigorous theoretical foundations, showing that the min- imizer of CV-imputation asymptotically converges the minimizer of the mean squared error (MSE) in our model. This theoretical basis enhances confidence in the accuracy and consistency of CV-imputation results.
In terms of computation efficiency, CV-imputation outperforms existing methods by eliminating costly singular value decomposition (SVD) steps, making it particularly suitable for analyzing large networks. Our simulation studies have confirmed the superior performance of CV-imputation, further highlighting its effectiveness in practical applications.
Beyond graphons, CV-imputation may extend to broader network models that preserve the required edge-independence structure, such latent-space networks and generalized sparse graphons. Sec- tion S.9 provides preliminary empirical support and discusses how our theoretical results may extend to these settings. Establishing formal guarantees in these settings remains an important direction for future work. However, our method can not be extended to models with temporal or sequential dependence since they violate edge independence.
In summary, CV-imputation stands out an efficient, versatile, and theoretically grounded method for analyzing networks. Its user-fries ser-friendly implementation and lack of tuning requirements make it a practical choice for various network analysis tasks.
USE OF LLMS
During the preparation this manuscript, the authors used ChatGPT (https://opmai.com/)) solely for improving the language, readability, and correcting the grammar.
ACKNOWLEDGMENTS
This work was partially supported by the U.S. National Science Foundation [DMS-1925066 DMS- 1903226, DMS-2124493, DMMS-211299, of Health [NIH R01GM152814]. The authors thank reviewers for helpful discussions and support.
DMS-231 and the National Institutes
REFERENCES
Adamic, L. and Glance, N. (2005), The political blogosphere and the 2004 us election: divided they blog, in PProceedings of the 3rd international workshop on Link discovery', pp. 36-43.
Athreya, A., Fishkind, D. E., Tang, M., Priebe, C. E., Park, Y., Vogelstein, J. T., Levin, K., Lyzinski, V., Qin, Y. and Sussman, D. L. (2018), 'Statistical inference random dot product graphs: survey', Journal of Machine Learning Research 18(226), 1-92.
Chan, S. and Airoldi, E. (2014), 'A consistent histogram estimator for exchangeable graph models', International Conference on Machine Learning pp. 208-216.
Chatterjee, S. (2015), 'Matrix estimation by universal singular value thresholding' The Annals of Statistics 43(1), 177-214.
Diaconis, P. and Janson, S. (2007), 'Graph limits and exchangeable random graphs', arXiv preprint arXiv:0712.2749.
Erdos, P. and Renyi, A. (1959), 'On random graphs. publicationes mathematicae (debrecen), vol. 6'.
10

---

Published as a conference paper at ICLR 2026
Ghoshdastidar, D., Gutzeit, M., Carpentier, A. and Luxburg, U. (2020), Twwo-samle hypothesis testing for inhomogeneous random graphs', Annals of Statistics 48(4).
Hoff, P. D., Raftery, A. E. and Handcock, M. S. (2002), 'Latent space approaches to social network analysis', Journal of the american Statistical association 97(460), 1090-1098.
Hu, P. and Lau, W. C. (2013), 'A survey and taxonomy of graph sampling', arXiv preprint arXiv: 1308:v8330.865
Klopp, O., Tsybakov, A. B. and Verzelen, N. (2017), 'Oracle incqualities for network models and sparse graphon estimation', Annals of Statistics 45(1), 316-354.
Li, J., Wu, S., Cui, C., Xu, G. and Zhu, J. (2023), 'Statistical inference on latent space models for network data', arXiv preprint arXiv:2312.06665
Li, T., Levina, E. and Zhu, J. (2020a), 'Network cross-validation by edge sampling'. Biometrika 107(2). 257-276.
Li, T., Levina, E. and Zhu, J. (20206), 'Network cross-validation by edge sampling', Biometrika 107(2), 257-276.
Lovász, L. and Szegedy, B. (2006), 'Limits of dense graph sequences', Journal of Combinatorial Theory, Series B 96(6), 933-957.
Newman, M. E. (2006), FFinding community structure in networks using the eigenvectors of matrices', Physical review E 74(3,, 036104.
Pirzada, R. H., Haseeb, M., Batool, M., Kim, M. and Choi, S. (2021), 'Remdesivir and ledipasvir among the fda-approved antiviral drugs have potential to inhibit sars-cov-2 replication', Cells 10(5), 1052.
Qin, Y., Yu, L. and Li, Y. (2021), 'Iterative connecting probability estimation for networks', Advances in Neural Information Processing Systems 34.
Söderberg, B. (2002), 'General formalism for inhomogencous random graphs', Physical review E 66(6), 066121.
van der Hofstad, (2013), 'Critical behavior in inhomogeneous random graphs', Random Structures & Algorithms 42(4), 480-508.
Von Mering, C., Krause, R., Snel, B., Cornell, M., Oliver, S. G., Fields, S. and Bork, P. (2002), 'Com- parative assessment large-scale data sets of protein-protein interactions', Nature 417(6887), 399- 403.
Wu, S., Cheng, H., Cai, J., Ma, and Zhong, W. (2023), Subsampling in large graphs using ricci curvature, in "International Conference on Learning Representations'
Zhang, Y., Levina, E. and Zhu, J. (2017), 'Estimating network edge probabilities by neighbourhood smoothing' Biometrika 104(4), 771-783.


Reviews:
[{"review_id": "SMReVqeC0m", "reviewer": "Reviewer_Q27V", "summary": "The paper proposes CV-imputation, a cross-validation method for selecting graphon-based models on network data. The method is model-agnostic, computationally efficient, and supported by theoretical guarantees of asymptotic consistency. Empirical results show that it outperforms or matches existing methods across various networks.", "questions": "1. How sensitive is CV-imputation to violations of the graphon assumption? Are the theoretical guarantees still meaningful outside the graphon framework?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. CV-imputation does not assume a specific form of the graphon, allowing it to be applied across diverse network structures without model restrictions. \n2. The method avoids expensive singular value decomposition (SVD), reducing runtime and enabling scalability to large networks. \n3. It is supported by a convergence result showing that its validation criterion aligns with mean squared error minimization in the asymptotic regime.", "weaknesses": "This work assumes the data comes from a graphon and the goal is to assess graphon-based estimators. However, would such a method be extended beyond this assumption? Discussion about the limitations of applicability would be a nice addition to the paper.\n\nAdditional discussion on the order complexity of the method vs the baselines would strengthen the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mfbFxDfKMg", "reviewer": "Reviewer_NTvL", "summary": "This paper proposes a new cross-validation approach for graphon estimation, introducing a random-imputation strategy to handle dependency structures in networks and to tune hyperparameters from a single observed graph. The authors argue that existing edge-sampling methods lead to bias by degrading network connectivity, and they provide a careful theoretical treatment to show consistency of their approach. The work is technically sound and well written, but the contribution represents a relatively narrow conceptual advance within the specific context of graphon models rather than a broader methodological step forward for network machine learning. The empirical results, while generally positive, do not convincingly demonstrate consistent or substantial gains over edge-based cross-validation (ECV). The paper would be strengthened by a deeper analysis of when and why ECV fails in practice, clearer discussion of how the proposed method could generalize beyond the graphon setting, and a more comprehensive evaluation showing robust and meaningful performance improvements across a wider range of network types.", "questions": "See weaknesses.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper addresses a legitimate technical challenge: how to form cross-validation sets in under dependence in networks. The proposed CV-imputation scheme is clearly described, mathematically justified, and accompanied by consistency proof. The implementation appears efficient, and the experiments consider several graphon estimators (NS, SAS, USVT, ICE), as well as both synthetic and real-world graph datasets. The manuscript is generally clear and thorough.", "weaknesses": "(1)\tScope and generality. The method applies specifically to graphon models and depends on smoothness and exchangeability assumptions. It is unclear how the proposed theoretical framework or random-imputation idea would extend to broader classes of network models (e.g., latent-space, temporal, or sparsified networks). Thus the paper’s claims of general applicability thus seem overstated.\n(2)\tEmpirical impact. The experimental gains over ECV are modest. In Table 1, SAS and ICE show no meaningful improvement, suggesting that differences arise mainly from estimator robustness rather than from the proposed validation method. In real-world datasets, results are essentially tied on three of four networks. Only the drug–disease network shows a visible advantage, which is not analyzed in depth. Without more in-depth analysis demonstrating the impact of ECV bias, it is difficult to conclude that the differences are practically important.\n(3)\tEfficiency gains. Although Figure 3 shows a computational speed-up relative to ECV, the paper does not provide an asymptotic complexity comparison. Moreover, the statistical efficiency results in Figure 5 are averaged across all graphon models and may be dominated by the weaker performance of NS and USVT, making it hard to assess whether the gains are consistent or meaningful across settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fLjZrdIRBf", "reviewer": "Reviewer_9pGj", "summary": "This paper introduces an improved cross-validation method with random imputation, which is unbiased and efficient compared to existing methods including edge sampling approaches and the matrix completion method proposed by Li et al. (2020). The paper compares against these baselines across multiple graphon estimation methods, demonstrating effectiveness in terms of both accuracy and computational efficiency. The authors provide theoretical justification showing that their cross-validation score is asymptotically correct. I found that this paper is strong and provides a comprehensive analysis based on both theory and numerical evidence. The case studies are insightful and demonstrate practical applicability of the proposed method.", "questions": "I am unclear why the computational time differs across estimation methods (Figure 3), since the cross-validation procedure itself should be independent of the estimation method being evaluated. I suspect the authors calculated the total CPU time, which includes both the cross-validation procedure and the estimation method execution, rather than isolating the cross-validation overhead alone. This make it unclear the actual speedup specifically attributable to CV-imputation compared to ECV. The authors should clarify what operations are included in their reported CPU times and, ideally, provide a breakdown separating cross-validation overhead from estimation costs.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The authors effectively articulate the fundamental challenge in applying cross-validation to network data, particularly how traditional edge sampling destroys network topology.\n\n2.  The random imputation strategy is quite simple and very effective. I could not think of any simpler way.\n\n3. The paper provides extensive experiments across multiple graphon models (varying in density and rank properties) and estimation methods (NS, SAS, USVT, ICE). Section 6's case studies are particularly compelling.\n\n4. Unlike ECV which requires low-rank assumptions and only has theoretical guarantees for specific models (SBM, RDPG), CV-imputation works for the general graphon model class", "weaknesses": "1. I could not follow the theoretical justification precisely, but I get the intuition behind it which is that the training and test data are independent of each other. Therefore, it doesn't change the distribution of the edge probabilities. It is worthwhile to note that this is valid only when the presence orabsense of an edge is independent of that of other edges.\n\n2.  While the paper tests networks up to approximately 2,600 nodes, many real-world networks contain tens or hundreds of thousands of nodes, yet no discussion addresses computational or memory requirements at such scales. I understand to some extent because the number of pairs for increases quadratically with respect to the number of nodes. But it is nicer to discuss a solution to scale up the method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fbmM4AYqru", "reviewer": "Reviewer_8g5b", "summary": "This paper addresses the problem of model selection in graphon estimation by proposing a new cross-validation method for selecting tuning parameters and estimation approaches. The authors prove that their cross-validation score is asymptotically aligned with the estimation error. Extensive numerical simulations and real-data analyses are provided.", "questions": "1. Could the authors clarify whether line 560 contains a type error? Should it perhaps be something like $P((v_i,v_j)\\in S_k)P(b_{ij}=1, a_{i'j'}=1) + P((v_i,v_j)\\notin S_k)P(a_{ij}=1,a_{i'j'}=1)?$ In addition, could the authors explain how the term $P(a_{ij}=1)P(a_{i'j'}=1)$ in line 561 is obtained? If I understand correctly, the edges $(i,j)$ and $(i',j')$ are correlated when $i=i'$ since they share the same $\\mu_i$.\n\t\n2. Line 597 could be made clearer. More precisely, the statement holds conditional on all $\\mu_i$'s.\n\t\t\n3. If all $\\mu_i$'s are treated as deterministic, then it is unclear why the paper introduces the graphon function.\n\t\t\n4.  It would be helpful if the authors could comment on the computational complexity of calculating $V_K(M)$, for example when $K\\asymp n$.\n\t\t\n5.  Could the authors clarify why Line 610 is correct? It seems that $S_k$ is random.\n\t\t\n\t\t\n6. It would be helpful if the authors could provide more clarification on when  Condition 1 is satisfied. For instance, including a toy example or specifying sufficient conditions would make it clearer. In addition, could the authors comment on whether this condition depends on $w_k$ and $\\theta$?\n\t\n7. It seems that the theorem holds for any fixed $\\theta$. What would happen if $\\theta = 0$ or 1? In addition, in the appendix the authors set $\\theta$ as a random variable, then how would this affect the validity of the theorem?\n\n\n8. It would be helpful if the authors could provide a theoretical comparison between their method and ECV in terms of implementation time.\n\t\n9. It would be interesting to know how the theoretical results behave when $p_{ij}$ tends to zero as $n$ increases.\n\t\n10.  Some minor errors: \n\t\nLine 158: $w_k\\theta$: $w_k\\theta 11^\\top$.\n\nLine 249, 251: five: four.\n\nLine 573: equation equation 8: equation 8.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. I feel the proposed method quite smart. By randomly replacing a portion of the edges, the authors introduce a controllable bias, while obtaining edges that are (conditionally) independent of the training set for validation. The idea is interesting and provides insights for existing research.\n\t\n2.\tThe authors show that minimizing $V_k(M)$ approximately corresponds to minimizing $L(M)$, which provides a theoretical justification for the proposed method.\n\t\n3. The authors have provided sufficient numerical simulations and applied their method to real data examples.\n\t\n4. I enjoyed reading the paper. The writing is clear and well-structured.", "weaknesses": "1. It is confused whether $v_i$ in Line 97 is a typo, since it is unusual for a node label to be a random variable. In addition, if $v_i$ is intended to be $\\mu_i$, then $p_{ij}$ would be random, see my Questions 1 and 2.\n\t\n2. It is unusual that the paper does not impose any assumptions on the graphon function. It is unclear what role the graphon function plays in their framework.\n\n3. The proofs need to be written more rigorously. See my Question 2, 5.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)