CS Paper Radar

Operationalising Weaker Faithfulness: Recovery, Ambiguity and Computational Limits

Cillian Hourican, Rick Quax

cs.LG stat.MEstat.ML ·submitted 2026-10-22 12:41 UTC · v1

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.

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.58
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

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

cs.AI ·2026-10-12 ·Tomasz Szandała, Damian Raczkowski
similarity 0.56
Abstract · 9 pages + appendix for reproducibility

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.

0.25

When Graph-JEPA Learns the Wrong Thing: Diagnosing and Repairing Category-Conditional Collapse

cs.LG ·2026-08-20 ·Gollam Rabby, Sören Auer
similarity 0.56
Abstract

Joint-embedding predictive architectures are selected almost universally by linear probing and effective rank. We report a case where both read healthily while the representation carries zero usable instance information. We repair it, and a second failure appears: the repaired metric saturates on a target carrying no structural information. Our corpus is a scientific-reasoning graph over 57,903 articles, each a subgraph. A Graph-JEPA predicts one masked aspect from a subgraph's remaining aspects, attaining linear-probe accuracy 0.871 and effective rank 18-47, yet retrieval recovers 0.00 of 14.4 bits (MRR 1.9e-4 vs chance 1.99e-4, p=0.98). Three upper bounds on the same pool and code recover nearly everything (+14.28, +14.34, +14.22 bits), ruling out corpus, masking, pool, and metric as causes. We trace this to variance allocation - frozen inputs place 86.05% of variance on subgraph identity and 0.40% on aspect identity, while trained latents place 0.39% and 99.61%. This is a property of the objective's optimum: the degenerate solution is a global minimum of the coupled predictor/EMA-target objective, present already at init. A repaired configuration reaches 14.377 of 14.379 bits, above the 13.865-bit oracle; reverting the loss to regression drops it to 0.307 bits, confirming it. Yet the repair licenses nothing about reasoning: the target is reducible, since intra-subgraph edges are a deterministic function of node census. The oracle reaches 96.4% of the ceiling, and our largest effect is the learning-rate schedule, not architecture. Bits and a reasoning probe show no relation across ten cells. A data-derived target fails a quality gate - 25.96% of nodes are duplicate placeholders, and the rest is more generic than supporting evidence. Rank, probes, and metrics can all saturate on an unsupportive evaluation. We release a harness with a reducibility audit and target gate.

0.25

GraphEcho: Structural Redundancy and Evidence Provenance in LLM Graph Agents

cs.AI cs.CL ·2026-09-15 ·Sikun Wang, Yixi Zhou, Lei Fan, Fan Zhang
benchmark similarity 0.55
Abstract · 13 pages, including figures and tables

A large language model (LLM) agent can follow more graph paths without acquiring more independent evidence. GraphEcho tests whether agents mistake these repeated encounters for additional corroboration. The benchmark varies path counts and evidential origins while holding evidence content fixed, and evaluates both judgments and active exploration. Controlled synthetic experiments reveal model-dependent judgment shifts, but redundant supporting paths increase the share of repeated walks across all evaluated frozen agents. Provenance-aware post-training (PAPT) reduces revisits and improves synthetic accuracy, yet covers fewer distinct sources. On scientific claims, it continues to reduce repetition while accuracy declines. These findings expose a gap between efficient exploration and effective evidence use: an agent can learn to stop repeating itself while overlooking information it needs. GraphEcho provides a controlled way to evaluate both what graph agents conclude and whether their exploration reaches distinct evidential sources.

0.36

What Does It Mean to Remove an Edge? Intervention-Aware Fidelity for Graph Neural Network Explanations

cs.LG ·2026-11-03 ·Rocco Mattia Di Mauro, Marco Grassia, Giuseppe Mangioni
similarity 0.55
Abstract · 15 pages, 2 figures. Under review

Graph neural network explanations are often evaluated via deletion fidelity, i.e., by deleting their top-ranked edges and measuring the resulting change in model output. Yet, in a message-passing GNN, "deleting an edge" does not specify a unique intervention. Structural deletion removes the edge from the graph and recomputes quantities such as degree normalization and attention, whereas message suppression leaves this structural context intact while blocking the message carried by the edge. The meaning of deletion fidelity therefore depends on what the intervention targets in the model computation. We formalize this distinction and derive sufficient conditions for exact equivalence. The two interventions coincide for additive message passing with edge-set-independent coefficients, but can diverge when aggregation depends on the presence of zero messages or when removing an edge changes the coefficients applied to surviving messages. We then construct intervention-specific edge attributions and evaluate each resulting ranking under both interventions, testing whether their relative fidelity changes with the evaluation intervention. Across nine datasets and a panel of GIN, GCN, and GATv2 models at depths 2--5, all nine GIN controls satisfy the equivalence predicted by the theory. On the target logit, the relative fidelity of the two rankings depends on the evaluation intervention in 10 of 11 reportable GCN and GATv2 cells, and in nine of them each ranking has the larger deletion area under the intervention it was built with. Deletion fidelity is thus not a property of an edge ranking alone. Evaluation protocols should explicitly report the intervention, output functional, target, and perturbation unit, and test alternative intervention semantics when the scientific question does not uniquely determine one.

