Algorithms for Convex Hull Finding in Undirected Graphical Models

An undirected graphical model is a joint distribution family defined on an undirected graph, and the convex hull of a node set in the graph is the minimal convex subgraph con-taining it. It has been shown that a graphical model is collapsible onto the minimal local sub-model induced by the convex hull which contains variables of interest under Gaus-sian and multinomial distributions. This motivates many scholars to design algorithms for finding the unique convex hull containing nodes of interest in a graph. In this paper, we propose two algorithms called, respectively, the node absorption algorithm (NA) and the inducing path absorption algorithm (IPA), to find the minimal convex subgraph contain-ing variables of interest in an undirected graph. These algorithms can be used as potential tools to find the minimal sub-model including variables of interest onto which a graphical model of large-scale can be collapsible. Experiments show that the proposed IPA signifi-cantly outperforms the NA and other existing algorithms. Furthermore, we apply the IPA to a gene network so as to collapse a large network onto a smaller network including the interested variables, and thus to achieve the aim of structural dimension reduction.(c) 2023 Elsevier Inc. All rights reserved.