Algorithms recover graph degree sequences from partial vertex data
Degree Sequence Reconstruction from Subgraph Traces
Information Theory
Summary
Sometimes we want to know how connected each point is in a network, but we only get pieces of the network where some points are missing. The paper presents two ways to figure out the full list of connections for all points from these incomplete views. One method uses a sampling trick with lots of examples, though it needs a lot of time to compute the answer. The other uses mathematical summaries called degree moments to reconstruct the connections more efficiently. The authors also studied how hard it is to count the total number of connections in this incomplete data setup.
What this means in practice
- •For network analysts: Estimate node connectivity in networks from incomplete or partially observed data where some nodes are missing at random.
- •For data recovery engineers: Reconstruct detailed network structure information when only partial snapshots with randomly missing nodes are available.
A theory result. No direct application yet.
Authors
Venkata Gandikota, Arick Grootveld, Haodong Yang
Abstract
The goal of degree sequence reconstruction is to recover the ordered vector of degrees of an unknown graph from vertex deleted traces, where each vertex is deleted independently with probability $p$. We provide two algorithms for reconstruction; the first uses rejection sampling to reduce the problem to an estimation problem for a mixture distribution. Combined with prior trace reconstruction results, this gives a reconstruction algorithm using $\Exp{\tilde O (n^{1/3})}$ traces, although no sub-exponential time decoder is known. Our other approach involves recovering certain graph invariants, degree moments, that can identify a graphs degree sequence. Extremal polynomial bounds show that $\tilde Θ(n^{1/2})$ degree moments are necessary and sufficient to reconstruct the degree sequence, which leads to an algorithm with $\Exp{\tilde O(n^{1/2})}$ trace complexity. The same polynomial machinery yields a sub-exponential time decoder for the degree sequence from the moments. Additionally, we give an $O(n^{3})$ upper bound and a $Ω(n^2)$ lower bound for the trace complexity of recovering the number of edges.