PaperlayerView exact revision on arXiv

Source-linked AI summary

Degree Sequence Reconstruction from Subgraph Traces

Venkata Gandikota, Arick Grootveld, Haodong Yang

arXiv:2609.09397v2cs.ITmath.IT

TL;DR

The paper studies exact recovery of a graph’s degree sequence from vertex-deletion traces, beyond earlier work focused on approximation and testing. It reduces the problem through mixture estimation and degree moments, and shows that a sub-exponential number of samples suffices to distinguish graphs with different degree sequences.

  • Problem

    The paper addresses exact degree-sequence reconstruction from traces, whereas earlier statistical work focused on approximation and testing.

    Source: §1 · p. 3

  • Method

    One approach uses rejection sampling to recover mixture parameters, while another reconstructs degree sequences using degree moments and polynomial methods.

    Source: §6 · p. 25

  • Results

    A sub-exponential yet super-polynomial number of samples suffices to distinguish any pair of graphs with different degree sequences.

    Source: §6 · p. 25

  • Takeaways & Limitations

    The paper gives complementary reconstruction algorithms with different sample and runtime complexities, including a moment-based decoder whose runtime matches its sample complexity.

    Source: §6 · p. 25

    For the mixture-parameter method, the only known decoder searches all mixture parameters and takes exp{O(n)} time.

    Source: §1.1 · p. 4

Abstract

