The tree structure of graphs for various graphical models

摘要

After proper decompositions or separations, there is a common characteristic of the secondary structures for various graphical models. In this paper, we show that the junction tree captures this common characteristic. To generalize all potential occurrences in different graphical models, we define junction trees on general set classes and show several equivalent properties of junction trees. For mixed graphical models and hierarchical models, we investigate in detail the M-decomposition of marked graphs and the H-decomposition of interaction graphs, and point out the junction tree structures of marked graphs and interaction graphs. Moreover, properties of separation trees and d-separation trees are discussed for undirected and directed graphs, respectively. Both separation and d-separation trees are closely associated with junction trees. Finally, we propose two algorithms for constructing junction tree structures for mixed graphical models and hierarchical models.