Randomized graph cluster randomization
The global average treatment effect (GATE) is a primary quantity of interest in the study of causal inference under network interference. With a correctly specified exposure model of the interference, the Horvitz–Thompson (HT) and Hájek estimators of the GATE are unbiased and consistent, respectivel...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2023-05-01
|
| Series: | Journal of Causal Inference |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jci-2022-0014 |
| _version_ | 1797814144498401280 |
|---|---|
| author | Ugander Johan Yin Hao |
| author_facet | Ugander Johan Yin Hao |
| author_sort | Ugander Johan |
| collection | DOAJ |
| description | The global average treatment effect (GATE) is a primary quantity of interest in the study of causal inference under network interference. With a correctly specified exposure model of the interference, the Horvitz–Thompson (HT) and Hájek estimators of the GATE are unbiased and consistent, respectively, yet known to exhibit extreme variance under many designs and in many settings of interest. With a fixed clustering of the interference graph, graph cluster randomization (GCR) designs have been shown to greatly reduce variance compared to node-level random assignment, but even so the variance is still often prohibitively large. In this work, we propose a randomized version of the GCR design, descriptively named randomized graph cluster randomization (RGCR), which uses a random clustering rather than a single fixed clustering. By considering an ensemble of many different clustering assignments, this design avoids a key problem with GCR where the network exposure probability of a given node can be exponentially small in a single clustering. We propose two inherently randomized graph decomposition algorithms for use with RGCR designs, randomized 3-net and 1-hop-max, adapted from the prior work on multiway graph cut problems and the probabilistic approximation of (graph) metrics. We also propose weighted extensions of these two algorithms with slight additional advantages. All these algorithms result in network exposure probabilities that can be estimated efficiently. We derive structure-dependent upper bounds on the variance of the HT estimator of the GATE, depending on the metric structure of the graph driving the interference. Where the best-known such upper bound for the HT estimator under a GCR design is exponential in the parameters of the metric structure, we give a comparable upper bound under RGCR that is instead polynomial in the same parameters. We provide extensive simulations comparing RGCR and GCR designs, observing substantial improvements in GATE estimation in a variety of settings. |
| first_indexed | 2024-03-13T08:03:13Z |
| format | Article |
| id | doaj.art-6ba80024e7844b95965e18515e889d0b |
| institution | Directory Open Access Journal |
| issn | 2193-3685 |
| language | English |
| last_indexed | 2024-03-13T08:03:13Z |
| publishDate | 2023-05-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Causal Inference |
| spelling | doaj.art-6ba80024e7844b95965e18515e889d0b2023-06-01T09:43:03ZengDe GruyterJournal of Causal Inference2193-36852023-05-011118324210.1515/jci-2022-0014Randomized graph cluster randomizationUgander Johan0Yin Hao1Management Science and Engineering, Stanford University, Stanford, CA 94305, California, United StatesInstitute for Computational and Mathematical Engineering, Stanford University, Stanford, CA 94305, California, United StatesThe global average treatment effect (GATE) is a primary quantity of interest in the study of causal inference under network interference. With a correctly specified exposure model of the interference, the Horvitz–Thompson (HT) and Hájek estimators of the GATE are unbiased and consistent, respectively, yet known to exhibit extreme variance under many designs and in many settings of interest. With a fixed clustering of the interference graph, graph cluster randomization (GCR) designs have been shown to greatly reduce variance compared to node-level random assignment, but even so the variance is still often prohibitively large. In this work, we propose a randomized version of the GCR design, descriptively named randomized graph cluster randomization (RGCR), which uses a random clustering rather than a single fixed clustering. By considering an ensemble of many different clustering assignments, this design avoids a key problem with GCR where the network exposure probability of a given node can be exponentially small in a single clustering. We propose two inherently randomized graph decomposition algorithms for use with RGCR designs, randomized 3-net and 1-hop-max, adapted from the prior work on multiway graph cut problems and the probabilistic approximation of (graph) metrics. We also propose weighted extensions of these two algorithms with slight additional advantages. All these algorithms result in network exposure probabilities that can be estimated efficiently. We derive structure-dependent upper bounds on the variance of the HT estimator of the GATE, depending on the metric structure of the graph driving the interference. Where the best-known such upper bound for the HT estimator under a GCR design is exponential in the parameters of the metric structure, we give a comparable upper bound under RGCR that is instead polynomial in the same parameters. We provide extensive simulations comparing RGCR and GCR designs, observing substantial improvements in GATE estimation in a variety of settings.https://doi.org/10.1515/jci-2022-0014causal inference under interferenceglobal average treatment effectnetwork effectsspilloverssocial networks62d05 |
| spellingShingle | Ugander Johan Yin Hao Randomized graph cluster randomization Journal of Causal Inference causal inference under interference global average treatment effect network effects spillovers social networks 62d05 |
| title | Randomized graph cluster randomization |
| title_full | Randomized graph cluster randomization |
| title_fullStr | Randomized graph cluster randomization |
| title_full_unstemmed | Randomized graph cluster randomization |
| title_short | Randomized graph cluster randomization |
| title_sort | randomized graph cluster randomization |
| topic | causal inference under interference global average treatment effect network effects spillovers social networks 62d05 |
| url | https://doi.org/10.1515/jci-2022-0014 |
| work_keys_str_mv | AT uganderjohan randomizedgraphclusterrandomization AT yinhao randomizedgraphclusterrandomization |