publications

2024

1. Preprint

   Sharp Bounds for Poly-GNNs and the Effect of Graph Noise

   Vinas, Luciano, and Amini, Arash A.

   Preprint 2024

   Abs arXiv

   We investigate the classification performance of graph neural networks with graph-polynomial features, poly-GNNs, on the problem of semi-supervised node classification. We analyze poly-GNNs under a general contextual stochastic block model (CSBM) by providing a sharp characterization of the rate of separation between classes in their output node representations. A question of interest is whether this rate depends on the depth of the network k, i.e., whether deeper networks can achieve a faster separation? We provide a negative answer to this question: for a sufficiently large graph, a depth k>1 poly-GNN exhibits the same rate of separation as a depth k=1 counterpart. Our analysis highlights and quantifies the impact of “graph noise” in deep GNNs and shows how noise in the graph structure can dominate other sources of signal in the graph, negating any benefit further aggregation provides. Our analysis also reveals subtle differences between even and odd-layered GNNs in how the feature noise propagates.

2. Preprint

   Network two-sample test for block models

   Nguen, Chung Kyong, Padilla, Oscar Hernan Madrid, and Amini, Arash A.

   2024

   Abs arXiv

   We consider the two-sample testing problem for networks, where the goal is to determine whether two sets of networks originated from the same stochastic model. Assuming no vertex correspondence and allowing for different numbers of nodes, we address a fundamental network testing problem that goes beyond simple adjacency matrix comparisons. We adopt the stochastic block model (SBM) for network distributions, due to their interpretability and the potential to approximate more general models. The lack of meaningful node labels and vertex correspondence translate to a graph matching challenge when developing a test for SBMs. We introduce an efficient algorithm to match estimated network parameters, allowing us to properly combine and contrast information within and across samples, leading to a powerful test. We show that the matching algorithm, and the overall test are consistent, under mild conditions on the sparsity of the networks and the sample sizes, and derive a chi-squared asymptotic null distribution for the test. Through a mixture of theoretical insights and empirical validations, including experiments with both synthetic and real-world data, this study advances robust statistical inference for complex network data.

3. BA

   Bayesian Community Detection for Networks with Covariates

   Shen, Luyi,  Amini, Arash, Josephs, Nathaniel, and Lin, Lizhen

   Bayesian Analysis 2024

   HTML
4. RLJ

   Graph Neural Thompson Sampling

   Wu, Shuang, and Amini, Arash A.

   Reinforcement Learning Journal (RLJ) 2024

   arXiv
5. TPAMI

   Federated Learning of Generalized Linear Causal Networks

   Ye, Qiaoling,  Amini, Arash A., and Zhou, Qing

   IEEE Transactions on Pattern Analysis and Machine Intelligence 2024

   HTML
6. BA

   Hierarchical Stochastic Block Model for Community Detection in Multiplex Networks

   Amini, Arash, Paez, Marina, and Lin, Lizhen

   Bayesian Analysis 2024

   arXiv HTML Code

2023

1. Preprint

   Learning non-graphical conditional independence structures via the neighbourhood lattice

   Amini, Arash A., Aragam, Bryon, and Qing Zhou,

   Preprint 2023
2. Preprint

   Simplifying GNN Performance with Low Rank Kernel Models

   Vinas, Luciano, and Amini, Arash A.

   Preprint 2023

   arXiv
3. Preprint

   Step and Smooth Decompositions as Topological Clustering

   Vinas, Luciano, and Amini, Arash A.

   Preprint 2023

   arXiv
4. Preprint

   Nested stochastic block model for simultaneously clustering networks and nodes

   Josephs, Nathaniel, Amini, Arash A, Paez, Marina, and Lin, Lizhen

   Preprint 2023

   arXiv
5. ICLR

   Statistical Guarantees for Consensus Clustering

   Zhou, Zhixin, Dudeja, Gautam, and Amini, Arash A.

   In ICLR 2023
