Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules

Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules

Speakers: Tian-Zuo Wang, Lecturer, Nanjing University; Wen-Bo Du; Zhi-Hua Zhou

Conference: ICML 2025

YouTube: https://slideslive.com/39044022

Overview

This talk, presented by Tian-Zuo Wang from Nanjing University, delves into a critical challenge within causal inference: efficiently identifying all possible causal structures consistent with observational data when latent variables are present. Specifically, the research focuses on the problem of Maximal Ancestral Graph (MAG) listing. In scenarios where unobserved confounders or selection variables complicate direct causal discovery, MAGs serve as powerful graphical models to represent causal relationships among observed variables. However, from observational data alone, one can typically only identify a Partial Ancestral Graph (PAG), which encapsulates a Markov equivalence class of MAGs, leaving certain causal directions ambiguous. The core task addressed in this work is to systematically enumerate all MAGs that are consistent with a given PAG.

The significance of MAG listing is profound. Knowing the full set of consistent MAGs is indispensable for downstream causal inference tasks, such as determining causal effect bounds, where the uncertainty in causal structure directly impacts the range of possible causal effects. Traditional methods for MAG listing often resort to brute-force enumeration of edge orientations, leading to computationally intractable "exponential delay." This presentation introduces a groundbreaking approach that leverages novel orientation rules to achieve the first polynomial-delay MAG listing algorithm. This advancement represents a substantial leap in the scalability and practicality of causal discovery in complex, real-world systems, moving the field closer to robust and automated causal analysis.

Background

▶ Watch: Introduction to Causal Inference, MAGs, and PAGs (0:00)

Causal inference, as formalized by Judea Pearl, typically employs causal graphs—most commonly Directed Acyclic Graphs (DAGs)—to visually represent causal relationships. In an ideal setting, where all relevant variables are observed, a DAG can fully characterize the causal structure. However, real-world datasets are rarely ideal. The presence of latent variables, such as unmeasured confounders or selection variables, introduces significant complexities. These unobserved factors can create spurious associations between observed variables, misleading standard DAG discovery algorithms.

To address this, the field has adopted more generalized graphical models. Maximal Ancestral Graphs (MAGs) are a class of graphs specifically designed to represent causal relationships among observed variables even when latent variables are present. Unlike DAGs, MAGs can include bi-directed edges (e.g., A<->B) to denote the presence of latent confounders affecting both variables, and directed edges (e.g., A->B) for direct causation. A key property of MAGs is that they are ancestral, meaning if there's a directed path from X to Y, then X is an ancestor of Y.

A fundamental limitation in causal discovery from observational data is that the full MAG cannot always be uniquely identified. Instead, under mild assumptions, one can typically only identify a Partial Ancestral Graph (PAG). A PAG represents a Markov equivalence class of MAGs; that is, all MAGs within this class imply the same set of conditional independencies among the observed variables. PAGs utilize special edge marks: a tail (e.g., A--B) indicates an edge directed away from that vertex (A<-B), an arrowhead (e.g., A->B) indicates an edge directed towards that vertex, and a circle (e.g., A-oB) indicates uncertainty—the edge could be directed towards, away from, or bi-directed at that vertex. For example, an edge marked A-oD in a PAG means the corresponding edge in a consistent MAG could be A->D, A<-D, or A<->D. This ambiguity is what makes MAG listing a challenging but crucial task.

The problem of MAG listing, given a PAG, is to output all MAGs that are consistent with it. This consistency implies that each enumerated MAG must encode the same conditional independencies as the input PAG. The speaker notes that there are many classical methods to learn a PAG from observational data, so their work assumes a learned PAG as input. The motivation for MAG listing stems from its utility in various downstream applications. For instance, in their prior work (ICML 2023, AI Journal 2025), the authors tackled causal effect bound determination, where knowing all possible MAGs allows for computing the range of potential causal effects, accounting for structural uncertainty.

