Which Old Edges Are Worth Keeping? Budgeted Relational Memory for Streaming Fraud Graphs

Fraud detectors that read a transaction graph, meaning the web of accounts, devices and contacts that link one event to another, catch coordinated schemes that a model looking at single rows misses. A deployed version of such a detector has to decide how much of that graph to keep. The usual answer is either "everything," which runs out of memory, or "the last N days," which is cheap. We propose to test a third answer. Treat retained graph history as a resource that shows diminishing returns. Measure how much each block of old edges is actually worth to current predictions, using only labels that have already arrived. Then keep the blocks worth most under a fixed memory budget, even when they are old.

The bet is simple. Much of old history is redundant or misleading once fraud patterns drift, so a plain recency window should work reasonably well. But some old edges are the only paths connecting today's accounts to the unlabeled "background" accounts that carry the signal. Throwing those away hurts accuracy in a way that recency alone cannot see. If that is true, a value-aware memory should beat the best recency window of the same size. If it is false, practitioners can stop worrying and use a recency window. Both outcomes are useful, and the experiment is designed so that either one is clearly visible.

Core Claim

Under strict chronological evaluation with realistic label delays, the accuracy of a streaming graph fraud detector as a function of retained history is concave and can turn downward. How far it turns down depends on which edges are kept, not only on how many. We claim that the value of a historical edge block can be estimated cheaply. The estimate is the gradient of the loss on the most recent window of matured labels with respect to a soft mask on that block's edges. We further claim that choosing edges by this estimate, subject to a constraint that keeps target nodes connected, beats the best tuned recency window at equal memory. The comparison is area under the ROC curve (AUC) and average precision (AP) on DGraph and Elliptic.

This moves the "diminishing returns in data scaling" question from training examples to inference-time relational context. As far as the file shows, no one has studied that setting.

What Is Known and What Is Missing

Evidence that background structure matters (motivates the proposal). DGraph released a 3.7M-node financial contact network with timestamped edges, a 1.3% fraud rate, and 2.4M unlabeled background nodes. Two findings from that paper frame this proposal. First, modelling target-to-background relations with a relational GCN raised AUC from 0.751 to 0.784, so background structure carries signal. Second, many specialised anomaly models ran out of memory or exceeded 24 hours on the full graph. DGraph documents this tension but offers no rule for what can be dropped.

Evidence that staleness and drift matter (motivates the proposal). BRIGHT makes graph inference fast enough for production. It precomputes entity embeddings in a daily batch and restricts edges to point from past transactions to current ones. Its cache is refreshed on a fixed schedule over whatever history exists, so it addresses latency, not which history is worth caching. Temporal Graph Benchmark evaluates models in streaming order. It shows that when many edges are unseen (a high "surprise index"), deep temporal models degrade and simple heuristics can win. It explicitly leaves fraud node classification open.

Methods whose ideas we reuse, in a different setting (supply the method). Capturing the Temporal Dependence of Training Data Influence estimates how much each training example shapes the final model along the SGD trajectory. It finds a low-influence middle phase, and shows that selecting data only in high-influence phases retains 96% of the gains at 5x less compute. We take the idea that data value is non-uniform and cheaply estimable, but apply it to edges consumed at inference rather than to training examples. We also use a first-order mask gradient rather than their unrolled Gauss-Newton machinery, which the file notes is derived for SGD and not for graphs. Customs Fraud Detection in the Presence of Concept Drift shows that drift degrades exploitation-only boosted-tree models, with correlation up to −0.55, and uses optimal-transport drift scores to steer exploration. It works on tabular records, and we borrow only its drift-scoring idea as a diagnostic.

Adjacent work that keeps memory differently (constrains the design). Incremental Learning with Concept Drift Detection for Graph Streams keeps a prototype memory and reports that passive sliding windows recover slowly after sudden drift. It warns us that a pure window can lag, but its graph-edit-distance prototypes do not scale to million-node graphs. CaT-GNN resists shift by mixing causal and environment neighbourhoods, and was evaluated only on static splits. Its neighbourhood reweighting is orthogonal to our question: it changes how edges are used, while we choose which edges exist. ENDEF shows that shortcut features learned from the past can invert under drift; in its case, 97% of Trump-mentioning items were real in training versus 33% at test. It is the textual analogue of our worry that old edges encode relations that no longer hold.

Research Program

Evaluation protocol. The first piece is a prequential protocol for graph fraud detection. Time is cut into blocks. At block $t$ the model scores new target nodes using only edges with timestamps before $t$, and trains only on labels that have "matured" by $t$. Maturity is simulated with a label delay $d$ swept over several block lengths, standing in for chargeback-style delays. Global normalisation over the whole timeline is forbidden. On DGraph we use edge timestamps to assign nodes to blocks. On Elliptic we use its native time steps.

History scaling curves. Inside this protocol we measure AUC and AP as a function of retained edge budget $B$, sweeping from a few percent of history up to all of it. We draw one curve per retention policy. The main scientific output is the shape of these curves. We ask whether they plateau, where they plateau, whether they decline, and whether the decline is steeper right after drift events flagged by an optimal-transport score on node features.

Edge-block value estimation. Partition historical edges into blocks $k$ by time slice and structural role. The roles are target–target edges, target–background edges, and background–background edges, split further by degree bucket. Attach a scalar mask $m_k$, initialised to 1, that multiplies messages along block $k$. The value of block $k$ at time $t$ is

$$ v_k(t) = -\frac{\partial}{\partial m_k} \sum_{i \in \mathcal{W}_t} \ell\big(f(x_i;\, G_{<t}, m),\, y_i\big)\Big|_{m=1}, $$

