Characterizing and Identifying Separable Graphical Models
2026-07-01 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study complex types of graphs that combine different kinds of connections to represent relationships and independencies in systems with feedback, hidden factors, or selection issues. They define 'separable graphs,' where the absence of a connection means there is a clear way to separate the nodes, and 'essentially separable graphs,' which are closely related to separable ones. The authors show how these graphs relate to many existing graph types and describe ways to tell when two graphs represent the same separations. They also create a standard form for these graphs and an algorithm to identify the right group for any essentially separable graph under certain conditions.
graphical modelsmixed graphsvertex separationseparable graphsgraph equivalencelatent variablesselection biasbidirected edgesfeedback systemsgraph algorithms
Authors
Christopher Meek, Kayvan Sadeghi
Abstract
We study a broad class of graphical models whose independencies correspond to vertex separation in mixed graphs with directed, undirected, and bidirected edges, that are capable of encoding independence structures arising from feedback, latent and selection mechanisms. In particular, we introduce separable graphs, in which each missing edge implies the existence of a separating set for its endpoints, and essentially separable graphs, those graphs separation equivalent to a separable graph. We show that these models include many existing graph families used to define graphical models an provide several characterizations of separable graphs and essentially separable graphs. We also provide multiple characterizations of separation equivalence for separable graphs. One is a graphical characterization in terms of ordinary graph properties, extending earlier results for specific subfamilies Another is a separational characterization depending only on graph separation properties. Finally, we provide a canonical representation for the equivalence classes of essentially separable graphs and develop an algorithm that, under suitable assumptions, identifies the equivalence class of any essentially separable graph.