Iterative Connecting Probability Estimation for Networks
Authors: Yichen Qin
Linhan Yu
Yang Li
Venue: NeurIPS 2021 Poster (2021)
Keywords: Graphon
vertex similarity
link probability
edge probability

Abstract: Estimating the probabilities of connections between vertices in a random network using an observed adjacency matrix is an important task for network data analysis. Many existing estimation methods are based on certain assumptions on network structure, which limit their applicability in practice. Without making strong assumptions, we develop an iterative connecting probability estimation method based on neighborhood averaging. Starting at a random initial point or an existing estimate, our method iteratively updates the pairwise vertex distances, the sets of similar vertices, and connecting probabilities to improve the precision of the estimate. We propose a two-stage neighborhood selection procedure to achieve the trade-off between smoothness of the estimate and the ability to discover local structure. The tuning parameters can be selected by cross-validation. We establish desirable theoretical properties for our method, and further justify its superior performance by comparing with existing methods in simulation and real data analysis.

Iterative Connecting Probability Estimation for Networks
Yichen Qin
Linhan Yu Renmin University of China yulinhan470foxmen oxmaill com
Yang Li Renmin University of China yang 1i@ruc. edu. en
University of Cincinnati ginyn@ucmail uc. edu
Abstract
Estimating the probabilities of connections between vertices a random network using observed adjacency matrix is important task for network data analy- sis. Many existing estimation methods are based on certain assumptions on ner- work structure, which limit their applicability in practice. Without making strong assumptions, we develop an iterative connecting probability estimation method based on neighborhood averaging. Starting at random initial point ing estimate, our method iteratively updates the pairwise vertex distances, the sets of similar vertices, and connecting probabilities to improve the precision of the estimate. We propose a two-stage neighborhood selection procedure to achieve the trade-off between smoothness of the estimate and the ability to discover local structure. The tuning parameters can be selected by cross-validation. We estab- lish desirable theoretical properties for method, and further justify its superior performance by comparing with existing methods in simulation and real data anal- ysis.
exist-
Introduction
Network analysis has been promising research in data science and widely applied in many fields, including medicine, social sciences. Objects such as genes, proteins, or people are presented vertices in the network, and relationships between objects (e.g.. protein interactions friendships) are presented as connections between pairs of vertices. In this paper, we focus on estimating the connecting probability between each pair of vertices based the observed network.
In the literature, the most fundamental assumption is the Aldous-Hoover theorem (Aldons, 1981). Assume that the network is vertex-exchangee exchangeable, then each vertex is associated with latent vari- able & and the connecting probability between any two vertices depends on a graphon function f(-) of the corresponding latent variables.
To estimate the connecting probabilities, some researchers focus on estimating f()) under strong assumptions. Chan and Airoldi (2(4) propose the sorting-and-smonn and-smoothing (SAS) algorithm. It first sorts the adjacency matrix using the empirical degrees and smoothes the sorted matrix via total variation minimization. It requires strict monotonicity of the degrees, which is difficult to be satisfied practice. Since the purpose of estimating /()) to estimate the connecting probabilities, another direction is to estimate the latter directly, such as stochastic block models approximation (SBA)
AArold ct all 2013: Holland et all LORE: Wang and Wong [+X7). Under the SBM, vertices can be divided into several blocks, and the connecting probability between two vertices depends only on the blocks they belong to. Once the vertices are clustered correctly, the connecting probabilities
can be estimated by moment estimator. In recent years, methods based SBM approximation
and its variation, network histograms, have been widely studied (Choi and Wolfe, 2014; Olhede
"ooresppndeence Author, Center for Applied Statistics and School of Statistics, Renmin University of China
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

and Wolfe, 201)), Gao and MR ( establish the framework of minimax error rate analysis for these methods. Since the adjacency matrix can be viewed as a noisy version of the connecting probability matrix, general matrix denoising methods can be applied too. Chatterjee (2015) provides a universal singular value thresholding method (USVT), and Xu (2018) analyzes error rate. Zhang et all (20TZ) propose an efficient neighborhood smoothing method (NS). They select those with similar connecting patterns as the neighbors for each vertex, then the connecting probabilities can be estimated by neighborhood averaging. However, the estimate is not reused to improve neighborhood selection, which may lead to information loss.
Since the main purpose of estimating the graphon function is to obtain the connecting probabilities, we focus on estimating the connecting probability matrix and develop an iterative connecting prob- ability estimation method (ICE) in this paper. We define a new vertex distance calculated directly on the probability matrix. In contrast to one-step neighborhood smoothing method, our method is iterative. In each iteration, with an estimate, it can update the pairwise vertex distances and the sets of similar vertices. Then, with better selected similar vertices, it can improve the performance on estimation, making it easier to discover complicated structure. The initial input of the iterations can be an estimate obtained by the existing methods as we introduce above. Even if it begins with a random neighborhood averaging estimate, it can converge quickly and perform well in many cases. We also propose a two-stage strategy for neighborhood selection, which uses different sizes of the similar vertex sets during and at the end of the iterations, aiming cope with the trade-off between the smoothness of the estimate and the ability to discover local structure. The tuning parameters can be selected by network coossvvliiation. According to the results simulated and real networks, our method is comparable to ofte-of-thh-art methods in simple cases and outperforms them in the presence of complicated structure.
2 Framework
Suppose G = EV, is the observed undirected network where V [n] denotes the vertex set and E denotes the edge set and E C {i..j) i.j E V,i * j}. The network can be represented by an adjacency matrix A [A,j] "=x" E 10,1] where A., 1 if vertices i and j are connected and 0 otherwise. We only consider undirected networks without self-loops, so A is symmetric with Ag = for E V. Assume that the network is vertex-exchane exchangeabhe,, according to the Aldous- Hoover theorem (Aldous, (1811,, we have the following representation: for each vertex i, there s.i.d. exists a latent random variable & ~ Uniform 1), then for each vertex pair (i,j), we have Ai Bernoulli P:j), where P.₃ = Ey)r,E)) and f(-) is called the graphon function. Let P [Pa]laxn E [0, 1] denote the probability matrix. Let ||-1|2 and ||-1| denote the &g and Frobenius norms respectively.
Given the observed adjacency matrix A, our goal is to estimate the connecting probability matrix P. Since for each pair (i, A.y is the only realization of P.j. it is hard to get sample-based estimation like maximum likelihood estimation. However, if there exists another vertex i' satisfying f(Ex.-) ~ f(E.,) )), then Ar, can be roughly viewed another realization of P.y for the reason that P. = (E., E,) R f(E,, E Pa.. Assume that there is such a group of vertices who share similar connecting patterns with vertex we refer to them in the rest of this paper simply
its "similar vertices". Let S denote the set of similar vertices for vertex i, that is, S = {i' P. = P..... Then we could estimate P.j by simply averaging the entries Az over i' S and j' S7. that is,
Pay = Pr (s")
Σ Σ Avy,
Y'S,, F'ES;
where 3' = |S is the number of similar vertices. Ideally, with known P, it is easy to define the set of similar vertices for vertex i as S (i': : dig. I dg. where di the distance between vertex and vertex i' and d,- is the s -th smallest elements of {d : 1' # i}.
||/ denotes
3 Methodology
3.1 Iterative Connecting Probability Estimation
The neighborhood averaging method in Section is only conceptually feasible. practice, without knowledge of P. it is difficult to obtain the pairwise vertex distances and the sets of similar ver-

---

tices. We propose an iterative connecting probability estimation method (ICE) to solve the problem.
Assume that we have initial estimate P, the estimated vertex distance di can be formulated as dip -IPP, P..ll 1r.11// l//n.. Then we can estimate S with S; = {i' 0 < dar S d,), where - |S: the estimated size of the similar vertex set and d, is the 8-th smallest elements of {dhp : i' + i). Then new estimate can be obtained by neighborhood averaging with
P.j P3s s
Σ
Σ
Avy.
(2)
PES J'E
Using such an estimate, we can update the pair- wise vertex distances and the sets of similar ver- tices again, and obtain new P. We repeat the pro- cess above until P converges. Let D = [dyy|>xx j=x and S = {. } denote the pairwise vertex distances and the sets of similar vertices respec- tively. The iterative procedure is inspired by the interdependence among D, S and P. as is shown in Figure We outline the details of our method in Algorithm MI
S
Figure 1: The relationship among D, S and P.
Algorithm 1 Iterative connecting probability estimation method
Input: observed adjacency matrix A; initial connecting probability estimate ((0); size s; threshold da 0.
neighborhood
Output: connecting probability estimate P.
1: Let 6p = +oo and m = 0.
2: while 6p > 6n do
3: For each vertex pair i E VV, obtain their distance dæ -|[p(mm) p((m) 12/n.
4: For each vertex i E V, obtain its set of similar vertices S; = ft' : 0 < des S dd).
5: For each vertex pair i,j E V. update their connecting probability estimate p(m+1)
1g
s Eves, Eyes,, Apg.
6: Let óp = ||p(m+1)_ - ||ml||///| |l|
7: Let
8: end while
9: return P == (1m).
In Algorithm M. an initial estimate (()) is required. Any P via existing methods can be used as ((0), Alternatively, a random initial value would also work as discussed in Section B.A since our method is not sensitive to the initialization. For each vertex i, we get S, by randomly sampling s vertices from VV {i) without replacement, then we can obtain such a random ((0) by neighborhood averaging with these random selected vertices.
As to the size of the similar vertex set s. Zhang et all (2017) set s = C'n log 1/2 for each vertex i, where C' is recommended set as 1. In Section B.3, we develop a two-stage procedure using different levels of C' in different stages, which improves the performance of our method significantly.
It should be noted that although we discuss our estimate as defined in (2) for convenience, in practice, in case that St and Sy may overlap, we modify it as
P. P,+ - |S n S,)
Apy.
N' ESS
3.2 Iterative Estimation versus One-step Estimation
A main contribution of our work is to estimate P iteratively rather than output a one-step estimate. As for those one-step methods (Zhang et all, 2012), they obtain the set of similar vertices based on the distances calculated from A, then obtain P by neighborhood averaging. However, if we update the set of similar vertices based on P. the previous set of similar vertices may be changed. The
3

---

contradiction may cause inefficiency on making full use of the observed network. Indeed, if P is reliable, we should update the set of similar vertices get a better estimate until the sets remain unchanged.
We compare the performances of iterative estimation and one-step estimation with simulated network which consists of 1000 vertices as an example. As shown in Figure 2[a}, the 1000 x 1000 connecting probability matrix is full rank with complicated structure. We use root mean squared errors (RMSE) to evaluate the performance. We present the results of the 1st and the 10th iterations with two kinds of initial inputs and varying value of tuning parameter C' in Figure Mbb It is clear that the iterations improve the precision of the estimates with both initializations.
The results also illustrate that our method is not sensitive to the initialization. Without iterations, the one-step estimate obtained by the NS method proposed by Zhang et all (2017)) outperforms random initialization significantly. However, after sufficient number of iterations, the performance of method with different initial values becomes comparable. In practice, as the true network structure unknown, we recommend using the random initial input.
catonn
(a) Probability matrix.
(b) The RMSE (multiplied by 100) of dif- ferent initial values with and without itera- tions.
Figure 2: The probability matrix and the RMSE of ICE with and without iterations.
3.3 Two-stage Neighborhood Selection
Setting an appropriate C is an important task. A small C is unable to make full use of the similar vertices while a large C' may lead to over-smoothing. To deal with the dilemma, we propose two- stage strategy. In stage one, we use a small = Cj during iterations avoid ovor-smog and to discover local structure. In stage two, after the estimate converges, a large C' = Cest is used to include more similar vertices to obtain smooth estimate. The reason is that, as the iterations progress, the precision neighborhood selection will be improved, we should enlarge the size of the similar vertex set gradually. However, is impracticable to select the upper bound, the lower bound and the step-size of C' simultancously. So, we simplify the problem by setting two tuning parameters. The first tuning parameter helps us better order the vertices according to their latent positions, whereas the second tuning parameter helps us obtain better estimates using the correct number of vertices.
We compare our two-stage strategy and the strategy using fixed C (Cis = Cest) on the above simulated network. We consider the estimate of Pr., where the index is set as 350 to present the local structure. As is shown in Figure B[a] using small fixed C helps to obtain an estimate with small bias but introduces large variance. In contrast, according to Figure Bib), by using large fixed C, we obtain smooth estimate but fail to capture the local structure. With the well-selected tuning parameters, the two-stage strategy outputs a smooth estimate P. while capturing the local structure well.
We present the RMSE of the estimates with diffferent combinations of (Ca, Cest) on the whole P over 100 repetitions in Figure Sic The horizontal axis stands for the value of Cest used while different curves present the results with different Cy- The curve of "Oracle" displays the RMSE when estimating P with the true similar vertices, which provides a golden standard. For all the curves, as Cest increases, RMSE decreases sharply first, reaches the bottom near Cast. = and increases gradually. which illustrates that using appropriate Cest is important. Comparing the different curves, it easily seen that with fixed Gests a smaller C₁ will lead to smaller RMSE since it helps to discover local structure. Another idea to achieve the trade-off is to use fixed medium

---

71
litee
Cook
RUBEE
C.innd
C Anxt
(a) Two-stage vs Small C.
(h) Two-stage vs Large C.
(c) The RMSE (multiplied by 100) of differ-
ent combinations of (Ci, Cen).
The performances on the estimation of P350. and the whole P by the strategy of using fixed C and our two-stage strategy with different combinations of (Cit. Cest).
Figure 3:
size of the similar vertex set. However, according to the orange curve, we force C₁ = Cest no matter what the value is, this strategy always defeated by our two-stage strategy. The performance of the combination (Oj = 0.2, Cest 1) is the most competitive and even comparable to that of "Oracle."
The two-stage strategy makes our proposed method more data-driven, thus estimating those connect- ing probability matrices with complicated structure more powerfully. To demonstrate this advantage, we display the estimates with different methods on the network above in Figure E. The estimate of satisfied. SAS also performs poorly, as the degree is non-monotone. NS recovers the smooth areas successfully but tends to over-smooth the local structure, Zhang et all (2017) have claimed. Our method combines the advantages of USVT and NS. It discovers the local structure while maintaining the smoothness of the whole matrix.
USVT smooth overall as the low rank assumption
(a) USVT & SAS
(b) NS & ICE
Figure 4: Probability matrix estimated by different methods on simulated networks Column 1: USVT (lower) and SAS (upper). Column 2: NS (lower) and our method (upper).
For our two-stage neighborhood selection strategy, it is important to select appropriate tuning pa- rameters. We apply the grid search method based the network cross-validation proposed by Li al (2020). As Algorithm displays, the edges are split into the training set Eusain and the validation set Eval- With estimate P obtained from the training network G(V, Erssin), the error the validation set can be evaluated with negative log-likelihood loss, which defined AAy log P.j + AAy) log (1 (.-P.)) The black horizontal line in Fig- ure Bic) presents the RMSE with selected parameters, which shows the reliability the cross- validation.
L = E
Theoretical Properties
We study the theoretical properties of our iterative method. All of the results below are based on the following assumptions about the network structure.
Assumption Let 0 zg < 21
< 2K
Ix 15k-1,22 2x) ( for 1 S k K and
1x 2k-1, 2K]. Assume that the graphon function f [0, 1J2 + [0, is bi-Lipschitz each
5

---

Algorithm 2 Tuning parameters selection of ICE via edge cross-validation
Input: observed adjacency matrix A; the training proportion p; the candidate set T of the tuning parameters (Cis, Cest); the number of replications M. Output: a combination of the tuning parameters (Cit, Cesa))
1: for m m==11 ,..... M do
2: Randomly sample a subset of edges from E with probability p to obtain the training set of the edges Exrain. Let Eval E Errain denote the validation set.
3: Apply matrix completion method to the adjacency matrix corresponding to the leftover train-
ing network G(V, Etrain) to obtain Atrain-
4: Apply ICE method on Atrain to estimate P with each (Cit, Cest), and calculate the negative
log-likelihood loss Lm (Cit; Cest) of the estimate on Eval-
5: end for
6: Let L(CiI, Cest. = Em= (Cir, Cest)/
7: return (Cit, Cest) arg Giaa L(Cits Cost).
4 x 1 K. That is, both [f(1 f v)1 S L|-1-121 and ff y1) f(x, y2)l 2
L y2l hold for all 2,,1,,5 12 E ly and v, U1, y2 E h, where L is a global constant.
Assumption The number of K grows with n as ming Mw/l((n log n)2 + co, where [x denotes the length of Ix-
For any & E [o, 1]. let I(E,) denote the interval that includes f., let Ni = -,G A ((;:) denote the neighborhood of ç, in which far y) is Lipschitz in E (A,) for any fixed y. Then according to the Lemma in Zhang et al, (2017), for arbitrary global constant C,C, >
0, define A,, - (C1 + 4) (n log'log log n)2//, then with probability 1 - 2n 2n--2nCh C1/4, have
min 1(v1: Ev (Ni(A 2 C(n log n)2 That is, if large enough, the size of the similar vertex set of each vertex larger than C'n log noggn)// with high probability. For simplicity, we let
C == 1 as Zhang et al. (2017) recommend.
Based on the assumptions, our goal is to obtain P which minimizes |P - P|1 by neighborhood averaging. If we can get the true set of similar vertices S then based on A, the corresponding esti- mate is with P.y defined as (W, which serves as the "Oracle" estimate for neighborhood averaging methods. We have the following results.
Theorem Let Cz C3,Co, C4, Cs Co > be arbitrary global constants and assume n. is large enough so that n + (C4 + 8)2/2n11 S [Cs (C2 331/22 - (Cs +3)1/2] (n=")nn)))) 1/4
and 8L2 1 (C1 + 1/2 (n logn) I (Co 2n²)(n 3 log n)4 let Cx
max 2C2/4, /3 22/ then with probability 1 8n Cn. we have
P Pl < Co(n log 1)4/4.
Theorem @ shows the best eπror rate we can achieve once we succeed to find all the true similar vertices, which seems unrealistic in practice. Luckily, we can reach the same error rate even if the set of similar vertices includes small number of non-similar vertices. We formulate this property in Theorem D
Theorem With arbitrary global constants CT, Cg satisfying Cs > 20, + 4C7 > f the Cs < a b < 1, for any
from Theorem M assume that Pij [a, for all (i,j) E V x V where
solution (S, P) where satisfies
V/n 5/8 (Togs/(loon))0 = e(n).
max Σ 1((i'5)) $ S x S3) <
(3)
b b-a
PES:
J'ES,
if is large enough so that 167, + (Ci + 4) (n--logn) < (Cs - (Cs-4C7- 10-44C-2C3))) -33 2/4
then with probability 1 - 8n C. we have
P -P p1 -2 < Cs(n -3 1/4

---

According to Theorem Q for each pair (i, since [S; x Sj = s², the maximum error rate allowed for neighborhood selection is e(m)/s² x e(n)/n log (C (og logn)////( greater then Ca(n log n)t/4, That is, we can obtain an estimate with low error rate even with relatively high error rate on neighborhood selection. The smaller b aa is, the larger the error rate allowed.
a), which is
If we use the estimates with existing methods as the initial values, we can achieve small error rate on neighborhood selection with a high probability, thus improving the estimation performance. For
P.j n- I Cg En) with probabil- ity - Cio, where the error rate E(n) satisfies -im B(n)/ log n) + oc, we have the following theorem for the estimate in the next iteration.
any estimate (00) which satisfies that m Σド-1 ((10)
Theorem Define the lower bound of the distance between each vertex i and any vertex 1" $ St as
((n) =
PPjj Parsls min EEV
assume that (n) 2 8L2 [1+ (C1 + 1) (n logn) 2(), then with the global con-
stunts Cz, C3, Ca, Co from Theorem 01 when use
((U) as the initial value to obtain new estimate P Pnew. with probability 1 8n C. n- C10, we have
P new
P Pl
S Co(nn Colnn loggg) n)
The results above show that if our proposed method start from reasonably good estimate obtained by an existing method, then will improve upon the initial estimate iteratively, making the final estimate comparable to that with all the true similar vertices. The next question is whether we can stop the iterations when the current estimate is P. Assume that the current estimate p(m) is smooth enough to satisfy Assumptions WI and D. we have the following theorem.
Theorem With arbitrary global constant Cn and C12 satisfying C12 > 4C's + 2011 > 0 for [ 1 (C1 + 4)2/2] (n logn) < (C12 40, 2Cn) (n-3 logn) 1/1 if ((mm) satisfies [[p(m)) P 1l1p//² I Cni(n loog 1/4
Os from Theorem I and let n be large enough that 32L
logn)"/t
then with probability 1 - 8n C. we have
p (m) pim+D S 112()=1logn)11
For our learning task, the adjacency matrix A is observed while the pairwise vertex distances and the sets of similar vertices can be viewed as unobserved data, and our goal to estimate with incomplete data, which is a typical task for an EM type algorithm and motivates dure. However, although updating P with S is the traditional M step, updating S using the current estimate P is not equivalent the step. Therefore, we cannot directly use the existing theory.
iterative proce-
Experiments
5.1 Simulated Networks
To evaluate the effectiveness of our proposed method, we compare its performance with several popular estimation methods using simulated networks with different features, including low-rank, degree monotonicity and local structure. Each network contains 1000 vertices. The connecting probability matrices displayed in Figure EL where the rows and the columns are ordered by Graphon is low rank and has vertex degree monotonicity. Graphon 2 is roughly monotone with local structure. Graphon 3 is a periodic function. Other graphons are all full-rank with extreme values local area like the diagonal and the corner.
We compare the following methods: universal singular value thresholding algorithm (USVT) (Chate terjee, 2015), stochastic blockmodel approximation algorithm (SBA) (Airoldi et all 203),, sorting and smoothing method (SAS) (Chan and Auroldi ( neighborhood smoothing method (NS)
7

---

Zhang et all 2017). our proposed method (ICE). For fair comparison, we use random neighbor- hood averaging estimate as the initial value. We also present the result of neighborhood averaging with true similar vertices (Oracle) as a golden standard.
Figure Graphon functions (1-8, from left to right) to generate simulated networks.
We show the results on average of 100 repetitions in Table II For each method, we report the mean of RMSE with standard deviation in the bracket. For probability matrices with low rank (Graphons 1 and 3). USVT does good job. However, if the graphon is full rank, the low-rank approximation by USVT becomes insufficient. Although SAS method performs well on Graphons 1 and since the expected degrees is monotone, it does not work on other graphon functions. NS method performs well in many cases, which coincides with the numerical results of afZaang et al. (2017). Our proposed method is comparable to NS on simple networks generated by Graphons and 3. Notably, on networks with complicated structure (Graphon 4-8), our method shows significant advantage for its ability to discover local structure.
We also display the tuning parameters (Cit, Cest) selected via cross cross- validaaaliotion and the best Cest we use true similar vertices (Oracle). The Cest we select is comparable to that with true similar vertices while the selected Ci always smaller, which again shows the advantage of our method on the trade-off between the smoothness of the estimate and the ability to discover local structure.
Table 1: The RMSE (multiplied by 100) of different methods and Cit and Cest. selected for ICE by validatoo simulated networks.
RMSE (multiplied by 100)
Cne and Caus selected
Graphen
USVT
SAS
NS
ICE
Oracle
ICE Ci.
ICE C..t
Oracle
162(0005)
4.79(0.06)
L.72(0.04)
2.55(0.04)
2.23(0.18)
1.55
1,05(0.40)
1.85(0443)
2.33
3.74(0.03)
38 (8.6600.05)
4.92(0.06)
3.78(0.03)
2.87(0.05)
2.40
1.13(0443
2.37(0.15)
2.33
2.67(0.03)
63.1990.46)
34.05(0.20
3.33(0.03)
1.2)(0.13)
2.49
0.47(0.47)
143(0.33)
1.67
7.53(0.05)
43.55(0.03)
14.00(0.07)
7.25(0.05)
6.09(0.08)
0.23(0.07)
1.07(0.14)
6.41(0.03)
8.35(0.02)
8.24(0.02)
6.85(0.05)
4.19(0.09)
3.55
0,58(0.16)
2.03(0.32)
1.78
7.22(0.03)
(2,80())
12.74(0.01)
6.54(0.06)
5.20(0.10)
0,28(0.07)
0.95(0.12)
8.09(0.09)
9,53(0.03)
9.1((0.22)
8.21(0.04)
6.84(0..1)
5.93
0.39(0.13)
2.27(0.37)
1.00
4.50(0.02)
10.61(0.03)
10.51(0.02)
3.88(0.05)
3.30(0.04)
2.71
0.49(0.16)
1.67(0.00)
1.00
5.2 Real Networks
We analyze a human brain projectome dataset from an experiment of Beijing Normal University in China (aanetaa all 2.04PP The dataset available on https:/NeuurDDtta.o. platform that enables large-scale neurodata storing, analyzing. and modeling. A "projectome" is large-scale mapping between regions the brain. This data include 48 anonymous healthy students as controls and each of them has 3 scans in different statuses. A valuable task is to the study the relationship between the regions, which may reveal the way they work together.
We have evaluated the performance of our methods on several subjects. For the sake of brevity, we only display the result estimating the projectome of the subject with ID 0027055 in the first S The network consists of 349 vertices and 3772 edges. We present the adjacency matrix in Figure blay The and columns ordered according the function of the regions.
As is shown in Figure El the estimates these methods are quite different. USVT tends to estimate the probability matrix SBM model with many blocks. It fails to recover the local structure in the top left. SBA and SAS both perform poorly, because the degree disruption does not coincide with the connecting behaviors. The result of NS is more similar that of ICE. They both obtain
hhtp://dx.doii.or//00..55 15387/fcppp indi.corr.bul
'ntp::/manneurdaata.. ---.aa.s-wwwweeeeeeeeeeeeeeeeeee website-us sustte-usssssslll httpsieeesseetttaaaaoaoooooo.oo www.a//nwww.co////u.... 00w.::mmmm00000000//////00000- 0tt.A///hhnnnn000000ggo000000000
0027055_scs-1_20 DS00350.00000 gpickle

---

smooth estimate with local structure. The difference is that, since the whole network is sparse, NS is easier to underestimate the connecting probability of moderately connected pairs. This shortcoming derives from its assumption about the smoothness, which may lead to over-smoothiig.
(a) Adjacency & USVT (b) SBA & SAS
(c) NS & ICE
Figure 6: Adjacency matrix and probability matrix estimated by different methods. Column 1: Adja- cency matrix (lower) and USVT (upper). Column 2: SBA (lower) and SAS (upper). Column 3: NS (lower) and ICE (upper).
As the true probability matrix is unknown, it is hard to examine and compare the results of different methods on real networks. Zhang et all (2017) evaluate their method by applying it to the task of link prediction. Assume that A is the true adjacency matrix while Amis is the observed version.
Assume that each edge the true network will removed in the observed network with probability
p. which can be formulated Amiss M A, where Mij i.s.d. Bernoulli(1 pp). Based on Amiss: the estimate P gives the scores proportional to the connecting probabilities (G all 2016). With threshold t 0, Zhang et al. (2017) define the false positive rate and the true positive rate by
FP(() = Σ (Pg > t, A,j = 0, Maj = =0) / Σ 1.
II (A, = 0, Mi = -),
1.
TP(t) = Σ 1 PPg > t, A, = 1, Mij = 0) / (A. 1, Mij = 0).
By varying 4, we can obtain the ROC curve and compare the precision of different methods with AUC. The missing rate p set as 0.1.
Here we develop a new approach for evaluation of connecting probability estimation methods in practice. Although P is unknown, result Post as the baseline. Then we generate the adjacency matrix Agen with Phoet and apply different methods to estimate it. We refer to the method used to obtain P host the "host" method. The "host" is always the best due to the home-court advantage. We focus on those methods whose performances competitive and even comparable to the "host", which demonstrates the capability of generalization.
estimate it by of the existing methods and apply the
To evaluate the precision on estimation, we display the results of the link prediction task in Fig- ure Maa). obvious that SBA and SAS are outperformed by others significantly. Our method is slightly better than NS and USVT due to its ability to recover the local structure with higher precision.
To evaluate the the capability of generalization, we use the approach we propose. For each "host", we generate the adjacency matrix for 100 repetitions and present the RMSE on average in Fig- ure ((b]). When P Phstt is based on USVT, it outperforms others significantly because P Phost is low rank. However, if the "host" our proposed method, USVT performs poorly as is hard to recover local structure. Under this setting, NS is also defeated by our method due to over-smoothing, When the "host" are SBA and SAS, NS outperforms others slightly. The reason that both SBA and SAS output smooth estimated probability matrices and satisfy the assumption about smoothness of NS. No matter what the "host" is, our method is always competitive, which manifests its ability of generalization.
6 Conclusions
We propose an iterative connecting probability matrix estimation method which updates the set of similar vertices and the estimate progressively. is intuitive, easy to implement and computationally

---

mwthod
UEVT
140
100
2 000
Vethul
025
12E
3/5
base
(a) The ROC curves on the (b) The RMSE (multiplied by 100) with task of link prediction.
different "host".
Figure 7: The performances of different methods on real network.
feasible for its fast convergence. Even starting with an estimate by random neighborhood averaging performs well. The main strength of method is the ability to discover local and complicated structure for networks. In our algorithm, deciding the size of the similar vertex set is crucial. We propose two-stage strategy using different sizes to balance its ability discover local structure and output smooth estimate. In practice, the appropriate size may vary from vertex to vertex. possible variation of our method is to specific size of the similar vertex for each vertex. Although may introduce more turning parameters, we believe that this issue is worth of further investigation.
Acknowledgments and Disclosure of Funding
We thank the program chair and reviewers for their insightful comments that greatly improve the article. Funding in direct support of this work: None. Additional revenues related to this work: None.
References
Edo M Airoldi, Thiago Costa, and Stanley H Chan. Stochastic blockmodel approximation of graphon: Theory and consistent estimation. In Advances in Neural Information Processing Systems, pages 692-700, 2013.
David Aldous. Representations for partially exchangeable arrays of random variables. Journal of Multivariate Analysis, 1144)5811-598, 1981.
Stanley Chan and Edoardo Airoldi. A consistent histogram estimator for exchangeable graph models. In International Conference on Machine Learning, pages 208-216, 2014.
Souray Chatterjee. Matrix estimation by universal singular value thresholding. The Annals of Statis- tics, 43(1):177-214, 2015.
David Choi and Patrick Wolfe. Co-clustering separately exchangeable network data. The Annals of Statistics, 42(1):29-63, 2014.
Chao Gao and Zongming Ma. Minimax Rates in Network Analysis: Graphon Estimation, Commu- nity Detection and Hypothesis Testing. Statistical Science, 36(1):16 33, 2021.
Chao Gao, Yu Lu, Zongming Ma, and Harrison H Zhou. Optimal estimation and completion of matrices with biclustering structures. The Journal of Machine Learning Research, 17(1):5602-
5630, 2016.
Paul Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Networks, 5(2): 100--0997777 137, 1983.
Tianxi Li, Elizaveta Levina, and Ji Zhu. Network cross-validation by edge sampling. Biometrika, 107(2):557-276, 04 2020. ISSN 0006-3444.
Sofia C Olhede and Patrick Wolfe. Network histograms and universality of blockmodel approxi- mation. Proceedings of the National Academy of Sciences, 111(41):44722-1477)) 2014.
10

---

Yuchung J Wang and George Y Wong. Stochastic blockmodels for directed graphs. Journal of the American Statistical Association, 82(397):8 1987.
Jiaming Xu. Rates of convergence of spectral methods for graphon estimation. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2018.
PMLR, 10-15 Jul
Chaogan Yan, Donggiang Liu, Yong He, Qihong Zou, Chaozhe Zhu, Xinian Zuo, Xiangyu Long, and Yufeng Zang. Spontaneous brain activity in the default mode network is sensitive to different resting-state state conditions with limited cognitive load. PloS One, 4(5):e5743, 2009.
Yuan Zhang, Elizaveta Levina, and Ji Zhu. Estimating network edge probabilities by neighbourhood smoothing. Biometrika, 104(4):771-783, 09 2017. ISSN 0006-3444.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Section M
(b) Did you describe the limitations of your work? [Yes] See Section i
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We will discuss them in the appendix due to the page limit.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
gl And we will further discuss the reasonableness of the assumptions in appendix.
(b) Did you include complete proofs of all theoretical results? [Yes] We provide the proofs in appendix.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] We include the code and data in the supplemental material and will publish them online later.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section B.3 and 5.11.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] See Section 5. We report both the mean and the standard deviation of our metric.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [No] Since method is computation- ally feasible for networks with moderate size, we omit this part for brevity.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 5.21
(b) Did you mention the license of the assets? [Yes] See Section [w
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] We include the code and data in the supplemental material and will publish them online later.
(d) Did you discuss whether and how consent was obtained from people whose data you're re using/curating? [No] The data we use is public and allowed to be used once cited correctly.
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [Yes]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "xjUr5vHZVlu", "reviewer": "Reviewer_9KpH", "summary": "The authors propose an iterative approach to estimate the probability of forming an edge between any two vertices in a graph, which they denote as the *connecting probability*. With only a single realization of the graph, it is a difficult task to estimate the connecting probabilities. The proposed iterative connecting probability estimation (ICE) method uses neighborhood averaging, similar to Zhang et al. (2017), but with iterative refinement of the neighborhood. They provide a theoretical analysis demonstrating that the error rate of their proposed estimation procedure is asymptotically as good as that of an \"oracle\" estimate that has access to the true connecting probabilities to choose the neighborhood. They also provide extensive simulations and a real data experiment demonstrating good empirical performance compared to prior work.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "**Originality: Moderate**  \nThe basic idea is straightforward enough that I would consider it to be low in originality: iterate a neighborhood averaging algorithm multiple times until convergence. The two-stage neighborhood selection approach using different $C$ values is innovative and appears to be effective.\n\nI did not carefully check the proofs in the supplement, so I cannot assess if there is any originality to the analysis techniques.\n\n**Quality: High**  \nThe authors present a principled approach extending the neighborhood smoothing approach of Zhang et al. (2017) and present simulation results along the way justifying their decisions. These are supplemented with more extensive simulation experiments showing very impressive performance on lots of different graphon functions and a real data experiment.\n\nThey also present theoretical results that I find to be of value. It is good to see that the proposed iteration has the same asymptotic error rates as an \"oracle\" estimator that knows the true neighbors. Again, I did not check the proofs for correctness.\n\n**Clarity: High**  \nI found the paper to be extremely well written and very easy to understand. Thank you! I have just a few minor points for improvement below.\n\nThe authors use the term \"neighbors\" of a vertex $i$ to denote a group of vertices with similar connecting probabilities compared to $i$. This may be confusing to some readers because the term \"neighbors\" is usually used to denote vertices connected to $i$. Perhaps this could be clarified with a 1-sentence explanation in the intro.\n\nIn Figure 4, showing 2 probability matrices in a single figure is confusing. Since the matrices are symmetric, only a triangular portion is necessary, which allows the matrices to be shown in this way, but there is plenty of room to show all 4 matrices as separate subfigures.\n\nTable 1: Use bold to denote the method that performs the best in terms of RMSE (excluding oracle) to simplify comparison between methods.\n\nWhy did you choose the single test subject for the real data experiment?\n\n**Significance: Moderate**  \nThis paper certainly advances statistical network estimation, but it is an incremental improvement on Zhang et al. (2017), which limits significance somewhat in my view. The approach could have some broader impact given the wide applicability of network analysis in many disciplines.\n\n**Comments after author response and discussion:**  \nI find the proposed method to be simple and provably effective, which is a very good combination. All the paper needs is a few minor revisions, such as changing the use of the word \"neighbor\", as discussed. Adding some more experimental results on the projectome data, even in the supplementary, would also strengthen the paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors provide a very brief discussion of limitations in the conclusion. Some discussion of societal impact is provided in the supplement.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "YvYAUI3CgPz", "reviewer": "Reviewer_WMZz", "summary": "The paper discusses a new strategy for graphon estimation that is based on an iteratively updating the graphon by considering certain neighborhoods of the nodes.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The paper discusses a novel idea for graphon estimation: instead of using a \"one-shot\" approach, e.g., based on a singular value decomposition, the idea is to use an procedure that --- starting from an initial guess --- updates the graphon estimate iteratively.\nThe problem of graphon estimation is indeed very relevant, and the presented theoretical guarantees and numerical experiments corroborate the results of the authors.\n\nI have a number of concern regarding the paper, in terms of the presentation and the results.\nFirst I found the initial discussion and the abstract to be somewhat misleading. The authors state that there are no strong assumptions that need to be made, but they assume that the graph is generated by a graphon model. This implies conditionally independent edges / vertex exchangability, and seems to be a pretty strong assumption to me. \nI think the presentation should have been clearer in stating that the problem is that of estimating a graphon, rather than estimating the connection probability -- which is a more general (and more vague) idea.\n\nGiven that the authors concentrate on graphon models, it would have however also been useful to discuss the aspect of sparsity -- it is well known that graphons are essesntially models for dense graphs; while one can adjust the density of them to a certain extend via a scaling parameter, but obtaining truly sparse graphs would require to turn to something like a graphex, or edge-exchangable models. This is a limitation that should have been discussed in more detail in my opinion.\nIndeed, we (basically) see a repercussion of this issue of graphons in Assumption 2, where the neighborhood size of a node needs to grow as (n log n)^(1/2).\n\nI would have also liked to see more theoretical discussion (and perhaps some numerical experiments) on the choice of the C parameter; indeed as the authors point out in the conclusion, we may actually have very different C for different vertices.\nSimilarly, how the initial estimate of the connection probability matrix P should be chosen, and what is effect would be on the algorithm seems a question that is somewhat underdeveloped in the paper.\n\nWhile some of these flaws will be very difficult to address in a revised version,  I think the paper has an interesting algorithmic idea and so I see it slight above the threshold.\n\n=========\nI thank the authors for their answers. I have updated my score, following the response and the comments from the other reviewers.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are several limitations, in particular w.r.t. the considered network model (a graphon) -- see above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "QjOrNI8Avwh", "reviewer": "Reviewer_JKKC", "summary": "The paper studies an interactive algorithm for connecting probability estimation. The proposed algorithm updates the pairwise vertex distance, neighborhood set, and the connecting probabilities iteratively to improve the estimation until the result converges. The authors have shown both theoretical and empirical results. Some practical techniques to improve the performance of the algorithm are also discussed in the paper.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "I think this paper has some interesting results. The proposed algorithm is simple, efficient, and well-motivated. The experiments are well designed to demonstrate the advantages of the algorithm when compared with other approaches. The theoretical results proved reasonable guarantees for the performance of the algorithm.\n\nI have a question about the algorithm. The proposed algorithm has an EM flavor. A natural question for such an algorithm is whether or not the algorithm is guaranteed to terminate and how many steps it takes to converge. Although some relevant analysis is given, I would appreciate a discussion for the general case, whether the result is positive or not.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hrs"}, "extra_text": {}}, {"review_id": "KYOBQOOIjpB", "reviewer": "Reviewer_7aba", "summary": "This paper deals with the task of estimating the connection probabilities in a random graph, assuming that it is drawn from a graphon model; i.e. $P_{ij} = f(\\xi_i, \\xi_j)$, where $f$ is a smooth function and the $\\xi_i$ are uniform random variables. The authors do so by exploiting the same ansatz as in Zhang et al: for $i \\in [n]$, find several $i'$ with connection probabilities \"close\" to those of $i$, and average the $P_{i'j}$ to find an estimate for $P_{ij}$.\n\nThe main difference with the existing litterature is the choice of the $i'$: the authors choose an iterative procedure, building ever improving estimators of the $P_{ij}$ and using the current estimate to find the $i'$ and build the next estimator. The paper also presents a two-step procedure to choose the right number of \"close\" vertices.\n\nThe authors then show several theoretical properties of their algorithm, in a model including (but not limited to) the classical stochastic block model. Their bounds depend on the number of vertices correctly classified as \"close\" to each vertex in the graph.\n\nFinally, they present experiments on both synthetic and real-world data; these seem to indicate that the ICE algorithm outperforms its counterparts when the graphon function $f$ becomes more complex. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "This paper presents a novel and effective method for probability estimation in graphon models. The authors show some convergence bounds on a restricted model (functions that are Lipschitz on rectangles), but the numerical experiments seem to indicate that the algorithm converges for a more general class of functions.\n\nOverall, the paper is well-written and easy to read, with a few caveats:\n* the use of \"neighbors\" to denote similar vertices clashes with the overwhelming acception of this term in graph theory, which causes some confusion,\n* the statements of Theorems 1-4 are very convoluted, involving up to 12 different constants; I'd rather suggest very slightly weaker but more readable versions (e.g. \"fusing\" some constants) in the main text, and if needed putting the exact bounds in the appendix.\n\nThose drawbacks being fairly straightforward to fix, they do not impact the overall quality of the paper too much.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a simple iterative and provably effective method for graphon estimation, which improves on previous "single shot" estimation techniques. The reviewers were in consensus that the idea is very natural and well-studied, and a significant contribution to the graphon literature.
Decision: Accept (Poster)