Propensity score matching (PSM) is a widely used method for performing causal inference with observational data. PSM requires fully specifying the set of confounding variables of treatment and outcome. In the case of relational data, this set may include nonintuitive relational variables, i.e., variables derived from the relational structure of the data. In this work, we provide an automated method to derive these relational variables based on the relational structure and a set of naive confounders. This automatic construction includes two unusual classes of variables: relational degree and entity identifiers. We provide experimental evidence that demonstrates the utility of these variables in accounting for certain latent confounders. Finally, through a set of synthetic experiments, we show that our method improves the performance of PSM for causal inference with relational data.
Propensity score matching (
Hometown
From Checks-In
Has Places
User
Friends
To illustrate this, consider the example domain shown in Figure 1, depicting a plausible relational domain. Foursquare is an example of a real system that could produce this sort of data. Suppose a researcher is interested in using data from this domain to assess whether smoking causes a user to gain weight. One approach would be to construct a propensity score model with user attributes that the researcher believes could be causes of whether a user smokes and the user’s weight, such as alcohol consumption and ethnicity: While this accounts for attributes associated with the user, it fails to account for possible confounders derived from relational variables. For example, it is plausible that the alcohol consumption of a user’s friends is a common cause of [User ].Weight and [User ].Smokes. To account for these effects, the corresponding relational variables should be included in the propensity score model.
It is not difficult to envision more complicated relational variables having an effect. In fact, as previous work has shown [Maier et al., 2013b], the number of relational variables can be arbitrarily large depending on how many entity and relationship types exist in the network, the size of the network, and the length of the longest path (the largest degree of separation) in the network where direct dependence exists.
An additional level of complexity introduced by relational data is that relational structures may result in multiple instances of a given variable. For example, a user with multiple friends could be influenced by the drinking behaviour of each of those friends. Typically, an aggregation function, such as mean, is used to combine this set of values into a single value. Properly conditioning on a relational variable entails choosing the correct set of aggregation functions to represent the distribution of values contained in the set. For example, in order to condition on a relational variable, it may be necessary to condition on multiple aspects of the distribution of those values, such as the mean and the standard deviation (stdev).
To address these issues, we introduce relational propensity score matching (RPSM), a method that applies propensity score matching to relational domains. RPSM leverages the framework of relational models [Getoor and Taskar, 2007, Maier et al., 2013b] to automatically construct the set of possible relational confounders given a simpler specification of the assumed dependency structure. RPSM also identifies opportunities to use relational degree variables and entity identifiers, which, as we show empirically, can reduce the bias arising from latent relational confounders. We evaluate RPSM via a set of synthetic experiments using the relational structure of a real-world relational domain, Foursquare. 2
In this section we provide a brief overview of matching methods and propensity scores. We then introduce the relational concepts necessary to formalize RPSM. 2.1
In the framework of potential outcomes [Rubin, 1974],
estimating the causal effect of treatment T on variable
Y is formalized as a comparison of potential outcomes.
More formally, let Ti be a binary treatment variable
for unit i and let Yi be the outcome variable for unit i,
where i ∈ {1, . . . , n}. Yi(Ti = 0) denotes the value of
Yi that would be observed if no treatment was applied
to unit i. Similarly, Yi(Ti = 1) is the value of Yi that
would be observed if unit i had received treatment.
The causal effect of T on Y is estimated by comparing
the difference Yi(Ti = 1)−Yi(Ti = 0) across all units i.
In practice, a specific unit either receives treatment or
not. Therefore, for a given value of i we never know
both Yi(T = 1) and Yi(T = 0). Experimental studies
often randomly assign units to treatment and control
groups, so that the expected distribution of the
covariates in these groups is identical. In observational
studies, where randomization is not possible, matching
can be used to pair similar samples from the treated
and the control groups. Matching can be generally
defined as a method that aims to approximate random
assignment by equating the distribution of covariates
in the treated and control group [Stuart, 2010].
Matching requires a measure quantifying how similar
two individuals are. This is achieved by (1) selecting
a set of features to be used in the computation of
similarity, and (2) choosing a similarity function to apply
on those features (for example Mahalanobis distance,
propensity score, etc.). Once a similarity measure has
been chosen, individuals are matched based on this
measure. There are multiple methods for performing
matching
The propensity score [Rosenbaum and Rubin, 1983] is the probability of receiving treatment, given the observed covariates Xi
ei(Xi) = P (Ti = 1|Xi).
Propensity scores are a form of dimensionality reduction that projects the original covariates down to a single value which preserves distance with respect to the likelihood of treatment. Matching can then be performed on the propensity score, as opposed to the covariates directly. The prevailing explanation for why propensity scores are appropriate for matching is that they are balancing scores (given the value of the propensity score, the treatment and control groups have the same distribution of covariates), and they preserve ignorability of treatment assignment (if treatment assignment is ignorable given the covariates, then treatment assignment is also ignorable given the propensity score) [Stuart, 2010].
Any method that models the conditional probability of a binary variable given a set of predictors can be used to estimate a propensity score. In this work, we employ logistic regression, a widely used method for obtaining a propensity score. However, other models (such as boosted trees, support vector machines, CHECKS-IN and neural networks) have been explored in the literature [Westreich et al., 2010, McCaffrey et al., 2004, Lee et al., 2010].
A key advantage of propensity scores is their
robustness to model misspe
Propositional representations, such as Bayesian networks, describe domains with a single entity type. However, many real-world systems involve multiple types of entities that interact with each other. Data produced by such systems are called relational or network data. In this section, we introduce the basic relational concepts, following the notation and terminology of Maier et al. [2013b].
A relational schema S = (E , R, A, card ) specifies the set of entity, relationship, and attribute classes of a 1Variables that are marginally independent of treatment or outcome.
Drinks
FRIENDS
CHECKS-IN
CHECKS-IN
Price Range
Corner Cafe
domain. It includes a cardinality function that
imposes constraints on the number of times an entity
instance can participate in a relationship. A
relational schema can be graphically represented with an
Entity-Relationship (ER) diagram. Figure 2 shows
the ER diagram for the Foursquare domain. In this
example, there are three entity classes (User , Place,
Hometown), and three relationship classes, (Friends,
ChecksIn, From). The entity class User has three
attributes: Smokes, Weight , and Drinks. The
cardinality constraints are depicted using crow’s feet notation.
For example, the cardinality of the From relationship
is one-to-many, indicating that one user has one
hometown, but many users can be from the same hometown.
A relational skeleton is a partial instantiation of a
relational schema that specifies the set of entity and
relationship instances that exist in the domain.
Figure 3 depicts an example relational skeleton for the
Foursquare domain. The network consists of two User
instances, Alice and Bob, who are friends with each
other and come from the same hometown. There are
two Place instances, Hillside Diner and Corner Cafe.
Given a relational schema, one can specify
relational paths, which intuitively correspond to
possible ways of traversing the schema
A relational model M = (S, D, Θ) is a collection of relational dependencies D defined over a relational schema along with their parameterizations Θ (a conditional probability distribution for each attribute given its parents). The structure of a relational model can be depicted by superimposing the dependencies on the ER diagram of the relational schema, as shown in Figure 2, and labeling each arrow with the dependency it corresponds to. If labels are omitted, the resulting graphical representation is known as a classdependency graph.
Re
In this section we present the new types of variables that are enabled by relational domains: (1) Relational variables (a way of defining a larger number of potential confounders) and aggregation; (2) Degree variables (a type of confounder not available without relational data); (3) Entity identifiers (which enable blocking, a way to account for latent confounders only available within relational data). Those types of variables are used in the calculation of relational propensity scores and are referred to as relational covariates. 2.4.1
A fundamental characteristic of relational data is the heterogeneity of the underlying relational structure. For example, a person can have many friends, different people have different sets of friends, and those sets can overlap to varying degrees. This implies that when constructing relational variables for a specific individual, the construction process will often return a set of values rather than a single value. For instance, the relational variable “friends’ age” for a person consists of a set of values containing the age of each one of that person’s friends. In the field of statistical relational learning, aggregation functions are commonly used to PERSON
TOWN
STATE
summarize the values of related instances into a single
value, representative of the distribution. Common
aggregation functions include mean, stdev, mode, count,
sum, min, max, and median. Researchers have also
defined more complex aggregation methods [Perli
Other work has pointed out that variation in the size of the set of values for a relational variable can strongly affect the distribution of the observed values of many aggregation functions [Jensen et al., 2003]. Jensen et al. call the size of this set the “degree” and it is equivalent, in the terminology of Maier et al. [2013b], to the size of the terminal set of a relational path. To account for the effects of degree on aggregated values, RPSM includes degree variables in the calculation of propensity scores. 2.4.3
Blocking designs are widely used in experimental
studies to account fo
In this work, we incorporate relational blocking with propensity scores by including entity identifiers as covariates in the calculation of propensity scores. We restrict the use of blocking to hierarchies, i.e., parts of the relational schema that are connected through a series of many-to-one relationships. An example hierarchy is shown in Figure 4. In this case, blocking on the identifier for towns (i.e., grouping users based on their hometown) accounts for the effect of latent variables associated with Hometown, and for the effect of latent variables associated with the State within which each town is located. More generally, blocking on the identifier of an entity in a hierarchy accounts for the effect of latent confounders that reside in that entity and in entities that appear higher up in the hierarchy. 3
We consider the following problem: given an entity E and two attributes on that entity, treatment [E].T and outcome [E].O, we seek to decide between [E].T ! [E].O and [E].T 6! [E].O. For notational convenience, we restrict our attention to cases where the treatment and outcome are on the same entity. In practice, RPSM can be applied to any treatment and outcome lying on entities that are connected through one-to-one relationships. We assume that the relational skeleton has been given a priori, i.e., all entity and relationship instances have been fully and correctly specified. Additionally, we assume that the effects of all latent variables can be accounted for by using relational blocking (in other words, latent variables exists only on paths that can be blocked on).
Relational propensity score matching (RPSM) provides an automatic method for constructing the set of aggregated relational variables, degree variables and entity identifiers (i.e., the relational covariates) to perform propensity score matching on relational data. The procedure for RPSM is described in Algorithm 1. RPSM takes as input a data-set X , a relational schema, the treatment and outcome attributes, a set of possible confounding attributes, a set of aggregation functions, and a hop-threshold h. The algorithm constructs the set of relational covariates based on the confounding attributes, the aggregation functions, and hop-threshold (line 2, discussed below in detail). The propensity score of the treatment given the covariates is then computed (line 3) and matching is performed based on the propensity score (line 4). The construction of relational covariates is presented in Algorithm 2. The algorithm first constructs all potential relational variables for the confounding attributes from the given perspective, up to the specified hop-threshold (line 1).2 This is the set of relational confounders. Then, for each relational confounder, it creates the appropriate relational covariates by applying the given aggregation functions (lines 7-8). A degree variable is then added for the paths of the relational confounders (line 9). Finally, the algorithm identifies parts of the schema that form a hierarchy and adds identifier variables for the schema item lowest in the hierarchy to perform blocking (lines 10-14). Relational covariates that were constructed from relational variables that are now determined by the blocking path Algorithm 1: RPSM (X , schema, treatment , outcome, confoundingAttrs, aggrFunctions, h) 1 perspective ← item class of treatment , outcome 2 covariates ← GetRelationalCovariates (schema, perspective, confoundingAttrs, aggrFunctions, h) 3 propensityScore ← Calculate propensity score for treatment ∼ covariates using X 4 matches ← Match (propensityScore, treatment , X ) 5 return matches Algorithm 2: GetRelationalCovariates (schema, perspective, confoundingAttrs, aggrFunctions, h) 1 relationalConfounders ← relational variables with attributes in confoundingAttrs from perspective perspective up to hop-threshold h 2 relCovariates ← ∅ 3 for P.X in relationalConfounders do 4 if P == [perspective] then 5 relCovariates ← relCovariates ∪ P .X 6 else 7 for agg in aggrFunctions do 8 relCovariates ← relCovariates ∪agg(P .X ) 9 relCovariates ← relCovariates ∪ degree(P ) 10 for P.X in relationalConfounders do 11 if P is valid blocking choice for perspective then 12 controlled ← relational variables that P controls for 13 relCovariates ← relCovariates \ controlled 14 relCovariates ← relCovariates ∪ P .id 15 return relCovariates are removed from the list of covariates (line 13). Example 3.1. Consider our earlier scenario of assessing the effect of smoking on a user’s weight. The treatment is User .Smokes and the outcome is User .Weight (the perspective of the analysis is the User entity class). If Drinks is given as a possible confounding attribute and the hop-threshold is 4, the algorithm will add the following relational variables to the set of relational confounders: [User ].Drinks [User , Friends, User ].Drinks [User , Friends, User , Friends, User ].Drinks [User , ChecksIn, Place, ChecksIn, User ].Drinks [User , From, Hometown, From, User ].Drinks The next step is to create relational covariates based on the above relational variables. First, relational variables that only involve the User entity, in this case [User ].Drinks, are added to the set of relational co2The algorithm can be trivially extended to exclude certain relational paths. For example, if the user has domain knowledge that would exclude specific relational paths or relational variables from the list of potential confounders. variates. Because these covariates are propositional, aggregation functions are not applied.
The aggregation functions are then applied to relational variables that cross the boundaries of the User entity. If the set of aggregation functions is {mean}, the algorithm will add the following to the set of relational covariates: mean [User , Friends, User ].Drinks , mean [User , Friends, User , Friends, User ].Drinks , mean [User , ChecksIn, Place, ChecksIn, User ].Drinks , mean [User , From, Hometown, From, User ].Drinks The set of relational covariates is augmented by including the degree of the relational paths that involve more than one entity classes: degree [User , Friends, User ] , degree [User , Friends, User , Friends, User ] , degree [User , ChecksIn, Place, ChecksIn, User ] , degree [User , From, Hometown, From, User ] Finally, id variables are added to the relational paths. In this case, there exists a hierarchy expressed by the relational path [User , From, Hometown]. Therefore, the algorithm adds the following relational covariate: [User , From, Hometown].id In practice, the hop-threshold should be chosen on a case by case basis, using expert knowledge of the application domain. The choice of aggregation functions can be guided by an analysis of each variable’s marginal distribution from the perspective of the treatment and outcome. 4
To evaluate the performance of RPSM we examine the following hypotheses: 1. Propensity score matching models that are limited to simplistic relational attributes (h = 2) fail to fully account for confounding network effects (h = 4) (Section 4.1). 2. Traditional aggregates for relational data, such as mean, when used in isolation do not sufficiently condition on the distribution of confounding relational variables (Section 4.2). 3. The inclusion of identifiers for entities that lie along valid blocking paths accounts for latent confounders on those entities as well on entities connected to them. That is, including entity identifiers in the propensity model performs an implicit causal blocking design (Section 4.3).
For all experiments we used the structure derived from
a sample of a real-world network, Four
For our experiments we generated data from multiple models to test each hypothesis individually. In all experiments, the treatment is [User ].Smokes and the outcome [User ].Weight . Each model was parameterized as follows: The value of the treatment was drawn from a logistic model parametrized using coefficients drawn from U (−2, 2) and interaction terms increasing in degree from 1 (no interaction) to 10 (up to 10 interacting covariates, not necessarily distinct, per term). We refer to this varying degree as “covariate complexity”. The value of outcome was drawn from a linear model with coefficients drawn from U (−2, 2) and an error distribution drawn from N (0, 1). Marginal distributions for each variable were drawn from N (μ, σ), with μ and σ sampled for each variable individually from U (0, 5) and U (1, 3), respectively.
We used logistic regression to calculate the
propensity score and then performed full matching using the
optmatch packa
SIMPLE NETWORK DEPENDENCIES We examine the first hypothesis, whether propensity score models limited to simplistic relational attributes fail to fully account for confounding network effects, by generating data from two models. Both models have the same class-dependency graph, shown in Figure 5, but differ in the length of the longest true dependency. In the first model (World2), the true relational confounders are at most two hops away from the treatment and outcome entity. This corresponds to dependencies that can be read directly from the class dependency graph, e.g., the places a user checks in to. The set of true relational confounders for the model is: [User ].Drinks [User , From, Hometown].SchoolQuality
[User , ChecksIn, Place].PriceRange In the second model (World4), the set of true confounders is extended to include relational variables up to four hops away, e.g., other users that check in to the same places as a user. The set of confounders includes all of the confounders of the first model as well as: [User , Friends, User ].Drinks [User , ChecksIn, Place, ChecksIn, User ].Drinks [User , From, Hometown, From, User ].Drinks [User , Friends, User , Friends, User ].Drinks [User , Friends, User , ChecksIn, Place].PriceRange [User , Friends, User , From, Hometown].SchoolQuality Using the above procedure we ran 100 trials. For each trial we considered two cases, one in which treatment and outcome are conditionally independent and one in which there is a direct effect between them. We then compared two methods for creating the relational covariates for propensity score matching: 1. RPSM using mean, stdev, max, min as aggregation functions and h = 2 without blocking or degree variables (RPSM2)
Model Used in RPSM
RPSM2: all aggregations, h=2 RPSM4: all aggregations, h=4 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Covariate Complexity
2. RPSM using mean, stdev, max, min as aggregation functions and h = 4 without blocking or degree variables (RPSM4) The results are shown in Figure 6. Along the diagonal the RPSM model is consistent with the world configuration. When models are over-specified, for instance RPSM4 in the World2 configuration, RPSM4 achieves comparable performance to RPSM2. However, when models are underspecified, for instance RPSM2 in the World 4 configuration, a spurious effect is inferred between treatment and outcome in the conditionally independent case. These results also demonstrate a case in which RPSM can successfully tolerate large numbers of irrelevant covariates. 4.2
In this section, we examine the second hypothesis regarding the effect of using complex aggregation function in the construction of relational covariates. We generated data from models with the same classdependency graph as in Section 4.1. We used World2 and World4, as before, and two simplified models which consider only mean as an aggregate, with hopthresholds of 2 (World2-) and 4 (World4-). We then used the RPSM2 and RPSM4 methods for constructing relational covariates and two simpler propensity score models that only include mean as an aggregate Model Used in RPSM RPSM2−: mean only, h=2 1.00 0.75 0.50 0.25 0.00 1.00 0.75 0.50 tge0.25 a n ce0.00 re1.00 P r rro0.75 E 0.50 0.25 0.00 1.00 0.75 0.50 0.25 0.00 The results are shown in Figure 7. Along the main diagonal, the assumptions of the RPSM model are consistent with the true world configuration. In cases where the employed model uses mean as the sole aggregation function but distributional dependencies are more complex, RPSM commits a large number of Type I errors. However, the over-specified models (e.g., RPSM4 in World2) maintain accuracy levels that are consistent with the most efficient RPSM configuration. 4.3
The final experiment examines the third hypothesis regarding the effect of including entity identifiers in the relational propensity score model. We generated data from a model similar to that of Figure 5, with an additional latent confounder on the Hometown entity. We then created relational covariates using four strategies: 1. Use all observed variables and hop-threshold of 2 (RPSM2) and 4 (RPSM4). 2. Use degree variables and entity-identifiers for all eligible blocking paths with either h = 2 or h = 4 (RPSM2+ and RPSM4+ respectively).
The results are shown in Figure 8. RPSM2 and
RPSM4 perform poorly, because of the bias induced
by unconditioned confounders. RPSM2+ performs
well when true relational dependencies are limited to
h = 2. RPSM4+ performs well in all cases. This
is an indication that including the entity identifiers
in the propensity model performs blocking, producing
effects similar to the explicit conditioning perfor
Multi-level propensity score models [Hong and
Rauden
In the area of relational causal dis
3SUTVA states that the outcome of an individual is independent of the treatment status of other individuals. 6
We plan on examining RPSM further, using more
complex synthetic data and real-world data. An
interesting avenue for future research is extending RPSM to
the case where the treatment or outcome lies along a
one-to-many relational path (e.g., the effect of a
treatment performed on an individual on an aggregate
attribute of the individual’s friends). There are also a
number of methods for performing matching without a
propensity score, such as matching on the full set of
covariates [Stuart, 2010], coarsened exact matc
Propensity score matching provides a powerful and robust method for causal inference on propositional data. However, naively applying PSM to relational data ignores both new challenges and opportunities presented by this richer type of data. RPSM automatically constructs the set of relational covariates to be used in the propensity score model given a set of confounding attributes, a set of aggregation functions, and a hop threshold. Further, it exploits the relational structure by identifying degree variables and entity identifiers, which can account for latent relational confounders. We evaluate its efficacy via synthetic experiments that leverage a real-world relational skeleton.