An Improved Clique-Picking Algorithm for Counting Markov Equivalent DAGs via Super Cliques Transfer

An Improved Clique-Picking Algorithm for Counting Markov Equivalent DAGs via Super Cliques Transfer

Speakers: Lifu Liu, Shiyuan He, Jianhua Guo

Conference: ICML 2025

YouTube: https://slideslive.com/39044021

Overview

This talk introduces an innovative approach to a fundamental problem in causal inference: efficiently counting the number of Markov Equivalent DAGs (MEC). Presented by Lifu Liu, Shiyuan He, and Jianhua Guo at ICML 2025, the work unveils the Improved Clique-Picking (ICP) algorithm, which significantly enhances the computational efficiency of determining the size of an MEC. This problem is critical because observational data often cannot uniquely identify a single Causal Directed Acyclic Graph (DAG), instead yielding an MEC—a set of DAGs that all encode the same conditional independence relationships. Understanding the size of this equivalence class is paramount for quantifying the inherent causal uncertainty in a given dataset.

The challenge lies in the super-exponential growth of MEC sizes as the complexity of the underlying graph increases; for instance, a mere 128 nodes can lead to 10^130 DAGs in an MEC. Existing algorithms, while foundational, struggle with the computational burden posed by large-scale graphs. The ICP algorithm addresses this by introducing novel higher-level graph structures called super cliques and super residues, and a sophisticated Super Cliques Transfer (SC-Trans) operation. These innovations allow for the reuse of computations and a theoretical reduction in the complexity of a critical step within the state-of-the-art Clique-Picking (CP) algorithm, moving from M * (V+E) to M^2.

The implications of this research are far-reaching for the field of causal inference and machine learning. By providing a dramatically more efficient method for quantifying causal uncertainty, ICP empowers researchers and practitioners to analyze larger, more complex datasets with greater accuracy and speed. This advancement not only accelerates fundamental research into causal discovery but also offers practical benefits for model builders and infrastructure teams by reducing the computational overhead associated with evaluating the robustness and ambiguity of learned causal structures.

Background

▶ Watch: Problem: Counting DAGs in Markov Equivalence Classes (0:00)

The study of causal inference is central to understanding relationships between variables, moving beyond mere correlation to establish cause-and-effect. A fundamental tool in this domain is the Directed Acyclic Graph (DAG), which visually represents these causal relationships. However, a significant challenge arises when working with observational data: it is often impossible to uniquely identify the true underlying DAG. Instead, the data typically allows for the identification of a Markov Equivalence Class (MEC). An MEC is a collection of DAGs that all imply the same set of conditional independence relationships among variables.

Quantifying the size of an MEC—that is, determining the number of DAGs it contains—is crucial for several reasons. It provides a direct measure of the inherent causal uncertainty associated with a given dataset. If an MEC is very large, it indicates substantial ambiguity regarding the true causal structure, highlighting the limitations of the observational data. Conversely, a smaller MEC suggests greater confidence in the identified causal relationships. Despite its importance, counting the number of DAGs within an MEC is a formidable computational problem. The number of DAGs can grow super-exponentially with the number of nodes; for example, a CPDAG (Completed Partially Directed Acyclic Graph) with just 128 nodes can have an MEC containing as many as 10^130 DAGs. This extreme growth underscores the urgent need for efficient algorithms.

Prior foundational work has sought to address this computational bottleneck. A key insight involves decomposing a CPDAG into its chain components, which are essentially the undirected parts remaining after removing all directed edges. These chain components are then represented as Undirected Connected Chordal Graphs (UCCGs). This decomposition strategy allows the problem of counting DAGs in a complex CPDAG to be broken down into counting DAGs within its simpler UCCG structures, with the total MEC size being the product of the sizes of its individual chain components. This simplification shifts the focus to efficiently calculating the size of a UCCG.

In recent years, algorithms have concentrated on improving the speed of UCCG size calculation. A notable advancement was the Clique-Picking (CP) algorithm, introduced in 2023. The core idea of CP is recursive: it identifies a common clique (a subset of vertices where every pair is connected by an edge) within a subclass of DAGs. By selecting a root clique, say K, it defines a subclass GK. When directed edges are removed from GK, it yields smaller UCCGs, leading to a recursive formula for the UCCG size. The CP algorithm proceeds by continuously reducing the scale of the graph. A critical step in the CP algorithm (Step 2) involves generating a set of undirected connected components (CG) of KP, where KP is derived from the current clique. This operation, for a single CG, requires V + E time, where V is the number of vertices and E is the number of edges. Since there can be M maximum cliques, the overall cost of Step 2 in the original CP algorithm is M * (V + E). While CP was considered the fastest algorithm for this problem, it still faced significant computational challenges when dealing with UCCGs containing thousands or more nodes, necessitating further improvements.

