Counting the Failure Modes You Have Not Seen: Head–Tail Estimation of Network Unreliability

When a well-built network such as a power grid fails, it fails by losing every link across some cut. A cut is a set of links whose removal splits the network in two. A few cheap cuts account for most of the risk, and a huge number of more expensive cuts share the remainder. Estimating the failure probability by simulation therefore looks a lot like estimating properties of a large-alphabet distribution. Each simulated failure reveals one "species" of failure mode. A few species show up over and over, and most of the tail is never observed at all. We propose to split the problem the way property-estimation methods split frequent from rare symbols. Failure modes seen often enough are computed exactly. The rest are estimated by reweighted sampling. A Good-Turing style count of how many modes were seen only once then yields a certificate, an explicit upper bound on how much failure probability could be hiding in modes the sampler never found.

This matters because the regime operators care about, where failure probabilities are around $10^{-6}$ and edge failure rates differ from link to link, is where current tools are weakest. The almost-linear randomized approximation schemes for unreliability assume every edge fails with the same probability. Logic-based counters slow down sharply when failure probabilities are tiny. Ordinary importance sampling, which simulates from a distribution with inflated failure rates and reweights, can report a tight but wrong confidence interval whenever its proposal misses a failure mode, because the empirical variance cannot see what was never sampled. Our contribution targets that silent-miss problem directly.

Core Claim

Label each simulated disconnected world by the vertex set $S$ of the connected component containing a fixed root vertex $r$. Failure means $S \neq V$. Every failed world gets exactly one label, so unreliability becomes an additive functional over a huge discrete alphabet:

$$U = \sum_{S \subsetneq V} P(S_r = S), \qquad P(S_r = S) = \Big(\prod_{e \in \delta S} q_e\Big)\, R_{G[S]},$$

Here $q_e$ is the failure probability of edge $e$, $\delta S$ is the set of edges leaving $S$, and $R_{G[S]}$ is the probability that the subgraph induced on $S$ stays connected. The additivity is the hook that lets frequency-estimation tools apply. The restriction of Data Amplification: Instance-Optimal Property Estimation to additive properties is exactly what this labeling satisfies.

The split works as follows. Head labels are those seen more than $\tau$ times in a pilot half of the samples. For each head label, the cut factor is computed exactly as a product. The interior factor $R_{G[S]}$ is close to 1, and pinning a quantity near 1 to small relative error takes only a modest crude Monte Carlo run. This uses the reliability–unreliability asymmetry that Network Unreliability in Almost-Linear Time and Beyond the Quadratic Time Barrier for Network Unreliability emphasize, but in the easy direction. The tail is estimated from the second half by importance sampling restricted to non-head labels. Because the pilot and estimation halves are independent, the tail estimate stays unbiased. The sample-splitting device comes from the data amplification paper.

The certificate works as follows. Suppose the proposal inflates each edge's failure rate so that $q_e/q'_e \le 1$. Then every world whose label is $S$ has a likelihood ratio of at most $C \cdot e^{-\lambda(S)}$. Here $C = \prod_e (1-q_e)/(1-q'_e)$ is a computable constant, and $\lambda(S) = \sum_{e\in\delta S}\log(q'_e/q_e)$ is the weight of the cut under log-tilt weights. Let $\lambda^\star$ be the smallest such weight among cuts not already in the observed set. Any min-cut routine can lower-bound it. Then

$$P(\text{unseen labels}) \;\le\; C\, e^{-\lambda^\star}\,\Big(\tfrac{N_1}{N} + \text{dev}(N,\delta)\Big),$$

where $N_1$ is the number of labels seen exactly once among $N$ proposal samples. $N_1/N$ is the Good-Turing estimate of the proposal's missing mass, and $\text{dev}(N,\delta)$ is a standard concentration term at confidence $1-\delta$.

The resulting estimator is unbiased for $U$ on its own. The certificate adds something plain importance sampling lacks: a bound on unseen failure mass whose validity does not depend on the sampler having already found every mode.

Research Program

The first strand is the estimator and its analysis. We will prove unbiasedness of the head-exact, tail-sampled estimator. We will bound its variance relative to plain importance sampling under the same proposal. The expected gain is that the variance contributed by head labels, which dominates when a few cheap cuts carry most of $U$, is removed entirely. We will also prove the certificate above, and tighten $\lambda^\star$ by enumerating the few smallest cuts under the tilt weights with a deterministic cut routine.

