CS Paper Radar

Does the Explanation Drift Before the Guarantee? Label-Free Early Warning on Evolving Graphs

Tomasz Szandała, Damian Raczkowski

cs.AI ·submitted 2026-10-12 10:22 UTC · v1

Abstract

Deployed models can fail silently as the world they describe evolves. Attribution drift has served as an early warning in tabular data; we ask whether, in graph streams, a model's own explanations can forewarn the loss of nominal conformal coverage. Doing so requires repairing the naive drift statistic twice. A vanishing edge loses mask mass regardless of whether the model relied on it, so we condition the importance on edge presence. Evolving graphs also break edge identity: a relabelling that changes nothing shifts the identity-based statistic by 0.69 on synthetic graphs and 0.83 on real ego-networks, whereas aggregating over structural roles brings both to 0.0 and stays well-defined when the support changes. We test six pre-registered regimes on thirty seeds each. A two-channel monitor, tracking conditional mask mass and its distribution over roles, precedes coverage collapse by 8 to 14.5 steps across four gradual regimes (node addition, removal, replacement, and edge thinning), all surviving Holm correction. A sudden knockout yields the expected zero lead, and a harmless change triggers no alarm. Leads track the length of the transitional phase (Spearman 0.79 over 150 runs). On real transaction ego-networks, the untuned mass channel forewarns staged drift by 27 steps and is the only channel, attributional or structural, that never alarms on a stationary stream. The main limitation is that the mass channel is blind to covariate drift, which breaks the guarantee in every run; the distributional channel detects it and also rescues the rewiring regime, so we report the two channels separately rather than as a union.

Comment
9 pages + appendix for reproducibility

Closest papers

Nearest neighbours by meaning across the whole index.

When Concealed Links Cannot Be Recovered: A Structural Identifiability Bound and Evaluation Pitfalls in Offshore Leak Networks

cs.IR math.PR ·2026-08-10 ·Joseph Bingham
position similarity 0.59
Abstract · 9 pages, 7 figures

Leaks such as the Panama and Paradise Papers expose large networks of offshore entities, and they invite an obvious question for network learning. Can the relations these structures are built to hide---above all, who beneficially owns what---be recovered from the public part of the leak by link prediction? We argue that the answer is mostly no, and that the analyses which suggest otherwise are measuring the wrong thing. Our main result is a distribution-free identifiability bound. For any recovery rule that respects graph isomorphism, and that covers every topological link-prediction score together with every message-passing graph neural network, a concealed endpoint left isolated in the observed graph is interchangeable with its structural twins, so its hidden edge cannot be recovered above chance. Isolation is only the sharpest case. In general the ceiling on recovery is set by the size of a node's structural-indistinguishability class, for which the Weisfeiler--Leman colour class is a computable stand-in, and node degree is at best a loose proxy. On the full ICIJ Offshore Leaks graph (814K entities and 84K labelled beneficial-owner edges) a classifier-free, degree-controlled probe reproduces an exact $0.5$ floor for isolated owners, who make up $20.6\%$ of all owners, and a trained graph neural network lands on the same floor. Recovery climbs only as structural distinctiveness grows, and the floor reappears in every one of the five leaks. Along the way we document five evaluation traps. Each one makes a bound that cannot be beaten look beaten, and we give a short rule that avoids them. The practical upshot is to redirect effort from the hidden principal, which is close to unrecoverable, toward the machinery of concealment, and to spell out why fusing external data helps far less than one would hope.

0.10

Operationalising Weaker Faithfulness: Recovery, Ambiguity and Computational Limits

cs.LG stat.MEstat.ML ·2026-10-22 ·Cillian Hourican, Rick Quax
similarity 0.56
Abstract

Variables can predict an outcome jointly while each is individually independent of it, causing structure learners to discard informative links. We investigate how to operationalise weaker faithfulness through two approaches: selective protection in an adjacency learner and explicit retention of alternative directed graph explanations. Matched experiments show that changes at both an early candidate-removal stage and later pruning can be necessary. In noisy XOR with a descendant (N = 10,000, 20 matched samples), combining reactivation and protection raises complete parent-pair recovery from 0/20 for either change alone to 20/20, while adding false edges. A confirmation study shows that the family estimator can preserve explanations lost by orienting the protected learner's selected skeleton: in one weaker signal XOR condition (N = 10,000) it retains the entire reference family in 48/50 samples, compared with 0/50 for the skeleton adapter. These gains are conditional. Protection can add only error, weaker effects produce false exclusions, and an ordinary faithful-chain comparison favours the PC learner. Complete nonempty family outputs decline at six/eight variables, and all 400 twelve/twenty-variable searches remain unfinished at the reporting cutoff. Neural controls show engineered retention, while the family estimator returns no accepted graph within its application budget. This operationalisation identifies two deletion stages that must be coordinated in the motivating example and shows when direct family search preserves explanations lost by selecting one skeleton. Finite evidence and computation remain substantial barriers to reliable general inference.

