Weak equivalence of local independence graphs
(2025) In Bernoulli 31(4). p.2772-2798- Abstract
Classical graphical modeling of random vectors uses graphs to encode conditional independence. In graphical modeling of multivariate stochastic processes, graphs may encode so-called local independence analogously. If some coordinate processes of the multivariate stochastic process are unobserved, the local independence graph of the observed coordinate processes is a directed mixed graph (DMG). Two DMGs may encode the same local independences in which case we say that they are Markov equivalent. Markov equivalence is a central notion in graphical modeling. We show that deciding Markov equivalence of DMGs is coNP-complete, even under a sparsity assumption. As a remedy, we introduce weak equivalence relations on DMGs that are less... (More)
Classical graphical modeling of random vectors uses graphs to encode conditional independence. In graphical modeling of multivariate stochastic processes, graphs may encode so-called local independence analogously. If some coordinate processes of the multivariate stochastic process are unobserved, the local independence graph of the observed coordinate processes is a directed mixed graph (DMG). Two DMGs may encode the same local independences in which case we say that they are Markov equivalent. Markov equivalence is a central notion in graphical modeling. We show that deciding Markov equivalence of DMGs is coNP-complete, even under a sparsity assumption. As a remedy, we introduce weak equivalence relations on DMGs that are less granular than Markov equivalence. This leads to feasible algorithms for naturally occurring computational problems, and the equivalence classes of a weak equivalence relation have attractive properties. In particular, each equivalence class has a greatest element which allows a concise representation of an equivalence class. Moreover, these equivalence relations define a hierarchy of granularity in the graphical modeling which leads to simple and interpretable connections between equivalence classes corresponding to different levels of granularity. Weak equivalence is an approximation to the more expressive Markov equivalence, and we also describe some properties of this approximation.
(Less)
- author
- Mogensen, Søren Wengel LU
- organization
- publishing date
- 2025-11
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Directed mixed graphs, local independence, local independence graph, Markov equivalence, weak equivalence, µ-separation
- in
- Bernoulli
- volume
- 31
- issue
- 4
- pages
- 27 pages
- publisher
- Bernoulli Society for Mathematical Statistics and Probability
- external identifiers
-
- scopus:105013887119
- ISSN
- 1350-7265
- DOI
- 10.3150/24-BEJ1825
- language
- English
- LU publication?
- yes
- id
- 6cd5e44b-16e8-4d8d-9916-3cdb465f1915
- date added to LUP
- 2025-10-09 12:18:55
- date last changed
- 2025-10-09 12:19:13
@article{6cd5e44b-16e8-4d8d-9916-3cdb465f1915,
abstract = {{<p>Classical graphical modeling of random vectors uses graphs to encode conditional independence. In graphical modeling of multivariate stochastic processes, graphs may encode so-called local independence analogously. If some coordinate processes of the multivariate stochastic process are unobserved, the local independence graph of the observed coordinate processes is a directed mixed graph (DMG). Two DMGs may encode the same local independences in which case we say that they are Markov equivalent. Markov equivalence is a central notion in graphical modeling. We show that deciding Markov equivalence of DMGs is coNP-complete, even under a sparsity assumption. As a remedy, we introduce weak equivalence relations on DMGs that are less granular than Markov equivalence. This leads to feasible algorithms for naturally occurring computational problems, and the equivalence classes of a weak equivalence relation have attractive properties. In particular, each equivalence class has a greatest element which allows a concise representation of an equivalence class. Moreover, these equivalence relations define a hierarchy of granularity in the graphical modeling which leads to simple and interpretable connections between equivalence classes corresponding to different levels of granularity. Weak equivalence is an approximation to the more expressive Markov equivalence, and we also describe some properties of this approximation.</p>}},
author = {{Mogensen, Søren Wengel}},
issn = {{1350-7265}},
keywords = {{Directed mixed graphs; local independence; local independence graph; Markov equivalence; weak equivalence; µ-separation}},
language = {{eng}},
number = {{4}},
pages = {{2772--2798}},
publisher = {{Bernoulli Society for Mathematical Statistics and Probability}},
series = {{Bernoulli}},
title = {{Weak equivalence of local independence graphs}},
url = {{http://dx.doi.org/10.3150/24-BEJ1825}},
doi = {{10.3150/24-BEJ1825}},
volume = {{31}},
year = {{2025}},
}