# A Sampling-based Framework for Hypothesis Testing on Large Attributed Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 37 references that are in the map.
- First posted on arXiv 20 Mar 2024.

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

- [Hypothesis Testing for Automated Community Detection in Networks](https://mlsanity.com/paper/1311.2694/) (2013)
- [Two-sample Hypothesis Testing for Inhomogeneous Random Graphs](https://mlsanity.com/paper/1707.00833/) (2017)
- [Slim Graph: Practical Lossy Graph Compression for Approximate Graph Processing, Storage, and Analytics](https://mlsanity.com/paper/1912.08950/) (2019)
- [Two-Sample Tests for Large Random Graphs Using Network Statistics](https://mlsanity.com/paper/1705.06168/) (2017)
- [Practical methods for graph two-sample testing](https://mlsanity.com/paper/1811.12752/) (2018)
- [Hypothesis Testing of Matrix Graph Model with Application to Brain Connectivity Analysis](https://mlsanity.com/paper/1511.00718/) (2015)

## Abstract (arXiv)

Hypothesis testing is a statistical method used to draw conclusions about populations from sample data, typically represented in tables. With the prevalence of graph representations in real-life applications, hypothesis testing in graphs is gaining importance. In this work, we formalize node, edge, and path hypotheses in attributed graphs. We develop a sampling-based hypothesis testing framework, which can accommodate existing hypothesis-agnostic graph sampling methods. To achieve accurate and efficient sampling, we then propose a Path-Hypothesis-Aware SamplEr, PHASE, an m- dimensional random walk that accounts for the paths specified in a hypothesis. We further optimize its time efficiency and propose PHASEopt. Experiments on real datasets demonstrate the ability of our framework to leverage common graph sampling methods for hypothesis testing, and the superiority of hypothesis-aware sampling in terms of accuracy and time efficiency.