Searching for Bayesian Network Structures in the Space of Restricted Acyclic Partially Directed Graphs

• Conditional-independence approaches use test-derived relationships to construct graphs, while test count and complexity drive costs and can cause unreliable results.Source: §1 · p. 2
• The DAG-to-equivalence-class count ratio is below four, while losing decomposable scoring makes equivalence-class search algorithms less efficient.Source: §1 · p. 3
• The authors introduce restricted acyclic partially directed graphs (RPDAGs) as a search space related to DAG equivalence classes, and define a local-search algorithm within it.Source: §1 · p. 3
• With a decomposable scoring function, neighboring RPDAGs can be scored locally, yielding an efficient algorithm that retains many advantages of equivalence-class search.Source: §1 · p. 3

1. Introduction

• The proposed method is designed to evaluate RPDAGs efficiently using a decomposable scoring function.Source: §1 · p. 3
• The proposed algorithm is experimentally evaluated on Alarm (Beinlich, Suermondt, Chavez & Cooper, 1989), Insurance (Binder, Koller, Russell & Kanazawa, 1997), Hailfinder (Abramson, Brown, Murphy & Winkler, 1996), UCI repository databases, and compared empirically with other state-of-the-art learning algorithms.Source: §1 · p. 3
• The paper concludes with remarks and proposals for future work in Section 7.Source: §1 · p. 3

2. DAGs and Equivalence Classes of DAGs

• Standard local DAG search uses arc addition, deletion, and reversal, while decomposable scores factor into local scores for a node and its parents.Decomposability supports efficient local-search evaluation because only scores for changed parent sets need recomputation.Source: §2 · p. 4
• Score-equivalent scores assign identical values to equivalent DAGs, motivating search over reduced equivalence classes rather than redundant structures.The section presents this as a way to avoid generating and evaluating equivalent DAGs.Source: §2 · p. 5
• Two DAGs are equivalent if and only if they have the same skeleton and the same v-structures, as characterized by Pearl & Verma (1990).A skeleton ignores edge directions; a v-structure is x → y ← z with x and z nonadjacent.Source: §2 · p. 5
• The equivalence-class space is smaller and may improve results for the same search effort, but its size-to-DAG ratio is reported to asymptote empirically to 0.267.The section also expects efficiency gains from avoiding the generation and evaluation of equivalent DAGs.Source: §2 · p. 5
• Class-space search can make neighbor generation costlier through consistency checks and can make evaluation more expensive when score decomposability cannot be exploited.It may also introduce local maxima absent from DAG space.Source: §2 · p. 6
• Equivalence classes are commonly represented by acyclic partially directed graphs (PDAGs), which contain directed and undirected edges but no directed cycles.The passage introduces PDAGs as graphical objects for representing DAG equivalence classes.Source: §2 · p. 6

2. D A Gs and Equiv alen e Classes of D A Gs

• A completed PDAG canonically represents a DAG equivalence class with directed compelled arcs and undirected links for reversible arcs, and completed PDAGs correspond one-to-one with classes.A reversible arc is one that is not compelled and can be reversed in an equivalent DAG.Source: §2 · p. 6
• A PDAG is completed exactly when it has no partially directed cycles, chordal chain components, no induced x→y←z configuration, and every directed arc occurs in one of four specified configurations.The four configurations are displayed in Figure 2.Source: §2 · p. 7, Figure 2 · p. 7
• The three-node example groups four DAG configurations into two equivalence classes, reducing the search space, though the savings are not spectacular and the ratio approaches less than four.The passage gives DAG-to-class ratios of 25/11, 543/185, and 29281/8792 for three, four, and five nodes, respectively.Source: §2 · pp. 7–8, Figure 3 · p. 8, Figure 4 · p. 8
• Adding links when arc directions are indistinguishable avoids prematurely pruning configurations that may contain the true DAG, a failure illustrated by a DAG-space local-search trap.In the example, an early direction choice excludes the true structure, and subsequent local changes cannot improve the score.Source: §2 · pp. 8–9
• In the example, adding the link x|y and then selecting the higher-scoring h-h pattern z→x—y yields the correct DAG.The alternative pattern z|x|y receives a lower score.Source: §2 · p. 9

3. Restricted Acyclic Partially Directed Graphs

