Logistic regression is a key method for modeling the probability of a binary outcome based on a collection of covariates. However, the classical formulation of logistic regression relies on the independent sampling assumption, which is often violated when the outcomes interact through an underlying network structure, such as over a temporal/spatial domain or on a social network. This necessitates the development of models that can simultaneously handle both the network 'peer-effect' (arising from neighborhood interactions) and the effect of (possibly) high-dimensional covariates. In this paper, we develop a framework for incorporating such dependencies in a high-dimensional logistic regression model by introducing a quadratic interaction term, as in the Ising model, designed to capture the pairwise interactions from the underlying network. The resulting model can also be viewed as an Ising model, where the node-dependent external fields linearly encode the high-dimensional covariates. We propose a penalized maximum pseudo-likelihood method for estimating the network peer-effect and the effect of the covariates (the regression coefficients), which, in addition to handling the high-dimensionality of the parameters, conveniently avoids the computational intractability of the maximum likelihood approach. Under various standard regularity conditions, we show that the corresponding estimate attains the classical high-dimensional rate of consistency. In particular, our results imply that even under network dependence it is possible to consistently estimate the model parameters at the same rate as in classical (independent) logistic regression, when the true parameter is sparse and the underlying network is not too dense. Consequently, we derive the rates of consistency of our proposed estimator for various natural graph ensembles, such as bounded degree graphs, sparse Erd\H{o}s-Rényi random graphs, and stochastic block models. We also develop an efficient algorithm for computing the estimates and validate our theoretical results in numerical experiments. An application to selecting genes in clustering spatial transcriptomics data is also discussed.

In this paper we consider the uniformity testing problem for high-dimensional discrete distributions (multinomials) under sparse alternatives. Specifically, we derive sharp detection thresholds for testing, based on n samples, whether a discrete distribution supported on d elements differs from the uniform distribution in at most s (out of the d) coordinates and is$\varepsilon $-far (in total variation distance) from uniformity. Our results reveal various interesting phase transitions which depend on the interplay of the sample size n and the signal strength$\varepsilon $with the dimension d and the sparsity level s. For instance, if the sample size is less than a threshold (which depends on d and s), then all tests are asymptotically powerless, irrespective of the magnitude of the signal strength. On the other hand, if the sample size is above the threshold, then the detection boundary undergoes a further phase transition depending on the signal strength. Here, a$\chi ^{2}$-type test attains the detection boundary in the dense regime, whereas in the sparse regime a Bonferroni correction of two maximum-type tests and a version of the Higher Criticism test is optimal up to sharp constants. These results combined provide a complete description of the phase diagram for the sparse uniformity testing problem across all regimes of the parameters n, d, s, and$\varepsilon $. One of the challenges in dealing with multinomials is that the parameters are always constrained to lie in the simplex. This results in a layered phase transition phenomenon in the parameter space. Specifically, there is a critical sample complexity (depending only on d) below which all tests are asymptotically powerless irrespective of the signal strength and above which there is a critical threshold for the signal strength that determines testability.

The$\boldsymbol {\beta } $-model for random graphs is commonly used for representing pairwise interactions in a network with degree heterogeneity. Going beyond pairwise interactions, Stasi et al. (2014) introduced the hypergraph$\boldsymbol {\beta } $-model for capturing degree heterogeneity in networks with higher-order (multi-way) interactions. In this paper we initiate the rigorous study of the hypergraph$\boldsymbol {\beta } $-model with multiple layers, which allows for hyperedges of different sizes across the layers. To begin with, we derive the rates of convergence of the maximum likelihood (ML) estimates and establish their minimax rate optimality. We also derive the limiting distribution of the ML estimates and construct asymptotically valid confidence intervals for the model parameters. Next, we consider the goodness-of-fit problem in the hypergraph$\boldsymbol {\beta } $-model. Specifically, we establish the asymptotic normality of the likelihood ratio (LR) test under the null hypothesis, derive its detection threshold, and also its limiting power at the threshold. Interestingly, the detection threshold of the LR test turns out to be minimax optimal, that is, all tests are asymptotically powerless below this threshold. The theoretical results are further validated in numerical experiments. In addition to developing the theoretical framework for estimation and inference for hypergraph$\boldsymbol {\beta } $-models, the above results fill a number of gaps in the graph$\boldsymbol {\beta } $-model literature, such as the minimax optimality of the ML estimates and the non-null properties of the LR test, which, to the best of our knowledge, have not been studied before.