6. AOS

   Adjusted Chi-Square Test for Degree-Corrected Block Models

   Zhang, Linfan, and Amini, Arash A.

   The Annals of Statistics 2023

   HTML PDF Code
7. ESA

   Performance evaluation of automotive dealerships using grouped mixture of regressions

   Almohri, Haidar, Chinnam, Ratna Babu, and Amini, Arash A.

   Expert Systems with Applications 2023

2022

1. MNRAS

   Finding quadruply imaged quasars with machine learning. I. Methods

   Akhazhanov, A., More, A.,  Amini, A., Hazlett, C., Treu, T.,  and others.

   Monthly Notices of the Royal Astronomical Society 2022

   arXiv HTML PDF
2. AISTATS

   On perfectness in Gaussian graphical models

   Amini, Arash, Aragam, Bryon, and Zhou, Qing

   In International Conference on Artificial Intelligence and Statistics 2022

   arXiv HTML PDF Code
3. NeurIPS

   Target alignment in truncated kernel ridge regression

   Amini, Arash A, Baumgartner, Richard, and Feng, Dai

   In NeurIPS 2022

   arXiv Code
4. Preprint

   A non-graphical representation of conditional independence via the neighbourhood lattice

   Amini, Arash A, Aragam, Bryon, and Zhou, Qing

   Preprint 2022

   arXiv

2021

1. EJS

   Spectrally-truncated kernel ridge regression and its free lunch

   Amini, Arash A.

   Electronic Journal of Statistics 2021

   arXiv HTML PDF
2. AOS

   Concentration of kernel matrices with application to kernel spectral clustering

   Amini, Arash A., and Razaee, Zahra S.

   The Annals of Statistics 2021

   arXiv HTML PDF
3. NeurIPS

   Label consistency in overfitted generalized k-means

   Zhang, Linfan, and Amini, Arash A.

   Neural Information Processing Systems (NeurIPS) 2021

   HTML PDF Supp

2020

1. NetSci-X

   Approximate Identification of the Optimal Epidemic Source in Complex Networks

   Kazemitabar, S. Jalil, and Amini, Arash A.

   In Proceedings of NetSci-X 2020: Sixth International Winter School and Conference on Network Science 2020

   Abs arXiv HTML PDF Code

   We consider the problem of identifying the source of a network epidemic from a complete snapshot of the infected nodes. We take a fully statistical approach and derive novel recursions to compute the Bayes optimal solution, under a heterogeneous susceptible-infected (SI) epidemic model. Our analysis is time and rate independent, and holds for general network topologies. We then provide two highly scalable algorithms for solving these recursions, a mean-field approximation and a greedy approach, and evaluate their performance on real and synthetic networks. Previous work on the problem has mostly focused on tree-like network topologies. Real networks are far from tree-like and an emphasis will be given to networks with high transitivity, such as social networks and those with communities. We show that on such networks, our approaches significantly outperform popular geometric and spectral centrality measures, most of which perform no better than random guessing.

2. JMLR

   Optimal bipartite network clustering

   Zhou, Zhixin, and Amini, Arash A.

   Journal of Machine Learning Research 2020

   arXiv HTML PDF
3. TPAMI

   Optimizing regularized Cholesky score for order-based learning of Bayesian networks

   Ye, Qiaoling,  Amini, Arash A., and Zhou, Qing

   IEEE Transactions on Pattern Analysis and Machine Intelligence 2020

   arXiv HTML
4. NeurIPS

   The Potts-Ising model for discrete multivariate data

   Razaee, Zahra, and Amini, Arash A.

   Advances in Neural Information Processing Systems 2020

   HTML Code
5. JSAIT

   Generalized Autoregressive Linear Models for Discrete High-Dimensional Data

   Pandit, Parthe, Sahraee-Ardakan, Mojtaba,  Amini, Arash A., Rangan, Sundeep, and Fletcher, Alyson K.

   IEEE Journal on Selected Areas in Information Theory 2020

   HTML