Key Findings

▶ Watch: Introducing "super cliques" and "super residues" higher-level structures (3:30)

The central contribution of this work is the Improved Clique-Picking (ICP) algorithm, which significantly advances the state-of-the-art in counting Markov Equivalent DAGs. ICP builds upon and substantially enhances the existing Clique-Picking (CP) algorithm by addressing its computational bottlenecks, particularly in the generation of undirected connected components.

The primary innovations and key findings include:

• Introduction of Higher-Level Structures: ICP introduces two novel conceptual structures: super cliques and super residues. A super clique groups a "clique header" (a clique closest to the root in a specific tree structure) with its "clique tails" (other cliques satisfying specific connectivity properties). A super residue is then defined as the set of residues corresponding to the cliques within a super clique.
• Fundamental Observation: A critical discovery underpinning ICP is that the induced subgraphs of these newly defined super residues within the original graph G are precisely the undirected connected components CG of the root clique K1. This observation provides an elegant and direct method for identifying these components from a higher-level, aggregated perspective, moving beyond the individual clique-level processing of the original CP algorithm.
• Super Cliques Transfer (SC-Trans) Operation: The most significant algorithmic contribution is the development of the SC-Trans operation. This mechanism allows for the efficient derivation of CG for any clique KI by simply modifying the CG of a parent clique K1. Instead of recomputing CG for every clique from scratch (as implied by the original M * (V+E) complexity), SC-Trans leverages the structural relationships between cliques in the root clique tree (TK1) to transfer and update previously computed components. This avoids redundant computations, which is crucial for efficiency.
• Theoretical Complexity Improvement: The SC-Trans operation directly targets Step 2 of the original CP algorithm, which previously incurred a cost of M * (V+E) for generating the undirected connected components. ICP, through SC-Trans, reduces the complexity of this critical step to M^2. This represents a significant theoretical improvement, especially for dense graphs where E can be large.
• Empirical Validation and Scalability: Extensive experiments on chordal graphs demonstrate that ICP consistently and substantially outperforms CP across various node counts and graph densities. Crucially, the time savings provided by ICP become progressively larger as the number of UCCG nodes increases. Furthermore, as graph density (R) increases, both the total counting time difference and the Step 2 time ratio between ICP and CP grow, confirming that ICP scales much more favorably for larger and denser graphs. This empirical evidence strongly validates the theoretical complexity improvement and confirms the practical utility of the algorithm.

In essence, ICP offers a more abstract and efficient way to manage the decomposition of graphs into connected components, dramatically accelerating the process of counting Markov Equivalent DAGs, particularly for complex and large-scale causal models.

Technical Deep Dive

▶ Watch: Super residues directly identify undirected connected components (4:30)

The Improved Clique-Picking (ICP) algorithm introduces sophisticated structural insights and a novel transfer mechanism to significantly accelerate the counting of DAGs within a UCCG (Undirected Connected Chordal Graph). To fully appreciate ICP, it's essential to first understand the core idea of the original Clique-Picking (CP) algorithm and its computational bottleneck.

The CP algorithm operates on the principle of recursively decomposing a UCCG. Given a UCCG G and a selected clique K within it, the algorithm considers a subclass of DAGs, denoted GK, where K is a common clique. By removing the directed edges from GK, the problem is reduced to counting DAGs in smaller UCCGs. The recursive formula for calculating the size of a UCCG is built upon this decomposition. A critical part of this recursion, referred to as Step 2, involves generating a set of undirected connected components (CG) of KP, where KP is a specific subgraph related to K. In the original CP algorithm, generating a single CG of KP requires V + E time, where V is the number of vertices and E is the number of edges. Since there can be M maximum cliques, the total cost for Step 2 across all relevant cliques is M (V + E). This M (V + E) term proved to be the primary performance bottleneck, especially for large and dense graphs.

ICP addresses this bottleneck by introducing two new concepts: super cliques and super residues, and a mechanism for Super Cliques Transfer (SC-Trans).

Super Cliques and Super Residues

The definitions of super cliques and super residues are rooted in the structure of a root clique tree (TK1), which represents the relationships between cliques when K1 is considered the root.

1. Clique Headers and Clique Tails:

• In a clique tree rooted at K1, some cliques (e.g., K2, K3, K4 in the example) have their parent cliques uniquely determined relative to K1. These are designated as clique headers.
• Other cliques (e.g., K6, K7 relative to K5) might have more complex connection patterns. A clique KQ is defined as a clique tail of a clique header KH if two specific properties related to their connectivity in the clique tree and the graph structure are satisfied. For instance, K5 might be a clique header (closest to the root among a group), and K6 and K7 could be its clique tails.

