acceptodds
Under review as a conference paper at ICLR 2027

ExMAG: Learning of Maximally Ancestral Graphs

Abstract

In mixed graphs, there are both directed and undirected edges. An extension of acyclicity to this mixed-graph setting is known as maximally ancestral graphs. This extension is of considerable interest in causal learning in the presence of confounders. There, directed edges represent a clear direction of causality, while undirected edges represent confounding. We propose a branch-and-cut algorithm for learning maximally ancestral graphs using a formulation as a mixed-integer quadratic program. Empirically, our method achieves comparable or improved reconstruction quality while requiring an order of magnitude fewer samples than state-of-the-art approaches.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
maximally ancestral graphs, learning, branch-and-cut methods

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_ZNTXOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes ExMAG, a branch and cut method for learning of maximal ancestral graphs (MAGs) from data with hidden confounders. The authors reason that MAGs are better than the standard directed acyclic graphs (DAGs) at modeling such data because MAGs can model a hidden confounder with a bidirected edge. The authors formulate this problem as a mixed integer program with a least squares objective. MAG requirements are met via lazily separated cuts which avoid exponential number of constraints. The method is evaluated on synthetic graphs with known causal graphs and a financial dataset.

Critical strengths
  • Causal structure learning is a difficult problem and the use of MAGs seems to be a very promising direction. Furthermore, the compact formulation (and lazy constraints) idea is novel and addresses key concerns in this research direction.
Critical weaknesses
  • The inducing path cuts can exclude valid MAGs. The paper states "the existence of an inducing path between two nonadjacent vertices implies that the graph is not maximal" but the proposed method (Sec 4.1) just states that inducing paths in general are forbidden without explicitly checking the adjacency of the endpoints. Also, the added cut only forbids the inducing path itself (without a guard for endpoint adjacency). In this case, valid MAGs may be excluded by the proposed method which would break the convergence to optimum claim in section 5.

  • The sample-efficiency claim is not supported by the results. The authors claim that the proposed method achieves comparable or improved performance while requiring significantly fewer samples than SOTA approaches. However, their results (Figure 2) shows each method at a different sample size. ExMAG is shown at n=50, FCI at n=100/500/1000, and the others at n=500. There seems to be equal n results in the appendix (Figure 6) which show that ExMAG does not consistently outperform baselines at low n (difficult to interpret due to small size).

Minor:

  • Figure 2 (the main results figure) is poorly presented. Several of the methods have very similar colors. The current scale on the y-axis also makes all lines very close together, which, combined with the dashed lines and the std dev bands, results in a plot that is very difficult to interpret.
Questions for authors
  • Does the proposed method check the adjacency of the endpoints of inducing paths when looking for violations? Furthermore, if the current inducing path constraint does not specify endpoint adjacency, can the authors confirm whether or not this would exclude valid MAGs from the solution search?
  • Could the authors include the results in Figure 6 in the main body of the paper and provide corresponding analysis?
  • Could the authors provide additional results and analysis on the solver run results? Specifically, the final constraint count of the solver and how it compares with other methods since the paper claims that "exponentially many constraints is avoided in many instances of the program".
  • Could the authors justify the selected time limits (7,200s for the proposed method and 1,800s for the baselines)? It is claimed that the baselines typically finish well within this limit, how many timed out?
  • Could the authors justify how the baselines were selected? Specifically, why were several MAG estimation methods cited in Sec 1 as existing works (line 77) excluded from the experiments (e.g., Rantanen et al, 2021)?
2 comments

Q1: Endpoint adjacency.

If the endpoints are connected by a directed edge, the graph cannot be a MAG, as that would create an almost directed cycle. Therefore, there is no need to check this case in our routine for inducing paths. A case that we forgot, however, is when there is a bidirected edge between the path endpoints.