Good-Turing is used here in the role that Competitive Distribution Estimation gives it for rare symbols, where it estimates total mass without identifying the rare items. The choice of $\tau$ follows the frequent/rare switch analyzed there and in Doubly-Competitive Distribution Estimation. As a secondary output, we will run the fingerprint linear program of Estimating the Unseen on the label counts. That program recovers a distribution consistent with how many labels were seen once, twice, and so on. Here it would estimate how many distinct failure modes carry non-negligible probability, which is a quantity operators ask for and no reliability tool currently reports.

The second strand is the proposal distribution under heterogeneous failure rates. We will not claim a new asymptotic runtime. The open question noted for the tree-packing methods, extending them to non-uniform edge probabilities, stays open. Instead, we will use a simple tilt: scale each $q_e$ up by a common factor, chosen on the pilot half so that failures appear in a constant fraction of samples. We will also use a cut-guided tilt that inflates only edges on the few smallest weighted cuts. The certificate holds for either, so the proposal can be heuristic without the error bar becoming heuristic.

The third strand is diagnostics. When $N_1/N$ is large, the certificate is loose, and the method reports that the tail is under-explored instead of reporting a false interval. It then prompts for more samples or a lower threshold $\tau$.

The role of prior work in this design is as follows. The two fast unreliability schemes motivate it, since they already split by regime, but only coarsely, at global $U$ against $1/n$ or in three tiers, and only for uniform $p$. We split per failure mode and allow heterogeneous $q_e$. Efficient Network Reliability Computation in Uncertain Graphs is the closest hybrid in spirit, combining exact structure on important parts with stratified sampling elsewhere. Its layer-discarding keeps no guarantee after pruning, while our split carries an explicit unseen-mass bound. The model-counting line, Counting-Based Reliability Estimation for Power-Transmission Grids, Network Reliability Estimation in Theory and Practice, and A Fast and Accurate ASP Counting Based Network Reliability Estimator, constrains the design in two ways. It gives real PAC guarantees, and it reports a performance cliff at small edge probabilities because tiny probabilities must be encoded as long chains of auxiliary variables. Our method never encodes probabilities logically, so that cliff does not apply.

Baselines

The naive reference is crude Monte Carlo. It simulates independent coin flips per edge and checks connectivity by breadth-first search, with its sample budget set to the same wall-clock time as our method. It is the right floor because it is what practitioners run. We expect it to return zero failures, or a handful, whenever $U$ is well below the inverse of the sample count. That is the $\Omega(1/U)$ sample requirement noted in the fast unreliability papers.

The strongest competitor on the rare-event question is plain importance sampling. It uses the identical tilted proposal, the identical total sample count including our pilot half, and a standard empirical-variance confidence interval. This is the fairest possible comparison, because it isolates exactly what the head–tail split and certificate add. No reported result was found on Lacuna for importance-sampling unreliability estimators on these benchmarks. The fast schemes of Network Unreliability in Almost-Linear Time and Beyond the Quadratic Time Barrier for Network Unreliability report asymptotic running times, and the file contains no empirical error figures for them. We will implement their uniform-$p$ importance sampler where an implementation is feasible and run it on uniform-$p$ instances only, since that is their stated scope.

The strongest published system on the shared benchmarks is RelNet-ASP. A Fast and Accurate ASP Counting Based Network Reliability Estimator reports an average observed error of 0.036 against 0.423 for GBAS, a Time Accuracy Penalty score of 2262 against 2853 for Huber22, and coverage of 587 of 710 instances within 10,000 seconds. For the power grids, RelNet reports a geometric-mean observed error of about 0.019 on the Eureka grid in Counting-Based Reliability Estimation for Power-Transmission Grids. We run both at their published tolerance settings under the same time limit.

Beating RelNet-ASP has two parts. At the published edge probabilities, we must match its observed error. As edge failure probabilities shrink to between $10^{-4}$ and $10^{-6}$, we must hold relative error while it times out or degrades. No reported result was found on Lacuna for RelNet-ASP in that low-probability regime, so we will measure it ourselves.

