Uniformity testing on matchings in graphs needs fewer samples
Uniformity Testing for the Monomer-Dimer Model
Data Structures and AlgorithmsDiscrete Mathematics
Summary
This paper looks at a problem where you want to check if a way of picking pairs from a network is completely fair or not, just by looking at some examples. The authors found a method to test fairness much quicker than fully figuring out the whole system, especially for networks where nodes connect to just a few others. They also proved that their method is about as efficient as possible, meaning you can't do much better in general. This is useful because testing fairness can be hard when the network gets big.
What this means in practice
- •For data analysts: Quickly test if distributions over network pairings are uniform without full estimation, saving time and data.
- •For network researchers: Understand fundamental limits on sample sizes needed for fairness testing across various graph structures.
A theory result. No direct application yet.
Authors
Joy Qiping Yang, Yuichi Yoshida
Abstract
We study uniformity testing for the monomer-dimer model on a known graph $G=(V,E)$. Given samples from an unknown distribution $D_w(M)\propto \prod_{e\in M} w_e$ over matchings $M$ of $G$, we ask whether $D_w$ is the uniform distribution over all matchings of $G$ or is $\varepsilon$-far from it in total variation distance. Our main result is that, for every maximum-degree bound $Δ$, uniformity can be tested with $\widetilde O_Δ(\sqrt m/\varepsilon^2)$ samples, where $m=|E|$. We complement this with an information-theoretic lower bound for general graphs: for every pair of parameters $n\le m\le n^2$, there are graphs with $Θ(n)$ vertices and $Θ(m)$ edges on which every tester requires $Ω(\sqrt m/\varepsilon^2)$ samples. Thus, for bounded-degree graph families with $m=Θ(n)$, testing uniformity over the space of matchings has $\widetilde Θ(\sqrt n/\varepsilon^2)$ sample complexity, in contrast with the $Θ(n/\varepsilon^2)$ samples needed to estimate $D_w$ in total variation distance.