• RPDAGs can represent an equivalence class by different RPDAGs in some cases, a deliberate choice that improves efficiency in exploring the search space.RPDAGs exclude directed cycles and completely undirected cycles, meaning cycles containing only links.Source: §3 · pp. 9–10
• Every RPDAG has at least one DAG extension, and all its extensions are equivalent because they share a skeleton and v-structures.An extension preserves the RPDAG’s skeleton and directed arcs and introduces no new h-h patterns.Source: §3 · p. 10
• For any PDAG satisfying RPDAG conditions 1–3, there is a unique RPDAG whose extension set contains the PDAG’s extensions.The construction repeatedly undirects arcs whose source has no parents.Source: §3 · p. 11
• Distinct RPDAGs have disjoint extension sets, and every DAG belongs to an RPDAG extension set, so these sets partition the DAG space.The section also states that two DAGs belong to the same RPDAG extension set exactly when they have the same skeleton and h-h patterns.Source: §3 · pp. 11–12

3.1 Restri ted PD A Gs and Completed PD A Gs

• Every RPDAG represents an equivalence class, but a class can have multiple RPDAGs; CPDAGs instead provide a one-to-one representation of equivalence classes.The paper illustrates three RPDAGs for one class, whose completed PDAG is a CPDAG; that class contains 12 DAGs.Source: §3.1 · p. 13
• RPDAG chain components are trees, unlike CPDAGs, which may contain undirected chordal cycles; an RPDAG can be formed from a CPDAG by orienting links to obtain tree components.The paper also states that the number of DAG extensions of an RPDAG is the product of the node counts of its chain components, since each tree can be directed by choosing a root.Source: §3.1 · p. 14
• The number of RPDAG representations of a class grows exponentially with the size of undirected cliques in its CPDAG.A search using RPDAGs need not explore every equivalent representation.Source: §3.1 · p. 14
• RPDAGs lack clear semantics: they represent sets of equivalent DAGs sharing causal patterns where effects have at least two causes, while single-cause effects may remain undetermined.This limitation is not problematic for model selection, but makes assigning priors for model averaging difficult.Source: §3.1 · p. 14
• Testing whether a PDAG is an RPDAG is easier than testing whether it is a CPDAG, trading unique class representation for more manageable consistency checks.The RPDAG check avoids the CPDAG checks for chordality and whether each arc belongs to a specified induced subgraph; a search may consequently evaluate an equivalence class more than once.Source: §3.1 · p. 14

4. The Search Method

• The search usually starts from an empty RPDAG corresponding to an empty DAG, but prior knowledge about edges or v-structures can motivate another starting configuration.Source: §4 · p. 15

4.1 Overview

• Neighborhood moves add a directed or undirected edge between nonadjacent nodes or delete an existing edge; reversals are excluded, and additions can yield multiple neighbors depending on topology and direction.Deleting an edge always yields one neighboring configuration.Source: §4.1 · p. 15

4.2 Neighboring Configurations

• Determining possible neighboring configurations from an edge addition or removal requires only local parameters of the two endpoint nodes.The paper introduces notation and properties of RPDAGs to support this systematic determination.Source: §4.2 · p. 16

4.2.1 Adding Edges

• Seven decision-tree states reduce to five distinct cases, using local properties of the endpoint nodes to enumerate configurations produced by adding an edge.The decision tree’s tests include endpoint parent and neighbor counts.Source: §4.2.1 · pp. 16–18, §4.2 · p. 16
• After generating edge additions, the algorithm completes orientations in a cascade to preserve RPDAG conditions and rejects candidates that create directed or completely undirected cycles.The cascade begins with links adjacent to the newly introduced arc.Source: §4.2.1 · p. 19

4.2.2 Deleting Edges

• Deleting either a link or an arc is described as much simpler than adding an edge.Source: §4.2.2 · p. 20
• Deleting an arc requires no directed- or undirected-cycle test, but may require converting arcs to links to preserve RPDAG condition 4.After deleting x→y, eligible children of y are recursively converted to neighbors; in one case, u→y must also become a link.Source: §4.2.2 · p. 20

4.3 The Operators

• The five operators are arc addition, link addition, arc deletion, link deletion, and hh addition, which adds an arc and transforms a link into an arc.Their application conditions are given in Table 2, and some operators require post-processing to ensure the resulting configuration is an RPDAG.Source: §4.3 · pp. 20, 22
• Cycle checks can be performed without inserting the candidate edge or h-h pattern by checking for specified paths in the current RPDAG.The link check looks for a path formed exclusively by links; directed-cycle checks look for a path from y to x using links or arcs directed away from y.Source: §4.3 · p. 22

