Network Signflip Parallel Analysis for Selecting the Embedding Dimension
arXiv:2509.05722
The paper proposes a data‑driven spectral technique called NetFlipPA that determines how many dimensions to keep when embedding large heterogeneous networks by comparing eigenvalues of the original normalized adjacency matrix to those after randomly flipping signs of its entries.
Abstract
This paper investigates the problem of selecting the embedding dimension for large heterogeneous networks that have weakly distinguishable community structure. For a broad family of embeddings based on normalized adjacency matrices, we introduce a novel spectral method that compares the eigenvalues of the normalized adjacency matrix to those obtained after randomly signflipping its entries. The proposed method, called network signflip parallel analysis (NetFlipPA), is interpretable, simple to implement, data driven, and does not require users to carefully tune parameters. For large random graphs arising from degree-corrected stochastic blockmodels with weakly distinguishable community structure (and consequently, non-diverging eigenvalues), NetFlipPA provably recovers the spectral noise floor (i.e., the operator norm of the noise component of the normalized adjacency matrix). NetFlipPA thus provides a statistically rigorous randomization-based method for selecting the embedding dimension by keeping the eigenvalues whose magnitudes rise above the recovered spectral noise floor. Compared to traditional cutoff-based methods, the data-driven threshold used in NetFlipPA is provably effective under milder assumptions on the node degree heterogeneity and the number of node communities. Our main results rely on careful non-asymptotic perturbation analysis and leverage recent progress on local laws for nonhomogeneous Wigner-type random matrices.
This article has been accepted for publication in the IEEE Transactions on Information Theory. (c) 2026 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information. 46 pages, 5 figures