where $\mathcal{W}_t$ is the set of target nodes whose labels matured in the most recent window before $t$, $\ell$ is class-weighted cross-entropy, $f$ is the detector, and $G_{<t}$ is the retained graph. Positive $v_k$ means strengthening that block would lower recent loss. One backward pass gives all $v_k$. Estimates are smoothed with an exponential moving average across windows.

Retention policy. Retention solves a budgeted selection problem: keep blocks with the largest $v_k$ per stored edge until the budget $B$ is met. The selection is subject to a reachability constraint: every target node that currently has a path to a background node within two hops must keep at least one such path. This constraint encodes the DGraph finding directly. A cheap check verifies whether the gradient estimate agrees with actually removing blocks. On a sample of blocks we drop the block, recompute recent-window loss, and report the rank correlation with $v_k$.

Budget accounting. Memory counts both stored edges and any cached embeddings. Latency is measured as P99 neighbourhood-fetch plus inference time on a fixed machine.

Baselines

Keep everything. The naive reference retains all history and uses the strongest detector the hardware allows. On DGraph's official split, TGAT is reported at AUC 0.792 and RGCN with background nodes at 0.784 (DGraph). We found no reported result on Lacuna for DGraph or Elliptic under a prequential, label-delayed protocol, so we re-run TGAT and RGCN in our protocol and report their numbers as the ceiling-at-unlimited-memory. Our method "beats" this reference if it matches its AUC within noise at a fraction of the memory, or exceeds it at full budget because harmful history is dropped.

Best recency window. The strongest simple competitor is a FIFO window of the most recent edges, tuned over window length with the same number of tuning runs as our method. We also report an oracle window chosen with hindsight on the test stream, as an upper bound for any recency policy. This is the baseline that could sink the proposal. We claim success only if value-based retention beats the tuned window at matched edge budgets on at least two of three budget levels across both datasets, with non-overlapping seed intervals. We will also report whether it matches or beats the oracle window.

Time decay inside the model. TGAT's learned time encoding already lets it down-weight old edges. We run TGAT with all history and with the recency window as a separate arm. If TGAT learns to ignore stale edges on its own, retention policies should add nothing.

Tabular boosted trees on graph features. LightGBM uses handcrafted degree and neighbour-label aggregates, recomputed each block from the same retained edges. On eBay's production graph, BRIGHT reports AP 0.4420 for its graph model versus 0.4201 for LightGBM. That data is not public, so the comparison anchors expectations rather than serving as a target.

Ablations isolating the key ingredient. There are three. The first keeps the budget and reachability constraint but chooses blocks at random. The second keeps value-based ranking but drops the reachability constraint. The third ranks blocks by structural role alone, keeping all target–background edges and filling the rest by recency, without any value estimate. The third ablation is the most important. It tests whether the gradient estimate earns its cost or whether a fixed structural rule suffices.

Why not just…?

Why not just use a sliding window? It may be enough, and the experiment is built to find out. The graph-stream work in Incremental Learning with Concept Drift Detection for Graph Streams reports prolonged degradation for passive windows after sudden drift, and DGraph's background-node result suggests that pruning by age alone severs useful paths. Neither result was measured on a fraud graph at equal memory. The oracle-window comparison settles this. If the hindsight-best window matches value-based retention, the recommendation becomes "tune a window" and the value estimator is unnecessary.

Why not just keep all target–background edges and window the rest? This rule-of-thumb is the structural-only ablation, and it is a genuine threat, since it captures the DGraph insight at no estimation cost. The value estimator justifies itself only if it adds accuracy on top of this rule. The most plausible place for that is after drift events, when some background regions become misleading and should be dropped. We test that case specifically by conditioning results on flagged drift blocks.

Why not just let a temporal attention model down-weight old edges? A learned time encoding cannot save memory, because the edges must still be stored and fetched, and latency grows with neighbourhood size. BRIGHT reports standard graph inference at 251 ms P99, exceeding 1.3 s at six hops. There is also an accuracy question: Temporal Graph Benchmark shows that learned temporal models can fail under high surprise, with Moving Average at NDCG@10 0.559 versus TGN at 0.315 on tgbn-reddit. The TGAT-with-all-history arm tells us whether this failure happens on fraud graphs.

Why not just subsample neighbours at inference, as GraphSAGE-style samplers do? Sampling bounds compute per query but not stored memory. Uniform sampling also treats a bridging edge and a redundant edge alike. We include uniform neighbour sampling at matched fetch cost as a secondary arm, so the latency comparison is fair.

Proposed Experiments and Decisive Checks

The main experiment runs every retention policy in the prequential protocol on DGraph and Elliptic, with label delays of zero, one and three blocks. We use three memory budgets (10%, 30% and 60% of full history), five seeds, and fixed detectors (RGCN and TGAT). We report AUC, AP, memory and P99 latency. As a secondary check, tgbn-trade and tgbn-reddit from TGB test whether the shape of the history curve generalises beyond fraud, with Moving Average included as the heuristic reference.

The decisive checks are three. First, the history curves must show concavity or decline for at least one policy. If accuracy keeps rising with history under every policy, the diminishing-returns premise fails and the proposal reduces to a memory-engineering exercise. Second, value-based retention must beat both the tuned recency window and the structural-only rule at matched budget. If it does not, we report that simple rules suffice. Third, the advantage should grow with label delay only if the value estimate stays informative when it is itself stale. We measure this by the rank correlation between $v_k$ computed from matured labels and $v_k$ recomputed with oracle labels. A collapse in that correlation at longer delays would show that label latency, not memory, is the binding limit for curating relational history online.