API reference

andrey.markov_check#

andrey.markov_check(graph, data, *, indep_test=None, alpha=0.05, categorical=None, sample_fraction=0.5, seed=None)[source]#

Test whether the independences a DAG or CPDAG implies hold in the data.

A graph implies independences: for a DAG, each variable is independent of every variable that comes earlier in a topological order and is not its parent, given its parents (the ordered local Markov property [1]). The check tests each one, a pair of variables and their conditioning set, with a conditional-independence test, and asks whether the p-values are uniform on (0, 1), as they are when every tested independence holds: the Anderson-Darling test of uniformity, with Marsaglia and Marsaglia’s p-value [2]. A small uniformity p-value, at most alpha, rejects the graph together with the test’s assumptions [1]. A CPDAG is checked through a DAG of its class, which implies the same independences. The number of tests is d (d - 1) / 2 minus the number of edges for d variables.

Use rows the graph was not learned from [1]: a graph fitted to the same rows can pass because the fit made its independences true there. Split the rows, learn on one half and check on the other.

Parameters:

  • graph (StructureOutput | GraphStructure) – The graph to check, of kind dag or cpdag: a method’s result, or its structure. A PAG, MAG, undirected, or cyclic graph, and a time-series result, raise ValueError (the check is validated for a DAG or CPDAG [1]).

  • data (ArrayLike) – The data to check against, as the methods take it. When the graph and the data both have labels (a DataFrame’s column names), a node is read from the column of its label and the two must name the same columns; otherwise the n-th node is the n-th column, and the counts must agree. Missing values (NaN) are deleted test by test, assuming they are missing completely at random.

  • indep_test (str | None) – The conditional-independence test, as pc takes it. None picks from the declared column types: "gsq" when every column is categorical, "cond_gauss" when some are, else "fisherz". metadata["indep_test"] names the one used. See Notes.

  • alpha (float) – The level of the uniformity test, in (0, 1), and the level at which share_dependent counts a p-value as small.

  • categorical (Sequence[str | int] | None) – The categorical columns, by label or 0-based position, as the methods take them; None reads them from a DataFrame’s category, bool, and text columns, and [] declares none.

  • sample_fraction (float) – The share of the rows each test reads, in (0, 1]: a random subset drawn without replacement for each test, so that the tests do not all read the same rows [1]. 1.0 reads every row in every test. See Notes. The same meaning as in bootstrap().

  • seed (int | None) – The seed of the row draws and of the randomized tests, a non-negative integer. None uses ANDREY_SEED, or 0 when it is unset, so a check repeats.

Returns:

The uniformity p-value, the verdict passed, and the p-value of every tested independence (table()). metadata records indep_test, seed, sample_fraction, rows_per_test, the topological order that fixed the independences, and rows_tested when missing values were deleted.

Return type:

MarkovCheckOutput

Raises:

ValueError – If graph is not a DAG or a CPDAG that has a DAG, if the graph and the data disagree on the columns, if an argument is out of range, if a test would read fewer than the conditioning set size plus four rows, or if a test returns a p-value outside [0, 1].

Warns:

SampleSizeWarning – With a categorical test ("gsq", "chisq") that reads a table with fewer than 5 rows per cell: the test then rejects true independences more often than alpha, so a rejection is not evidence against the graph. See Notes.

Notes

Rows per test. The tests read the same data, so their p-values are uniform one by one but not independent, and the Anderson-Darling p-value assumes independence. With every test on every row (sample_fraction=1.0, the script of [1] and the default of Tetrad), the check rejected a true graph in 9% to 21% of 1,000 simulated linear datasets per cell at alpha=0.05, more with more tests (10 and 20 variables, average degree 2 and 4, 200 and 1,000 rows). With each test on its own random half of the rows (the default, as in the text of [1]), the rate was 6% to 9%, and with each test on new rows it was 5%. A subsample costs power: one missing edge was rejected in 96% to 99% of the datasets at 1,000 rows (98% to 100% on all rows) and in 72% to 82% at 200 rows (89% to 93%). The verdict also depends on seed, because the row draws do.

The uniformity p-value. The Anderson-Darling p-value is exact for one tested independence. For two or more it is Marsaglia and Marsaglia’s approximation [2], which was within 0.002 of the level at 0.01, 0.05, and 0.2 in 200,000 or more simulated sets of uniform p-values for each of 2 to 400 independences, and looser in the middle of its range (off by up to 0.017 at two).

What a pass shows. A graph with extra edges also passes, since an added edge removes independences without making any other false, so a pass is not evidence that the edges are right [1]; compare graphs of the same data by the check and by their number of edges. Missing edges and wrongly oriented v-structures are rejected. Which independences are tested follows a topological order broken by the nodes’ labels (their positions without labels), so the order that fixed them is in metadata["order"].

Tests on categorical data. The G-square test ("gsq") and the chi-square test ("chisq") reject true independences more often than alpha on tables with few rows per cell, so the check does too: with 3 to 5 categories per variable and 500 to 2,000 rows, 69% to 86% of the true graphs were rejected, and with 2 to 3 categories, 24% at 500 rows, 12% at 2,000, and 10% at 5,000. A warning names the case. A mixed-data or kernel test is allowed and was not measured; a test whose p-values are discrete or concentrated at 1 departs from the uniform distribution the check assumes.

Limitations. Measured on linear data with Gaussian and uniform noise simulated on random graphs (10 to 40 variables, average degree 2 and 4, 200 to 2,000 rows, "fisherz"), at alpha=0.05, with every test on all rows unless noted. A graph in the true graph’s equivalence class passes, as it must: reversing an edge without changing the CPDAG was rejected in 0% to 24% of the datasets in cells of 25 or more, and a reversal that changes it in 70% to 100%. Two extra edges were rejected in 6% to 20%, the rate of the true graph. The DAG of the observed variables of a model with hidden confounders was rejected in every one of 500 datasets. pc outputs were rejected in 57% to 70% of the datasets (89% to 94% when an adjacency was missing, 15% to 26% when none was); ges outputs near the rate of a true graph, since its misses are weak edges whose loss leaves no detectable independence; and direct_lingam outputs on Gaussian data near that rate too. Many tests dilute one false independence: one missing edge among 740 tests (40 variables) was rejected in 75% to 80% of the datasets, against 97% to 100% among 35 to 170. The pairwise tests miss a dependence that shows only in a set of variables [1], and a test misses a dependence it cannot see, such as "fisherz" on a nonlinear one, so the check misses that missing edge too. The check was not measured on data with mixed types, on small categorical tables beyond the cases above, or for effect sizes.

References

Examples

>>> import numpy as np
>>> from andrey import GraphStructure, markov_check
>>> rng = np.random.default_rng(0)
>>> a = rng.standard_normal(500)
>>> b = a + rng.standard_normal(500)
>>> c = b + rng.standard_normal(500)
>>> data = np.column_stack([a, b, c])
>>> chain = GraphStructure.from_numpy(
...     np.array([[0, 1, 0], [2, 0, 1], [0, 2, 0]]), kind="dag", labels=("a", "b", "c")
... )
>>> markov_check(chain, data, sample_fraction=1.0).passed
True