Pith. sign in

REVIEW 4 major objections 5 minor 12 references

Predictive Subsampling for Scalable Inference in Networks

T0 review · 4 major / 5 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Fit on m nodes, predict all n: network estimation stays consistent

desk verdict Estimation idea is solid and worth a look; the testing-consistency claim overreaches — the bootstrap procedures aren't what the theorems analyze. read the letter →

arxiv 2602.16041 v2 pith:AXTXZQPU submitted 2026-02-17 stat.ME

Arpan Kumar , Minh Tang , Srijan Sengupta This is my paper · ORCID
classification stat.ME
keywords networkdatasubsamplinggeneralizedrandomdotproductgraphestimationtwo-samplehypothesistestingadjacencyspectralembeddingout-of-samplepredictiontwo-to-infinitynorm
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes estimating a large network by drawing a random subsample of $m$ vertices, embedding only that small subgraph, and then predicting the latent position of every other vertex from its observed connections to the subsample. It claims that this Predictive Subsampling (PredSub) estimator is consistent for the full probability matrix, with relative Frobenius error of order $\sqrt{n/m}$ and row-wise error of order $\sqrt{n \log n / m}$, while reducing the computational cost of adjacency spectral embedding from roughly $O(n^3)$ to $O(n m d)$. Built on the same estimator, two bootstrap procedures — PredSubTest and PureSubTest — are shown to provide asymptotically valid and consistent two-sample tests of whether two networks share the same edge probabilities. The practical payoff, demonstrated in simulations and on two large real networks, is a 3-to-180-fold speedup with accuracy that matches the full-sample method.

What carries the argument

The out-of-sample predictor $\hat{x}_i^T = A_{i,S} \hat{X}_S (\hat{X}_S^T \hat{X}_S)^{-1} I_{p,q}$ for each vertex outside the subsample: it converts a vertex's $m$ observed edges to the subsample into an estimate of its $d$-dimensional latent position in $O(m d)$ work. Together with a single adjacency spectral embedding of the $m \times m$ subsample (cost $O(m^3)$ or $O(m^2 d)$ with iterative methods), it yields the full $n \times n$ probability matrix estimate at total cost $O(n m d)$. The mechanism works because the generalized random dot product graph likelihood implies $P_{i,S} = x_i^T I_{p,q} X_S^T$, so the latent position is recoverable by solving a small linear system against the subsample's estimated positions.

What would settle it

Simulate a network with $\rho_n = n^{-1}$ and $m = \log n$, so that $m \rho_n$ tends to 0, and measure the Frobenius and two-to-infinity errors of the PredSub estimate of $P$; if the errors stop shrinking as $n$ grows, the stated rates fail. Alternatively, generate the paper's mixed-membership model but raise a few hub rows to ten times the nominal sparsity level, and check whether the two-to-infinity error for those rows remains bounded.

Watch

Extended reading notes

Core claim

The central claim is that the entire graph's latent positions can be estimated consistently from a random subsample of $m$ vertices by embedding the subsample and then regressing each remaining vertex's observed adjacency vector onto the subsample's estimated latent positions. Theorems 2 and 3 give rates $\sqrt{\log m / m}$ and $1/\sqrt{m}$ in two-to-infinity and Frobenius norms for the latent-position estimates, and Corollary 4 converts these into probability-matrix error rates of order $\|X\|_F \sqrt{n/m}$ (Frobenius) and $\|X\|_{2 \to \infty} \sqrt{n \log n / m}$ (two-to-infinity). The same construction drives two bootstrap tests, PredSubTest and PureSubTest, whose consistency is stated in Theorems 6, 7, and 9.

Load-bearing premise

The rates require every edge probability to lie between $c_1 \rho_n$ and $c_2 \rho_n$ and the subsample's expected degree $m \rho_n$ to grow at least like $\log m$; real networks with hubs or very sparse subsamples can escape these conditions.

Editorial extensions

