Search

Data structures known as $k$-d trees have numerous applications in scientific computing, particularly in areas of modern statistics and data science such as range search in decision trees, clustering, nearest neighbors search, local regression, and so forth. In this article we present a scalable mechanism to construct $k$-d trees for distributed data, based on approximating medians for each recursive subdivision of the data. We provide theoretical guarantees of the quality of approximation using this approach, along with a simulation study quantifying the accuracy and scalability of our proposed approach in practice., 34 pages, 3 figures; submitted for publication

Harnessing distributed computing environments to build scalable inference algorithms for very large data sets is a core challenge across the broad mathematical sciences. Here we provide a theoretical framework to do so along with fully implemented examples of scalable algorithms with performance guarantees. We begin by formalizing the class of statistics which admit straightforward calculation in such environments through independent parallelization. We then show how to use such statistics to approximate arbitrary functional operators, thereby providing practitioners with a generic approximate inference procedure that does not require data to reside entirely in memory. We characterize the $L^2$ approximation properties of our approach, and then use it to treat two canonical examples that arise in large-scale statistical analyses: sample quantile calculation and local polynomial regression. A variety of avenues and extensions remain open for future work., Comment: 74 pages, 3 figures; submitted for publication

We adopt the statistical framework on robustness proposed by Watson and Holmes in 2016 and then tackle the practical challenges that hinder its applicability to network models. The goal is to evaluate how the quality of an inference for a network feature degrades when the assumed model is misspecified. Decision theory methods aimed to identify model missespecification are applied in the context of network data with the goal of investigating the stability of optimal actions to perturbations to the assumed model. Here the modified versions of the model are contained within a well defined neighborhood of model space. Our main challenge is to combine stochastic optimization and graph limits tools to explore the model space. As a result, a method for robustness on exchangeable random networks is developed. Our approach is inspired by recent developments in the context of robustness and recent works in the robust control, macroeconomics and financial mathematics literature and more specifically and is based on the concept of graphon approximation through its empirical graphon., 34 pages, 5 figures

Some of the most used sampling mechanisms that implicitly leverage a social network depend on tuning parameters; for instance, Respondent-Driven Sampling (RDS) is specified by the number of seeds and maximum number of referrals. We are interested in the problem of optimizing these sampling mechanisms with respect to their tuning parameters in order to optimize the inference on a population quantity, where such quantity is a function of the network and measurements taken at the nodes. This is done by formulating the problem in terms of decision theory and information theory, in turn. We discuss how the approaches discussed in this paper relate, via theoretical results, to other formalisms aimed to compare sampling designs, namely sufficiency and the Goel-DeGroot Criterion. The optimization procedure for different network sampling mechanisms is illustrated via simulations in the fashion of the ones used for Bayesian clinical trials., 21 pages, 1 figure

The topology of any complex system is key to understanding its structure and function. Fundamentally, algebraic topology guarantees that any system represented by a network can be understood through its closed paths. The length of each path provides a notion of scale, which is vitally important in characterizing dominant modes of system behavior. Here, by combining topology with scale, we prove the existence of universal features which reveal the dominant scales of any network. We use these features to compare several canonical network types in the context of a social media discussion which evolves through the sharing of rumors, leaks and other news. Our analysis enables for the first time a universal understanding of the balance between loops and tree-like structure across network scales, and an assessment of how this balance interacts with the spreading of information online. Crucially, our results allow networks to be quantified and compared in a purely model-free way that is theoretically sound, fully automated, and inherently scalable., Comment: 95 pages, 10 figures, 2 algorithms

We characterize the large-sample properties of network modularity in the presence of covariates, under a natural and flexible nonparametric null model. This provides for the first time an objective measure of whether or not a particular value of modularity is meaningful. In particular, our results quantify the strength of the relation between observed community structure and the interactions in a network. Our technical contribution is to provide limit theorems for modularity when a community assignment is given by nodal features or covariates. These theorems hold for a broad class of network models over a range of sparsity regimes, as well as weighted, multi-edge, and power-law networks. This allows us to assign $p$-values to observed community structure, which we validate using several benchmark examples in the literature. We conclude by applying this methodology to investigate a multi-edge network of corporate email interactions., 56 pages, 4 figures; submitted for publication