5. The Exploring Pro ess and the Ev aluation of Candidate Stru tures

• A simpler approach—selecting a representative DAG extension and scoring it—can be inefficient because it requires recomputing local scores for all nodes.The passage notes that this can make equivalence-class search considerably slower than searching DAGs, as in Chickering (1996).Source: §5 · p. 23
• The method evaluates RPDAGs directly and scores each neighbor with at most two local scores, avoiding conversion to a DAG while retaining DAG-search advantages.The two-local-score bound applies to decomposable score-equivalent scoring functions.Source: §5 · p. 23
• The score of a neighboring RPDAG can be obtained from the current structure’s score by computing only two local scores.Some of these local scores may already have been computed in earlier search iterations.Source: §5 · p. 25
• The score-change derivation uses score equivalence and decomposability, then considers five cases for evaluating candidate structures.The supplied passage fragments enumerate cases (a)–(e) and apply local parent-set terms, but do not preserve enough notation to report the resulting equations.Source: §5 · pp. 26–27

5.1 Comparison with Other Approa hes

• Unlike completed-PDAG search methods, the proposed method avoids PDAG-to-DAG and DAG-to-PDAG conversion procedures, using path tests and a simple cascading process to validate and generate RPDAG neighbors.The validity tests check for undirected or partially directed paths; neighbor generation directs links or undirects arcs starting from a single node.Source: §5.1 · pp. 27–28
• For many decomposable scoring functions, each RPDAG except the initial one can be evaluated by computing only two local scores; completed-PDAG methods generally need to recompute all local scores.Source: §5.1 · p. 28

5.1 Comparison with Other Approaches

• The algorithm has no duplicate representations of equivalence classes.Source: §5.1 · p. 28
• Whether CPDAG move costs offset the larger number of RPDAGs and local scores to compute is an empirical question that may depend on domain sparsity.The passage does not report a comparative result; it identifies sparsity of the specific domain problem as a possible factor.Source: §5.1 · p. 28

6. Exp erimen tal Results

• The experiments tested the algorithm on nine discrete-variable problems, comparing RPDAG-based and DAG-based local search.The problems included Alarm, Insurance, Hailfinder, Breast-Cancer, rx, Flare2, House-Votes, Mushroom, and Nursery.Source: §6 · pp. 28, 30

For the synthetic domains (Tables 3, 4 and 5)

• On all five synthetic databases, RPDAG search obtained better scoring-function results than DAG search, with larger differences on the non-logarithmic scale.The reported scores use a logarithmic version of the scoring function.Source: §6 · p. 32
• RPDAG search produced considerably lower Hamming distances than DAG-space search on the synthetic domains.Hamming distance counts added, deleted, and wrongly oriented edges relative to the gold-standard network.Source: §6 · p. 32
• RPDAG search was generally more efficient, using fewer iterations, evaluated individuals, database statistics, and total statistics, and running faster in most cases.The average number of variables involved in statistics was slightly greater in four cases.Source: §6 · pp. 32–33

For the UCI domains (Table 6)

• For the UCI domains, the results were less conclusive about the RPDAG method's effectiveness relative to DAG search.Source: §6 · p. 33

6. Exp erimen tal Results

• Across six cases, greedy RPDAG and DAG search matched on two, RPDAG won three and DAG one; neither clearly outperformed the other on efficiency measures.Source: §6 · p. 34
• Tabu search rarely improved RPDAG greedy results, while TS-DAG generally improved DAG results, except on two UCI databases and Alarm-3000.On the synthetic domains, TS-RPDAG and RPDAG matched in all but one Insurance database.Source: §6 · p. 35
• TS-RPDAG was preferred on synthetic domains, TS-DAG did better on Insurance, UCI outcomes split evenly with two ties, and TS-RPDAG ran somewhat faster.The UCI comparison found each algorithm better on two domains and equal on the remaining two.Source: §6 · pp. 35–36
• The KL measure requires caution because a high value may indicate overfitting, particularly for networks with many edges.Source: §6 · p. 37
• RPDAG-space search with BDeu was competitive; only TS-DAG, and to a lesser extent K2, performed better than RPDAG in some cases.The comparison included Alarm, Insurance, and Hailfinder, using BDeu, BIC, and KL-based measures.Source: §6 · p. 37

