More Like this

1. Sparse High Dimensional Expanders via Local Lifts

   https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.68  

   Ben_Yaacov, Inbar; Dikstein, Yotam; Maor, Gal (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Kumar, Amit; Ron-Zewi, Noga (Ed.)

   High dimensional expanders (HDXs) are a hypergraph generalization of expander graphs. They are extensively studied in the math and TCS communities due to their many applications. Like expander graphs, HDXs are especially interesting for applications when they are bounded degree, namely, if the number of edges adjacent to every vertex is bounded. However, only a handful of constructions are known to have this property, all of which rely on algebraic techniques. In particular, no random or combinatorial construction of bounded degree high dimensional expanders is known. As a result, our understanding of these objects is limited. The degree of an i-face in an HDX is the number of (i+1)-faces that contain it. In this work we construct complexes whose higher dimensional faces have bounded degree. This is done by giving an elementary and deterministic algorithm that takes as input a regular k-dimensional HDX X and outputs another regular k-dimensional HDX X̂ with twice as many vertices. While the degree of vertices in X̂ grows, the degree of the (k-1)-faces in X̂ stays the same. As a result, we obtain a new "algebra-free" construction of HDXs whose (k-1)-face degree is bounded. Our construction algorithm is based on a simple and natural generalization of the expander graph construction by Bilu and Linial [Yehonatan Bilu and Nathan Linial, 2006], which build expander graphs using lifts coming from edge signings. Our construction is based on local lifts of high dimensional expanders, where a local lift is a new complex whose top-level links are lifts of the links of the original complex. We demonstrate that a local lift of an HDX is also an HDX in many cases. In addition, combining local lifts with existing bounded degree constructions creates new families of bounded degree HDXs with significantly different links than before. For every large enough D, we use this technique to construct families of bounded degree HDXs with links that have diameter ≥ D. 

   more » « less
2. A Sparse Delaunay Filtration

   Sheehy, Donald R. (July 2021, Leibniz international proceedings in informatics)

   Buchin, Kevin and (Ed.)

   We show how a filtration of Delaunay complexes can be used to approximate the persistence diagram of the distance to a point set in ℝ^d. Whereas the full Delaunay complex can be used to compute this persistence diagram exactly, it may have size O(n^⌈d/2⌉). In contrast, our construction uses only O(n) simplices. The central idea is to connect Delaunay complexes on progressively denser subsamples by considering the flips in an incremental construction as simplices in d+1 dimensions. This approach leads to a very simple and straightforward proof of correctness in geometric terms, because the final filtration is dual to a (d+1)-dimensional Voronoi construction similar to the standard Delaunay filtration. We also, show how this complex can be efficiently constructed. 

   more » « less
3. Co-Generation with GANs using AIS based HMC

   Tiantian Fang, Alexander Schwing (January 2019, Advances in Neural Information Processing Systems)

   Inferring the most likely configuration for a subset of variables of a joint distribution given the remaining ones – which we refer to as co-generation – is an important challenge that is computationally demanding for all but the simplest settings. This task has received a considerable amount of attention, particularly for classical ways of modeling distributions like structured prediction. In contrast, almost nothing is known about this task when considering recently proposed techniques for modeling high-dimensional distributions, particularly generative adversarial nets (GANs). Therefore, in this paper, we study the occurring challenges for co-generation with GANs. To address those challenges we develop an annealed importance sampling based Hamiltonian Monte Carlo co-generation algorithm. The presented approach significantly outperforms classical gradient based methods on a synthetic and on the CelebA and LSUN datasets. The code is available at https://github.com/AilsaF/cogen_by_ais 

   more » « less
4. Proximal Causal Inference with Text Data

   Chen, Jacob M; Bhattacharya, Rohit; Keith, Katherine A (December 2024, Advances in neural information processing systems)

   Recent text-based causal methods attempt to mitigate confounding bias by estimating proxies of confounding variables that are partially or imperfectly measured from unstructured text data. These approaches, however, assume analysts have supervised labels of the confounders given text for a subset of instances, a constraint that is sometimes infeasible due to data privacy or annotation costs. In this work, we address settings in which an important confounding variable is completely unobserved. We propose a new causal inference method that uses two instances of pre-treatment text data, infers two proxies using two zero-shot models on the separate instances, and applies these proxies in the proximal g-formula. We prove, under certain assumptions about the instances of text and accuracy of the zero-shot predictions, that our method of inferring text-based proxies satisfies identification conditions of the proximal g-formula while other seemingly reasonable proposals do not. To address untestable assumptions associated with our method and the proximal g-formula, we further propose an odds ratio falsification heuristic that flags when to proceed with downstream effect estimation using the inferred proxies. We evaluate our method in synthetic and semi-synthetic settings---the latter with real-world clinical notes from MIMIC-III and open large language models for zero-shot prediction---and find that our method produces estimates with low bias. We believe that this text-based design of proxies allows for the use of proximal causal inference in a wider range of scenarios, particularly those for which obtaining suitable proxies from structured data is difficult. 

   more » « less
5. Open-Domain Hierarchical Event Schema Induction by Incremental Prompting and Verification

   https://doi.org/10.18653/v1/2023.acl-long.312  

   Li, Sha; Zhao, Ruining; Li, Manling; Ji, Heng; Callison-Burch, Chris; Han, Jiawei (January 2023, Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics)

   Event schemas are a form of world knowledge about the typical progression of events. Recent methods for event schema induction use information extraction systems to construct a large number of event graph instances from documents, and then learn to generalize the schema from such instances. In contrast, we propose to treat event schemas as a form of commonsense knowledge that can be derived from large language models (LLMs). This new paradigm greatly simplifies the schema induction process and allows us to handle both hierarchical relations and temporal relations between events in a straightforward way. Since event schemas have complex graph structures, we design an incremental prompting and verification method INCPROMPT to break down the construction of a complex event graph into three stages: event skeleton construction, event expansion, and event-event relation verification. Compared to directly using LLMs to generate a linearized graph, INCPROMPT can generate large and complex schemas with 7.2% F1 improvement in temporal relations and 31.0% F1 improvement in hierarchical relations. In addition, compared to the previous state-of-the-art closed-domain schema induction model, human assessors were able to cover ∼10% more events when translating the schemas into coherent stories and rated our schemas 1.3 points higher (on a 5-point scale) in terms of readability. 

   more » « less