Chain Graph Reduction Into Power Chain Graphs

A graph is an ordered pair, G = (V, E), consisting of V, a set of nodes (also called vertices), and E, a set of edges, which are formally defined as pairs of nodes. Reduction, or simplification, of graphs is a class of methods used to reduce the dimensionality (defined as the total number of nodes and edges) of a graph. For a smaller graph to be considered a reduction of a larger graph, the properties of the reduced graph have to be induced from the properties of the larger original graph (Aref et al., 2014). In areas such as statistical learning, neuroscience, distributed control of networked dynamical systems, and others that use high-dimensional datasets (Xu et al., 2011), and in which the use of proxy variables is common, these procedures are of particular interest.

It appears from the literature on statistical and machine learning, as well as from the literature on probabilistic graphical models, that motif discovery (Hu et al., 2005), community detection (Javed et al., 2018) and other methods (e.g., Chao et al., 2019; Shah et al., 2017) are used as the main techniques to identify ways of combining variables or simplifying the graphical representation of a high-dimensional set of variables when the true graph structure is unknown. Graph reduction methods are used to reduce directed graphs or undirected graphs. For a third category of graphs, chain graphs, which utilize both directed and undirected edges, there is still no procedure to reduce them effectively.

The main objective of this research is to present a novel type of graph, called a power chain graph (PCG), which is a directed acyclic graph (DAG) derived from the reduction of a chain graph (CG; Cox & Wermuth, 1993), in which all nodes and undirected edges are contracted into a set of power nodes (i.e., nodes that represent groups of nodes), and all the original directed edges are contracted into a set of power edges (i.e., edges that represent groups of edges). Moreover, we propose a PCG structure learning procedure that can be used when the observed undirected graph is a Gaussian graphical model (GGM; Lauritzen, 1996; Uhler, 2017) and it is assumed that the true graph is a chain graph with unknown structure. Lastly, we evaluate the effectiveness of our PCG structure learning procedure by performing three simulation studies and an empirical example with real data.

The remainder of this paper is organized as follows. The next section presents a definition of PCGs and how to reduce CGs into PCGs. In the third section, we present a method for empirically learning the structures of PCGs. Following that, we conduct three simulation studies to test how well our structure learning procedure can recover the structures of simulated PCGs. Next, an empirical example is presented to illustrate how the PCG structure learning procedure can be used to derive causal hypotheses from the data. The paper concludes with a discussion and a few closing remarks.

Probabilistic Graphical Models, Graph Reduction and Power Chain Graphs

Probabilistic graphical models (Koller et al., 2009) are graphical representation of multivariate distributions that satisfy a set of conditional independence relations. In cases where the set of edges V and the set of nodes E are high dimensional, it may be of interest to represent the graph G in a reduced form. A graph H is called a graph minor (i.e., a reduction or an induced minor) of graph G if H can be formed from G by deleting edges and nodes, and by contracting edges (Lovász, 2006). The operation of edge contraction consists in removing an edge from a graph while simultaneously merging the two nodes that it previously connected (Asano & Hirata, 1983).

If G is an undirected graph (i.e., all edges in E are symmetric relations), then a power graph (Royer et al., 2008) PG = (V’, E’) is a reduction of a graph G, with edges contracted from motifs. Motifs are recurrent or statistically significant sub-graphs or patterns in a graph (Holland & Leinhardt, 1976). For PGs, V’ is a set of power nodes (i.e., a set of contracted nodes), and E’ is a set of power edges (i.e., a set of contracted edges). PGs do not require all edges to be contracted, and the PG derived from an undirected graph is also an undirected graph.

A similar approach is also used for contraction of directed graphs (i.e., graphs where all edges in E are directional, or causal, relations; Harary et al., 1965). A directed graph is a graph DG = (V, A), where A is a set of directed edges (also called arrows; Scutari & Denis, 2021). A node i is called a parent (or a cause) of j if the arrow from i to j is an element of A and a child (or an effect) of j if the arrow from j to i is an element of A. The reduction of a directed graph by contracting all of the nodes in each strongly connected component (i.e., a subgraph such as every node is reachable from every other node) always results in a directed acyclic graph (DAG; Lauritzen, 1996). A DAG is a type of directed graph such that there is no way to start at any node i and follow a consistently-directed sequence of edges that eventually goes back to i again.