If this is right

  • A uniform random subsample of m vertices suffices to estimate the full n-vertex probability matrix consistently; error shrinks as m grows, with rates sqrt(n/m) in Frobenius norm and sqrt(n log n / m) in two-to-infinity norm.
  • PredSub reduces estimation cost from O(n^3) to O(n m d), so for fixed dimension d and moderate m the cost scales nearly linearly in n, making millions-of-vertices networks feasible.
  • The PredSubTest detects differences in probability matrices even when only one row of P differs, provided the row difference exceeds order sqrt(n rho_n log n / m).
  • PureSubTest, which bootstraps only one subgraph, needs about O(n log n / m) differing rows to be consistent but is even faster, with cost O(m^2 d B).
  • Bootstrap resampling under the null only requires generating n×m adjacency blocks, so computing p-values costs O(n m d B) instead of repeated full-spectrum embeddings.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The predictor formula is essentially a projection of the observed cross-edges onto the subsample's estimated latent space; any consistent embedding of the subsample (for instance a Laplacian embedding) could plausibly replace the spectral embedding without changing the overall scheme.
  • The paper's own simulations use mixed-membership models whose Dirichlet rows create heterogeneous degrees, a setting outside the stated uniform-sparsity assumption; the method may therefore be consistent under weaker row-wise sparsity conditions than the ones assumed.
  • Because out-of-sample vertices are predicted independently, the prediction step parallelizes trivially; on distributed hardware the wall-clock time could drop to roughly O(m^3 + n d) per worker, making the approach suitable for very large graphs with modest per-machine memory.
  • The testing framework's threshold structure suggests that in applications with a known sparsity level, m could be chosen adaptively to hit a target detectable alternative size — a selection rule the paper does not derive.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The manuscript introduces Predictive Subsampling (PredSub), a scalable estimation and two-sample testing framework for generalized random dot product graphs. The estimator chooses a uniformly random subset S of m vertices, computes an adjacency spectral embedding of the induced subgraph A_S, and extends the latent positions to the remaining vertices through the out-of-sample formula x_i^T = A_{i,S} \hat X_S (\hat X_S^T \hat X_S)^{-1} I_{p,q}, yielding O(nmd) complexity. The paper states finite-sample error bounds for the estimated latent positions in 2-to-infinity and row-normalized Frobenius norms, and Frobenius/2-to-infinity bounds for the implied probability matrix estimator. It then proposes two parametric bootstrap two-sample tests (PredSubTest and PureSubTest) and claims consistency of these tests. Theoretical results in Section 4.3, however, concern oracle rejection regions of the form T > K R sqrt(n log n / m) with unspecified constants, rather than the bootstrap procedures implemented in Algorithms 2 and 3. Simulations and two real-data applications are reported.

Significance. The estimation component is potentially valuable: if the entrywise and normalized Frobenius bounds are correct, PredSub provides a principled way to reduce the cost of spectral estimation in large GRDPGs while retaining row-wise accuracy, and the simulation study demonstrates substantial speedups with accuracy close to full ASE. The out-of-sample predictive step is simple, parallelizable, and clearly motivated by the GRDPG structure. The testing contribution, however, is not supported by the supplied theory: the consistency theorems are for oracle thresholds that the implemented bootstrap algorithms do not use, and Section 7 explicitly states that theoretical guarantees for the bootstrap procedures are open. As submitted, the abstract's claim of 'testing consistency of the proposed methods' overstates what is proven. The empirical testing results may be useful, but the formal testing guarantees do not apply to the proposed procedures.