6. Stat Med

   On the properties of the toxicity index and its statistical efficiency

   Razaee, Zahra S,  Amini, Arash A., Diniz, Márcio A, Tighiouart, Mourad, Yothers, Greg,  and others.

   Statistics in Medicine 2020

   HTML PDF

2019

1. NeurIPS

   Globally optimal score-based learning of directed acyclic graphs in high-dimensions

   Aragam, Bryon,  Amini, Arash, and Zhou, Qing

   In Advances in Neural Information Processing Systems 2019

   HTML PDF Supp
2. JMLR

   Matched Bipartite Block Model with Covariates.

   Razaee, Zahra S,  Amini, Arash A., and Li, Jingyi Jessica

   Journal of Machine Learning Research 2019

   arXiv HTML PDF Code
3. JMLR

   Analysis of spectral clustering algorithms for community detection: the general bipartite setting

   Zhou, Zhixin, and Amini, Arash A.

   Journal of Machine Learning Research 2019

   arXiv HTML PDF
4. AISTATS

   Sparse Multivariate Bernoulli Processes in High Dimensions

   Pandit, Parthe, Sahraee-Ardakan, Mojtaba,  Amini, Arash, Rangan, Sundeep, and Fletcher, Alyson K.

   In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics 2019

   Abs HTML PDF Supp

   We consider the problem of estimating the parameters of a multivariate Bernoulli process with auto-regressive feedback in the high-dimensional setting where the number of samples available is much less than the number of parameters. This problem arises in learning interconnections of networks of dynamical systems with spiking or binary valued data. We also allow the process to depend on its past up to a lag p, for a general p ≥1, allowing for more realistic modeling in many applications. We propose and analyze an \ell_1-regularized maximum likelihood (ML) estimator under the assumption that the parameter tensor is approximately sparse. Rigorous analysis of such estimators is made challenging by the dependent and non-Gaussian nature of the process as well as the presence of the nonlinearities and multi-level feedback. We derive precise upper bounds on the mean-squared estimation error in terms of the number of samples, dimensions of the process, the lag p and other key statistical properties of the model. The ideas presented can be used in the rigorous high-dimensional analysis of regularized M-estimators for other sparse nonlinear and non-Gaussian processes with long-range dependence.

5. Tech Report

   Exact slice sampler for Hierarchical Dirichlet Processes

   Amini, Arash A., Paez, Marina, Lin, Lizhen, and Razaee, Zahra S.

   Technical Report 2019

   Abs arXiv Code

   We propose an exact slice sampler for Hierarchical Dirichlet process (HDP) and its associated mixture models (Teh et al., 2006). Although there are existing MCMC algorithms for sampling from the HDP, a slice sampler has been missing from the literature. Slice sampling is well-known for its desirable properties including its fast mixing and its natural potential for parallelization. On the other hand, the hierarchical nature of HDPs poses challenges to adopting a full-fledged slice sampler that automatically truncates all the infinite measures involved without ad-hoc modifications. In this work, we adopt the powerful idea of Bayesian variable augmentation to address this challenge. By introducing new latent variables, we obtain a full factorization of the joint distribution that is suitable for slice sampling. Our algorithm has several appealing features such as (1) fast mixing; (2) remaining exact while allowing natural truncation of the underlying infinite-dimensional measures, as in (Kalli et al., 2011), resulting in updates of only a finite number of necessary atoms and weights in each iteration; and (3) being naturally suited to parallel implementations. The underlying principle for joint factorization of the full likelihood is simple and can be applied to many other settings, such as designing sampling algorithms for general dependent Dirichlet process (DDP) models.

