Publications

2024

1. Bounding causal effects with leaky instruments David S. Watson, Jordan Penn, Lee M. Gunderson, Gecia Bravo-Hermsdorff, Afsaneh Mastouri, and Ricardo Silva In Fortieth Conference on Uncertainty in Artificial Intelligence (UAI), 2024 [Abstract] [URL] [Code]

   Instrumental variables (IVs) are a popular and powerful tool for estimating causal effects in the presence of unobserved confounding. However, classical approaches rely on strong assumptions such as the exclusion criterion, which states that instrumental effects must be entirely mediated by treatments. This assumption often fails in practice. When IV methods are improperly applied to data that do not meet the exclusion criterion, estimated causal effects may be badly biased. In this work, we propose a novel solution that provides partial identification in linear models given a set of leaky instruments, which are allowed to violate the exclusion criterion to some limited degree. We derive a convex optimization objective that provides provably sharp bounds on the average treatment effect under some common forms of information leakage, and implement inference procedures to quantify the uncertainty of resulting estimates. We demonstrate our method in a set of experiments with simulated data, where it performs favorably against the state of the art.

2023

1. Intervention Generalization: A View from Factor Graph Models Gecia Bravo-Hermsdorff, David S. Watson, Jialin Yu, Jakob Zeitler, and Ricardo Silva In Neural Information Processing Systems 37 (NeurIPS), 2023 [Abstract] [URL] [PDF] [Poster] [Code] [Video]

   One of the goals of causal inference is to generalize from past experiments and observational data to novel conditions. While it is in principle possible to eventually learn a mapping from a novel experimental condition to an outcome of interest, provided a sufficient variety of experiments is available in the training data, coping with a large combinatorial space of possible interventions is hard. Under a typical sparse experimental design, this mapping is ill-posed without relying on heavy regularization or prior distributions. Such assumptions may or may not be reliable, and can be hard to defend or test. In this paper, we take a close look at how to warrant a leap from past experiments to novel conditions based on minimal assumptions about the factorization of the distribution of the manipulated system, communicated in the well-understood language of factor graph models. A postulated interventional factor model (IFM) may not always be informative, but it conveniently abstracts away a need for explicitly modeling unmeasured confounding and feedback mechanisms, leading to directly testable claims. Given an IFM and datasets from a collection of experimental regimes, we derive conditions for identifiability of the expected outcomes of new regimes never observed in these training data. We implement our framework using several efficient algorithms, and apply them on a range of semi-synthetic experiments.

2. The Graph Pencil Method: Mapping Subgraph Densities to Stochastic Block Models Lee M. Gunderson, Gecia Bravo-Hermsdorff, Peter Orbanz In Neural Information Processing Systems 37 (NeurIPS), 2023 [Abstract] [URL] [PDF] [Poster]

   In this work, we describe a method that determines an exact map from a finite set of subgraph densities to the parameters of a stochastic block model (SBM) matching these densities. Given a number K of blocks, the subgraph densities of a finite number of stars and bistars uniquely determines a single element of the class of all degree-separated stochastic block models with K blocks. Our method makes it possible to translate estimates of these subgraph densities into model parameters, and hence to use subgraph densities directly for inference. The computational overhead is negligible; computing the translation map is polynomial in K, but independent of the graph size once the subgraph densities are given.

3. Quantifying Human Priors over Social and Navigation Networks Gecia Bravo-Hermsdorff In Fortieth International Conference on Machine Learning (ICML), 2023 [Abstract] [URL] [PDF] [Poster] [Demo of experimental platform]

   Human knowledge is largely implicit and relational — do we have a friend in common? can I walk from here to there? In this work, we leverage the combinatorial structure of graphs to quantify human priors over such relational data. Our experiments focus on two domains that have been continuously relevant over evolutionary timescales: social interaction and spatial navigation. We find that some features of the inferred priors are remarkably consistent, such as the tendency for sparsity as a function of graph size. Other features are domain-specific, such as the propensity for triadic closure in social interactions. More broadly, our work demonstrates how nonclassical statistical analysis of indirect behavioral experiments can be used to efficiently model latent biases in the data.