The present paper provides a comprehensive study of de-noising properties of frames and, in particular, tight frames, which constitute one of the most popular tools in contemporary signal processing. The objective of the paper is to bridge the existing gap between mathematical and statistical theories on one hand and engineering practice on the other and explore how one can take advantage of a specific structure of a frame in contrast to an arbitrary collection of vectors or an orthonormal basis. For both the general and the tight frames, the paper presents a set of practically implementable de-noising techniques which take frame induced correlation structures into account. These results are supplemented by an examination of the case when the frame is constructed as a collection of orthonormal bases. In particular, recommendations are given for aggregation of the estimators at the stage of frame coefficients. The paper is concluded by a finite sample simulation study which confirms that taking frame structure and frame induced correlations into account indeed improves de-noising precision., Comment: 22 pages, 2 figures

The analysis of datasets taking the form of simple, undirected graphs continues to gain in importance across a variety of disciplines. Two choices of null model, the logistic-linear model and the implicit log-linear model, have come into common use for analyzing such network data, in part because each accounts for the heterogeneity of network node degrees typically observed in practice. Here we show how these both may be viewed as instances of a broader class of null models, with the property that all members of this class give rise to essentially the same likelihood-based estimates of link probabilities in sparse graph regimes. This facilitates likelihood-based computation and inference, and enables practitioners to choose the most appropriate null model from this family based on application context. Comparative model fits for a variety of network datasets demonstrate the practical implications of our results., 12 pages, 2 figures; submitted for publication

This article discusses the properties of extremes of degree sequences calculated from network data. We introduce the notion of a normalized degree, in order to permit a comparison of degree sequences between networks with differing numbers of nodes. We model each normalized degree as a bounded continuous random variable, and determine the properties of the ordered k-maxima and minima of the normalized network degrees when they comprise a random sample from a Beta distribution. In this setting, their means and variances take a simplified form given by their ordering, and we discuss the relation of these quantities to other prescribed decays such as power laws. We verify the derived properties from simulated sets of normalized degrees, and discuss possible extensions to more flexible classes of distributions., Comment: 8 pages, 1 figure

We derive the sampling properties of random networks based on weights whose pairwise products parameterize independent Bernoulli trials. This enables an understanding of many degree-based network models, in which the structure of realized networks is governed by properties of their degree sequences. We provide exact results and large-sample approximations for power-law networks and other more general forms. This enables us to quantify sampling variability both within and across network populations, and to characterize the limiting extremes of variation achievable through such models. Our results highlight that variation explained through expected degree structure need not be attributed to more complicated generative mechanisms., Comment: 31 pages, 3 figures, submitted for publication

Covariance matrix estimates are an essential part of many signal processing algorithms, and are often used to determine a low-dimensional principal subspace via their spectral decomposition. However, exact eigenanalysis is computationally intractable for sufficiently high-dimensional matrices, and in the case of small sample sizes, sample eigenvalues and eigenvectors are known to be poor estimators of their population counterparts. To address these issues, we propose a covariance estimator that is computationally efficient while also performing shrinkage on the sample eigenvalues. Our approach is based on the Nystr��m method, which uses a data-dependent orthogonal projection to obtain a fast low-rank approximation of a large positive semidefinite matrix. We provide a theoretical analysis of the error properties of our estimator as well as empirical results, including examples of its application to adaptive beamforming and image denoising.

Graphs and networks provide a canonical representation of relational data, with massive network data sets becoming increasingly prevalent across a variety of scientific fields. Although tools from mathematics and computer science have been eagerly adopted by practitioners in the service of network inference, they do not yet comprise a unified and coherent framework for the statistical analysis of large-scale network data. This paper serves as both an introduction to the topic and a first step toward formal inference procedures. We develop and illustrate our arguments using the example of hypothesis testing for network structure. We invoke a generalized likelihood ratio framework and use it to highlight the growing number of topics in this area that require strong contributions from statistical science. We frame our discussion in the context of previous work from across a variety of disciplines, and conclude by outlining fundamental statistical challenges whose solutions will in turn serve to advance the science of network inference., 16 pages, 6 figures; submitted for publication