6. Tech Report

   On the support recovery of marginal regression

   Kazemitabar, S. Jalil,  Amini, Arash A., and Talwalkar, Ameet

   Technical Report 2019

   Abs arXiv

   Leading methods for support recovery in high-dimensional regression, such as Lasso, have been well-studied and their limitations in the context of correlated design have been characterized with precise incoherence conditions. In this work, we present a similar treatment of selection consistency for marginal regression (MR), a computationally efficient family of methods with connections to decision trees. Selection based on marginal regression is also referred to as covariate screening or independence screening and is a popular approach in applied work, especially in ultra high-dimensional settings. We identify the underlying factors—which we denote as \emphMR incoherence—affecting MR’s support recovery performance. Our near complete characterization provides a much more nuanced and optimistic view of MR in comparison to previous works. To ground our results, we provide a broad taxonomy of results for leading feature selection methods, relating the behavior of Lasso, OMP, SIS, and MR. We also lay the foundation for interesting generalizations of our analysis, e.g., to non-linear feature selection methods and to more general regression frameworks such as a general additive models.

7. Tech Report

   The neighborhood lattice for encoding partial correlations in a Hilbert space

   Amini, Arash A., Aragam, Bryon, and Zhou, Qing

   2019

   Abs arXiv

   Neighborhood regression has been a successful approach in graphical and structural equation modeling, with applications to learning undirected and directed graphical models. We extend these ideas by defining and studying an algebraic structure called the neighborhood lattice based on a generalized notion of neighborhood regression. We show that this algebraic structure has the potential to provide an economic encoding of all conditional independence statements in a Gaussian distribution (or conditional uncorrelatedness in general), even in the cases where no graphical model exists that could "perfectly" encode all such statements. We study the computational complexity of computing these structures and show that under a sparsity assumption, they can be computed in polynomial time, even in the absence of the assumption of perfectness to a graph. On the other hand, assuming perfectness, we show how these neighborhood lattices may be "graphically" computed using the separation properties of the so-called partial correlation graph. We also draw connections with directed acyclic graphical models and Bayesian networks. We derive these results using an abstract generalization of partial uncorrelatedness, called partial orthogonality, which allows us to use algebraic properties of projection operators on Hilbert spaces to significantly simplify and extend existing ideas and arguments. Consequently, our results apply to a wide range of random objects and data structures, such as random vectors, data matrices, and functions.

2018

1. AOS

   On semidefinite relaxations for the block model

   Amini, A. A., and Levina, E.

   The Annals of Statistics 2018

   arXiv HTML PDF Code

2017

1. NeurIPS

   Variable Importance Using Decision Trees

   Kazemitabar, Jalil,  Amini, Arash A., Bloniarz, Adam, and Talwalkar, Ameet S

   In Advances in Neural Information Processing Systems 30 2017

   HTML PDF Supp
2. EJS

   Structured regression models for high-dimensional spatial spectroscopy data

   Amini, Arash A., Levina, Elizaveta, and Shedden, Kerby A.

   Electron. J. Statist. 2017

   arXiv HTML
3. Tech Report

   Partial correlation graphs and the neighborhood lattice

   Amini, Arash A., Aragam, Bryon, and Zhou, Qing

   2017

   Abs arXiv

   We define and study partial correlation graphs (PCGs) with variables in a general Hilbert space and their connections to generalized neighborhood regression, without making any distributional assumptions. Using operator-theoretic arguments, and especially the properties of projection operators on Hilbert spaces, we show that these neighborhood regressions have the algebraic structure of a lattice, which we call a neighborhood lattice. This lattice property significantly reduces the number of conditions one has to check when testing all partial correlation relations among a collection of variables. In addition, we generalize the notion of perfectness in graphical models for a general PCG to this Hilbert space setting, and establish that almost all Gram matrices are perfect. Under this perfectness assumption, we show how these neighborhood lattices may be "graphically" computed using separation properties of PCGs. We also discuss extensions of these ideas to directed models, which present unique challenges compared to their undirected counterparts. Our results have implications for multivariate statistical learning in general, including structural equation models, subspace clustering, and dimension reduction. For example, we discuss how to compute neighborhood lattices efficiently and furthermore how they can be used to reduce the sample complexity of learning directed acyclic graphs. Our work demonstrates that this abstract viewpoint via projection operators significantly simplifies existing ideas and arguments from the graphical modeling literature, and furthermore can be used to extend these ideas to more general nonparametric settings.

