Suppose you want to estimate how many disjoint pairs can be formed in a huge network, such as a collaboration or web graph, while reading only a small fraction of it. Suppose also that an adversary has blanked out some of the entries before you start. Sometimes the blanked-out places are marked, so you know where the gaps are. Sometimes they are not marked, and the adversary has instead overwritten entries with false neighbors. The pairing problem is maximum matching: choosing as many edges as possible so that no two share a vertex. Theory for estimating matching size quickly already exists for clean graphs. For the two damaged versions, nothing is known.
Property testing, the study of deciding global properties from a few queries, has names for the two failure modes. Marked gaps are erasures; unmarked falsehoods are errors, and a tester that copes with errors is called tolerant. It has also proved that erasures can be exponentially easier than errors, but only for artificial coding-theoretic properties (Erasures vs. Errors in Local Decoding and Property Testing). This note proposes the first graph-theoretic version of that separation. Its tool is the Edge-Degree Constrained Subgraph (EDCS), a sparse subgraph defined only by local degree conditions that is known to preserve about two-thirds of the maximum matching. The central observation is that marked gaps in adjacency lists can be modeled as an implicit, query-free "wildcard" structure attached to the EDCS. Unmarked lies admit no such trick.
Core Claim
In the adjacency-list model, a query asks for "the $i$-th neighbor of $u$" or for "the degree of $u$". Let an adversary erase an $\alpha$ fraction of list entries, so that such queries return $\bot$. The truth is then pinned only to an interval. At the low end is $\mu_{lo}$, the matching size of the known edges. At the high end is $\mu_{hi}$, the largest matching size over all graphs consistent with the erasures.
We claim that both ends can be estimated to within a factor $1.5+\epsilon$, plus an additive $\epsilon n$, at essentially the same query cost as the clean-graph EDCS estimator of Sublinear Algorithms for (1.5+ε)-Approximate Matching, whose running time is $n^{2-\Theta(\epsilon^2)}$. The only extra cost should be a $1/(1-\alpha)$ overhead, of the kind Dixit et al. obtained for line-domain properties.
We further conjecture that the same guarantee is unattainable at comparable cost when the same budget is spent on corruptions instead of erasures. The plan targets this conjecture at two strengths:
- Provable target. A clean logarithmic-type separation for a graph property built from EDCS certificates.
- Stretch goal. A polynomial separation for matching-size testing itself.
The technical handle for $\mu_{hi}$ is concrete. An erased entry in $u$'s list is a "stub": $u$ has some neighbor we cannot see. Any two stub-carrying vertices could be joined in some consistent completion. So $\mu_{hi}$ is, up to a small bookkeeping error, the matching size of $G_{known} \cup K(S)$, where $S$ is the set of stub vertices and $K(S)$ is the complete graph on them. That clique never needs to be queried. Its degree structure is determined by $|S|$ and by which vertices belong to $S$, both of which the estimator learns from $\bot$ answers. An EDCS on the union can therefore be simulated as a local, query-driven structure. Its two defining constraints are:
$$d_H(u)+d_H(v)\le \beta \ \text{ for edges } (u,v)\in H, \qquad d_H(u)+d_H(v)\ge \beta-\delta \ \text{ for edges } (u,v)\notin H.$$
Here $H$ is the sparse subgraph, $d_H$ is degree inside $H$, and $\beta,\delta$ are integer parameters. Both constraints still read only degrees, which is why erasures are benign. Corruptions attack exactly those degrees and neighbor identities without warning.
Research Program
Model. The first task is to fix the model carefully. Degree queries stay intact, and erasures hide neighbor identities. This matches the "sensor knows it has a link but not to whom" failure. We define an erasure-resilient $(c,\epsilon)$-estimator as one whose output lies in $[\mu_{lo}/c-\epsilon n,\ \mu_{hi}+\epsilon n]$. This mirrors the completion-based definition of erasure-resilient testing in Dixit et al.. We then adapt the Bhattacharya–Kiss–Saranurak EDCS construction (paper) in two ways:
- Sampling correction. Random-neighbor sampling at a vertex draws $\bot$ at a rate the algorithm observes, so the sampler can reweight by that rate. The adversary can concentrate erasures on chosen vertices, so the analysis must bound the damage from heavily erased vertices. We plan to charge that damage to the additive $\epsilon n$ term and to the EDCS slack $\delta$.
- Implicit clique. The same construction runs on the implicit clique for the $\mu_{hi}$ estimate.
Analysis. The analysis reuses the EDCS matching guarantee of Assadi and Bernstein unchanged. The new work lies in the sampling lemmas.
For bipartite inputs we will also track small-$\beta$ parameters. Azarmehr et al. proved via a factor-revealing linear program that EDCS attains ratio 0.6774 at $\beta=6,\beta^-=5$. Small $\beta$ is also exactly the regime where each erased entry most perturbs local degrees.
Separation. This is the second, harder half. The provable target imitates the basic $\Omega(\log N)$ versus $O(1)$ separation of Raskhodnikova et al. (see also Raskhodnikova and Varma) inside a graph. The construction works as follows:
- Each list entry carries a claimed membership bit for $H$ and a redundantly encoded copy of the endpoint's $H$-degree.
- The property is "the marking is an EDCS of $G$".
- Under erasures, any surviving copy of a degree suffices, so checking a random edge's two constraints takes $O(1/(1-\alpha))$ queries.
- Under errors, the copies must be decoded against adversarial noise.
We aim to prove a lower bound that grows with $n$ in that case. The stretch goal is a polynomial separation for the natural property "$\mu \ge k$". The approach is to let corruptions plant, locally and invisibly, the hard instances behind the $n^{1.2-o(1)}$ lower bound of Behnezhad, Roghani and Rubinstein. With erasures, the same regions would be flagged and could be absorbed into the interval.
We state the stretch goal honestly as a conjecture. It may fail, because matching estimation is already hard in the clean model and the extra hardness from errors could vanish in the $\epsilon n$ slack. Deciding which way it goes is itself a result.
Non-adaptive lens. Pallavoor et al. turned erasure-resilient hard instances into lower bounds for non-adaptive testers, which fix all queries in advance. As a side question, we will check whether the stub-clique view gives a cleaner hard distribution for the non-adaptive matching gap of Shah. That gap runs between an $n^{1/3}$ lower bound and an $n^{1/2}$ upper bound. It is secondary and not needed for the main claim.
Baselines
Naive reference. The naive reference is the clean-graph EDCS estimator of Bhattacharya et al. run with every $\bot$ treated as a non-edge. It is the obvious thing a practitioner would do. It targets only $\mu_{lo}$, and its degree-proportional sampling is silently biased by the erasures. It receives the same query budget, the same $(\beta,\delta)$ grid, and the same random seeds as our estimator. We beat it if we achieve the following on hub- and matching-targeted erasures:
- Low end. Lower error in estimating $\mu_{lo}$.
- High end. An upper estimate that contains the true $\mu_{hi}$, which the baseline cannot produce at all.
Strongest existing method. The strongest method for the underlying quantity is the same EDCS estimator given the uncorrupted graph. Its theoretical guarantee is $(1.5+\epsilon)$ in $n^{2-\Theta(\epsilon^2)}$ time, from Bhattacharya et al.. For bipartite inputs, the best proven EDCS ratio is 0.6774 at $\beta=6$ (Azarmehr et al.). We found no reported empirical result on Lacuna for sublinear matching-size estimation on any of the benchmark graphs below. We will therefore measure this "oracle" baseline ourselves and treat it as a ceiling: matching it within a $1/(1-\alpha)$ query overhead counts as success.
Simpler competitors. We also run the adaptive random-order greedy estimator that attains a 2-approximation in $\tilde O(n)$ queries, as cited in Shah, with $\bot$ handled both naively and by reweighting. We also run Shah's non-adaptive $n^{1/2}$-approximation, which uses $O(n\log^2 n)$ queries.
Ablation. The key ingredient is isolated by an ablation that keeps the erasure-aware sampler but drops the implicit clique, and one that keeps the clique but drops reweighting.
Why not just…?
Why not just treat $\bot$ as a missing edge and run the clean estimator? This is the real threat for the low end: $\mu(G_{known})$ is exactly $\mu_{lo}$. Its weakness is the sampler, not the target. Bhattacharya-style sampling draws neighbors in proportion to reported degree. If the adversary concentrates erasures on the vertices of a maximum matching, those samples hit $\bot$ disproportionately, and the density check is evaluated on the wrong vertices. The naive-baseline comparison on matching-targeted erasures settles whether this bias matters in practice. If it does not, our contribution for the low end shrinks to the analysis, and the $\mu_{hi}$ estimate becomes the main deliverable.
Why not just sample edges uniformly and rescale by $1-\alpha$? Uniform sampling drops isolated matching edges with constant probability, which is why Assadi and Bernstein and the EDCS line use degree-sensitive sparsifiers instead. Demystifying Graph Sparsification Algorithms also reports that random sampling preserves structural metrics worse than degree-based methods. We include it as a cheap control on graphs with many degree-one vertices.
Why not just use the fault-tolerant EDCS of Assadi and Bernstein? Their subgraph of $O(f+n)$ edges survives $f$ adversarial deletions, but building it requires reading the whole graph offline (paper). It also does not distinguish deletions the algorithm can see from lies it cannot. Our estimator must work sublinearly with the damage already in place.
Why not just run a tolerant tester and ignore the erasure marks? Raskhodnikova et al. show that discarding the location of the gaps can cost a polynomial factor in queries. Whether the same holds for matchings is precisely our separation question. The corruption experiments below measure it directly.
Proposed Experiments
Data and exact answers. We use real networks from the sparsification benchmark of Demystifying Graph Sparsification Algorithms: ego-Facebook, email-Enron, ca-AstroPh, ca-HepPh, com-DBLP, com-Amazon, web-Google and web-Stanford. The bipartite small-$\beta$ experiments add bipartite double covers of these graphs. For each graph we compute $\mu_{lo}$ and $\mu_{hi}$ exactly offline. For $\mu_{hi}$ we use a blossom-algorithm matching on $G_{known}\cup K(S)$ and verify it against brute-force completions on small subgraphs.
Adversaries. Four erasure adversaries are applied at $\alpha\in\{0.01,0.05,0.1,0.2\}$:
- uniform random erasure;
- erasure of hub adjacency lists;
- erasure concentrated on the vertices of a fixed maximum matching;
- erasure of the edges an EDCS would include.
Each is paired with a corruption adversary that spends the same budget rewiring the same entries to plausible false neighbors, without marks.
Metrics. We report estimate over true value for each end of the interval, the fraction of runs whose output interval contains the truth, and queries used as a fraction of $2m$.
Decisive checks. The first check concerns erasures. The erasure-aware estimator should contain the truth in nearly all runs, with query overhead close to $1/(1-\alpha)$, while the naive baseline misses $\mu_{lo}$ under matching-targeted erasures.
The second check is the empirical face of the separation. Under corruptions at equal budget, every estimator we have should show error that grows with the budget. That includes ours run with no marks, the greedy estimator, and the clean EDCS. If corruption proves no more damaging than erasure on these graphs, that is evidence against the polynomial conjecture, and the theory effort then narrows to the certificate-property separation.
The third check is the proof. We regard the proof of the erasure upper bound and of the logarithmic certificate separation as the core deliverable. The experiments determine whether the stronger conjecture is worth pursuing.
References
- Erasures vs. Errors in Local Decoding and Property Testing
- Sublinear Algorithms for (1.5+ε)-Approximate Matching
- Erasure-Resilient Property Testing
- Towards a Unified Theory of Sparsification for Matching Problems
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
- Brief Announcement: Erasure-Resilience Versus Tolerance to Errors
- Sublinear Time Algorithms and Complexity of Approximate Maximum Matching
- Approximating the distance to monotonicity of Boolean functions
- Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
- Demystifying Graph Sparsification Algorithms in Graph Properties Preservation