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 \n ## Diagram: User-Post-Media Interaction Loop ### Overview The image depicts a diagram illustrating a feedback loop between a User, a Post, and Media. The diagram uses shapes (ovals and diamonds) and arrows to represent concepts and their relationships. It appears to model how user sentiment influences post engagement, which in turn shapes media preference, and potentially loops back to influence user sentiment. ### Components/Axes The diagram consists of three main sections, labeled "USER", "POST", and "MEDIA", arranged horizontally from left to right. Within each section are: * **USER:** Contains an oval labeled "Sentiment". * **POST:** Contains an oval labeled "Engagement" and a diamond labeled "REACTS". * **MEDIA:** Contains an oval labeled "Preference" and a diamond labeled "CREATES". Arrows indicate the direction of influence or flow between these components. A dashed arrow also exists, indicating a feedback loop. ### Detailed Analysis or Content Details The diagram shows the following flow: 1. **USER Sentiment** influences the **POST REACTS** action. This is represented by a solid arrow from "Sentiment" to "REACTS". 2. **POST REACTS** leads to **POST Engagement**. This is represented by a solid arrow from "REACTS" to "Engagement". 3. **POST Engagement** influences **MEDIA CREATES**. This is represented by a solid arrow from "Engagement" to "CREATES". 4. **MEDIA CREATES** leads to **MEDIA Preference**. This is represented by a solid arrow from "CREATES" to "Preference". 5. **MEDIA Preference** influences **USER Sentiment**. This is represented by a dashed arrow from "Preference" to "Sentiment", indicating a feedback loop. The diagram does not contain any numerical data or scales. It is a conceptual model. ### Key Observations The diagram highlights a cyclical relationship between user sentiment, post engagement, and media preference. The dashed arrow suggests that media preference can influence user sentiment, creating a continuous feedback loop. The use of diamonds ("REACTS", "CREATES") suggests actions or processes that mediate the relationship between the ovals (concepts). ### Interpretation This diagram illustrates a model of how social media interactions work. It suggests that user sentiment drives engagement with posts, which in turn influences the type of media that is created and ultimately shapes user preferences. The feedback loop indicates that media preferences can also influence user sentiment, creating a self-reinforcing cycle. This model could be used to understand how to optimize content creation to maximize engagement and influence user preferences. The diagram is a simplified representation of a complex system, and other factors likely play a role in shaping these relationships. The distinction between "REACTS" and "CREATES" suggests that the post itself is a response to user sentiment, while the media is a creation *from* engagement. This is a subtle but important distinction. </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 Interaction Model ### Overview The image presents a diagram illustrating a model of social interaction, likely within a social media context. It depicts three different representations (labeled (a), (b), and (c)) of relationships between users (Alice and Bob), their sentiments, posts (P1, P2, M1), engagement, and preferences. The diagram uses boxes to represent entities and arrows to represent relationships or actions. ### Components/Axes The diagram consists of three sub-diagrams: * **(a):** A simplified representation showing direct reactions and creations. Entities include "Alice", "Bob", "Sentiment", "P1" (Post 1), "P2" (Post 2), "M1" (Media 1), "Engagement", and "Preference". Relationships are labeled "REACTS", "CREATES". * **(b):** A more detailed representation showing the sentiment of Alice and Bob, engagement with posts P1 and P2, and preference for media M1. Entities are labeled as "Alice.Sentiment", "Bob.Sentiment", "P1.Engagement", "P2.Engagement", and "M1.Preference". * **(c):** A complex representation using bracketed terms to represent combined actions and entities. Entities include "[USER].Sentiment", "[USER].Engagement", "[USER].Preference", and combinations of "USER", "REACTS", "POST", "CREATES", "MEDIA", and "Engagement". The symbol "∩" represents intersection. ### Detailed Analysis or Content Details **(a) Simplified Model:** * Alice's Sentiment "REACTS" to P1 (Engagement). * Bob's Sentiment "REACTS" to P1 (Engagement). * P1 (Engagement) "CREATES" M1 (Preference). * P2 (Engagement) "CREATES" M1 (Preference). **(b) Detailed Model:** * Alice.Sentiment influences P2.Engagement. * Bob.Sentiment influences P1.Engagement. * P1.Engagement influences M1.Preference. * P2.Engagement influences M1.Preference. **(c) Complex Model:** * [USER].Sentiment is influenced by [USER, REACTS, POST, REACTS].Engagement. * [USER].Engagement is influenced by [USER, REACTS, POST, CREATES, MEDIA, CREATES, POST].Engagement. * [USER].Preference is influenced by [USER, REACTS, POST, CREATES, MEDIA].Preference. * [USER, REACTS, POST, CREATES, MEDIA, CREATES, POST].Engagement is the intersection of [USER, REACTS, POST, REACTS].Engagement and [USER, REACTS, POST, REACTS].Engagement. * [USER].Engagement is influenced by [USER, REACTS, POST, USER, REACTS].Engagement. ### Key Observations * The diagram progresses from a simplified model (a) to increasingly complex representations (b and c). * The use of bracketed terms in (c) suggests an attempt to generalize the relationships and represent them in a more abstract form. * The intersection symbol in (c) indicates a focus on commonalities or shared influences. * The diagram highlights the interplay between sentiment, engagement, and preference in a social interaction context. ### Interpretation The diagram models how user sentiment and actions (reactions, posts, creations) influence engagement and preference within a social system. The progression from (a) to (c) suggests a move towards a more nuanced understanding of these relationships. Diagram (a) provides a basic overview, while (b) adds detail by explicitly representing the sentiment of individual users. Diagram (c) attempts to generalize these relationships using abstract terms, potentially for use in a computational model or algorithm. The intersection in (c) is particularly interesting. It suggests that certain types of engagement are driven by shared reactions or common interests. The use of "[USER]" suggests a variable representing any user within the system. The diagram implies that user sentiment is influenced by the engagement of other users, creating a feedback loop. The diagram is likely intended to be a conceptual model for understanding social dynamics on platforms where users react to and create content, and where engagement and preference are key metrics. It could be used to inform the design of algorithms for content recommendation, sentiment analysis, or user behavior prediction. The diagram does not provide any quantitative data, but rather focuses on the qualitative relationships between different entities. </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 \n ## Diagram: Conceptual Model of Sentiment and Engagement ### Overview The image presents two diagrams, labeled (a) and (b), depicting conceptual models of sentiment and engagement. Both diagrams use nodes (ovals/rectangles) to represent concepts and directed edges (arrows) to represent relationships between them. Diagram (a) appears to model a dyadic interaction between Alice and Bob, while diagram (b) focuses on user interactions with content. ### Components/Axes Diagram (a) includes the following nodes: * Alice.Sentiment * P2.Engagement * Bob.Sentiment * M1.Preference * P1.Engagement Diagram (b) includes the following nodes: * [USER.Sentiment] * [USER, REACTS, POST, POST].Engagement * [USER, REACTS, POST, CREATES].MediaPreference * [USER, REACTS, POST, CREATES, MEDIA, POST].Engagement * [USER, REACTS, POST, REACTS, USER].Sentiment * [USER, REACTS, POST, REACTS, USER, REACTS, POST].Engagement The diagrams do not have explicit axes, scales, or legends in the traditional chart sense. The relationships are indicated by the direction of the arrows. ### Detailed Analysis or Content Details **Diagram (a):** * An arrow originates from "Alice.Sentiment" and points to "P2.Engagement". * An arrow originates from "Bob.Sentiment" and points to "P1.Engagement". * An arrow originates from "P2.Engagement" and points to "Bob.Sentiment". * An arrow originates from "P1.Engagement" and points to "Alice.Sentiment". * An arrow originates from "Bob.Sentiment" and points to "M1.Preference". * An arrow originates from "P1.Engagement" and points to "M1.Preference". **Diagram (b):** * An arrow originates from "[USER.Sentiment]" and points to "[USER, REACTS, POST, POST].Engagement". * An arrow originates from "[USER, REACTS, POST, POST].Engagement" and points to "[USER, REACTS, POST, CREATES].MediaPreference". * An arrow originates from "[USER, REACTS, POST, POST].Engagement" and points to "[USER, REACTS, POST, CREATES, MEDIA, POST].Engagement". * An arrow originates from "[USER, REACTS, POST, CREATES].MediaPreference" and points to "[USER, REACTS, POST, CREATES, MEDIA, POST].Engagement". * An arrow originates from "[USER, REACTS, POST, CREATES, MEDIA, POST].Engagement" and points to "[USER, REACTS, POST, REACTS, USER].Sentiment". * An arrow originates from "[USER, REACTS, POST, REACTS, USER].Sentiment" and points to "[USER, REACTS, POST, REACTS, USER, REACTS, POST].Engagement". * An arrow originates from "[USER, REACTS, POST, REACTS, USER, REACTS, POST].Engagement" and points to "[USER, REACTS, POST, REACTS, USER].Sentiment". ### Key Observations * Diagram (a) shows a reciprocal relationship between Alice and Bob's sentiments and their respective engagements. It suggests a feedback loop where sentiment influences engagement, and engagement influences sentiment. * Diagram (b) depicts a more complex flow of user interactions, starting with sentiment, progressing through various engagement levels (reacting, posting, creating), and ultimately influencing further sentiment and engagement. * The nodes in diagram (b) are described with increasingly detailed actions, suggesting a progression of user activity. * The intersection symbol (∩) in diagram (b) indicates a logical AND operation between two engagement nodes. ### Interpretation Diagram (a) likely represents a simplified model of social interaction, where individuals' sentiments influence their engagement with each other, and vice versa. The model suggests that sentiment and engagement are mutually reinforcing. Diagram (b) appears to model the relationship between user sentiment and engagement with online content. The diagram suggests that user sentiment drives initial engagement (reacting, posting), which then leads to more complex engagement (creating media). This, in turn, influences further sentiment and engagement, creating a cycle. The increasing detail in the engagement nodes suggests that more active engagement leads to a more nuanced understanding of user sentiment. The intersection symbol indicates that a certain level of engagement is required to trigger a specific sentiment response. The diagrams, taken together, could be interpreted as a model of how social interactions and online engagement influence sentiment and behavior. They highlight the importance of feedback loops and the complex interplay between individual emotions and external stimuli. The diagrams are conceptual and do not provide quantitative data, but they offer a framework for understanding the dynamics of sentiment and engagement. </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 \n ## Diagram: State Transition Diagram (Likely for a Control System) ### Overview The image depicts a state transition diagram, likely representing the states and transitions within a control system or a similar process. It uses circles to represent states and diamonds to represent decision points or events. Arrows indicate transitions between states, labeled with variables representing the conditions or inputs that trigger those transitions. ### Components/Axes The diagram consists of the following components: * **States:** Represented by circles labeled `i_y`, `i_x'`, `i_z`, `i_x`, and `e_b`. * **Decision Points/Events:** Represented by diamonds labeled `r_n` and `r_m`. * **Transitions:** Represented by arrows, labeled with variables `E_y`, `E_x`, `R_n`, `E_z`, `E_m`, and `E_b`. Some transitions are dashed, indicating a different type of transition or condition. * **Labels:** Each state and event is labeled with a unique identifier. ### Detailed Analysis or Content Details The diagram shows the following connections and transitions: 1. **`i_y` to `i_x'`:** A dashed arrow labeled `E_y` connects state `i_y` to state `i_x'`. 2. **`i_x'` to `r_n`:** A solid arrow labeled `E_x` connects state `i_x'` to event `r_n`. 3. **`r_n` to `i_z`:** A solid arrow labeled `R_n` connects event `r_n` to state `i_z`. 4. **`i_z` to `i_x'`:** A solid arrow labeled `E_z` connects state `i_z` to state `i_x'`. 5. **`i_x` to `r_m`:** A solid arrow labeled `E_x` connects state `i_x` to event `r_m`. 6. **`r_m` to `e_b`:** A solid arrow labeled `E_m` connects event `r_m` to state `e_b`. 7. **`e_b` to `i_x`:** A solid arrow labeled `E_b` connects state `e_b` to state `i_x`. 8. **`i_y` to `r_n`:** A dashed arrow connects state `i_y` to event `r_n`. ### Key Observations * The diagram contains a loop involving states `i_x'`, `r_n`, and `i_z`. * The dashed arrows (`E_y` from `i_y` to `i_x'`) and (`i_y` to `r_n`) suggest alternative or conditional transitions. * The diagram appears to represent a cyclical process, with transitions between states and decision points. * The variables `E_x`, `E_y`, `E_z`, `E_m`, `E_b`, and `R_n` likely represent events or conditions that trigger the transitions. ### Interpretation This diagram likely represents a control system or a state machine. The states (`i_y`, `i_x'`, `i_z`, `i_x`, `e_b`) could represent different operational modes or conditions of the system. The events (`r_n`, `r_m`) represent decision points where the system's behavior changes based on certain criteria. The dashed lines suggest that the transition from `i_y` can either go directly to `i_x'` or to `r_n`, depending on some condition not explicitly shown in the diagram. The loop involving `i_x'`, `r_n`, and `i_z` suggests a feedback mechanism or a repeating process. The variables `E_x`, `E_y`, etc., likely represent input signals or events that trigger the transitions. For example, `E_x` might represent a signal indicating that a certain condition has been met, causing the system to transition from `i_x'` to `r_n`. Without further context, it's difficult to determine the specific function of this system. However, the diagram provides a clear visual representation of the states, transitions, and decision points involved in its operation. The diagram is a high-level abstraction and does not provide details about the internal workings of each state or the specific logic used to evaluate the conditions for transitions. </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.