Changelog

Version 0.3.0 (2026-11-02)

This release adds hypergraph backbones, the remaining Backbone 3.0 features, the Pólya and GloSS filters, generalized null models and weight transforms, and a new temporal module for networks observed over time (conversions between snapshots, events, and spans, and collapsing them to a static weighted graph). The public API is now type-annotated and dispatches to NetworkX backends. It also fixes many correctness problems found in a full code review that checked every method against its paper, and checks p-values and backbones against R backbone 3.0.4 and netbone, which they now match (signed backbones included) except where the documented conventions differ. Several methods now return different results; see Changes in results below. Open work is tracked in the Roadmap and in GitHub issues.

Renamed (breaking)

• The package is now nx-backbone: install it with pip install nx-backbone and import it as import nx_backbone. The repository moved to brianckeegan/nx-backbone, and the documentation to https://www.brianckeegan.com/nx-backbone/. This is a clean break: there is no networkx_backbone alias, so import networkx_backbone fails once the old package is uninstalled. The old networkx-backbone project on PyPI is not updated.

• To migrate, replace the distribution and the imports:

  pip uninstall networkx-backbone
  pip install nx-backbone
  # then, in your code:
  #   import networkx_backbone as nb  ->  import nx_backbone as nb
  #   from networkx_backbone import ...  ->  from nx_backbone import ...
  

  Function names, arguments and edge attributes are unchanged by the rename. The BibTeX key that describe_backbone() writes is now keegan_nx_backbone.

Supported versions (breaking)

• Requires Python 3.12 or newer and NetworkX 3.4 or newer, matching NetworkX’s own support window. The optional dependency minimums now match NetworkX’s too: NumPy 2.2, SciPy 1.15, Matplotlib 3.10. A CI job tests these minimums exactly.

New features

Statistical and structural methods