A special type of graph known as chain graph (Lauritzen, 1996), defined as CG = (V, A, E), includes both a set of undirected edges E and a set of directed edges A. In the probabilistic graphical model literature, chain graphs are also known as mixed graphs with no semi-directed cycles and no bidirectional edges (Højsgaard et al., 2012), being thus a generalization of both undirected graphs and DAGs. CGs, like DAGs, can be used to make causal interpretations between variables connected by directed edges. However, the undirected edges in CGs can be interpreted in several different ways, depending on the assumed or real conditional dependencies and the presence or absence of latent variables. For instance, Lauritzen and Richardson (2002) used the example presented in Figure 1 to argue that undirected edges in CGs should not be interpreted as causal relations, unless extra information is presented. At the top of Figure 1 we present an observed CG, with the following factorization of the joint density of variables a, b, c, and d:

where $⫫$ represents independence.

The DAGs and the DG on the bottom are commonly used to interpret, or statistically model, the undirected edge on the CG. However, none of these graphs result in the same conditional distribution, as the joint density of DAG1, DAG2, and DG are, respectively, represented by

where $\neg ⫫$ represents dependence. These relations show that CGs can, and should, be used when correlations have no clear causal interpretation. Despite this fact, it is not rare for causal models to be assumed, for instance, in psychometrics and fMRI studies, where the correlated data (e.g., test responses and voxels) are assumed to have a common latent cause (e.g., psychological construct and original neural signal). In these research areas, statistical modeling usually requires additional assumptions about how observed data relates to the latent causes (e.g., Mair, 2018; Roberts & Everson, 2001).

In the literature on CGs, when the structure is high dimensional, chain graphs can be divided in a path of blocks of variables, known as dependence chains (Wermuth & Lauritzen, 1990). Dependence chains are used to illustrate and properly condition causal effects in CGs because within blocks the relations are undirected, but between blocks the relations are directed. The interpretation of these dependence chains relies on what interpretation of CGs is assumed in the given study. There are three main interpretations of CGs, each with its own peculiarities (Javidian & Valtorta, 2018): (i) Lauritzen-Wermuth-Frydenberg (LWF) CGs; (ii) Andersson-Madigan-Perlman (AMP) CGs; and (iii) multivariate regression (MVR) CGs.

The first two, AMP and LWF CGs, are characterized by having directed and undirected edges, but differ on how they establish independence relations between parents of vertices that are linked by an undirected edge. MVR CGs, on the other hand, use directed edges together with bidirectional edges. MVR CGs have more in common with AMP CGs, as each node depends only on its own parents according to both interpretations. Both interpretations can also be modelled with linear equations, being the main difference between MVR CGs and AMP CGs the modelling of noise (Sonntag, 2016). The bidirected edges in MVR CGs are used to model latent (or hidden) variables (Javidian & Valtorta, 2021), being related, then, to DAG1 represented in Figure 1. LWF CGs, on the other hand, assume that each node is affected by the parents of the whole block and, therefore, the causal effects propagate bidirectionally between undirected edges, being related, then, to DG represented in Figure 1.

Despite the specific CG interpretation, if all nodes in a subgraph (i.e., a group of variables) have directed relations with all nodes of another subgraph, the nodes within each subgraph can be considered as part of the same block, even if the block represents a disconnected subgraph (i.e., a graph which not all nodes are directly connected). On the other hand, if the blocks are defined by clusters of variables, and if it is possible to test or assume the disjointness condition (i.e., that it is possible to define the direction of the relations between blocks), then we have a special type of CG which can be reduced to a PCG, as illustrated in Figure 2. Despite the fact that the factorization of both the CG and the PCG in Figure 2 are identical, the PCG representation allows further inference about the clustering process of the predictor variables and the causal chains as a whole, without having to assume, a priori, a specific CG interpretation.

The undirected part of the chain graphs can be reduced by graph minor operations, while the directed part can be reduced by the contraction of an undirected equivalent of the strongly connected component to achieve a power chain graph (PCG). The PCG can be defined as the graph P = (V’, A’), where all original nodes and undirected edges are contracted into a set of power nodes, V’, and all the original directed edges are contracted into a set of directed power edges, A’. Figure 3 depicts this reduction process, where it is possible to see that a PCG is equivalent to a DAG that implies an underlying CG. MVR CGs can, at this point, again be contrasted with PCGs, in the sense that they also operate a type of graph reduction. However, MVR CGs assume that strongly connected subgraphs result from a latent common cause, which have to be marginalized from the original CG before causal discovery can occur (Javidian & Valtorta, 2018; Sonntag & Peña, 2015). PCG does not require this additional assumption.