A formal proof of why a directed edge between the endpoints is not a problem is here: In MAG, an inducing path can be formed by bidirected edges only. Consider path X1↔X2↔X3↔⋯↔XkX_1 \leftrightarrow X_2 \leftrightarrow X_3 \leftrightarrow \cdots \leftrightarrow X_k. Here, X2X_2 needs to be an ancestor of XkX_k (ie, there is a path from X2X_2 to XkX_k, as X2X_2 cannot be an ancestor of X1X_1, as that would mean an almost directed cycle and the graph would not be MAG). Similarly, there is a path from Xk−1X_{k-1} to X1X_1. If X1→XkX_1 \rightarrow X_k, then there is an almost directed cycle formed by Xk−1↔XkX_{k-1} \leftrightarrow X_k, path from Xk−1X_{k-1} to X1X_1, X1→XkX1 \rightarrow X_k. A symmetric situation happens for Xk→X1X_k \rightarrow X_1. The case where either X1 -> X2, or Xk -> Xk-1 is allowed in the inducing path, but invalid in MAG can be ruled out by a similar argument, as it creates an almost directed cycle or a cycle. The last case that remains is that X1 <-> Xk, which we have truly overlooked and we fixed in the submitted version. Please also refer to Appendix G, where we discuss special cases in detail. This change also implies adding one term in the Inducing Paths constraint.

Q2: Figure 6

Figure 6 was left out for space reasons; we have now moved it to the main paper body and added a brief introduction to the existing analysis in the first and second paragraphs of the “Experimental results” subsection.

Q3: Constraint counts.

We now record the number of lazy cuts of each type and the model size. The numbers below come from our re-run of 540 instances: the six generators BF-0.4-0.3, BF-0.2-0.15, 3BF-0.4-0.3, 3BF-0.2-0.15, ER-2 and ER-3 (20 % of the variables hidden), d ∈ {5, 10, 15, 20, 25}, n ∈ {50, 100, 500, 1000} and 5 random seeds each (without the combinations that do not exist: ER-3 with d = 5, and BF-0.4-0.3 with d ≥ 20, for which the MAG generator accepts no graph), all with λ = 1 and a time limit of 7,200 s. The structural part stays small: the initial model has 6d(d−1) + nd linear and nd quadratic constraints (d = 25, n = 50: 4,850 and 1,250), and the solver adds at most a few hundred cuts, almost all of them directed-cycle cuts (e.g. d = 10, n = 50: on average 287 cycle, 17 almost-directed-cycle and 2.1 inducing-path cuts); inducing-path cuts were needed in only 36 of the 540 runs. The exponential families of constraints are thus indeed avoided. However, the re-run also shows that these numbers are small partly because the solver explores few nodes for larger d, and that the bottleneck is the continuous, n-dependent part of the model rather than the number of structural constraints. For comparison, ip4ancadmg with the bounds used in the paper enumerates on average 4,595 candidate columns for d = 10, 24,454 for d = 15 and 176,918 for d = 25 before solving, each requiring a score computation. The exponential families of structural constraints are thus indeed avoided, but the re-run also shows that this alone does not make ExMAG fast: the bottleneck is the non-convex continuous part of the model (Reviewer moG4, Q3).

Q4: Could the authors justify the selected time limits (7,200s for the proposed method and 1,800s for the baselines)? It is claimed that the baselines typically finish well within this limit, how many timed out?

ExMAG is an anytime branch-and-cut method: because the dual bound of the non-convex MIQP does not close (see Reviewer moG4, Q3), it always runs until the time limit, while good incumbents appear earlier (Appendix C). We chose 7,200 s as the budget after which the incumbent rarely improves. For the baselines, 1,800 s was a safety cut-off for non-responsive runs. FCI never timed out (median 2.5 s, maximum 84 s), while ip4ancadmg found no solution within 1,800 s on 23 of the 540 instances (all with d = 25) and stopped at the limit with a solution not proven optimal on 97 more.