major comments (4)
  1. [§4.3 (Theorems 6, 7, 9); Section 7] The consistency results are stated for oracle rejection regions of the form {T_F > 2K_4 R_F sqrt(n/m)} and {T_{2\to\infty} > 2K_4 R_{2\to\infty} sqrt(n log n / m)}, with an unspecified universal constant K_4 and a data-dependent norm R. Algorithms 2 and 3 do not use these thresholds; they reject by comparing the observed statistic with a parametric bootstrap distribution generated under the pooled estimate. No theorem in the paper shows that this bootstrap quantile is close to the oracle threshold, and Section 7 explicitly says 'bootstrap-based testing procedures, for which theoretical guarantees remain an open problem.' Consequently, the abstract's claim of 'testing consistency of the proposed methods' is not a property of the implemented procedures. This is not a presentation issue: the formal testing contribution covers exactly the algorithms compared in Sections 5–6 and used on the r
  2. [§4.2, Corollary 4 and surrounding text] The statement that 'Theorems 2 and 3 imply that the estimate \hat P_PS given by Algorithm 1 is also consistent' is ambiguous. Theorem 3 is a row-normalized Frobenius bound, while Corollary 4 gives the absolute Frobenius bound O_p(\|X\|_F sqrt(n/m)). Under the uniform-sparsity Assumption 3 the natural scaling is \|X\|_F = \Theta(sqrt(n \rho_n)), so the bound is O_p(n sqrt(\rho_n/m)); this is not o_p(1) when m is polylogarithmic in n and \rho_n is constant, although it is o_p(1) relative to \|P\|_F \asymp n \rho_n. If the intended result is relative or normalized Frobenius consistency, it must be stated as such; otherwise the abstract and the paragraph overstate what Corollary 4 delivers.
  3. [§4.2, Lemma 5 and proof of Theorem 2] The theoretical analysis samples S by independent Bernoulli inclusion with probability m/n, while Algorithm 1 uses a uniformly random subset of size m. Lemma 5 and the subsequent proof rely on independence of the sampling indicators, for example through the matrix Bernstein argument with the random matrices Y_i. The paper does not provide a coupling or an argument that the same bounds hold for sampling without replacement. This makes the proofs not formally aligned with the implemented algorithm, even though a standard coupling may repair the mismatch.
  4. [§4.3, Theorems 6 and 7] Apart from the bootstrap gap, the oracle rejection regions are not implementable as stated. The constant K_4 is asserted to exist but its value is never specified, and the regions depend on the data through R_F or R_{2\to\infty} without a consistent estimator of K_4 being proposed. Thus the theorems establish an existence-type asymptotic statement, not a usable level-\alpha test. Furthermore, the type I error claim in Theorem 6, 'P(T_F \in R_n) = o_p(1)', is not well-formed because P(T_F \in R_n) is a nonrandom sequence and should be o(1); this notational issue also obscures what is being claimed about the rejection region.
minor comments (5)
  1. [Algorithm 3] The input list does not include the number of bootstrap resamples B, although Step 5 and Step 8 use B. Add B to the Input line.
  2. [Theorem 7 statement] The rejection region is typeset with an unmatched parenthesis: '{T_{2\to\infty} \geq 2K_4 R_{2\to\infty} sqrt((n log n)/m' is missing a closing delimiter. Please fix the display.
  3. [Algorithm 2 complexity discussion] The statement that each bootstrap sample only requires an n x m matrix is correct only if the same subsample S is reused in every bootstrap step. The algorithm should state explicitly that S is selected once and fixed across all resamples; otherwise an n x n matrix would be needed.
  4. [Definition 5] The notation 'lim_{n\to\infty} P(R_n)' is imprecise because R_n is a rejection region, not an event. It should be 'limsup_{n\to\infty} P(T_n \in R_n)'.
  5. [Assumptions 3 and 5] The uniform sparsity assumption P_ij = \Theta(\rho_n) and the requirement m\rho_n = \Omega(\log m) exclude heterogeneous degree distributions and very sparse regimes that are common in practice. This limitation should be acknowledged explicitly, since the proof of Lemma 4 and the out-of-sample predictor use the uniform entry bound in an essential way.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity; estimation rates are derived from assumptions and concentration bounds. Minor self-citations are not load-bearing. The main caveat is that testing proofs analyze oracle thresholds, while bootstrap theory is explicitly left open.

full rationale