6. Experimental Results

• The different-test-set evaluation trained on Alarm-3000 and tested on the next 3,000 Alarm cases; for Insurance and Hailfinder, it used different databases for training and testing.The study computed BDeu, BIC, and KL values for learned structures against the separate test databases.Source: §6 · p. 38
• On a different test set, RPDAG performs better than TS-DAG and K2 in KL, and the results are analogous to those using the same databases for training and testing.The authors argue that this result means RPDAG’s good behavior cannot be attributed to overfitting.Source: §6 · pp. 38–39
• Under experimental conditions matching Chickering’s work, the study selected House-Votes and Mushroom, used BDeu with equivalent sample size 10 and structure prior 0.001, and used approximately 70% data subsets.Source: §6 · p. 39
• Both RPDAG and CPDAG are more efficient than DAG, although CPDAG appears to run faster than RPDAG.The authors caution that differences may reflect experimental setup and call for more systematic comparisons.Source: §6 · pp. 39–40
• RPDAG matches DAG’s solution on House-Votes and outperforms DAG on Mushroom, while CPDAG performs worse than DAG on Mushroom.The comparison averages RPDAG results across five datasets; the reported differences are small.Source: §6 · p. 40

7. Con luding Remarks

• The proposed local-search algorithm uses restricted PDAGs, a representation close to DAG equivalence classes, rather than searching directly in DAG space.This reduces the search space while retaining local scoring: with a decomposable score, each neighboring RPDAG can be evaluated using at most two local scores.Source: §7 · p. 40
• The search space avoids early edge-direction decisions, which may help guide search toward better network structures.The authors describe this as a potential benefit of the reduced, smoother search landscape.Source: §7 · p. 40
• PDAG-based search can obtain slightly better effectiveness and efficiency than DAG-based search, especially for highly structured models, but the reported results do not show significant improvement.The authors say such models can be almost perfectly represented by a DAG.Source: §7 · p. 40
• The authors propose PDAGs as potentially useful for complex domains with many variables and complicated dependence patterns, as well as sparse domains with many independence relationships.Source: §7 · p. 40
• Future work includes integrating the techniques with more powerful search methods, adding operators, and adapting the algorithm to classification problems.The proposed operators include classical arc reversal or a specialized operator for destroying h-h patterns.Source: §7 · pp. 40–41

A kno wledgmen ts

• The work was supported by Spanish national and regional research projects.Source: A kno wledgmen ts · p. 41
• The authors thank colleague José M. Puerta for help implementing several algorithms.Source: A kno wledgmen ts · p. 41
• The authors thank three anonymous reviewers for comments and suggestions.Source: A kno wledgmen ts · p. 41

References

• The list also includes application-focused work on the Alarm Monitoring System and probabilistic networks for severe-weather forecasting.The cited titles describe the Alarm Monitoring System as a case study and Hailfinder as a Bayesian system for forecasting severe weather.Source: Referen es · p. 41
• Other cited approaches include hybrid methods, independence criteria, ant-colony optimization, and genetic algorithms for learning Bayesian networks.The titles include methods for learning right-sized belief networks, using independence relationships, and searching over orderings or other spaces.Source: Referen es · pp. 41–43
• The references include work on Bayesian-network construction, structure search, and learning equivalence classes of network structures.Titles cover local search and search methods, alongside work on transforming and learning equivalent Bayesian network structures.Source: Referen es · p. 42
• The listed structure-learning work includes MDL-based methods, genetic algorithms, ordering search, and branch-and-bound.Examples include Lam and Bachus (1994), Larrañaga et al. (1996), Suzuki (1993, 1996), and Tian (2000).Source: Referen es · pp. 44, 46
• Other entries cover Bayesian model averaging, learning from incomplete data, and foundational works on Bayesian networks and information theory.The list includes Madigan et al. (1996), Ramoni and Sebastiani (1997), Herskovits (1991), Jensen (1996), Pearl (1988), and Kullback (1968).Source: Referen es · pp. 44–45
• The bibliography also includes work on causal models, causal polytrees, and learning Bayesian networks from data.Examples include Pearl and Verma (1990), Rebane and Pearl (1987), Huete and de Campos (1993), and Singh and Valtorta (1993, 1995).Source: Referen es · pp. 44–45