0.25

Amortised Post-Hoc Explanation with Exact Preservation for Dynamic Graph Anomaly Detectors

cs.LG cs.AI ·2026-08-16 ·Iyad Assaad Nekka, Hamida Seba, Walid Khaled Hidouci, Karima Amrouche
code/data similarity 0.55
Abstract

Anomaly detection in dynamic graphs underpins financial fraud analysis, intrusion detection, and platform integrity, where automated decisions require human-interpretable justifications. StrGNN, the strongest performer in recent benchmarks, produces no explanation: when an edge is flagged, the analyst receives only a score. Explanation metrics are undefined for StrGNN because no attribution vector exists. This paper closes that gap. We present X-StrGNN, a post-hoc explanation layer that wraps a trained, frozen StrGNN and emits, for every flagged edge, dual attributions: a structural attribution identifying which contextual interactions in the enclosing subgraph drove the decision, and a temporal attribution identifying which historical snapshot carried the signal. Both attributions are multiplicative masks identically one in the unexplained pass, so the layer is an exact pass-through: detection is preserved to machine precision, verified rather than asserted (Delta AUC = 0.0000, Delta AP = 0.0000, Delta P@100 = 0.0000). Attribution costs 0.66 ms per edge, making explanation of an entire alarm list feasible. We conduct the first controlled design study of attribution strategies for this architecture, comparing gradient attribution, per-instance mask optimisation, and amortised parameterisation under one protocol, one budget, and three seeds. X-StrGNN attains the highest stability (0.913) at 268x lower cost than per-instance optimisation, and its temporal attribution (1.601 against a measured random floor of 0.973) is separably better than its ablated control, while per-instance optimisation - the most expensive strategy - falls below that floor. Code, protocol, and per-seed measurements are released.

0.20

Network Topology Does Not Matter: The Breakdown of Classical Consensus in LLM Populations

cs.MA cs.AI ·2026-10-24 ·Sahil Rajesh Dhayalkar
similarity 0.54
Abstract · 19 pages, 3 figures, 3 tables

As multi-agent language model networks become widely deployed, predicting their collective behavior is a critical challenge. Classical distributed consensus theory relies on network topology to predict convergence, structurally assuming that agent updates are convex combinations, population means are conserved, and weights are content-independent. In this work, we demonstrate that these foundational assumptions fail for large language models (LLMs). By deterministically extracting continuous credence from token-level probabilities across eight instruction-tuned models and 73,080 controlled exchanges, we directly measure the empirical LLM update operator. We find that LLMs systematically violate convexity by updating outside the hull of observed opinions, exhibiting active repulsion (negative weights) that fundamentally breaks row-stochastic modeling and standard bounded-confidence repairs. Scaling these empirically fitted operators to simulations of 10,000 agents reveals that algebraic connectivity explains almost none of the final outcome variance. Instead, population dynamics are governed entirely by the model's internal update bias and message framing. Consequently, populations of several models, including those with up to 7B parameters, reliably compound small local drifts to reach confident agreement on objectively false claims regardless of their network structure. Our results prove that classical graph-theoretic metrics are inadequate for LLM populations, highlighting a profound deployment risk where multi-agent deliberation predictably saturates in collective delusion.

0.20

Chasing Label Shifters: A Change-Aware Framework for Dynamic Graph Node Classification

cs.LG cs.AI ·2026-10-13 ·Junghoon Kim, Seungyoon Choi, Hyunsung Kim, Chanyoung Park
publishedcode/data similarity 0.54
Abstract · NeurIPS 2026

Entities in real-world systems often evolve over time: users shift between information consumption patterns, researchers migrate between fields, and firms transition between financial risk states. When such systems are modeled as dynamic graphs, these transitions correspond to nodes whose class labels change between consecutive snapshots, which we call shifters. Correctly classifying shifters is often more consequential than classifying stable nodes with persistent labels, as detecting such transitions enables timely intervention in high-stakes settings. Yet, we identify a systematic failure mode across all major dynamic graph neural network architectures: shifter performance consistently lags behind stable nodes, with errors concentrated on the old label. Our structural analysis traces this failure to embedding inertia: neighborhood aggregation keeps shifter representations anchored to the old-class centroid, and this effect is strongest precisely where it is hardest to correct, namely for shifters whose neighborhoods remain aligned with the old class. Guided by this finding, we propose CHASE, a model-agnostic CHange-Aware framework for Shifting nodEs that wraps any dynamic GNN with targeted components for detecting label shifts and overriding stale neighborhood signals. CHASE consistently improves shifter performance across all tested models and datasets (up to 114.9% and 202.5% improvement on accuracy and F1 score, respectively) while preserving stable-node performance. We additionally contribute three dynamic graph benchmarks with naturally shifting labels, filling a gap in existing resources. The source code is available at https://github.com/jhkim611/CHASE