In the case of CGs, it has been shown that the structure of CGs, just like DAGs, can be, under the correct circumstances and assumptions, recovered from observational data (Peña & Gómez-Olmedo, 2016). A possible method for CGs is a PC-like algorithm, based on the Peter-Clark (PC) algorithm (Spirtes et al., 2000), which uses partial correlations and theorems of causality theory (Pearl, 2009) to infer a causal structure from the data. However, this PC-like approach for CGs, just as for DAGs, will recover, in most cases, only a CG which is in the same equivalent class as the graph that generated the data (Peña & Gómez-Olmedo, 2016). On top of that, as CGs are more complex and general than DAGs, these equivalence classes tend to contain more options than for DAGs, so it would be in interest of a researcher if some CG structures could be reduced to DAG structures by PCG reduction.

If the CG is given or assumed, then reducing it to a PCG requires only three steps. First, one must define or choose a measurement function for assessing the conditional dependencies between the nodes. Then, the strongly connected undirected subgraphs are theoretically defined or empirically estimated from data. In the final step, a method for ensembling the weights of the directed edges of similar nodes in A into directed power edges in A’ is applied to the graph. However, more usually than not, the CG is not given nor should be assumed to be known. In this more realistic scenario, structure learning procedure (also known as causal discovery algorithm) can be used to first estimate the PCG and then the relations in the CG can be implied from the PCG.

Structure Learning of Power Chain Graphs

We propose a structure learning procedure for PCGs where the dependencies between variables are assumed to be linear and, therefore, the variables are assumed to follow a multivariate normal distribution. Gaussian graphical models (GGMs; Lauritzen, 1996; Uhler, 2017) are a usual decision for modeling network models in this scenario (e.g., Drton & Perlman, 2008; Epskamp et al., 2018; Yin & Li, 2011). GGMs are mathematically convenient for modeling linear dependencies and conditional linear dependencies between variables, as GGMs present maximal entropy configuration and the possibility for intuitive maximum likelihood estimation.

The first step of our structure learning procedure for learning the structure of PCGs is the identification of the groups of similar nodes by some data-driven procedure. In a chain graph that can be represented by a GGM, any node v_a is more similar to any node v_b than to any node v_c if and only if ${\lambda }_{{\rho }_a,{\rho }_b}>{\lambda }_{{\rho }_a,{\rho }_c}$. The measure ${\lambda }_{{\rho }_a,{\rho }_b}$ assesses the similarity between the vectors of dependencies ρ_a and ρ_b. The vector of dependencies ρ_a has as its elements the dependencies involving the v_a node. The vector of dependencies ρ_b is interpreted similarly to ρ_a in respect to v_b, and ${\lambda }_{{\rho }_a,{\rho }_c}$ is interpreted similarly to ${\lambda }_{{\rho }_a,{\rho }_b}$ in respect to ρ_a and ρ_c. With GGMs, Pearson correlation coefficient and regularized partial correlation are the most commonly used measures of dependency between nodes (Epskamp et al., 2018). Clusters (i.e., groups or communities) can then be found by conventional methods, such as exploratory factor analysis with parallel analysis (Horn, 1965), exploratory graph analysis (Golino & Epskamp, 2017), and motif discovery.

In the second step of our structure learning procedure, after finding the clusters of variables, the directions of the relations between power nodes can be estimated using causal discovery algorithms (Malinsky & Danks, 2018). More specifically, we propose that correlations between different clusters can be averaged and the resulting averaged correlation matrix can be fed to a causal discovery algorithm, resulting in the PCG. Because the steps in our structure learning procedure are complex and dependent on a series of intricate assumptions, we summarize the steps as well as the main assumptions in Table 1.

Simulation Studies

Empirical Example

For illustration purposes, the present empirical example will apply PCG to derive causal hypotheses related to the empathy construct. Davis (1980) proposed a multidimensional measurement of empathy, operationalized in a questionnaire composed by four seven-item subscales: perspective-taking; fantasy; empathic concern; and personal distress. Fantasy is the tendency to get involved in the actions of fictional characters from diverse media. Perspective-taking is the tendency to comprehend others’ point of view. Empathic concern is the tendency of feeling concern and sympathy for people in distress. Personal distress is the tendency of feeling unease in difficult, tense or emotional situations.

As usual in the psychological literature, the psychometric properties of the questionnaire were evaluated by Davis (1980) by means of exploratory factor analysis, without explicit assumptions regarding causal relations between the latent factors. This analysis resulted in what is usually considered as good evidence of validity (i.e., items theorized to be together were indeed clustered by the same latent factor) and reliability (i.e., Cronbach’s alpha above 0.70). Briganti et al. (2018) applied the EGA procedure and found the same structure as the original study by Davis (1980). In the present example, we will apply our PCG procedure to the open dataset, originally from Braun et al. (2015), provided by Briganti et al. (2018).

Discussion

