Skip to content

Module: denoise

File: src/spatial_graph_algorithms/denoise/__init__.py Status: Implemented — scorers, filters, one-call denoising, and ground-truth evaluation.

Purpose

Remove likely-false edges from a SpatialGraph without knowing the ground truth. The input is a noisy graph; the output is a SpatialGraph with suspect edges removed.

This module is the complement of the false-edge injection in simulate — the goal is to recover an edge set closer to the true proximity graph.

API

from spatial_graph_algorithms.denoise import denoise

sg_clean = denoise(sg_noisy, method="jaccard", fraction_to_remove=0.05)

The same entry point works for the local walk-support scorer:

sg_clean = denoise(
    sg_noisy,
    method="local_walk_support",
    fraction_to_remove=0.05,
    sample_fraction=0.25,
    walk_len=8,
    walks_per_edge=500,
    seed=42,
)

For a two-step workflow, score first and pass the same method name to the filterer. Score polarity is resolved from SCORE_POLARITY; method descriptions live in SCORING_METHODS, so user code should not track score direction or method meaning manually.

from spatial_graph_algorithms.denoise import EdgeFilterer, score_edges
from spatial_graph_algorithms.metrics import evaluate_denoising

scores = score_edges(sg_noisy, method="jaccard")
sg_clean = EdgeFilterer().by_fraction(
    sg_noisy, scores, fraction=0.10, method="jaccard"
)
report = evaluate_denoising(sg_clean, scores=scores, method="jaccard")

Scoring Methods

Each method returns a dict[tuple[int, int], float] keyed by canonical edge tuples (min(u, v), max(u, v)). Polarity (high or low score = suspect) is registered in SCORE_POLARITY and resolved automatically by all filterers.

Method Polarity How it works Cost
betweenness high = suspect Edge betweenness centrality via NetworkX O(VE) — slow on large graphs
jaccard low = suspect Jaccard neighbourhood overlap; unipartite only O(E·k)
square_bipartite low = suspect 4-cycle count; bipartite only O(E·k²)
community low = suspect Louvain intra-community consistency (igraph, n_runs=5) O(E log V) per run
walk_visit_expansion low = suspect Bridge-filtered walk visitation matrix followed by repeated matrix expansion O(n · walks · steps + n³ · expansions); allocates n×n matrix
local_walk_support low = suspect Endpoint random-walk support against local neighbourhoods; supports edge sampling O(sampled_edges * walks_per_edge * walk_len)

walk_visit_expansion is the older walk scorer: it launches walks from every node, discards walks that cannot show two edge-disjoint return paths, normalises the visitation matrix, then applies repeated matrix squaring to expand the signal.

local_walk_support estimates whether each edge is supported by random walks from its endpoints. It uses numba kernels for production-speed scoring. Lower scores are more suspicious; scores below 1.0 indicate weaker-than-expected local support. Use sample_size or sample_fraction for large graphs when you want a fast estimate or a partial filter, or omit both arguments to score all edges.

For diagnostics, call the result helper directly. This exposes per-edge scores, the scored_mask, runtime, and threshold summaries:

from spatial_graph_algorithms.denoise import denoise
from spatial_graph_algorithms.denoise.ES import local_walk_support_result

result = local_walk_support_result(
    sg_noisy.adjacency_matrix,
    sample_fraction=0.10,
    walk_len=10,
    walks_per_edge=500,
)
summary = result.threshold_summary(threshold=1.0)
fraction = summary["estimated_prune_fraction"]

sg_clean = denoise(
    sg_noisy,
    method="local_walk_support",
    fraction_to_remove=fraction,
    walk_len=10,
    walks_per_edge=500,
)

Filtering Strategies

All strategies accept the same (sg, scores, *, method) signature and return a new SpatialGraph with edge_metadata["is_removed"] set.

Strategy Description
by_fraction(fraction=0.05) Remove the worst fraction of scored edges
by_threshold(threshold=t) Remove edges above/below an explicit score value
by_percentile(percentile=5.0) Remove edges outside a percentile band
by_optimal_f1(sg, scores) Oracle: sweep thresholds to maximise F1 vs ground truth

by_optimal_f1 is a ground-truth oracle and only works on simulated graphs with edge_metadata["is_false"]. Use it to establish the upper bound for a scorer.

Implementation Notes

  • SpatialGraph is never mutated — all filterers return a new object via sg.replace().
  • Removed edges are recorded in edge_metadata["is_removed"]; the column is created from scratch if edge_metadata was None.
  • Score polarity lives in SCORE_POLARITY; consumers must not pass a direction flag.
  • jaccard raises ValueError on bipartite graphs; square_bipartite raises on unipartite.
  • Canonical method descriptions live in SCORING_METHODS; compatibility aliases map random_walk to walk_visit_expansion and edge_support to local_walk_support.
  • local_walk_support lives in ES.py; EdgeScorer.local_walk_support() returns a simple score dict, while spatial_graph_algorithms.denoise.ES.local_walk_support_result() exposes diagnostics such as threshold_summary().

File Structure

denoise/
├── __init__.py          — SCORE_POLARITY, EdgeScorer, EdgeFilterer, score_edges(), denoise()
└── ES.py                — local walk-support random-walk scoring and diagnostics