4. Quantifying Network Similarity using Graph Cumulants Gecia Bravo-Hermsdorff*, Lee M. Gunderson*, Pierre-André Maugis, and Carey E. Priebe Journal of Machine Learning Research, 24(187):1−27, 2023 [Abstract] [URL] [PDF]

   How might one test the hypothesis that networks were sampled from the same distribution? Here, we compare two statistical tests that use subgraph counts to address this question. The first uses the empirical subgraph densities themselves as estimates of those of the underlying distribution. The second test uses a new approach that converts these subgraph densities into estimates of the graph cumulants of the distribution (without any increase in computational complexity). We demonstrate — via theory, simulation, and application to real data — the superior statistical power of using graph cumulants. I n summary, when analyzing data using subgraph/motif densities, we suggest using the corresponding graph cumulants instead.

2022

1. Private and Communication-Efficient Algorithms for Entropy Estimation Gecia Bravo-Hermsdorff, Robert Busa-Fekete, Mohammad Ghavamzadeh, Andrés Munõs Medina, and Umar Syed In Neural Information Processing Systems 36 (NeurIPS), 2022 [Abstract] [URL] [PDF] [Summary video (2m35s)]

   Modern statistical estimation is often performed in a distributed setting where each sample belongs to a single user who shares their data with a central server. Users are typically concerned with preserving the privacy of their samples, and also with minimizing the amount of data they must transmit to the server. We give improved private and communication-efficient algorithms for estimating several popular measures of the entropy of a distribution. All of our algorithms have constant communication cost and satisfy local differential privacy. For a joint distribution over many variables whose conditional independence given by a tree, we describe algorithms for estimating Shannon entropy that require a number of samples that is linear in the number of variables, compared to the quadratic sample complexity of prior work. We also describe an algorithm for estimating Gini entropy whose sample complexity has no dependence on the support size of the distribution and can be implemented using a single round of concurrent communication between the users and the server. In contrast, the previously best-known algorithm has high communication cost and requires the server to facilitate interaction between the users. Finally, we describe an algorithm for estimating collision entropy that matches the space and sample complexity of the best known algorithm but generalizes it to the private and communication-efficient setting.

2. Statistical Anonymity: Quantifying Reidentification Risks Without Reidentifying Users Gecia Bravo-Hermsdorff, Robert Busa-Fekete, Lee M. Gunderson, Andrés Munõs Medina, and Umar Syed arXiv preprint, 2022 [Abstract] [URL] [PDF]

   Data anonymization is an approach to privacy-preserving data release aimed at preventing participants reidentification, and it is an important alternative to differential privacy in applications that cannot tolerate noisy data. Existing algorithms for enforcing k-anonymity in the released data assume that the curator performing the anonymization has complete access to the original data. Reasons for limiting this access range from undesirability to complete infeasibility. This paper explores ideas -- objectives, metrics, protocols, and extensions -- for reducing the trust that must be placed in the curator, while still maintaining a statistical notion of k-anonymity. We suggest trust (amount of information provided to the curator) and privacy (anonymity of the participants) as the primary objectives of such a framework. We describe a class of protocols aimed at achieving these goals, proposing new metrics of privacy in the process, and proving related bounds. We conclude by discussing a natural extension of this work that completely removes the need for a central curator.

2021

1. A Principled (and Practical) Test for Network Comparison Gecia Bravo-Hermsdorff*, Lee M. Gunderson*, Pierre-André Maugis, and Carey E. Priebe arXiv preprint, 2021 [Abstract] [URL] [PDF]

   How might one test the hypothesis that graphs were sampled from the same distribution? Here, we compare two statistical tests that address this question. The first uses the observed subgraph densities themselves as estimates of those of the underlying distribution. The second test uses a new approach that converts these subgraph densities into estimates of the graph cumulants of the distribution. We demonstrate -- via theory, simulation, and application to real data -- the superior statistical power of using graph cumulants.

