Causal Structure Shift Detection via Orthogonal Residual Moments

Causal relationships may appear or disappear across environments, and capturing them is essential for understanding the structure of the underlying system. Most existing methods can identify which causal mechanisms shift under a common graph, but they cannot attribute a detected shift to a change in the causal structure. In this work, we consider nonlinear additive noise models sharing a causal order and establish conditions under which observed data uniquely identify the causal structure shifts, even when the order is not unique. We also provide conditions that preserve this guarantee under structure shifts consistent with a common order. Building on these identifiability results, we propose STORM, a two-stage algorithm that first estimates a common order by repeatedly removing a node with no children in any environment and then detects shifts by testing whether omitting a candidate parent changes the target node's conditional mean. To reduce the impact of regression estimation errors on both stages, we derive orthogonal scores whose expectations are insensitive to the errors to first order. Experiments on synthetic and real-world datasets showed the effectiveness of STORM in various scenarios.