2202.10706v2

Ragib Ahsan David Arbour Elena Zheleva Editors: Bernhard Sch¨ olkopf, Caroline Uhler and Kun Zhang ## Abstract Causal reasoning in relational domains is fundamental to studying real-world social phenomena in which individual units can influence each other's traits and behavior. Dynamics between interconnected units can be represented as an instantiation of a relational causal model; however, causal reasoning over such instantiation requires additional templating assumptions that capture feedback loops of influence. Previous research has developed lifted representations to address the relational nature of such dynamics but has strictly required that the representation has no cycles. To facilitate cycles in relational representation and learning, we introduce relational σ -separation, a new criterion for understanding relational systems with feedback loops. We also introduce a new lifted representation, σ -abstract ground graph which helps with abstracting statistical independence relations in all possible instantiations of the cyclic relational model. We show the necessary and sufficient conditions for the completeness of σ -AGG and that relational σ -separation is sound and complete in the presence of one or more cycles with arbitrary length. To the best of our knowledge, this is the first work on representation of and reasoning with cyclic relational causal models. Keywords: Representation, Cycles, Relational Causal Model ## 1. Introduction Causal inference methods from observational data often assume that causal relationships can be represented in an acyclic graphical model. However, many real-world phenomena involve feedback loops or cycles that violate the acyclicity assumption. For example, supply and demand affect price and vice versa, hormone levels in the body affect each other and friends can impact each other's choices. Common to these scenarios is that these interactions occur over time but any individual directed relationship may not be observed. Instead what is observed is a set of values that are result of long term individual interactions. This current state can be represented through a cycle. The existing works on cyclic causal models primarily focus independently and identically distributed (i.i.d) data instances (Richardson, 1996, 1997; Strobl, 2019; Rantanen et al., 2020). However, in many real-world systems units are often interconnected in a complex network. Causal reasoning over such relational systems is central to understanding real-world social phenomena, such as social influence and information diffusion. For example, a well-known study by Christakis and Fowler (2007) investigates whether obesity is contagious in a population where each person's eating habits can affect their friends and family and vice-versa. Similarly, several real-world problems in epidemiology and computational social science encounter such mutual influence and interaction ## Relational Causal Models with Cycles: Representation and Reasoning RAHSAN3@UIC.EDU ARBOUR@ADOBE.COM EZHELEVA@UIC.EDU Figure 1: Example of relational model with and without feedback loop. Rectangle, rhombus and oval shapes represent entity, relationship and attributes respectively. Arrows refer to relational dependence. The solid arrows constitute an acyclic relational model. The dashed arrow creates a feedback loop in the model. <details> <summary>Image 1 Details</summary>  ### Visual Description ## Diagram: User-Post-Media Relationship ### Overview The image is a diagram illustrating the relationships between a user, a post, and media. It shows how a user's sentiment influences their reactions to posts, which in turn affects engagement. Media is created from posts and influences user preferences. ### Components/Axes * **Nodes:** * USER (Rectangle) * Sentiment (Oval) * POST (Rectangle) * Engagement (Oval) * MEDIA (Rectangle) * Preference (Oval) * **Relationships:** * REACTS (Diamond) * CREATES (Diamond) * **Arrows:** * Solid arrows indicate a direct influence or creation. * A dashed arrow indicates a feedback loop or indirect influence. ### Detailed Analysis * **USER:** The "USER" node is represented by a rectangle. Inside the rectangle is an oval labeled "Sentiment." * **POST:** The "POST" node is represented by a rectangle. Inside the rectangle is an oval labeled "Engagement." * **MEDIA:** The "MEDIA" node is represented by a rectangle. Inside the rectangle is an oval labeled "Preference." * **Relationships:** * A solid arrow goes from "Sentiment" to the "REACTS" diamond. The "REACTS" diamond connects the "USER" rectangle to the "POST" rectangle. * A solid arrow goes from the "REACTS" diamond to "Engagement." * A solid arrow goes from "Engagement" to the "CREATES" diamond. The "CREATES" diamond connects the "POST" rectangle to the "MEDIA" rectangle. * A solid arrow goes from the "CREATES" diamond to "Preference." * A dashed arrow goes from "Engagement" back to "Sentiment." ### Key Observations * The diagram shows a flow of influence from user sentiment to post engagement to media preference. * There is a feedback loop from post engagement back to user sentiment. ### Interpretation The diagram illustrates a simplified model of how users interact with content on a platform. A user's sentiment influences how they react to posts. These reactions contribute to the overall engagement of the post. The post, in turn, leads to the creation of media, which shapes user preferences. The dashed arrow indicates that the engagement with a post can also influence the user's sentiment, creating a feedback loop. This model could be used to understand and predict user behavior, optimize content creation, and improve user experience. </details> among human subjects. For example, effect of vaccination in mother and child (Shpitser, 2015; VanderWeele et al., 2012), and justices influencing each other in supreme court decisions (Ogburn et al., 2020) are all examples of mutual influence. Studying such phenomena requires causal reasoning over complex interactions between interconnected entities. However, causal questions of mutual influence in a relational system can be hard to answer due to the lack of appropriate causal representations and reasoning mechanisms. One way to represent interference is through SCMs which capture pairwise relationships (Ogburn et al., 2014; Shalizi and Thomas, 2011), where one individual's influence on another is represented independently. Such representation is easy to reason about but it assumes that pairs of nodes are independent of other pairs of nodes. Unfortunately, this does not reflect the properties of real-world social networks in which nodes are arbitrarily interconnected with each other. The development of relational causal models , which generalize over structural causal models, is an important step towards capturing interactions between non-i.i.d instances (Maier et al., 2013b,a; Lee and Honavar, 2015; Bhattacharya et al., 2020). Relational models involve multiple types of interacting entities with probabilistic dependencies among their attributes. Maier et al. (2013b) developed a lifted causal representation named abstract ground graph (AGG) that abstracts over all instantiations of a relational model. AGG enables reasoning about causal queries in relational causal models and relational causal discovery. However, existing relational causal models assume acyclicity and do not allow for reasoning about identification in the presence of feedback loops. Figure 1 shows an example of a relational model where users react to news articles or posts on a specific topic (e.g., vaccines) generated by media agencies. The preference of the media regarding a topic (e.g., pro- vs anti-vaccination) is influenced by the engagement or feedback (e.g., positive/negative comments) it receives on its existing posts. The sentiment of a user towards a given post directly impacts their engagement in the post. The relational model representation tempts one to conclude that the sentiment of users regarding vaccination is independent of the preference of media agencies given engagements of the posts the users react to. However, as we show in section 3.5, this is not necessarily true. Moreover, users' sentiment can also be impacted by the engagements in posts they interact with. The dashed arrow in Figure 1 represents such a dependency which makes the model a cyclic one. Unfortunately, even though the model seems simple and realistic, the abstract ground graph (AGG) representation and relational d -separation no longer apply due to the presence of a feedback loop (i.e., a cycle). In this work, we specifically study cyclic RCMs and show that they offer the necessary representation to reason about a lot of real-world causal problems where popular assumptions do not hold. We do not assume the Stable Unit Treatment Value Assumption (SUTVA), of causal inference, according to which the outcome of each unit depends only on the unit itself (Rubin, 1980). This Assumption is violated in relational systems where the treatment and outcome of one unit can impact other units' outcomes. To the best of our knowledge, this is the first work that addresses representation of and reasoning about cyclic relational causal models. We define a new abstract representation, σ -abstract ground graph ( σ -AGG) which generalizes over cyclic relational models. In order to reason about relational queries in σ -AGG, we introduce relational σ -separation and provide proofs for its soundness and completeness for all instantiations of a relational model. The implications of this new representation are twofold. First, it can lead the way for reasoning about causal effects like interference and contagion in relational systems, which are of wide interest in the social sciences. Second, the abstract representation and its identified properties will lay a foundation for causal structure learning from relational models with cycles. We show the sufficient conditions for the completeness of σ -AGG by first resolving an open problem on the completeness of AGG. Finally, we discuss the Markov condition of relational σ -separation and its implications. ## 2. Related Work Maier et al. (2013b) proposed a sound and complete abstract representation for relational data with multiple entities and relationships. They defined an abstract representation of relational dependence called abstract ground graph based on the assumption that the underlying relational model is acyclic. Moreover, they introduced relational d -separation, a new criterion to reason about statistical independence in all the instantiations of a relational model. They proved the soundness and completeness of relational d -separation. The AGG and associated relational d -separation criterion together allows a formal basis of causal analysis in relational systems. The same authors proposed a constraint-based causal structural learning algorithm called RCD (Maier et al., 2013a) which is first of its kind. Lee and Honavar (2015) presented a critical view on the generalizability of AGG where they constructed a counterexample which shows how AGG can fail to abstract all d -separation relationships in the ground graphs. They also identified a shortcoming of the necessary conditions for considering a intersection variable and provided a revised set of conditions. In a different work, Lee and Honavar (2020) proposed a new abstract representation of relational causal models called the unrolled graph which guarantees a weaker sense of completeness. However, neither of the two groups of work moved away from the assumption of acyclicity. As a result their developments are not directly applicable to relational models with cycles or feedback loops. Alternatively, chain graphs have been used for representing systems with pairwise feedback loops (Lauritzen and Richardson, 2002; Dawid, 2010; Ogburn et al., 2020). There is no prior work that focuses on representation and reasoning of relational models with cycles or feedback loops of arbitrary length. Existing research on representation and reasoning about systems with cycles is based on propositional variables, not relational ones. Spirtes (1995) showed that, in general case, without any specific assumption regarding the nature of dependence (linear, polynomial etc.), the d -separation relations in a directed cyclic graph are not sufficient to entail all the corresponding conditional independence relations. Forr´ e and Mooij (2017) introduced σ -separation, an alternative formulation for which the corresponding Markov property is shown to hold in a very general setting. According to them, the σ -separation Markov property seems appropriate for a wide class of cyclic structural causal models with non-linear functional relationships between non-discrete variables. ## 3. Preliminaries In this section we introduce the necessary terminology to discuss representation and abstraction of cyclic relational models. ## 3.1. Directed Cyclic Graphs ADirected Cyclic Graph (DCG) is a graph G = 〈V , E〉 with nodes V and edges E ⊆ { ( u, v ) : u, v ∈ V, u = v } where ( u, v ) is an ordered pair of nodes. We will denote a directed edge ( u, v ) ∈ E as u → v or v ← u , and call u a parent of v . In this work, we restrict ourselves to DCG as the causal graphical model. A walk between two nodes u, v ∈V is a tuple 〈 v 0 , e 1 , v 1 , e 2 , v 2 , ..., e n , v n 〉 of alternating nodes and edges in G ( n ≥ 0) , such that v 0 , ..., v n ∈ V , and e 1 , ..., e n ∈ E , starting with node v 0 = u and ending with node v n = v where the edge e k connects the two nodes v k -1 and v k ∈ G for all k = 1 , ..., n . If the walk contains each node at most once, it is called a path . A directed walk (path) from v i ∈ V to v j ∈ V is a walk (path) between v i and v j such that every edge e k on the walk (path) is of the form v k -1 → v k , i.e., every edge is directed and points away from v i . We get the ancestors of node v j by repeatedly following the path(s) through the parents: AN G ( v j ) := { v i ∈ V : v i = v 0 → v 1 → ... → v n = v j ∈ G} . Similarly, we define the descendants of v i : DE G ( v i ) := v j ∈ V : v i = v 0 → v 1 → ... → v n = v j ∈ G . Each node is an ancestor and descendant of itself. A directed cycle is a directed path from v i to v j such that in addition, v j → v i ∈ E . All nodes on directed cycles passing through v i ∈ V together form the strongly connected component SC G ( v i ) := AN G ( v i ) ∩ DE G ( v i ) of v i . ## 3.2. σ -separation The idea of σ -separation follows from d -separation, a fundamental notion in DAGs which was first introduced by Pearl (1988): Definition 1 ( d -separation) A walk 〈 v 0 ...v n 〉 in DCG G = 〈V , E〉 is d -separated by C ⊆ V if: 1. its first node v 0 ∈ C or its last node v n ∈ C , or 2. it contains a collider v k / ∈ AN G ( C ) , or 3. it contains a non-collider v k ∈ C . If all paths in G between any node in set A ⊆ V and any node in set B ⊆ V are d -blocked by a set C ⊆ V , we say that A is d -separated from B by C , and we write A d | = G B | C . d -separation exhibits the global Markov property in DAGs which states that if two variables X and Y are d -separated given another variable Z in a DAG representation then X and Y are conditionally independent given Z in the corresponding distribution of the variables. However, Spirtes (1995); Neal (2000) show that without any specific assumption regarding the nature of dependence (i.e. linear, polynomial), the d -separation relations are not sufficient to entail all the corresponding conditional independence relations in a DCG. In a recent work, an alternative formulation called σ -separation is introduced which holds for a very general graphical settings (Forr´ e and Mooij, 2017). Here, we consider a simplified version of the formal definition of σ -separation: Definition 2 ( σ -separation) A walk 〈 v 0 ...v n 〉 in DCG G = 〈V , E〉 is σ -blocked by C ⊆ V (Forr´ e and Mooij, 2017) if: 1. its first node v 0 ∈ C or its last node v n ∈ C , or 2. it contains a collider v k / ∈ AN G ( C ) , or 3. it contains a non-collider v k ∈ C that points to a node on the walk in another strongly connected component (i.e., v k -1 → v k → v k +1 with v k +1 / ∈ SC G ( v k ) , v k -1 ← v k ← v k +1 with v k -1 / ∈ SC G ( v k ) or v k -1 ← v k → v k +1 with v k -1 / ∈ SC G ( v k ) or v k +1 / ∈ SC G ( v k ) ). If all paths in G between any node in set A ⊆ V and any node in set B ⊆ V are σ -blocked by a set C ⊆ V , we say that A is σ -separated from B by C , and we write A σ | = G B | C . Forr´ e and Mooij (2017) show that the global directed Markov property 1 holds for σ -separation in directed cyclic graphs, unlike d -separation. This enables σ -separation to perform a similar role to d -separation but for directed cyclic graphs. σ -separation is a generalization of d -separation. ## 3.3. σ -faithfulness σ -faithfulness refers to the property which states that all statistical dependencies found in the distribution generated by a given causal structure model is entailed by the σ -separation relationships. Definition 3 ( σ -faithfulness) Given X A , X B , X C as the distributions of variables A , B , C respectively in solution X of a causal model M , σ -faithfulness states that if X A and X B are conditionally independent given X C , then A and B are σ -separated by C in the corresponding possibly cyclic graphical model G of M . ## 3.4. Relational Causal Models (RCM) We adopt the definition of relational causal model used by previous work on relational causal discovery (Maier et al., 2013a; Lee and Honavar, 2020). We denote random variables and their realizations with uppercase and lowercase letters respectively, and bold to denote sets. We use a simplified Entity-Relationship model to describe relational data following previous work (Heckerman et al., 2007). A relational schema S = 〈 E , R , A , card 〉 represents a relational domain where E , R and A refer to the set of entity, relationship and attribute classes respectively. It includes a cardinality function that constrains the number of times an entity instance can participate in a relationship. Figure 1 shows an example relational model that describes a simplified user-media engagement system. The model consists of three entity classes (User, Post, and Media), and two relationship classes (Reacts and Creates). Each entity class has a single attribute. The cardinality constraints are shown with crow's feet notation- a user can react to multiple posts, multiple users can react to a post, a post can be created by only a single media entity. A relational skeleton s is an instantiation of a relational schema S , represented by an undirected graph of entities and relationships. Figure 2( a ) shows an example skeleton of the relational model from Figure 1. It shows that Alice and Bob both react to post P1. Alice also reacts to post P2. P1 1. Definition given in appendix Figure 2: Fragments of a relational skeleton, ground graph, and abstract ground graph corresponding to the relational causal model from Figure 1. The arrows represent relational dependencies. <details> <summary>Image 2 Details</summary>  ### Visual Description ## Diagram: Social Media Interaction Models ### Overview The image presents three diagrams (a, b, and c) illustrating different models of social media interaction. Each diagram depicts relationships between users (Alice, Bob), posts (P1, P2), media (M1), and their associated sentiments, engagement, and preferences. The diagrams use nodes to represent entities and directed edges to represent relationships or flow of influence. ### Components/Axes **Diagram (a):** * **Nodes:** * ALICE: Contains "Sentiment" * BOB: Contains "Sentiment" * P1: Contains "Engagement" * P2: Contains "Engagement" * M1: Contains "Preference" * **Edges:** * ALICE -> P1: Labeled "REACTS" * BOB -> P1: Labeled "REACTS" * P1 -> P2: Labeled "REACTS" * P1 -> M1: Labeled "CREATES" * P2 -> M1: Labeled "CREATES" **Diagram (b):** * **Nodes:** * Alice.Sentiment * Bob.Sentiment * P1.Engagement * P2.Engagement * M1.Preference * **Edges:** * Alice.Sentiment -> P1.Engagement * Bob.Sentiment -> P1.Engagement * P1.Engagement -> P2.Engagement * P1.Engagement -> M1.Preference * P2.Engagement -> M1.Preference * Alice.Sentiment -> P2.Engagement **Diagram (c):** * **Nodes:** * \[USER].Sentiment * \[USER, REACTS, POST].Engagement * \[USER, REACTS, POST, CREATES, MEDIA].Preference * \[USER, REACTS, POST, CREATES, MEDIA, CREATES, POST].Engagement * \[USER, REACTS, POST, REACTS, USER].Sentiment * \[USER, REACTS, POST, REACTS, USER, REACTS, POST].Engagement (appears twice, with an intersection symbol between them) * \[USER, REACTS, POST, REACTS, USER, REACTS, POST].Engagement * **Edges:** * \[USER].Sentiment -> \[USER, REACTS, POST].Engagement * \[USER, REACTS, POST].Engagement -> \[USER, REACTS, POST, CREATES, MEDIA].Preference * \[USER, REACTS, POST].Engagement -> \[USER, REACTS, POST, CREATES, MEDIA, CREATES, POST].Engagement * \[USER, REACTS, POST, REACTS, USER].Sentiment -> \[USER, REACTS, POST].Engagement * \[USER, REACTS, POST, REACTS, USER].Sentiment -> \[USER, REACTS, POST, REACTS, USER, REACTS, POST].Engagement * \[USER, REACTS, POST, CREATES, MEDIA, CREATES, POST].Engagement -> the intersection of the two \[USER, REACTS, POST, REACTS, USER, REACTS, POST].Engagement nodes ### Detailed Analysis or ### Content Details **Diagram (a):** * Alice and Bob's sentiments influence post P1's engagement. * Post P1's engagement influences post P2's engagement. * Both P1 and P2 create media M1's preference. **Diagram (b):** * Alice's and Bob's sentiments directly influence P1's engagement. * P1's engagement influences P2's engagement and M1's preference. * P2's engagement also influences M1's preference. * Alice's sentiment also influences P2's engagement. **Diagram (c):** * This diagram uses set notation to represent the relationships. * A user's sentiment leads to engagement. * Engagement leads to preference. * Reacting users' sentiments lead to engagement. * Engagement and reacting users' sentiments lead to a more specific type of engagement. ### Key Observations * Diagram (a) provides a high-level overview of the interactions. * Diagram (b) refines the model by specifying the entities with their attributes (e.g., Alice.Sentiment). * Diagram (c) uses set notation to represent the relationships, providing a more abstract view. ### Interpretation The diagrams illustrate how user sentiments, post engagement, and media preferences are interconnected in a social media environment. Diagram (a) shows a basic model, while diagram (b) provides a more detailed view with specific entities. Diagram (c) abstracts the relationships using set notation, highlighting the roles of users, reactions, posts, and media in shaping engagement and preferences. The intersection in diagram (c) suggests a combined influence or a specific type of engagement resulting from multiple factors. The diagrams collectively demonstrate the complex interplay of factors that drive social media interactions. </details> and P2 both are created by media M1. There could be infinitely many possible skeletons for a given RCM. We denote the set of all skeletons for schema S as ∑ S . Given a relational schema, we can specify relational paths, which intuitively correspond to ways of traversing the schema. For the schema shown in Figure 1, possible paths include [ User, Reacts, Post ] (the posts a user reacts to), as well as [ User, Reacts, Post, Reacts, User ] (other users who react to the same post). Relational variables consist of a relational path and an attribute. For example, the relational variable [ User, Reacts, Post ] .Engagement corresponds to the overall engagements of the post that a user reacts to. The first item (i.e. User ) in the relational path corresponds to the perspective of the relational variable. A terminal set, P | i k is the terminal item on the relational path P = [ I j , ..., I k ] consisting of instances of class I k ∈ E ∪ R . A relational causal model M = 〈S , D〉 , is a collection of relational dependencies defined over schema S . Relational dependencies consist of two relational variables, cause and effect. As an example, consider the following relational dependency [ Post, Reacts, User ] .Sentiment → [ Post ] .Engagement which states that the engagement of a post is affected by the actions of users who react on that post. In Figure 1, the arrows represents relational dependencies. Note that, all causal dependencies are defined with respect to a specific perspective. ## 3.5. Ground Graph and Abstract Ground Graph A realization of a relational model M with a relational skeleton is referred to as the ground graph GG M . It is a directed graph consisting attributes of entities in the skeleton as nodes and relational dependencies among them as edges. A single relational model is actually a template for a set of possible ground graphs based on the given schema. A ground graph has the same semantic as a graphical model. Given a relational model M and a relational skeleton s , we can construct a ground graph GG M s by applying the relational dependencies as specified in the model to the specific instances of the relational skeleton. Figure 2( b ) shows the ground graph for the relational model from Figure 1. The relational dependencies present in the given RCM may temp one to conclude a conditional independence statement: [ User ] .Sentiment | = [ Media ] .Preference | [ Post ] .Engagement . However, when the model is unrolled in a ground graph we see the corresponding statement is not true (i.e. [ Bob ] .Sentiment ⊥ ⊥ [ M 1] .Preference | [ P 1] .Engagement ) since there is an alternative path through [ Alice ] .Sentiment and [ P 2] .Engagement which is activated when conditioned on [ P 1] .Engagement . This shows why generalization over all possible ground graphs is hard. An abstract ground graph (AGG) is an abstract representation that solves the problem of generalization by capturing the consistent dependencies in all possible ground graphs and representing them as a directed graph. AGGs are defined for a specific perspective and hop threshold , h . Hop threshold refers to the maximum length of the relational paths allowed in a specific AGG. There are two types of nodes in AGG, relational variables and intersection variables. Intersection variables are constructed from pairs of relational variables with non-empty intersections (Maier et al., 2013b). For example, [ User, Reacts, Post ] refers to the set of posts a user reacts to whereas [ User, Reacts, Post, Reacts, User, Reacts, Post ] refers to the set of other posts reacted by other users who also reacted to the same post as the given user. These two sets of posts can overlap which is reflected by the corresponding intersection variable. Edges between a pair of nodes of AGG exist if the instantiations of those constituting relational variables contain a dependent pair in all ground graphs. We define W as the set of nodes augmented with their corresponding intersection nodes for the set of relational variables W : W = W ∪ ⋃ W ∈ W { W ∩ W ′ | W ∩ W ′ is an intersection node in AGG M s } . Figure 2( c ) presents the AGG from the perspective of User and with h = 6 corresponding to the model from Figure 1. The AGG shows that the sentiment of a user is no longer independent of media preference given just engagements of the corresponding posts the user reacts to. We also need to condition on the sentiment of other users who reacted to the same post. ## 3.6. Relational d-separation Relational model describes a template for many possible instantiations of a relational schema. In order to reason about conditional independence facts entailed in all instances of a given relational template, Maier et al. (2013b) develop a relational counterpart for d -separation criteria. Two sets of relational variables X and Y from a given perspective are said to be d -separated by another set Z if and only if the terminal sets of X and Y are d -separated by the terminal set of Z from the given perspective in all possible ground graphs of the given model. Maier et al. (2013b) introduce AGG as a means to reason about relational d -separation queries from a given perspective. The soundness and completeness of relational d -separation for AGG relies on the following assumptions: ## A 1 The relational model is acyclic. ## A 2 There are no unobserved confounders in the relational model. Here, soundness refers to the fact that any d -separation relationship found in AGG implies corresponding d -separation relationship in all ground graphs it represents whereas completeness claims that the d -separation facts that hold across all ground graphs are also entailed by d -separation on the AGG. The soundness of relational d -separation under AGG is already proved by Maier et al. (2013b). However, the conditions under which completeness holds have been an open question since Lee and Honavar (2015) show that the initial formulation of Maier et al. (2013b) is not complete. We resolve this question in Section 4.4 and show that AGG is also complete under certain realistic assumptions. Figure 3: Ground graph and σ -AGG for the cyclic relational model shown in Figure 1. <details> <summary>Image 3 Details</summary>  ### Visual Description ## Diagram: Social Network Interaction Models ### Overview The image presents two diagrams, labeled (a) and (b), illustrating different models of social network interactions. Diagram (a) depicts a simplified model with named entities and their relationships, while diagram (b) presents a more complex model using abstract categories of user actions and their interdependencies. ### Components/Axes **Diagram (a):** * **Nodes:** Represented as ovals, each labeled with a specific entity. * Alice.Sentiment * P1.Engagement * Bob.Sentiment * P2.Engagement * M1.Preference * **Edges:** Represented as arrows, indicating the direction of influence or interaction between entities. **Diagram (b):** * **Nodes:** Represented as rounded rectangles, each labeled with a set of user actions or categories enclosed in square brackets. * \[USER, REACTS, POST, CREATES, MEDIA, CREATES, POST] Engagement * \[USER] Sentiment * \[USER, REACTS, POST] Engagement * \[USER, REACTS, POST, CREATES, MEDIA] Preference * \[USER, REACTS, POST, REACTS, USER] Sentiment * \[USER, REACTS, POST, REACTS, USER, REACTS, POST] Engagement * **Edges:** Represented as arrows, indicating the direction of influence or interaction between categories. ### Detailed Analysis **Diagram (a):** * Alice.Sentiment influences P1.Engagement and P2.Engagement. * P1.Engagement influences Alice.Sentiment, Bob.Sentiment, and M1.Preference. * Bob.Sentiment influences P1.Engagement. * P2.Engagement influences Alice.Sentiment and M1.Preference. * M1.Preference is influenced by P1.Engagement and P2.Engagement. **Diagram (b):** * \[USER, REACTS, POST, CREATES, MEDIA, CREATES, POST] Engagement influences \[USER, REACTS, POST, CREATES, MEDIA] Preference. * \[USER] Sentiment influences \[USER, REACTS, POST] Engagement and vice versa. * \[USER, REACTS, POST, REACTS, USER] Sentiment influences \[USER] Sentiment and \[USER, REACTS, POST] Engagement. * \[USER, REACTS, POST, CREATES, MEDIA, CREATES, POST] Engagement and \[USER, REACTS, POST, REACTS, USER, REACTS, POST] Engagement are related by an intersection symbol (∩), suggesting a shared subset of actions. * \[USER, REACTS, POST, REACTS, USER, REACTS, POST] Engagement influences \[USER, REACTS, POST, REACTS, USER] Sentiment. * \[USER, REACTS, POST, REACTS, USER, REACTS, POST] Engagement influences \[USER, REACTS, POST] Engagement. ### Key Observations * Diagram (a) uses specific entities (Alice, Bob, P1, P2, M1) to represent the social network, while diagram (b) uses abstract categories of user actions. * Both diagrams illustrate the flow of influence or interaction between different elements within the social network. * Diagram (b) is more complex, with multiple interconnected categories and a shared subset of actions represented by the intersection symbol. ### Interpretation The diagrams represent two different approaches to modeling social network interactions. Diagram (a) provides a simplified view with specific entities, which might be useful for understanding individual relationships and influences. Diagram (b) offers a more abstract and generalized model, focusing on the types of user actions and their interdependencies. This model could be used to analyze broader patterns of engagement and sentiment within the network. The intersection between two engagement categories suggests that certain actions can contribute to multiple types of engagement, highlighting the complexity of user behavior in social networks. </details> ## 4. Relational Systems With Cycles In this section, we develop definitions for cyclic relational causal models (RCM) and an abstract representation that allows causal reasoning and discovery. We introduce a criterion for abstracting cyclic RCMs and provide proofs for its correctness. ## 4.1. Cyclic RCM An RCM is cyclic when the set of relational dependencies form one or more arbitrary length cycles. Definition 4 (Cyclic RCM) A relational model M = ( S , D ) is said to be cyclic if the set of relational dependencies D constructs one or more directed cycles of arbitrary length. Cycles in RCM represent equilibrium states among a set of nodes in the ground graphs. It implies that the ground graphs are no longer guaranteed to be DAGs. In order to facilitate this, we propose a revised definition of relational dependency provided by Maier et al. (2013b) by relaxing the restriction of having different attribute classes for cause and effect. Definition 5 (Relational Dependency) A relational dependency [ I j , ..., I k ] .X ′ → [ I j ] .X is a directed probabilistic dependence from any attribute class X ′ to X through the relational path [ I j , ..., I k ] such that I j , ..., I k ∈ E ∪ R , X,X ′ ∈ A . Note that it is possible to have X = X ′ . Figure 1 shows an example relational model with cyclic dependencies (i.e. dashed arrows). We see a pair of dependencies [ Post, Reacts, User ] .Sentiment → [ Post ] .Engagement and [ Post ] .Engagement → [ Post, Reacts, User ] .Sentiment which are inverse to each other and form a feedback loop. However, this mere feedback loop prohibits the use of AGG to answer relational causal query that asks whether a user's Sentiment about a post they reacted to is independent of the preference of media given the posts. Unfortunately, the work by Maier et al. (2013b) is not sufficient to reason about conditional independence relationships in the ground graphs of such relational models since it contain cycles. This motivates us to introduce a new criterion that enables the abstraction of relational queries with cyclic dependencies over all ground graphs. ## 4.2. Relational σ -separation Conditional independence facts are only useful when they hold across all ground graphs that are consistent with the model. Maier et al. (2013b) show that relational d -separation is sufficient to achieve that for acyclic models. However, such abstraction is not possible for cyclic models since the correctness of d -separation is not guaranteed for cyclic graphical models (Spirtes, 1995; Neal, 2000). In this work, we propose the following definition of relational σ -separation specifically for cyclic relational models: Definition 6 (Relational σ -separation) Let X , Y , and Z be three distinct sets of relational variables with the same perspective B ∈ E ∪ R defined over relational schema S . Then, for relational model structure M , X and Y are σ -separated by Z if and only if, for all skeletons s ∈ ∑ S , X | b and Y | b are σ -separated by Z | b in ground graph GG M s for all instances b ∈ s ( B ) where s ( B ) refers to the instances of B in skeleton s . The definition directly follows from the definition of relational d -separation. If there exists even one skeleton and faithful distribution represented by the relational model for which X ⊥ ⊥ Y | Z , then X | b and Y | b are not σ -separated by Z | b for b ∈ s ( B ) . ## 4.3. σ -Abstract Ground Graph We refer to the lifted representation for cyclic RCMs as σ -abstract ground graph or σ -AGG. A σ -AGG is constructed using the same extend method used to construct AGG (Maier et al., 2013b). Definition 7 ( σ -Abstract Ground Graph) An abstract ground graph σ -AGG M = ( V, E ) for relational model structure M = ( S , D ) , perspective B ∈ E ∪ R , and hop threshold h ∈ N 0 is a directed graph that abstracts the dependencies D for all ground graphs GG M s , where s ∈ ∑ S . The σ -AGG M s is a directed cyclic graph with the following nodes and edges: 1. V = RV ∪ IV , where 2. (a) RV is the set of relational variables with a path of length at most h + 1. 3. (b) IV are intersection variables between pairs of relational variables that could intersect 2. E = RVE ∪ IVE , where 5. (a) RVE ⊂ RV × RV are the relational variable edges 6. (b) IVE ⊂ ( IV × RV ) ∪ ( RV × IV ) are the intersection variable edges. This is the set of edges that intersection variables 'inherit' from the relational variables that they were created from Since the construction of an AGG and a σ -AGG M s is identical, they share mostly identical properties as defined by Maier et al. (2013b) for AGG. The main difference being the existence of cycles. Consequently, the goal of σ -AGG M s is to reason about relational σ -separation queries instead of relational d -separation. Figure 3( b ) shows the σ -AGG M s corresponding to the cyclic RCM in Figure 1 with a pairwise feedback loop. It is similar to the AGG in Figure 2( c ) but allows cycles without violating the conditional independence statements under σ -separation which are otherwise undefined with d -separation. ## 4.4. Soundness and Completeness of Relational σ -separation In order to discuss soundness and completeness of relational σ -separation we first address the open problem of necessary conditions for the completeness of relational d -separation. Previous work has shown that the original claim of completeness of relational d -separation by Maier et al. (2013a) cannot be guaranteed for any relational model (Lee and Honavar, 2015). A counterexample has been developed as well. In this work, we show that relational d -separation is complete under the following assumption: ## A 3 The degree of any entity in the relational skeleton is greater than 1. Note that, this assumption is about the topology of the ground graphs, i.e., the network which defines how entities are connected to each other. It only allows entities that are connected to at least two other entities. For example, if the entities are users in a social network, the framework would only consider users who have degree at least two, i.e., are connected to at least two other users. While this restricts the space of graph topologies allowable under the results in this work, many networks observed in real world domains, such as social networks, have minimum degree greater than one. We introduce the following lemma that establishes sufficient conditions for AGGs to be realizable in ground graphs. This result may be of independent interest, since it provides sufficient conditions for soundness in the original presentation of relational d -separation under additional assumptions (Maier et al., 2013b; Lee and Honavar, 2015). Lemma 1 Under assumption 3, every abstract ground graph can be realized as a ground graph. That is, for every acyclic relational model M and skeleton s ∈ ∑ S any relational variable in AGG M s has non-empty terminal sets in some ground graph GG M s . ## Proof We first consider the conditions under which empty terminal sets can occur, resulting in an AGG that is unrealizable in the ground graphs. There are two necessary and sufficient conditions for empty terminal sets to appear in all ground graphs corresponding to an AGG. First, there must be at least one intersection variable present in the AGG. If no intersection variable exist in the AGG, then the completeness proof of relational d -separation by Maier et al. (2013b) holds. The second condition is that the intersection must be on a path consisting of only one-to-one relationships. In order to understand this condition, lets look at an example with the following relational paths from a hypothetical relational model which is a generalization of the counterexample given by Lee and Honavar (2015) 2 : $$\begin{array} { r l } & { \bullet P = [ E _ { i } , \dots , R _ { j } , \dots , E _ { k } ] } & { \bullet Q = [ E _ { i } , \dots , R _ { j } , \dots , R _ { m } , E _ { k } , \dots , E _ { q } ] } \\ & { \bullet S = [ E _ { i } , \dots , R _ { j } , \dots , R _ { m } , \dots , E _ { s } ] } & { \bullet S ^ { \prime } = P + [ R _ { m } , \dots , E _ { s } ] } \end{array}$$ where E i , E k , E q , E s are some entity classes, R j , R m are relationship classes, ' . . . ' are arbitrary valid sequences of entities and relationships, and + represents the concatenation of relational paths. Let's assume two relational dependencies exist in the given model, P.X → Q.Y and S.Z → Q.Y where X,Y,Z are attributes of corresponding entity classes. By definition, the corresponding edges P.X → Q.Y , S.Z → Q.Y appear in the AGG. Since S and S ′ are intersectable an additional edge S.Z ∩ S ′ .Z → Q.Y also appears in the AGG. Such a model can be realized in many possible ground graphs. However, if we restrict the relationships to be strictly one-to-one, then there is only one skeleton structure possible to satisfy the relational dependencies at the cost of S ′ .Z having empty 2. The complete counterexample and figure explaining it is given in the Appendix terminal sets since an intance of R m can connect to only one instance of E k . If we allow many-tomany relationships then we can always construct a skeleton where an instance of R m connects to two instances of E k to produce non-empty terminal sets for both Q and S ′ . Since assumption 3 prohibits the second condition, it essentially implies that any relational variable in AGG M s results into non-empty terminal sets in corresponding ground graphs for every acyclic relational model M and skeleton s ∈ ∑ S which completes the proof for Lemma 1. The following proposition establishes the completeness of AGG for relational d -separation under the assumption of a minimum degree greater than 1. Proposition 1 AGG is sound and complete for relational d -separation under assumption 3. Proof Following lemma 1, the original proof of soundness and completeness of relational d -separation by Maier et al. (2013b) directly applies which proves proposition 1. The correctness of our approach to relational σ -separation relies on several facts which are similar to the case for AGG: (1) σ -separation is valid for directed cyclic graphs; (2) ground graphs are directed cyclic graphs; and (3) σ -AGGs are directed cyclic graphs that represent exactly the edges that could appear in all possible ground graphs. Note that we no longer need assumption 1, but assumptions 2 and 3 are adopted from relational d -separation. Using the previous definitions and lemmas, the following additional assumptions and sequence of results proves the correctness of our approach to identifying independence in cyclic relational models. A 4 The given cyclic relational model structure is σ -faithful. Theorem 1 The rules of σ -separation are sound and complete for cyclic directed graphs. Proof Forr´ e and Mooij (2017) show that for quite general structural equation models HEDGes 3 always follow a directed global Markov property based on σ -separation which completes the proof for soundness since directed cyclic graphs are subsets of HEDGes. The completeness claim is already covered by Assumption 4. Theorem 2 For every cyclic RCM M = ( S , D ) and skeleton s ∈ ∑ S such that relational variables involved in D are non-empty, the ground graph GG M s is a cyclic directed graph. ## Proof Let's assume for contradiction that there exists an acyclic ground graph g which is a realization of a given cyclic RCM M = ( S , D ) and skeleton s ∈ ∑ S . According to the definition of ground graphs, the edges of ground graphs are directly constructed based on the relational dependencies of the model. Definition 4 states that a cyclic RCM consists of one or more cycles formed by the relational dependencies. Assume a cycle in cyclic RCM is formed by the pair of relational dependencies as follows: a) P.j → Q.k , and b) Q.k → P.j where P and Q are relational paths from some perspective b and i, j refers to two attribute classes. By construction of g there must be two nodes a, b in g corresponding to P.j and Q.k respectively. Moreover, the definition of g requires two edges a → b and b → a to be present in the ground graph. But such edges constructs a cycle which is contradictory to the initial claim. Thus, the ground graph g must be cyclic. 3. The definition of HEDG is provided in the Appendix Theorem 3 For every cyclic relational model structure M and perspective B ∈ E ∪ R , the σ -AGG M s is sound and complete for all ground graphs GG M s with skeleton s ∈ ∑ S . The proof follows from the proof of soundness and completeness of AGG (Maier et al., 2013b). The complete proof is provided in the Appendix. Theorem 4 The abstract ground graph σ -AGG M s is a cyclic directed graph if and only if the underlying relational model structure is cyclic. ## Proof Let M be an arbitrary (possibly) cyclic relational model structure, and let B ∈ E ∪ R be an arbitrary perspective. It is clear by Definition 7 that every edge in the abstract ground graph σ -AGG M s is directed by construction. Assume for contradiction that no cycles exists in σ -AGG M s even if the relational dependencies form one or more cycles. Now assume the following two dependencies are part of the given relational model M : 1. [ I j , ..., I k ] .X → [ I j ] .Y ∈ D , 2. [ I j ] .Y → [ I j , ..., I k ] .X ∈ D where I j , ..., I k ∈ E ∪ R . By Definition 7, all edges inserted in σ -AGG M s are drawn from some dependency in M and edges in σ -AGG M s are constructed for all the dependencies in D . As a result there must be corresponding edges in the σ -AGG M s for both dependencies that form a cycle, which contradicts the assumption. Now, assume that a σ -AGG M s is acyclic even if the underlying RCM is cyclic. Using the same argument as above we can say that the edges in the σ -AGG M s constructed based on the dependencies in D . If a cycle exists in the σ -AGG M s it directly implies the existence of a cycle in the RCM which leads to a contradiction. Thus the proof completes from both directions. Theorem 5 Relational σ -separation is sound and complete for σ -AGG. Let M be a (possibly) cyclic relational model structure, and let X , Y , and Z be three distinct sets of relational variables defined over relational schema S . Then, X and Y are σ -separated by Z on the abstract ground graph σ -AGG M s if and only if for all skeletons s ∈ ∑ S and for all perspectives b ∈ s ( B ) , X | b and Y | b are σ -separated by Z | b in ground graph GG M s . ## Proof We must show that σ -separation on an abstract ground graph implies σ -separation on all ground graphs it represents (soundness) and that σ -separation facts that hold across all ground graphs are also entailed by σ -separation on the abstract ground graph (completeness). The proof follows from the proof of soundness and completeness of AGG (Maier et al., 2013b). ## Soundness: Assume that ¯ X and ¯ Y are σ -separated by ¯ Z on σ -AGG M s . Assume for contradiction that there exists an item instance b such that X | b and Y | b are not σ -separated by Z | b in the ground graph GG M s for some arbitrary skeleton s . Then, there must exist a σ -connecting path p from some x ∈ ¯ X | b to some y ∈ ¯ Y | b given all z ∈ ¯ Z | b . By Theorem 3, σ -AGG M s is complete, so all edges in GG M s are captured by edges in σ -AGG M s . So, path p must be represented from some node in { N x | x ∈ N x | b } to some node in { N y | y ∈ N y | b } , where N x , N y are nodes in σ -AGG M s . If p is σ -connecting in GG M s , then it is σ -connecting in σ -AGG M s , implying that ¯ X and ¯ Y are not σ -separated by ¯ Z . So, X | b and Y | b must be σ -separated by Z | b . ## Completeness: Assume that X | b and Y | b are σ -separated by Z | b in the ground graph GG M s for all skeletons s for all b ∈ s ( B ) . Assume for contradiction that ¯ X and ¯ Y are not σ -separated by ¯ Z on σ -AGG M s . Then, there must exist a σ -connecting path p for some relational variable X ∈ ¯ X to some Y ∈ ¯ Y given all Z ∈ ¯ Z . By Theorem 3, σ -AGG M s is sound, so every edge in σ -AGG M s must correspond to some pair of variables in some ground graph. So, if p is σ -connecting in σ -AGG M s , then there must exist some skeleton s such that p is σ -connecting in GG M s for some b ∈ s ( B ) , implying that σ -separation does not hold for that ground graph. So, ¯ X and ¯ Y must be σ -separated by ¯ Z on σ -AGG M s . Maier et al. (2013b) show that relational d -separation is equivalent to the Markov condition on acyclic relational models. However, it doesn't hold for cyclic relational model. Here, we show how relational σ -separation is equivalent to the Markov condition on cyclic relational models. Definition 8 (Relational σ -separation Markov Condition) Let X,Y,Z be relational variables for perspective B ∈ E ∪ R defined over relational schema S . For any solution ( X , ) of a relational model M which follows a simple SCM, $$X \underset { \mathcal { M } } { \overset { \perp } { \| } } Y | Z \implies \pm b { \ m a t h s c r { x } } _ { X } \underset { \mathbb { P } _ { \mathcal { M } } ( \pm b { \ m a t h s c r { x } } ) } { \overset { \perp } { \| } } \pm b { \ m a t h s c r { X } } _ { Y } | \pm b { \ m a t h s c r { X } } _ { Z } , i f a n d o n l y i f$$ $$\underset { G G _ { \mathcal { M } } } { x \overset { \sigma } { \| } } y | z \implies \mathfrak { x } _ { x } ^ { \prime } \underset { \mathbb { P } _ { G G _ { \mathcal { M } } } ( \mathcal { X } ^ { \prime } ) } { \overset { \| } { \perp } } \mathcal { X } _ { y } ^ { \prime } | \mathcal { X } _ { z } ^ { \prime } , f o r \, \forall x \in X | _ { b } , \, \forall y \in Y | _ { b } , \, \forall z \in Z | _ { b }$$ $$X _ { \mathcal { M } } ^ { \underline { \sigma } } | Y | Z \implies x _ { X } _ { \mathbb { P } _ { \mathcal { M } } ( \mathcal { X } ) } \, | x _ { X } \, \underline { \perp }$$ in ground graph GG M s for all skeletons s ∈ ∑ S and for all b ∈ s ( B ) where ( X ′ , ′ ) refers to the solution of the SCM corresponding to the ground graphs. In other words, σ -separation of two relational variables X and Y given a third relational variable Z would imply X and Y are conditionally independent given Z if and only if, for all instances of X , Y , Z in all possible ground graphs, the same condition holds. Since ground graphs of cyclic RCMare directed cyclic graphs and σ -separation on σ -AGG M s is sound and complete (by Theorem 5), we can conclude that relational σ -separation is equivalent to the relational Markov property. ## 5. Conclusion Cycles or feedback loops are common elements of many real-world system. Unfortunately, it is hardly studied in the field of causal inference primarily because it breaks the nice properties of directed acyclic graphs. As a result, cycles and feedback loops are mostly avoided in the domain of relational causal model. In this study, we take a step forward to bridge this gap by developing an abstract representation and a criterion to reason about statistical relationships in relational models with or without cycles under a general framework. We show that the new criterion called σ -separation can consistently capture the statistical independence relationships of all possible instantiations of a relational causal model. We believe that this work will open the door for further development including but not limited to causal structure learning of relational models with cycles. ## 6. Acknowledgment This material is based on research sponsored in part by the Defense Advanced Research Projects Agency (DAPRA) under contract number HR001121C0168 and the National Science Foundation under grant No. 2047899. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of DARPA or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein. ## References - Rohit Bhattacharya, Daniel Malinsky, and Ilya Shpitser. Causal inference under interference and network uncertainty. In Uncertainty in Artificial Intelligence , pages 1028-1038. PMLR, 2020. - N. A. Christakis and J. H. Fowler. The spread of obesity in a large social network over 32 years. NEJM , 357(4):370-379, 2007. - A Philip Dawid. Beware of the dag! In Causality: objectives and assessment , pages 59-86. PMLR, 2010. - Patrick Forr´ e and Joris M Mooij. Markov properties for graphical models with cycles and latent variables. arXiv preprint arXiv:1710.08775 , 2017. - D. Heckerman, C. Meek, and D. Koller. Probabilistic entity-relationship models, prms, and plate models. Introduction to statistical relational learning , pages 201-238, 2007. - Steffen L Lauritzen and Thomas S Richardson. Chain graph models and their causal interpretations. Journal of the Royal Statistical Society: Series B (Statistical Methodology) , 64(3):321-348, 2002. - Sanghack Lee and Vasant Honavar. Towards robust relational causal discovery. In Uncertainty in Artificial Intelligence , pages 345-355. PMLR, 2020. - Sanghack Lee and Vasant G Honavar. Lifted representation of relational causal models revisited: Implications for reasoning and structure learning. In ACI@UAI , 2015. - Marc Maier, Katerina Marazopoulou, David Arbour, and David Jensen. A sound and complete algorithm for learning causal models from relational data. arXiv preprint arXiv:1309.6843 , 2013a. - Marc Maier, Katerina Marazopoulou, and David Jensen. Reasoning about independence in probabilistic models of relational data. arXiv preprint arXiv:1302.4381 , 2013b. - Radford M Neal. On deducing conditional independence from d-separation in causal graphs with feedback (research note). Journal of Artificial Intelligence Research , 12:87-91, 2000. - Elizabeth L Ogburn, Tyler J VanderWeele, et al. Causal diagrams for interference. Statistical science , 29(4):559-578, 2014. - Elizabeth L Ogburn, Ilya Shpitser, and Youjin Lee. Causal inference, social networks and chain graphs. Journal of the Royal Statistical Society: Series A (Statistics in Society) , 183(4):16591676, 2020. - Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference . Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1988. - Kari Rantanen, Antti Hyttinen, and Matti J¨ arvisalo. Discovering causal graphs with cycles and latent confounders: An exact branch-and-bound approach. Int. J. Approx. Reason. , 117:29-49, 2020. - T Richardson. A discovery algorithm for directed cyclic graphs. In Proceedings of the 12th Conference on Uncertainty in Artificial Intelligence , 1996. - Thomas S. Richardson. A characterization of markov equivalence for directed cyclic graphs. Int. J. Approx. Reason. , 17:107-162, 1997. - Donald B Rubin. Randomization analysis of experimental data: The fisher randomization test comment. Journal of the American Statistical Association , 75(371):591-593, 1980. - Cosma Rohilla Shalizi and Andrew C Thomas. Homophily and contagion are generically confounded in observational social network studies. Sociological methods & research , 40(2):211239, 2011. - Ilya Shpitser. Segregated graphs and marginals of chain graph models. Advances in Neural Information Processing Systems , 28:1720-1728, 2015. - Peter L Spirtes. Directed cyclic graphical representations of feedback models. Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence , 1995. - Eric V. Strobl. A constraint-based algorithm for causal discovery with cycles, latent variables and selection bias. International Journal of Data Science and Analytics , pages 1-24, 2019. - Tyler J VanderWeele, Eric J Tchetgen Tchetgen, and M Elizabeth Halloran. Components of the indirect effect in vaccine trials: identification of contagion and infectiousness effects. Epidemiology (Cambridge, Mass.) , 23(5):751, 2012. ## Appendix A. Preliminaries ## A.1. Directed Graphs with Hyperedges (HEDGes) A directed graph with hyperedges or hyperedged directed graph (HEDG) is a tuple G = ( V , E , H ) , where ( V , E ) is a directed graph (with or without cycles) and H a simplicial complex over the set of vertices V of G . A simplicial complex H over V is a set of subsets of V such that: 1) all single element sets { v } are in H for v ∈ V , and 2) if F ∈ H then also all subsets F ′ ⊆ F are elements of V . The general directed global Markov property (gdGMP) for the HEDGes is stated as follows: Definition 9 (gdGMP) For all subsets X,Y,Z ⊆ V we have the implication: $$X _ { \frac { \| } { G } } ^ { \stackrel { \sigma } { \| } } Y | Z \implies X _ { \frac { \| } { P _ { v } } } Y | Z$$ ## A.2. Counterexample by Lee and Honavar (2015) The following counterexample shows that AGG is not complete for relational d -separation. Example. Let S = 〈E , R , A , card 〉 be a relational schema such that: E = { E i } 5 i =1 ; R = { R j } 3 j =1 with R 1 = 〈 E 1 , E 2 , E 4 〉 , R 2 = 〈 E 2 , E 3 〉 , R 3 = 〈 E 3 , E 4 , E 5 〉 ; A = { E 2 : { Y } , E 3 : { X } , E 5 : { Z }} ; and ∀ R ∈R ∀ E ∈E card ( R,E ) = one . Let M = 〈S , D 〉 be a relational model with $$\pm b { \ m a t h s c r D } = \{ D _ { 1 } . X \to [ I _ { Y } ] . Y , D _ { 2 } . Z \to [ I _ { Y } ] . Y \}$$ such that D 1 = [ E 2 , R 2 , E 3 , R 3 , E 4 , R 1 , E 2 , R 2 , E 3 ] and D 2 = [ E 2 , R 2 , E 3 , R 3 , E 5 ] . Let P.X,Q.Y,S.Z,S ′ .Z be four relational variables of the same perspective B = E 1 where their relational paths are distinct where - P = [ E 1 , R 1 , E 2 , R 2 , E 3 ] · Q = [ E 1 , R 1 , E 4 , R 3 , E 3 , R 2 , E 2 ] - S = [ E 1 , R 1 , E 4 , R 3 , E 5 ] · S ′ = [ E 1 , R 1 , E 2 , R 2 , E 3 , R 3 , E 5 ] Figure 4: Construction of the counterexample by Lee and Honavar (2015). The notations inside the circles/rhombus refer to instances of the corresponding entity/relationship classes which are mentioned outside the shapes. The dashed lines represent relational dependencies. The dotted line represents a hypothetical connection that can nullify the counterexample under assumption 3. <details> <summary>Image 4 Details</summary>  ### Visual Description ## Diagram: Relational Graph ### Overview The image presents a relational graph diagram, illustrating relationships between entities and their attributes. The diagram consists of nodes representing entities and attributes, connected by edges that represent relationships. ### Components/Axes * **Nodes:** * `i_y`: Located at the top-left. * `i'_x`: Located at the top-center. * `i_z`: Located at the top-right. * `i_x`: Located at the bottom-left. * `e_b`: Located at the bottom-right. * `r_n`: Located at the top-center-right, diamond-shaped. * `r_m`: Located at the bottom-center-right, diamond-shaped. * **Edges:** * Solid lines connecting `i_y` to `i'_x`, `i'_x` to `r_n`, `r_n` to `i_z`, `i_x` to `r_m`, `r_m` to `e_b`, and `r_n` to `r_m`. * Dashed line connecting `i_z` to `i_y`. * Dotted line connecting `i_x` to `i_y`. * **Labels:** * `E_y` near `i_y`. * `E_x` near the edge connecting `i_y` and `i'_x`. * `E_x` near the edge connecting `i_x` and `i'_x`. * `E_b` near `e_b`. * `E_m` near the edge connecting `i_x` and `r_m`. ### Detailed Analysis The diagram illustrates a network of entities (`i_y`, `i'_x`, `i_z`, `i_x`, `e_b`) and relations (`r_n`, `r_m`). The solid lines indicate direct relationships, while the dashed and dotted lines might indicate different types of indirect relationships or dependencies. The labels `E_y`, `E_x`, `E_b`, and `E_m` likely represent attributes or properties associated with the entities or relationships. ### Key Observations * The graph has a roughly rectangular structure. * `i_y` seems to be a central node, receiving connections from both `i'_x` and `i_z`. * `r_n` and `r_m` are relational nodes connecting different parts of the graph. ### Interpretation The diagram likely represents a relational model, where entities are connected through relationships. The dashed and dotted lines suggest different types of dependencies or indirect relationships. The labels `E_y`, `E_x`, `E_b`, and `E_m` could represent attributes or properties associated with the entities or relationships. The diagram could be used to model various systems, such as social networks, knowledge graphs, or database schemas. </details> Given the above example, Lee and Honavar (2015) make two claims: $$C l a i m \, 1 . ( \overline { P . X } \not \leq \overline { S ^ { \prime } . Z } | \overline { Q . Y } ) _ { A G G _ { M } }$$ $$\begin{array} { r l } & { C l a i m \, 2 . T h e r e i s n o s \in \sum _ { S } a n d b \in s ( B ) s u c h t h a t \left ( P . X | _ { b } \not \subset S ^ { \prime } . Z | _ { b } | Q . Y | _ { b } \right ) _ { G G _ { M _ { s } } } } \\ & { F i n } \end{array}$$ Figure 4 shows the general pattern discussed in Section 4.4 regarding the construction of the counterexample by Lee and Honavar (2015). ## Appendix B. Proofs The proof for Theorem 3 is given as follows: ## Proof Let M = ( S , D ) be an arbitrary cyclic relational model structure and B ∈ E ∪ R an arbitrary perspective. Soundness: To prove that σ -AGG M s is sound, we must show that for every edge P k .X → P j .Y in σ -AGG M s , there exists a corresponding edge i k .X → i j .Y in the ground graph GG M s for some skeleton s ∈ ∑ S , where i k ∈ P k | b and i j ∈ P j | b for some b ∈ s ( B ) . There are three subcases, one for each type of edge in an abstract ground graph: (a) Let [ B,..., I k ] .X → [ B,..., I j ] .Y ∈ RVE be an arbitrary edge in σ -AGG M s between a pair of relational variables. Assume for contradiction that there exists no edge i k .X → i j .Y in any ground graph: $$\begin{array} { r } { \forall s \in \Sigma _ { \mathcal { S } } , \forall i _ { k } \in [ B , \dots , I _ { k } ] | _ { b } , \forall i _ { j } \in [ B , \dots , I _ { j } ] | _ { b } } \\ { ( i _ { k } . X \to i _ { j } . Y \notin G G _ { \mathcal { M } _ { S } } ) } \end{array}$$ By Definition 7 for σ -AGG M s , if [ B,..., I k ] .X → [ B,..., I j ] .Y ∈ RVE , then the model must have dependency [ I j , ..., I k ] .X → [ I j ] .Y ∈ D such that [ B,..., I k ] ∈ extend ([ B,..., I j ] , [ I j , ..., I k ]) . So, by the definition of ground graphs, there is an edge from every i k .X to every i j .Y , where i k is in the terminal set for i j along [ I j , ..., I k ] . Therefore, there exists a ground graph GG M s such that i k .X → i j .Y ∈ GG M s , which contradicts the assumption. - (b) Let P 1 .X ∩ P 2 .X → [ B,..., I j ] .Y ∈ IVE be an arbitrary edge in σ -AGG M s between an intersection variable and a relational variable, where P 1 = [ B,..., I m , ..., I k ] and P 2 = [ B,..., I n , ..., I k ] with I m = I n . By Definition 7, if the σ -abstract ground graph has edge P 1 .X ∩ P 2 .X → [ B,..., I j ] .Y ∈ IVE , then either P 1 .X → [ B,..., I j ] .Y ∈ RVE or P 2 .X → [ B,..., I j ] .Y ∈ RVE . Then, as shown in case (a), there exists an i j ∈ [ B,..., I j ] | b such that i k .X → i j .Y ∈ GG M s , which contradicts the assumption. (c) Let [ B,..., I k ] .Y → P 1 .X ∩ P 2 .X ∈ IVE be an arbitrary edge in σ -AGG M s between an intersection variable and a relational variable, where P 1 = [ B,..., I m , ..., I j ] and P 2 = [ B,..., I n , ..., I j ] with I m = I n . The proof follows case (b) to show that there exists a skeleton s ∈ ∑ S and b ∈ s ( B ) such that for all i k ∈ [ B,..., I k ] | b there exists an i j ∈ P 1 ∩ P 2 | b such that i k .X → i j .Y ∈ GG M s . Completeness: To prove that the σ -abstract ground graph σ -AGG M s is complete, we show that for every edge i k .X → i j .Y in every ground graph GG M s where s ∈ ∑ S , there is a set of corresponding edges in σ -AGG M s . Specifically, the edge i k .X → i j .Y yields two sets of relational variables for some b ∈ s ( B ) , namely P k .X = { P k .X | i k ∈ P k | b } and P j .Y = { P j .Y | i j ∈ P j | b } . Note that all relational variables in both P k .X and P j .Y are nodes in σ -AGG M s , as are all pairwise intersection variables. We show that for all P k .X ∈ P k .X and for all P j .Y ∈ P j .Y either (a) P k .X → P j .Y ∈ σ -AGG M s (b) P k .X ∩ P ′ k .X → P j .Y ∈ σ -AGG M s where P ′ k .X ∈ P k .X , or (c) P k .X → P j .Y ∩ P ′ j .Y ∈ σ -AGG M s where P ′ j .Y ∈ P j .Y . Let s ∈ ∑ S be an arbitrary skeleton, let i k .X → i j .Y ∈ GG M s be an arbitrary edge drawn from [ I j , ..., I k ] .X → [ I j ] .Y ∈ D , and let P k .X ∈ P k .X, P j .Y ∈ P j .Y be an arbitrary pair of relational variables. - (a) If P k ∈ extend ( P j , [ I j , ..., I k ]) , then P k .X → P j .Y ∈ σ -AGG M s by Definition 7. - (b) If P k / ∈ extend ( P j , [ I j , ..., I k ]) , but ∃ P ′ k ∈ extend ( P j , [ I j , ..., I k ]) such that P ′ k .X ∈ P k .X , then P ′ k .X → P j .Y ∈ σ -AGG M s , and P k .X ∩ P ′ k .X → P j .Y ∈ σ -AGG M s by Definition 7. - (c) If ∀ P ∈ extend ( P j , [ I j , ..., I k ])( P.X / ∈ Pk.X ) , then ∃ P ′ j such that i j ∈ P ′ j | b and P k ∈ extend ( P ′ j , [ I j , ..., I k ]) . Therefore, P ′ j .Y ∈ P j .Y, P k .X → P ′ j .Y ∈ σ -AGG M s , and P k .X → P ′ j .Y ∩ P j .Y ∈ σ -AGG M s by Definition 7.