Q5: Could the authors justify how the baselines were selected? Specifically, why were several MAG estimation methods cited in Sec 1 as existing works (line 77) excluded from the experiments (e.g., Rantanen et al, 2021)?

We compare with the methods that solve the same problem by integer programming over MAGs/ADMGs with a linear-Gaussian score — ip4ancadmg (Chen et al., 2021) and its successor ipbm (Dash et al., 2025), the current state of the art of this line — and with FCI as the standard constraint-based method. We explained this choice in the updated paper.

Thank you for the response and clarification. The endpoint-adjacency issue is resolved, and the constraint counts are helpful. However some concerns remain:

  1. The sample-efficiency claim is not supported. Figure 3 does not show comparable quality with “an order of magnitude fewer samples”. It shows that the evaluated methods are comparable at the same small n values. The claim should be restated or removed.

  2. The time budgets are not comparable. ExMAG is given 7,200 s and the baselines 1,800 s. The ip4ancadmg runs that hit the limit may well have found or improved solutions with the longer budget, and no justification for this time budget is given for ipbm. It would be helpful to provide results under equal time budgets. Also, the paper should state the longer runtime of ExMAG as a limitation.

Due to the above points, I am keeping my original score.

Reviewer_E5GuOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes ExMAG, an optimization-based method for learning maximal ancestral graphs from observational data with latent confounders. It combines a residual-based fitting objective with sparsity regularization and uses Gurobi with dynamically added constraints to enforce acyclicity, ancestrality, and maximality. The method is evaluated on synthetic graphs with an additional financial-data application. The experiments assess structural recovery and runtime, reporting advantages in some small-sample settings.

Critical strengths

The paper presents an optimization framework for learning MAGs with latent confounders. It integrates graph checks into the solver and adds structural constraints as needed, avoiding the need to list all such constraints in advance.

Critical weaknesses

Appendix H relates WBW_B to the residual precision matrix. The main text treats WB,ij≠0W_{B,ij}\neq 0 as indicating a bidirected edge between ii and jj. These are not generally equivalent. The paper does not explain why this correspondence is valid. This raises concerns about the correctness of the proposed method. The results in Appendices A and B do not show a consistent advantage over the baselines. The authors acknowledge that performance gets worse as the sample size increases on some datasets. The method also takes longer to run than the baselines. These results raise concerns about its effectiveness and practical usefulness.

Questions for authors

Why does WB,ij≠0W_{B,ij}\neq 0 indicate a bidirected edge between ii and jj? Appendix H relates WBW_B to the residual precision matrix. How does this support the interpretation used in the main text?

How does the inducing-path constraint account for the requirement that the endpoints are nonadjacent? Adding an edge between the endpoints may produce a valid MAG without removing the inducing path. Does the proposed constraint exclude such valid graphs?

How is Jdual(y∗)J_{\mathrm{dual}}(y^*) in Equation (25) obtained for ExMAG? Please explain how this value is computed and updated during optimization.

Please clarify the meaning of the parameters in labels such as BF-0.4-0.3 in the figure captions.

Section 6 states: “In cases when the ground-truth weight matrix W is known, the best solution (in terms of structural Hamming distance, see below) is kept over those defined by different threshold δ values.” Does this mean that δ\delta is chosen to minimize SHD against the true graph? Is a fixed threshold used for evaluation? How should the threshold be selected in practice when the true graph is unknown?

2 comments

Q1: Why does indicate a bidirected edge between and ? Appendix H relates to the residual precision matrix. How does this support the interpretation used in the main text? These are not equivalent in general. The off-diagonal support of W_B is the support of the residual precision matrix (Appendix H, Eq. 20), while the bidirected edges of a MAG are the support of the residual covariance beta. They coincide exactly when every district is complete; otherwise the precision support is a superset within districts. Please see our answer to Reviewer moG4 (W1/Q1) for the derivation. We will state the assumption explicitly and no longer present W_B ≠ 0 as equivalent to a bidirected edge in general.