In this paper we study the two-sample problem for inhomogeneous Erdős-Rényi (IER), random graph models, in the $L_r$ norm, in the high-dimensional regime where the number of samples is smaller or comparable to the size of the graphs. Given two symmetric matrices $P, Q \in [0, 1]^{n \times n}$ (with zeros on the diagonals), the two-sample problem for IER graphs (with respect to the $L_r$ norm $||\cdot||_r$) is to test the hypothesis $H_0: P=Q$ versus $H_1: ||P-Q||_r \geq \varepsilon$, given a sample of $m$ graphs from the respective distributions. In this paper, we obtain the optimal sample complexity for testing in the $L_r$-norm, for all integers $r \geq 1$. We also derive the asymptotic distribution of the optimal tests under $H_0$ and develop a method for consistently estimating their variances. This allows us to efficiently implement the optimal tests with precise asymptotic level and establish their asymptotic consistency. We validate our theoretical results by numerical experiments for various natural IER models.

The hardcore model on a graph$G$with parameter$\lambda > 0$is a probability measure on the collection of all independent sets of$G$, that assigns to each independent set$I$a probability proportional to$\lambda ^{|I|}$. In this paper we consider the problem of estimating the parameter$\lambda $given a single sample from the hardcore model on a graph$G$. To bypass the computational intractability of the maximum likelihood method, we use the maximum pseudo-likelihood (MPL) estimator, which for the hardcore model has a surprisingly simple closed form expression. We show that for any sequence of graphs$\{G_{N}\}_{N \geq 1}$, where$G_{N}$is a graph on$N$vertices, the MPL estimate of$\lambda $is$\sqrt {N}$-consistent (that is, it converges to the true parameter at rate$1/\sqrt {N}$), whenever the graph sequence has uniformly bounded average degree. We then extend our methods to obtain estimates for the vector of activity parameters in general$H$-coloring models, in which restrictions between adjacent colors are encoded by a constraint graph$H$. These constitute an important class of Markov random fields that includes all hard-constraint models, which arise in a broad array of fields including combinatorics, statistical physics, and communication networks. Given a single sample from an$H$-coloring model, we derive sufficient conditions under which the MPL estimate is$\sqrt {N}$-consistent. Moreover, we verify the sufficient conditions for$H$-coloring models for which there is at least one ‘unconstrained’ color (that is, there exists at least one vertex in the constraint graph$H$that is connected to all vertices), as long as the graph sequence has uniformly bounded average degree. This applies to many$H$-coloring examples such as the Widom-Rowlinson and multi-state hard-core models. On the other hand, for the$q$-coloring model, which falls outside this class, we show that the condition can fail and consistent estimation may be impossible even for graphs with bounded average degree. Nevertheless, we show that the MPL estimate is$\sqrt {N}$-consistent in the$q$-coloring model when$\{G_{N}\}_{N \geq 1}$has bounded average double neighborhood. The presence of hard constraints, as opposed to soft constraints, leads to new challenges, and our proofs entail applications of the method of exchangeable pairs as well as combinatorial arguments that employ the probabilistic method.

Hypothesis testing of random networks is an emerging area of modern research, especially in the high-dimensional regime, where the number of samples is smaller or comparable to the size of the graph. In this paper we consider the goodness-of-fit testing problem for large inhomogeneous random (IER) graphs, where given a (known) reference symmetric matrix $Q \in [0, 1]^{n \times n}$ and $m$ independent samples from an IER graph given by an unknown symmetric matrix $P \in [0, 1]^{n \times n}$, the goal is to test the hypothesis $P=Q$ versus $||P-Q|| \geq \varepsilon$, where $||\cdot||$ is some specified norm on symmetric matrices. Building on recent related work on two-sample testing for IER graphs, we derive the optimal minimax sample complexities for the goodness-of-fit problem in various natural norms, such as the Frobenius norm and the operator norm. We also propose practical implementations of natural test statistics, using their asymptotic distributions and through the parametric bootstrap. We compare the performances of the different tests in simulations, and show that the proposed tests outperform the baseline tests across various natural random graphs models.

The upper tail problem for the largest eigenvalue of the Erdös--Rényi random graph $\mathcal{G}_{n,p}$ is to estimate the probability that the largest eigenvalue of the adjacency matrix of $\mathcal{G}_{n,p}$ exceeds its typical value by a factor of $1+\delta$. In this note we show that for $\delta >0$ fixed, and $p \rightarrow 0$ such that $n^{\frac{1}{2}} p \rightarrow \infty$, the upper tail probability for the largest eigenvalue of $\mathcal{G}_{n,p}$ is $\exp[-(1+o(1)) \min\{\tfrac{(1+\delta)^2}{2}, \delta(1+\delta) \} n^{2}p^{2}\log (1/p)].$ In the same regime of $p$, we show that the second largest eigenvalue $\lambda_2(\mathcal{G}_{n,p})$ of the adjacency matrix of $\mathcal{G}_{n,p}$ satisfies $\mathbb{P}(\lambda_2(\mathcal{G}_{n,p})\ge \delta np) = \exp[-(1+o(1)) \tfrac{1}{2} \delta^2n^2p^2 \log (1/p)],$ where $\delta =\delta_n < 1$ can depend on $n$ such that $\delta n^{\frac{1}{2}} p \rightarrow \infty$, which covers deviations of $\lambda_2(\mathcal{G}_{n,p})$ between $n^{\frac{1}{2}}$ and $np$. Our arguments build on recent results on the large deviations of the largest eigenvalue and related nonlinear functions of the adjacency matrix in terms of natural mean-field entropic variational problems.