0.30

When Should an In-Context Learner Expand Its Hypothesis Space?

cs.LG ·2026-10-07 ·Weihan Li, Xinlei Chen, Junhao Wu, Tianshi Zheng
similarity 0.55
Abstract · 46 pages, 12 figures, 13 tables

Learning systems adapt quickly within a familiar family of models. The harder step is deciding, from a prediction failure, whether opening a richer family is worth its cost. We cast this as a costly sequential decision and introduce the Structural Revision Environment (SRE), which produces matched failures from noise, exceptions, change within the family or structure outside it, varies the price of expansion and the remaining horizon independently of the evidence, and admits an exact normative solution of the one-shot decision. The solution shows that revision is a value boundary, not an evidence threshold: except at the lowest prices, the richer family becomes the more probable explanation long before expanding becomes optimal. Small Transformers trained in SRE reproduce the expansion boundary from utility alone. Pretrained 7B and 8B language models fail at a definite point: their predictions carry a failure-sensitive signal that their decisions do not reflect. Told the gain of expanding, they weigh it against price and horizon only when they reason, and the one model that finishes its reasoning on the history alone still does not estimate that gain. Controlled post-training of the small Transformers moves the prior and the sharpness of predictions, and neither moves the criterion.

0.30

Guide, Not Bind: Why Defeasible Priors Fail in Augmented Lagrangian Causal Discovery

cs.LG ·2026-09-03 ·Sairam Sundararaman, Sara Girdhar, Manit Narasimha Murthy, Samrudh N, Bhaskarjyoti Das
theory similarity 0.55
Abstract · 29 pages, 6 figures

Differentiable causal discovery methods increasingly encode expert priors as forbidden-edge constraints enforced by an Augmented Lagrangian (ALM) penalty, on the assumption that a data-adaptive relaxation mechanism will discount and eventually override a rule the data consistently contradicts. We show this design, which we call \emph{guide, not bind}, fails for two independent, precisely characterized reasons, and that directly repairing both restores it only partially. First, sequential penalty-ramping ALM suppresses a wrongly-forbidden true edge before any counterfactual check can detect it: we give three necessary conditions any adaptive relaxation must satisfy to avoid this (Proposition~\ref{prop:conditions}), prove that DADU---the natural relaxation rule this paper introduces as the object of study---violates all three (Corollary~\ref{cor:dadu_failure}), and confirm the failure across 3{,}072 training runs spanning graphs from 4 to 32 nodes, where a single wrong prior suppresses a true edge in 87--97\% of trials under DADU. Second, and independent of any fix to the mechanism, we prove in closed form that the standard correlation-matching objective ties a true edge and its reverse to an identical cost of exactly $2r^2$ (Lemma~\ref{lem:tie}), not because the underlying equal-variance model is unidentifiable, but because normalizing to correlation discards exactly the variance information that would make it identifiable; covariance matching instead separates the two directions by a provable margin of at least $w_0^4$ (Lemma~\ref{lem:separation}).

0.16

When the tail is earned by its companions: measuring label dependence in long-tailed multi-label classification

cs.LG cs.CLcs.IR ·2026-11-17 ·Christoffer Löffler
similarity 0.55
Abstract · 27 pages, 3 figures, 13 tables. Submitted to Information Sciences

A rare label seldom occurs alone, and a classifier can recover it from the frequent labels it co-occurs with, its companions, without having learned the label itself. Existing diagnostics of this need a trained model: none says before training whether a corpus admits the failure, or what the standard aggregate hides. Macro-F1, like any measure built from per-label confusion counts, is unchanged by how a label's recall divides between occurrences with and without a companion. We introduce a within-label estimand of that division, a reading rule under which a fall in dependence counts only if companion-free recall rises, and a statistic of training labels that bounds, before training, how far reported recall can exceed companion-free recall. Across 23 corpora, 7 training objectives and five families of label-correlation mechanisms, companion-free recall falls short on all six corpora where the estimand is defined. Up to 18.4% of the tail true positives macro-F1 credits would vanish at the companion-free rate, within the training-label bound on every corpus. No long-tail objective reduces the dependence, but architecture moves it. Models whose tail score is computed from other labels' predictions are strongly dependent.

0.41