Q2: How does the inducing-path constraint account for the requirement that the endpoints are nonadjacent? Adding an edge between the endpoints may produce a valid MAG without removing the inducing path. Does the proposed constraint exclude such valid graphs?

Adding a directed edge between the endpoints causes the graph to contain a cycle forbidden by the MAG properties, and thus no such valid MAG exists. However, we have omitted a case when there is a bidirected edge between the endpoints, which might be an MAG. We have updated the pseudocode and the attached code. Please see our response to ZNTX, where we state in detail the proof that the directed edge between the endpoints can never happen in a MAG.

Q3: How is in Equation (25) obtained for ExMAG? Please explain how this value is computed and updated during optimization. The MIPGAP calculates the relative difference of the objective function value of the current best solutions of the program, and the current best lower bound on the optimum of the cost function JJ. For ExMAG the relaxation at a node relaxes the binary edge variables to [0, 1] and replaces each bilinear term R_ik · w^B_kj by its McCormick envelope over the current variable bounds (spatial branching, NonConvex = 2). For ExMAG the bound stays close to the regularisation term, so the gap stays close to 1 (see Reviewer moG4, Q3). From the ExMAG perspective, the bound is computed and updated automatically by Gurobi (as for any solved (mixed) integer linear/quadratic program) without any need for interference from our code. We have added this explanation after the equation. Please note that the original formulation contained a typo - instead of the boud, it contained a dual solution, which is something else.

Q4: Please clarify the meaning of the parameters in labels such as BF-0.4-0.3 in the figure captions.

The first number is the probability of a directed edge i -> j for every pair i < j (the vertex order is a topological order); the second is the probability of a bidirected edge for a pair without a directed edge (so its unconditional probability is 0.6 · 0.3 = 0.18). 3BF additionally limits every vertex to three arrowheads (parents plus spouses). We added this to the dataset description.

Q5: Section 6 states: “In cases when the ground-truth weight matrix W is known, the best solution (in terms of structural Hamming distance, see below) is kept over those defined by different threshold δ values.” Does this mean that is chosen to minimize SHD against the true graph? Is a fixed threshold used for evaluation? How should the threshold be selected in practice when the true graph is unknown?

The final program often results in near-zero edge weights. Those values are caused by the numeric solver using floating-point numbers in place of integers. Internally, we calculate the results with the default of numerical tolerance 10^{−3} - to remove just the numeric errors; we also calculate the results with a fixed δ = 0.3, and the oracle choice of delta. The threshold can be then set from expectations on the graph density - larger threshold means fewer edges, while smaller means more edges. Note that FCI, ip4ancadmg and ipbm return unweighted graphs and were never thresholded.

Thank you for the comments. It remains unclear whether the omission in the inducing-path constraint has been correctly addressed. This is essential to ensuring that the formulation does not exclude valid MAGs. Moreover, your explanation of WBW_B does not adequately justify interpreting its nonzero entries as bidirected edges in general. These concerns remain substantive, and I therefore keep my score.

Reviewer_moG4OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes ExMAG, a method for learning maximally ancestral graphs (MAGs) by formulating the problem as a mixed-integer quadratic program (MIQP). The method uses branch-and-bound and lazy constraint generation to handle directed cycles, almost directed cycles, and inducing paths. Experiments are conducted on several synthetic datasets and a real-world financial dataset. The authors report that ExMAG achieves competitive structure recovery with relatively few samples. However, the statistical foundations of the model, the experimental evaluation protocol, and the scalability of the approach require further examination.

Critical strengths
  1. MAGs represent relationships involving latent confounders through directed and bidirected edges, making them a useful framework for causal structure learning when not all variables are observed.
  2. ExMAG formulates MAG learning as an MIQP and uses lazy constraint generation to handle graph-structural restrictions, avoiding the need to explicitly include all constraints in the initial model.
  3. The paper evaluates different graph sizes, sample sizes, and graph densities, compares ExMAG with several existing methods, and includes an application to real-world financial data.
