Efficient and Practical Clustering of Variables in Causal Graphs

Otto Tabell, Jani Nykänen, Santtu Tikka, Juha KarvanenarXiv 2026 · arXiv

TL;DR

This paper introduces conduits, a new class of variable clusters for causal graphs that simplify complex models without losing the ability to identify causal effects. The authors provide FINDCONDUITS, the first sound and complete polynomial-time algorithm to detect these clusters, enabling significant graph size reductions (up to 62%) in real-world applications.

What Problem Does This Paper Address?

Directed Acyclic Graphs (DAGs) are the bread and butter of causal inference, but they don't scale well for humans. A graph representing a complex system—like a national economy or a medical diagnostic tool—can have hundreds of variables, making it a "hairball" that is impossible to interpret.

One solution is clustering: merging related variables (e.g., several health questionnaire items) into a single "super-node." However, arbitrary clustering is dangerous. It can create directed cycles or, more subtly, destroy identifiability. An effect that was calculable from data in the original graph might become "hidden" in the clustered version.

Previous attempts to automate this were either too restrictive (finding very few clusters) or computationally ruinous (taking exponential time). This paper seeks a "Goldilocks" solution: a class of clusters that is broad enough to be useful, safe for causal inference, and fast to find.

Methods

The authors define a new structural unit called a conduit.

The Conduit Definition

A conduit is a set of vertices that satisfies two main properties:

  1. Coherence: For every parent of the cluster and every child of the cluster, there must be a directed path between them that stays entirely within the cluster. This ensures the clustered graph remains a DAG and doesn't introduce "fake" causal paths.
  2. Iterative Sibling Structure: Conduits are built using "Iterative Parental Siblings" (IPS) and "Iterative Filial Siblings" (IFS). Essentially, the algorithm starts with a node and iteratively adds its "siblings"—nodes that share the same parents or children—to form a candidate set.

The FINDCONDUITS Algorithm

The core contribution is an algorithm that enumerates all conduits in a graph. Unlike previous methods that faced exponential blowups, FINDCONDUITS runs in polynomial time ($O(n^5m)$, where $n$ is the number of vertices and $m$ is the number of edges). It works by:

  • Preprocessing ancestral relationships.
  • Generating all possible IPS and IFS sets.
  • Constructing candidate clusters from the intersections of these sets.
  • Validating each candidate against the "coherence" requirement.
Figure 1 illustrates why simple clustering can be problematic (top row) and how conduits maintain structural integrity (bottom row).

Datasets

The authors evaluated their approach using two main sources:

  1. Synthetic DAGs: Randomly generated connected graphs ranging from 25 to 150 vertices, tested at different edge densities.
  2. Bayesian Network Repository: 17 real-world benchmark graphs used in the field, including:
  3. ALARM: A monitoring system for ICU patients.
  4. INSURANCE: A model for car insurance claim costs.
  5. HEPAR2: A diagnostic system for liver disorders.
  6. PATHFINDER: A system for lymph node pathology.

To test robustness, they also added "latent confounders" (unobserved variables represented by bidirected edges) to these real-world graphs.

Key Insights and Ideas

  • Identification Invariance: The authors leverage the concept of "coherence" to prove that if a causal effect is identifiable in the original graph, it remains identifiable after clustering a conduit. This makes clustering a "safe" operation for researchers.
  • Natural Occurrence: Conduits aren't just mathematical abstractions; they appear frequently in models designed by experts. In the INSURANCE model, a single conduit was found that could collapse 13 mediating variables into one, reducing a 19-node subgraph to just 7 nodes.
  • The Power of Siblings: By defining clusters based on shared parents/children (siblings), the authors found a way to "bound" the search space, turning an exponential search problem into a manageable polynomial one.

Key Results

  • Significant Simplification: In the HEPAR2 graph, clustering conduits resulted in a median size reduction of 62%. Across all 17 real-world graphs, conduits consistently provided much higher reduction rates than previous "transit cluster" methods.
  • Efficiency: The algorithm scales well. For a dense graph with 150 nodes, the median running time was roughly 154 seconds. For sparse graphs of the same size, it took only 7 seconds.
  • Robustness to Latent Variables: Even when many unobserved confounders were added, the algorithm still found enough "safe" conduits to reduce graph sizes by 36–44%.
Figure 2 shows the median running times and the number of conduits found as the number of vertices increases.

Limitations and Future Work

  • Computational Complexity: While $O(n^5m)$ is polynomial, it may still be slow for "mega-graphs" with tens of thousands of variables. Further optimization or heuristic versions might be needed for such scales.
  • Optimal Selection: The algorithm finds all conduits. However, many conduits overlap. The paper uses a greedy approach (largest to smallest) to pick which ones to actually cluster, but finding the mathematically optimal set of clusters to maximize reduction remains an open challenge.
  • Scope of Models: The current proofs rely on semi-Markovian structural causal models. Extending these results to even more general classes of causal models (like those with selection bias) is a potential next step.

Summary updated

Abstract

Clustering variables in a graph may improve visual clarity and simplify causal inference. Harnessing the full potential of clustering requires an automated method to detect useful clusters in a graph. We introduce a novel class of clusters called conduits, and present a sound, complete and efficient algorithm for detecting all conduits in the graph. In addition to algorithmic detectability, conduits appear naturally in causal graphs stemming from real-world applications, enabling substantial size reduction. Furthermore, the structure of conduits enables the application of known identifiability results regarding clustering. We demonstrate these properties in a simulation study with real-world graphs.
BibTeX
@misc{tabell2026efficient,
  author = {Otto Tabell and Jani Nykänen and Santtu Tikka and Juha Karvanen},
  title = {{Efficient and Practical Clustering of Variables in Causal Graphs}},
  year = {2026},
  eprint = {2611.17971},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.17971},
}
Figure