Beating plain importance sampling means lower relative error at equal samples. It also means, and this matters more, empirical coverage of our certified interval near its nominal level on instances where the importance-sampling interval undercovers.

Two ablations isolate the key ingredients. The first keeps the head–tail split but drops the certificate, reporting only the empirical-variance interval. It tests whether the Good-Turing bound, not merely the split, is responsible for any gain in coverage. The second keeps the certificate but sets the threshold $\tau$ to infinity, so there is no exact head. It tests whether exact head computation, not merely the bound, is responsible for any reduction in variance.

Why not just…?

Why not just run crude Monte Carlo longer? At $U = 10^{-6}$, collecting even a few dozen failures takes tens of millions of connectivity checks per estimate. The reliability search literature already shows how badly this scales. In Fast Reliability Search in Uncertain Graphs, a bounded search is reported up to 100,000 times faster than sampling baselines. In Efficient Network Reliability Computation in Uncertain Graphs, hybrid BDD–sampling is reported up to 51.2 times faster than traditional sampling. Our crude Monte Carlo runs at matched time will quantify the gap on grids.

Why not just use importance sampling with its usual confidence interval? This is the real threat. On networks with one dominant cut, a well-tilted importance sampler may already be accurate, and our split would then add bookkeeping for nothing. The case for our method rests on networks with many near-tied cheap cuts, or a mode the tilt under-weights. In those networks the empirical variance is computed only from observed modes and can be confidently wrong. We will settle this by measuring interval coverage over hundreds of repeated runs on instances with exact ground truth. If plain importance sampling covers at its nominal rate across the benchmark, the certificate is unnecessary and we will say so.

Why not just enumerate the cheap cuts and union-bound the rest? Deterministic cut enumeration gives a rigorous upper bound with no sampling, and on small, sparse grids it may be tight enough. The contrasting evidence is structural. Near-minimum cuts can number on the order of $n^{2\alpha}$, and Beyond the Quadratic Time Barrier for Network Unreliability shows that avoiding cut enumeration is what breaks the quadratic barrier. We will report the union bound alongside our certificate on every instance. Wherever it is within a factor of two of the truth, it is the better tool.

Why not just use an exact method? A Fast and Accurate ASP Counting Based Network Reliability Estimator reports that ProbLog solves only 164 of 710 instances within 10,000 seconds. Counting-Based Reliability Estimation for Power-Transmission Grids reports that S-RDA timed out on 8 of 10 city grids at 1,000 seconds. We use exact methods only where they finish, as ground truth.

Proposed Experiments

The ground-truth set is the subset of the 710 Gridkit and social networks from the RelNet-ASP benchmark that exact solvers finish. We add the ten municipal grids from RelNet, including Amarillo, Lakeland, and Eureka, and small $N \times N$ grids, where exact BDDs still fit in memory. On each network we sweep edge failure probabilities from the published settings down to $10^{-6}$. We use both uniform rates and heterogeneous rates drawn log-uniformly over two orders of magnitude, so that $U$ spans roughly $10^{-2}$ to $10^{-8}$.

For every method we record relative error of $\hat U$ against the exact value, wall-clock time, and failure-to-finish. For the sampling methods we also record empirical coverage of the reported 95% interval over 200 repetitions. To test scale, we run the 58-topology U.S. power-transmission suite from Network Reliability Estimation in Theory and Practice and larger rectangular grids, where exact answers are unavailable, and compare intervals and runtimes.

The decisive check targets the silent-miss scenario. We plant it by constructing grids with two disjoint cheap cuts. The tilt is tuned to favor one of them, and the planted cut carries a controlled share of $U$, from 1% to 50%. Plain importance sampling should report narrow intervals that exclude the truth when the planted cut is rarely sampled. Our certificate should widen exactly then, driven by the rise in singleton labels $N_1$.

A second check asks whether the Unseen fingerprint estimate of the number of failure modes above a probability floor matches exact enumeration on small grids. It is a secondary result, but it would be a new quantity for reliability analysis.

The project is falsified if, across the ground-truth set, plain importance sampling achieves nominal coverage and equal relative error at equal samples. It is also falsified if our certificate is so loose that it never excludes $U$ values an order of magnitude above the truth.