Early approaches to MAG listing often involved directly enumerating all possible orientation combinations for the ambiguous "circle" marks in a PAG. This "brute-force" method is inherently inefficient, as the number of circles can be large, leading to an exponential number of combinations. A more sophisticated approach involves recursively enumerating a subset of circles and then utilizing orientation rules to deterministically orient other edges. These rules are logical inferences that, based on partial orientations, can resolve ambiguities without further enumeration. However, for this recursive strategy to be effective, the utilized rules must be sound (never produce an invalid MAG) and complete (identify all possible orientations that are consistent). The speaker highlights that previous recursive methods, including their own in ICML 2024, suffered from an "exponential delay," meaning the time to output each MAG could still grow exponentially in the worst case. This inefficiency arose because, even with rules, the process of enumerating "local structures" (all circles at a selected vertex) could still yield an exponential number of candidates, many of which might not correspond to any valid MAG. This gap between the exponential number of enumerated structures and the potentially polynomial number of valid structures necessitated a more refined approach to rule development and enumeration strategy.

Key Findings

▶ Watch: MAG listing challenge: inefficiency of brute-force, need for rules (2:20)

The central discovery leading to this paper's contribution is the identification of a critical bottleneck in prior MAG listing algorithms: the "exponential delay." This delay, observed in recursive methods such as the authors' ICML 2024 work, stemmed from enumerating an exponential number of potential "local structures" (all possible orientations of circles around a single vertex). While the total number of valid MAGs might be large, the time taken to produce each valid MAG should ideally be polynomial in the size of the input PAG, rather than exponential.

To overcome this, the authors made a pivotal shift in their enumeration strategy. Instead of considering complex "local structures," they opted for a simpler approach: enumerating just one circle at a selected variable at each step. This single circle orientation is termed "singleton background knowledge." The key insight was that existing orientation rules were not complete for effectively incorporating such singleton background knowledge. This incompleteness meant that even with a single edge oriented, the rules couldn't fully propagate the implications, potentially leading to redundant or invalid enumerations down the line.

The primary contributions and key findings of this research are twofold:

1. Novel Locally Complete Orientation Rules: The paper introduces three novel orientation rules specifically designed to be sound and locally complete for incorporating singleton background knowledge. "Locally complete" in this context means that when a single circle is oriented, these new rules can fully determine all other implied orientations that are consistent with that specific local choice, preventing the need for further, potentially meaningless, enumeration based on that local decision. This advancement is crucial because it ensures that every enumeration step efficiently prunes the search space. The speaker mentions that the development of these rules is central to the overall efficiency improvement.

1. First Polynomial-Delay MAG Listing Algorithm: Building upon these novel rules, the authors developed the first polynomial-delay algorithm for MAG listing. The polynomial-delay property is a strong guarantee: it means that the time complexity to output each MAG is polynomial in the size of the input PAG, regardless of the total number of MAGs. This is a significant improvement over methods with exponential delay, which could take an exponentially long time to produce even a single MAG in the worst case. The reason for this polynomial delay is attributed to the "locally complete property" of the new rules, which ensures that the algorithm "will never execute the meaningless enumeration."

Furthermore, the authors conducted theoretical proofs confirming the effectiveness and polynomial-delay property of their proposed method. They also verified its performance empirically, although specific experimental details were not provided in the talk.

An intriguing additional finding, discussed towards the end of the presentation, concerns the broader completeness of orientation rules. While the three novel rules achieve local completeness for singleton background knowledge, the authors investigated whether the combined set of all known rules (including their new ones) is complete for incorporating arbitrary background knowledge. They unfortunately found that the rules are not yet complete for arbitrary background knowledge. To demonstrate this, they proposed two counter-examples, which in turn motivate the development of two more orientation rules for future research. This highlights that while significant progress has been made, the quest for a universally complete set of orientation rules for MAGs remains an open problem in causal inference.

Technical Deep Dive

▶ Watch: Novel idea: enumerate one circle using new rules for efficiency (5:30)