Critical weaknesses
  1. Insufficient justification for bidirected edge weights. The paper defines ββ as the residual covariance matrix and derives WBW_B from it, relating its sparsity to conditional independence. However, the connection between this relationship and bidirected edges in a MAG remains unclear.

  2. Unclear synthetic data construction. The BF and 3BF datasets use the bidirected-edge adjacency matrix as the noise covariance matrix, but the paper does not explain how positive semidefiniteness is ensured. The construction of the ground-truth MAG after hiding 20% of the variables in the ER dataset is also unclear.

  3. Potential bias in evaluating sample efficiency. The paper selects edge-weight thresholds based on ground-truth SHD and highlights the best results across sample sizes. This reliance on ground-truth information may overstate practical performance and weakens the evidence for the claimed sample-efficiency advantage.

  4. Limitations of the financial data evaluation. The matrix (F) prohibits directed edges between companies in different sectors, potentially preventing the recovery of cross-sector causal relationships, despite their relevance to the paper's motivation. The lack of a ground-truth MAG further limits quantitative validation.

  5. Unclear baseline comparison protocol. FCI outputs a PAG, whereas other methods output MAGs, but the paper does not explain how uncertain edge endpoints are handled when computing SHD. Moreover, ip4ancadmg and ipbm are evaluated only on 3BF graphs with maximum in-degree three, limiting the scope of the comparison.

  6. Insufficient theoretical and computational validation. The paper does not clearly establish the identifiability conditions for MAGs under correlated residuals, and experiments cover at most 25 variables. Additionally, Algorithm 4 sets MIPGap$=0.1$, while the supplementary material reports a final gap slightly below 1.0. This discrepancy requires clarification.

  7. Minor Comments: a. Unresolved citation placeholder. On page 3, the definition of an inducing path contains the placeholder (?Zhang). The authors should replace it with the appropriate reference. b. Figure readability. Figures 2 and 3 contain small subplots, axis labels, and legends, making some of the results difficult to read. The authors should consider enlarging the figures or splitting them into separate panels to make comparisons across experimental settings easier. c. The contributions are not clearly summarized. The introduction describes the MIQP formulation and the use of lazy constraints, but it does not clearly distinguish the individual contributions or explain how they differ from existing MAG learning methods. A concise summary of the main contributions at the end of the introduction would help clarify the paper's novelty.

Questions for authors
  1. Given that WBW_B is derived from the residual covariance matrix, can the authors provide a more rigorous explanation of the theoretical relationship between its sparsity pattern and bidirected edges in a MAG? What assumptions are required for this correspondence to hold?
  2. How exactly are the noise covariance matrices constructed for the BF and 3BF datasets? For the ER dataset, how do the authors determine the ground-truth MAG over the observed variables after hiding the latent variables?
  3. Could the authors report structure recovery results using prespecified sample sizes and parameter-selection rules, rather than selecting thresholds based on the ground-truth SHD? Could they also explain the discrepancy between MIPGap$=0.1$ and the final MIP gap being close to 1.0?
1 comment

Q1: Given that is derived from the residual covariance matrix, can the authors provide a more rigorous explanation of the theoretical relationship between its sparsity pattern and bidirected edges in a MAG? What assumptions are required for this correspondence to hold?