2. Permutation-Equivariant Neural Networks for Power Spectrum Estimation Gecia Bravo-Hermsdorff Informal write-up, 2021 [Quick summary] [PDF]

   A fun and short introduction (in a form of a dialogue!) to permutation equivariant neural networks,ie, neural networks that don’t care about the order of things. This was my mini-project for the AI residency onboarding program to get familiar with Google’s infrastructure.

2020

1. Introducing Graph Cumulants: What is the Variance of your Social Network? Lee M. Gunderson* and Gecia Bravo-Hermsdorff* arXiv preprint, 2020 [Quick summary] [Abstract] [URL] [PDF] [Summary video (9m21s)] [Code]

   Over a century ago, Thiele (1889) introduced cumulants, a concept now fundamental to the field of statistics, which has justifiably percolated throughout the scientific community. In this work, we introduce graph cumulants, their generalization to networks. This principled hierarchy of network statistics provides a framework to systematically describe and compare networks, naturally including those with additional features, such as directed edges, node attributes, and edge weights. Moreover, through the lens of the maximum entropy principle, these statistics induce a natural hierarchical family of network models. These models are immune to the "degeneracy problem", providing a principled prescription for obtaining distributions that are clustered around the properties of the network they intend to model.

   In an increasingly interconnected world, understanding and summarizing the structure of these networks becomes increasingly relevant. However, this task is nontrivial; proposed summary statistics are as diverse as the networks they describe, and a standardized hierarchy has not yet been established. In contrast, vector-valued random variables admit such a description in terms of their cumulants (e.g., mean, (co)variance, skew, kurtosis). Here, we introduce the natural analogue of cumulants for networks, building a hierarchical description based on correlations between an increasing number of connections, seamlessly incorporating additional information, such as directed edges, node attributes, and edge weights. These graph cumulants provide a principled and unifying framework for quantifying the propensity of a network to display any substructure of interest (such as cliques to measure clustering). Moreover, they give rise to a natural hierarchical family of maximum entropy models for networks (i.e., ERGMs) that do not suffer from the “degeneracy problem”, a common practical pitfall of other ERGMs.

2. Quantifying Human Priors over Abstract Relational Structures Gecia Bravo-Hermsdorff Ph.D. Dissertation, Princeton University, 2020 [Abstract] [URL] [PDF] [Slides] [Demos of Mturk experiments]

   Some new tasks are trivial to learn, while others are essentially impossible; what determines how easy it is to learn the structure of a given task? Similar to how our priors about visual scenes demonstrably color our perception of the world, our priors about the structure of tasks shape our learning, decision-making, and generalization abilities. Drawing inspiration from the insights afforded to neuroscience by the characterization of visual priors, in this dissertation, we strive to quantify priors over abstract structures. In particular, we focus on graphs: the structure of interactions.
   
   In Chapter 3, we describe the natural analogue of cumulants (e.g., mean, (co)variance, skew, kurtosis) for graphs, building a hierarchical description based on local correlations between an increasing number of connections. This provides a principled framework for quantifying the propensity of a network to display arbitrary substructures, and allows one to meaningfully compare networks of different sizes and edge densities.
   
   In Chapter 4, we analyze graph structure globally, via the dynamics of diffusion, providing an algorithm that reduces a graph while preserving its large-scale structure. Our framework analytically unifies two areas of research, namely graph sparsification (removing edges) and graph coarsening (merging nodes), and is competitive with current state-of-the-art algorithms.
   
   From a neuroscience perspective, we develop a novel method for quantifying human priors over graphs (Chapters 2 and 3). In Chapter 5, we apply this method to graphical representations of social and navigation tasks: two domains that have been relevant (over evolutionary timescales) to our everyday life. We find that the resulting priors exhibit non-trivial graphical structure. While some features appear to be general, such as the preferred amount of sparsity as a function of graph size, other features appear to be domain-specific, such as the preference for triadic closure in social interactions.
   
   Through the development of principled methods for analyzing network structure and the use of an analytically tractable model of human learning on graphs, this work provides useful tools that could cross-pollinate with other active areas of research, such as artificial intelligence.

2019

