Graph neighbor sampling and time-safe evaluation

Last updated: 7 Oct 20265 min read

tutorial

Sampling controls the number of edges a graph batch touches, but the sampled neighborhood must still obey the prediction timestamp and label boundary.

Start with seed nodes

A node-classification batch contains seed services whose labels contribute to the loss. To compute a two-layer message-passing result, the loader needs neighbors of seeds and neighbors of those neighbors; these context nodes are not automatically extra labeled examples. Record seed IDs separately from sampled node IDs, and mask the loss to seeds. If a context node also appears in validation, that is not necessarily leakage for a transductive fixed graph; using its held-out label or post-cutoff features is leakage. State the evaluation setting.

Bound the receptive field

With at most k neighbors at each of L hops, a seed can touch up to a quantity proportional to k raised to L nodes before deduplication. High-degree hubs make full-neighborhood training expensive. Sampling caps work but adds variance: two draws around the same service can differ. Fix a seed for parity tests and keep fanout, hop count and edge direction with the model artifact. If the task depends on one rare upstream service, uniform sampling may omit exactly the relation that matters. Compare recall by degree and relation type.

Enforce edge and feature cutoff

For an incident scored at minute 47, exclude a dependency first observed at minute 53 and telemetry emitted after minute 47, even if the graph snapshot is built days later. A stored row timestamp is only useful if it represents when the value became observable, not when it was eventually backfilled. A feature computed over a centered window can include the future without an obvious future timestamp on the row. Edge direction remains a separate contract.

Choose the split deliberately

A temporal split tests future incidents on known services. A service-holdout split tests transfer to services absent from training, and may need a different identity encoding. A random node split on one static graph usually answers a narrower transductive question. Split by incident identity where one incident labels many related service nodes; otherwise near-duplicate states can land in both train and test. Keep a simple local-feature baseline under the same split. Leakage boundaries apply to graph context too.

Test sampled versus full-neighborhood inference

For a small held-out graph, compare sampled outputs across several draws with full-neighborhood outputs. Report variance and failure cases rather than presenting one favorable sample. At serving time, pin the graph snapshot, fanout and seed policy; a changed graph can change scores without a model update. Keep a fallback if required neighbors are missing. The project makes the cutoff and evaluation populations explicit.

Implementation

from random import Random

observed_calls = [
    ("checkout", "billing", 31),
    ("billing", "ledger", 39),
    ("checkout", "inventory", 53),
]

def sample_visible_callers(seed_services, call_events, cutoff_minute, fanout, seed):
    if fanout < 1:
        raise ValueError("fanout must be positive")
    incoming = {service: [] for service in seed_services}
    for caller, callee, observed_minute in call_events:
        if observed_minute <= cutoff_minute and callee in incoming:
            incoming[callee].append(caller)
    randomizer = Random(seed)
    return {service: tuple(randomizer.sample(sorted(set(callers)),
                                             min(fanout, len(set(callers)))))
            for service, callers in incoming.items()}

sampled = sample_visible_callers(["billing", "inventory"], observed_calls,
                                 cutoff_minute=47, fanout=2, seed=29)
assert sampled == {"billing": ("checkout",), "inventory": ()}

Performance and operating cost

Building a filtered adjacency list costs O(E) time and O(E) space for E call events; sampling up to k callers for B seed nodes costs roughly O(Bk) after indexing, subject to degree and deduplication. This small demonstration rescans events and is suited to an audit, not a high-throughput loader. Multiple graph layers may expand neighborhoods toward O(Bk^L) before shared nodes merge. Store or query a timestamp-indexed graph snapshot for production and measure the bias from missing sampled neighbors.

Common Mistakes

Do not apply a seed-node label to every context node in its sampled subgraph.
Do not use future graph edges merely because the test graph was exported later.
Do not compare a sampled model with a full-graph baseline under different feature cutoffs.