0.41

FMMO: Detecting the Divergence Between Local Attribution and Global Drift

cs.LG ·2026-09-05 ·Muhammad Rehman Zafar, Ali El-Sharif, Naimul Khan
benchmark similarity 0.53
Abstract

Post-deployment drift poses a critical risk to algorithmic accountability, particularly when ground truth labels are delayed and performance degradation becomes a "silent failure". While Explainable AI (XAI) is often relied upon to audit these shifts, we demonstrate that popular local attribution methods (e.g., TreeSHAP) can exhibit misleading stability even as model reliability collapses. In this paper, we propose a Framework for Model Monitoring and Observability (FMMO) designed to expose the divergence between local explanation stability and global distribution shifts. Using benchmark, synthetic, and real-world datasets, we show that local XAI methods fail to flag drift-induced disparate impact, specifically where False Positive Rates spike for protected groups while feature attributions remain unchanged. By integrating global surrogate models with model utilization measurements, FMMO mitigates this fairness blind spot, ensuring that stakeholders can detect discriminatory deterioration that standard local XAI tools overlook.

0.17

When the Martingale Never Stops Firing: Anytime-Valid Gating on Real Forecast Streams

cs.LG stat.MEstat.ML ·2026-08-31 ·Weijia Han, Lisha Qu
similarity 0.53
Abstract · 4 pages, 2 figures

Machine learning systems are increasingly corrected while they run, and the decision of when to intervene is increasingly delegated to statistical monitors. Anytime-valid inference promises evidence that can be acted on at any moment, exactly the guarantee this setting needs, and it is moving from theory into deployed monitoring. Conformal test martingales are the change-detection instrument, and Ville's inequality caps their false-alarm probability on exchangeable data. The guarantee is conditional. A deployment inherits it only if the stream it monitors behaves exchangeably. The premise is hardest to satisfy where these monitors are most useful, on dependent data and inside loops where the monitor modifies the learner whose scores it reads. It is also rarely measured. We measure it in a pre-specified case study, where such a monitor gates the online updates of a Kalman adapter correcting frozen time-series foundation models on five forecasting streams. On exchangeable synthetic streams, the same implementation fires in at most 1 of 60 runs. On the real streams, at alpha = 0.05, 135 of 135 clean-stream runs fired. The construction does not explain the firing; the failure comes from the deployed score stream itself. Repeated fires hold the gate's drift response active, and the gated filter amplifies the very transient it was designed to prevent. The component worth keeping makes no validity claim. Huber-style gating of the filter's own updates cuts isolated-spike degradation by an order of magnitude with no dataset specific tuning. Anytime-valid methods proposed for dependent data should therefore be accompanied by null-calibration controls and mechanism traces.

0.25

NICE: Scale-Stable Perturbations for Graph Neural Network Explanations via Noise Corruption

cs.LG cs.AI ·2026-08-17 ·Ziluowen Luo, Jun Yin, Ruochen Liu, Ming Cheng, Shirui Pan +2 more
similarity 0.53
Abstract · 17 pages, 9 figures

Post-hoc Graph Neural Network (GNN) explainers commonly follow a Perturb-Query paradigm, inferring the importance of graph elements based on queried predictions to perturbed inputs. However, such perturbations often introduce substantial distribution shift, undermining the reliability of the queried predictions used to derive explanations. While existing efforts mainly improve perturbed graphs or stabilize model predictions on them, we revisit the perturbation mechanism itself. We show that the widely used Element-wise Masking(EM) suppresses edge-induced messages toward zero, causing deterministic scale contraction that accumulates across message-passing layers, a phenomenon we term Scale Drift. Consequently, prediction changes under EM may conflate information corruption with deviations in propagation scale. As a scale-stable alternative to EM, we introduce Noise Corruption (NC), which perturbs each message through matched-norm random-direction corruption while preserving the expected squared message norm. Building on NC, we propose NICE, a Noise Corruption-based explanation framework, which learns a Stochastic Restoration Boundary (SRB) under NC-induced uncertainty, balancing target-prediction restoration against compactness. Furthermore, Boundary-Integrated Gradient (BIG) converts this boundary into edge attributions by accumulating each edge's contribution to reducing restoration risk along the restoration path. Experiments across multiple benchmarks demonstrate stronger explanation performance and model faithfulness while confirming that NC substantially reduces the Scale Drift induced by masking.

0.19