1. Super Clique: A super clique is formed by grouping a clique header with all its corresponding clique tails. Visually, these are depicted as aggregated units, like blue circles in the presentation's example.
2. Super Residue: For each super clique, the set of residues (the graph components that remain after removing the clique and its edges) corresponding to all cliques within that super clique is collectively defined as a super residue.

The crucial insight here is that the induced subgraphs of these new super residues in the original graph G are precisely the undirected connected components (CG) of K1. This observation provides a direct and elegant way to identify these components from a higher, more abstract level, rather than through individual clique-by-clique processing.

Super Cliques Transfer (SC-Trans) Operation

While defining CG of K1 using super residues is a step forward, the true efficiency gain comes from the Super Cliques Transfer (SC-Trans) operation. This mechanism allows the algorithm to derive CG for any other clique KI (e.g., a child clique of K1) by intelligently modifying the already computed CG of K1, thereby avoiding redundant computations. The core idea is to efficiently transfer information from TK1 (the root clique tree for K1) to TKI (the root clique tree for KI).

The SC-Trans framework consists of three main rules:

1. Splitting of Super Cliques due to Root Change: When the root of the clique tree changes (e.g., from K1 to K5, where K5 was a child of K1), the super clique that contained K5 in TK1 might split. Its children (e.g., K6 and K7 of K5) now become new clique headers or parts of new super cliques in TK5. Correspondingly, their super residues generate new undirected connected components in CG of K5. This rule accounts for the local structural changes around the new root.
2. Formation of New Super Cliques Involving the Old Root: In the new root's clique tree (e.g., TK5), the old root K1 and its immediate neighbors (e.g., K2) might form a new super clique. This new super clique will generate new undirected connected components in CG of K5. This rule handles how the previous root and its immediate context are re-integrated into the new clique tree structure.
3. Direct Transfer of Unaffected Super Cliques: This is the most critical rule for efficiency. Except for the super cliques directly affected by the root change (as described in rules 1 and 2), all other super cliques and their corresponding super residues remain exactly the same. This means their associated undirected connected components can be directly transferred from CG of K1 to CG of KI without any re-computation. This avoids the V+E cost for a large portion of the graph, leading to significant savings.

By applying these three rules, the ICP algorithm can efficiently transfer the CG from a parent clique KI to any child clique KT in the clique tree. This systematic reuse of information transforms the M * (V+E) complexity of Step 2 in the original CP algorithm into M^2 for the ICP algorithm. The M^2 complexity arises from the fact that the transfer operations primarily involve managing the relationships between M cliques, rather than repeatedly scanning the full graph structure (V+E) for each clique. This represents a substantial theoretical improvement, especially in scenarios where V and E are large.

Experimental Setup & Results

▶ Watch: Detailed explanation of the three SC-Trans algorithm rules (6:00)

To demonstrate the practical efficacy and computational advantages of the Improved Clique-Picking (ICP) algorithm, a series of experiments were conducted, comparing its performance against the original Clique-Picking (CP) algorithm. The experimental setup focused on generating synthetic graphs and measuring the total counting time, with particular attention to the time spent in Step 2, the bottleneck addressed by ICP.

Graph Generation

The experiments utilized chordal graphs, which are a specific class of graphs relevant to the problem, generated using the minimal triangulation method. This ensures a controlled environment for evaluating the algorithms' performance on graph structures characteristic of UCCGs.

Experiment 1: Fixed Graph Density, Varying Number of Vertices (V)

In the first set of experiments, the graph density was kept constant, while the number of vertices (V) in the UCCGs was systematically varied. This setup aimed to assess how well ICP scales with increasing graph size.

• Results: The results, presented in tables and graphs, clearly showed that ICP consistently outperformed CP across all tested node counts and densities.
• Key Observation: More importantly, as the number of UCCG nodes increased, the time saved by the ICP algorithm became progressively larger. This indicates that ICP's efficiency gains are not merely constant factors but rather manifest as increasingly significant speedups for larger problem instances. This strongly supports the theoretical complexity improvement, suggesting that ICP's M^2 scaling for Step 2 is more favorable than CP's M * (V+E) for growing V and E.

Experiment 2: Varying Graph Density (R)

The second set of experiments investigated the algorithms' performance under varying graph densities, denoted by R, while potentially keeping the number of vertices constant or within a range. This explored how the algorithms cope with increasing edge counts, which directly impacts the E term in M * (V+E).