1. A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening Gecia Bravo-Hermsdorff* and Lee M. Gunderson* In Neural Information Processing Systems 33 (NeurIPS), 2019 [Quick summary] [Abstract] [URL] [PDF] [Poster] [Code] [Summary video (4m14s)] [Reduction playlist]

   The deletion of edges (sparsification) and the merging of adjacent vertices (coarsening) are two common methods for reducing a graph. We analytically unify these two operations using a single objective function based on the graph Laplacian pseudoinverse, providing a principled algorithm that simultaneously sparsifies and coarsens a graph while preserving its large-scale structure.

   How might one “reduce” a graph? That is, generate a smaller graph that preserves the global structure at the expense of discarding local details? There has been extensive work on both graph sparsification (removing edges) and graph coarsening (merging nodes, often by edge contraction); however, these operations are currently treated separately. Interestingly, for a planar graph, edge deletion corresponds to edge contraction in its planar dual (and more generally, for a graphical matroid and its dual). Moreover, with respect to the dynamics induced by the graph Laplacian (e.g., diffusion), deletion and contraction are physical manifestations of two reciprocal limits: edge weights of zero and infinity, respectively. In this work, we provide a unifying framework that captures both of these operations, allowing one to simultaneously sparsify and coarsen a graph while preserving its large-scale structure. The limit of infinite edge weight is rarely considered, as many classical notions of graph similarity diverge. However, its algebraic, geometric, and physical interpretations are reflected in the Laplacian pseudoinverse, which remains finite in this limit. Motivated by this insight, we provide a probabilistic algorithm that reduces graphs while preserving the Laplacian pseudoinverse, using an unbiased procedure that minimizes its variance. We compare our algorithm with several existing sparsification and coarsening algorithms using real-world datasets, and demonstrate that it more accurately preserves the large-scale structure.

2. Gender and Collaboration Patterns in a Temporal Scientific Authorship Network Gecia Bravo-Hermsdorff, Valkyrie Felso, Emily Ray, Lee M. Gunderson, Mary E. Helander, Joana Maria, and Yael Niv Applied Network Science, 4(1), 2019 [Quick summary] [Abstract] [URL] [PDF] [Dataset]

   We constructed a gender-labeled temporal bipartite graph of academic collaborations in the Institute for Operations Research and the Management Sciences (INFORMS) spanning over six decades. Employing two metrics based on the graph Laplacian which are sensitive to global connectivity, we analyze the relevance of gender in these collaboration patterns.

   One can point to a variety of historical milestones for gender equality in STEM (science, technology, engineering, and mathematics), however, practical effects are incremental and ongoing. It is important to quantify gender differences in subdomains of scientific work in order to detect potential biases and monitor progress. In this work, we study the relevance of gender in scientific collaboration patterns in the Institute for Operations Research and the Management Sciences (INFORMS), a professional society with sixteen peer-reviewed journals. Using their publication data from 1952 to 2016, we constructed a large temporal bipartite network between authors and publications, and augmented the author nodes with gender labels. We characterized differences in several basic statistics of this network over time, highlighting how they have changed with respect to relevant historical events. We find a steady increase in participation by women (e.g., fraction of authorships by women and of new women authors) starting around 1980. However, women still comprise less than 25% of the INFORMS society and an even smaller fraction of authors with many publications. Moreover, we describe a methodology for quantifying the structural role of an authorship with respect to the overall connectivity of the network, using it to measure subtle differences between authorships by women and by men. Specifically, as measures of structural importance of an authorship, we use effective resistance and contraction importance, two measures related to diffusion throughout a network. As a null model, we propose a degreepreserving temporal and geometric network model with emergent communities. Our results suggest the presence of systematic differences between the collaboration patterns of men and women that cannot be explained by only local statistics.

3. Modeling the Hemodynamic Response Function for Prediction Errors in the Ventral Striatum Gecia Bravo-Hermsdorff and Yael Niv bioRxiv, Cold Spring Harbor Laboratory, 2019 [URL]

2018

1. Quantifying Humans’ Priors Over Graphical Representations of Tasks Gecia Bravo-Hermsdorff, Talmo Pereira, and Yael Niv In Unifying Themes in Complex Systems IX. ICCS, 2018 [URL]