Optimal adaptivity of signed-polygon statistics for network testing
From MaRDI portal
Abstract: Given a symmetric social network, we are interested in testing whether it has only one community or multiple communities. The desired tests should (a) accommodate severe degree heterogeneity, (b) accommodate mixed-memberships, (c) have a tractable null distribution, and (d) adapt automatically to different levels of sparsity, and achieve the optimal phase diagram. How to find such a test is a challenging problem. We propose the Signed Polygon as a class of new tests. Fixing , for each -gon in the network, define a score using the centered adjacency matrix. The sum of such scores is then the -th order Signed Polygon statistic. The Signed Triangle (SgnT) and the Signed Quadrilateral (SgnQ) are special examples of the Signed Polygon. We show that both the SgnT and SgnQ tests satisfy (a)-(d), and especially, they work well for both very sparse and less sparse networks. Our proposed tests compare favorably with the existing tests. For example, the EZ and GC tests behave unsatisfactorily in the less sparse case and do not achieve the optimal phase diagram. Also, many existing tests do not allow for severe heterogeneity or mixed-memberships, and they behave unsatisfactorily in our settings. The analysis of the SgnT and SgnQ tests is delicate and extremely tedious, and the main reason is that we need a unified proof that covers a wide range of sparsity levels and a wide range of degree heterogeneity. For lower bound theory, we use a phase transition framework, which includes the standard minimax argument, but is more informative. The proof uses classical theorems on matrix scaling.
Recommendations
- scientific article; zbMATH DE number 2112480
- Hypothesis Testing for Network Data with Power Enhancement
- Network and adaptive sampling
- Adaptive statistical algorithms in network reliability analysis
- Hypothesis testing for populations of networks
- Polytope samplers for network tomography
- On adaptive testing in orthogonal saturated designs
- Efficient connectivity testing of hypercubic networks with faults
Cites work
- A goodness-of-fit test for stochastic block models
- An impossibility result for reconstruction in the degree-corrected stochastic block model
- Asymptotics of sample eigenstructure for a large dimensional spiked covariance model
- Community structure in social and biological networks
- Computational barriers in minimax submatrix detection
- Contiguity and non-reconstruction results for planted partition models: the dense case
- Detecting overlapping communities in networks using spectral methods
- Detection boundary in sparse regression
- Diagonal Equivalence to Matrices with Prescribed Row and Column Sums. II
- Fast community detection by SCORE
- Hierarchical Community Detection by Recursive Partitioning
- Higher criticism for detecting sparse heterogeneous mixtures.
- Hypothesis testing for automated community detection in networks
- Likelihood-based model selection for stochastic block models
- Matrix estimation by universal singular value thresholding
- Mixed membership stochastic blockmodels
- Non-backtracking spectrum of degree-corrected stochastic block models
- Reconstruction and estimation in the planted partition model
- Scaling of matrices to achieve specified row and column sums
- Scaling of symmetric matrices by positive diagonal congruence
- Subsampling bootstrap of count features of networks
- Testing for high-dimensional geometry in random graphs
- The DAD Theorem for Arbitrary Row Sums
- The method of moments and degree distributions for network models
Cited in
(24)- Mixed Membership Estimation for Social Networks
- Mathematical foundations of machine learning. Abstracts from the workshop held March 21--27, 2021 (hybrid meeting)
- Hierarchical Community Detection by Recursive Partitioning
- On the efficacy of higher-order spectral clustering under weighted stochastic block models
- Optimal Estimation of the Number of Network Communities
- Power enhancement and phase transitions for global testing of the mixed membership stochastic block model
- Universal rank inference via residual subsampling with application to large networks
- A Spectral-Based Framework for Hypothesis Testing in Populations of Networks
- Stock co-jump networks
- Random geometric graph: some recent developments and perspectives
- Special invited paper: the SCORE normalization, especially for heterogeneous network and text data
- Statistical limits for testing correlation of random hypergraphs
- Co-citation and Co-authorship Networks of Statisticians
- Rejoinder: “Co-citation and Co-authorship Networks of Statisticians”
- Likelihood Ratio Tests in Random Graph Models with Increasing Dimensions
- Multiscale tests for point processes and longitudinal networks
- Network Goodness-of-Fit for the Block-Model Family
- Information-theoretic limits for testing community structures in weighted networks
- Optimal Network Pairwise Comparison
- Testing common degree-correction parameters of multilayer networks
- Goodness-of-fit testing based on graph functionals for homogeneous Erdős-Rényi graphs
- Testing network correlation efficiently via counting trees
- Robust detection of watermarks for large language models under human edits
- New methods for testing community structures in general networks
This page was built for publication: Optimal adaptivity of signed-polygon statistics for network testing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2073714)