• New gloss_filter(), the GloSS filter of Radicchi, Ramasco & Fortunato (2011). It tests each edge weight against a global null model that keeps the topology and draws weights from the network’s own weight distribution, conditioning on both endpoints’ degrees and strengths, and adds gloss_pvalue. The p-values of the paper’s Eq. (4) are computed exactly (integer weights) by direct convolution, stable at any degree; directed graphs use out- and in-degrees and strengths. Les Misérables: 3 edges at alpha = 0.05 (#43).

• New polya_filter(): the Pólya urn filter of Marcaccioli & Livan (2019), adding polya_pvalue. The null model is the beta-binomial urn of Eqs. (1)-(2), tested from both endpoints (out- and in-links for directed graphs). By default the reinforcement parameter a is the maximum-likelihood estimate of the paper’s Supplementary Note 5, stored in H.graph["polya_a"]; non-integer weights use the paper’s large-strength approximation, Eq. (6). Les Misérables: a = 0.340 and 12 edges at polya_pvalue < 0.05 (#42).

• disparity_filter(a=...) generalizes the uniform share null to a symmetric Dirichlet null with concentration 1/a, so a share is Beta(1/a, (k-1)/a) and the p-value is a regularized incomplete beta function. a=1 (the default) is the original filter, bit for bit and without SciPy; a="ml" fits a by maximum likelihood and stores it in H.graph["disparity_a"]. With the shares fixed, it is the large-strength limit of polya_filter’s beta-binomial null. Les Misérables: a = 0.525 and 19 edges at alpha = 0.05 (9 at a=1) (#55).

• New transform_weights() returns a copy of a graph with transformed weights, from a plain callable or any object with a scikit-learn style fit_transform (scikit-learn is not a dependency). It keeps each node’s neighbor order, rejects non-finite or constant output, warns when a transform reorders weights or creates ties, and records the transform for describe_backbone. The new user guide page Weights, Units, and Transforms has a table of which methods are invariant to rescaling and to increasing transforms, each entry checked by a test (#55).

• unit= on marginal_likelihood_filter, ecm_filter, and noise_corrected_filter sets the weight of one count; the models use weight / unit. The default unit=1 leaves results unchanged. The three scorers now warn (UserWarning) when weight / unit is not an integer count, naming how they coerce it: MLF rounds counts below 0.5 to 0, the ECM raises counts below 1.5 to 1 (#55).

• describe_backbone reports a of the disparity filter (with the fitted value for a="ml"), unit, and transforms recorded by transform_weights (#55).

• A calibration test harness (tests/test_calibration.py) simulates weights from the disparity filter’s null models and checks that endpoint p-values are uniform (#55).

• ecm_filter and noise_corrected_filter accept signed=True (#25).

• missing_as_zero=True on disparity_filter, lans_filter, marginal_likelihood_filter, ecm_filter, noise_corrected_filter and backbone_from_weighted (Backbone 3.0). Node pairs without an edge are tested as weight-0 edges and returned with weight 0, so a signed backbone can keep pairs that interact significantly less than expected. Degrees, strengths, and fitted multipliers still come from the existing edges only, as in the R package; each scorer’s Notes say how it scores a weight of 0. A RuntimeWarning is raised above one million added pairs (#26).

• glab_filter now supports directed graphs using the out- and in-involvement of Zhang et al. (2014), Section 2.3 (#12). On a symmetric DiGraph it gives the undirected p-values.

• doubly_stochastic_filter now also runs the second stage of Slater’s two-stage algorithm: a boolean ds_keep edge attribute flags the edges added, in descending ds_weight order, until each connected component is connected (tie levels added together, so the result does not depend on insertion order). Extract it with boolean_filter(H, "ds_keep"). ds_weight is unchanged by this stage (#44).

• doubly_stochastic_filter(smoothing=...) adds a pseudocount to every off-diagonal cell before Sinkhorn-Knopp, so the scaling converges on trees and sparse networks (netbone uses 1e-4). The default 0 leaves the matrix unchanged (#54).

• local_path_index(weight=...); a h_bridge attribute from h_backbone; statistically_validated_cores(max_groups=...).

• seed= on modularity_backbone, sparsify, and compare_graphs.

• lspar(convention="r") reproduces R backbone’s lspar. R excludes the endpoints from the Jaccard denominator, uses dense ranks, ignores edges with Jaccard 0, and keeps floor(d**s) edges per node with no minimum of one. The reference tests show that it matches R exactly on the karate club and Les Misérables at s = 0.3, 0.5 and 0.7 (karate at s = 0.3: 30 edges, against 54 with the default). The default, convention="satuluri", is unchanged (#59).

Bipartite and hypergraph methods

• Hypergraph module: the parameter-free MDL hypergraph backbone (Kirkley et al., 2026) with "edge", "node", and "auto" optimizers; statistically validated hypergraphs and cores (SVH/SVC); maximal hyperedges, order filtering, s-components, and intersection graphs.

• New local_mdl_hypergraph_backbone(): the local MDL hypergraph backbone of Kirkley et al. (2026, Appendix E). It finds the MDL backbone of each node’s neighborhood separately and combines them with the "union", "majority" (default), or "all" rule. HypergraphBackbone gains n_hyperedges, aggregation, local_backbones, and local_description_lengths (#24).

• Backbone 3.0 parity: multiple-testing correction (adjust_pvalues(), threshold_filter(mtc=...)), signed backbones (signed=True), and SDSM-EC edge constraints.

• backbone_from_projection(mtc=...); sdsm(pvalue_method=...); fdsm(burn_in=..., thin=...); bicm(tol=..., max_iter=...).

• backbone_from_projection(missing_as_zero=False) tests only the agent pairs that co-occur, as R backbone does by default. Pairs that never co-occur are not counted by mtc and are never retained, even as significantly weak with signed=True. The default, True, is unchanged and tests every pair, like R’s missing_as_zero = TRUE. The reference tests check both settings against R on Davis Southern Women, where they give different backbones in 13 of 48 settings at alpha = 0.06, 0.6 and 0.8; at 0.05 none differs (#59).

• hyper_projection(newman=True) / projection="newman" gives Newman’s \(1/(d(z)-1)\) weighting, equal to nx.bipartite.collaboration_weighted_projected_graph. The default hyperbolic weight, \(1/d(z)\), is unchanged and follows Coscia & Rossi (2019). Projection citations are corrected to Coscia & Rossi (2019, arXiv:1906.09081) (#13).

Inputs and interoperability

• New to_graph() converts a NumPy or SciPy sparse adjacency matrix (with nodelist and directed) or a pandas edge-list DataFrame (source/target/weight columns) to a graph with NetworkX’s own converters, refusing an asymmetric matrix for an undirected graph and duplicate edge-list rows. backbone, backbone_from_weighted and backbone_from_unweighted accept these inputs directly and give the same backbone as the graph path; nx.to_pandas_edgelist returns the scored edges as a DataFrame. The individual scorers keep graph-only signatures (#20).

• Bipartite functions accept NumPy, SciPy sparse, or pandas incidence matrices with agent_labels/artifact_labels, and agent_nodes is optional (#20, bipartite part).

• hypergraph_io: hypergraph_to_bipartite, the HIF interchange format, and adapters for xgi, HyperNetX, HypergraphX, and HAT.

• The hypergraph adapters carry weights: to_xgi, to_hypernetx, to_hypergraphx, and to_hat take weights=, and the from_* functions take return_weights=. New extras [xgi], [hypernetx], [hypergraphx], [hat], and [interop] (all four) install the libraries; supported versions are in Installation (#15). Testing against the real libraries found and fixed these adapter bugs:

  • to_xgi failed on tuple node labels (xgi read a two-node hyperedge as a (members, edge_id) pair).

  • to_hat silently dropped repeated hyperedges (HAT’s default compress=True), and from_hat returned row indices instead of node labels. Labels now round-trip through H.nodes["Names"].

  • to_hypergraphx silently merged repeated hyperedges. It still merges them, since HypergraphX has no multi-edges, but now sums their weights, and it explains the TypeError raised for mixed-type node labels.

  • The HAT and HypergraphX HIF readers raised KeyError on write_hif output, which omitted the nodes and edges lists. write_hif now always writes both.

• multigraph_to_weighted(aggregate=...), which can sum, average, or take the max/min of parallel-edge weights.

• New module nx_backbone.temporal (first part of #67): temporal networks as snapshots (a dict or list of graphs), events (a multigraph with a time per edge), or spans (start/end, read as the half-open interval [start, end)). temporal_form() detects the form; snapshots_from_events(), snapshots_from_spans(), events_from_snapshots(), spans_from_snapshots(), events_from_spans(), spans_from_events() and convert_temporal() convert between them, binning with freq=/origin= and combining weights with multigraph_to_weighted(aggregate=...). Snapshots to events or spans and back is lossless (empty snapshots, isolated nodes, and node, edge and graph attributes are kept in M.graph["temporal"]). Numeric times and datetime times with timedelta steps need only NetworkX; frequency strings such as "1D" import pandas lazily. See Temporal networks: formats and conversions.

• flatten_temporal() collapses snapshots, events or spans into one static weighted graph for the static backbone methods: one edge per node pair with the combined weight (aggregate= sum, count, mean, max or min, or "duration" for spans, the length of the union of a pair’s spans), n_obs, first and last (and active_time for spans), optionally restricted to a half-open window=(t0, t1).

• from_event_table() and to_event_table() read and write pandas event (or span) tables, keeping duplicate rows as separate events (#70, pandas part).

• Temporal backbone scores, descriptive (no p-values), for any of the three forms (events and spans are binned with freq=). Each returns one static graph, the union of the observed edges with score attributes and H.graph["temporal"] (method, input form, step times, n_steps, freq, origin, parameters), so threshold_filter and the other filters apply. They count only an edge’s eligible steps, those in which both endpoints are present: an absent edge is an observed zero there and unknown elsewhere, so a node that joins late is not penalized (#67).

  • observation_fraction(): obs_fraction, n_obs, n_eligible, first_obs, last_obs; weight= and min_weight= count only heavier observations (#68).

  • persistence(): max_run, mean_run, n_runs and persistence, the share of observed steps whose next eligible step is also observed; ineligible="break" lets unknown steps end a run (#68).

  • backbone_stability(): runs any static method (disparity_filter, lans_filter, …) on every step with the same cut and adds stability (n_kept / n_eligible), n_kept, n_eligible, first_kept, last_kept. The cut’s attribute comes from the new describe.SCORE_KEYS registry (#69).

  • weight_trend() (needs numpy): weight_mean, weight_std, weight_cv, weight_slope per step (and weight_slope_time per unit of numeric time), with an optional, descriptive slope p-value (SciPy) (#69).

  All but weight_trend work with NetworkX alone. describe_backbone describes them, including the number of steps and the binning. New tutorial: Temporal Backbones; Temporal backbones: presence and eligible steps explains the eligible steps.

• New edge_persistence_hmm() (needs numpy): a two-state hidden Markov model of edge activity. Each edge switches between an inactive and an active state (transition probabilities a01 and a10) and is observed with a false-positive rate alpha and a miss rate beta, all shared by the edges and fitted by Baum-Welch (EM) pooled over the edges, or fixed with params=. The observations are, in each eligible step, the edge’s presence (observe="presence"), whether a static method keeps it with backbone_stability’s per-step cut (observe="keep"), or its p-value (observe="pvalue": uniform when inactive, Beta(a, 1) when active, a modeling choice); ineligible steps carry no evidence. Exact forward-backward and Viterbi give per-edge hmm_posterior (a dict over the eligible steps), hmm_active_fraction, hmm_score, hmm_n_active and hmm_keep (active in at least min_steps steps); the fitted model is in H.graph["temporal"]["hmm"]. alpha < 1 - beta is imposed by relabeling the states. hmm_score is a persistence-smoothed membership score, not a p-value. The temporal tutorial compares it with persistence (#73).

• edge_persistence_hmm records two diagnostics in H.graph["temporal"]["hmm"]: n_active_steps, the number of eligible steps the most likely state paths mark active, and unobserved_active_share, the share of them in which the edge was not observed. Because the parameters are pooled over the edges, a mix of persistent and randomly flickering edges can be fitted with a large miss rate and slow switching, which gives the flickering edges more active steps than the persistent ones. A large share flags this. The Notes explain the trade-off and when to fix beta with params=. A Beta prior on alpha and beta (MAP-EM) was evaluated on planted-truth simulations and not adopted. No fitted values change (#112).

• New kalman_backbone() (needs numpy and SciPy), a novel adaptation of the Kalman filter and Rauch-Tung-Striebel smoother to backboning (#72). It runs a static significance test (disparity_filter or glab_filter; discrete tests such as noise_corrected_filter with discrete="raw") on every step, scoring eligible absent edges as weight 0 with missing_as_zero=True, turns the p-values into probit scores, and smooths each edge’s series with a local-level model (mode="smoother" or the online "filter"; unknown steps and unequal spacing are handled exactly). Per-step p-values use the exact null distribution of the smoothed level; the edge-level kalman_pvalue tests the largest smoothed z-score over the steps against a null simulated once per missingness pattern (n_sim=, seed=). The process variance comes from q=, half_life= (in steps) or a pooled maximum likelihood fit, recorded in H.graph["temporal"]["kalman"]. Each edge also gets kalman_score, kalman_n_obs and the per-step dicts kalman_pvalues, kalman_levels and kalman_innovations; kalman_snapshots() expands them into per-step graphs. Methods with discrete p-values (LANS, ECM, the marginal likelihood filter, Pólya, GloSS) raise unless discrete="raw" (valid but conservative), because none reports the P(X > x) that a mid-p transform needs. The disparity filter and GLAB give an edge the smaller of two endpoint p-values, which smoothing would turn into many false positives; the default sidak=True corrects for that, which keeps their smoothed tests valid but conservative. The docstring documents the risks: temporal leakage, autocorrelated confounders, and multiple testing over edges and steps.

Reporting and documentation

• New describe_backbone(): methods-section text and citations for a backbone, in text, Markdown, or BibTeX; the counterpart of Backbone 3.0’s narrative (#23). It is backed by one method-to-BibTeX registry that covers every public scorer, and a test enforces that coverage.

• New tutorial, “Validating a backbone”: multiple-testing correction, compare_backbones, consensus, signed backbones, and reporting (#27).

• New narrative tutorial, “From a hairball to a backbone, end to end”, the “Start here” entry point linked from the home page, the quick start, the tutorials index, and the statistical, filters, measures and describe API pages. A worked case study on Les Misérables and a seeded, simulated collaboration network with planted departments: why a global weight cut fails, scoring versus filtering and the disparity filter’s null model for one node, choosing alpha with Bonferroni and Benjamini-Hochberg corrections, four backbones compared in small multiples with compare_backbones, robustness to alpha and to the method (consensus_backbone), a signed backbone, and describe_backbone output. It is a Sphinx-Gallery example, so its nine figures (light and dark variants, in the shared figure style) and every number are computed when the docs are built, and hidden checks fail the build if a claim in the text stops holding. The tutorials index is reorganized into “Start here”, “By network type”, and “Going further” (#89, #96).

• New narrative tutorial, “Structural and proximity backbones”, executed in the example gallery with eight figures: what spanning trees, the PMFG, the metric and ultrametric backbones, salience, the h-backbone and the doubly stochastic filter guarantee (checked at build time) against the disparity filter; weights as strengths or distances; ties and which methods still depend on input order; proximity scores and sparsifiers for unweighted graphs, including lspar(convention="r"); and Sinkhorn-Knopp convergence with smoothing= (#91).

• Added CITATION.cff.

Changes in results (bug fixes)

The Les Misérables counts below are edges kept at the documented threshold. Davis counts are significant woman-woman pairs at alpha = 0.05.

• doubly_stochastic_filter: when Sinkhorn-Knopp does not converge, ds_weight depended on the orientation in which each edge was stored, and so on node insertion order (by up to 0.86 on Les Misérables). It is now the symmetric scaling \(\sqrt{D_{uv} D_{vu}}\), which equals the doubly stochastic limit whenever the iteration converges. On Les Misérables (no convergence) ds_keep now keeps 187 of 254 edges instead of 220 (#54).

• strongest_n_ties keeps ties together: each node selects every edge whose weight is at least its n-th largest weight, so a node can select more than n edges. Before, ties at the cutoff were broken by adjacency order, so G and G.copy() could give different backbones (on Les Misérables at n=2 they differed in 23 edges). The result now depends only on the weights, as for lspar/local_degree; on an unweighted graph every edge is kept. Les Misérables: 69 -> 108 edges (n=1), 113 -> 146 (n=2), 146 -> 165 (n=3) (#60).

• global_sparsification and edge_betweenness_filter break ties by the sorted string form of an undirected edge’s endpoints, so the result no longer depends on how each edge is stored (which follows node insertion order). Edge counts are unchanged; on Les Misérables at s=0.5, 5 (global sparsification) and 6 (edge betweenness) of the 127 kept edges swap for other edges tied with them (#60).

• noise_corrected_filter now implements the published Bayesian noise-corrected backbone (Coscia & Neffke, 2017). Its scores and standard deviations match the authors’ reference code exactly. nc_score is the transformed lift, in (-1, 1), with new nc_sdev and nc_pvalue attributes. Keep edges with nc_score > 1.64 * nc_sdev or nc_pvalue < 0.05; thresholding nc_score at 2.0 now keeps nothing. The old z-score is available as method="zscore". Les Misérables: 98 -> 195 edges (#9); see the next entry for the p-value.

• noise_corrected_filter: nc_pvalue is now, by default, the exact binomial tail \(P(X \geq n_{ij})\) of the method’s null model, \(X \sim B(n_{..}, n_{i.} n_{.j} / n_{..}^2)\) (the p-value of the paper’s footnote 2), computed with the regularized incomplete beta function so that non-integer counts are not rounded. The previous nc_pvalue, the normal tail of nc_score / nc_sdev (the paper’s delta rule read as a z-test), is pvalue_method="delta". The delta rule divides the score by a standard deviation evaluated at the observed weight through a transform that flattens as the lift grows, so the ratio has no bound: on gnm_random_graph(30, 40, seed=1) with unit weights all 40 edges had p ≈ 1e-65 (median) and 4 are now below 0.05 (median 0.12). On simulated graphs from the model’s own null (2,000 unit interactions among 50 nodes, 20 seeds), the share of nc_pvalue < 0.05 was 0.24 (undirected) and 0.34 (directed) before and is 0.047 and 0.051 now. nc_score and nc_sdev are unchanged. On a directed graph with integer weights the default p-values equal marginal_likelihood_filter’s; on Les Misérables and the karate club the two keep the same edges. kalman_backbone now treats the default noise-corrected p-values as discrete (discrete="raw" is needed). Les Misérables: 195 -> 126 edges (unit=0.1: 222 -> 215); karate club: 68 -> 39 (#105).

• multiple_linkage_analysis now fits each node’s sorted weights to ideal dominance distributions by default (method="dominance"; Van Nuffel, 2007, after Weaver, 1954) and adds mla_rank. The previous LANS threshold is method="lans". The fit is the coefficient of determination over the zero-padded profile, as restated by Van Nuffel, Derudder & Witlox (2010), whose Table 1 the tests reproduce; a new deviation= keyword also offers "profile" (whole-profile squared deviation, the measure used earlier in this development cycle) and "weaver" (Weaver’s variance over the candidate links). Les Misérables: 109 -> 205 edges ("profile": 223, "weaver": 253) (#10).

• sparsify(umst=True) now adds the union of all minimum spanning trees (Hamann et al., 2016) instead of one arbitrary spanning forest, so tied scores no longer make the result depend on node order (#32). The union is added whenever umst=True, not only when filtering split a component.

• ecm_filter: the solver never converged and every p-value was about 0, so every edge was kept (254 of 254). It now fits the ECM by maximum likelihood and uses the correct geometric tail; it keeps 72 edges and warns if the fit does not converge.

• marginal_likelihood_filter: now uses Dianati’s null, \(B(T, s_is_j/2T^2)\). The old formula depended on the order nodes were added. Les Misérables: 70 -> 126 edges.

• glab_filter: now uses per-node shortest-path involvement and \((1-I_{ij})^{(k_i-1)^c}\) (Zhang et al., 2014) instead of global edge betweenness. Les Misérables: 5 -> 56 edges.

• disparity_filter: the p-value is now \((1 - p_{ij})^{k_i - 1}\) (Serrano et al., 2009). Versions 0.1.0 and 0.2.0 computed \(1 - (k_i - 1)(1 - p_{ij})^{k_i - 2}\), the integrand of the paper’s formula in place of its integral, so almost every edge looked significant. Les Misérables: 247 -> 9 edges. On directed graphs it also tests the target’s incoming links.

• lans_filter on directed graphs also tests the target’s incoming links (#11, contributed by @bfs2021 in #34).

• lans_filter(signed=True): the lower tail is now #{weights < w} / k, the mirror image of the upper tail #{weights > w} / k, as in R backbone 3.0.4. It was the empirical CDF #{weights <= w} / k, which counts the link itself and is never below 1 / k, so a link could be significantly weak only at a node of degree above 40 (at alpha = 0.05). The two-sided p-values now equal R’s. The one-tailed lans_pvalue is unchanged. Les Misérables signed backbone at alpha = 0.05: 108 positive / 0 negative -> 108 positive / 86 negative (R: 68 / 126, the difference being 40 ties, whose sign the next entry matches); karate: 45 / 0 -> 45 / 25 (#58).

• Signed backbones sign an edge whose upper and lower tail p-values are exactly equal -1, as R backbone 3.0.4 does (its .retain takes upper < lower as positive, in both its weighted and bipartite models); it was +1. The rule is the same for every signed scorer (disparity_filter, marginal_likelihood_filter, lans_filter, ecm_filter, noise_corrected_filter, sdsm, fdsm, fixedfill, fixedrow, fixedcol and the backbone_from_* wrappers). Two-sided p-values do not change. Only LANS ties are significant on the reference data, so only LANS backbones change, and its signed backbones now equal R’s for every mtc: Les Misérables at alpha = 0.05, 108 positive / 86 negative -> 68 / 126; karate, 45 / 25 -> 30 / 40. In every other model a tie needs both tails of at least 0.5 (two-sided p-value 1), so only the sign attribute of untestable or non-significant edges changes, for example ECM self-loops and, under the disparity filter, edges between two degree-1 nodes. Ties are now equal by construction rather than by floating-point rounding: noise_corrected_filter signs by the statistic, so only a score of exactly 0 is a tie, and fixedrow makes the two tails of a symmetric hypergeometric null observed at its mean exactly equal and no longer depends on the order of the two agents. Davis fixedrow: all 7 such pairs are now -1 (6 were +1) (#59).

• bicm/sdsm: the BiCM is now actually fitted rather than approximated with Chung-Lu, and p-values use exact Poisson-binomial tails (or RNA). SDSM-EC refits on the free cells. Davis: 3 -> 0 pairs.

• sdsm (and backbone_from_projection(method="sdsm")): pvalue_method="auto" now computes exact Poisson-binomial tails whenever that is affordable, instead of switching to the refined normal approximation (RNA) above 200 artifacts. The RNA’s far upper tail is anti-conservative when a pair’s expected co-occurrence is small, as on sparse data. On a 2000 x 500 pure-noise matrix of density 0.01, the smallest p-value goes from 5.7e-37 to 3.9e-05 and Benjamini-Hochberg at 0.05 keeps 1,498 -> 0 pairs. Under SDSM’s own null (600 x 300, density 0.01) the share of p-values below 1e-4 goes from 7.2e-04 to 1.1e-06. When exact tails would be too costly, "auto" keeps them for the pairs of degree classes with the smallest expected co-occurrence, uses the RNA for the rest and warns. pvalue_method="rna" is unchanged and still matches R backbone. Davis and other inputs with at most 200 artifacts were already exact; their p-values change only in the last bits (#108).

• fdsm: the null now preserves degrees (a curveball chain; previously 197 of 200 samples broke the margins), and p-values are (count + 1) / (trials + 1). Davis: about 10 -> 5 pairs.

• fixedfill and fixedcol use their exact null distributions.

• backbone_from_projection and backbone() now threshold sdsm and fdsm at alpha, as they already did for the other models.

• lspar/sparsify and local_degree: each node ranks its own edges (Satuluri et al., 2011; Lindner et al., 2015), and ties are kept together. Les Misérables: 136 -> 174 (LSpar) and 135 -> 91 (local degree).

• h_backbone follows Zhang et al. (2018): unweighted betweenness on the full graph, normalized by N. When h = 0 no edges are kept. Les Misérables: 22 -> 18.

• high_salience_skeleton splits credit among tied shortest paths, so saliences sum to n - 1.

• metric_backbone uses a relative tolerance; ultrametric_backbone no longer crashes on self-loops.

• Proximity indices exclude self-loops from neighborhoods and use out-degree for directed graphs.

• doubly_stochastic_filter warns when Sinkhorn-Knopp does not converge and no longer accepts a loose convergence check.

• reachability counts directed reachability correctly; compare_backbones forwards weight to every measure that accepts it.

• adjust_pvalues keeps NaN as NaN and excludes it from the number of tests (as R’s p.adjust does), instead of making it significant.

API conventions (NetworkX compatibility)

• Every scorer raises NetworkXNotImplemented for multigraphs (use multigraph_to_weighted() first), and NetworkXError for missing, non-positive, NaN, or infinite weights.

• Bipartite functions accept generators for agent_nodes, reject agent sets that are not one side of the bipartition, and raise AmbiguousSolution when the partition cannot be inferred.

• Filters keep graph, node, and edge attributes and multigraph keys. fraction_filter ignores unscored elements, and consensus_backbone works with node labels of mixed types and returns edges in a deterministic order.

• Functions that used a hardcoded seed=42 now default to seed=None, following NetworkX. Pass a seed for reproducible results.

• The graph-in, graph-out functions (statistical, structural, proximity, hybrid, and unweighted methods, multigraph_to_weighted, and the threshold, fraction, and boolean filters) are dispatchable through nx._dispatchable: they accept backend= and follow nx.config.backend_priority, under dispatch names prefixed with backbone_ so they cannot clash with NetworkX’s own (two would have: adamic_adar_index and resource_allocation_index). A new Backends guide shows how to use backends and records nx-parallel timings for the shortest-path methods. Bipartite, hypergraph, measure, and conversion functions are not dispatchable, since they take matrices or hyperedge lists or return numbers. The RuntimeWarning of ecm_filter and polya_filter now points at the caller’s line (#19).

• SDSM-EC constraints that contradict the data (a required pair that is not an edge of B, a prohibited pair that is) are now ignored with one RuntimeWarning per call, pointing at the caller’s line, that counts and lists them, instead of raising NetworkXError. This applies to sdsm, backbone_from_projection and backbone. Pairs naming nodes that are not an (agent, artifact) pair of B still raise, and so does a pair listed as both required and prohibited. When no constraint remains (all ignored, or empty lists), the p-values equal those of the unconstrained SDSM exactly. R backbone 3.0.4 codes constraints as cell values of the incidence matrix, so a constraint there replaces the observed value instead.

Performance

• Bipartite projections and null models use sparse incidence matrices and score agent pairs in row blocks, and backbone_from_projection builds edges only for significant pairs. On a 3000x800 projection this cuts run time from 40-76 s to under 2 s and peak memory from 2.2 GB to 0.23 GB; results are unchanged (#30).

• Exact SDSM tails truncate each Poisson-binomial convolution at the largest co-occurrence that can be observed (the smaller agent degree, or the observed count with edge constraints), which keeps every probability exact: the mass above the cut is accumulated as it crosses it. Building the tail tables is 8-60x faster (2000 x 2000 at density 0.01: 5.3 s -> 0.18 s; 5000 x 5000 at 0.002: 19.7 s -> 0.35 s) (#108).

• Vectorized sdsm/fixed*/fdsm (sdsm on 400x300: 6.4 s -> 0.36 s); MDL "node" optimizer with a lazy heap (m = 2000: 8.3 s -> 0.47 s); vectorized SVC p-values.

• ecm_filter fits the ECM over classes of nodes with the same degree and strength (out- and in-degree and strength for directed graphs), which is exact. Pair sums are computed in chunks, and the dense Newton polish is replaced by damped Newton steps (Newton-CG for large problems). On a 2,000-node Barabási-Albert graph the fit drops from about 90 s and 600 MB to under 2 s and 50 MB; 20,000 nodes take about 16 s and 300 MB (about 90 s for a directed version, which has 10,660 classes). The fit now also converges on directed graphs where the old solver stopped short, and nodes whose links all have weight 1 get the exact \(y_i = 0\). P-values on Les Misérables agree with the old solver to about 1e-8 (#21).

Infrastructure and documentation

• New narrative tutorial, “Hypergraph backbones: keeping the groups that matter”, a Sphinx-Gallery example executed at build time on the Davis Southern Women events and a synthetic meeting log. It covers what the pairwise projection loses, the MDL backbone’s description-length trade-off and its optimizers, the local MDL aggregation rules, the statistically validated hypergraphs and cores, the structural helpers, and a HIF round trip, with six figures in light and dark variants. It is listed under “By network type” in the tutorials index and linked from the hypergraph API page and the how-to tutorial (#93, #96).

• A shared figure style for the docs, docs/_figures/style.py (docs only, not library API): color tokens checked with a palette validator against the docs theme’s light and dark backgrounds (kept and removed edges, positive and negative edges, a one-hue ramp for scores, eight categorical colors in a fixed order), matplotlib defaults, a cached layout per dataset, a helper that draws a backbone over its original graph with a legend and the counts, and helpers that save light and dark variants and write the reST that shows the one matching the reader’s theme. Sphinx-Gallery examples start from this style (#88, #96).

• Two narrative guides, executed when the docs are built (#95): Coming from R backbone or netbone maps each R backbone 3.0 and netbone function to nx-backbone, checks the four convention switches against the R fixtures, and reproduces R’s fixed row backbone of the Davis Southern Women p-value by p-value; Scaling up to large networks covers sparse inputs, cost classes with run times measured at build time, the ECM solver’s degree-strength classes, and the committed nx-parallel timings.

• The method gallery on the API pages is regenerated and redesigned. The images committed for 0.2.0 showed pre-fix results (the ECM image kept nearly every edge, where the fixed ECM keeps 72 of 254). The gallery is now generated on every docs build by scripts/generate_visualizations.py into the gitignored docs/_gallery/; no gallery image is committed any more, and the build fails when a public method has no figure. Each figure draws the backbone over its original graph (kept edges in blue, removed edges faint), in one layout per dataset, under the method’s own name, with a legend, light and dark variants, and the edges and nodes kept in the caption and alt text. New figures cover polya_filter, gloss_filter, a signed backbone (fixedrow(signed=True), negative edges dashed), the MDL hypergraph backbones on Davis Southern Women as a hypergraph, and the temporal scores (including edge_persistence_hmm) on the temporal tutorial’s snapshots. The graph comparison example now draws the statistical and structural methods as small multiples, with a bar chart of the edges each keeps. The “Generate Visualization Gallery” workflow became a strict docs build on pull requests, and the deploy workflow no longer runs a separate gallery step. Generating the gallery takes about 15 s; with the lighter comparison example, a full docs build takes about 35 s instead of about 27 s (#88).

• New narrative tutorial, Statistical null models side by side: the seven statistical scorers on Les Misérables, with figures of p-value against weight, backbone overlap (checked against the hierarchy reported by Yassin et al., 2025), the KS distances of each backbone, the disparity filter’s a=, the count models’ unit=, transform_weights, and signed backbones with the R tie convention. It is executed at build time (#90, #96).

• A narrative tutorial, Bipartite projections and their backbones, executed when the docs are built: two-mode data and why the raw projection overstates ties, the five projection weights, the five null models compared against the FDSM, the FDSM p-value floor and multiple testing, signed backbones, SDSM-EC constraints (including contradictory ones), a check against R backbone with missing_as_zero, and sparse incidence input, with seven figures in light and dark variants. It is listed under “By network type” in the tutorials index (#92, #96).

• New narrative tutorial, Temporal backbones, from snapshots to smoothing: snapshots, events and spans and binning with freq=; flatten_temporal by count and by duration, and what a static backbone of the flattened graph misses; observation fraction, persistence and backbone stability on a persistent block among random flicker; the Kalman backbone on a planted rising block (smoother against filter, the edge-level test, the Šidák correction and temporal leakage); the persistence HMM’s posterior against raw presence; and a table for choosing among them. Five figures, executed at build time; it is listed under “By network type” in the tutorials index (#94, #96).

• The structural and proximity and the hypergraph tutorials no longer embed their figures in the page as base64 data: the figures are written at build time to the gitignored docs/_static/example_figures/ and linked, and load lazily, so a reader fetches only the variant (light or dark) on screen. The three dense network drawings of the structural tutorial are PNG; the charts stay SVG. The pages shrink from 3.9 MB and 1.5 MB of HTML to 0.4 MB and 0.2 MB, both tutorials get a real gallery thumbnail, and the structural tutorial’s captions, which the theme hid in light mode, show again (#96).

• The public API and the HypergraphBackbone/ValidatedHypergraph result classes have type annotations, and the package ships a py.typed marker (PEP 561), so mypy and pyright check calls into it. Functions whose return type depends on a flag (bicm(return_labels=...), read_hif/from_* with return_weights=..., compare_graphs(return_diff=...)) have overloads. The decorators (not_implemented_for, py_random_state, the backend dispatcher) are typed so they keep each signature, and dispatchable functions also accept backend=.... NumPy, SciPy, pandas, and Matplotlib types are imported only for type checking, so the core package still needs only NetworkX at runtime. A new CI job runs non-strict mypy with the types-networkx stubs; the new typing extra pins both. The API pages keep plain signatures (autodoc_typehints = "none"); the docstrings still give the types. No behavior changes (#18).

• The roadmap page opens with a “Roadmap at a glance” section: a stacked bar chart of item status per section, a network map of sections and their items colored by status, and the same counts as a table. scripts/roadmap_figures.py generates them from docs/roadmap.rst on every docs build, in light and dark variants, so they always match the page (#56).

• Docstrings are validated by the Sphinx build and by a new numpydoc lint CI step. The checks are GL06, GL08, SS01, PR01, PR02, PR03, RT01, and EX01, configured in [tool.numpydoc_validation]. numpydoc alone now renders docstrings; sphinx.ext.napoleon was removed (#17).

• The Les Misérables benchmark table is computed at docs build time from benchmarks/benchmarks/les_miserables.py, the same definitions whose counts the tests pin (#28).

• An asv benchmark suite in benchmarks/ covers the statistical, bipartite, MDL and SVH/SVC hypergraph, and shortest-path methods. It comes with a benchmark extra and a manually triggered Benchmarks workflow (#22).

• Cross-implementation reference tests (tests/test_reference_implementations.py) compare p-values and backbones with R backbone 3.0.4 and netbone 0.2.3 on Les Misérables, the karate club, and Davis Southern Women, using JSON fixtures written by scripts/make_reference_fixtures.R and scripts/make_netbone_fixtures.py (no R or netbone needed to run them). Disparity, MLF, LANS (one-tailed), BiCM, SDSM (RNA), fixed fill, fixed row, p.adjust, local degree, metric and ultrametric backbones match exactly. SDSM on Davis finds no significant pair at alpha = 0.05 in R either (smallest p-value 0.097 in R, 0.088 here with the exact tail), and FDSM finds the same 5 pairs. Documented differences: signed disparity and LANS lower tails, lspar conventions, global threshold strictness, mtc counting non-co-occurring pairs, R’s logistic-regression SDSM-EC fit, and netbone’s noise-corrected total, GLAB and salience tie handling, h-bridge, and MLA. R’s fdsm default draws samples with too few curveball trades on Davis, which biases its p-values upward by up to about 0.03 (#14).

• The multiple_linkage_analysis documentation no longer says method="lans" reproduces netbone: netbone 0.2.3’s mlam is a correlation-based fit that neither method reproduces (#14).

• A decision note (docs/design/reference-conventions.md) covers the 14 documented convention differences from R backbone and netbone. It measures each on Les Misérables, the karate club, and Davis Southern Women and recommends whether to keep ours, match the reference, or add an option. The R fixture gains lspar backbones for Les Misérables and Davis backbones at alphas where the mtc scope matters; every existing fixture value is unchanged. The multiple_linkage_analysis Notes now compare netbone’s 134 Les Misérables links with the default’s 205 (223 was the deviation="profile" count), and the global_threshold_filter Notes show how to reproduce R’s strict threshold (#59).

• CI on every push and pull request: ruff lint and format checks, tests and doctests on Python 3.12-3.14, a job pinned to the oldest supported versions, and a NetworkX-only job that checks the optional dependencies stay optional. Test coverage is 97%.

• A CI job (and a step in the oldest-versions job) runs the dispatch tests (tests/test_dispatch.py and tests/test_api_contract.py, which call every dispatchable function) under NetworkX’s dispatch test harness, NETWORKX_TEST_BACKEND=nx_loopback, which checks that every dispatchable call gives the same result through a backend as without one (#19). The whole suite also passes under the harness.

• The test suite was condensed from 1,732 to 804 collected tests (with doctests) at unchanged line and branch coverage: sweeps over a registry (every method, style, scorer or dispatchable function) are one test per axis whose failure message names every failing case, and duplicated tests were merged. Doctests and coverage run on one Python version in CI.

• An “Interop” workflow (pull requests, weekly, and on demand) installs .[interop,test] and runs pytest -m interop: round trips of hyperedges, weights, and node labels through the real xgi, HyperNetX, HypergraphX, and HAT, and HIF exchange with each library’s own reader and writer. It is a separate, non-required workflow, so an upstream release cannot block unrelated pull requests (#15).

• A coverage evaluation of the 15 methods compared by Yassin et al. (2025) (docs/design/yassin-2025-coverage.md). The package covered 13 of them; the two it lacked, the Pólya urn and GloSS filters, were then added (#42, #43). The evaluation also notes where the covered methods behave differently from netbone (#29).

• The PyPI workflow builds from the release tag with its full history and fails unless the wheel and sdist carry the tag’s version; manual runs no longer upload (they had published 0.2.0.post1.dev9). The conda recipe takes its version from the tag instead of a hardcoded 0.1.0. The Development Status classifier is now 4 - Beta (#16).

• New Roadmap; full numpydoc sections for the bipartite, hypergraph, and structural APIs; corrected citations (Van Nuffel, 2007; Lü et al., 2009; Lindner et al., 2015); the docs version is taken from the package metadata.

Version 0.2.0 (2026-02-14)

Tagged v0.2.0 in git. PyPI has 0.1.0 and a development build (0.2.0.post1.dev9), but no 0.2.0 release: pyproject.toml at the tag still set version = "0.1.0", so the release workflow built 0.1.0 again, and the development build came from a later manual run on main.

• New visualization module: graph_difference(), compare_graphs(), and save_graph_comparison() draw an original graph and its backbone side by side.

• A Sphinx-Gallery visual comparison gallery and score-then-filter examples in the documentation.

Version 0.1.0 (Initial Release)

First public release of networkx-backbone.

Features:

• 47 backbone extraction functions across 8 modules

• Statistical methods: disparity filter, noise-corrected filter, marginal likelihood filter, ECM filter, LANS filter

• Structural methods: global threshold, strongest N ties, high salience skeleton, metric backbone, ultrametric backbone, doubly stochastic filter, h-backbone, modularity backbone, planar maximally filtered graph, maximum spanning tree backbone

• Proximity methods: neighborhood overlap, Jaccard, Dice, cosine, hub promoted/depressed indices, LHN local index, preferential attachment, Adamic-Adar, resource allocation, graph distance proximity, local path index

• Hybrid methods: GLAB filter

• Bipartite methods: SDSM, FDSM

• Unweighted sparsification: sparsify, LSpar, local degree

• Filtering utilities: threshold, fraction, boolean, consensus backbone

• Evaluation measures: node/edge/weight fractions, reachability, KS degree, KS weight, compare backbones