Characteristic Imsets for Cyclic Linear Causal Models and the Chickering Ideal

2025/06/16 by Joseph Johnson, Johnson, Joseph, Pardis Semnani +1
Computer Science · #Algebraic Geometry (math.AG) #Bayesian Modeling and Causal Inference #Combinatorics (math.CO) #FOS: Mathematics #Formal Methods in Verification #Logic, Reasoning, and Knowledge #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2506.13407

openalex publication_date 2025/06/16 · openalex created_date 2025/10/13 · openalex updated_date 2026/07/28

Abstract

Two directed graphs are called covariance equivalent if they induce the same set of covariance matrices, up to a Lebesgue measure zero set, on the random variables of their associated linear structural equation models. For acyclic graphs, covariance equivalence is characterized both structurally, via essential graphs and characteristic imsets, and transformationally, through sequences of covered edge flips. However, when cycles are allowed, only a transformational characterization of covariance equivalence has been discovered. We consider a linear map whose fibers correspond to the sets of graphs with identical characteristic imset vectors, and study the toric ideal associated to its integer matrix. Using properties of this ideal we show that directed graphs with the same characteristic imset vectors are covariance equivalent. In applications, imsets form a smaller search space for solving causal discovery via greedy search.

Citations

• Causal Structure Learning in Directed, Possibly Cyclic, Graphical Models
• Rhombus Criterion and the Chordal Graph Polytope
• On the Edges of Characteristic Imset Polytopes
• Greedy Causal Discovery is Geometric
• Structure Learning for Cyclic Linear Causal Models
• Ordering-Based Causal Structure Learning in the Presence of Latent Variables
• Markov Properties for Graphical Models with Cycles and Latent Variables
• Consistency Guarantees for Greedy Permutation-Based Causal Inference\n Algorithms
• Consistency guarantees for greedy permutation-based causal inference algorithms
• The characteristic imset polytope of Bayesian networks with ordered nodes
• Discovering Cyclic Causal Models by Independent Components Analysis
• Ordering-Based Search: A Simple and Effective Algorithm for Learning Bayesian Networks
• A Theorem on the Manipulability of Redundant Serial Kinematic Chains
• A Discovery Algorithm for Directed Cyclic Graphs
• A Transformational Characterization of Equivalent Bayesian Network Structures
• Learning Bayesian Networks: The Combination of Knowledge and Statistical Data
• Binomial Ideals

Related

• Hyperplane Representations of Interventional Characteristic Imset Polytopes
• Efficiently Deciding Algebraic Equivalence of Bow-Free Acyclic Path Diagrams
• One-connection rule for structural equation models
• On the Equivalence of Causal Models: A Category-Theoretic Approach
• Calculation of Entailed Rank Constraints in Partially Non-Linear and Cyclic Models