• Results: As the graph density R increased, the total counting time difference between ICP and CP also increased.
• Key Observation: Furthermore, the Step 2 time ratio (the ratio of time spent by CP in Step 2 compared to ICP in the equivalent step) also became significantly larger with increasing R. This finding is particularly important because higher graph density implies a larger number of edges (E), which directly contributes to the computational cost of the original CP algorithm's Step 2. ICP's ability to handle this growth more efficiently highlights the strength of its Super Cliques Transfer (SC-Trans) mechanism in avoiding redundant computations associated with edge processing.

Overall Conclusion from Experiments

The empirical findings from both sets of experiments provide strong validation for the theoretical complexity improvement introduced by ICP. The consistent outperformance, coupled with the progressively larger time savings for increasing node counts and densities, confirms that ICP scales more favorably for larger and denser graphs. This makes ICP a robust and efficient solution for counting Markov Equivalent DAGs in real-world scenarios where causal models can involve many variables and complex interdependencies.

Practical Implications

▶ Watch: Experimental results: ICP significantly outperforms CP algorithm (7:00)

The development of the Improved Clique-Picking (ICP) algorithm carries substantial practical implications across various facets of machine learning and causal inference, impacting researchers, model builders, and infrastructure teams alike.

For practitioners and researchers in causal inference, ICP offers a critical tool for navigating the inherent uncertainties in causal discovery. The ability to efficiently count the number of DAGs in a Markov Equivalence Class (MEC) directly translates to a more robust quantification of causal uncertainty. This means researchers can now analyze larger and more complex datasets, where previously the computational cost of assessing MEC size was prohibitive. This allows for a more nuanced understanding of "how certain" a discovered causal graph truly is, leading to more reliable scientific conclusions and better-informed decisions. For instance, in fields like epidemiology, economics, or computational biology, where causal models often involve hundreds or thousands of variables, ICP enables a deeper exploration of potential causal structures and their ambiguities.

For model builders and developers working on causal discovery algorithms, ICP provides an enhanced backend component. Many causal discovery algorithms output a CPDAG (Completed Partially Directed Acyclic Graph), and the next logical step is often to understand the breadth of the MEC it represents. By integrating ICP, these tools can offer faster and more scalable evaluations of MEC size, which can be critical for:

• Algorithm evaluation: Comparing the "uniqueness" or "certainty" of different causal discovery algorithms.
• Model selection: Choosing between competing CPDAGs based on the level of uncertainty they represent.
• Robustness analysis: Understanding how sensitive downstream predictions or interventions are to the specific DAG chosen from an MEC. The reduced computational time means faster iteration cycles for developing and testing new causal models.

Infrastructure teams responsible for managing computational resources will also benefit. Tasks involving MEC size calculation, which were previously highly demanding in terms of CPU time and memory, can now be executed significantly faster. This translates directly to:

• Reduced compute costs: Less time spent on high-performance computing clusters or cloud resources.
• Faster job completion: Accelerating research pipelines and enabling more experiments within a given timeframe.
• Improved resource utilization: Freeing up computational resources for other demanding tasks.

However, it is important to consider the tradeoffs and limitations. While ICP offers a significant theoretical and empirical improvement, the problem of counting DAGs in an MEC remains fundamentally challenging due to its super-exponential nature. Even with an M^2 complexity for a critical step, the constant factors and the overall scale of M (the number of maximum cliques) can still lead to substantial computation for extremely large or dense graphs. The algorithm focuses on counting DAGs within an MEC, not on the causal discovery process itself. The accuracy of the MEC size count is contingent on the correctness of the input CPDAG. While ICP pushes the boundaries of tractability, there will still be graph sizes and complexities beyond current computational limits. Therefore, while ICP is a major step forward, it doesn't eliminate the inherent difficulty of the problem, but rather makes a much larger class of instances tractable.

Key Takeaways

• Counting the number of DAGs in a Markov Equivalence Class (MEC) is crucial for quantifying causal uncertainty but is computationally challenging, growing super-exponentially with graph size.
• The prior state-of-the-art Clique-Picking (CP) algorithm had a computational bottleneck in generating undirected connected components, incurring M * (V+E) time for a critical step.
• The Improved Clique-Picking (ICP) algorithm introduces novel higher-level structures: super cliques and super residues, which efficiently identify graph components.
• ICP's core innovation is the Super Cliques Transfer (SC-Trans) operation, which intelligently reuses computations across cliques, avoiding redundant processing.
• SC-Trans reduces the complexity of CP's bottleneck step from M * (V+E) to M^2, a significant theoretical improvement.
• Empirical results confirm ICP consistently and substantially outperforms CP, with speedups becoming more pronounced for larger and denser graphs, validating its practical scalability.

About the Speaker(s)

The talk was presented by Lifu Liu, Shiyuan He, and Jianhua Guo.