We thank the reviewer for this question, and we agree that the main text overstates the correspondence. For fixed W_D the residuals are R = X(I − W_D), and at the true W_D the population residuals with covariance β. Minimising Eq. (3) over the j-th column of W_B is the regression of R_j on R_{−j}, whose population solution is w_{·j} = β_{−j,−j}^{−1} β_{−j,j}. Hence (W_B){lj} ≠ 0 iff β^{−1}{lj} ≠ 0, i.e. iff the residuals of l and j are dependent given all other residuals; this is what Eq. (20) in Appendix H states. In a linear Gaussian MAG, on the other hand, l <-> j is absent iff β_{lj} = 0. The two supports coincide when every district (connected component of the bidirected part) is complete, because then β and β^{−1} are block-diagonal with full blocks. For an incomplete district, β^{−1} is generically dense within the district, so supp(β^{−1}) is a strict superset of supp(β) within the district. The population fit can be improved by bidirected edges between non-adjacent members of the same district. Many of these pairs cannot be realized anyway, because they are joined by a directed edge (E + B ≤ 1) or are ancestrally related (the ancestrality cuts forbid them), and the sparsity penalty removes those whose contribution to the fit is small. We quantified this on our generators (10 random MAGs per setting). In agreement with the above, supp(β^{−1}) = supp(β) holds exactly for the instances whose districts are complete: 70–80 % of the graphs with d = 5, 0–30 % with d = 10, and almost none for d ≥ 15 (e.g. 3BF-0.2-0.15, d = 20: 10.6 bidirected edges, 25.3 additional non-zeros of β^{−1}, 3.3 of them not representable).

Q2: How exactly are the noise covariance matrices constructed for the BF and 3BF datasets? For the ER dataset, how do the authors determine the ground-truth MAG over the observed variables after hiding the latent variables?

Noise covariance (BF/3BF). Both datasets are generated in the same way. 3BF additionally limits every node to at most three arrowheads. The noise covariance Ω is sparse and follows the bidirected edges of the generated MAG. For each edge, the corresponding field is drawn uniformly from [−2, −1) ∪ [1, 2), and all other off-diagonal entries are zero. Each diagonal entry is Ωii = u + 0.7 + Σ{j≠i} |Ωij| with u ~ U(0.7, 1.2). This makes Ω strictly diagonally dominant and therefore positive definite. The noise is sampled as ε ~ N(0, Ω).

Ground truth (ER). The data are simulated from a linear Gaussian SEM on an Erdős–Rényi DAG, and 20% of the variables are then hidden at random. The ground truth directed part is the subgraph of the original DAG induced on the observed variables. Its bidirected part is random: each pair of observed variables that are non-adjacent in that subgraph receives an edge with probability 0.2, and the pair is also recorded as a tabu edge.

Q3: Could the authors report structure recovery results using prespecified sample sizes and parameter-selection rules, rather than selecting thresholds based on the ground-truth SHD? Could they also explain the discrepancy between MIPGap and the final MIP gap being close to 1.0?

Threshold: The final program often results in near-zero edge weights. Those values are caused by the numeric solver using floating point numbers in place of integers. Internally, we calculate the results with the default of numerical tolerance 10^{−3} - to remove just the numeric errors; we also calculate the results with a fixed δ = 0.3, and the oracle choice of delta. Note that FCI, ip4ancadmg and ipbm return unweighted graphs and were never thresholded.

MIP GAP: MIPGap = 0.1 in Algorithm 4 is Gurobi's termination tolerance (stop when (UB − LB)/UB ≤ 0.1); the value close to 1 in Appendix C is the gap actually reached, so the tolerance is never met and ExMAG always stops at the time limit. The reason is that Eq. (3) multiplies continuous variables (the residual R_ik, which is linear in W_D, by w^B_kj), so the MIQP is non-convex and Gurobi bounds it through spatial branching with McCormick relaxations of the bilinear terms. With the big-M formulation and unbounded residuals these relaxations carry almost no information on the least-squares term, and the dual bound stays at the value of the regularisation term.

For the rebuttal, we run 540 experiment settings (see our response to ZNTX Q3) where the median ratio bound/incumbent is 0.0000 and the median final gap 1.0000 (536 runs stop at the time limit, 4 small instances with d = 5 are solved to optimality). The returned graph is always a MAG, but its global optimality is not certified. We updated the explanation and the supplementary materials with a brief explanation of this behavior.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.