The main aim of the present study was to propose a procedure of structure learning of PCGs. The secondary aim of the study was to compare clustering algorithms and causal discovery algorithms that can be used for learning the structure of the PCGs. To achieve these aims we used simulated data. To evaluate the practical value of our procedure, we did a full analysis of an empirical example. Our simulations showed that our procedure can properly recover both the clusters of variables, by means of the CGMM procedure, and the correct direction of the underlying causal relations, by means of averaged correlation matrix and the PC-stable algorithm. Our simulations have also illustrated how PCGs can be used to further investigate the structure of CGs, through tuning of the CG implied by the PCG using three different classes of causal discovery algorithms.

To assess the performance of the CGMM procedure in finding the correct number of clusters, we used a number of accuracy related indices and cluster comparison indices. We also compared the CGMM performance with two other more traditional procedures in statistical analysis: PA-EFA and EGA. Our results show that, in general, CGMM outperformed both procedures in a number of different conditions of sample sizes, number of variables per cluster, and the total number of clusters. These results are somewhat unexpected. Previous studies (e.g., Golino et al, 2020) have shown high accuracy for both PA-EFA and EGA procedures. However, PA-EFA performed very poorly and EGA performed poorer than expected (despite the fact that it performed better than the CGMM in some conditions). One possible reason for this result is the differences in design between our study and the previous studies. In our study, the simulation has an underlying causal structure that forces independence between some power nodes. Previous studies used correlated underlying structures. This difference causes data to be factorized in a different manner (Lauritzen, 1996), probably resulting in the differences of performance found in our study. This design difference also means that more studies are necessary to evaluate how well CGMM will perform when there are dependencies between all power nodes.

The PC-stable algorithm performed well in a number of different conditions, even when the clustering was not known a priori. Changing the sample sizes, number of variables per cluster and the total number of clusters had little to no clear effect in the accuracy related indices. The second part of the causal discovery analysis, which compared different tuning algorithms, has some implications for structure learning procedures of CGs (e.g., Drton & Perlman, 2008; Ma et al., 2008; Peña et al., 2014). Most of these procedures try to find the best fitting CG by brute force (Peña, 2018): fitting a large number of different models and choosing the best fitting one. Our results indicate that learning the structure using the full PCG procedure and then using its implied CG as an initial guess for the estimated true CG can enhance CG’s structure learning procedures.

Regarding the empirical example, although it was used more as an illustration of our procedure than a true investigation of the causal structures of empathy as proposed by Davis (1980), our findings look promising. In sum, the results indicate that it is reasonable to infer that our own feelings of uneasiness in difficult situations and our capacity to comprehend others’ point of view causes how we feel for people in distress. Also, how we feel for people in distress and our own feelings of uneasiness in difficult situations causes how we feel for fictional characters in distress. These inferences may have implications that might be of interest for replication and extension from researchers of empathy. For instance, longitudinal (e.g., Zhou et al., 2002) studies could be used to test if the causal structure holds in a developmental setting. Neurological (e.g., Singer et al., 2004) studies, on the other hand, could help to validate the estimated causal structure by identifying which areas of the brain are related to which factor, as well as if neural relations reflect the causal structure found in the present study. For researchers from other areas of study can also benefit from these results as they provide insight that maybe constructs first hypothesized to be only associational can actually present some identifiable underlying causal structure.

There are two main limitations of the present study. The first is the CGMM procedure. Despite its performance in the simulation study, the results may be limited to the particular setting of the data generating process. Theoretical studies are necessary to better understand in what conditions CGMM may perform the best so the present results regarding CGMM can be properly generalized. However, this has little impact on the PCG procedure as a whole, as any clustering procedure can be used in place of the CGMM, as long as it respects the “similarity” condition for clustering the variables. The second main limitation is related to the averaging of the correlation matrix. Despite its relation with the definitions of a power edge and similarity between nodes, there is neither logical implication nor model constraint that requires for the power edges to be estimated like this. Therefore, it is also necessary for future studies to evaluate which procedures for estimating or calculating power edges can improve the performance of the PCG procedure.

Future studies on PCG can focus on both theoretical aspects of CGMM and how causal discovery algorithms can be extended for learning the causal structure from the averaged correlation matrix. For instance, what would happen if instead of correlations, measures of dependence (Paul & Shill, 2017; Zhao et al., 2016), such as the maximal information coefficient or distance correlations, were used in CGMM? What would be the impact of using partial distance correlations’ tests (Székely & Rizzo, 2014) instead of partial correlations’ tests in the PC-stable algorithm? Is it possible to incorporate a clustering procedure such as CGMM directly as a step in the score-based algorithms? These questions help to set the environment for prolific research about PCGs and all its constituent elements: clustering; causal discovery; and CG structure learning.