The core of this research lies in navigating the complexities of Maximal Ancestral Graphs (MAGs) and Partial Ancestral Graphs (PAGs) through a sophisticated application of orientation rules. Understanding these graphical models is fundamental. A MAG is a mixed graph (containing directed and bi-directed edges) that represents causal relationships among observed variables, even in the presence of unobserved confounders or selection bias. Directed edges (e.g., A->B) denote direct causation, while bi-directed edges (e.g., A<->B) indicate the presence of a latent common cause. MAGs are "maximal" in the sense that they include all edges implied by the conditional independencies, and "ancestral" meaning if there's a directed path from X to Y, then X is an ancestor of Y.

A PAG, on the other hand, is what can be learned from observational data. It represents a Markov equivalence class of MAGs, meaning all MAGs consistent with a given PAG imply the same set of conditional independencies. PAGs use three types of edge marks:

• A-->B: The edge is directed A->B in all consistent MAGs.
• A--B: The edge is directed A<-B in all consistent MAGs.
• A-oB: The orientation of the edge between A and B is ambiguous. In different consistent MAGs, it could be A->B, A<-B, or A<->B. The "circle" represents this uncertainty.

The goal of MAG listing is to resolve all these o marks such that the resulting graph is a valid MAG consistent with the input PAG.

The talk highlights the inefficiency of prior methods. A direct, brute-force enumeration approach would involve iterating through all possible combinations of orientations for every o mark in the PAG. Given k such o marks, there could be 3^k potential combinations (directed A->B, A<-B, or bi-directed A<->B), leading to an exponential complexity that quickly becomes intractable for even moderately sized graphs.

More advanced methods, including the authors' earlier work (e.g., ICML 2024), adopted a recursive enumeration strategy. This strategy involves:

1. Selecting a vertex.
2. Enumerating all "local structures" at that vertex, which refers to all possible consistent orientations of the o marks incident to that vertex.
3. For each valid local structure, applying orientation rules to propagate the implications of these choices to other parts of the graph, potentially resolving other o marks.
4. Recursively repeating the process until all o marks are resolved.

The fundamental flaw identified in this recursive approach was its "exponential delay." The number of "local structures" (valid orientations for all circles at a given vertex) could still be exponential with respect to the number of variables. Even if only a polynomial subset of these local structures were truly valid and led to consistent MAGs, the algorithm would still spend exponential time enumerating and validating the invalid ones. This "meaningless enumeration" was the primary cause of the exponential delay.

The novel approach presented in this paper tackles this by simplifying the enumeration step. Instead of enumerating complex "local structures," the algorithm focuses on enumerating just one circle at a selected variable at each step. This single orientation choice is referred to as singleton background knowledge. The challenge then shifts: existing orientation rules were not sufficiently powerful (i.e., not "complete") to fully propagate the implications of such a minimal piece of background knowledge.

To address this, the paper's most significant technical contribution is the development of three novel orientation rules. These rules are designed to be **sound and locally complete** for incorporating singleton background knowledge.

• Soundness means that any orientation implied by these rules will always lead to a MAG consistent with the original PAG. The rules never introduce an inconsistency.
• Local completeness is the critical innovation. It implies that for any given single o mark that is oriented (e.g., A-oB becomes A->B or A<->B), these rules can deduce all other necessary orientations and mark changes in the graph that are implied by this single choice, without requiring further enumeration of related ambiguities. This ensures that the algorithm avoids exploring branches of the search space that are ultimately inconsistent or redundant.

While the specific formal definitions of these three novel rules are not detailed in the transcript, their conceptual role is clear: they act as powerful inference mechanisms. By ensuring local completeness, these rules effectively prune the search space at each step of the recursive enumeration. When a single o mark is chosen and oriented, the rules rapidly update the PAG, converting other o marks to ->, <-, or <-> as dictated by consistency. This guarantees that "meaningless enumeration" is never executed, meaning the algorithm doesn't waste time exploring paths that won't lead to valid MAGs or that merely duplicate existing valid MAGs.

