- 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
Thank you for the response and clarification. The endpoint-adjacency issue is resolved, and the constraint counts are helpful. However some concerns remain:
-
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.
-
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.
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↔⋯↔Xk. Here, X2 needs to be an ancestor of Xk (ie, there is a path from X2 to Xk, as X2 cannot be an ancestor of X1, as that would mean an almost directed cycle and the graph would not be MAG). Similarly, there is a path from Xk−1 to X1. If X1→Xk, then there is an almost directed cycle formed by Xk−1↔Xk, path from Xk−1 to X1, X1→Xk. A symmetric situation happens for Xk→X1. 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.
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.
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).
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.
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.