The PredSub estimator is not fit to the target quantities: given a uniformly random subsample S, it computes ASE on A_S and then uses the GRDPG identity x_i^T = P_i,S X_S (X_S^T X_S)^{-1} I_{p,q} with A_i,S and \hat X_S plugged in (Section 3.1, Algorithm 1). Theorem 2 and Corollary 4 then follow from standard Davis-Kahan / two-to-infinity perturbation results, matrix Bernstein inequalities, and Assumptions 1-5; no fitted constant is renamed as a prediction. The rates are genuine consequences of the subsample size, sparsity, and incoherence assumptions. Theorems 6/7/9, however, prove consistency for rejection regions of the form {T > c R sqrt(n log n/m)} with unspecified constants; these are oracle tests, not the bootstrap p-values computed in Algorithms 2/3. Section 7 states: 'We also considered bootstrap-based testing procedures, for which theoretical guarantees remain an open problem.' This is an internal gap between the abstract's testing-consistency claim and the analyzed tests, but it is not a circular reduction. Self-citations (Tang and Cape 2025, Chakraborty et al. 2025, Bhadra et al. 2025a,b) are used for related work, comparisons, or a lemma that is proved in the paper (Lemma 6), so they are not load-bearing. Hence no circular step is established.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

No new entities are postulated; the method reuses the existing GRDPG latent-position machinery. The axioms are standard or explicitly stated assumptions, with one ad hoc mismatch between Bernoulli sampling in proofs and uniform sampling in the algorithm.

free parameters (4)
  • subsample size m (equivalently exponent a) = chosen in experiments as ceil((log n)^(1+a)) with a in {2.625,...,3.375}
    User-chosen tuning parameter; theory only requires m=Omega((log n)^(1+a)) and m rho_n=Omega(log m).
  • rank d = fixed in theory; chosen in simulations and real data as 5, 10, 20
    d is assumed known in Assumption 2 and set by the user in the algorithms.
  • signature (p,q) = estimated from signs of eigenvalues in Algorithm 1 step 3
    p is set as the number of positive eigenvalues among the d largest (in modulus).
  • bootstrap resamples B = B=100 in simulations
    Monte Carlo parameter for the bootstrap p-value; not theoretically analyzed.
assumptions (6)
  • domain assumption GRDPG model: A_ij independent Bernoulli with P = X I_{p,q} X^T
    Definition 1; the whole method and identifiability discussion rest on this model.
  • domain assumption Uniform sparsity: c1 rho_n <= P_ij <= c2 rho_n for all i,j (Assumption 3)
    Needed for Lemma 4 (coherence of eigenvectors), Lemma 5, and the 2-to-infinity rates; fails for degree-heterogeneous networks.
  • domain assumption Bounded condition number kappa(P) <= c0 (Assumption 4)
    Eigen-gap condition; used in Lemma 4 and Davis-Kahan bounds.
  • domain assumption m = Omega((log n)^(1+a)) and m rho_n = Omega(log m) (Assumptions 1,5)
    Lower bounds on subsample size and subsample expected degree; without them the noise terms in Theorem 2 do not vanish.
  • ad hoc to paper Subsample entries sampled independently with probability m/n in proof, while algorithm uses uniform subsample without replacement
    Lemma 5 and Lemma 6 analysis use independent Bernoulli sampling; the paper does not justify equivalence to uniform random subset of exactly m vertices.
  • standard math External perturbation lemmas: Davis-Kahan, Lemma B.3 of Xie (2024), Lemma 6.7 of Cape et al. (2019), matrix Bernstein
    Used without proof in Appendix A; rates are taken as given.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Predictive Subsampling for Scalable Inference in Networks." pith.science (2026). https://pith.science/paper/AXTXZQPU

@misc{pith2026260216041,
  author       = {Pith},
  title        = {Pith review of: Predictive Subsampling for Scalable Inference in Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AXTXZQPU}},
  note         = {Machine review of arXiv:2602.16041}
}
read the original abstract