This refined strategy, combining the enumeration of singleton background knowledge with the new locally complete orientation rules, leads to the first polynomial-delay MAG listing method. Polynomial delay means that the computational time taken to output each individual MAG is bounded by a polynomial function of the input PAG's size (e.g., number of vertices and edges). This is a much stronger guarantee than simply having a polynomial total runtime, as the total number of MAGs can still be exponential. For instance, if there are N variables, a polynomial-delay algorithm might take O(N^k) time per MAG, whereas an exponential-delay algorithm might take O(exp(N)) time per MAG. This makes the method practical even when the number of consistent MAGs is large, as each one is discovered efficiently.

Finally, the talk touches upon a broader open problem: the completeness of orientation rules for arbitrary background knowledge. While the three new rules achieve local completeness for singleton choices, the authors discovered, through two counter-examples, that the entire set of existing rules (including their new three) is still not complete for incorporating more complex, arbitrary pieces of background knowledge. This finding motivates the need for two additional orientation rules to achieve a more universal completeness, indicating a promising avenue for future research.

Experimental Setup & Results

▶ Watch: Introducing three novel, locally complete orientation rules (6:15)

The speaker briefly mentions that the effectiveness and polynomial delay property of their method were not only proven theoretically but also verified empirically [06:17]. However, the presentation transcript does not provide any specific details regarding the experimental setup or results.

Therefore, we cannot elaborate on:

• The specific datasets used for evaluation (e.g., synthetic graphs, real-world biological or social science data, their size or characteristics).
• The baselines against which the proposed polynomial-delay method was compared (e.g., earlier brute-force methods, their own ICML 2024 recursive method, other state-of-the-art MAG listing algorithms).
• The hardware used for experiments (e.g., CPU, GPU, specific server configurations).
• The metrics employed to quantify performance (e.g., actual delay per MAG, total execution time, number of valid MAGs found, memory usage).
• Any headline numbers (e.g., speedup factors, maximum graph sizes handled, specific runtime figures).
• Ablation studies exploring the contribution of individual novel rules or components of the algorithm.

The focus of this particular conference talk appears to be primarily on the theoretical contributions—the novel orientation rules, the algorithmic design, and the formal proof of polynomial delay. While empirical validation is stated to have been performed, its specifics were not part of this presentation.

Practical Implications

▶ Watch: Open problem: general completeness of orientation rules for background knowledge (7:00)

The development of a polynomial-delay MAG listing algorithm carries significant practical implications for various stakeholders involved in causal inference and data-driven decision-making.

For Causal Inference Practitioners:

This work directly addresses a major bottleneck in causal discovery from observational data. Previously, the computational cost of enumerating all possible Maximal Ancestral Graphs (MAGs) consistent with a Partial Ancestral Graph (PAG) was prohibitive for all but the smallest problems. With a polynomial-delay algorithm, practitioners can now tackle larger and more complex datasets, enabling them to:

• Explore structural uncertainty: Instead of relying on a single, potentially incorrect, causal graph, they can systematically explore the entire space of plausible causal structures. This is vital for understanding the robustness of causal claims.
• Determine robust causal effect bounds: For tasks like policy evaluation or intervention planning, knowing the full range of possible causal structures allows for computing more accurate and reliable bounds on causal effects, accounting for the inherent uncertainty. This can lead to more informed and less risky decisions.
• Automate causal discovery workflows: The increased efficiency makes it feasible to integrate MAG listing into automated causal inference pipelines, reducing manual effort and expert intervention.

For Infrastructure Teams and Model Builders:

The ability to efficiently list MAGs indirectly benefits teams responsible for building and deploying ML models, especially in domains where interpretability and causal understanding are paramount (e.g., healthcare, finance, social sciences).