from arXiv · show

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 \Theta(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 $\Omega(n^2)$ lower bound for the trace complexity of recovering the number of edges.

1 Introduction

The paper studies exact degree-sequence reconstruction from vertex-deletion traces, contrasting this property-recovery task with broader graph reconstruction and earlier statistical work on approximation and testing. It presents two reconstruction approaches, bounds the trace complexity of recovering graph size, and identifies the moment count needed for degree-sequence recovery.

1 Introduction

  • Graph trace reconstruction deletes vertices independently; prior work reports small trace complexity for random graphs but exp{Ω(n)} traces for arbitrary graphs.This contrasts with the classical card formulation, which considers all single-vertex-deleted subgraphs.Source: §1 · p. 2
  • Earlier statistical studies focused on estimator properties, approximation, and testing, whereas this work addresses exact degree-sequence reconstruction sample complexity.The introduction situates this problem within the longer history of graph reconstruction.Source: §1 · p. 3

1.1 Our Results

  • The moment-based approach estimates graph invariants and shows how many suffice to identify the degree sequence uniquely.The paper also provides a reconstruction algorithm with runtime matching its sample complexity.Source: §1.1 · pp. 3–4
  • Rejection sampling reduces degree-sequence reconstruction to estimating binomial-mixture parameters, but the only known decoder is brute-force search with exp{O(n)} runtime.The sample-complexity analysis uses a prior trace-reconstruction result.Source: §1.1 · pp. 3–4
  • k = ˜Θ(√n) degree moments are necessary and sufficient to recover any graph’s degree sequence.The paper also develops an algorithm to recover the sequence from these moments using a polynomial construction.Source: §1.1 · p. 4

2 Preliminaries

The preliminaries specify the graph and deletion-channel model, then frame degree-sequence reconstruction through moments estimated from degree-sequence traces.

2 Preliminaries

  • Graphs are unlabeled, finite, and simple; the vertex count n and retention probability q are treated as known.The text notes that n can also be recovered with high probability from traces.Source: §2 · p. 4

2.1 The Degree-Sequence Deletion Channel

  • A degree-sequence trace is the degree-count vector of a vertex-deleted subgraph, an observation model that discards its topology.The algorithms use only these vectors, and the paper states that its results also hold when the full subgraph traces are observed.Source: §2.1 · p. 6
  • Although the full trace distribution may depend on graph topology, its expectation depends only on the original degree-count vector.The channel retains each vertex independently with probability q; a degree-ℓ vertex appears with degree i when it is retained and exactly i of its neighbors are retained.Source: §2.1 · p. 6

2.2 Degree Moments

  • The moment approach estimates low-order degree moments from traces and uses them to identify the degree-count vector.The section poses two questions: how many moments distinguish degree sequences, and how many traces recover those moments exactly.Source: §2.2 · p. 7

3 Edge Count Reconstruction

The section bounds the trace complexity of recovering a graph’s edge count, with a cubic upper bound and a quadratic lower bound.

3 Edge Count Reconstruction

  • O(n^3) traces suffice, while Ω(n^2) traces are necessary to recover the number of edges with high probability.The upper bound is stated for degree-sequence traces; the lower bound applies to any algorithm.Source: §3 · pp. 7–9
  • Each edge survives with probability q^2, so the observed trace edge count can be used to estimate the original edge count.The upper-bound argument uses concentration around the mean to recover the integer edge count.Source: §3 · pp. 7–8
  • The lower bound uses two bipartite graphs with different edge counts but close trace distributions.It holds even when algorithms observe full subgraph traces.Source: §3 · p. 9

4 Degree Sequence Reconstruction: Binomial Mixtures

The first degree-sequence method reduces trace reconstruction to estimating a binomial mixture through rejection sampling. It yields trace complexity exp{˜O(n^(1/3))}, but no sub-exponential-time mixture decoder is known.

4 Degree Sequence Reconstruction: Binomial Mixtures

  • exp{˜O(n^(1/3))} traces suffice for degree-sequence reconstruction using a method based on.The method reduces reconstruction to estimating binomial-mixture parameters.Source: §4 · p. 9
  • Rejection sampling converts trace samples into samples from a binomial mixture whose weights encode the degree counts.The mixture weights are α_i = d_i/n; estimating its parameters recovers the degree sequence.Source: §4 · pp. 9, 11
  • The mixture-estimation result gives information-theoretic separation, but no sub-exponential algorithm for recovering its components is known.An exhaustive search takes exponential time.Source: §4 · p. 11

5 Degree Sequence Reconstruction: Degree Moments

This section studies degree-moment methods for reconstructing a graph’s degree sequence, including how trace moments relate to the graph’s moments and how many moments are needed. It establishes a lower bound and describes reconstruction from moments, while identifying noisy moment extraction from traces as a bottleneck.

5.1 From traces to degree moments

  • A bijection relates post-channel falling factorial degree moments to the graph’s true degree moments, and the first k_n moments can be estimated exactly with high probability.The trace-to-moment relationship reduces estimation to the falling factorial moments.Source: §5.1 · p. 13

5.2 How Many Moments Do We Need?

  • About ˜Θ(√n) degree moments are necessary and sufficient to uniquely identify a graph’s degree sequence.The reconstruction question is converted to bounding the multiplicity of a root at x = 1 for polynomials with bounded coefficients.Source: §5.2 · p. 14

5.2.1 Upper Bound

  • The upper bound uses polynomial multiplicity results to show that O(√n log n) degree moments suffice for unique reconstruction.The polynomial argument imposes an L1 constraint on coefficients and uses tight bounds for polynomials with a high-multiplicity root at x = 1.Source: §5.2 · p. 14, §5.2.1 · p. 17

5.2.2 Lower Bound

  • The lower bound constructs a polynomial with coefficients in {−1, 0, 1} and many roots at 1, then uses the Erdős–Gallai theorem to obtain distinct graphical degree sequences.This construction shows that fewer than about ˜Θ(√n) moments cannot distinguish all degree sequences.Source: §5.2 · p. 14, §5.2.2 · p. 18
  • The cited passage reports combining Theorem 5.3 and Theorem 5.4, but the excerpt stops before stating what follows from that combination.Source: §5.2.2 · p. 21

5.3 Degree Sequence from Degree Moments

  • The first k_H moments uniquely identify any degree vector d in H_n, motivating recovery of the degree sequence directly from moments.The section's stated goal is an efficient algorithm that solves this recovery problem.Source: §5.3 · p. 22
  • Noisy trace observations must still be distilled into true moments, which the paper identifies as the bottleneck of the moment-based algorithm.The authors contrast this with Section 4's better sample complexity, whose recovery algorithm is implicit and not known to run in sub-exponential time.Source: §5.3 · p. 22
  • Algorithm 2 implements the method for recovering the degree sequence using the moments, and its runtime is poly(nk), as stated for the algorithm in the cited passage.Source: §5.3 · p. 22

6 Conclusion

The paper gives two complementary approaches to degree-sequence reconstruction: mixture estimation and recovery from degree moments. It also establishes trace-complexity bounds for size estimation and identifies open directions for improving reconstruction.

6 Conclusion

  • The mixture-based algorithm reduces degree-sequence reconstruction to estimating binomial-mixture parameters, while the degree-moment approach uses polynomial bounds to recover the sequence algebraically.The mixture weights encode the degree sequence; the moment approach also admits an efficient decoder using the same polynomial bound.Source: §6 · p. 25
  • The polynomial bound gives a degree-moment count that is tight up to logarithmic factors and an efficient decoder whose runtime matches its sample complexity.The number of moments required is necessary and sufficient up to logarithmic factors.Source: §6 · p. 25
  • The mixture-based method currently has only a brute-force decoder, which takes exponential time.The paper describes the two algorithms as having complementary sample and runtime complexities.Source: §6 · p. 25
  • For estimating graph size, the trace-complexity upper and lower bounds differ by a factor of n.The conclusion identifies this as an introductory result on estimating the first moment.Source: §6 · p. 25
  • Any two graphs with different degree sequences can be distinguished with a sub-exponential but still super-polynomial number of samples.This contrasts with the cited exponential-sample lower bound for reconstructing arbitrary graphs.Source: §6 · p. 25
  • Improving the degree-sequence trace upper bound remains an open problem; the authors suggest exploiting joint information across traces rather than using one vertex per trace.They describe the single-vertex-per-trace approach as seemingly wasteful.Source: §6 · p. 26
  • Other open directions include closing the size-reconstruction trace gap, proving a non-trivial degree-sequence lower bound, and considering non-constant q or other channels.The paper also mentions coded and approximate trace reconstruction for unlabeled graphs.Source: §6 · p. 26

A Proof of Theorem 3.2

The proof compares traces from two nearby complete bipartite graphs by mapping pairs of binomial variables to graph traces. It uses a Hellinger-distance bound to support a sample-based distinction argument.

A Proof of Theorem 3.2

  • A bounded Hellinger distance between the pair distributions is the intermediate result used in the proof.The proposition is titled “Bounded Hellinger Distance.”Source: A Proof of Theorem 3.2 · p. 32
  • The proof uses the likelihood ratio and a large-deviation event under the mixture law to control the Hellinger distance, then invokes tensorization for repeated samples.The argument frames the sample requirement as distinguishing the graph-trace distributions with probability at least 1−δ.Source: A Proof of Theorem 3.2 · pp. 32–34
  • The proof compares K_N,N with K_N+1,N−1 and maps pairs of binomial variables to their corresponding complete bipartite graph traces.The binomial variables have distribution Bin(N, q), and the second input law is a mixture involving Bin(N−1, q) and Bin(N+1, q).Source: A Proof of Theorem 3.2 · pp. 32, 34
Loading 2609.09397v2…