What is the chance that among a group of $n$ friends, there are $s$ friends all of whom have the same birthday? This is the celebrated birthday problem which can be formulated as the existence of a monochromatic $s$-clique $K_s$ ($s$-matching birthdays) in the complete graph $K_n$, where every vertex of $K_n$ is uniformly colored with 365 colors (corresponding to birthdays). More generally, for a general connected graph $H$, let $T(H, G_n)$ be the number of monochromatic copies of $H$ in a uniformly random coloring of the vertices of the graph $G_n$ with $c_n$ colors. In this paper we show that $T(H, G_n)$ converges to ${Pois}(\lambda)$ whenever $\mathbb{E} T(H, G_n) \rightarrow \lambda$ and ${Var} T(H, G_n) \rightarrow \lambda$, that is, the asymptotic Poisson distribution of $T(H, G_n)$ is determined just by the convergence of its mean and variance. Moreover, this condition is necessary if and only if $H$ is a star-graph. In fact, the second-moment phenomenon is a consequence of a more general theorem about the convergence of $T(H,G_n)$ to a finite linear combination of independent Poisson random variables. As an application, we derive the limiting distribution of $T(H, G_n)$, when $G_n\sim G(n, p)$ is the Erdös--Rényi random graph. Multiple phase transitions emerge as $p$ varies from 0 to 1, depending on whether the graph $H$ is balanced or unbalanced.

Digital circuits are often prone to suffer from uncertain timing, inadequate sensor feedback, limited controllability of past states or inability of initializing memory-banks, and erroneous behavior of analog-to-digital converters, which may produce an unknown (${X}$) logic value at various circuit nodes. Additionally, many design bugs that are identified during the post-silicon validation phase manifest themselves as${X}$-values. The presence of such${X}$-sources on certain primary or secondary inputs of a logic circuit may cause loss of fault-coverage of a test set, which, in turn, may impact its reliability and robustness. In this paper, we provide a mechanism for predicting the sensitivity of${X}$-sources in terms of loss of fault-coverage, on the basis of learning only a few structural features of the circuit that are easy to extract from the netlist. We show that the${X}$-sources can be graded satisfactorily according to their sensitivity using support vector regression, thereby obviating the need for costly explicit simulation. Experimental results on several benchmark circuits demonstrate the efficacy, speed, and accuracy of prediction.

We consider the problem of testing whether two unequal-sized samples were drawn from identical distributions, versus distributions that differ significantly. Specifically, given a target error parameter $\eps > 0$, $m_1$ independent draws from an unknown distribution $p$ with discrete support, and $m_2$ draws from an unknown distribution $q$ of discrete support, we describe a test for distinguishing the case that $p=q$ from the case that $||p-q||_1 \geq \eps$. If $p$ and $q$ are supported on at most $n$ elements, then our test is successful with high probability provided $m_1\geq n^{2/3}/\varepsilon^{4/3}$ and $m_2 = \Omega\left(\max\{\frac{n}{\sqrt m_1\varepsilon^2}, \frac{\sqrt n}{\varepsilon^2}\}\right).$ We show that this tradeoff is information theoretically optimal throughout this range, in the dependencies on all parameters, $n,m_1,$ and $\eps$, to constant factors. As a consequence, we obtain an algorithm for estimating the mixing time of a Markov chain on $n$ states up to a $\log n$ factor that uses $\tilde{O}(n^{3/2} \tau_{mix})$ queries to a ``next node'' oracle. The core of our testing algorithm is a relatively simple statistic that seems to perform well in practice, both on synthetic data and on natural language data. We believe that this statistic might prove to be a useful primitive within larger machine learning and natural language processing systems.

In this paper, we study the properties of the Fermat-Weber point for a set of fixed points, whose arrangement coincides with the vertices of a regular polygonal chain. A k-chain of a regular n-gon is the segment of the boundary of the regular n-gon formed by a set of k (≤ n) consecutive vertices of the regular n-gon. We show that for every odd positive integer k, there exists an integer N(k), such that the Fermat-Weber point of a set of k fixed points lying on the vertices a k-chain of a n-gon coincides with a vertex of the chain whenever n ≥ N(k). We also show that $\lceil$πm(m + 1) - π 2 /4$\rceil$ ≤ N(k) ≤ $\lfloor$πm(m + 1) + 1$\rfloor$, where k (= 2m + 1) is any odd positive integer. We then extend this result to a more general family of point set, and give an O(hk log k) time algorithm for determining whether a given set of k points, having h points on the convex hull, belongs to such a family.