• Enhanced model interpretability: Causal graphs provide a more profound understanding of system dynamics than mere correlations. By exploring all consistent MAGs, model builders can gain deeper insights into the underlying causal mechanisms, which can inform feature engineering, model design, and debugging.
• Robustness against latent confounding: The algorithm explicitly handles latent confounders, making it invaluable for building models that are robust to unobserved variables—a common problem in real-world data.
• Guidance for data collection: Identifying ambiguous parts of a PAG through MAG listing can highlight areas where collecting additional data or performing targeted experiments (e.g., randomized control trials) would be most beneficial to resolve causal uncertainty.

Tradeoffs and Limitations:

While a significant advancement, the method comes with inherent tradeoffs and limitations:

• Total number of MAGs can still be exponential: The "polynomial delay" guarantee applies to the time taken per outputted MAG. If the input PAG is very ambiguous and consistent with an exponentially large number of MAGs, the total time to list all of them will still be exponential. Practitioners must be aware that while each individual MAG is found efficiently, the sheer volume can still be daunting for highly uncertain causal structures.
• Quality of input PAG: The efficacy of the MAG listing algorithm is contingent on the quality of the input PAG. If the PAG learned from observational data is inaccurate or unstable, the list of MAGs derived from it will reflect these inaccuracies. This underscores the continued importance of robust PAG learning algorithms.
• Completeness for arbitrary background knowledge: As noted by the speaker, the current set of orientation rules, even with the novel contributions, is not yet complete for incorporating "arbitrary background knowledge" (e.g., more complex constraints beyond singleton edge orientations). This means there might be certain scenarios where additional, valid MAGs are not discovered if more complex background knowledge is provided. This is an active area of research, as highlighted by the two counter-examples presented.
• Scalability for extremely large graphs: While polynomial delay is a strong theoretical guarantee, the polynomial factor can still be high for very large graphs, potentially impacting practical scalability for graphs with hundreds or thousands of variables. Further optimization and approximation methods might be needed for such extreme scales.

In essence, this research provides a powerful tool for navigating causal uncertainty, making the exploration of multiple causal hypotheses computationally tractable. It shifts the bottleneck from the enumeration process itself to the sheer complexity of the underlying causal system, enabling practitioners to focus on interpreting the rich set of causal structures rather than grappling with computational intractability.

Key Takeaways

• Causal inference with latent variables often requires Maximal Ancestral Graphs (MAGs) to represent causal relationships among observed variables, as standard Directed Acyclic Graphs (DAGs) are insufficient.
• Partial Ancestral Graphs (PAGs) represent Markov equivalence classes of MAGs, encoding the same conditional independencies but leaving certain edge orientations ambiguous (marked by "circles").
• Listing all MAGs consistent with a given PAG is crucial for downstream tasks like causal effect bound determination, but traditional brute-force or inefficient recursive methods suffer from "exponential delay."
• This paper introduces three novel orientation rules that are proven to be sound and locally complete for incorporating singleton background knowledge (orienting a single ambiguous edge).
• These novel rules enable the development of the first polynomial-delay MAG listing algorithm, significantly improving the efficiency of discovering all consistent causal structures by avoiding "meaningless enumeration."
• While a major breakthrough for local completeness, the research also reveals that the combined set of existing orientation rules, even with the new additions, is still not complete for arbitrary background knowledge, motivating further rule development.

About the Speaker(s)

Tian-Zuo Wang is a lecturer at Nanjing University. His research is centered on causal inference, particularly in complex scenarios involving latent variables or confounders. He is part of a research group that has been actively publishing on these topics, demonstrating a sustained commitment to advancing the field. His work includes contributions to efficient methods for causal effect bound determination and the development of sound and complete orientation rules for various types of background knowledge in MAGs. This presentation is part of a series of studies by his team, with previous works published in prominent venues such as ICML (2023, 2024), AI Journal (2025), and NeurIPS (2022). His co-authors on this paper are Wen-Bo Du and Zhi-Hua Zhou.