Current methods for statistical inference in networks often encounter substantial computational bottlenecks when applied to the massive network datasets that are increasingly common across scientific domains. In this paper, we develop \textit{Predictive Subsampling} (\texttt{PredSub}), a scalable framework for estimation and two-sample testing in networks. The central idea is to replace a full-sample estimation procedure by estimation on a random subsample, followed by out-of-sample prediction of the remaining vertices. This construction exploits the fact that the subsample provides an inferential anchor, which enables each remaining vertex to be incorporated in a \textit{predictive} manner through a fast vector operation. Building on this estimator, we develop two scalable procedures for two-sample testing, namely \texttt{PredSubTest} and \texttt{PureSubTest}. We establish finite-sample error bounds as well as estimation and testing consistency of the proposed methods in both Frobenius and two-to-infinity norms. These results formally characterize the trade-offs between statistical accuracy and computational efficiency with respect to the subsample size, the choice of test statistic, and the choice of norm. We demonstrate the empirical performance of the proposed methods through detailed simulation studies and two real-world applications involving DBLP coauthorship networks and the Cannes 2013 social media networks.

Figures

Figures reproduced from arXiv: 2602.16041 by the authors.

Figure 1
Figure 1. PredSub Schematic As we alluded to earlier, Algorithm 1 is very computationally efficient as it involves a single matrix decomposition of AS that is of much smaller size than A, while the remaining steps in Algorithm 1 only use standard matrix-vector products; see [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 3 linked inside Pith

  1. [1]

    L. A. Adamic and N. Glance. The political blogosphere and the 2004 us election: divided they blog. InProceedings of the 3rd international workshop on Link discovery, pages 36–43,

    2004

  2. [2]

    Then t2 1 2ρn∥V∥ 2 + 2∥V∥ 2∞t1/3 ≥ 2 3 v(ν, d, n)∥V∥2→∞ + p 2ρnv(ν, d, n)∥V∥ 2 2ρn∥V∥+ 2 3 ∥V∥ 2→∞ 2 3 v(ν, d, n)∥V∥2→∞ + p 2ρnv(ν, d, n)∥V∥ ≥v(ν, d, n)

    40 Applying Bernstein’s inequality we obtain P e⊤ i EV w > t ≤exp −t2 2ρn∥V∥ 2 + 2∥V∥ 2→∞t/3 Lett 1 = 2 3 v(ν, d, n)∥V∥2→∞ + p 2ρnv(ν, d, n)∥V∥. Then t2 1 2ρn∥V∥ 2 + 2∥V∥ 2∞t1/3 ≥ 2 3 v(ν, d, n)∥V∥2→∞ + p 2ρnv(ν, d, n)∥V∥ 2 2ρn∥V∥+ 2 3 ∥V∥ 2→∞ 2 3 v(ν, d, n)∥V∥2→∞ + p 2ρnv(ν, d, n)∥V∥ ≥v(ν, d, n). and hence P e⊤ i EV w > t1 ≤exp{−v(ν, d, n)}=n−ν5−d. The v...

    2018

  3. [3]

    Then for anym×dmatrixVindependent ofE, ∥EV∥ 2→∞ ≤2 p 2ρnv(ν, d, n)∥V∥+4 3 ∥V∥ 2→∞v(ν, d, n) 39 with probability at least1−n −(ν−1) wherev(ν, d, n) = log(nν5d)

    DefineE=A−P. Then for anym×dmatrixVindependent ofE, ∥EV∥ 2→∞ ≤2 p 2ρnv(ν, d, n)∥V∥+4 3 ∥V∥ 2→∞v(ν, d, n) 39 with probability at least1−n −(ν−1) wherev(ν, d, n) = log(nν5d). ProofOur result is a slight modification of Lemma 8 of Tang and Cape (2025), and we follow similar steps for the proof. The main difference is that, in contrast with Tang and Cape (202...

    2025

  4. [7]

    ProofWe follow the proof ideas in Bhattacharjee et al

    logn ϵ2 for some constantc >0, then we have |σi(P)−˜σ i(P)| ≤ϵnρn with probability at least1−n −c. ProofWe follow the proof ideas in Bhattacharjee et al. (2024). LetR∈R n×|S| be the scaled sampling matrix such thatR ⊤P R= n m PS. NowP=U P DP U ⊤ P =U P |DP |1/2Ip,q|DP |1/2U ⊤ P and hence n m PS have the same eigenvalues as|D P |1/2U ⊤ P RR⊤UP |DP |1/2Ip,q...

    2024

  5. [10]

    we have ˆXSc −P Sc,SUPS |DPS |−1/2Ip,qW ∗ =A Sc,SUAS |DAS |−1/2Ip,q −P Sc,SUPS |DPS |−1/2Ip,qW ∗ = h R+ | −R− i , R+ =A Sc,SUAS +|DAS +|−1/2 −P Sc,SUPS +|DPS +|−1/2W ∗ +, R− =A Sc,SUAS −|DAS −|−1/2 −P Sc,SUPS −|DPS −|−1/2W ∗ −. We can further decomposeR + andR − as R± =E Sc,SUAS ±|DAS ±|−1/2 +P Sc,S(UAS ± −U PS ±W ∗ +)|DAS ±|−1/2 +P Sc,SUPS +Q± whereE Sc,...

    2024

  6. [11]

    Using Lemma B.5 of Xie (2024) we also have ∥UAS ±∥2→∞ =O p (∥UPS ±∥2→∞) =O p (∥UPS ∥2→∞) =O p m−1/2 Applying Lemma 6 we obtain ∥R1±∥2→∞ =O p p ρn logn ,(8) and hence ∥R1±∥2→∞ × ∥|DAS ±|−1/2∥2 =O p r logn m We next boundR 2,±. In particular ∥R2±∥2→∞ ≤ ∥PSc,S∥2→∞∥UAS ± −U PS ±U ⊤ PS ±UAS ± +U PS ±(U ⊤ PS ±UAS ± −W ∗ ±)∥ ≤ ∥PSc,S∥2→∞{∥UAS ± −U PS ±U ⊤ PS ±UA...

    2024

  7. [2005]

    E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing. Mixed membership stochastic blockmodels.The Journal of Machine Learning Research, 9:1981–2014,

    1981

  8. [2012]

    Tang and J

    M. Tang and J. R. Cape. Eigenvector fluctuations and limit results for random graphs with infinite rank kernels.arXiv preprint arXiv:2501.15725,

    arXiv

Show all 12 references
  1. [2014]

    Komolafe, A

    T. Komolafe, A. Fong, and S. Sengupta. Scalable community extraction of text networks for automated grouping in medical databases.arXiv preprint arXiv:2111.15633,

    arXiv

  2. [2015]

    (2019) we have ∥R2±∥ ≤ ∥PSc,S∥ × ∥UAS ± −U PS ±W ∗ ±∥=O p(√nρn)

    and Lemma 6.7 in Cape et al. (2019) we have ∥R2±∥ ≤ ∥PSc,S∥ × ∥UAS ± −U PS ±W ∗ ±∥=O p(√nρn). 46 Combining the above bounds we obtain ∥R1±∥ × ∥|DAS ±|−1/2∥F =O p p n/m , ∥R2±∥ × ∥|DAS ±|−1/2∥F =O p p n/m , ∥PSc,SUPS ±∥ × ∥Q±∥F =O p s nlogm m2ρn . and hence∥R ±∥F =O p( p n/m). ...

    2019

  3. [2018]

    doi: 10.1073/pnas.1800683115

    ISSN 0027-8424. doi: 10.1073/pnas.1800683115. S. Bhadra, K. Chakraborty, S. Sengupta, and S. N. Lahiri. A bootstrap-based method for testing similarity of matched networks.Journal of Computational and Graphical Statistics, (just-accepted):1–24, 2025a. S. Bhadra, M. Pensky, and...

    arXiv

  4. [2022]

    Proof of Stated Results We begin by stating a collection of lemmas and known results, along with proofs as appro- priate, that will be used throughout the subsequent analysis

    35 Appendix A. Proof of Stated Results We begin by stating a collection of lemmas and known results, along with proofs as appro- priate, that will be used throughout the subsequent analysis. Result 1 (W eyl’s Inequality , W eyl (1912))LetAandBbe symmetricn×nmatrices. Then max ...

    1912

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.