# Higher-order accurate two-sample network inference and network hashing

arXiv: https://arxiv.org/abs/2208.07573 · HTML: https://mlsanity.com/paper/2208.07573/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 76 references that are in the map.
- First posted on arXiv 16 Aug 2022.

## Builds on (most cited first, 27 of 27)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [NetLSD: Hearing the Shape of a Graph](https://mlsanity.com/paper/1805.10712/) (2018)
- [Community Detection in Networks with Node Attributes](https://mlsanity.com/paper/1401.7267/) (2014)
- [Metrics for Graph Comparison: A Practitioner's Guide](https://mlsanity.com/paper/1904.07414/) (2019)
- [Community Detection in Degree-Corrected Block Models](https://mlsanity.com/paper/1607.06993/) (2016)
- [Estimating network edge probabilities by neighborhood smoothing](https://mlsanity.com/paper/1509.08588/) (2015)
- [Graph Matching: Relax at Your Own Risk](https://mlsanity.com/paper/1405.3133/) (2014)
- [Network histograms and universality of blockmodel approximation](https://mlsanity.com/paper/1312.5306/) (2013)
- [Hypothesis Testing For Network Data in Functional Neuroimaging](https://mlsanity.com/paper/1407.5525/) (2014)
- [Optimal hypothesis testing for stochastic block models with growing degrees](https://mlsanity.com/paper/1705.05305/) (2017)
- [Two-sample Hypothesis Testing for Inhomogeneous Random Graphs](https://mlsanity.com/paper/1707.00833/) (2017)
- [Randomized incomplete U-statistics in high dimensions](https://mlsanity.com/paper/1712.00771/) (2017)
- [Bootstrapping Networks with Latent Space Structure](https://mlsanity.com/paper/1907.10821/) (2019)
- [Testing for Global Network Structure Using Small Subgraph Statistics](https://mlsanity.com/paper/1710.00862/) (2017)
- [Subsampling bootstrap of count features of networks](https://mlsanity.com/paper/1312.2645/) (2013)
- [Two-Sample Tests for Large Random Graphs Using Network Statistics](https://mlsanity.com/paper/1705.06168/) (2017)
- [Bootstrapping Exchangeable Random Graphs](https://mlsanity.com/paper/1711.00813/) (2017)
- [Practical methods for graph two-sample testing](https://mlsanity.com/paper/1811.12752/) (2018)
- [Graphon based Clustering and Testing of Networks: Algorithms and Theory](https://mlsanity.com/paper/2110.02722/) (2021)
- [Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks](https://mlsanity.com/paper/1812.10519/) (2018)
- [Testing Network Structure Using Relations Between Small Subgraph Probabilities](https://mlsanity.com/paper/1704.06742/) (2017)
- [Network Global Testing by Counting Graphlets](https://mlsanity.com/paper/1807.08440/) (2018)
- [Subsampling Sparse Graphons Under Minimal Assumptions](https://mlsanity.com/paper/1907.12528/) (2019)
- [Statistical inference for network samples using subgraph counts](https://mlsanity.com/paper/1701.00505/) (2017)
- [Edgeworth expansions for network moments](https://mlsanity.com/paper/2004.06615/) (2020)
- [A Practical Two-Sample Test for Weighted Random Graphs](https://mlsanity.com/paper/2101.12492/) (2021)
- [Central limit theorems for local network statistics](https://mlsanity.com/paper/2006.15738/) (2020)

## Built on by (most cited first, 1 of 1)

- [Optimal Clustering of Discrete Mixtures: Binomial, Poisson, Block Models, and Multi-layer Networks](https://mlsanity.com/paper/2311.15598/) (2023)

## Abstract (arXiv)

Two-sample hypothesis testing for network comparison presents many significant challenges, including: leveraging repeated network observations and known node registration, but without requiring them to operate; relaxing strong structural assumptions; achieving finite-sample higher-order accuracy; handling different network sizes and sparsity levels; fast computation and memory parsimony; controlling false discovery rate (FDR) in multiple testing; and theoretical understandings, particularly regarding finite-sample accuracy and minimax optimality. In this paper, we develop a comprehensive toolbox, featuring a novel main method and its variants, all accompanied by strong theoretical guarantees, to address these challenges. Our method outperforms existing tools in speed and accuracy, and it is proved power-optimal. Our algorithms are user-friendly and versatile in handling various data structures (single or repeated network observations; known or unknown node registration). We also develop an innovative framework for offline hashing and fast querying as a very useful tool for large network databases. We showcase the effectiveness of our method through comprehensive simulations and applications to two real-world datasets, which revealed intriguing new structures.