2015

1. Tech Report

   Identifiability of Gaussian DAGs in the equal-variance case: A linear-algebraic proof

   Amini, A. A.

   Technical Report 2015
2. Tech Report

   Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression

   Aragam, Bryon,  Amini, Arash A., and Zhou, Qing

   2015

   Abs arXiv

   We study a family of regularized score-based estimators for learning the structure of a directed acyclic graph (DAG) for a multivariate normal distribution from high-dimensional data with p≫n. Our main results establish support recovery guarantees and deviation bounds for a family of penalized least-squares estimators under concave regularization without assuming prior knowledge of a variable ordering. These results apply to a variety of practical situations that allow for arbitrary nondegenerate covariance structures as well as many popular regularizers including the MCP, SCAD, \ell_0 and \ell_1. The proof relies on interpreting a DAG as a recursive linear structural equation model, which reduces the estimation problem to a series of neighbourhood regressions. We provide a novel statistical analysis of these neighbourhood problems, establishing uniform control over the superexponential family of neighbourhoods associated with a Gaussian distribution. We then apply these results to study the statistical properties of score-based DAG estimators, learning causal DAGs, and inferring conditional independence relations via graphical models. Our results yield—for the first time—finite-sample guarantees for structure learning of Gaussian DAGs in high-dimensions via score-based estimation.

2013

1. Preprint

   Bayesian inference as iterated random functions with applications to sequential inference in graphical models

   Amini, A. A., and Nguyen, X.

   Preprint 2013

   arXiv
2. NeurIPS

   Bayesian inference as iterated random functions with applications to sequential inference in graphical models

   Amini, A. A., and Nguyen, X.

   In Neural Information Processing Systems (NIPS) 2013

   HTML PDF
3. AOS

   Pseudo-likelihood methods for community detection in large sparse networks

   Amini, A. A., Chen, A., Bickel, P. J., and Levina, E.

   The Annals of Statistics 2013

   arXiv HTML Code
4. ITIT

   Sequential Detection of Multiple Change Points in Networks: A Graphical Model Approach

   Amini, A. A., and Nguyen, X.

   IEEE Transactions on Information Theory 2013

   HTML

2012

1. ISIT

   Message-passing sequential detection of multiple change points in networks

   Nguyen, X.,  Amini, A. A., and Rajagopal, R.

   In IEEE International Symposium on Information Theory (ISIT) 2012

   HTML
2. JAT

   Approximation properties of certain operator-induced norms on Hilbert spaces

   Amini, A. A., and Wainwright, M. J.

   Journal of Approximation Theory 2012

   arXiv HTML PDF
3. AOS

   Sampled forms of functional PCA in reproducing kernel Hilbert spaces

   Amini, A. A., and Wainwright, M. J.

   The Annals of Statistics 2012

   arXiv HTML PDF

2009

1. AOS

   High-dimensional analysis of semidefinite relaxations for sparse principal components

   Amini, A. A., and Wainwright, M. J.

   The Annals of Statistics 2009

   HTML PDF

2008

1. ISIT

   High-dimensional analysis of semidefinite relaxations for sparse principal components

   Amini, A. A., and Wainwright, M. J.

   In IEEE International Symposium on Information Theory (ISIT) 2008

   HTML

2006

1. MaxEnt

   A fast method for sparse component analysis based on iterative detection-projection

   Amini, A. A., Babai-Zadeh, M., and Jutten, C.

   In Bayesian Inference and Maximum Entropy Methods in Science and Engineering (MaxEnt) 2006
2. EUSIPCO

   A new approach for sparse decomposition and sparse source separation

   Amini, A. A., Babaie-Zadeh, M., and Jutten, C.

   In European Signal Processing Conference (EUSIPCO) 2006