# Analyzing Markov Boundary Discovery Algorithms in Ideal Conditions Using the d-Separation Criterion
## 1 Introduction  
Researchers often need to extract the causal information contained within large datasets comprising of many variables and samples [1]. Causal information is usually inaccessible, but extremely useful for producing new knowledge and encoding it for human or machine consumption, or for reducing the dimensionality of the dataset itself for further applications. These are the goals of causal inference and feature selection, respectively. Either way, one of the most fundamental encodings of causal information is the Bayesian network [2]. A Bayesian network is a directed acyclic graph where nodes represent the variables of the dataset and the edges represent dependence relationships between the variables. It must be emphasized that the absence of an edge between two specific nodes does not imply their independence. To determine independence correctly, the directional separation criterion (d-separation) must be applied instead [2]. This criterion only requires the analysis of paths between nodes in the network to determine whether two variables are independent or not given a subset of other variables. Knowing the Bayesian network that underlies an observed dataset is ideal in research, but it is rarely available. A straightforward method of discovering the Bayesian network from a dataset is to discover the Markov boundaries of a sufficient number of individual variables in the dataset, then connecting these boundaries together, thus assembling the underlying network itself [2]. Algorithms that analyze the independence relationships between the variables of a dataset with the explicit goal of discovering their Markov boundaries are plainly calledMarkov Boundary Discovery (MBD) algorithms [3]. In broad terms, MBD algorithms work by performing many conditional independence (CI) tests on permutations of variables from the dataset in order to find the variables that compose the boundary of a specific variable of interest. This involves steps such as detecting candidate variables for the boundary, then removing any false positives from the candidates. MBD algorithms usually rely on statistical conditional independence tests [4; 5; 6; 7] such as the \(\chi^{2}\) test or the G-test, but some algorithms use heuristics that stand as a proxy for conditional independence [8; 9]. This article is concerned with the methodological process of evaluating and validating MBD algorithms. Specifically, it focuses on the source of independence information consumed by such an algorithm during its operation. When the behavior of an MBD algorithm of interest is evaluated on an actual dataset, it requires a statistical CI test or a heuristic. The final accuracy and efficiency of the algorithm are affected by the accuracy and efficiency of the tests or of the heuristic, which are in turn affected by multiple other factors, such as:  
* the total number of samples in the entire dataset;
* the number of values taken by the variables;
* the number of samples recorded in the dataset for various combinations of values. In other words, datasets can contain unintentional biases which can distort the evaluation and validation of an MBD algorithm when relying on a statistical CI test. This is obviously true for both synthetic or sampled datasets. Moreover, performing statistical CI tests consumes an overwhelming proportion of the computing resources used in total by the algorithm [10]. If available in such cases, an efficient implementation of the CI test is essential for providing quick feedback to the researcher. This article proposes a methodological alternative to help address these issues: instead of using statistical tests computed on synthetic data generated from the Bayesian network, the studied MBD algorithm can be provided with ideal information on conditional independence by using the d-separation criterion [2] computed directly on the Bayesian network, effectively replacing the statistical test.