Basically a summary of papers over the last couple of years I’ve found interesting enough to download and in some cases even read.
See arxiv download script for details on the downloads directory to output HTML pipeline.
| file_size | downloaded | last_accessed | entry_id | title | summary | authors | |
|---|---|---|---|---|---|---|---|
| 1906.07221 | 666566 | 2020-10-28 08:38:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1906.07221v1 | Why and How zk-SNARK Works | Despite the existence of multiple great resources on zk-SNARK construction, from original papers to explainers, due to the sheer number of moving parts the subject remains a black box for many. While some pieces of the puzzle are given one can not see the full picture without the missing ones. Hence the focus of this work is to shed light onto the topic with a straightforward and clean approach based on examples and answering many whys along the way so that more individuals can appreciate the state of the art technology, its innovators and ultimately the beauty of math. Paper's contribution is a simplistic exposition with a sufficient and gradually increasing level of complexity, necessary to understand zk-SNARK without any prerequisite knowledge of the subject, cryptography or advanced math. The primary goal is not only to explain how it works but why it works and how it came to be this way. | Maksym Petkus |
| 2011.02677 | 982163 | 2020-11-10 08:34:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2011.02677v5 | The causal foundations of applied probability and statistics | Statistical science (as opposed to mathematical statistics) involves far more than probability theory, for it requires realistic causal models of data generators - even for purely descriptive goals. Statistical decision theory requires more causality: Rational decisions are actions taken to minimize costs while maximizing benefits, and thus require explication of causes of loss and gain. Competent statistical practice thus integrates logic, context, and probability into scientific inference and decision using narratives filled with causality. This reality was seen and accounted for intuitively by the founders of modern statistics, but was not well recognized in the ensuing statistical theory (which focused instead on the causally inert properties of probability measures). Nonetheless, both statistical foundations and basic statistics can and should be taught using formal causal models. The causal view of statistical science fits within a broader information-processing framework which illuminates and unifies frequentist, Bayesian, and related probability-based foundations of statistics. Causality theory can thus be seen as a key component connecting computation to contextual information, not extra-statistical but instead essential for sound statistical training and applications. | Sander Greenland |
| 2010.14610 | 22282320 | 2020-11-17 13:26:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2010.14610v1 | Improving seasonal forecast using probabilistic deep learning | The path toward realizing the potential of seasonal forecasting and its socioeconomic benefits depends heavily on improving general circulation model based dynamical forecasting systems. To improve dynamical seasonal forecast, it is crucial to set up forecast benchmarks, and clarify forecast limitations posed by model initialization errors, formulation deficiencies, and internal climate variability. With huge cost in generating large forecast ensembles, and limited observations for forecast verification, the seasonal forecast benchmarking and diagnosing task proves challenging. In this study, we develop a probabilistic deep neural network model, drawing on a wealth of existing climate simulations to enhance seasonal forecast capability and forecast diagnosis. By leveraging complex physical relationships encoded in climate simulations, our probabilistic forecast model demonstrates favorable deterministic and probabilistic skill compared to state-of-the-art dynamical forecast systems in quasi-global seasonal forecast of precipitation and near-surface temperature. We apply this probabilistic forecast methodology to quantify the impacts of initialization errors and model formulation deficiencies in a dynamical seasonal forecasting system. We introduce the saliency analysis approach to efficiently identify the key predictors that influence seasonal variability. Furthermore, by explicitly modeling uncertainty using variational Bayes, we give a more definitive answer to how the El Nino/Southern Oscillation, the dominant mode of seasonal variability, modulates global seasonal predictability. | Baoxiang Pan, Gemma J. Anderson, AndrE Goncalves, Donald D. Lucas, CEline J. W. Bonfils, Jiwoo Lee |
| 2002.05909 | 13527215 | 2020-11-21 12:16:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2002.05909v3 | Deep reconstruction of strange attractors from time series | Experimental measurements of physical systems often have a limited number of independent channels, causing essential dynamical variables to remain unobserved. However, many popular methods for unsupervised inference of latent dynamics from experimental data implicitly assume that the measurements have higher intrinsic dimensionality than the underlying system---making coordinate identification a dimensionality reduction problem. Here, we study the opposite limit, in which hidden governing coordinates must be inferred from only a low-dimensional time series of measurements. Inspired by classical analysis techniques for partial observations of chaotic attractors, we introduce a general embedding technique for univariate and multivariate time series, consisting of an autoencoder trained with a novel latent-space loss function. We show that our technique reconstructs the strange attractors of synthetic and real-world systems better than existing techniques, and that it creates consistent, predictive representations of even stochastic systems. We conclude by using our technique to discover dynamical attractors in diverse systems such as patient electrocardiograms, household electricity usage, neural spiking, and eruptions of the Old Faithful geyser---demonstrating diverse applications of our technique for exploratory data analysis. | William Gilpin |
| 1906.01769 | 1560242 | 2020-11-21 12:18:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1906.01769v2 | PI-Net: A Deep Learning Approach to Extract Topological Persistence Images | Topological features such as persistence diagrams and their functional approximations like persistence images (PIs) have been showing substantial promise for machine learning and computer vision applications. This is greatly attributed to the robustness topological representations provide against different types of physical nuisance variables seen in real-world data, such as view-point, illumination, and more. However, key bottlenecks to their large scale adoption are computational expenditure and difficulty incorporating them in a differentiable architecture. We take an important step in this paper to mitigate these bottlenecks by proposing a novel one-step approach to generate PIs directly from the input data. We design two separate convolutional neural network architectures, one designed to take in multi-variate time series signals as input and another that accepts multi-channel images as input. We call these networks Signal PI-Net and Image PI-Net respectively. To the best of our knowledge, we are the first to propose the use of deep learning for computing topological features directly from data. We explore the use of the proposed PI-Net architectures on two applications: human activity recognition using tri-axial accelerometer sensor data and image classification. We demonstrate the ease of fusion of PIs in supervised deep learning architectures and speed up of several orders of magnitude for extracting PIs from data. Our code is available at https://github.com/anirudhsom/PI-Net. | Anirudh Som, Hongjun Choi, Karthikeyan Natesan Ramamurthy, Matthew Buman, Pavan Turaga |
| 1809.09269 | 1336087 | 2020-12-03 13:23:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1809.09269v2 | Sparse Circular Coordinates via Principal $\mathbb{Z}$-Bundles | We present in this paper an application of the theory of principal bundles to the problem of nonlinear dimensionality reduction in data analysis. More explicitly, we derive, from a 1-dimensional persistent cohomology computation, explicit formulas for circle-valued functions on data with nontrivial underlying topology. We show that the language of principal bundles leads to coordinates defined on an open neighborhood of the data, but computed using only a smaller subset of landmarks. It is in this sense that the coordinates are sparse. Several data examples are presented, as well as theoretical results underlying the construction. | Jose A. Perea |
| 2012.00174 | 162708 | 2020-12-03 17:00:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2012.00174v5 | What are the most important statistical ideas of the past 50 years? | We review the most important statistical ideas of the past half century, which we categorize as: counterfactual causal inference, bootstrapping and simulation-based inference, overparameterized models and regularization, Bayesian multilevel models, generic computation algorithms, adaptive decision analysis, robust inference, and exploratory data analysis. We discuss key contributions in these subfields, how they relate to modern computing and big data, and how they might be developed and extended in future decades. The goal of this article is to provoke thought and discussion regarding the larger themes of research in statistics and data science. | Andrew Gelman, Aki Vehtari |
| 1809.02942 | 4733582 | 2020-12-03 17:00:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1809.02942v2 | Cellular automata as convolutional neural networks | Deep learning techniques have recently demonstrated broad success in predicting complex dynamical systems ranging from turbulence to human speech, motivating broader questions about how neural networks encode and represent dynamical rules. We explore this problem in the context of cellular automata (CA), simple dynamical systems that are intrinsically discrete and thus difficult to analyze using standard tools from dynamical systems theory. We show that any CA may readily be represented using a convolutional neural network with a network-in-network architecture. This motivates our development of a general convolutional multilayer perceptron architecture, which we find can learn the dynamical rules for arbitrary CA when given videos of the CA as training data. In the limit of large network widths, we find that training dynamics are nearly identical across replicates, and that common patterns emerge in the structure of networks trained on different CA rulesets. We train ensembles of networks on randomly-sampled CA, and we probe how the trained networks internally represent the CA rules using an information-theoretic technique based on distributions of layer activation patterns. We find that CA with simpler rule tables produce trained networks with hierarchical structure and layer specialization, while more complex CA produce shallower representations---illustrating how the underlying complexity of the CA's rules influences the specificity of these internal representations. Our results suggest how the entropy of a physical process can affect its representation when learned by neural networks. | William Gilpin |
| 2012.01714 | 19745893 | 2020-12-04 11:15:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2012.01714v2 | AutoInt: Automatic Integration for Fast Neural Volume Rendering | Numerical integration is a foundational technique in scientific computing and is at the core of many computer vision applications. Among these applications, neural volume rendering has recently been proposed as a new paradigm for view synthesis, achieving photorealistic image quality. However, a fundamental obstacle to making these methods practical is the extreme computational and memory requirements caused by the required volume integrations along the rendered rays during training and inference. Millions of rays, each requiring hundreds of forward passes through a neural network are needed to approximate those integrations with Monte Carlo sampling. Here, we propose automatic integration, a new framework for learning efficient, closed-form solutions to integrals using coordinate-based neural networks. For training, we instantiate the computational graph corresponding to the derivative of the network. The graph is fitted to the signal to integrate. After optimization, we reassemble the graph to obtain a network that represents the antiderivative. By the fundamental theorem of calculus, this enables the calculation of any definite integral in two evaluations of the network. Applying this approach to neural rendering, we improve a tradeoff between rendering speed and image quality: improving render times by greater than 10 times with a tradeoff of slightly reduced image quality. | David B. Lindell, Julien N. P. Martel, Gordon Wetzstein |
| 1806.01261 | 9421943 | 2020-12-05 10:51:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1806.01261v3 | Relational inductive biases, deep learning, and graph networks | Artificial intelligence (AI) has undergone a renaissance recently, making major progress in key domains such as vision, language, control, and decision-making. This has been due, in part, to cheap data and cheap compute resources, which have fit the natural strengths of deep learning. However, many defining characteristics of human intelligence, which developed under much different pressures, remain out of reach for current approaches. In particular, generalizing beyond one's experiences--a hallmark of human intelligence from infancy--remains a formidable challenge for modern AI. The following is part position paper, part review, and part unification. We argue that combinatorial generalization must be a top priority for AI to achieve human-like abilities, and that structured representations and computations are key to realizing this objective. Just as biology uses nature and nurture cooperatively, we reject the false choice between "hand-engineering" and "end-to-end" learning, and instead advocate for an approach which benefits from their complementary strengths. We explore how using relational inductive biases within deep learning architectures can facilitate learning about entities, relations, and rules for composing them. We present a new building block for the AI toolkit with a strong relational inductive bias--the graph network--which generalizes and extends various approaches for neural networks that operate on graphs, and provides a straightforward interface for manipulating structured knowledge and producing structured behaviors. We discuss how graph networks can support relational reasoning and combinatorial generalization, laying the foundation for more sophisticated, interpretable, and flexible patterns of reasoning. As a companion to this paper, we have released an open-source software library for building graph networks, with demonstrations of how to use them in practice. | Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song, Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, Razvan Pascanu |
| 1902.04615 | 1707480 | 2020-12-20 12:22:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1902.04615v3 | Gauge Equivariant Convolutional Networks and the Icosahedral CNN | The principle of equivariance to symmetry transformations enables a theoretically grounded approach to neural network architecture design. Equivariant networks have shown excellent performance and data efficiency on vision and medical imaging problems that exhibit symmetries. Here we show how this principle can be extended beyond global symmetries to local gauge transformations. This enables the development of a very general class of convolutional neural networks on manifolds that depend only on the intrinsic geometry, and which includes many popular methods from equivariant and geometric deep learning. We implement gauge equivariant CNNs for signals defined on the surface of the icosahedron, which provides a reasonable approximation of the sphere. By choosing to work with this very regular manifold, we are able to implement the gauge equivariant convolution using a single conv2d call, making it a highly scalable and practical alternative to Spherical CNNs. Using this method, we demonstrate substantial improvements over previous methods on the task of segmenting omnidirectional images and global climate patterns. | Taco S. Cohen, Maurice Weiler, Berkay Kicanaoglu, Max Welling |
| 1706.05098 | 869440 | 2020-12-20 12:29:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1706.05098v1 | An Overview of Multi-Task Learning in Deep Neural Networks | Multi-task learning (MTL) has led to successes in many applications of machine learning, from natural language processing and speech recognition to computer vision and drug discovery. This article aims to give a general overview of MTL, particularly in deep neural networks. It introduces the two most common methods for MTL in Deep Learning, gives an overview of the literature, and discusses recent advances. In particular, it seeks to help ML practitioners apply MTL by shedding light on how MTL works and providing guidelines for choosing appropriate auxiliary tasks. | Sebastian Ruder |
| 1506.08903 | 932621 | 2020-12-27 15:34:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1506.08903v7 | A roadmap for the computation of persistent homology | Persistent homology (PH) is a method used in topological data analysis (TDA) to study qualitative features of data that persist across multiple scales. It is robust to perturbations of input data, independent of dimensions and coordinates, and provides a compact representation of the qualitative features of the input. The computation of PH is an open area with numerous important and fascinating challenges. The field of PH computation is evolving rapidly, and new algorithms and software implementations are being updated and released at a rapid pace. The purposes of our article are to (1) introduce theory and computational methods for PH to a broad range of computational scientists and (2) provide benchmarks of state-of-the-art implementations for the computation of PH. We give a friendly introduction to PH, navigate the pipeline for the computation of PH with an eye towards applications, and use a range of synthetic and real-world data sets to evaluate currently available open-source implementations for the computation of PH. Based on our benchmarking, we indicate which algorithms and implementations are best suited to different types of data sets. In an accompanying tutorial, we provide guidelines for the computation of PH. We make publicly available all scripts that we wrote for the tutorial, and we make available the processed version of the data sets used in the benchmarking. | Nina Otter, Mason A. Porter, Ulrike Tillmann, Peter Grindrod, Heather A. Harrington |
| 1506.08903 | 932621 | 2020-12-27 15:34:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1506.08903v7 | A roadmap for the computation of persistent homology | Persistent homology (PH) is a method used in topological data analysis (TDA) to study qualitative features of data that persist across multiple scales. It is robust to perturbations of input data, independent of dimensions and coordinates, and provides a compact representation of the qualitative features of the input. The computation of PH is an open area with numerous important and fascinating challenges. The field of PH computation is evolving rapidly, and new algorithms and software implementations are being updated and released at a rapid pace. The purposes of our article are to (1) introduce theory and computational methods for PH to a broad range of computational scientists and (2) provide benchmarks of state-of-the-art implementations for the computation of PH. We give a friendly introduction to PH, navigate the pipeline for the computation of PH with an eye towards applications, and use a range of synthetic and real-world data sets to evaluate currently available open-source implementations for the computation of PH. Based on our benchmarking, we indicate which algorithms and implementations are best suited to different types of data sets. In an accompanying tutorial, we provide guidelines for the computation of PH. We make publicly available all scripts that we wrote for the tutorial, and we make available the processed version of the data sets used in the benchmarking. | Nina Otter, Mason A. Porter, Ulrike Tillmann, Peter Grindrod, Heather A. Harrington |
| 2010.03633 | 331718 | 2021-01-06 07:47:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2010.03633v2 | Simplicial Neural Networks | We present simplicial neural networks (SNNs), a generalization of graph neural networks to data that live on a class of topological spaces called simplicial complexes. These are natural multi-dimensional extensions of graphs that encode not only pairwise relationships but also higher-order interactions between vertices - allowing us to consider richer data, including vector fields and $n$-fold collaboration networks. We define an appropriate notion of convolution that we leverage to construct the desired convolutional neural networks. We test the SNNs on the task of imputing missing data on coauthorship complexes. | Stefania Ebli, Michaël Defferrard, Gard Spreemann |
| 2006.08806 | 576989 | 2021-01-28 06:32:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2006.08806v4 | Liquidity Provider Returns in Geometric Mean Markets | Geometric mean market makers (G3Ms), such as Uniswap and Balancer, comprise a popular class of automated market makers (AMMs) defined by the following rule: the reserves of the AMM before and after each trade must have the same (weighted) geometric mean. This paper extends several results known for constant-weight G3Ms to the general case of G3Ms with time-varying and potentially stochastic weights. These results include the returns and no-arbitrage prices of liquidity pool (LP) shares that investors receive for supplying liquidity to G3Ms. Using these expressions, we show how to create G3Ms whose LP shares replicate the payoffs of financial derivatives. The resulting hedges are model-independent and exact for derivative contracts whose payoff functions satisfy an elasticity constraint. These strategies allow LP shares to replicate various trading strategies and financial contracts, including standard options. G3Ms are thus shown to be capable of recreating a variety of active trading strategies through passive positions in LP shares. | Alex Evans |
| 2012.08040 | 1416724 | 2021-01-28 06:38:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2012.08040v1 | When does the tail wag the dog? Curvature and market making | Liquidity and trading activity on constant function market makers (CFMMs) such as Uniswap, Curve, and Balancer has grown significantly in the second half of 2020. Much of the growth of these protocols has been driven by incentivized pools or 'yield farming', which reward participants in crypto assets for providing liquidity to CFMMs. As a result, CFMMs and associated protocols, which were historically very small markets, now constitute the most liquid trading venues for a large number of crypto assets. But what does it mean for a CFMM to be the most liquid market? In this paper, we propose a basic definition of price sensitivity and liquidity. We show that this definition is tightly related to the curvature of a CFMM's trading function and can be used to explain a number of heuristic results. For example, we show that low-curvature markets are good for coins whose market value is approximately fixed and that high-curvature markets are better for liquidity providers when traders have an informational edge. Additionally, the results can also be used to model interacting markets and explain the rise of incentivized liquidity provision, also known as 'yield farming.' | Guillermo Angeris, Alex Evans, Tarun Chitra |
| 2101.08344 | 4574426 | 2021-02-16 06:43:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2101.08344v1 | Structured Time-Delay Models for Dynamical Systems with Connections to Frenet-Serret Frame | Time-delay embeddings and dimensionality reduction are powerful techniques for discovering effective coordinate systems to represent the dynamics of physical systems. Recently, it has been shown that models identified by dynamic mode decomposition (DMD) on time-delay coordinates provide linear representations of strongly nonlinear systems, in the so-called Hankel alternative view of Koopman (HAVOK) approach. Curiously, the resulting linear model has a matrix representation that is approximately antisymmetric and tridiagonal with a zero diagonal; for chaotic systems, there is an additional forcing term in the last component. In this paper, we establish a new theoretical connection between HAVOK and the Frenet-Serret frame from differential geometry, and also develop an improved algorithm to identify more stable and accurate models from less data. In particular, we show that the sub- and super-diagonal entries of the linear model correspond to the intrinsic curvatures in Frenet-Serret frame. Based on this connection, we modify the algorithm to promote this antisymmetric structure, even in the noisy, low-data limit. We demonstrate this improved modeling procedure on data from several nonlinear synthetic and real-world examples. | Seth M. Hirsh, Sara M. Ichinaga, Steven L. Brunton, J. Nathan Kutz, Bingni W. Brunton |
| 2012.11551 | 8832701 | 2021-02-16 06:46:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2012.11551v1 | AVAE: Adversarial Variational Auto Encoder | Among the wide variety of image generative models, two models stand out: Variational Auto Encoders (VAE) and Generative Adversarial Networks (GAN). GANs can produce realistic images, but they suffer from mode collapse and do not provide simple ways to get the latent representation of an image. On the other hand, VAEs do not have these problems, but they often generate images less realistic than GANs. In this article, we explain that this lack of realism is partially due to a common underestimation of the natural image manifold dimensionality. To solve this issue we introduce a new framework that combines VAE and GAN in a novel and complementary way to produce an auto-encoding model that keeps VAEs properties while generating images of GAN-quality. We evaluate our approach both qualitatively and quantitatively on five image datasets. | Antoine Plumerault, Hervé Le Borgne, Céline Hudelot |
| 2101.03933 | 8378238 | 2021-02-16 06:47:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2101.03933v1 | Variability in higher order structure of noise added to weighted networks | From spiking activity in neuronal networks to force chains in granular materials, the behavior of many real-world systems depends on a network of both strong and weak interactions. These interactions give rise to complex and higher-order system behaviors, and are encoded using data as the network's edges. However, distinguishing between true weak edges and low-weight edges caused by noise remains a challenge. We address this problem by examining the higher-order structure of noisy, weak edges added to model networks. We find that the structure of low-weight, noisy edges varies according to the topology of the model network to which it is added. By investigating this variation more closely, we see that at least three qualitative classes of noise structure emerge. Furthermore, we observe that the structure of noisy edges contains enough model-specific information to classify the model networks with moderate accuracy. Finally, we offer network generation rules that can drive different types of structure in added noisy edges. Our results demonstrate that noise does not present as a monolithic nuisance, but rather as a nuanced, topology-dependent, and even useful entity in characterizing higher-order network interactions. Hence, we provide an alternate approach to noise management by embracing its role in such interactions. | Ann S. Blevins, Jason Z. Kim, Danielle S. Bassett |
| 1812.05944 | 3077936 | 2021-02-16 06:51:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1812.05944v3 | A Tutorial on Distance Metric Learning: Mathematical Foundations, Algorithms, Experimental Analysis, Prospects and Challenges (with Appendices on Mathematical Background and Detailed Algorithms Explanation) | Distance metric learning is a branch of machine learning that aims to learn distances from the data, which enhances the performance of similarity-based algorithms. This tutorial provides a theoretical background and foundations on this topic and a comprehensive experimental analysis of the most-known algorithms. We start by describing the distance metric learning problem and its main mathematical foundations, divided into three main blocks: convex analysis, matrix analysis and information theory. Then, we will describe a representative set of the most popular distance metric learning methods used in classification. All the algorithms studied in this paper will be evaluated with exhaustive testing in order to analyze their capabilities in standard classification problems, particularly considering dimensionality reduction and kernelization. The results, verified by Bayesian statistical tests, highlight a set of outstanding algorithms. Finally, we will discuss several potential future prospects and challenges in this field. This tutorial will serve as a starting point in the domain of distance metric learning from both a theoretical and practical perspective. | Juan Luis Suárez-Díaz, Salvador García, Francisco Herrera |
| 2012.02258 | 795687 | 2021-02-16 06:53:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2012.02258v1 | WedgeChain: A Trusted Edge-Cloud Store With Asynchronous (Lazy) Trust | We propose WedgeChain, a data store that spans both edge and cloud nodes (an edge-cloud system). WedgeChain consists of a logging layer and a data indexing layer. In this study, we encounter two challenges: (1) edge nodes are untrusted and potentially malicious, and (2) edge-cloud coordination is expensive. WedgeChain tackles these challenges by the following proposals: (1) Lazy (asynchronous) certification: where data is committed at the untrusted edge and then lazily certified at the cloud node. This lazy certification method takes advantage of the observation that an untrusted edge node is unlikely to act maliciously if it knows it will be detected (and punished) eventually. Our lazy certification method guarantees that malicious acts (i.e., lying) are eventually detected. (2) Data-free certification: our lazy certification method only needs to send digests of data to the cloud, instead of sending all data to the cloud, which enables saving network and cloud resources and reduce costs. (3) LSMerkle: we extend a trusted index (mLSM) to enable indexing data at the edge while utilizing lazy and data-free certification. | Faisal Nawab |
| 2006.11156 | 1274539 | 2021-02-16 06:53:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2006.11156v1 | Why Stake When You Can Borrow? | As smart contract platforms autonomously manage billions of dollars of capital, quantifying the portfolio risk that investors engender in these systems is increasingly important. Recent work illustrates that Proof of Stake (PoS) is vulnerable to financial attacks arising from on-chain lending and has worse capital efficiency than Proof of Work (PoW) \cite{fanti_pos_econ}. Numerous methods for improving capital efficiency have been proposed that allow stakers to create fungible derivative claims on their staked assets. In this paper, we construct a unifying model for studying the security risks of these proposals. This model combines birth-death P\'olya processes and risk models adapted from the credit derivatives literature to assess token inequality and return profiles. We find that there is a sharp transition between 'safe' and 'unsafe' derivative usage. Surprisingly, we find that contrary to \cite{fanti2019compounding} there exist conditions where derivatives can \emph{reduce} concentration of wealth in these networks. This model also applies to Decentralized Finance (DeFi) protocols where staked assets are used as insurance. Our theoretical results are validated using agent-based simulation. | Tarun Chitra, Alex Evans |
| 2102.05242 | 2722195 | 2021-02-17 16:20:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2102.05242v2 | Patterns, predictions, and actions: A story about machine learning | This graduate textbook on machine learning tells a story of how patterns in data support predictions and consequential actions. Starting with the foundations of decision making, we cover representation, optimization, and generalization as the constituents of supervised learning. A chapter on datasets as benchmarks examines their histories and scientific bases. Self-contained introductions to causality, the practice of causal inference, sequential decision making, and reinforcement learning equip the reader with concepts and tools to reason about actions and their consequences. Throughout, the text discusses historical context and societal impact. We invite readers from all backgrounds; some experience with probability, calculus, and linear algebra suffices. | Moritz Hardt, Benjamin Recht |
| 2009.14021 | 3794695 | 2021-02-22 21:14:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2009.14021v1 | High-Frequency Trading on Decentralized On-Chain Exchanges | Decentralized exchanges (DEXs) allow parties to participate in financial markets while retaining full custody of their funds. However, the transparency of blockchain-based DEX in combination with the latency for transactions to be processed, makes market-manipulation feasible. For instance, adversaries could perform front-running -- the practice of exploiting (typically non-public) information that may change the price of an asset for financial gain. In this work we formalize, analytically exposit and empirically evaluate an augmented variant of front-running: sandwich attacks, which involve front- and back-running victim transactions on a blockchain-based DEX. We quantify the probability of an adversarial trader being able to undertake the attack, based on the relative positioning of a transaction within a blockchain block. We find that a single adversarial trader can earn a daily revenue of over several thousand USD when performing sandwich attacks on one particular DEX -- Uniswap, an exchange with over 5M USD daily trading volume by June 2020. In addition to a single-adversary game, we simulate the outcome of sandwich attacks under multiple competing adversaries, to account for the real-world trading environment. | Liyi Zhou, Kaihua Qin, Christof Ferreira Torres, Duc V Le, Arthur Gervais |
| 1805.08498 | 924127 | 2021-02-25 15:44:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1805.08498v4 | Implicit Reparameterization Gradients | By providing a simple and efficient way of computing low-variance gradients of continuous random variables, the reparameterization trick has become the technique of choice for training a variety of latent variable models. However, it is not applicable to a number of important continuous distributions. We introduce an alternative approach to computing reparameterization gradients based on implicit differentiation and demonstrate its broader applicability by applying it to Gamma, Beta, Dirichlet, and von Mises distributions, which cannot be used with the classic reparameterization trick. Our experiments show that the proposed approach is faster and more accurate than the existing gradient estimators for these distributions. | Michael Figurnov, Shakir Mohamed, Andriy Mnih |
| 1509.03264 | 434868 | 2021-03-01 07:46:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1509.03264v6 | Can You hear the Shape of a Market? Geometric Arbitrage and Spectral Theory | Geometric Arbitrage Theory reformulates a generic asset model possibly allowing for arbitrage by packaging all assets and their forwards dynamics into a stochastic principal fibre bundle, with a connection whose parallel transport encodes discounting and portfolio rebalancing, and whose curvature measures, in this geometric language, the 'instantaneous arbitrage capability' generated by the market itself. The cashflow bundle is the vector bundle associated to this stochastic principal fibre bundle for the natural choice of the vector space fibre. The cashflow bundle carries a stochastic covariant differentiation induced by the connection on the principal fibre bundle. The link between arbitrage theory and spectral theory of the connection Laplacian on the vector bundle is given by the zero eigenspace resulting in a parametrization of all risk neutral measures equivalent to the statistical one. This indicates that a market satisfies the (NFLVR) condition if and only if $0$ is in the discrete spectrum of the connection Laplacian on the cash flow bundle or of the Dirac Laplacian of the twisted cash flow bundle with the exterior algebra bundle. We apply this result by extending Jarrow-Protter-Shimbo theory of asset bubbles for complete arbitrage free markets to markets not satisfying the (NFLVR). Moreover, by means of the Atiyah-Singer index theorem, we prove that the Euler characteristic of the asset nominal space is a topological obstruction to the the (NFLVR) condition, and, by means of the Bochner-Weitzenb\"ock formula, the non vanishing of the homology group of the cash flow bundle is revealed to be a topological obstruction to (NFLVR), too. Asset bubbles are defined, classified and decomposed for markets allowing arbitrage. | Simone Farinelli, Hideyuki Takada |
| 2103.01507 | 3579232 | 2021-03-03 14:24:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2103.01507v1 | Arnold Conjecture and Morava K-theory | We prove that the rank of the cohomology of a closed symplectic manifold with coefficients in a field of characteristic $p$ is smaller than the number of periodic orbits of any non-degenerate Hamiltonian flow. Following Floer, the proof relies on constructing a homology group associated to each such flow, and comparing it with the homology of the ambient symplectic manifold. The proof does not proceed by constructing a version of Floer's complex with characteristic $p$ coefficients, but uses instead the canonical (stable) complex orientations of moduli spaces of Floer trajectories to construct a version of Floer homology with coefficients in Morava's $K$-theories, and can thus be seen as an implementation of Cohen, Jones, and Segal's vision for a Floer homotopy theory. The key feature of Morava K-theory that allows the construction to be carried out is the fact that the corresponding homology and cohomology groups of classifying spaces of finite groups satisfy Poincar\'e duality. | Mohammed Abouzaid, Andrew J. Blumberg |
| 0910.1671 | 684818 | 2021-03-14 16:54:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/0910.1671v10 | Geometric Arbitrage Theory and Market Dynamics Reloaded | We have embedded the classical theory of stochastic finance into a differential geometric framework called Geometric Arbitrage Theory and show that it is possible to: --Write arbitrage as curvature of a principal fibre bundle. --Parameterize arbitrage strategies by its holonomy. --Give the Fundamental Theorem of Asset Pricing a differential homotopic characterization. --Characterize Geometric Arbitrage Theory by five principles and show they they are consistent with the classical theory of stochastic finance. --Derive for a closed market the equilibrium solution for market portfolio and dynamics in the cases where: -->Arbitrage is allowed but minimized. -->Arbitrage is not allowed. --Prove that the no-free-lunch-with-vanishing-risk condition implies the zero curvature condition. | Simone Farinelli |
| 2103.03212 | 2160626 | 2021-03-17 06:46:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2103.03212v2 | Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks | The pairwise interaction paradigm of graph machine learning has predominantly governed the modelling of relational systems. However, graphs alone cannot capture the multi-level interactions present in many complex systems and the expressive power of such schemes was proven to be limited. To overcome these limitations, we propose Message Passing Simplicial Networks (MPSNs), a class of models that perform message passing on simplicial complexes (SCs). To theoretically analyse the expressivity of our model we introduce a Simplicial Weisfeiler-Lehman (SWL) colouring procedure for distinguishing non-isomorphic SCs. We relate the power of SWL to the problem of distinguishing non-isomorphic graphs and show that SWL and MPSNs are strictly more powerful than the WL test and not less powerful than the 3-WL test. We deepen the analysis by comparing our model with traditional graph neural networks (GNNs) with ReLU activations in terms of the number of linear regions of the functions they can represent. We empirically support our theoretical claims by showing that MPSNs can distinguish challenging strongly regular graphs for which GNNs fail and, when equipped with orientation equivariant layers, they can improve classification accuracy in oriented SCs compared to a GNN baseline. | Cristian Bodnar, Fabrizio Frasca, Yu Guang Wang, Nina Otter, Guido Montúfar, Pietro Liò, Michael Bronstein |
| 1705.07664 | 1184592 | 2021-03-19 06:23:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1705.07664v2 | CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filters | The rise of graph-structured data such as social networks, regulatory networks, citation graphs, and functional brain networks, in combination with resounding success of deep learning in various applications, has brought the interest in generalizing deep learning models to non-Euclidean domains. In this paper, we introduce a new spectral domain convolutional architecture for deep learning on graphs. The core ingredient of our model is a new class of parametric rational complex functions (Cayley polynomials) allowing to efficiently compute spectral filters on graphs that specialize on frequency bands of interest. Our model generates rich spectral filters that are localized in space, scales linearly with the size of the input data for sparsely-connected graphs, and can handle different constructions of Laplacian operators. Extensive experimental results show the superior performance of our approach, in comparison to other spectral domain convolutional architectures, on spectral image classification, community detection, vertex classification and matrix completion tasks. | Ron Levie, Federico Monti, Xavier Bresson, Michael M. Bronstein |
| 2003.02345 | 305192 | 2021-03-25 07:43:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2003.02345v2 | The base-e representation of numbers and the power law | Some properties of the optimal representation of numbers are investigated. This representation, which is to the base-e, is examined for coding of integers. An approximate representation without fractions that we call WF is introduced and compared with base-2 and base-3 representations, which are next to base-e in efficiency. Since trees are analogous to number representation, we explore the relevance of the statistical optimality of the base-e system for the understanding of complex system behavior and of social networks. We show that this provides a new theoretical explanation for the nature of the power law exhibited by many open complex systems. In specific, we show that the power law distribution most often proposed for such systems has a form that is similar to that derived from the optimal base-e representation. | Subhash Kak |
| 2103.12732 | 792509 | 2021-04-07 09:23:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2103.12732v7 | SoK: Decentralized Exchanges (DEX) with Automated Market Maker (AMM) Protocols | As an integral part of the decentralized finance (DeFi) ecosystem, decentralized exchanges (DEXs) with automated market maker (AMM) protocols have gained massive traction with the recently revived interest in blockchain and distributed ledger technology (DLT) in general. Instead of matching the buy and sell sides, automated market makers (AMMs) employ a peer-to-pool method and determine asset price algorithmically through a so-called conservation function. To facilitate the improvement and development of automated market maker (AMM)-based decentralized exchanges (DEXs), we create the first systematization of knowledge in this area. We first establish a general automated market maker (AMM) framework describing the economics and formalizing the system's state-space representation. We then employ our framework to systematically compare the top automated market maker (AMM) protocols' mechanics, illustrating their conservation functions, as well as slippage and divergence loss functions. We further discuss security and privacy concerns, how they are enabled by automated market maker (AMM)-based decentralized exchanges (DEXs)' inherent properties, and explore mitigating solutions. Finally, we conduct a comprehensive literature review on related work covering both decentralized finance (DeFi) and conventional market microstructure. | Jiahua Xu, Krzysztof Paruch, Simon Cousaert, Yebo Feng |
| 2105.05233 | 32348895 | 2021-05-14 06:51:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2105.05233v4 | Diffusion Models Beat GANs on Image Synthesis | We show that diffusion models can achieve image sample quality superior to the current state-of-the-art generative models. We achieve this on unconditional image synthesis by finding a better architecture through a series of ablations. For conditional image synthesis, we further improve sample quality with classifier guidance: a simple, compute-efficient method for trading off diversity for fidelity using gradients from a classifier. We achieve an FID of 2.97 on ImageNet 128$\times$128, 4.59 on ImageNet 256$\times$256, and 7.72 on ImageNet 512$\times$512, and we match BigGAN-deep even with as few as 25 forward passes per sample, all while maintaining better coverage of the distribution. Finally, we find that classifier guidance combines well with upsampling diffusion models, further improving FID to 3.94 on ImageNet 256$\times$256 and 3.85 on ImageNet 512$\times$512. We release our code at https://github.com/openai/guided-diffusion | Prafulla Dhariwal, Alex Nichol |
| 2006.13922 | 1347037 | 2021-05-14 07:05:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2006.13922v3 | DeFi Protocols for Loanable Funds: Interest Rates, Liquidity and Market Efficiency | We coin the term *Protocols for Loanable Funds (PLFs)* to refer to protocols which establish distributed ledger-based markets for loanable funds. PLFs are emerging as one of the main applications within Decentralized Finance (DeFi), and use smart contract code to facilitate the intermediation of loanable funds. In doing so, these protocols allow agents to borrow and save programmatically. Within these protocols, interest rate mechanisms seek to equilibrate the supply and demand for funds. In this paper, we review the methodologies used to set interest rates on three prominent DeFi PLFs, namely Compound, Aave and dYdX. We provide an empirical examination of how these interest rate rules have behaved since their inception in response to differing degrees of liquidity. We then investigate the market efficiency and inter-connectedness between multiple protocols, examining first whether Uncovered Interest Parity holds within a particular protocol and second whether the interest rates for a particular token market show dependence across protocols, developing a Vector Error Correction Model for the dynamics. | Lewis Gudgeon, Sam M. Werner, Daniel Perez, William J. Knottenbelt |
| 2102.04152 | 2904228 | 2021-05-14 07:14:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2102.04152v2 | EigenGame Unloaded: When playing games is better than optimizing | We build on the recently proposed EigenGame that views eigendecomposition as a competitive game. EigenGame's updates are biased if computed using minibatches of data, which hinders convergence and more sophisticated parallelism in the stochastic setting. In this work, we propose an unbiased stochastic update that is asymptotically equivalent to EigenGame, enjoys greater parallelism allowing computation on datasets of larger sample sizes, and outperforms EigenGame in experiments. We present applications to finding the principal components of massive datasets and performing spectral clustering of graphs. We analyze and discuss our proposed update in the context of EigenGame and the shift in perspective from optimization to games. | Ian Gemp, Brian McWilliams, Claire Vernade, Thore Graepel |
| 1711.02625 | 750319 | 2021-05-17 17:02:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1711.02625v5 | In search of a new economic model determined by logistic growth | In this paper we extend the work by Ryuzo Sato devoted to the development of economic growth models within the framework of the Lie group theory. We propose a new growth model based on the assumption of logistic growth in factors. It is employed to derive new production functions and introduce a new notion of wage share. In the process it is shown that the new functions compare reasonably well against relevant economic data. The corresponding problem of maximization of profit under conditions of perfect competition is solved with the aid of one of these functions. In addition, it is explained in reasonably rigorous mathematical terms why Bowley's law no longer holds true in post-1960 data. | Roman G. Smirnov, Kunpeng Wang |
| 1910.06739 | 301760 | 2021-05-17 17:06:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1910.06739v2 | The Cobb-Douglas production function revisited | Charles Cobb and Paul Douglas in 1928 used data from the US manufacturing sector for 1899-1922 to introduce what is known today as the Cobb-Douglas production function that has been widely used in economic theory for decades. We employ the R programming language to fit the formulas for the parameters of the Cobb-Douglas production function generated by the authors recently via the bi-Hamiltonian approach to the same data set utilized by Cobb and Douglas. We conclude that the formulas for the output elasticities and total factor productivity are compatible with the original 1928 data. | Roman G. Smirnov, Kunpeng Wang |
| 1604.04687 | 1903786 | 2021-05-18 07:00:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1604.04687v2 | Insights from Machine Learning for Evaluating Production Function Estimators on Manufacturing Survey Data | Organizations like U.S. Census Bureau rely on non-exhaustive surveys to estimate industry-level production functions in years in which a full Census is not conducted. When analyzing data from non-census years, we propose selecting an estimator based on a weighting of its in-sample and predictive performance. We compare Cobb-Douglas functional assumptions to existing nonparametric shape constrained estimators and a newly proposed estimator. For simulated data, we find that our proposed estimator has the lowest weighted errors. For actual data, specifically the 2010 Chilean Annual National Industrial Survey, a Cobb-Douglas specification describes at least 90\% as much variance as the best alternative estimators in practically all cases considered providing two insights: the benefits of using application data for selecting an estimator, and the benefits of structure in noisy data. | José Luis Preciado Arreola, Daisuke Yagi, Andrew L. Johnson |
| 2004.11118 | 294356 | 2021-05-18 10:04:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2004.11118v1 | Some Applications of Lie Groups in Theory of Technical Progress | In recent decades, we have known some interesting applications of Lie theory in the theory of technological progress. Firstly, we will discuss some results of R. Saito in \cite{rS1980} and \cite{rS1981} about the application modeling of Lie groups in the theory of technical progress. Next, we will describe the result on Romanian economy of G. Zaman and Z. Goschin in \cite{ZG2010}. Finally, by using Sato's results and applying the method of G. Zaman and Z. Goschin, we give an estimation of the GDP function of Viet Nam for the 1995-2018 period and give several important observations about the impact of technical progress on economic growth of Viet Nam. | Le Anh Vu, Duong Quang Hoa, Nguyen Minh Tri, Ha Van Hieu |
| 1906.11224 | 147706 | 2021-05-18 10:07:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1906.11224v1 | The Hamiltonian approach to the problem of derivation of production functions in economic growth theory | We introduce a general Hamiltonian framework that appears to be a natural setting for the derivation of various production functions in economic growth theory, starting with the celebrated Cobb-Douglas function. Employing our method, we investigate some existing models and propose a new one as special cases of the general $n$-dimensional Lotka-Volterra system of eco-dynamics. | Roman G. Smirnov, Kunpeng Wang |
| 2004.10178 | 1020074 | 2021-06-02 08:03:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2004.10178v2 | Forecasting directional movements of stock prices for intraday trading using LSTM and random forests | We employ both random forests and LSTM networks (more precisely CuDNNLSTM) as training methodologies to analyze their effectiveness in forecasting out-of-sample directional movements of constituent stocks of the S&P 500 from January 1993 till December 2018 for intraday trading. We introduce a multi-feature setting consisting not only of the returns with respect to the closing prices, but also with respect to the opening prices and intraday returns. As trading strategy, we use Krauss et al. (2017) and Fischer & Krauss (2018) as benchmark. On each trading day, we buy the 10 stocks with the highest probability and sell short the 10 stocks with the lowest probability to outperform the market in terms of intraday returns -- all with equal monetary weight. Our empirical results show that the multi-feature setting provides a daily return, prior to transaction costs, of 0.64% using LSTM networks, and 0.54% using random forests. Hence we outperform the single-feature setting in Fischer & Krauss (2018) and Krauss et al. (2017) consisting only of the daily returns with respect to the closing prices, having corresponding daily returns of 0.41% and of 0.39% with respect to LSTM and random forests, respectively. | Pushpendu Ghosh, Ariel Neufeld, Jajati Keshari Sahoo |
| 2103.02559 | 17182153 | 2021-06-04 09:09:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2103.02559v4 | Minimum-Distortion Embedding | We consider the vector embedding problem. We are given a finite set of items, with the goal of assigning a representative vector to each one, possibly under some constraints (such as the collection of vectors being standardized, i.e., having zero mean and unit covariance). We are given data indicating that some pairs of items are similar, and optionally, some other pairs are dissimilar. For pairs of similar items, we want the corresponding vectors to be near each other, and for dissimilar pairs, we want the corresponding vectors to not be near each other, measured in Euclidean distance. We formalize this by introducing distortion functions, defined for some pairs of the items. Our goal is to choose an embedding that minimizes the total distortion, subject to the constraints. We call this the minimum-distortion embedding (MDE) problem. The MDE framework is simple but general. It includes a wide variety of embedding methods, such as spectral embedding, principal component analysis, multidimensional scaling, dimensionality reduction methods (like Isomap and UMAP), force-directed layout, and others. It also includes new embeddings, and provides principled ways of validating historical and new embeddings alike. We develop a projected quasi-Newton method that approximately solves MDE problems and scales to large data sets. We implement this method in PyMDE, an open-source Python package. In PyMDE, users can select from a library of distortion functions and constraints or specify custom ones, making it easy to rapidly experiment with different embeddings. Our software scales to data sets with millions of items and tens of millions of distortion functions. To demonstrate our method, we compute embeddings for several real-world data sets, including images, an academic co-author network, US county demographic data, and single-cell mRNA transcriptomes. | Akshay Agrawal, Alnur Ali, Stephen Boyd |
| 1804.07346 | 1831357 | 2021-06-06 10:47:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1804.07346v2 | Symbolic tensor calculus on manifolds: a SageMath implementation | These lecture notes present a method for symbolic tensor calculus that (i) runs on fully specified smooth manifolds (described by an atlas), (ii) is not limited to a single coordinate chart or vector frame, (iii) runs even on non-parallelizable manifolds and (iv) is independent of the symbolic backend used to perform calculus at the level of coordinate expressions. In addition to the main ideas, we discuss some details of the implementation in the open-source mathematics software system SageMath, which has been performed via the SageManifolds project. | Eric Gourgoulhon, Marco Mancini |
| 2010.14694 | 854311 | 2021-06-13 07:09:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2010.14694v2 | Deep Learning for Individual Heterogeneity: An Automatic Inference Framework | We develop methodology for estimation and inference using machine learning to enrich economic models. Our framework takes a standard economic model and recasts the parameters as fully flexible nonparametric functions, to capture the rich heterogeneity based on potentially high dimensional or complex observable characteristics. These "parameter functions" retain the interpretability, economic meaning, and discipline of classical parameters. Deep learning is particularly well-suited to structured modeling of heterogeneity in economics. We show how to design the network architecture to match the structure of the economic model, delivering novel methodology that moves deep learning beyond prediction. We prove convergence rates for the estimated parameter functions. These functions are the key inputs into the finite-dimensional parameter of inferential interest. We obtain inference based on a novel influence function calculation that covers any second-stage parameter and any machine-learning-enriched model that uses a smooth per-observation loss function. No additional derivations are required. The score can be taken directly to data, using automatic differentiation if needed. The researcher need only define the original model and define the parameter of interest. A key insight is that we need not write down the influence function in order to evaluate it on the data. Our framework gives new results for a host of contexts, covering such diverse examples as price elasticities, willingness-to-pay, and surplus measures in binary or multinomial choice models, effects of continuous treatment variables, fractional outcome models, count data, heterogeneous production functions, and more. We apply our methodology to a large scale advertising experiment for short-term loans. We show how economically meaningful estimates and inferences can be made that would be unavailable without our results. | Max H. Farrell, Tengyuan Liang, Sanjog Misra |
| 1909.07889 | 620043 | 2021-06-13 08:19:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1909.07889v3 | Distributional conformal prediction | We propose a robust method for constructing conditionally valid prediction intervals based on models for conditional distributions such as quantile and distribution regression. Our approach can be applied to important prediction problems including cross-sectional prediction, k-step-ahead forecasts, synthetic controls and counterfactual prediction, and individual treatment effects prediction. Our method exploits the probability integral transform and relies on permuting estimated ranks. Unlike regression residuals, ranks are independent of the predictors, allowing us to construct conditionally valid prediction intervals under heteroskedasticity. We establish approximate conditional validity under consistent estimation and provide approximate unconditional validity under model misspecification, overfitting, and with time series data. We also propose a simple "shape" adjustment of our baseline method that yields optimal prediction intervals. | Victor Chernozhukov, Kaspar Wüthrich, Yinchu Zhu |
| 2106.06020 | 10672063 | 2021-06-14 12:14:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2106.06020v1 | Coordinate Independent Convolutional Networks -- Isometry and Gauge Equivariant Convolutions on Riemannian Manifolds | Motivated by the vast success of deep convolutional networks, there is a great interest in generalizing convolutions to non-Euclidean manifolds. A major complication in comparison to flat spaces is that it is unclear in which alignment a convolution kernel should be applied on a manifold. The underlying reason for this ambiguity is that general manifolds do not come with a canonical choice of reference frames (gauge). Kernels and features therefore have to be expressed relative to arbitrary coordinates. We argue that the particular choice of coordinatization should not affect a network's inference -- it should be coordinate independent. A simultaneous demand for coordinate independence and weight sharing is shown to result in a requirement on the network to be equivariant under local gauge transformations (changes of local reference frames). The ambiguity of reference frames depends thereby on the G-structure of the manifold, such that the necessary level of gauge equivariance is prescribed by the corresponding structure group G. Coordinate independent convolutions are proven to be equivariant w.r.t. those isometries that are symmetries of the G-structure. The resulting theory is formulated in a coordinate free fashion in terms of fiber bundles. To exemplify the design of coordinate independent convolutions, we implement a convolutional network on the M\"obius strip. The generality of our differential geometric formulation of convolutional networks is demonstrated by an extensive literature review which explains a large number of Euclidean CNNs, spherical CNNs and CNNs on general surfaces as specific instances of coordinate independent convolutions. | Maurice Weiler, Patrick Forré, Erik Verlinde, Max Welling |
| 1806.06373 | 1485846 | 2021-06-20 11:17:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1806.06373v1 | Geodesic Convex Optimization: Differentiation on Manifolds, Geodesics, and Convexity | Convex optimization is a vibrant and successful area due to the existence of a variety of efficient algorithms that leverage the rich structure provided by convexity. Convexity of a smooth set or a function in a Euclidean space is defined by how it interacts with the standard differential structure in this space -- the Hessian of a convex function has to be positive semi-definite everywhere. However, in recent years, there is a growing demand to understand non-convexity and develop computational methods to optimize non-convex functions. Intriguingly, there is a type of non-convexity that disappears once one introduces a suitable differentiable structure and redefines convexity with respect to the straight lines, or {\em geodesics}, with respect to this structure. Such convexity is referred to as {\em geodesic convexity}. Interest in studying it arises due to recent reformulations of some non-convex problems as geodesically convex optimization problems over geodesically convex sets. Geodesics on manifolds have been extensively studied in various branches of Mathematics and Physics. However, unlike convex optimization, understanding geodesics and geodesic convexity from a computational point of view largely remains a mystery. The goal of this exposition is to introduce the first part of geodesic convex optimization -- geodesic convexity -- in a self-contained manner. We first present a variety of notions from differential and Riemannian geometry such as differentiation on manifolds, geodesics, and then introduce geodesic convexity. We conclude by showing that certain non-convex optimization problems such as computing the Brascamp-Lieb constant and the operator scaling problem have geodesically convex formulations. | Nisheeth K. Vishnoi |
| 2001.03241 | 43208561 | 2021-06-23 07:54:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2001.03241v2 | Network Geometry | Real networks are finite metric spaces. Yet the geometry induced by shortest path distances in a network is definitely not its only geometry. Other forms of network geometry are the geometry of latent spaces underlying many networks, and the effective geometry induced by dynamical processes in networks. These three approaches to network geometry are all intimately related, and all three of them have been found to be exceptionally efficient in discovering fractality, scale-invariance, self-similarity, and other forms of fundamental symmetries in networks. Network geometry is also of great utility in a variety of practical applications, ranging from the understanding how the brain works, to routing in the Internet. Here, we review the most important theoretical and practical developments dealing with these approaches to network geometry in the last two decades, and offer perspectives on future research directions and challenges in this novel frontier in the study of complexity. | Marian Boguna, Ivan Bonamassa, Manlio De Domenico, Shlomo Havlin, Dmitri Krioukov, M. Angeles Serrano |
| 2102.07542 | 868939 | 2021-07-04 08:07:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2102.07542v1 | High-Dimensional Gaussian Process Inference with Derivatives | Although it is widely known that Gaussian processes can be conditioned on observations of the gradient, this functionality is of limited use due to the prohibitive computational cost of $\mathcal{O}(N^3 D^3)$ in data points $N$ and dimension $D$. The dilemma of gradient observations is that a single one of them comes at the same cost as $D$ independent function evaluations, so the latter are often preferred. Careful scrutiny reveals, however, that derivative observations give rise to highly structured kernel Gram matrices for very general classes of kernels (inter alia, stationary kernels). We show that in the low-data regime $N<D$, the Gram matrix can be decomposed in a manner that reduces the cost of inference to $\mathcal{O}(N^2D + (N^2)^3)$ (i.e., linear in the number of dimensions) and, in special cases, to $\mathcal{O}(N^2D + N^3)$. This reduction in complexity opens up new use-cases for inference with gradients especially in the high-dimensional regime, where the information-to-cost ratio of gradient observations significantly increases. We demonstrate this potential in a variety of tasks relevant for machine learning, such as optimization and Hamiltonian Monte Carlo with predictive gradients. | Filip de Roos, Alexandra Gessner, Philipp Hennig |
| 1701.06794 | 844624 | 2021-07-10 10:42:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1701.06794v1 | Computations with p-adic numbers | This document contains the notes of a lecture I gave at the "Journ\'ees Nationales du Calcul Formel" (JNCF) on January 2017. The aim of the lecture was to discuss low-level algorithmics for p-adic numbers. It is divided into two main parts: first, we present various implementations of p-adic numbers and compare them and second, we introduce a general framework for studying precision issues and apply it in several concrete situations. | Xavier Caruso |
| 2104.06488 | 4268969 | 2021-07-13 06:09:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2104.06488v4 | Positive Energy Warp Drive from Hidden Geometric Structures | Warp drives in Einstein's general theory of relativity provide a unique mechanism for manned interstellar travel. It is well-known that the classical superluminal soliton spacetimes require negative energy densities, likely sourced by quantum processes of the uncertainty principle. It has even been claimed by few that negative energy densities are a requirement of superluminal motion. However, recent studies suggest this may not be the case. A general decomposition of the defining variables and the corresponding decomposition of the Eulerian energy are studied. A geometrical interpretation of the Eulerian energy is found, shedding new light on superluminal solitons generated by realistic energy distributions. With this new interpretation, it becomes a relatively simple matter to generate solitonic configurations, within a certain subclass, that respect the positive energy constraint. Using this newfound interpretation, a superluminal solitonic spacetime is presented that possesses positive semi-definite energy. A modest numerical analysis is carried out on a set of example configurations, finding total energy requirements four orders of magnitude smaller than the solar mass. Extraordinarily, the example configurations are generated by purely positive energy densities, a tremendous improvement on the classical configurations. The geometrical interpretation of the Eulerian energy thus opens new doors to generating realistic warp fields for laboratory study and potential future manned interstellar travel. | Shaun D. B. Fell, Lavinia Heisenberg |
| 2102.13459 | 2741402 | 2021-07-20 05:55:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2102.13459v2 | Geometrization of the local Langlands correspondence | Following the idea of [Far16], we develop the foundations of the geometric Langlands program on the Fargues--Fontaine curve. In particular, we define a category of $\ell$-adic sheaves on the stack $\mathrm{Bun}_G$ of $G$-bundles on the Fargues--Fontaine curve, prove a geometric Satake equivalence over the Fargues--Fontaine curve, and study the stack of $L$-parameters. As applications, we prove finiteness results for the cohomology of local Shimura varieties and general moduli spaces of local shtukas, and define $L$-parameters associated with irreducible smooth representations of $G(E)$, a map from the spectral Bernstein center to the Bernstein center, and the spectral action of the category of perfect complexes on the stack of $L$-parameters on the category of $\ell$-adic sheaves on $\mathrm{Bun}_G$. | Laurent Fargues, Peter Scholze |
| 2105.02782 | 505109 | 2021-09-15 06:50:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2105.02782v1 | The Homogenous Properties of Automated Market Makers | Automated market makers (AMM) have grown to obtain significant market share within the cryptocurrency ecosystem, resulting in a proliferation of new products pursuing exotic strategies for horizontal differentiation. Yet, their theoretical properties are curiously homogeneous when a set of basic assumptions are met. In this paper, we start by presenting a universal approach to deriving a formula for liquidity provisioning for AMMs. Next, we show that the constant function market maker and token swap market maker models are theoretically equivalent when liquidity reserves are uniform. Proceeding with an examination of AMM market microstructure, we show how non-linear price effect translates into slippage for traders and impermanent losses for liquidity providers. We proceed by showing how impermanent losses are a function of both volatility and market depth and discuss the implications of these findings within the context of the literature. | Johannes Rude Jensen, Mohsen Pourpouneh, Kurt Nielsen, Omri Ross |
| 2101.02778 | 1368269 | 2021-09-15 08:16:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2101.02778v1 | Dynamic Curves for Decentralized Autonomous Cryptocurrency Exchanges | One of the exciting recent developments in decentralized finance (DeFi) has been the development of decentralized cryptocurrency exchanges that can autonomously handle conversion between different cryptocurrencies. Decentralized exchange protocols such as Uniswap, Curve and other types of Automated Market Makers (AMMs) maintain a liquidity pool (LP) of two or more assets constrained to maintain at all times a mathematical relation to each other, defined by a given function or curve. Examples of such functions are the constant-sum and constant-product AMMs. Existing systems however suffer from several challenges. They require external arbitrageurs to restore the price of tokens in the pool to match the market price. Such activities can potentially drain resources from the liquidity pool. In particular, dramatic market price changes can result in low liquidity with respect to one or more of the assets and reduce the total value of the LP. We propose in this work a new approach to constructing the AMM by proposing the idea of dynamic curves. It utilizes input from a market price oracle to modify the mathematical relationship between the assets so that the pool price continuously and automatically adjusts to be identical to the market price. This approach eliminates arbitrage opportunities and, as we show through simulations, maintains liquidity in the LP for all assets and the total value of the LP over a wide range of market prices. | Bhaskar Krishnamachari, Qi Feng, Eugenio Grippo |
| 0809.4221 | 3286854 | 2021-09-25 09:20:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/0809.4221v7 | An elementary illustrated introduction to simplicial sets | This is an expository introduction to simplicial sets and simplicial homotopy theory with particular focus on relating the combinatorial aspects of the theory to their geometric/topological origins. It is intended to be accessible to students familiar with just the fundamentals of algebraic topology. | Greg Friedman |
| 2106.12575 | 2089057 | 2021-11-19 11:52:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2106.12575v3 | Weisfeiler and Lehman Go Cellular: CW Networks | Graph Neural Networks (GNNs) are limited in their expressive power, struggle with long-range interactions and lack a principled way to model higher-order structures. These problems can be attributed to the strong coupling between the computational graph and the input graph structure. The recently proposed Message Passing Simplicial Networks naturally decouple these elements by performing message passing on the clique complex of the graph. Nevertheless, these models can be severely constrained by the rigid combinatorial structure of Simplicial Complexes (SCs). In this work, we extend recent theoretical results on SCs to regular Cell Complexes, topological objects that flexibly subsume SCs and graphs. We show that this generalisation provides a powerful set of graph "lifting" transformations, each leading to a unique hierarchical message passing procedure. The resulting methods, which we collectively call CW Networks (CWNs), are strictly more powerful than the WL test and not less powerful than the 3-WL test. In particular, we demonstrate the effectiveness of one such scheme, based on rings, when applied to molecular graph problems. The proposed architecture benefits from provably larger expressivity than commonly used GNNs, principled modelling of higher-order signals and from compressing the distances between nodes. We demonstrate that our model achieves state-of-the-art results on a variety of molecular datasets. | Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liò, Guido Montúfar, Michael Bronstein |
| 2106.10934 | 1690210 | 2021-11-20 12:55:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2106.10934v2 | GRAND: Graph Neural Diffusion | We present Graph Neural Diffusion (GRAND) that approaches deep learning on graphs as a continuous diffusion process and treats Graph Neural Networks (GNNs) as discretisations of an underlying PDE. In our model, the layer structure and topology correspond to the discretisation choices of temporal and spatial operators. Our approach allows a principled development of a broad new class of GNNs that are able to address the common plights of graph learning models such as depth, oversmoothing, and bottlenecks. Key to the success of our models are stability with respect to perturbations in the data and this is addressed for both implicit and explicit discretisation schemes. We develop linear and nonlinear versions of GRAND, which achieve competitive results on many standard graph benchmarks. | Benjamin Paul Chamberlain, James Rowbottom, Maria Gorinova, Stefan Webb, Emanuele Rossi, Michael M. Bronstein |
| 2110.09443 | 2056256 | 2021-11-20 12:58:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2110.09443v1 | Beltrami Flow and Neural Diffusion on Graphs | We propose a novel class of graph neural networks based on the discretised Beltrami flow, a non-Euclidean diffusion PDE. In our model, node features are supplemented with positional encodings derived from the graph topology and jointly evolved by the Beltrami flow, producing simultaneously continuous feature learning and topology evolution. The resulting model generalises many popular graph neural networks and achieves state-of-the-art results on several benchmarks. | Benjamin Paul Chamberlain, James Rowbottom, Davide Eynard, Francesco Di Giovanni, Xiaowen Dong, Michael M Bronstein |
| 2008.04823 | 2354471 | 2021-11-23 07:41:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2008.04823v2 | Decomposition of Feynman Integrals by Multivariate Intersection Numbers | We present a detailed description of the recent idea for a direct decomposition of Feynman integrals onto a basis of master integrals by projections, as well as a direct derivation of the differential equations satisfied by the master integrals, employing multivariate intersection numbers. We discuss a recursive algorithm for the computation of multivariate intersection numbers and provide three different approaches for a direct decomposition of Feynman integrals, which we dub the straight decomposition, the bottom-up decomposition, and the top-down decomposition. These algorithms exploit the unitarity structure of Feynman integrals by computing intersection numbers supported on cuts, in various orders, thus showing the synthesis of the intersection-theory concepts with unitarity-based methods and integrand decomposition. We perform explicit computations to exemplify all of these approaches applied to Feynman integrals, paving a way towards potential applications to generic multi-loop integrals. | Hjalte Frellesvig, Federico Gasparotto, Stefano Laporta, Manoj K. Mandal, Pierpaolo Mastrolia, Luca Mattiazzi, Sebastian Mizera |
| 2111.13740 | 180300 | 2021-11-30 19:25:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2111.13740v1 | Replicating Monotonic Payoffs Without Oracles | In this paper, we show that any monotonic payoff can be replicated using only liquidity provider shares in constant function market makers (CFMMs), without the need for additional collateral or oracles. Such payoffs include cash-or-nothing calls and capped calls, among many others, and we give an explicit method for finding a trading function matching these payoffs. For example, this method provides an easy way to show that the trading function for maintaining a portfolio where 50% of the portfolio is allocated in one asset and 50% in the other is exactly the constant product market maker (e.g., Uniswap) from first principles. We additionally provide a simple formula for the total earnings of an arbitrageur who is arbitraging against these CFMMs. | Guillermo Angeris, Alex Evans, Tarun Chitra |
| 2112.03235 | 10248063 | 2021-12-07 09:18:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2112.03235v2 | Simulation Intelligence: Towards a New Generation of Scientific Methods | The original "Seven Motifs" set forth a roadmap of essential methods for the field of scientific computing, where a motif is an algorithmic method that captures a pattern of computation and data movement. We present the "Nine Motifs of Simulation Intelligence", a roadmap for the development and integration of the essential algorithms necessary for a merger of scientific computing, scientific simulation, and artificial intelligence. We call this merger simulation intelligence (SI), for short. We argue the motifs of simulation intelligence are interconnected and interdependent, much like the components within the layers of an operating system. Using this metaphor, we explore the nature of each layer of the simulation intelligence operating system stack (SI-stack) and the motifs therein: (1) Multi-physics and multi-scale modeling; (2) Surrogate modeling and emulation; (3) Simulation-based inference; (4) Causal modeling and inference; (5) Agent-based modeling; (6) Probabilistic programming; (7) Differentiable programming; (8) Open-ended optimization; (9) Machine programming. We believe coordinated efforts between motifs offers immense opportunity to accelerate scientific discovery, from solving inverse problems in synthetic biology and climate science, to directing nuclear energy experiments and predicting emergent behavior in socioeconomic settings. We elaborate on each layer of the SI-stack, detailing the state-of-art methods, presenting examples to highlight challenges and opportunities, and advocating for specific ways to advance the motifs and the synergies from their combinations. Advancing and integrating these technologies can enable a robust and efficient hypothesis-simulation-analysis type of scientific method, which we introduce with several use-cases for human-machine teaming and automated science. | Alexander Lavin, David Krakauer, Hector Zenil, Justin Gottschlich, Tim Mattson, Johann Brehmer, Anima Anandkumar, Sanjay Choudry, Kamil Rocki, Atılım Güneş Baydin, Carina Prunkl, Brooks Paige, Olexandr Isayev, Erik Peterson, Peter L. McMahon, Jakob Macke, Kyle Cranmer, Jiaxin Zhang, Haruko Wainwright, Adi Hanuka, Manuela Veloso, Samuel Assefa, Stephan Zheng, Avi Pfeffer |
| 2112.03460 | 1703509 | 2021-12-08 13:54:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2112.03460v2 | A Response to Economics as Gauge Theory | We provide an analysis of the recent work by Malaney-Weinstein on "Economics as Gauge Theory" presented on November 10, 2021 at the Money and Banking Workshop hosted by University of Chicago. In particular, we distill the technical mathematics used in their work into a form more suitable to a wider audience. Furthermore, we resolve the conjectures posed by Malaney-Weinstein, revealing that they provide no discernible value for the calculation of index numbers or rates of inflation. Our conclusion is that the main contribution of the Malaney-Weinstein work is that it provides a striking example of how to obscure simple concepts through an uneconomical use of gauge theory. | Timothy Nguyen |
| 2112.03270 | 595538 | 2021-12-08 15:58:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2112.03270v1 | Toward a Taxonomy of Trust for Probabilistic Machine Learning | Probabilistic machine learning increasingly informs critical decisions in medicine, economics, politics, and beyond. We need evidence to support that the resulting decisions are well-founded. To aid development of trust in these decisions, we develop a taxonomy delineating where trust in an analysis can break down: (1) in the translation of real-world goals to goals on a particular set of available training data, (2) in the translation of abstract goals on the training data to a concrete mathematical problem, (3) in the use of an algorithm to solve the stated mathematical problem, and (4) in the use of a particular code implementation of the chosen algorithm. We detail how trust can fail at each step and illustrate our taxonomy with two case studies: an analysis of the efficacy of microcredit and The Economist's predictions of the 2020 US presidential election. Finally, we describe a wide variety of methods that can be used to increase trust at each step of our taxonomy. The use of our taxonomy highlights steps where existing research work on trust tends to concentrate and also steps where establishing trust is particularly challenging. | Tamara Broderick, Andrew Gelman, Rachael Meager, Anna L. Smith, Tian Zheng |
| 2112.03178 | 2518532 | 2021-12-09 15:43:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2112.03178v1 | Player of Games | Games have a long history of serving as a benchmark for progress in artificial intelligence. Recently, approaches using search and learning have shown strong performance across a set of perfect information games, and approaches using game-theoretic reasoning and learning have shown strong performance for specific imperfect information poker variants. We introduce Player of Games, a general-purpose algorithm that unifies previous approaches, combining guided search, self-play learning, and game-theoretic reasoning. Player of Games is the first algorithm to achieve strong empirical performance in large perfect and imperfect information games -- an important step towards truly general algorithms for arbitrary environments. We prove that Player of Games is sound, converging to perfect play as available computation time and approximation capacity increases. Player of Games reaches strong performance in chess and Go, beats the strongest openly available agent in heads-up no-limit Texas hold'em poker (Slumbot), and defeats the state-of-the-art agent in Scotland Yard, an imperfect information game that illustrates the value of guided search, learning, and game-theoretic reasoning. | Martin Schmid, Matej Moravcik, Neil Burch, Rudolf Kadlec, Josh Davidson, Kevin Waugh, Nolan Bard, Finbarr Timbers, Marc Lanctot, Zach Holland, Elnaz Davoodi, Alden Christianson, Michael Bowling |
| 2111.11218 | 1014201 | 2021-12-10 17:01:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2111.11218v2 | Parallel Logic Programming: A Sequel | Multi-core and highly-connected architectures have become ubiquitous, and this has brought renewed interest in language-based approaches to the exploitation of parallelism. Since its inception, logic programming has been recognized as a programming paradigm with great potential for automated exploitation of parallelism. The comprehensive survey of the first twenty years of research in parallel logic programming, published in 2001, has served since as a fundamental reference to researchers and developers. The contents are quite valid today, but at the same time the field has continued evolving at a fast pace in the years that have followed. Many of these achievements and ongoing research have been driven by the rapid pace of technological innovation, that has led to advances such as very large clusters, the wide diffusion of multi-core processors, the game-changing role of general-purpose graphic processing units, and the ubiquitous adoption of cloud computing. This has been paralleled by significant advances within logic programming, such as tabling, more powerful static analysis and verification, the rapid growth of Answer Set Programming, and in general, more mature implementations and systems. This survey provides a review of the research in parallel logic programming covering the period since 2001, thus providing a natural continuation of the previous survey. The goal of the survey is to serve not only as a reference for researchers and developers of logic programming systems, but also as engaging reading for anyone interested in logic and as a useful source for researchers in parallel systems outside logic programming. Under consideration in Theory and Practice of Logic Programming (TPLP). | Agostino Dovier, Andrea Formisano, Gopal Gupta, Manuel V. Hermenegildo, Enrico Pontelli, Ricardo Rocha |
| 2111.14377 | 5260315 | 2021-12-14 18:06:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2111.14377v3 | Collective Intelligence for Deep Learning: A Survey of Recent Developments | In the past decade, we have witnessed the rise of deep learning to dominate the field of artificial intelligence. Advances in artificial neural networks alongside corresponding advances in hardware accelerators with large memory capacity, together with the availability of large datasets enabled practitioners to train and deploy sophisticated neural network models that achieve state-of-the-art performance on tasks across several fields spanning computer vision, natural language processing, and reinforcement learning. However, as these neural networks become bigger, more complex, and more widely used, fundamental problems with current deep learning models become more apparent. State-of-the-art deep learning models are known to suffer from issues that range from poor robustness, inability to adapt to novel task settings, to requiring rigid and inflexible configuration assumptions. Collective behavior, commonly observed in nature, tends to produce systems that are robust, adaptable, and have less rigid assumptions about the environment configuration. Collective intelligence, as a field, studies the group intelligence that emerges from the interactions of many individuals. Within this field, ideas such as self-organization, emergent behavior, swarm optimization, and cellular automata were developed to model and explain complex systems. It is therefore natural to see these ideas incorporated into newer deep learning methods. In this review, we will provide a historical context of neural network research's involvement with complex systems, and highlight several active areas in modern deep learning research that incorporate the principles of collective intelligence to advance its current capabilities. We hope this review can serve as a bridge between the complex systems and deep learning communities. | David Ha, Yujin Tang |
| 2110.02910 | 1394423 | 2021-12-15 18:34:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2110.02910v3 | Equivariant Subgraph Aggregation Networks | Message-passing neural networks (MPNNs) are the leading architecture for deep learning on graph-structured data, in large part due to their simplicity and scalability. Unfortunately, it was shown that these architectures are limited in their expressive power. This paper proposes a novel framework called Equivariant Subgraph Aggregation Networks (ESAN) to address this issue. Our main observation is that while two graphs may not be distinguishable by an MPNN, they often contain distinguishable subgraphs. Thus, we propose to represent each graph as a set of subgraphs derived by some predefined policy, and to process it using a suitable equivariant architecture. We develop novel variants of the 1-dimensional Weisfeiler-Leman (1-WL) test for graph isomorphism, and prove lower bounds on the expressiveness of ESAN in terms of these new WL variants. We further prove that our approach increases the expressive power of both MPNNs and more expressive architectures. Moreover, we provide theoretical results that describe how design choices such as the subgraph selection policy and equivariant neural architecture affect our architecture's expressive power. To deal with the increased computational cost, we propose a subgraph sampling scheme, which can be viewed as a stochastic version of our framework. A comprehensive set of experiments on real and synthetic datasets demonstrates that our framework improves the expressive power and overall performance of popular GNN architectures. | Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, Haggai Maron |
| 1902.02992 | 6951712 | 2021-12-16 17:52:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1902.02992v2 | A Wrapped Normal Distribution on Hyperbolic Space for Gradient-Based Learning | Hyperbolic space is a geometry that is known to be well-suited for representation learning of data with an underlying hierarchical structure. In this paper, we present a novel hyperbolic distribution called \textit{pseudo-hyperbolic Gaussian}, a Gaussian-like distribution on hyperbolic space whose density can be evaluated analytically and differentiated with respect to the parameters. Our distribution enables the gradient-based learning of the probabilistic models on hyperbolic space that could never have been considered before. Also, we can sample from this hyperbolic probability distribution without resorting to auxiliary means like rejection sampling. As applications of our distribution, we develop a hyperbolic-analog of variational autoencoder and a method of probabilistic word embedding on hyperbolic space. We demonstrate the efficacy of our distribution on various datasets including MNIST, Atari 2600 Breakout, and WordNet. | Yoshihiro Nagano, Shoichiro Yamaguchi, Yasuhiro Fujita, Masanori Koyama |
| 1808.08271 | 2322026 | 2021-12-18 08:31:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1808.08271v2 | An elementary introduction to information geometry | In this survey, we describe the fundamental differential-geometric structures of information manifolds, state the fundamental theorem of information geometry, and illustrate some use cases of these information manifolds in information sciences. The exposition is self-contained by concisely introducing the necessary concepts of differential geometry, but proofs are omitted for brevity. | Frank Nielsen |
| 2101.01162 | 1194847 | 2021-12-18 13:27:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2101.01162v1 | Transport information Bregman divergences | We study Bregman divergences in probability density space embedded with the $L^2$--Wasserstein metric. Several properties and dualities of transport Bregman divergences are provided. In particular, we derive the transport Kullback--Leibler (KL) divergence by a Bregman divergence of negative Boltzmann--Shannon entropy in $L^2$--Wasserstein space. We also derive analytical formulas and generalizations of transport KL divergence for one-dimensional probability densities and Gaussian families. | Wuchen Li |
| 1905.11027 | 737557 | 2021-12-18 13:37:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1905.11027v4 | A Geometric Modeling of Occam's Razor in Deep Learning | Why do deep neural networks (DNNs) benefit from very high dimensional parameter spaces? Their huge parameter complexities vs stunning performances in practice is all the more intriguing and not explainable using the standard theory of regular models. In this work, we propose a geometrically flavored information-theoretic approach to study this phenomenon. Namely, we introduce the locally varying dimensionality of the parameter space of neural network models by considering the number of significant dimensions of the Fisher information matrix, and model the parameter space as a manifold using the framework of singular semi-Riemannian geometry. We derive model complexity measures which yield short description lengths for deep neural network models based on their singularity analysis thus explaining the good performance of DNNs despite their large number of parameters. | Ke Sun, Frank Nielsen |
| 1709.10219 | 1379193 | 2021-12-18 13:46:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1709.10219v1 | Information Geometry Connecting Wasserstein Distance and Kullback-Leibler Divergence via the Entropy-Relaxed Transportation Problem | Two geometrical structures have been extensively studied for a manifold of probability distributions. One is based on the Fisher information metric, which is invariant under reversible transformations of random variables, while the other is based on the Wasserstein distance of optimal transportation, which reflects the structure of the distance between random variables. Here, we propose a new information-geometrical theory that is a unified framework connecting the Wasserstein distance and Kullback-Leibler (KL) divergence. We primarily considered a discrete case consisting of $n$ elements and studied the geometry of the probability simplex $S_{n-1}$, which is the set of all probability distributions over $n$ elements. The Wasserstein distance was introduced in $S_{n-1}$ by the optimal transportation of commodities from distribution ${\mathbf{p}}$ to distribution ${\mathbf{q}}$, where ${\mathbf{p}}$, ${\mathbf{q}} \in S_{n-1}$. We relaxed the optimal transportation by using entropy, which was introduced by Cuturi. The optimal solution was called the entropy-relaxed stochastic transportation plan. The entropy-relaxed optimal cost $C({\mathbf{p}}, {\mathbf{q}})$ was computationally much less demanding than the original Wasserstein distance but does not define a distance because it is not minimized at ${\mathbf{p}}={\mathbf{q}}$. To define a proper divergence while retaining the computational advantage, we first introduced a divergence function in the manifold $S_{n-1} \times S_{n-1}$ of optimal transportation plans. We fully explored the information geometry of the manifold of the optimal transportation plans and subsequently constructed a new one-parameter family of divergences in $S_{n-1}$ that are related to both the Wasserstein distance and the KL-divergence. | Shun-ichi Amari, Ryo Karakida, Masafumi Oizumi |
| 2010.08895 | 2436198 | 2021-12-25 09:42:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2010.08895v3 | Fourier Neural Operator for Parametric Partial Differential Equations | The classical development of neural networks has primarily focused on learning mappings between finite-dimensional Euclidean spaces. Recently, this has been generalized to neural operators that learn mappings between function spaces. For partial differential equations (PDEs), neural operators directly learn the mapping from any functional parametric dependence to the solution. Thus, they learn an entire family of PDEs, in contrast to classical methods which solve one instance of the equation. In this work, we formulate a new neural operator by parameterizing the integral kernel directly in Fourier space, allowing for an expressive and efficient architecture. We perform experiments on Burgers' equation, Darcy flow, and Navier-Stokes equation. The Fourier neural operator is the first ML-based method to successfully model turbulent flows with zero-shot super-resolution. It is up to three orders of magnitude faster compared to traditional PDE solvers. Additionally, it achieves superior accuracy compared to previous learning-based solvers under fixed resolution. | Zongyi Li, Nikola Kovachki, Kamyar Azizzadenesheli, Burigede Liu, Kaushik Bhattacharya, Andrew Stuart, Anima Anandkumar |
| 2108.08052 | 9246895 | 2022-01-06 13:55:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2108.08052v2 | Moser Flow: Divergence-based Generative Modeling on Manifolds | We are interested in learning generative models for complex geometries described via manifolds, such as spheres, tori, and other implicit surfaces. Current extensions of existing (Euclidean) generative models are restricted to specific geometries and typically suffer from high computational costs. We introduce Moser Flow (MF), a new class of generative models within the family of continuous normalizing flows (CNF). MF also produces a CNF via a solution to the change-of-variable formula, however differently from other CNF methods, its model (learned) density is parameterized as the source (prior) density minus the divergence of a neural network (NN). The divergence is a local, linear differential operator, easy to approximate and calculate on manifolds. Therefore, unlike other CNFs, MF does not require invoking or backpropagating through an ODE solver during training. Furthermore, representing the model density explicitly as the divergence of a NN rather than as a solution of an ODE facilitates learning high fidelity densities. Theoretically, we prove that MF constitutes a universal density approximator under suitable assumptions. Empirically, we demonstrate for the first time the use of flow models for sampling from general curved surfaces and achieve significant improvements in density estimation, sample quality, and training complexity over existing CNFs on challenging synthetic geometries and real-world benchmarks from the earth and climate sciences. | Noam Rozen, Aditya Grover, Maximilian Nickel, Yaron Lipman |
| 2201.01816 | 2414708 | 2022-01-10 15:35:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2201.01816v1 | Hidden Agenda: a Social Deduction Game with Diverse Learned Equilibria | A key challenge in the study of multiagent cooperation is the need for individual agents not only to cooperate effectively, but to decide with whom to cooperate. This is particularly critical in situations when other agents have hidden, possibly misaligned motivations and goals. Social deduction games offer an avenue to study how individuals might learn to synthesize potentially unreliable information about others, and elucidate their true motivations. In this work, we present Hidden Agenda, a two-team social deduction game that provides a 2D environment for studying learning agents in scenarios of unknown team alignment. The environment admits a rich set of strategies for both teams. Reinforcement learning agents trained in Hidden Agenda show that agents can learn a variety of behaviors, including partnering and voting without need for communication in natural language. | Kavya Kopparapu, Edgar A. Duéñez-Guzmán, Jayd Matyas, Alexander Sasha Vezhnevets, John P. Agapiou, Kevin R. McKee, Richard Everett, Janusz Marecki, Joel Z. Leibo, Thore Graepel |
| 2201.00650 | 15816157 | 2022-01-10 19:23:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2201.00650v2 | Deep Learning Interviews: Hundreds of fully solved job interview questions from a wide range of key topics in AI | The second edition of Deep Learning Interviews is home to hundreds of fully-solved problems, from a wide range of key topics in AI. It is designed to both rehearse interview or exam specific topics and provide machine learning MSc / PhD. students, and those awaiting an interview a well-organized overview of the field. The problems it poses are tough enough to cut your teeth on and to dramatically improve your skills-but they're framed within thought-provoking questions and engaging stories. That is what makes the volume so specifically valuable to students and job seekers: it provides them with the ability to speak confidently and quickly on any relevant topic, to answer technical questions clearly and correctly, and to fully understand the purpose and meaning of interview questions and answers. Those are powerful, indispensable advantages to have when walking into the interview room. The book's contents is a large inventory of numerous topics relevant to DL job interviews and graduate level exams. That places this work at the forefront of the growing trend in science to teach a core set of practical mathematical and computational skills. It is widely accepted that the training of every computer scientist must include the fundamental theorems of ML, and AI appears in the curriculum of nearly every university. This volume is designed as an excellent reference for graduates of such programs. | Shlomo Kashani, Amir Ivry |
| 2109.12510 | 1008182 | 2022-01-11 15:57:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2109.12510v1 | Towards Online Optimization for Power Grids | In this note, we discuss potential advantages in extending distributed optimization frameworks to enhance support for power grid operators managing an influx of online sequential decisions. First, we review the state-of-the-art distributed optimization frameworks for electric power systems, and explain how distributed algorithms deliver scalable solutions. Next, we introduce key concepts and paradigms for online optimization, and present a distributed online optimization framework highlighting important performance characteristics. Finally, we discuss the connection and difference between offline and online distributed optimization, showcasing the suitability of such optimization techniques for power grid applications. | Deming Yuan, Abhishek Bhardwaj, Ian Petersen, Elizabeth L. Ratnam, Guodong Shi |
| 1906.10064 | 1602029 | 2022-01-17 07:00:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1906.10064v1 | Variations on the Chebyshev-Lagrange Activation Function | We seek to improve the data efficiency of neural networks and present novel implementations of parameterized piece-wise polynomial activation functions. The parameters are the y-coordinates of n+1 Chebyshev nodes per hidden unit and Lagrangian interpolation between the nodes produces the polynomial on [-1, 1]. We show results for different methods of handling inputs outside [-1, 1] on synthetic datasets, finding significant improvements in capacity of expression and accuracy of interpolation in models that compute some form of linear extrapolation from either ends. We demonstrate competitive or state-of-the-art performance on the classification of images (MNIST and CIFAR-10) and minimally-correlated vectors (DementiaBank) when we replace ReLU or tanh with linearly extrapolated Chebyshev-Lagrange activations in deep residual architectures. | Yuchen Li, Frank Rudzicz, Jekaterina Novikova |
| 2106.05709 | 1205148 | 2022-01-19 15:15:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2106.05709v3 | Basins with tentacles | To explore basin geometry in high-dimensional dynamical systems, we consider a ring of identical Kuramoto oscillators. Many attractors coexist in this system; each is a twisted periodic orbit characterized by a winding number $q$, with basin size proportional to $e^{-kq^2}.$ We uncover the geometry behind this size distribution and find the basins are octopus-like, with nearly all their volume in the tentacles, not the head of the octopus (the ball-like region close to the attractor). We present a simple geometrical reason why basins with tentacles should be common in high-dimensional systems. | Yuanzhao Zhang, Steven H. Strogatz |
| 2201.12324 | 413584 | 2022-02-01 08:28:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2201.12324v1 | Optimal Transport Tools (OTT): A JAX Toolbox for all things Wasserstein | Optimal transport tools (OTT-JAX) is a Python toolbox that can solve optimal transport problems between point clouds and histograms. The toolbox builds on various JAX features, such as automatic and custom reverse mode differentiation, vectorization, just-in-time compilation and accelerators support. The toolbox covers elementary computations, such as the resolution of the regularized OT problem, and more advanced extensions, such as barycenters, Gromov-Wasserstein, low-rank solvers, estimation of convex maps, differentiable generalizations of quantiles and ranks, and approximate OT between Gaussian mixtures. The toolbox code is available at \texttt{https://github.com/ott-jax/ott} | Marco Cuturi, Laetitia Meng-Papaxanthos, Yingtao Tian, Charlotte Bunne, Geoff Davis, Olivier Teboul |
| 2201.12689 | 10353944 | 2022-02-02 06:45:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2201.12689v2 | Hyperbolic band theory through Higgs bundles | Hyperbolic lattices underlie a new form of quantum matter with potential applications to quantum computing and simulation and which, to date, have been engineered artificially. A corresponding hyperbolic band theory has emerged, extending 2-dimensional Euclidean band theory in a natural way to higher-genus configuration spaces. Attempts to develop the hyperbolic analogue of Bloch's theorem have revealed an intrinsic role for algebro-geometric moduli spaces, notably those of stable bundles on a curve. We expand this picture to include Higgs bundles, which enjoy natural interpretations in the context of band theory. First, their spectral data encodes a crystal lattice and momentum, providing a framework for symmetric hyperbolic crystals. Second, they act as a complex analogue of crystal momentum. As an application, we elicit a new perspective on Euclidean band theory. Finally, we speculate on potential interactions of hyperbolic band theory, facilitated by Higgs bundles, with other themes in mathematics and physics. | Elliot Kienzle, Steven Rayan |
| 2201.12689 | 10353944 | 2022-02-02 06:45:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2201.12689v2 | Hyperbolic band theory through Higgs bundles | Hyperbolic lattices underlie a new form of quantum matter with potential applications to quantum computing and simulation and which, to date, have been engineered artificially. A corresponding hyperbolic band theory has emerged, extending 2-dimensional Euclidean band theory in a natural way to higher-genus configuration spaces. Attempts to develop the hyperbolic analogue of Bloch's theorem have revealed an intrinsic role for algebro-geometric moduli spaces, notably those of stable bundles on a curve. We expand this picture to include Higgs bundles, which enjoy natural interpretations in the context of band theory. First, their spectral data encodes a crystal lattice and momentum, providing a framework for symmetric hyperbolic crystals. Second, they act as a complex analogue of crystal momentum. As an application, we elicit a new perspective on Euclidean band theory. Finally, we speculate on potential interactions of hyperbolic band theory, facilitated by Higgs bundles, with other themes in mathematics and physics. | Elliot Kienzle, Steven Rayan |
| 2111.12128 | 701344 | 2022-02-04 08:14:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2111.12128v3 | On the Unreasonable Effectiveness of Feature propagation in Learning on Graphs with Missing Node Features | While Graph Neural Networks (GNNs) have recently become the de facto standard for modeling relational data, they impose a strong assumption on the availability of the node or edge features of the graph. In many real-world applications, however, features are only partially available; for example, in social networks, age and gender are available only for a small subset of users. We present a general approach for handling missing features in graph machine learning applications that is based on minimization of the Dirichlet energy and leads to a diffusion-type differential equation on the graph. The discretization of this equation produces a simple, fast and scalable algorithm which we call Feature Propagation. We experimentally show that the proposed approach outperforms previous methods on seven common node-classification benchmarks and can withstand surprisingly high rates of missing features: on average we observe only around 4% relative accuracy drop when 99% of the features are missing. Moreover, it takes only 10 seconds to run on a graph with $\sim$2.5M nodes and $\sim$123M edges on a single GPU. | Emanuele Rossi, Henry Kenlay, Maria I. Gorinova, Benjamin Paul Chamberlain, Xiaowen Dong, Michael Bronstein |
| 2111.03794 | 5006469 | 2022-02-08 06:32:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2111.03794v2 | Physics-Informed Neural Operator for Learning Partial Differential Equations | In this paper, we propose physics-informed neural operators (PINO) that uses available data and/or physics constraints to learn the solution operator of a family of parametric Partial Differential Equation (PDE). This hybrid approach allows PINO to overcome the limitations of purely data-driven and physics-based methods. For instance, data-driven methods fail to learn when data is of limited quantity and/or quality, and physics-based approaches fail to optimize on challenging PDE constraints. By combining both data and PDE constraints, PINO overcomes all these challenges. Additionally, a unique property that PINO enjoys over other hybrid learning methods is its ability to incorporate data and PDE constraints at different resolutions. This allows us to combine coarse-resolution data, which is inexpensive to obtain from numerical solvers, with higher resolution PDE constraints, and the resulting PINO has no degradation in accuracy even on high-resolution test instances. This discretization-invariance property in PINO is due to neural-operator framework which learns mappings between function spaces and allows evaluation at different resolutions without the need for re-training. Moreover, PINO succeeds in the purely physics setting, where no data is available, while other approaches such as the Physics-Informed Neural Network (PINN) fail due to optimization challenges, e.g. in multi-scale dynamic systems such as Kolmogorov flows. This is because PINO learns the solution operator by optimizing PDE constraints on multiple instances while PINN optimizes PDE constraints of a single PDE instance. Further, in PINO, we incorporate the Fourier neural operator (FNO) architecture which achieves orders-of-magnitude speedup over numerical solvers and also allows us to compute explicit gradients on function spaces efficiently. | Zongyi Li, Hongkai Zheng, Nikola Kovachki, David Jin, Haoxuan Chen, Burigede Liu, Kamyar Azizzadenesheli, Anima Anandkumar |
| 2103.16034 | 134449 | 2022-02-08 07:31:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2103.16034v1 | TensorDiffEq: Scalable Multi-GPU Forward and Inverse Solvers for Physics Informed Neural Networks | Physics-Informed Neural Networks promise to revolutionize science and engineering practice, by introducing domain-aware deep machine learning models into scientific computation. Several software suites have emerged to make the implementation and usage of these architectures available to the research and industry communities. Here we introduce\linebreak TensorDiffEq, built on Tensorflow 2.x, which presents an intuitive Keras-like interface for problem domain definition, model definition, and solution of forward and inverse problems using physics-aware deep learning methods. TensorDiffEq takes full advantage of Tensorflow 2.x infrastructure for deployment on multiple GPUs, allowing the implementation of large high-dimensional and complex models. Simultaneously, TensorDiffEq supports the Keras API for custom neural network architecture definitions. In the case of smaller or simpler models, the package allows for rapid deployment on smaller-scale CPU platforms with negligible changes to the implementation scripts. We demonstrate the basic usage and capabilities of TensorDiffEq in solving forward, inverse, and data assimilation problems of varying sizes and levels of complexity. The source code is available at https://github.com/tensordiffeq. | Levi D. McClenny, Mulugeta A. Haile, Ulisses M. Braga-Neto |
| 2202.05008 | 650302 | 2022-02-11 06:37:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2202.05008v2 | EvoJAX: Hardware-Accelerated Neuroevolution | Evolutionary computation has been shown to be a highly effective method for training neural networks, particularly when employed at scale on CPU clusters. Recent work have also showcased their effectiveness on hardware accelerators, such as GPUs, but so far such demonstrations are tailored for very specific tasks, limiting applicability to other domains. We present EvoJAX, a scalable, general purpose, hardware-accelerated neuroevolution toolkit. Building on top of the JAX library, our toolkit enables neuroevolution algorithms to work with neural networks running in parallel across multiple TPU/GPUs. EvoJAX achieves very high performance by implementing the evolution algorithm, neural network and task all in NumPy, which is compiled just-in-time to run on accelerators. We provide extensible examples of EvoJAX for a wide range of tasks, including supervised learning, reinforcement learning and generative art. Since EvoJAX can find solutions to most of these tasks within minutes on a single accelerator, compared to hours or days when using CPUs, our toolkit can significantly shorten the iteration cycle of evolutionary computation experiments. EvoJAX is available at https://github.com/google/evojax | Yujin Tang, Yingtao Tian, David Ha |
| 2110.05357 | 707964 | 2022-02-16 06:55:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2110.05357v2 | Graph-Guided Network for Irregularly Sampled Multivariate Time Series | In many domains, including healthcare, biology, and climate science, time series are irregularly sampled with varying time intervals between successive readouts and different subsets of variables (sensors) observed at different time points. Here, we introduce RAINDROP, a graph neural network that embeds irregularly sampled and multivariate time series while also learning the dynamics of sensors purely from observational data. RAINDROP represents every sample as a separate sensor graph and models time-varying dependencies between sensors with a novel message passing operator. It estimates the latent sensor graph structure and leverages the structure together with nearby observations to predict misaligned readouts. This model can be interpreted as a graph neural network that sends messages over graphs that are optimized for capturing time-varying dependencies among sensors. We use RAINDROP to classify time series and interpret temporal dynamics on three healthcare and human activity datasets. RAINDROP outperforms state-of-the-art methods by up to 11.4% (absolute F1-score points), including techniques that deal with irregular sampling using fixed discretization and set functions. RAINDROP shows superiority in diverse setups, including challenging leave-sensor-out settings. | Xiang Zhang, Marko Zeman, Theodoros Tsiligkaridis, Marinka Zitnik |
| 2111.05803 | 801509 | 2022-02-24 14:01:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2111.05803v2 | Gradients are Not All You Need | Differentiable programming techniques are widely used in the community and are responsible for the machine learning renaissance of the past several decades. While these methods are powerful, they have limits. In this short report, we discuss a common chaos based failure mode which appears in a variety of differentiable circumstances, ranging from recurrent neural networks and numerical physics simulation to training learned optimizers. We trace this failure to the spectrum of the Jacobian of the system under study, and provide criteria for when a practitioner might expect this failure to spoil their differentiation based optimization algorithms. | Luke Metz, C. Daniel Freeman, Samuel S. Schoenholz, Tal Kachman |
| 2105.04906 | 873759 | 2022-03-02 07:31:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2105.04906v3 | VICReg: Variance-Invariance-Covariance Regularization for Self-Supervised Learning | Recent self-supervised methods for image representation learning are based on maximizing the agreement between embedding vectors from different views of the same image. A trivial solution is obtained when the encoder outputs constant vectors. This collapse problem is often avoided through implicit biases in the learning architecture, that often lack a clear justification or interpretation. In this paper, we introduce VICReg (Variance-Invariance-Covariance Regularization), a method that explicitly avoids the collapse problem with a simple regularization term on the variance of the embeddings along each dimension individually. VICReg combines the variance term with a decorrelation mechanism based on redundancy reduction and covariance regularization, and achieves results on par with the state of the art on several downstream tasks. In addition, we show that incorporating our new variance term into other methods helps stabilize the training and leads to performance improvements. | Adrien Bardes, Jean Ponce, Yann LeCun |
| 2107.07511 | 24797104 | 2022-03-02 14:32:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2107.07511v6 | A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification | Black-box machine learning models are now routinely used in high-risk settings, like medical diagnostics, which demand uncertainty quantification to avoid consequential model failures. Conformal prediction is a user-friendly paradigm for creating statistically rigorous uncertainty sets/intervals for the predictions of such models. Critically, the sets are valid in a distribution-free sense: they possess explicit, non-asymptotic guarantees even without distributional assumptions or model assumptions. One can use conformal prediction with any pre-trained model, such as a neural network, to produce sets that are guaranteed to contain the ground truth with a user-specified probability, such as 90%. It is easy-to-understand, easy-to-use, and general, applying naturally to problems arising in the fields of computer vision, natural language processing, deep reinforcement learning, and so on. This hands-on introduction is aimed to provide the reader a working understanding of conformal prediction and related distribution-free uncertainty quantification techniques with one self-contained document. We lead the reader through practical theory for and examples of conformal prediction and describe its extensions to complex machine learning tasks involving structured outputs, distribution shift, time-series, outliers, models that abstain, and more. Throughout, there are many explanatory illustrations, examples, and code samples in Python. With each code sample comes a Jupyter notebook implementing the method on a real-data example; the notebooks can be accessed and easily run using our codebase. | Anastasios N. Angelopoulos, Stephen Bates |
| 2101.02118 | 425739 | 2022-03-04 15:36:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2101.02118v2 | Do We Really Need Deep Learning Models for Time Series Forecasting? | Time series forecasting is a crucial task in machine learning, as it has a wide range of applications including but not limited to forecasting electricity consumption, traffic, and air quality. Traditional forecasting models rely on rolling averages, vector auto-regression and auto-regressive integrated moving averages. On the other hand, deep learning and matrix factorization models have been recently proposed to tackle the same problem with more competitive performance. However, one major drawback of such models is that they tend to be overly complex in comparison to traditional techniques. In this paper, we report the results of prominent deep learning models with respect to a well-known machine learning baseline, a Gradient Boosting Regression Tree (GBRT) model. Similar to the deep neural network (DNN) models, we transform the time series forecasting task into a window-based regression problem. Furthermore, we feature-engineered the input and output structure of the GBRT model, such that, for each training window, the target values are concatenated with external features, and then flattened to form one input instance for a multi-output GBRT model. We conducted a comparative study on nine datasets for eight state-of-the-art deep-learning models that were presented at top-level conferences in the last years. The results demonstrate that the window-based input transformation boosts the performance of a simple GBRT model to levels that outperform all state-of-the-art DNN models evaluated in this paper. | Shereen Elsayed, Daniela Thyssens, Ahmed Rashed, Hadi Samer Jomaa, Lars Schmidt-Thieme |
| 1904.01681 | 9103054 | 2022-03-14 14:12:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1904.01681v3 | Augmented Neural ODEs | We show that Neural Ordinary Differential Equations (ODEs) learn representations that preserve the topology of the input space and prove that this implies the existence of functions Neural ODEs cannot represent. To address these limitations, we introduce Augmented Neural ODEs which, in addition to being more expressive models, are empirically more stable, generalize better and have a lower computational cost than Neural ODEs. | Emilien Dupont, Arnaud Doucet, Yee Whye Teh |
| 2101.10037 | 5923804 | 2022-03-29 06:53:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2101.10037v1 | Optimizing Convergence for Iterative Learning of ARIMA for Stationary Time Series | Forecasting of time series in continuous systems becomes an increasingly relevant task due to recent developments in IoT and 5G. The popular forecasting model ARIMA is applied to a large variety of applications for decades. An online variant of ARIMA applies the Online Newton Step in order to learn the underlying process of the time series. This optimization method has pitfalls concerning the computational complexity and convergence. Thus, this work focuses on the computational less expensive Online Gradient Descent optimization method, which became popular for learning of neural networks in recent years. For the iterative training of such models, we propose a new approach combining different Online Gradient Descent learners (such as Adam, AMSGrad, Adagrad, Nesterov) to achieve fast convergence. The evaluation on synthetic data and experimental datasets show that the proposed approach outperforms the existing methods resulting in an overall lower prediction error. | Kevin Styp-Rekowski, Florian Schmidt, Odej Kao |
| 2202.08906 | 1976413 | 2022-04-02 09:37:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2202.08906v2 | ST-MoE: Designing Stable and Transferable Sparse Expert Models | Scale has opened new frontiers in natural language processing -- but at a high cost. In response, Mixture-of-Experts (MoE) and Switch Transformers have been proposed as an energy efficient path to even larger and more capable language models. But advancing the state-of-the-art across a broad set of natural language tasks has been hindered by training instabilities and uncertain quality during fine-tuning. Our work focuses on these issues and acts as a design guide. We conclude by scaling a sparse model to 269B parameters, with a computational cost comparable to a 32B dense encoder-decoder Transformer (Stable and Transferable Mixture-of-Experts or ST-MoE-32B). For the first time, a sparse model achieves state-of-the-art performance in transfer learning, across a diverse set of tasks including reasoning (SuperGLUE, ARC Easy, ARC Challenge), summarization (XSum, CNN-DM), closed book question answering (WebQA, Natural Questions), and adversarially constructed tasks (Winogrande, ANLI R3). | Barret Zoph, Irwan Bello, Sameer Kumar, Nan Du, Yanping Huang, Jeff Dean, Noam Shazeer, William Fedus |
| 2010.05840 | 28847206 | 2022-04-09 08:20:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2010.05840v2 | Cohomology fractals, Cannon-Thurston maps, and the geodesic flow | Cohomology fractals are images naturally associated to cohomology classes in hyperbolic three-manifolds. We generate these images for cusped, incomplete, and closed hyperbolic three-manifolds in real-time by ray-tracing to a fixed visual radius. We discovered cohomology fractals while attempting to illustrate Cannon-Thurston maps without using vector graphics; we prove a correspondence between these two, when the cohomology class is dual to a fibration. This allows us to verify our implementations by comparing our images of cohomology fractals to existing pictures of Cannon-Thurston maps. In a sequence of experiments, we explore the limiting behaviour of cohomology fractals as the visual radius increases. Motivated by these experiments, we prove that the values of the cohomology fractals are normally distributed, but with diverging standard deviations. In fact, the cohomology fractals do not converge to a function in the limit. Instead, we show that the limit is a distribution on the sphere at infinity, only depending on the manifold and cohomology class. | David Bachman, Matthias Goerner, Saul Schleimer, Henry Segerman |
| 2203.08890 | 8744025 | 2022-04-11 18:21:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2203.08890v1 | The Mathematics of Artificial Intelligence | We currently witness the spectacular success of artificial intelligence in both science and public life. However, the development of a rigorous mathematical foundation is still at an early stage. In this survey article, which is based on an invited lecture at the International Congress of Mathematicians 2022, we will in particular focus on the current "workhorse" of artificial intelligence, namely deep neural networks. We will present the main theoretical directions along with several exemplary results and discuss key open problems. | Gitta Kutyniok |
| 2204.06974 | 1033406 | 2022-04-20 13:45:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2204.06974v1 | Planting Undetectable Backdoors in Machine Learning Models | Given the computational cost and technical expertise required to train machine learning models, users may delegate the task of learning to a service provider. We show how a malicious learner can plant an undetectable backdoor into a classifier. On the surface, such a backdoored classifier behaves normally, but in reality, the learner maintains a mechanism for changing the classification of any input, with only a slight perturbation. Importantly, without the appropriate "backdoor key", the mechanism is hidden and cannot be detected by any computationally-bounded observer. We demonstrate two frameworks for planting undetectable backdoors, with incomparable guarantees. First, we show how to plant a backdoor in any model, using digital signature schemes. The construction guarantees that given black-box access to the original model and the backdoored version, it is computationally infeasible to find even a single input where they differ. This property implies that the backdoored model has generalization error comparable with the original model. Second, we demonstrate how to insert undetectable backdoors in models trained using the Random Fourier Features (RFF) learning paradigm or in Random ReLU networks. In this construction, undetectability holds against powerful white-box distinguishers: given a complete description of the network and the training data, no efficient distinguisher can guess whether the model is "clean" or contains a backdoor. Our construction of undetectable backdoors also sheds light on the related issue of robustness to adversarial examples. In particular, our construction can produce a classifier that is indistinguishable from an "adversarially robust" classifier, but where every input has an adversarial example! In summary, the existence of undetectable backdoors represent a significant theoretical roadblock to certifying adversarial robustness. | Shafi Goldwasser, Michael P. Kim, Vinod Vaikuntanathan, Or Zamir |
| 1907.00899 | 1401128 | 2022-04-21 10:51:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1907.00899v1 | Engineering Token Economy with System Modeling | Cryptocurrencies and blockchain networks have attracted tremendous attention from their volatile price movements and the promise of decentralization. However, most projects run on business narratives with no way to test and verify their assumptions and promises about the future. The complex nature of system dynamics within networked economies has rendered it difficult to reason about the growth and evolution of these networks. This paper drew concepts from differential games, classical control engineering, and stochastic dynamical system to come up with a framework and example to model, simulate, and engineer networked token economies. A model on a generalized token economy is proposed where miners provide service to a platform in exchange for a cryptocurrency and users consume service from the platform. Simulations of this model allow us to observe outcomes of complex dynamics and reason about the evolution of the system. Speculative price movements and engineered block rewards were then experimented to observe their impact on system dynamics and network-level goals. The model presented is necessarily limited so we conclude by exploring those limitations and outlining future research directions. | Zixuan Zhang |
| 2204.10923 | 820400 | 2022-04-29 07:18:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2204.10923v2 | You Only Linearize Once: Tangents Transpose to Gradients | Automatic differentiation (AD) is conventionally understood as a family of distinct algorithms, rooted in two "modes" -- forward and reverse -- which are typically presented (and implemented) separately. Can there be only one? Following up on the AD systems developed in the JAX and Dex projects, we formalize a decomposition of reverse-mode AD into (i) forward-mode AD followed by (ii) unzipping the linear and non-linear parts and then (iii) transposition of the linear part. To that end, we define a (substructurally) linear type system that can prove a class of functions are (algebraically) linear. Our main results are that forward-mode AD produces such linear functions, and that we can unzip and transpose any such linear function, conserving cost, size, and linearity. Composing these three transformations recovers reverse-mode AD. This decomposition also sheds light on checkpointing, which emerges naturally from a free choice in unzipping `let` expressions. As a corollary, checkpointing techniques are applicable to general-purpose partial evaluation, not just AD. We hope that our formalization will lead to a deeper understanding of automatic differentiation and that it will simplify implementations, by separating the concerns of differentiation proper from the concerns of gaining efficiency (namely, separating the derivative computation from the act of running it backward). | Alexey Radul, Adam Paszke, Roy Frostig, Matthew Johnson, Dougal Maclaurin |
| 2201.10085 | 2084899 | 2022-04-30 10:03:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2201.10085v2 | Dissipative Hamiltonian Neural Networks: Learning Dissipative and Conservative Dynamics Separately | Understanding natural symmetries is key to making sense of our complex and ever-changing world. Recent work has shown that neural networks can learn such symmetries directly from data using Hamiltonian Neural Networks (HNNs). But HNNs struggle when trained on datasets where energy is not conserved. In this paper, we ask whether it is possible to identify and decompose conservative and dissipative dynamics simultaneously. We propose Dissipative Hamiltonian Neural Networks (D-HNNs), which parameterize both a Hamiltonian and a Rayleigh dissipation function. Taken together, they represent an implicit Helmholtz decomposition which can separate dissipative effects such as friction from symmetries such as conservation of energy. We train our model to decompose a damped mass-spring system into its friction and inertial terms and then show that this decomposition can be used to predict dynamics for unseen friction coefficients. Then we apply our model to real world data including a large, noisy ocean current dataset where decomposing the velocity field yields useful scientific insights. | Andrew Sosanya, Sam Greydanus |
| 1806.07366 | 3990592 | 2022-05-02 10:52:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1806.07366v5 | Neural Ordinary Differential Equations | We introduce a new family of deep neural network models. Instead of specifying a discrete sequence of hidden layers, we parameterize the derivative of the hidden state using a neural network. The output of the network is computed using a black-box differential equation solver. These continuous-depth models have constant memory cost, adapt their evaluation strategy to each input, and can explicitly trade numerical precision for speed. We demonstrate these properties in continuous-depth residual networks and continuous-time latent variable models. We also construct continuous normalizing flows, a generative model that can train by maximum likelihood, without partitioning or ordering the data dimensions. For training, we show how to scalably backpropagate through any ODE solver, without access to its internal operations. This allows end-to-end training of ODEs within larger models. | Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, David Duvenaud |
| 2003.04630 | 2616562 | 2022-05-02 10:52:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2003.04630v2 | Lagrangian Neural Networks | Accurate models of the world are built upon notions of its underlying symmetries. In physics, these symmetries correspond to conservation laws, such as for energy and momentum. Yet even though neural network models see increasing use in the physical sciences, they struggle to learn these symmetries. In this paper, we propose Lagrangian Neural Networks (LNNs), which can parameterize arbitrary Lagrangians using neural networks. In contrast to models that learn Hamiltonians, LNNs do not require canonical coordinates, and thus perform well in situations where canonical momenta are unknown or difficult to compute. Unlike previous approaches, our method does not restrict the functional form of learned energies and will produce energy-conserving models for a variety of tasks. We test our approach on a double pendulum and a relativistic particle, demonstrating energy conservation where a baseline approach incurs dissipation and modeling relativity without canonical coordinates where a Hamiltonian approach fails. Finally, we show how this model can be applied to graphs and continuous systems using a Lagrangian Graph Network, and demonstrate it on the 1D wave equation. | Miles Cranmer, Sam Greydanus, Stephan Hoyer, Peter Battaglia, David Spergel, Shirley Ho |
| 2107.01188 | 2738845 | 2022-05-02 10:54:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2107.01188v2 | Combinatorial Optimization with Physics-Inspired Graph Neural Networks | Combinatorial optimization problems are pervasive across science and industry. Modern deep learning tools are poised to solve these problems at unprecedented scales, but a unifying framework that incorporates insights from statistical physics is still outstanding. Here we demonstrate how graph neural networks can be used to solve combinatorial optimization problems. Our approach is broadly applicable to canonical NP-hard problems in the form of quadratic unconstrained binary optimization problems, such as maximum cut, minimum vertex cover, maximum independent set, as well as Ising spin glasses and higher-order generalizations thereof in the form of polynomial unconstrained binary optimization problems. We apply a relaxation strategy to the problem Hamiltonian to generate a differentiable loss function with which we train the graph neural network and apply a simple projection to integer variables once the unsupervised training process has completed. We showcase our approach with numerical results for the canonical maximum cut and maximum independent set problems. We find that the graph neural network optimizer performs on par or outperforms existing solvers, with the ability to scale beyond the state of the art to problems with millions of variables. | Martin J. A. Schuetz, J. Kyle Brubaker, Helmut G. Katzgraber |
| 1910.03193 | 757987 | 2022-05-02 10:57:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1910.03193v3 | DeepONet: Learning nonlinear operators for identifying differential equations based on the universal approximation theorem of operators | While it is widely known that neural networks are universal approximators of continuous functions, a less known and perhaps more powerful result is that a neural network with a single hidden layer can approximate accurately any nonlinear continuous operator. This universal approximation theorem is suggestive of the potential application of neural networks in learning nonlinear operators from data. However, the theorem guarantees only a small approximation error for a sufficient large network, and does not consider the important optimization and generalization errors. To realize this theorem in practice, we propose deep operator networks (DeepONets) to learn operators accurately and efficiently from a relatively small dataset. A DeepONet consists of two sub-networks, one for encoding the input function at a fixed number of sensors $x_i, i=1,\dots,m$ (branch net), and another for encoding the locations for the output functions (trunk net). We perform systematic simulations for identifying two types of operators, i.e., dynamic systems and partial differential equations, and demonstrate that DeepONet significantly reduces the generalization error compared to the fully-connected networks. We also derive theoretically the dependence of the approximation error in terms of the number of sensors (where the input function is defined) as well as the input function type, and we verify the theorem with computational results. More importantly, we observe high-order error convergence in our computational tests, namely polynomial rates (from half order to fourth order) and even exponential convergence with respect to the training dataset size. | Lu Lu, Pengzhan Jin, George Em Karniadakis |
| 1910.12430 | 506137 | 2022-05-02 10:58:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1910.12430v1 | Differentiable Convex Optimization Layers | Recent work has shown how to embed differentiable optimization problems (that is, problems whose solutions can be backpropagated through) as layers within deep learning architectures. This method provides a useful inductive bias for certain problems, but existing software for differentiable optimization layers is rigid and difficult to apply to new settings. In this paper, we propose an approach to differentiating through disciplined convex programs, a subclass of convex optimization problems used by domain-specific languages (DSLs) for convex optimization. We introduce disciplined parametrized programming, a subset of disciplined convex programming, and we show that every disciplined parametrized program can be represented as the composition of an affine map from parameters to problem data, a solver, and an affine map from the solver's solution to a solution of the original problem (a new form we refer to as affine-solver-affine form). We then demonstrate how to efficiently differentiate through each of these components, allowing for end-to-end analytical differentiation through the entire convex program. We implement our methodology in version 1.1 of CVXPY, a popular Python-embedded DSL for convex optimization, and additionally implement differentiable layers for disciplined convex programs in PyTorch and TensorFlow 2.0. Our implementation significantly lowers the barrier to using convex optimization problems in differentiable programs. We present applications in linear machine learning models and in stochastic control, and we show that our layer is competitive (in execution time) compared to specialized differentiable solvers from past work. | Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, Zico Kolter |
| 2202.02435 | 4376865 | 2022-05-02 10:59:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2202.02435v1 | On Neural Differential Equations | The conjoining of dynamical systems and deep learning has become a topic of great interest. In particular, neural differential equations (NDEs) demonstrate that neural networks and differential equation are two sides of the same coin. Traditional parameterised differential equations are a special case. Many popular neural network architectures, such as residual networks and recurrent networks, are discretisations. NDEs are suitable for tackling generative problems, dynamical systems, and time series (particularly in physics, finance, ...) and are thus of interest to both modern machine learning and traditional mathematical modelling. NDEs offer high-capacity function approximation, strong priors on model space, the ability to handle irregular data, memory efficiency, and a wealth of available theory on both sides. This doctoral thesis provides an in-depth survey of the field. Topics include: neural ordinary differential equations (e.g. for hybrid neural/mechanistic modelling of physical systems); neural controlled differential equations (e.g. for learning functions of irregular time series); and neural stochastic differential equations (e.g. to produce generative models capable of representing complex stochastic dynamics, or sampling from complex high-dimensional distributions). Further topics include: numerical methods for NDEs (e.g. reversible differential equations solvers, backpropagation through differential equations, Brownian reconstruction); symbolic regression for dynamical systems (e.g. via regularised evolution); and deep implicit models (e.g. deep equilibrium models, differentiable optimisation). We anticipate this thesis will be of interest to anyone interested in the marriage of deep learning with dynamical systems, and hope it will provide a useful reference for the current state of the art. | Patrick Kidger |
| 1909.01377 | 856245 | 2022-05-02 11:11:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1909.01377v2 | Deep Equilibrium Models | We present a new approach to modeling sequential data: the deep equilibrium model (DEQ). Motivated by an observation that the hidden layers of many existing deep sequence models converge towards some fixed point, we propose the DEQ approach that directly finds these equilibrium points via root-finding. Such a method is equivalent to running an infinite depth (weight-tied) feedforward network, but has the notable advantage that we can analytically backpropagate through the equilibrium point using implicit differentiation. Using this approach, training and prediction in these networks require only constant memory, regardless of the effective "depth" of the network. We demonstrate how DEQs can be applied to two state-of-the-art deep sequence models: self-attention transformers and trellis networks. On large-scale language modeling tasks, such as the WikiText-103 benchmark, we show that DEQs 1) often improve performance over these state-of-the-art models (for similar parameter counts); 2) have similar computational requirements to existing models; and 3) vastly reduce memory consumption (often the bottleneck for training large sequence models), demonstrating an up-to 88% memory reduction in our experiments. The code is available at https://github.com/locuslab/deq . | Shaojie Bai, J. Zico Kolter, Vladlen Koltun |
| 1906.02152 | 1644222 | 2022-05-09 13:17:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1906.02152v3 | (In)Stability for the Blockchain: Deleveraging Spirals and Stablecoin Attacks | We develop a model of stable assets, including non-custodial stablecoins backed by cryptocurrencies. Such stablecoins are popular methods for bootstrapping price stability within public blockchain settings. We derive fundamental results about dynamics and liquidity in stablecoin markets, demonstrate that these markets face deleveraging feedback effects that cause illiquidity during crises and exacerbate collateral drawdown, and characterize stable dynamics of the system under particular conditions. The possibility of such `deleveraging spirals' was first predicted in the initial release of our paper in 2019 and later directly observed during the `Black Thursday' crisis in Dai in 2020. From these insights, we suggest design improvements that aim to improve long-term stability. We also introduce new attacks that exploit arbitrage-like opportunities around stablecoin liquidations. Using our model, we demonstrate that these can be profitable. These attacks may induce volatility in the `stable' asset and cause perverse incentives for miners, posing risks to blockchain consensus. A variant of such attacks also later occurred during Black Thursday, taking the form of mempool manipulation to clear Dai liquidation auctions at near zero prices, costing $8m. | Ariah Klages-Mundt, Andreea Minca |
| 2202.02296 | 736002 | 2022-05-11 06:45:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2202.02296v2 | Graph-Coupled Oscillator Networks | We propose Graph-Coupled Oscillator Networks (GraphCON), a novel framework for deep learning on graphs. It is based on discretizations of a second-order system of ordinary differential equations (ODEs), which model a network of nonlinear controlled and damped oscillators, coupled via the adjacency structure of the underlying graph. The flexibility of our framework permits any basic GNN layer (e.g. convolutional or attentional) as the coupling function, from which a multi-layer deep neural network is built up via the dynamics of the proposed ODEs. We relate the oversmoothing problem, commonly encountered in GNNs, to the stability of steady states of the underlying ODE and show that zero-Dirichlet energy steady states are not stable for our proposed ODEs. This demonstrates that the proposed framework mitigates the oversmoothing problem. Moreover, we prove that GraphCON mitigates the exploding and vanishing gradients problem to facilitate training of deep multi-layer GNNs. Finally, we show that our approach offers competitive performance with respect to the state-of-the-art on a variety of graph-based learning tasks. | T. Konstantin Rusch, Benjamin P. Chamberlain, James Rowbottom, Siddhartha Mishra, Michael M. Bronstein |
| 2202.04579 | 8091540 | 2022-05-11 06:45:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2202.04579v4 | Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs | Cellular sheaves equip graphs with a "geometrical" structure by assigning vector spaces and linear maps to nodes and edges. Graph Neural Networks (GNNs) implicitly assume a graph with a trivial underlying sheaf. This choice is reflected in the structure of the graph Laplacian operator, the properties of the associated diffusion equation, and the characteristics of the convolutional models that discretise this equation. In this paper, we use cellular sheaf theory to show that the underlying geometry of the graph is deeply linked with the performance of GNNs in heterophilic settings and their oversmoothing behaviour. By considering a hierarchy of increasingly general sheaves, we study how the ability of the sheaf diffusion process to achieve linear separation of the classes in the infinite time limit expands. At the same time, we prove that when the sheaf is non-trivial, discretised parametric diffusion processes have greater control than GNNs over their asymptotic behaviour. On the practical side, we study how sheaves can be learned from data. The resulting sheaf diffusion models have many desirable properties that address the limitations of classical graph diffusion equations (and corresponding GNN models) and obtain competitive results in heterophilic settings. Overall, our work provides new connections between GNNs and algebraic topology and would be of interest to both fields. | Cristian Bodnar, Francesco Di Giovanni, Benjamin Paul Chamberlain, Pietro Liò, Michael M. Bronstein |
| 2202.11356 | 1587719 | 2022-05-11 06:47:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2202.11356v1 | Preformer: Predictive Transformer with Multi-Scale Segment-wise Correlations for Long-Term Time Series Forecasting | Transformer-based methods have shown great potential in long-term time series forecasting. However, most of these methods adopt the standard point-wise self-attention mechanism, which not only becomes intractable for long-term forecasting since its complexity increases quadratically with the length of time series, but also cannot explicitly capture the predictive dependencies from contexts since the corresponding key and value are transformed from the same point. This paper proposes a predictive Transformer-based model called {\em Preformer}. Preformer introduces a novel efficient {\em Multi-Scale Segment-Correlation} mechanism that divides time series into segments and utilizes segment-wise correlation-based attention for encoding time series. A multi-scale structure is developed to aggregate dependencies at different temporal scales and facilitate the selection of segment length. Preformer further designs a predictive paradigm for decoding, where the key and value come from two successive segments rather than the same segment. In this way, if a key segment has a high correlation score with the query segment, its successive segment contributes more to the prediction of the query segment. Extensive experiments demonstrate that our Preformer outperforms other Transformer-based methods. | Dazhao Du, Bing Su, Zhewei Wei |
| 2202.11737 | 849633 | 2022-05-11 06:47:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2202.11737v3 | Renormalization Group Flow as Optimal Transport | We establish that Polchinski's equation for exact renormalization group flow is equivalent to the optimal transport gradient flow of a field-theoretic relative entropy. This provides a compelling information-theoretic formulation of the exact renormalization group, expressed in the language of optimal transport. A striking consequence is that a regularization of the relative entropy is in fact an RG monotone. We compute this monotone in several examples. Our results apply more broadly to other exact renormalization group flow equations, including widely used specializations of Wegner-Morris flow. Moreover, our optimal transport framework for RG allows us to reformulate RG flow as a variational problem. This enables new numerical techniques and establishes a systematic connection between neural network methods and RG flows of conventional field theories. | Jordan Cotler, Semon Rezchikov |
| 2104.04610 | 8778026 | 2022-05-11 12:22:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2104.04610v2 | Deep Time Series Forecasting with Shape and Temporal Criteria | This paper addresses the problem of multi-step time series forecasting for non-stationary signals that can present sudden changes. Current state-of-the-art deep learning forecasting methods, often trained with variants of the MSE, lack the ability to provide sharp predictions in deterministic and probabilistic contexts. To handle these challenges, we propose to incorporate shape and temporal criteria in the training objective of deep models. We define shape and temporal similarities and dissimilarities, based on a smooth relaxation of Dynamic Time Warping (DTW) and Temporal Distortion Index (TDI), that enable to build differentiable loss functions and positive semi-definite (PSD) kernels. With these tools, we introduce DILATE (DIstortion Loss including shApe and TimE), a new objective for deterministic forecasting, that explicitly incorporates two terms supporting precise shape and temporal change detection. For probabilistic forecasting, we introduce STRIPE++ (Shape and Time diverRsIty in Probabilistic forEcasting), a framework for providing a set of sharp and diverse forecasts, where the structured shape and time diversity is enforced with a determinantal point process (DPP) diversity loss. Extensive experiments and ablations studies on synthetic and real-world datasets confirm the benefits of leveraging shape and time features in time series forecasting. | Vincent Le Guen, Nicolas Thome |
| 1602.03505 | 248026 | 2022-05-17 10:04:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1602.03505v1 | Basel III capital surcharges for G-SIBs fail to control systemic risk and can cause pro-cyclical side effects | In addition to constraining bilateral exposures of financial institutions, there are essentially two options for future financial regulation of systemic risk (SR): First, financial regulation could attempt to reduce the financial fragility of global or domestic systemically important financial institutions (G-SIBs or D-SIBs), as for instance proposed in Basel III. Second, future financial regulation could attempt strengthening the financial system as a whole. This can be achieved by re-shaping the topology of financial networks. We use an agent-based model (ABM) of a financial system and the real economy to study and compare the consequences of these two options. By conducting three "computer experiments" with the ABM we find that re-shaping financial networks is more effective and efficient than reducing leverage. Capital surcharges for G-SIBs can reduce SR, but must be larger than those specified in Basel III in order to have a measurable impact. This can cause a loss of efficiency. Basel III capital surcharges for G-SIBs can have pro-cyclical side effects. | Sebastian Poledna, Olaf Bochmann, Stefan Thurner |
| 2201.03626 | 328524 | 2022-05-20 07:14:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2201.03626v1 | Ribbon concordance of knots is a partial order | In this note we show that ribbon concordance forms a partial ordering on the set of knots, answering a question of Gordon. The proof makes use of representation varieties of the knot groups to $SO(N)$ and relations between them induced by a ribbon concordance. | Ian Agol |
| 2111.14522 | 3932102 | 2022-05-23 09:50:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2111.14522v3 | Understanding over-squashing and bottlenecks on graphs via curvature | Most graph neural networks (GNNs) use the message passing paradigm, in which node features are propagated on the input graph. Recent works pointed to the distortion of information flowing from distant nodes as a factor limiting the efficiency of message passing for tasks relying on long-distance interactions. This phenomenon, referred to as 'over-squashing', has been heuristically attributed to graph bottlenecks where the number of $k$-hop neighbors grows rapidly with $k$. We provide a precise description of the over-squashing phenomenon in GNNs and analyze how it arises from bottlenecks in the graph. For this purpose, we introduce a new edge-based combinatorial curvature and prove that negatively curved edges are responsible for the over-squashing issue. We also propose and experimentally test a curvature-based graph rewiring method to alleviate the over-squashing. | Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, Michael M. Bronstein |
| 2202.07643 | 3630007 | 2022-05-24 06:39:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2202.07643v2 | Lie Point Symmetry Data Augmentation for Neural PDE Solvers | Neural networks are increasingly being used to solve partial differential equations (PDEs), replacing slower numerical solvers. However, a critical issue is that neural PDE solvers require high-quality ground truth data, which usually must come from the very solvers they are designed to replace. Thus, we are presented with a proverbial chicken-and-egg problem. In this paper, we present a method, which can partially alleviate this problem, by improving neural PDE solver sample complexity -- Lie point symmetry data augmentation (LPSDA). In the context of PDEs, it turns out that we are able to quantitatively derive an exhaustive list of data transformations, based on the Lie point symmetry group of the PDEs in question, something not possible in other application areas. We present this framework and demonstrate how it can easily be deployed to improve neural PDE solver sample complexity by an order of magnitude. | Johannes Brandstetter, Max Welling, Daniel E. Worrall |
| 2202.03376 | 11372160 | 2022-05-24 06:39:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2202.03376v3 | Message Passing Neural PDE Solvers | The numerical solution of partial differential equations (PDEs) is difficult, having led to a century of research so far. Recently, there have been pushes to build neural--numerical hybrid solvers, which piggy-backs the modern trend towards fully end-to-end learned systems. Most works so far can only generalize over a subset of properties to which a generic solver would be faced, including: resolution, topology, geometry, boundary conditions, domain discretization regularity, dimensionality, etc. In this work, we build a solver, satisfying these properties, where all the components are based on neural message passing, replacing all heuristically designed components in the computation graph with backprop-optimized neural function approximators. We show that neural message passing solvers representationally contain some classical methods, such as finite differences, finite volumes, and WENO schemes. In order to encourage stability in training autoregressive models, we put forward a method that is based on the principle of zero-stability, posing stability as a domain adaptation problem. We validate our method on various fluid-like flow problems, demonstrating fast, stable, and accurate performance across different domain topologies, equation parameters, discretizations, etc., in 1D and 2D. | Johannes Brandstetter, Daniel Worrall, Max Welling |
| 2111.10315 | 509557 | 2022-05-24 15:21:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2111.10315v2 | Compositional Thermostatics | We define a thermostatic system to be a convex space of states together with a concave function sending each state to its entropy, which is an extended real number. This definition applies to classical thermodynamics, classical statistical mechanics, quantum statistical mechanics, and also generalized probabilistic theories of the sort studied in quantum foundations. It also allows us to treat a heat bath as a thermostatic system on an equal footing with any other. We construct an operad whose operations are convex relations from a product of convex spaces to a single convex space, and prove that thermostatic systems are algebras of this operad. This gives a general, rigorous formalism for combining thermostatic systems, which captures the fact that such systems maximize entropy subject to whatever constraints are imposed upon them. | John C. Baez, Owen Lynch, Joe Moeller |
| 2206.03992 | 1705761 | 2022-06-09 14:18:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2206.03992v1 | Neural Diffusion Processes | Gaussian processes provide an elegant framework for specifying prior and posterior distributions over functions. They are, however, also computationally expensive, and limited by the expressivity of their covariance function. We propose Neural Diffusion Processes (NDPs), a novel approach based upon diffusion models, that learn to sample from distributions over functions. Using a novel attention block, we can incorporate properties of stochastic processes, such as exchangeability, directly into the NDP's architecture. We empirically show that NDPs are able to capture functional distributions that are close to the true Bayesian posterior of a Gaussian process. This enables a variety of downstream tasks, including hyperparameter marginalisation and Bayesian optimisation. | Vincent Dutordoir, Alan Saul, Zoubin Ghahramani, Fergus Simpson |
| 2102.07835 | 791920 | 2022-06-10 14:06:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2102.07835v4 | Topological Graph Neural Networks | Graph neural networks (GNNs) are a powerful architecture for tackling graph learning tasks, yet have been shown to be oblivious to eminent substructures such as cycles. We present TOGL, a novel layer that incorporates global topological information of a graph using persistent homology. TOGL can be easily integrated into any type of GNN and is strictly more expressive (in terms the Weisfeiler--Lehman graph isomorphism test) than message-passing GNNs. Augmenting GNNs with TOGL leads to improved predictive performance for graph and node classification tasks, both on synthetic data sets, which can be classified by humans using their topology but not by ordinary GNNs, and on real-world data. | Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, Karsten Borgwardt |
| 1908.02591 | 7483813 | 2022-06-17 13:36:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1908.02591v1 | Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics | Anti-money laundering (AML) regulations play a critical role in safeguarding financial systems, but bear high costs for institutions and drive financial exclusion for those on the socioeconomic and international margins. The advent of cryptocurrency has introduced an intriguing paradox: pseudonymity allows criminals to hide in plain sight, but open data gives more power to investigators and enables the crowdsourcing of forensic analysis. Meanwhile advances in learning algorithms show great promise for the AML toolkit. In this workshop tutorial, we motivate the opportunity to reconcile the cause of safety with that of financial inclusion. We contribute the Elliptic Data Set, a time series graph of over 200K Bitcoin transactions (nodes), 234K directed payment flows (edges), and 166 node features, including ones based on non-public data; to our knowledge, this is the largest labelled transaction data set publicly available in any cryptocurrency. We share results from a binary classification task predicting illicit transactions using variations of Logistic Regression (LR), Random Forest (RF), Multilayer Perceptrons (MLP), and Graph Convolutional Networks (GCN), with GCN being of special interest as an emergent new method for capturing relational information. The results show the superiority of Random Forest (RF), but also invite algorithmic work to combine the respective powers of RF and graph methods. Lastly, we consider visualization for analysis and explainability, which is difficult given the size and dynamism of real-world transaction graphs, and we offer a simple prototype capable of navigating the graph and observing model performance on illicit activity over time. With this tutorial and data set, we hope to a) invite feedback in support of our ongoing inquiry, and b) inspire others to work on this societally important challenge. | Mark Weber, Giacomo Domeniconi, Jie Chen, Daniel Karl I. Weidele, Claudio Bellei, Tom Robinson, Charles E. Leiserson |
| 1908.02591 | 7483813 | 2022-06-17 13:36:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1908.02591v1 | Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics | Anti-money laundering (AML) regulations play a critical role in safeguarding financial systems, but bear high costs for institutions and drive financial exclusion for those on the socioeconomic and international margins. The advent of cryptocurrency has introduced an intriguing paradox: pseudonymity allows criminals to hide in plain sight, but open data gives more power to investigators and enables the crowdsourcing of forensic analysis. Meanwhile advances in learning algorithms show great promise for the AML toolkit. In this workshop tutorial, we motivate the opportunity to reconcile the cause of safety with that of financial inclusion. We contribute the Elliptic Data Set, a time series graph of over 200K Bitcoin transactions (nodes), 234K directed payment flows (edges), and 166 node features, including ones based on non-public data; to our knowledge, this is the largest labelled transaction data set publicly available in any cryptocurrency. We share results from a binary classification task predicting illicit transactions using variations of Logistic Regression (LR), Random Forest (RF), Multilayer Perceptrons (MLP), and Graph Convolutional Networks (GCN), with GCN being of special interest as an emergent new method for capturing relational information. The results show the superiority of Random Forest (RF), but also invite algorithmic work to combine the respective powers of RF and graph methods. Lastly, we consider visualization for analysis and explainability, which is difficult given the size and dynamism of real-world transaction graphs, and we offer a simple prototype capable of navigating the graph and observing model performance on illicit activity over time. With this tutorial and data set, we hope to a) invite feedback in support of our ongoing inquiry, and b) inspire others to work on this societally important challenge. | Mark Weber, Giacomo Domeniconi, Jie Chen, Daniel Karl I. Weidele, Claudio Bellei, Tom Robinson, Charles E. Leiserson |
| 2001.00888 | 1033120 | 2022-06-21 15:23:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2001.00888v4 | Towards Scalable Dataframe Systems | Dataframes are a popular abstraction to represent, prepare, and analyze data. Despite the remarkable success of dataframe libraries in Rand Python, dataframes face performance issues even on moderately large datasets. Moreover, there is significant ambiguity regarding dataframe semantics. In this paper we lay out a vision and roadmap for scalable dataframe systems. To demonstrate the potential in this area, we report on our experience building MODIN, a scaled-up implementation of the most widely-used and complex dataframe API today, Python's pandas. With pandas as a reference, we propose a simple data model and algebra for dataframes to ground discussion in the field. Given this foundation, we lay out an agenda of open research opportunities where the distinct features of dataframes will require extending the state of the art in many dimensions of data management. We discuss the implications of signature data-frame features including flexible schemas, ordering, row/column equivalence, and data/metadata fluidity, as well as the piecemeal, trial-and-error-based approach to interacting with dataframes. | Devin Petersohn, Stephen Macke, Doris Xin, William Ma, Doris Lee, Xiangxi Mo, Joseph E. Gonzalez, Joseph M. Hellerstein, Anthony D. Joseph, Aditya Parameswaran |
| 2206.11267 | 3765347 | 2022-06-27 07:49:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2206.11267v1 | Neural Implicit Manifold Learning for Topology-Aware Generative Modelling | Natural data observed in $\mathbb{R}^n$ is often constrained to an $m$-dimensional manifold $\mathcal{M}$, where $m < n$. Current generative models represent this manifold by mapping an $m$-dimensional latent variable through a neural network $f_\theta: \mathbb{R}^m \to \mathbb{R}^n$. Such procedures, which we call pushforward models, incur a straightforward limitation: manifolds cannot in general be represented with a single parameterization, meaning that attempts to do so will incur either computational instability or the inability to learn probability densities within the manifold. To remedy this problem, we propose to model $\mathcal{M}$ as a neural implicit manifold: the set of zeros of a neural network. To learn the data distribution within $\mathcal{M}$, we introduce constrained energy-based models, which use a constrained variant of Langevin dynamics to train and sample within the learned manifold. The resulting model can be manipulated with an arithmetic of manifolds which allows practitioners to take unions and intersections of model manifolds. In experiments on synthetic and natural data, we show that constrained EBMs can learn manifold-supported distributions with complex topologies more accurately than pushforward models. | Brendan Leigh Ross, Gabriel Loaiza-Ganem, Anthony L. Caterini, Jesse C. Cresswell |
| 2206.13446 | 3129780 | 2022-06-29 06:51:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2206.13446v1 | Pen and Paper Exercises in Machine Learning | This is a collection of (mostly) pen-and-paper exercises in machine learning. The exercises are on the following topics: linear algebra, optimisation, directed graphical models, undirected graphical models, expressive power of graphical models, factor graphs and message passing, inference for hidden Markov models, model-based learning (including ICA and unnormalised models), sampling and Monte-Carlo integration, and variational inference. | Michael U. Gutmann |
| 1506.08903 | 1095613 | 2022-07-03 10:30:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1506.08903v7 | A roadmap for the computation of persistent homology | Persistent homology (PH) is a method used in topological data analysis (TDA) to study qualitative features of data that persist across multiple scales. It is robust to perturbations of input data, independent of dimensions and coordinates, and provides a compact representation of the qualitative features of the input. The computation of PH is an open area with numerous important and fascinating challenges. The field of PH computation is evolving rapidly, and new algorithms and software implementations are being updated and released at a rapid pace. The purposes of our article are to (1) introduce theory and computational methods for PH to a broad range of computational scientists and (2) provide benchmarks of state-of-the-art implementations for the computation of PH. We give a friendly introduction to PH, navigate the pipeline for the computation of PH with an eye towards applications, and use a range of synthetic and real-world data sets to evaluate currently available open-source implementations for the computation of PH. Based on our benchmarking, we indicate which algorithms and implementations are best suited to different types of data sets. In an accompanying tutorial, we provide guidelines for the computation of PH. We make publicly available all scripts that we wrote for the tutorial, and we make available the processed version of the data sets used in the benchmarking. | Nina Otter, Mason A. Porter, Ulrike Tillmann, Peter Grindrod, Heather A. Harrington |
| 1506.08903 | 1095613 | 2022-07-03 10:30:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1506.08903v7 | A roadmap for the computation of persistent homology | Persistent homology (PH) is a method used in topological data analysis (TDA) to study qualitative features of data that persist across multiple scales. It is robust to perturbations of input data, independent of dimensions and coordinates, and provides a compact representation of the qualitative features of the input. The computation of PH is an open area with numerous important and fascinating challenges. The field of PH computation is evolving rapidly, and new algorithms and software implementations are being updated and released at a rapid pace. The purposes of our article are to (1) introduce theory and computational methods for PH to a broad range of computational scientists and (2) provide benchmarks of state-of-the-art implementations for the computation of PH. We give a friendly introduction to PH, navigate the pipeline for the computation of PH with an eye towards applications, and use a range of synthetic and real-world data sets to evaluate currently available open-source implementations for the computation of PH. Based on our benchmarking, we indicate which algorithms and implementations are best suited to different types of data sets. In an accompanying tutorial, we provide guidelines for the computation of PH. We make publicly available all scripts that we wrote for the tutorial, and we make available the processed version of the data sets used in the benchmarking. | Nina Otter, Mason A. Porter, Ulrike Tillmann, Peter Grindrod, Heather A. Harrington |
| 1701.06081 | 652608 | 2022-07-04 14:18:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1701.06081v1 | Topology data analysis of critical transitions in financial networks | We develop a topology data analysis-based method to detect early signs for critical transitions in financial data. From the time-series of multiple stock prices, we build time-dependent correlation networks, which exhibit topological structures. We compute the persistent homology associated to these structures in order to track the changes in topology when approaching a critical transition. As a case study, we investigate a portfolio of stocks during a period prior to the US financial crisis of 2007-2008, and show the presence of early signs of the critical transition. | Marian Gidea |
| 1612.03554 | 1890723 | 2022-07-04 14:21:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1612.03554v4 | Modeling the spread of the Zika virus using topological data analysis | Zika virus (ZIKV), a disease spread primarily through the Aedes aegypti mosquito, was identified in Brazil in 2015 and was declared a global health emergency by the World Health Organization (WHO). Epidemiologists often use common state-level attributes such as population density and temperature to determine the spread of disease. By applying techniques from topological data analysis, we believe that epidemiologists will be able to better predict how ZIKV will spread. We use the Vietoris-Rips filtration on high-density mosquito locations in Brazil to create simplicial complexes, from which we extract homology group generators. Previously epidemiologists have not relied on topological data analysis to model disease spread. Evaluating our model on ZIKV case data in the states of Brazil demonstrates the value of these techniques for the improved assessment of vector-borne diseases. | Derek Lo, Briton Park |
| 1501.00179 | 933800 | 2022-07-05 08:50:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1501.00179v3 | A persistence landscapes toolbox for topological statistics | Topological data analysis provides a multiscale description of the geometry and topology of quantitative data. The persistence landscape is a topological summary that can be easily combined with tools from statistics and machine learning. We give efficient algorithms for calculating persistence landscapes, their averages, and distances between such averages. We discuss an implementation of these algorithms and some related procedures. These are intended to facilitate the combination of statistics and machine learning with topological data analysis. We present an experiment showing that the low-dimensional persistence landscapes of points sampled from spheres (and boxes) of varying dimensions differ. | Peter Bubenik, Pawel Dlotko |
| 2111.00254 | 131327 | 2022-07-05 09:21:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2111.00254v1 | Equinox: neural networks in JAX via callable PyTrees and filtered transformations | JAX and PyTorch are two popular Python autodifferentiation frameworks. JAX is based around pure functions and functional programming. PyTorch has popularised the use of an object-oriented (OO) class-based syntax for defining parameterised functions, such as neural networks. That this seems like a fundamental difference means current libraries for building parameterised functions in JAX have either rejected the OO approach entirely (Stax) or have introduced OO-to-functional transformations, multiple new abstractions, and been limited in the extent to which they integrate with JAX (Flax, Haiku, Objax). Either way this OO/functional difference has been a source of tension. Here, we introduce `Equinox', a small neural network library showing how a PyTorch-like class-based approach may be admitted without sacrificing JAX-like functional programming. We provide two main ideas. One: parameterised functions are themselves represented as `PyTrees', which means that the parameterisation of a function is transparent to the JAX framework. Two: we filter a PyTree to isolate just those components that should be treated when transforming (`jit', `grad' or `vmap'-ing) a higher-order function of a parameterised function -- such as a loss function applied to a model. Overall Equinox resolves the above tension without introducing any new programmatic abstractions: only PyTrees and transformations, just as with regular JAX. Equinox is available at \url{https://github.com/patrick-kidger/equinox}. | Patrick Kidger, Cristian Garcia |
| 2203.02540 | 5025599 | 2022-07-11 07:36:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2203.02540v5 | Evolving symbolic density functionals | Systematic development of accurate density functionals has been a decades-long challenge for scientists. Despite the emerging application of machine learning (ML) in approximating functionals, the resulting ML functionals usually contain more than tens of thousands parameters, which makes a huge gap in the formulation with the conventional human-designed symbolic functionals. We propose a new framework, Symbolic Functional Evolutionary Search (SyFES), that automatically constructs accurate functionals in the symbolic form, which is more explainable to humans, cheaper to evaluate, and easier to integrate to existing density functional theory codes than other ML functionals. We first show that without prior knowledge, SyFES reconstructed a known functional from scratch. We then demonstrate that evolving from an existing functional $\omega$B97M-V, SyFES found a new functional, GAS22 (Google Accelerated Science 22), that performs better for the majority of molecular types in the test set of Main Group Chemistry Database (MGCDB84). Our framework opens a new direction in leveraging computing power for the systematic development of symbolic density functionals. | He Ma, Arunachalam Narayanaswamy, Patrick Riley, Li Li |
| 1906.00722 | 6690083 | 2022-07-12 07:50:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1906.00722v5 | Topological Autoencoders | We propose a novel approach for preserving topological structures of the input space in latent representations of autoencoders. Using persistent homology, a technique from topological data analysis, we calculate topological signatures of both the input and latent space to derive a topological loss term. Under weak theoretical assumptions, we construct this loss in a differentiable manner, such that the encoding learns to retain multi-scale connectivity information. We show that our approach is theoretically well-founded and that it exhibits favourable latent representations on a synthetic manifold as well as on real-world image data sets, while preserving low reconstruction errors. | Michael Moor, Max Horn, Bastian Rieck, Karsten Borgwardt |
| 1901.08991 | 2197793 | 2022-07-12 07:52:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1901.08991v2 | Diffusion Variational Autoencoders | A standard Variational Autoencoder, with a Euclidean latent space, is structurally incapable of capturing topological properties of certain datasets. To remove topological obstructions, we introduce Diffusion Variational Autoencoders with arbitrary manifolds as a latent space. A Diffusion Variational Autoencoder uses transition kernels of Brownian motion on the manifold. In particular, it uses properties of the Brownian motion to implement the reparametrization trick and fast approximations to the KL divergence. We show that the Diffusion Variational Autoencoder is capable of capturing topological properties of synthetic datasets. Additionally, we train MNIST on spheres, tori, projective spaces, SO(3), and a torus embedded in R3. Although a natural dataset like MNIST does not have latent variables with a clear-cut topological structure, training it on a manifold can still highlight topological and geometrical properties. | Luis A. Pérez Rey, Vlado Menkovski, Jacobus W. Portegies |
| 2201.12843 | 699177 | 2022-07-12 08:35:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2201.12843v4 | Graph Representation Learning via Aggregation Enhancement | Graph neural networks (GNNs) have become a powerful tool for processing graph-structured data but still face challenges in effectively aggregating and propagating information between layers, which limits their performance. We tackle this problem with the kernel regression (KR) approach, using KR loss as the primary loss in self-supervised settings or as a regularization term in supervised settings. We show substantial performance improvements compared to state-of-the-art in both scenarios on multiple transductive and inductive node classification datasets, especially for deep networks. As opposed to mutual information (MI), KR loss is convex and easy to estimate in high-dimensional cases, even though it indirectly maximizes the MI between its inputs. Our work highlights the potential of KR to advance the field of graph representation learning and enhance the performance of GNNs. The code to reproduce our experiments is available at https://github.com/Anonymous1252022/KR_for_GNNs | Maxim Fishman, Chaim Baskin, Evgenii Zheltonozhskii, Almog David, Ron Banner, Avi Mendelson |
| 2205.02302 | 631244 | 2022-07-12 10:10:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2205.02302v3 | Machine Learning Operations (MLOps): Overview, Definition, and Architecture | The final goal of all industrial machine learning (ML) projects is to develop ML products and rapidly bring them into production. However, it is highly challenging to automate and operationalize ML products and thus many ML endeavors fail to deliver on their expectations. The paradigm of Machine Learning Operations (MLOps) addresses this issue. MLOps includes several aspects, such as best practices, sets of concepts, and development culture. However, MLOps is still a vague term and its consequences for researchers and professionals are ambiguous. To address this gap, we conduct mixed-method research, including a literature review, a tool review, and expert interviews. As a result of these investigations, we provide an aggregated overview of the necessary principles, components, and roles, as well as the associated architecture and workflows. Furthermore, we furnish a definition of MLOps and highlight open challenges in the field. Finally, this work provides guidance for ML researchers and practitioners who want to automate and operate their ML products with a designated set of technologies. | Dominik Kreuzberger, Niklas Kühl, Sebastian Hirschl |
| 2005.12798 | 601952 | 2022-07-14 09:05:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2005.12798v1 | Opinion Dynamics on Discourse Sheaves | We introduce a novel class of Laplacians and diffusion dynamics on discourse sheaves as a model for network dynamics, with application to opinion dynamics on social networks. These sheaves are algebraic data structures tethered to a network (or more general space) that can represent various modes of communication, including selective opinion modulation and lying. After introducing the sheaf model, we develop a sheaf Laplacian in this context and show how to evolve both opinions and communications with diffusion dynamics over the network. Issues of controllability, reachability, bounded confidence, and harmonic extension are addressed using this framework. | Jakob Hansen, Robert Ghrist |
| 2206.08702 | 383748 | 2022-07-15 05:36:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2206.08702v1 | Sheaf Neural Networks with Connection Laplacians | A Sheaf Neural Network (SNN) is a type of Graph Neural Network (GNN) that operates on a sheaf, an object that equips a graph with vector spaces over its nodes and edges and linear maps between these spaces. SNNs have been shown to have useful theoretical properties that help tackle issues arising from heterophily and over-smoothing. One complication intrinsic to these models is finding a good sheaf for the task to be solved. Previous works proposed two diametrically opposed approaches: manually constructing the sheaf based on domain knowledge and learning the sheaf end-to-end using gradient-based methods. However, domain knowledge is often insufficient, while learning a sheaf could lead to overfitting and significant computational overhead. In this work, we propose a novel way of computing sheaves drawing inspiration from Riemannian geometry: we leverage the manifold assumption to compute manifold-and-graph-aware orthogonal maps, which optimally align the tangent spaces of neighbouring data points. We show that this approach achieves promising results with less computational overhead when compared to previous SNN models. Overall, this work provides an interesting connection between algebraic topology and differential geometry, and we hope that it will spark future research in this direction. | Federico Barbero, Cristian Bodnar, Haitz Sáez de Ocáriz Borde, Michael Bronstein, Petar Veličković, Pietro Liò |
| 2002.03864 | 6475407 | 2022-07-15 05:38:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2002.03864v2 | Deep Graph Mapper: Seeing Graphs through the Neural Lens | Recent advancements in graph representation learning have led to the emergence of condensed encodings that capture the main properties of a graph. However, even though these abstract representations are powerful for downstream tasks, they are not equally suitable for visualisation purposes. In this work, we merge Mapper, an algorithm from the field of Topological Data Analysis (TDA), with the expressive power of Graph Neural Networks (GNNs) to produce hierarchical, topologically-grounded visualisations of graphs. These visualisations do not only help discern the structure of complex graphs but also provide a means of understanding the models applied to them for solving various tasks. We further demonstrate the suitability of Mapper as a topological framework for graph pooling by mathematically proving an equivalence with Min-Cut and Diff Pool. Building upon this framework, we introduce a novel pooling algorithm based on PageRank, which obtains competitive results with state of the art methods on graph classification benchmarks. | Cristian Bodnar, Cătălina Cangea, Pietro Liò |
| 2106.02584 | 4598361 | 2022-07-19 09:48:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2106.02584v2 | Self-Attention Between Datapoints: Going Beyond Individual Input-Output Pairs in Deep Learning | We challenge a common assumption underlying most supervised deep learning: that a model makes a prediction depending only on its parameters and the features of a single input. To this end, we introduce a general-purpose deep learning architecture that takes as input the entire dataset instead of processing one datapoint at a time. Our approach uses self-attention to reason about relationships between datapoints explicitly, which can be seen as realizing non-parametric models using parametric attention mechanisms. However, unlike conventional non-parametric models, we let the model learn end-to-end from the data how to make use of other datapoints for prediction. Empirically, our models solve cross-datapoint lookup and complex reasoning tasks unsolvable by traditional deep learning models. We show highly competitive results on tabular data, early results on CIFAR-10, and give insight into how the model makes use of the interactions between points. | Jannik Kossen, Neil Band, Clare Lyle, Aidan N. Gomez, Tom Rainforth, Yarin Gal |
| 2202.01379 | 1388993 | 2022-07-20 07:43:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2202.01379v2 | A Very Elementary Introduction to Sheaves | This paper is a very non-rigorous, loose, and extremely basic introduction to sheaves. This is meant to be a a guide to gaining intuition about sheaves, what they look like, and how they work, so that after reading this paper, someone can jump into the extremely abstract definitions and examples seen in textbooks with at least some idea of what is going on. Most of this material is inspired and built from the work of Dr. Michael Robinson, and that of Dr. Robert Ghrist and Dr. Jakob Hansen, as well as Dr. Justin Curry's PhD thesis, who are some of the only applied sheaf theorists out there and they do an amazing job of explaining sheaves in a concrete way through their research. The rest of this paper is populated by mathematical definitions found in textbooks that I have stretched from two lines into multiple pages, as well as some analogies for thinking of sheaves I have thought of myself. This paper only assumes knowledge of basic linear algebra, basic group theory, and the very fundamentals of topology. If there is anything in the setup that you do not understand it is probably a quick Wikipedia search away. I hope this paper provides insight, intuition, and helpful examples of why sheaves are such powerful tools in both math and science. | Mark Agrios |
| 2002.05287 | 2719995 | 2022-07-20 13:20:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2002.05287v2 | Geom-GCN: Geometric Graph Convolutional Networks | Message-passing neural networks (MPNNs) have been successfully applied to representation learning on graphs in a variety of real-world applications. However, two fundamental weaknesses of MPNNs' aggregators limit their ability to represent graph-structured data: losing the structural information of nodes in neighborhoods and lacking the ability to capture long-range dependencies in disassortative graphs. Few studies have noticed the weaknesses from different perspectives. From the observations on classical neural network and network geometry, we propose a novel geometric aggregation scheme for graph neural networks to overcome the two weaknesses. The behind basic idea is the aggregation on a graph can benefit from a continuous space underlying the graph. The proposed aggregation scheme is permutation-invariant and consists of three modules, node embedding, structural neighborhood, and bi-level aggregation. We also present an implementation of the scheme in graph convolutional networks, termed Geom-GCN (Geometric Graph Convolutional Networks), to perform transductive learning on graphs. Experimental results show the proposed Geom-GCN achieved state-of-the-art performance on a wide range of open datasets of graphs. Code is available at https://github.com/graphdml-uiuc-jlu/geom-gcn. | Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, Bo Yang |
| 2207.09238 | 514843 | 2022-07-20 14:39:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2207.09238v1 | Formal Algorithms for Transformers | This document aims to be a self-contained, mathematically precise overview of transformer architectures and algorithms (*not* results). It covers what transformers are, how they are trained, what they are used for, their key architectural components, and a preview of the most prominent models. The reader is assumed to be familiar with basic ML terminology and simpler neural network architectures such as MLPs. | Mary Phuong, Marcus Hutter |
| 1601.02513 | 557432 | 2022-07-24 10:47:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1601.02513v1 | How to learn a graph from smooth signals | We propose a framework that learns the graph structure underlying a set of smooth signals. Given $X\in\mathbb{R}^{m\times n}$ whose rows reside on the vertices of an unknown graph, we learn the edge weights $w\in\mathbb{R}_+^{m(m-1)/2}$ under the smoothness assumption that $\text{tr}{X^\top LX}$ is small. We show that the problem is a weighted $\ell$-1 minimization that leads to naturally sparse solutions. We point out how known graph learning or construction techniques fall within our framework and propose a new model that performs better than the state of the art in many settings. We present efficient, scalable primal-dual based algorithms for both our model and the previous state of the art, and evaluate their performance on artificial and real data. | Vassilis Kalofolias |
| 1812.08313 | 5852272 | 2022-07-24 11:11:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1812.08313v1 | Iterated Belief Revision Under Resource Constraints: Logic as Geometry | We propose a variant of iterated belief revision designed for settings with limited computational resources, such as mobile autonomous robots. The proposed memory architecture---called the {\em universal memory architecture} (UMA)---maintains an epistemic state in the form of a system of default rules similar to those studied by Pearl and by Goldszmidt and Pearl (systems $Z$ and $Z^+$). A duality between the category of UMA representations and the category of the corresponding model spaces, extending the Sageev-Roller duality between discrete poc sets and discrete median algebras provides a two-way dictionary from inference to geometry, leading to immense savings in computation, at a cost in the quality of representation that can be quantified in terms of topological invariants. Moreover, the same framework naturally enables comparisons between different model spaces, making it possible to analyze the deficiencies of one model space in comparison to others. This paper develops the formalism underlying UMA, analyzes the complexity of maintenance and inference operations in UMA, and presents some learning guarantees for different UMA-based learners. Finally, we present simulation results to illustrate the viability of the approach, and close with a discussion of the strengths, weaknesses, and potential development of UMA-based learners. | Dan P. Guralnik, Daniel E. Koditschek |
| 1707.00354 | 745442 | 2022-07-24 11:16:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1707.00354v2 | Local cohomology and stratification | We outline an algorithm to recover the canonical (or, coarsest) stratification of a given finite-dimensional regular CW complex into cohomology manifolds, each of which is a union of cells. The construction proceeds by iteratively localizing the poset of cells about a family of subposets; these subposets are in turn determined by a collection of cosheaves which capture variations in cohomology of cellular neighborhoods across the underlying complex. The result is a nested sequence of categories, each containing all the cells as its set of objects, with the property that two cells are isomorphic in the last category if and only if they lie in the same canonical stratum. The entire process is amenable to efficient distributed computation. | Vidit Nanda |
| 2207.03522 | 605569 | 2022-07-26 07:05:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2207.03522v1 | TF-GNN: Graph Neural Networks in TensorFlow | TensorFlow GNN (TF-GNN) is a scalable library for Graph Neural Networks in TensorFlow. It is designed from the bottom up to support the kinds of rich heterogeneous graph data that occurs in today's information ecosystems. Many production models at Google use TF-GNN and it has been recently released as an open source project. In this paper, we describe the TF-GNN data model, its Keras modeling API, and relevant capabilities such as graph sampling, distributed training, and accelerator support. | Oleksandr Ferludin, Arno Eigenwillig, Martin Blais, Dustin Zelle, Jan Pfeifer, Alvaro Sanchez-Gonzalez, Sibon Li, Sami Abu-El-Haija, Peter Battaglia, Neslihan Bulut, Jonathan Halcrow, Filipe Miguel Gonçalves de Almeida, Silvio Lattanzi, André Linhares, Brandon Mayer, Vahab Mirrokni, John Palowitch, Mihir Paradkar, Jennifer She, Anton Tsitsulin, Kevin Villela, Lisa Wang, David Wong, Bryan Perozzi |
| 2105.14491 | 699201 | 2022-07-26 08:27:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2105.14491v3 | How Attentive are Graph Attention Networks? | Graph Attention Networks (GATs) are one of the most popular GNN architectures and are considered as the state-of-the-art architecture for representation learning with graphs. In GAT, every node attends to its neighbors given its own representation as the query. However, in this paper we show that GAT computes a very limited kind of attention: the ranking of the attention scores is unconditioned on the query node. We formally define this restricted kind of attention as static attention and distinguish it from a strictly more expressive dynamic attention. Because GATs use a static attention mechanism, there are simple graph problems that GAT cannot express: in a controlled problem, we show that static attention hinders GAT from even fitting the training data. To remove this limitation, we introduce a simple fix by modifying the order of operations and propose GATv2: a dynamic graph attention variant that is strictly more expressive than GAT. We perform an extensive evaluation and show that GATv2 outperforms GAT across 11 OGB and other benchmarks while we match their parametric costs. Our code is available at https://github.com/tech-srl/how_attentive_are_gats . GATv2 is available as part of the PyTorch Geometric library, the Deep Graph Library, and the TensorFlow GNN library. | Shaked Brody, Uri Alon, Eran Yahav |
| 0811.1067 | 563414 | 2022-07-26 08:29:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/0811.1067v2 | Statistical ranking and combinatorial Hodge theory | We propose a number of techniques for obtaining a global ranking from data that may be incomplete and imbalanced -- characteristics almost universal to modern datasets coming from e-commerce and internet applications. We are primarily interested in score or rating-based cardinal data. From raw ranking data, we construct pairwise rankings, represented as edge flows on an appropriate graph. Our statistical ranking method uses the graph Helmholtzian, the graph theoretic analogue of the Helmholtz operator or vector Laplacian, in much the same way the graph Laplacian is an analogue of the Laplace operator or scalar Laplacian. We study the graph Helmholtzian using combinatorial Hodge theory: we show that every edge flow representing pairwise ranking can be resolved into two orthogonal components, a gradient flow that represents the L2-optimal global ranking and a divergence-free flow (cyclic) that measures the validity of the global ranking obtained -- if this is large, then the data does not have a meaningful global ranking. This divergence-free flow can be further decomposed orthogonally into a curl flow (locally cyclic) and a harmonic flow (locally acyclic but globally cyclic); these provides information on whether inconsistency arises locally or globally. An obvious advantage over the NP-hard Kemeny optimization is that discrete Hodge decomposition may be computed via a linear least squares regression. We also investigated the L1-projection of edge flows, showing that this is dual to correlation maximization over bounded divergence-free flows, and the L1-approximate sparse cyclic ranking, showing that this is dual to correlation maximization over bounded curl-free flows. We discuss relations with Kemeny optimization, Borda count, and Kendall-Smith consistency index from social choice theory and statistics. | Xiaoye Jiang, Lek-Heng Lim, Yuan Yao, Yinyu Ye |
| 1604.04647 | 745013 | 2022-07-26 08:49:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1604.04647v2 | Sheaf and duality methods for analyzing multi-model systems | There is an interplay between models, specified by variables and equations, and their connections to one another. This dichotomy should be reflected in the abstract as well. Without referring to the models directly -- only that a model consists of spaces and maps between them -- the most readily apparent feature of a multi-model system is its topology. We propose that this topology should be modeled first, and then the spaces and maps of the individual models be specified in accordance with the topology. Axiomatically, this construction leads to sheaves. Sheaf theory provides a toolbox for constructing predictive models described by systems of equations. Sheaves are mathematical objects that manage the combination of bits of local information into a consistent whole. The power of this approach is that complex models can be assembled from smaller, easier-to-construct models. The models discussed in this chapter span the study of continuous dynamical systems, partial differential equations, probabilistic graphical models, and discrete approximations of these models. | Michael Robinson |
| 1603.01446 | 2027554 | 2022-07-26 08:49:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1603.01446v3 | Sheaves are the canonical datastructure for sensor integration | A sensor integration framework should be sufficiently general to accurately represent all information sources, and also be able to summarize information in a faithful way that emphasizes important, actionable information. Few approaches adequately address these two discordant requirements. The purpose of this expository paper is to explain why sheaves are the canonical data structure for sensor integration and how the mathematics of sheaves satisfies our two requirements. We outline some of the powerful inferential tools that are not available to other representational frameworks. | Michael Robinson |
| 1704.04110 | 568897 | 2022-07-28 16:46:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1704.04110v3 | DeepAR: Probabilistic Forecasting with Autoregressive Recurrent Networks | Probabilistic forecasting, i.e. estimating the probability distribution of a time series' future given its past, is a key enabler for optimizing business processes. In retail businesses, for example, forecasting demand is crucial for having the right inventory available at the right time at the right place. In this paper we propose DeepAR, a methodology for producing accurate probabilistic forecasts, based on training an auto regressive recurrent network model on a large number of related time series. We demonstrate how by applying deep learning techniques to forecasting, one can overcome many of the challenges faced by widely-used classical approaches to the problem. We show through extensive empirical evaluation on several real-world forecasting data sets accuracy improvements of around 15% compared to state-of-the-art methods. | David Salinas, Valentin Flunkert, Jan Gasthaus |
| 2201.09792 | 2031055 | 2022-07-29 09:39:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2201.09792v1 | Patches Are All You Need? | Although convolutional networks have been the dominant architecture for vision tasks for many years, recent experiments have shown that Transformer-based models, most notably the Vision Transformer (ViT), may exceed their performance in some settings. However, due to the quadratic runtime of the self-attention layers in Transformers, ViTs require the use of patch embeddings, which group together small regions of the image into single input features, in order to be applied to larger image sizes. This raises a question: Is the performance of ViTs due to the inherently-more-powerful Transformer architecture, or is it at least partly due to using patches as the input representation? In this paper, we present some evidence for the latter: specifically, we propose the ConvMixer, an extremely simple model that is similar in spirit to the ViT and the even-more-basic MLP-Mixer in that it operates directly on patches as input, separates the mixing of spatial and channel dimensions, and maintains equal size and resolution throughout the network. In contrast, however, the ConvMixer uses only standard convolutions to achieve the mixing steps. Despite its simplicity, we show that the ConvMixer outperforms the ViT, MLP-Mixer, and some of their variants for similar parameter counts and data set sizes, in addition to outperforming classical vision models such as the ResNet. Our code is available at https://github.com/locuslab/convmixer. | Asher Trockman, J. Zico Kolter |
| 2201.12689 | 10356352 | 2022-07-29 09:42:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2201.12689v2 | Hyperbolic band theory through Higgs bundles | Hyperbolic lattices underlie a new form of quantum matter with potential applications to quantum computing and simulation and which, to date, have been engineered artificially. A corresponding hyperbolic band theory has emerged, extending 2-dimensional Euclidean band theory in a natural way to higher-genus configuration spaces. Attempts to develop the hyperbolic analogue of Bloch's theorem have revealed an intrinsic role for algebro-geometric moduli spaces, notably those of stable bundles on a curve. We expand this picture to include Higgs bundles, which enjoy natural interpretations in the context of band theory. First, their spectral data encodes a crystal lattice and momentum, providing a framework for symmetric hyperbolic crystals. Second, they act as a complex analogue of crystal momentum. As an application, we elicit a new perspective on Euclidean band theory. Finally, we speculate on potential interactions of hyperbolic band theory, facilitated by Higgs bundles, with other themes in mathematics and physics. | Elliot Kienzle, Steven Rayan |
| 2201.12689 | 10356352 | 2022-07-29 09:42:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2201.12689v2 | Hyperbolic band theory through Higgs bundles | Hyperbolic lattices underlie a new form of quantum matter with potential applications to quantum computing and simulation and which, to date, have been engineered artificially. A corresponding hyperbolic band theory has emerged, extending 2-dimensional Euclidean band theory in a natural way to higher-genus configuration spaces. Attempts to develop the hyperbolic analogue of Bloch's theorem have revealed an intrinsic role for algebro-geometric moduli spaces, notably those of stable bundles on a curve. We expand this picture to include Higgs bundles, which enjoy natural interpretations in the context of band theory. First, their spectral data encodes a crystal lattice and momentum, providing a framework for symmetric hyperbolic crystals. Second, they act as a complex analogue of crystal momentum. As an application, we elicit a new perspective on Euclidean band theory. Finally, we speculate on potential interactions of hyperbolic band theory, facilitated by Higgs bundles, with other themes in mathematics and physics. | Elliot Kienzle, Steven Rayan |
| 2107.07346 | 2835760 | 2022-07-31 11:01:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2107.07346v1 | You Do Not Need a Bigger Boat: Recommendations at Reasonable Scale in a (Mostly) Serverless and Open Stack | We argue that immature data pipelines are preventing a large portion of industry practitioners from leveraging the latest research on recommender systems. We propose our template data stack for machine learning at "reasonable scale", and show how many challenges are solved by embracing a serverless paradigm. Leveraging our experience, we detail how modern open source can provide a pipeline processing terabytes of data with limited infrastructure work. | Jacopo Tagliabue |
| 1911.05467 | 770805 | 2022-08-02 15:40:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1911.05467v2 | ChebNet: Efficient and Stable Constructions of Deep Neural Networks with Rectified Power Units using Chebyshev Approximations | In a recent paper [B. Li, S. Tang and H. Yu, arXiv:1903.05858], it was shown that deep neural networks built with rectified power units (RePU) can give better approximation for sufficient smooth functions than those with rectified linear units, by converting polynomial approximation given in power series into deep neural networks with optimal complexity and no approximation error. However, in practice, power series are not easy to compute. In this paper, we propose a new and more stable way to construct deep RePU neural networks based on Chebyshev polynomial approximations. By using a hierarchical structure of Chebyshev polynomial approximation in frequency domain, we build efficient and stable deep neural network constructions. In theory, ChebNets and the deep RePU nets based on Power series have the same upper error bounds for general function approximations. But numerically, ChebNets are much more stable. Numerical results show that the constructed ChebNets can be further trained and obtain much better results than those obtained by training deep RePU nets constructed basing on power series. | Shanshan Tang, Bo Li, Haijun Yu |
| 1703.04385 | 4612750 | 2022-08-03 07:53:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1703.04385v2 | Topological Data Analysis of Financial Time Series: Landscapes of Crashes | We explore the evolution of daily returns of four major US stock market indices during the technology crash of 2000, and the financial crisis of 2007-2009. Our methodology is based on topological data analysis (TDA). We use persistence homology to detect and quantify topological patterns that appear in multidimensional time series. Using a sliding window, we extract time-dependent point cloud data sets, to which we associate a topological space. We detect transient loops that appear in this space, and we measure their persistence. This is encoded in real-valued functions referred to as a 'persistence landscapes'. We quantify the temporal changes in persistence landscapes via their $L^p$-norms. We test this procedure on multidimensional time series generated by various non-linear and non-equilibrium models. We find that, in the vicinity of financial meltdowns, the $L^p$-norms exhibit strong growth prior to the primary peak, which ascends during a crash. Remarkably, the average spectral density at low frequencies of the time series of $L^p$-norms of the persistence landscapes demonstrates a strong rising trend for 250 trading days prior to either dotcom crash on 03/10/2000, or to the Lehman bankruptcy on 09/15/2008. Our study suggests that TDA provides a new type of econometric analysis, which goes beyond the standard statistical measures. The method can be used to detect early warning signals of imminent market crashes. We believe that this approach can be used beyond the analysis of financial time series presented here. | Marian Gidea, Yuri Katz |
| 1809.00695 | 4094556 | 2022-08-03 07:57:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1809.00695v1 | Topological recognition of critical transitions in time series of cryptocurrencies | We analyze the time series of four major cryptocurrencies (Bitcoin, Ethereum, Litecoin, and Ripple) before the digital market crash at the end of 2017 - beginning 2018. We introduce a methodology that combines topological data analysis with a machine learning technique -- $k$-means clustering -- in order to automatically recognize the emerging chaotic regime in a complex system approaching a critical transition. We first test our methodology on the complex system dynamics of a Lorenz-type attractor, and then we apply it to the four major cryptocurrencies. We find early warning signals for critical transitions in the cryptocurrency markets, even though the relevant time series exhibit a highly erratic behavior. | Marian Gidea, Daniel Goldsmith, Yuri Katz, Pablo Roldan, Yonah Shmalo |
| 1507.05379 | 1230934 | 2022-08-08 09:39:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1507.05379v4 | Hodge Laplacians on graphs | This is an elementary introduction to the Hodge Laplacian on a graph, a higher-order generalization of the graph Laplacian. We will discuss basic properties including cohomology and Hodge theory. The main feature of our approach is simplicity, requiring only knowledge of linear algebra and graph theory. We have also isolated the algebra from the topology to show that a large part of cohomology and Hodge theory is nothing more than the linear algebra of matrices satisfying $AB = 0$. For the remaining topological aspect, we cast our discussions entirely in terms of graphs as opposed to less-familiar topological objects like simplicial complexes. | Lek-Heng Lim |
| 1904.07403 | 3506793 | 2022-08-17 15:45:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1904.07403v2 | Persistent Homology of Complex Networks for Dynamic State Detection | In this paper we develop a novel Topological Data Analysis (TDA) approach for studying graph representations of time series of dynamical systems. Specifically, we show how persistent homology, a tool from TDA, can be used to yield a compressed, multi-scale representation of the graph that can distinguish between dynamic states such as periodic and chaotic behavior. We show the approach for two graph constructions obtained from the time series. In the first approach the time series is embedded into a point cloud which is then used to construct an undirected $k$-nearest neighbor graph. The second construct relies on the recently developed ordinal partition framework. In either case, a pairwise distance matrix is then calculated using the shortest path between the graph's nodes, and this matrix is utilized to define a filtration of a simplicial complex that enables tracking the changes in homology classes over the course of the filtration. These changes are summarized in a persistence diagram---a two-dimensional summary of changes in the topological features. We then extract existing as well as new geometric and entropy point summaries from the persistence diagram and compare to other commonly used network characteristics. Our results show that persistence-based point summaries yield a clearer distinction of the dynamic behavior and are more robust to noise than existing graph-based scores, especially when combined with ordinal graphs. | Audun Myers, Elizabeth Munch, Firas A. Khasawneh |
| 2206.10991 | 806820 | 2022-08-18 08:06:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2206.10991v3 | Graph Neural Networks as Gradient Flows: understanding graph convolutions via energy | Gradient flows are differential equations that minimize an energy functional and constitute the main descriptors of physical systems. We apply this formalism to Graph Neural Networks (GNNs) to develop new frameworks for learning on graphs as well as provide a better theoretical understanding of existing ones. We derive GNNs as a gradient flow equation of a parametric energy that provides a physics-inspired interpretation of GNNs as learning particle dynamics in the feature space. In particular, we show that in graph convolutional models (GCN), the positive/negative eigenvalues of the channel mixing matrix correspond to attractive/repulsive forces between adjacent features. We rigorously prove how the channel-mixing can learn to steer the dynamics towards low or high frequencies, which allows to deal with heterophilic graphs. We show that the same class of energies is decreasing along a larger family of GNNs; albeit not gradient flows, they retain their inductive bias. We experimentally evaluate an instance of the gradient flow framework that is principled, more efficient than GCN, and achieves competitive performance on graph datasets of varying homophily often outperforming recent baselines specifically designed to target heterophily. | Francesco Di Giovanni, James Rowbottom, Benjamin P. Chamberlain, Thomas Markovich, Michael M. Bronstein |
| 1910.08345 | 1610238 | 2022-08-26 12:36:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1910.08345v2 | A Topological "Reading" Lesson: Classification of MNIST using TDA | We present a way to use Topological Data Analysis (TDA) for machine learning tasks on grayscale images. We apply persistent homology to generate a wide range of topological features using a point cloud obtained from an image, its natural grayscale filtration, and different filtrations defined on the binarized image. We show that this topological machine learning pipeline can be used as a highly relevant dimensionality reduction by applying it to the MNIST digits dataset. We conduct a feature selection and study their correlations while providing an intuitive interpretation of their importance, which is relevant in both machine learning and TDA. Finally, we show that we can classify digit images while reducing the size of the feature set by a factor 5 compared to the grayscale pixel value features and maintain similar accuracy. | Adélie Garin, Guillaume Tauzin |
| 2208.11970 | 5033664 | 2022-08-27 10:26:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2208.11970v1 | Understanding Diffusion Models: A Unified Perspective | Diffusion models have shown incredible capabilities as generative models; indeed, they power the current state-of-the-art models on text-conditioned image generation such as Imagen and DALL-E 2. In this work we review, demystify, and unify the understanding of diffusion models across both variational and score-based perspectives. We first derive Variational Diffusion Models (VDM) as a special case of a Markovian Hierarchical Variational Autoencoder, where three key assumptions enable tractable computation and scalable optimization of the ELBO. We then prove that optimizing a VDM boils down to learning a neural network to predict one of three potential objectives: the original source input from any arbitrary noisification of it, the original source noise from any arbitrarily noisified input, or the score function of a noisified input at any arbitrary noise level. We then dive deeper into what it means to learn the score function, and connect the variational perspective of a diffusion model explicitly with the Score-based Generative Modeling perspective through Tweedie's Formula. Lastly, we cover how to learn a conditional distribution using diffusion models via guidance. | Calvin Luo |
| 1711.09883 | 1944073 | 2022-09-01 08:02:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1711.09883v2 | AI Safety Gridworlds | We present a suite of reinforcement learning environments illustrating various safety properties of intelligent agents. These problems include safe interruptibility, avoiding side effects, absent supervisor, reward gaming, safe exploration, as well as robustness to self-modification, distributional shift, and adversaries. To measure compliance with the intended safe behavior, we equip each environment with a performance function that is hidden from the agent. This allows us to categorize AI safety problems into robustness and specification problems, depending on whether the performance function corresponds to the observed reward function. We evaluate A2C and Rainbow, two recent deep reinforcement learning agents, on our environments and show that they are not able to solve them satisfactorily. | Jan Leike, Miljan Martic, Victoria Krakovna, Pedro A. Ortega, Tom Everitt, Andrew Lefrancq, Laurent Orseau, Shane Legg |
| 2004.09095 | 2874015 | 2022-09-06 08:34:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2004.09095v3 | The State and Fate of Linguistic Diversity and Inclusion in the NLP World | Language technologies contribute to promoting multilingualism and linguistic diversity around the world. However, only a very small number of the over 7000 languages of the world are represented in the rapidly evolving language technologies and applications. In this paper we look at the relation between the types of languages, resources, and their representation in NLP conferences to understand the trajectory that different languages have followed over time. Our quantitative investigation underlines the disparity between languages, especially in terms of their resources, and calls into question the "language agnostic" status of current models and systems. Through this paper, we attempt to convince the ACL community to prioritise the resolution of the predicaments highlighted here, so that no language is left behind. | Pratik Joshi, Sebastin Santy, Amar Budhiraja, Kalika Bali, Monojit Choudhury |
| 1810.03993 | 995470 | 2022-09-06 11:02:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1810.03993v2 | Model Cards for Model Reporting | Trained machine learning models are increasingly used to perform high-impact tasks in areas such as law enforcement, medicine, education, and employment. In order to clarify the intended use cases of machine learning models and minimize their usage in contexts for which they are not well suited, we recommend that released models be accompanied by documentation detailing their performance characteristics. In this paper, we propose a framework that we call model cards, to encourage such transparent model reporting. Model cards are short documents accompanying trained machine learning models that provide benchmarked evaluation in a variety of conditions, such as across different cultural, demographic, or phenotypic groups (e.g., race, geographic location, sex, Fitzpatrick skin type) and intersectional groups (e.g., age and race, or sex and Fitzpatrick skin type) that are relevant to the intended application domains. Model cards also disclose the context in which models are intended to be used, details of the performance evaluation procedures, and other relevant information. While we focus primarily on human-centered machine learning models in the application fields of computer vision and natural language processing, this framework can be used to document any trained machine learning model. To solidify the concept, we provide cards for two supervised models: One trained to detect smiling faces in images, and one trained to detect toxic comments in text. We propose model cards as a step towards the responsible democratization of machine learning and related AI technology, increasing transparency into how well AI technology works. We hope this work encourages those releasing trained machine learning models to accompany model releases with similar detailed evaluation numbers and other relevant documentation. | Margaret Mitchell, Simone Wu, Andrew Zaldivar, Parker Barnes, Lucy Vasserman, Ben Hutchinson, Elena Spitzer, Inioluwa Deborah Raji, Timnit Gebru |
| 2001.09768 | 710181 | 2022-09-06 11:24:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2001.09768v2 | Artificial Intelligence, Values and Alignment | This paper looks at philosophical questions that arise in the context of AI alignment. It defends three propositions. First, normative and technical aspects of the AI alignment problem are interrelated, creating space for productive engagement between people working in both domains. Second, it is important to be clear about the goal of alignment. There are significant differences between AI that aligns with instructions, intentions, revealed preferences, ideal preferences, interests and values. A principle-based approach to AI alignment, which combines these elements in a systematic way, has considerable advantages in this context. Third, the central challenge for theorists is not to identify 'true' moral principles for AI; rather, it is to identify fair principles for alignment, that receive reflective endorsement despite widespread variation in people's moral beliefs. The final part of the paper explores three ways in which fair principles for AI alignment could potentially be identified. | Iason Gabriel |
| 2102.04257 | 585241 | 2022-09-06 14:35:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2102.04257v3 | Fairness for Unobserved Characteristics: Insights from Technological Impacts on Queer Communities | Advances in algorithmic fairness have largely omitted sexual orientation and gender identity. We explore queer concerns in privacy, censorship, language, online safety, health, and employment to study the positive and negative effects of artificial intelligence on queer communities. These issues underscore the need for new directions in fairness research that take into account a multiplicity of considerations, from privacy preservation, context sensitivity and process fairness, to an awareness of sociotechnical impact and the increasingly important role of inclusive and participatory research processes. Most current approaches for algorithmic fairness assume that the target characteristics for fairness--frequently, race and legal gender--can be observed or recorded. Sexual orientation and gender identity are prototypical instances of unobserved characteristics, which are frequently missing, unknown or fundamentally unmeasurable. This paper highlights the importance of developing new approaches for algorithmic fairness that break away from the prevailing assumption of observed characteristics. | Nenad Tomasev, Kevin R. McKee, Jackie Kay, Shakir Mohamed |
| 2103.06720 | 1055543 | 2022-09-07 09:46:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2103.06720v3 | Variational inference with a quantum computer | Inference is the task of drawing conclusions about unobserved variables given observations of related variables. Applications range from identifying diseases from symptoms to classifying economic regimes from price movements. Unfortunately, performing exact inference is intractable in general. One alternative is variational inference, where a candidate probability distribution is optimized to approximate the posterior distribution over unobserved variables. For good approximations, a flexible and highly expressive candidate distribution is desirable. In this work, we use quantum Born machines as variational distributions over discrete variables. We apply the framework of operator variational inference to achieve this goal. In particular, we adopt two specific realizations: one with an adversarial objective and one based on the kernelized Stein discrepancy. We demonstrate the approach numerically using examples of Bayesian networks, and implement an experiment on an IBM quantum computer. Our techniques enable efficient variational inference with distributions beyond those that are efficiently representable on a classical computer. | Marcello Benedetti, Brian Coyle, Mattia Fiorentini, Michael Lubasch, Matthias Rosenkranz |
| 2203.15544 | 722746 | 2022-09-07 13:24:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2203.15544v3 | Graph Neural Networks are Dynamic Programmers | Recent advances in neural algorithmic reasoning with graph neural networks (GNNs) are propped up by the notion of algorithmic alignment. Broadly, a neural network will be better at learning to execute a reasoning task (in terms of sample complexity) if its individual components align well with the target algorithm. Specifically, GNNs are claimed to align with dynamic programming (DP), a general problem-solving strategy which expresses many polynomial-time algorithms. However, has this alignment truly been demonstrated and theoretically quantified? Here we show, using methods from category theory and abstract algebra, that there exists an intricate connection between GNNs and DP, going well beyond the initial observations over individual algorithms such as Bellman-Ford. Exposing this connection, we easily verify several prior findings in the literature, produce better-grounded GNN architectures for edge-centric tasks, and demonstrate empirical results on the CLRS algorithmic reasoning benchmark. We hope our exposition will serve as a foundation for building stronger algorithmically aligned GNNs. | Andrew Dudzik, Petar Veličković |
| 2209.03307 | 190161 | 2022-09-08 07:38:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2209.03307v1 | A primer on perpetuals | We consider a continuous-time financial market with no arbitrage and no transactions costs. In this setting, we introduce two types of perpetual contracts, one in which the payoff to the long side is a fixed function of the underlyers and the long side pays a funding rate to the short side, the other in which the payoff to the long side is a fixed function of the underlyers times a discount factor that changes over time but no funding payments are required. Assuming asset prices are continuous and strictly positive, we derive model-free expressions for the funding rate and discount rate of these perpetual contracts as well as replication strategies for the short side. When asset prices can jump, we derive expressions for the funding and discount rates, which are semi-robust in the sense that they do not depend on the dynamics of the volatility process of the underlying risky assets, but do depend on the intensity of jumps under the market's pricing measure. When asset prices can jump and the volatility process is independent of the underlying risky assets, we derive an explicit replication strategy for the short side of a perpetual contract. Throughout the paper, we illustrate through examples how specific perpetual contracts relate to traditional financial instruments such as variance swaps and leveraged exchange traded funds. | Guillermo Angeris, Tarun Chitra, Alex Evans, Matthew Lorig |
| 1308.4621 | 239680 | 2022-09-09 14:36:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1308.4621v1 | Understanding networks and their behaviors using sheaf theory | Many complicated network problems can be easily understood on small networks. Difficulties arise when small networks are combined into larger ones. Fortunately, the mathematical theory of sheaves was constructed to address just this kind of situation; it extends locally-defined structures to globally valid inferences by way of consistency relations. This paper exhibits examples in network monitoring and filter hardware where sheaves have useful descriptive power. | Michael Robinson |
| 1303.3255 | 2570574 | 2022-09-13 09:26:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1303.3255v2 | Sheaves, Cosheaves and Applications | This thesis develops the theory of sheaves and cosheaves with an eye towards applications in science and engineering. To provide a theory that is computable, we focus on a combinatorial version of sheaves and cosheaves called cellular sheaves and cosheaves, which are finite families of vector spaces and maps parametrized by a cell complex. We develop cellular (co)sheaves as a new tool for topological data analysis, network coding and sensor networks. A foundation for multi-dimensional level-set persistent homology is laid via constructible cosheaves, which are equivalent to representations of MacPherson's entrance path category. By proving a van Kampen theorem, we give a direct proof of this equivalence. A cosheaf version of the i'th derived pushforward of the constant sheaf along a definable map is constructed directly as a representation of this category. We go on to clarify the relationship of cellular sheaves to cosheaves by providing a formula that defines a derived equivalence, which in turn recovers Verdier duality. Compactly-supported sheaf cohomology is expressed as the coend with the image of the constant sheaf through this equivalence. The equivalence is further used to establish relations between sheaf cohomology and a herein newly introduced theory of cellular sheaf homology. Inspired to provide fast algorithms for persistence, we prove that the derived category of cellular sheaves over a 1D cell complex is equivalent to a category of graded sheaves. Finally, we introduce the interleaving distance as an extended pseudo-metric on the category of sheaves. We prove that global sections partition the space of sheaves into connected components. We conclude with an investigation into the geometry of the space of constructible sheaves over the real line, which we relate to the bottleneck distance in persistence. | Justin Curry |
| 2012.06333 | 2656097 | 2022-09-22 06:22:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2012.06333v1 | Sheaf Neural Networks | We present a generalization of graph convolutional networks by generalizing the diffusion operation underlying this class of graph neural networks. These sheaf neural networks are based on the sheaf Laplacian, a generalization of the graph Laplacian that encodes additional relational structure parameterized by the underlying graph. The sheaf Laplacian and associated matrices provide an extended version of the diffusion operation in graph convolutional networks, providing a proper generalization for domains where relations between nodes are non-constant, asymmetric, and varying in dimension. We show that the resulting sheaf neural networks can outperform graph convolutional networks in domains where relations between nodes are asymmetric and signed. | Jakob Hansen, Thomas Gebhart |
| 2210.01542 | 11463178 | 2022-10-11 07:30:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2210.01542v1 | Hyperbolic Deep Reinforcement Learning | We propose a new class of deep reinforcement learning (RL) algorithms that model latent representations in hyperbolic space. Sequential decision-making requires reasoning about the possible future consequences of current behavior. Consequently, capturing the relationship between key evolving features for a given task is conducive to recovering effective policies. To this end, hyperbolic geometry provides deep RL models with a natural basis to precisely encode this inherently hierarchical information. However, applying existing methodologies from the hyperbolic deep learning literature leads to fatal optimization instabilities due to the non-stationarity and variance characterizing RL gradient estimators. Hence, we design a new general method that counteracts such optimization challenges and enables stable end-to-end learning with deep hyperbolic representations. We empirically validate our framework by applying it to popular on-policy and off-policy RL algorithms on the Procgen and Atari 100K benchmarks, attaining near universal performance and generalization benefits. Given its natural fit, we hope future RL research will consider hyperbolic representations as a standard tool. | Edoardo Cetin, Benjamin Chamberlain, Michael Bronstein, Jonathan J Hunt |
| 1906.06132 | 565730 | 2022-10-11 13:00:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1906.06132v2 | SchenQL -- A Domain-Specific Query Language on Bibliographic Metadata | Information access needs to be uncomplicated, users rather use incorrect data which is easily received than correct information which is harder to obtain. Querying bibliographic metadata from digital libraries mainly supports simple textual queries. A user's demand for answering more sophisticated queries could be fulfilled by the usage of SQL. As such means are highly complex and challenging even for trained programmers, a domain-specific query language is needed to provide a straightforward way to access data. In this paper we present SchenQL, a simple query language focused on bibliographic metadata in the area of computer science while using the vocabulary of domain-experts. By facilitating a plain syntax and fundamental aggregate functions, we propose an easy-to-learn domain-specific query language capable of search and exploration. It is suitable for domain-experts as well as casual users while still providing the possibility to answer complicated queries. A user study with computer scientists directly compared our query language to SQL and clearly demonstrated SchenQL's suitability and usefulness for given queries as well as users' acceptance. | Christin Katharina Kreutz, Michael Wolz, Ralf Schenkel |
| 1906.06132 | 565730 | 2022-10-11 13:00:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1906.06132v2 | SchenQL -- A Domain-Specific Query Language on Bibliographic Metadata | Information access needs to be uncomplicated, users rather use incorrect data which is easily received than correct information which is harder to obtain. Querying bibliographic metadata from digital libraries mainly supports simple textual queries. A user's demand for answering more sophisticated queries could be fulfilled by the usage of SQL. As such means are highly complex and challenging even for trained programmers, a domain-specific query language is needed to provide a straightforward way to access data. In this paper we present SchenQL, a simple query language focused on bibliographic metadata in the area of computer science while using the vocabulary of domain-experts. By facilitating a plain syntax and fundamental aggregate functions, we propose an easy-to-learn domain-specific query language capable of search and exploration. It is suitable for domain-experts as well as casual users while still providing the possibility to answer complicated queries. A user study with computer scientists directly compared our query language to SQL and clearly demonstrated SchenQL's suitability and usefulness for given queries as well as users' acceptance. | Christin Katharina Kreutz, Michael Wolz, Ralf Schenkel |
| 1312.6454 | 446270 | 2022-10-11 14:45:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1312.6454v2 | Discrete Morse theory for computing cellular sheaf cohomology | Sheaves and sheaf cohomology are powerful tools in computational topology, greatly generalizing persistent homology. We develop an algorithm for simplifying the computation of cellular sheaf cohomology via (discrete) Morse-theoretic techniques. As a consequence, we derive efficient techniques for distributed computation of (ordinary) cohomology of a cell complex. | Justin Curry, Robert Ghrist, Vidit Nanda |
| 1202.0275 | 3880637 | 2022-10-11 14:46:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1202.0275v1 | Euler Calculus with Applications to Signals and Sensing | This article surveys the Euler calculus - an integral calculus based on Euler characteristic - and its applications to data, sensing, networks, and imaging. | Justin Curry, Robert Ghrist, Michael Robinson |
| 1804.04740 | 89531 | 2022-10-11 14:47:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1804.04740v2 | Persistent Homology and Euler Integral Transforms | The Euler calculus -- an integral calculus based on Euler characteristic as a valuation on constructible functions -- is shown to be an incisive tool for answering questions about injectivity and invertibility of recent transforms based on persistent homology for shape characterization. | Robert Ghrist, Rachel Levanger, Huy Mai |
| 1805.09782 | 474707 | 2022-10-11 14:49:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1805.09782v3 | How Many Directions Determine a Shape and other Sufficiency Results for Two Topological Transforms | In this paper we consider two topological transforms that are popular in applied topology: the Persistent Homology Transform (PHT) and the Euler Characteristic Transform (ECT). Both of these transforms are of interest for their mathematical properties as well as their applications to science and engineering, because they provide a way of summarizing shapes in a topological, yet quantitative, way. Both transforms take a shape, viewed as a tame subset $M$ of $\mathbb{R}^d$, and associates to each direction $v\in S^{d-1}$ a shape summary obtained by scanning $M$ in the direction $v$. These shape summaries are either persistence diagrams or piecewise constant integer-valued functions called Euler curves. By using an inversion theorem of Schapira, we show that both transforms are injective on the space of shapes, i.e.~each shape has a unique transform. Moreover, we prove that these transforms determine continuous maps from the sphere to the space of persistence diagrams, equipped with any Wasserstein $p$-distance, or the space of Euler curves, equipped with certain $L^p$ norms. By making use of a stratified space structure on the sphere, induced by hyperplane divisions, we prove additional uniqueness results in terms of distributions on the space of Euler curves. Finally, our main result proves that any shape in a certain uncountable space of PL embedded shapes with plausible geometric bounds can be uniquely determined using only finitely many directions. | Justin Curry, Sayan Mukherjee, Katharine Turner |
| 2208.02107 | 730536 | 2022-10-11 14:50:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2208.02107v1 | A Convolutional Persistence Transform | We consider a new topological feauturization of $d$-dimensional images, obtained by convolving images with various filters before computing persistence. Viewing a convolution filter as a motif within an image, the persistence diagram of the resulting convolution describes the way the motif is distributed throughout that image. This pipeline, which we call convolutional persistence, extends the capacity of topology to observe patterns in image data. Indeed, we prove that (generically speaking) for any two images one can find some filter for which they produce different persistence diagrams, so that the collection of all possible convolutional persistence diagrams for a given image is an injective invariant. This is proven by showing convolutional persistence to be a special case of another topological invariant, the Persistent Homology Transform. Other advantages of convolutional persistence are improved stability and robustness to noise, greater flexibility for data-dependent vectorizations, and reduced computational complexity for convolutions with large stride vectors. Additionally, we have a suite of experiments showing that convolutions greatly improve the predictive power of persistence on a host of classification tasks, even if one uses random filters and vectorizes the resulting diagrams by recording only their total persistences. | Elchanan Solomon, Paul Bendich |
| 2204.09020 | 3059311 | 2022-10-11 14:59:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2204.09020v2 | A Sheaf-Theoretic Construction of Shape Space | We present a sheaf-theoretic construction of shape space -- the space of all shapes. We do this by describing a homotopy sheaf on the poset category of constructible sets, where each set is mapped to its Persistent Homology Transform (PHT). Recent results that build on fundamental work of Schapira have shown that this transform is injective, thus making the PHT a good summary object for each shape. Our homotopy sheaf result allows us to "glue" PHTs of different shapes together to build up the PHT of a larger shape. In the case where our shape is a polyhedron we prove a generalized nerve lemma for the PHT. Finally, by re-examining the sampling result of Smale-Niyogi-Weinberger, we show that we can reliably approximate the PHT of a manifold by a polyhedron up to arbitrary precision. | Shreya Arya, Justin Curry, Sayan Mukherjee |
| 2210.02671 | 248145 | 2022-10-20 08:19:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2210.02671v3 | Transformers Can Be Expressed In First-Order Logic with Majority | Characterizing the implicit structure of the computation within neural networks is a foundational problem in the area of deep learning interpretability. Can the inner decision process of neural networks be captured symbolically in some familiar logic? We show that any fixed-precision transformer neural network can be translated into an equivalent fixed-size $\mathsf{FO}(\mathsf{M})$ formula, i.e., a first-order logic formula that, in addition to standard universal and existential quantifiers, may also contain majority-vote quantifiers. The proof idea is to design highly uniform boolean threshold circuits that can simulate transformers, and then leverage known theoretical connections between circuits and logic. Our results reveal a surprisingly simple formalism for capturing the behavior of transformers, show that simple problems like integer division are "transformer-hard", and provide valuable insights for comparing transformers to other models like RNNs. Our results suggest that first-order logic with majority may be a useful language for expressing programs extracted from transformers. | William Merrill, Ashish Sabharwal |
| 1810.01118 | 6251519 | 2022-10-20 08:19:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1810.01118v3 | Sinkhorn AutoEncoders | Optimal transport offers an alternative to maximum likelihood for learning generative autoencoding models. We show that minimizing the p-Wasserstein distance between the generator and the true data distribution is equivalent to the unconstrained min-min optimization of the p-Wasserstein distance between the encoder aggregated posterior and the prior in latent space, plus a reconstruction error. We also identify the role of its trade-off hyperparameter as the capacity of the generator: its Lipschitz constant. Moreover, we prove that optimizing the encoder over any class of universal approximators, such as deterministic neural networks, is enough to come arbitrarily close to the optimum. We therefore advertise this framework, which holds for any metric space and prior, as a sweet-spot of current generative autoencoding objectives. We then introduce the Sinkhorn auto-encoder (SAE), which approximates and minimizes the p-Wasserstein distance in latent space via backprogation through the Sinkhorn algorithm. SAE directly works on samples, i.e. it models the aggregated posterior as an implicit distribution, with no need for a reparameterization trick for gradients estimations. SAE is thus able to work with different metric spaces and priors with minimal adaptations. We demonstrate the flexibility of SAE on latent spaces with different geometries and priors and compare with other methods on benchmark data sets. | Giorgio Patrini, Rianne van den Berg, Patrick Forré, Marcello Carioni, Samarth Bhargav, Max Welling, Tim Genewein, Frank Nielsen |
| 2202.11097 | 352470 | 2022-10-21 13:42:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2202.11097v1 | Message passing all the way up | The message passing framework is the foundation of the immense success enjoyed by graph neural networks (GNNs) in recent years. In spite of its elegance, there exist many problems it provably cannot solve over given input graphs. This has led to a surge of research on going "beyond message passing", building GNNs which do not suffer from those limitations -- a term which has become ubiquitous in regular discourse. However, have those methods truly moved beyond message passing? In this position paper, I argue about the dangers of using this term -- especially when teaching graph representation learning to newcomers. I show that any function of interest we want to compute over graphs can, in all likelihood, be expressed using pairwise message passing -- just over a potentially modified graph, and argue how most practical implementations subtly do this kind of trick anyway. Hoping to initiate a productive discussion, I propose replacing "beyond message passing" with a more tame term, "augmented message passing". | Petar Veličković |
| 2005.02975 | 248746 | 2022-10-22 09:35:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2005.02975v3 | DisCoPy: Monoidal Categories in Python | We introduce DisCoPy, an open source toolbox for computing with monoidal categories. The library provides an intuitive syntax for defining string diagrams and monoidal functors. Its modularity allows the efficient implementation of computational experiments in the various applications of category theory where diagrams have become a lingua franca. As an example, we used DisCoPy to perform natural language processing on quantum hardware for the first time. | Giovanni de Felice, Alexis Toumi, Bob Coecke |
| 2103.01931 | 1256166 | 2022-10-29 10:18:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2103.01931v2 | Categorical Foundations of Gradient-Based Learning | We propose a categorical semantics of gradient-based machine learning algorithms in terms of lenses, parametrised maps, and reverse derivative categories. This foundation provides a powerful explanatory and unifying framework: it encompasses a variety of gradient descent algorithms such as ADAM, AdaGrad, and Nesterov momentum, as well as a variety of loss functions such as as MSE and Softmax cross-entropy, shedding new light on their similarities and differences. Our approach to gradient-based learning has examples generalising beyond the familiar continuous domains (modelled in categories of smooth maps) and can be realized in the discrete setting of boolean circuits. Finally, we demonstrate the practical significance of our framework with an implementation in Python. | G. S. H. Cruttwell, Bruno Gavranović, Neil Ghani, Paul Wilson, Fabio Zanasi |
| 1910.03656 | 774987 | 2022-11-14 09:12:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1910.03656v1 | Bayesian open games | This paper generalises the treatment of compositional game theory as introduced by the second and third authors with Ghani and Winschel, where games are modelled as morphisms of a symmetric monoidal category. From an economic modelling perspective, the existing notion of an open game is not expressive enough for many applications. This includes stochastic environments, stochastic choices by players, as well as incomplete information regarding the game being played. The current paper addresses these three issue all at once. To achieve this we make significant use of category theory, especially the 'coend optics' of Riley. | Joe Bolt, Jules Hedges, Philipp Zahn |
| 1803.05316 | 3032448 | 2022-12-19 08:41:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1803.05316v3 | Seven Sketches in Compositionality: An Invitation to Applied Category Theory | This book is an invitation to discover advanced topics in category theory through concrete, real-world examples. It aims to give a tour: a gentle, quick introduction to guide later exploration. The tour takes place over seven sketches, each pairing an evocative application, such as databases, electric circuits, or dynamical systems, with the exploration of a categorical structure, such as adjoint functors, enriched categories, or toposes. No prior knowledge of category theory is assumed. A feedback form for typos, comments, questions, and suggestions is available here: https://docs.google.com/document/d/160G9OFcP5DWT8Stn7TxdVx83DJnnf7d5GML0_FOD5Wg/edit | Brendan Fong, David I Spivak |
| 1808.01513 | 729467 | 2022-12-20 07:43:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1808.01513v2 | Toward a Spectral Theory of Cellular Sheaves | This paper outlines a program in what one might call spectral sheaf theory --- an extension of spectral graph theory to cellular sheaves. By lifting the combinatorial graph Laplacian to the Hodge Laplacian on a cellular sheaf of vector spaces over a regular cell complex, one can relate spectral data to the sheaf cohomology and cell structure in a manner reminiscent of spectral graph theory. This work gives an exploratory introduction, and includes results on eigenvalue interlacing, sparsification, effective resistance, and sheaf approximation. These results and subsequent applications are prefaced by an introduction to cellular sheaves and Laplacians. | Jakob Hansen, Robert Ghrist |
| 2102.13196 | 569372 | 2022-12-23 12:04:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2102.13196v3 | Named Tensor Notation | We propose a notation for tensors with named axes, which relieves the author, reader, and future implementers of machine learning models from the burden of keeping track of the order of axes and the purpose of each. The notation makes it easy to lift operations on low-order tensors to higher order ones, for example, from images to minibatches of images, or from an attention mechanism to multiple attention heads. After a brief overview and formal definition of the notation, we illustrate it through several examples from modern machine learning, from building blocks like attention and convolution to full models like Transformers and LeNet. We then discuss differential calculus in our notation and compare with some alternative notations. Our proposals build on ideas from many previous papers and software libraries. We hope that our notation will encourage more authors to use named tensors, resulting in clearer papers and more precise implementations. | David Chiang, Alexander M. Rush, Boaz Barak |
| 2212.09703 | 3011418 | 2022-12-23 12:25:00 | 2023-01-23 08:51:00 | http://arxiv.org/abs/2212.09703v1 | A Survey of Vectorization Methods in Topological Data Analysis | Attempts to incorporate topological information in supervised learning tasks have resulted in the creation of several techniques for vectorizing persistent homology barcodes. In this paper, we study thirteen such methods. Besides describing an organizational framework for these methods, we comprehensively benchmark them against three well-known classification tasks. Surprisingly, we discover that the best-performing method is a simple vectorization, which consists only of a few elementary summary statistics. Finally, we provide a convenient web application which has been designed to facilitate exploration and experimentation with various vectorization methods. | Dashti Ali, Aras Asaad, Maria-Jose Jimenez, Vidit Nanda, Eduardo Paluzo-Hidalgo, Manuel Soriano-Trigueros |
| 2001.12004 | 1281030 | 2022-12-26 15:41:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/2001.12004v2 | Neural MMO v1.3: A Massively Multiagent Game Environment for Training and Evaluating Neural Networks | Progress in multiagent intelligence research is fundamentally limited by the number and quality of environments available for study. In recent years, simulated games have become a dominant research platform within reinforcement learning, in part due to their accessibility and interpretability. Previous works have targeted and demonstrated success on arcade, first person shooter (FPS), real-time strategy (RTS), and massive online battle arena (MOBA) games. Our work considers massively multiplayer online role-playing games (MMORPGs or MMOs), which capture several complexities of real-world learning that are not well modeled by any other game genre. We present Neural MMO, a massively multiagent game environment inspired by MMOs and discuss our progress on two more general challenges in multiagent systems engineering for AI research: distributed infrastructure and game IO. We further demonstrate that standard policy gradient methods and simple baseline models can learn interesting emergent exploration and specialization behaviors in this setting. | Joseph Suarez, Yilun Du, Igor Mordatch, Phillip Isola |
| 0904.2012 | 381328 | 2022-12-31 11:57:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/0904.2012v1 | Simplicial Databases | In this paper, we define a category DB, called the category of simplicial databases, whose objects are databases and whose morphisms are data-preserving maps. Along the way we give a precise formulation of the category of relational databases, and prove that it is a full subcategory of DB. We also prove that limits and colimits always exist in DB and that they correspond to queries such as select, join, union, etc. One feature of our construction is that the schema of a simplicial database has a natural geometric structure: an underlying simplicial set. The geometry of a schema is a way of keeping track of relationships between distinct tables, and can be thought of as a system of foreign keys. The shape of a schema is generally intuitive (e.g. the schema for round-trip flights is a circle consisting of an edge from $A$ to $B$ and an edge from $B$ to $A$), and as such, may be useful for analyzing data. We give several applications of our approach, as well as possible advantages it has over the relational model. We also indicate some directions for further research. | David I. Spivak |
| 1906.06132 | 565730 | 2023-01-02 07:54:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1906.06132v2 | SchenQL -- A Domain-Specific Query Language on Bibliographic Metadata | Information access needs to be uncomplicated, users rather use incorrect data which is easily received than correct information which is harder to obtain. Querying bibliographic metadata from digital libraries mainly supports simple textual queries. A user's demand for answering more sophisticated queries could be fulfilled by the usage of SQL. As such means are highly complex and challenging even for trained programmers, a domain-specific query language is needed to provide a straightforward way to access data. In this paper we present SchenQL, a simple query language focused on bibliographic metadata in the area of computer science while using the vocabulary of domain-experts. By facilitating a plain syntax and fundamental aggregate functions, we propose an easy-to-learn domain-specific query language capable of search and exploration. It is suitable for domain-experts as well as casual users while still providing the possibility to answer complicated queries. A user study with computer scientists directly compared our query language to SQL and clearly demonstrated SchenQL's suitability and usefulness for given queries as well as users' acceptance. | Christin Katharina Kreutz, Michael Wolz, Ralf Schenkel |
| 1906.06132 | 565730 | 2023-01-02 07:54:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1906.06132v2 | SchenQL -- A Domain-Specific Query Language on Bibliographic Metadata | Information access needs to be uncomplicated, users rather use incorrect data which is easily received than correct information which is harder to obtain. Querying bibliographic metadata from digital libraries mainly supports simple textual queries. A user's demand for answering more sophisticated queries could be fulfilled by the usage of SQL. As such means are highly complex and challenging even for trained programmers, a domain-specific query language is needed to provide a straightforward way to access data. In this paper we present SchenQL, a simple query language focused on bibliographic metadata in the area of computer science while using the vocabulary of domain-experts. By facilitating a plain syntax and fundamental aggregate functions, we propose an easy-to-learn domain-specific query language capable of search and exploration. It is suitable for domain-experts as well as casual users while still providing the possibility to answer complicated queries. A user study with computer scientists directly compared our query language to SQL and clearly demonstrated SchenQL's suitability and usefulness for given queries as well as users' acceptance. | Christin Katharina Kreutz, Michael Wolz, Ralf Schenkel |
| 1302.6946 | 4045923 | 2023-01-02 11:52:00 | 2023-01-23 08:50:00 | http://arxiv.org/abs/1302.6946v3 | Category theory for scientists (Old version) | There are many books designed to introduce category theory to either a mathematical audience or a computer science audience. In this book, our audience is the broader scientific community. We attempt to show that category theory can be applied throughout the sciences as a framework for modeling phenomena and communicating results. In order to target the scientific audience, this book is example-based rather than proof-based. For example, monoids are framed in terms of agents acting on objects, sheaves are introduced with primary examples coming from geography, and colored operads are discussed in terms of their ability to model self-similarity. A new version with solutions to exercises will be available through MIT Press. | David I. Spivak |
| 2301.08210 | 345956 | 2023-01-23 07:44:00 | 2023-01-23 07:45:00 | http://arxiv.org/abs/2301.08210v1 | Everything is Connected: Graph Neural Networks | In many ways, graphs are the main modality of data we receive from nature. This is due to the fact that most of the patterns we see, both in natural and artificial systems, are elegantly representable using the language of graph structures. Prominent examples include molecules (represented as graphs of atoms and bonds), social networks and transportation networks. This potential has already been seen by key scientific and industrial groups, with already-impacted application areas including traffic forecasting, drug discovery, social network analysis and recommender systems. Further, some of the most successful domains of application for machine learning in previous years -- images, text and speech processing -- can be seen as special cases of graph representation learning, and consequently there has been significant exchange of information between these areas. The main aim of this short survey is to enable the reader to assimilate the key concepts in the area, and position graph representation learning in a proper context with related fields. | Petar Veličković |
| 2005.12348 | 689228 | 2023-01-26 07:29:00 | 2023-01-26 07:30:00 | http://arxiv.org/abs/2005.12348v1 | Cosheaf Representations of Relations and Dowker Complexes | The Dowker complex is an abstract simplicial complex that is constructed from a binary relation in a straightforward way. Although there are two ways to perform this construction -- vertices for the complex are either the rows or the columns of the matrix representing the relation -- the two constructions are homotopy equivalent. This article shows that the construction of a Dowker complex from a relation is a non-faithful covariant functor. Furthermore, we show that this functor can be made faithful by enriching the construction into a cosheaf on the Dowker complex. The cosheaf can be summarized by an integer weight function on the Dowker complex that is a complete isomorphism invariant for the relation. The cosheaf representation of a relation actually embodies both Dowker complexes, and we construct a duality functor that exchanges the two complexes. Finally, we explore a different cosheaf that detects the failure of the Dowker complex itself to be a faithful functor. | Michael Robinson |
| 1905.09791 | 1958608 | 2023-02-07 07:49:00 | 2023-02-07 07:49:00 | http://arxiv.org/abs/1905.09791v3 | Multi-relational Poincaré Graph Embeddings | Hyperbolic embeddings have recently gained attention in machine learning due to their ability to represent hierarchical data more accurately and succinctly than their Euclidean analogues. However, multi-relational knowledge graphs often exhibit multiple simultaneous hierarchies, which current hyperbolic models do not capture. To address this, we propose a model that embeds multi-relational graph data in the Poincar\'e ball model of hyperbolic space. Our Multi-Relational Poincar\'e model (MuRP) learns relation-specific parameters to transform entity embeddings by M\"obius matrix-vector multiplication and M\"obius addition. Experiments on the hierarchical WN18RR knowledge graph show that our Poincar\'e embeddings outperform their Euclidean counterpart and existing embedding methods on the link prediction task, particularly at lower dimensionality. | Ivana Balažević, Carl Allen, Timothy Hospedales |
| 2212.14052 | 1914825 | 2023-02-15 07:24:00 | 2023-02-15 07:26:00 | http://arxiv.org/abs/2212.14052v2 | Hungry Hungry Hippos: Towards Language Modeling with State Space Models | State space models (SSMs) have demonstrated state-of-the-art sequence modeling performance in some modalities, but underperform attention in language modeling. Moreover, despite scaling nearly linearly in sequence length instead of quadratically, SSMs are still slower than Transformers due to poor hardware utilization. In this paper, we make progress on understanding the expressivity gap between SSMs and attention in language modeling, and on reducing the hardware barrier between SSMs and attention. First, we use synthetic language modeling tasks to understand the gap between SSMs and attention. We find that existing SSMs struggle with two capabilities: recalling earlier tokens in the sequence and comparing tokens across the sequence. To understand the impact on language modeling, we propose a new SSM layer, H3, that is explicitly designed for these abilities. H3 matches attention on the synthetic languages and comes within 0.4 PPL of Transformers on OpenWebText. Furthermore, a hybrid 125M-parameter H3-attention model that retains two attention layers surprisingly outperforms Transformers on OpenWebText by 1.0 PPL. Next, to improve the efficiency of training SSMs on modern hardware, we propose FlashConv. FlashConv uses a fused block FFT algorithm to improve efficiency on sequences up to 8K, and introduces a novel state passing algorithm that exploits the recurrent properties of SSMs to scale to longer sequences. FlashConv yields 2$\times$ speedup on the long-range arena benchmark and allows hybrid language models to generate text 2.4$\times$ faster than Transformers. Using FlashConv, we scale hybrid H3-attention language models up to 2.7B parameters on the Pile and find promising initial results, achieving lower perplexity than Transformers and outperforming Transformers in zero- and few-shot learning on a majority of tasks in the SuperGLUE benchmark. | Tri Dao, Daniel Y. Fu, Khaled K. Saab, Armin W. Thomas, Atri Rudra, Christopher Ré |
| 1706.03762 | 2201700 | 2023-02-15 07:25:00 | 2023-02-15 07:25:00 | http://arxiv.org/abs/1706.03762v5 | Attention Is All You Need | The dominant sequence transduction models are based on complex recurrent or convolutional neural networks in an encoder-decoder configuration. The best performing models also connect the encoder and decoder through an attention mechanism. We propose a new simple network architecture, the Transformer, based solely on attention mechanisms, dispensing with recurrence and convolutions entirely. Experiments on two machine translation tasks show these models to be superior in quality while being more parallelizable and requiring significantly less time to train. Our model achieves 28.4 BLEU on the WMT 2014 English-to-German translation task, improving over the existing best results, including ensembles by over 2 BLEU. On the WMT 2014 English-to-French translation task, our model establishes a new single-model state-of-the-art BLEU score of 41.8 after training for 3.5 days on eight GPUs, a small fraction of the training costs of the best models from the literature. We show that the Transformer generalizes well to other tasks by applying it successfully to English constituency parsing both with large and limited training data. | Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, Illia Polosukhin |
| 2106.05081 | 1076486 | 2023-02-23 07:29:00 | 2023-02-23 07:29:00 | http://arxiv.org/abs/2106.05081v1 | Global Context Enhanced Graph Neural Networks for Session-based Recommendation | Session-based recommendation (SBR) is a challenging task, which aims at recommending items based on anonymous behavior sequences. Almost all the existing solutions for SBR model user preference only based on the current session without exploiting the other sessions, which may contain both relevant and irrelevant item-transitions to the current session. This paper proposes a novel approach, called Global Context Enhanced Graph Neural Networks (GCE-GNN) to exploit item transitions over all sessions in a more subtle manner for better inferring the user preference of the current session. Specifically, GCE-GNN learns two levels of item embeddings from session graph and global graph, respectively: (i) Session graph, which is to learn the session-level item embedding by modeling pairwise item-transitions within the current session; and (ii) Global graph, which is to learn the global-level item embedding by modeling pairwise item-transitions over all sessions. In GCE-GNN, we propose a novel global-level item representation learning layer, which employs a session-aware attention mechanism to recursively incorporate the neighbors' embeddings of each node on the global graph. We also design a session-level item representation learning layer, which employs a GNN on the session graph to learn session-level item embeddings within the current session. Moreover, GCE-GNN aggregates the learnt item representations in the two levels with a soft attention mechanism. Experiments on three benchmark datasets demonstrate that GCE-GNN outperforms the state-of-the-art methods consistently. | Ziyang Wang, Wei Wei, Gao Cong, Xiao-Li Li, Xian-Ling Mao, Minghui Qiu |
| 2006.15735 | 1942116 | 2023-02-23 07:32:00 | 2023-02-23 07:32:00 | http://arxiv.org/abs/2006.15735v2 | Predicting Customer Churn in World of Warcraft | World of Warcraft is a massively multiplayer online video game released on November 23, 2004, by Blizzard Entertainment. In contrast with traditional games only having a single upfront fee to play, WoW also has a monthly subscription to play the game. With customer subscriptions in mind, we can apply the use of churn prediction to not only predict whether a customer will unsubscribe from the service but explore the user's playing behavior to obtain more insight into user playing patterns. The churn problem is somewhat complex due to the nature of not having a one size fits all solution, as different services define churn in a variety of ways. In this paper, we explore a dataset that focuses on one year from January 1, 2008, until December 31, 2008, as it highlights the release of a major content update in the game. Machine learning is used in two aspects of this paper: Survival Analysis and Binary Classification. Firstly, we explore the dataset using the Kaplan Meier estimator to predict the duration until a customer churns, and lastly predict whether a person will churn in six months using traditional machine learning algorithms such as Logistic Regression, Support Vector Machine, KNN Classifier, and Random Forests. From the survival analysis results, WoW customers have a relatively long duration until churn, which solidifies the addictiveness of the game. Lastly, the binary classification performed in the best performing algorithm having a 96% ROC AUC score in predicting whether a customer will churn in six months. | Sulman Khan |
| 1908.03748 | 192553 | 2023-02-23 07:49:00 | 2023-02-23 07:49:00 | http://arxiv.org/abs/1908.03748v1 | Show Me Your Account: Detecting MMORPG Game Bot Leveraging Financial Analysis with LSTM | With the rapid growth of MMORPG market, game bot detection has become an essential task for maintaining stable in-game ecosystem. To classify bots from normal users, detection methods are proposed in both game client and server-side. Among various classification methods, data mining method in server-side captured unique characteristics of bots efficiently. For features used in data mining, behavioral and social actions of character are analyzed with numerous algorithms. However, bot developers can evade the previous detection methods by changing bot's activities continuously. Eventually, overall maintenance cost increases because the selected features need to be updated along with the change of bot's behavior. To overcome this limitation, we propose improved bot detection method with financial analysis. As bot's activity absolutely necessitates the change of financial status, analyzing financial fluctuation effectively captures bots as a key feature. We trained and tested model with actual data of Aion, a leading MMORPG in Asia. Leveraging that LSTM efficiently recognizes time-series movement of data, we achieved meaningful detection performance. Further on this model, we expect sustainable bot detection system in the near future. | Kyung Ho Park, Eunjo Lee, Huy Kang Kim |
| 1801.06368 | 5763302 | 2023-02-23 07:51:00 | 2023-02-23 08:00:00 | http://arxiv.org/abs/1801.06368v1 | No Silk Road for Online Gamers!: Using Social Network Analysis to Unveil Black Markets in Online Games | Online game involves a very large number of users who are interconnected and interact with each other via the Internet. We studied the characteristics of exchanging virtual goods with real money through processes called "real money trading (RMT)." This exchange might influence online game user behaviors and cause damage to the reputation of game companies. We examined in-game transactions to reveal RMT by constructing a social graph of virtual goods exchanges in an online game and identifying network communities of users. We analyzed approximately 6,000,000 transactions in a popular online game and inferred RMT transactions by comparing the RMT transactions crawled from an out-game market. Our findings are summarized as follows: (1) the size of the RMT market could be approximately estimated; (2) professional RMT providers typically form a specific network structure (either star-shape or chain) in the trading network, which can be used as a clue for tracing RMT transactions; and (3) the observed RMT market has evolved over time into a monopolized market with a small number of large-sized virtual goods providers. | Eunjo Lee, Jiyoung Woo, Hyoungshick Kim, Huy Kang Kim |
| 2301.09308 | 1143603 | 2023-03-02 10:16:00 | 2023-03-02 10:16:00 | http://arxiv.org/abs/2301.09308v1 | On the Expressive Power of Geometric Graph Neural Networks | The expressive power of Graph Neural Networks (GNNs) has been studied extensively through the Weisfeiler-Leman (WL) graph isomorphism test. However, standard GNNs and the WL framework are inapplicable for geometric graphs embedded in Euclidean space, such as biomolecules, materials, and other physical systems. In this work, we propose a geometric version of the WL test (GWL) for discriminating geometric graphs while respecting the underlying physical symmetries: permutations, rotation, reflection, and translation. We use GWL to characterise the expressive power of geometric GNNs that are invariant or equivariant to physical symmetries in terms of distinguishing geometric graphs. GWL unpacks how key design choices influence geometric GNN expressivity: (1) Invariant layers have limited expressivity as they cannot distinguish one-hop identical geometric graphs; (2) Equivariant layers distinguish a larger class of graphs by propagating geometric information beyond local neighbourhoods; (3) Higher order tensors and scalarisation enable maximally powerful geometric GNNs; and (4) GWL's discrimination-based perspective is equivalent to universal approximation. Synthetic experiments supplementing our results are available at https://github.com/chaitjo/geometric-gnn-dojo | Chaitanya K. Joshi, Cristian Bodnar, Simon V. Mathis, Taco Cohen, Pietro Liò |
| 1908.02591 | 7483813 | 2023-03-09 18:01:00 | 2023-03-09 18:01:00 | http://arxiv.org/abs/1908.02591v1 | Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics | Anti-money laundering (AML) regulations play a critical role in safeguarding financial systems, but bear high costs for institutions and drive financial exclusion for those on the socioeconomic and international margins. The advent of cryptocurrency has introduced an intriguing paradox: pseudonymity allows criminals to hide in plain sight, but open data gives more power to investigators and enables the crowdsourcing of forensic analysis. Meanwhile advances in learning algorithms show great promise for the AML toolkit. In this workshop tutorial, we motivate the opportunity to reconcile the cause of safety with that of financial inclusion. We contribute the Elliptic Data Set, a time series graph of over 200K Bitcoin transactions (nodes), 234K directed payment flows (edges), and 166 node features, including ones based on non-public data; to our knowledge, this is the largest labelled transaction data set publicly available in any cryptocurrency. We share results from a binary classification task predicting illicit transactions using variations of Logistic Regression (LR), Random Forest (RF), Multilayer Perceptrons (MLP), and Graph Convolutional Networks (GCN), with GCN being of special interest as an emergent new method for capturing relational information. The results show the superiority of Random Forest (RF), but also invite algorithmic work to combine the respective powers of RF and graph methods. Lastly, we consider visualization for analysis and explainability, which is difficult given the size and dynamism of real-world transaction graphs, and we offer a simple prototype capable of navigating the graph and observing model performance on illicit activity over time. With this tutorial and data set, we hope to a) invite feedback in support of our ongoing inquiry, and b) inspire others to work on this societally important challenge. | Mark Weber, Giacomo Domeniconi, Jie Chen, Daniel Karl I. Weidele, Claudio Bellei, Tom Robinson, Charles E. Leiserson |
| 1908.02591 | 7483813 | 2023-03-09 18:01:00 | 2023-03-09 18:01:00 | http://arxiv.org/abs/1908.02591v1 | Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics | Anti-money laundering (AML) regulations play a critical role in safeguarding financial systems, but bear high costs for institutions and drive financial exclusion for those on the socioeconomic and international margins. The advent of cryptocurrency has introduced an intriguing paradox: pseudonymity allows criminals to hide in plain sight, but open data gives more power to investigators and enables the crowdsourcing of forensic analysis. Meanwhile advances in learning algorithms show great promise for the AML toolkit. In this workshop tutorial, we motivate the opportunity to reconcile the cause of safety with that of financial inclusion. We contribute the Elliptic Data Set, a time series graph of over 200K Bitcoin transactions (nodes), 234K directed payment flows (edges), and 166 node features, including ones based on non-public data; to our knowledge, this is the largest labelled transaction data set publicly available in any cryptocurrency. We share results from a binary classification task predicting illicit transactions using variations of Logistic Regression (LR), Random Forest (RF), Multilayer Perceptrons (MLP), and Graph Convolutional Networks (GCN), with GCN being of special interest as an emergent new method for capturing relational information. The results show the superiority of Random Forest (RF), but also invite algorithmic work to combine the respective powers of RF and graph methods. Lastly, we consider visualization for analysis and explainability, which is difficult given the size and dynamism of real-world transaction graphs, and we offer a simple prototype capable of navigating the graph and observing model performance on illicit activity over time. With this tutorial and data set, we hope to a) invite feedback in support of our ongoing inquiry, and b) inspire others to work on this societally important challenge. | Mark Weber, Giacomo Domeniconi, Jie Chen, Daniel Karl I. Weidele, Claudio Bellei, Tom Robinson, Charles E. Leiserson |