Workshop

Zoom Link

We revisit the classical broken sample problem: Two samples of iid data points X={X_1,...,X_n} and Y={Y_1,...,Y_m} are observed without correspondence, with m \leq n. The goal is to distinguish the following two hypotheses: Under the null hypothesis, X and Y are independent. Under the alternative hypothesis, X and Y are correlated in the sense that (X_{\pi(i)}, Y_i)'s are drawn independently from a bivariate distribution for some latent injection \pi: [m] \to [n]. Originally introduced by DeGroot, Feder, and Goel [AoMS 1971] to model matching records in census data, this problem has recently gained renewed interest due to its applications in data de-anonymization, data integration, and target tracking. Despite extensive research over the past decades, determining the precise detection threshold has remained an open problem even for equal sample sizes (m=n). Assuming m and n grow proportionally, in this work, we show that the sharp threshold is given by a spectral and an L_2 condition of the likelihood ratio operator, resolving a conjecture of Bai and Hsing [PTRF 2005] in the positive. Extensions to high dimensions and linear models are also discussed. This is based on joint work with Shuyang Gong (Peking University), Simiao Jiao (Duke), and Jiaming Xu (Duke).

Zoom Link

Zoom Link

Zoom Link

Zoom Link

We investigate the problem of detecting and estimating a changepoint in the attachment function of a network evolving according to a preferential attachment model on $n$ vertices, using only a single final snapshot of the network. Bet et al. show that a simple test based on thresholding the number of vertices with minimum degrees can detect the changepoint when the change occurs at time $n-\Omega(\sqrt{n})$. They further make the striking conjecture that detection becomes impossible for any test if the change occurs at time $n-o(\sqrt{n}).$ Kaddouri et al. make a step forward by proving the detection is impossible if the change occurs at time $n-o(n^{1/3}).$ In this paper, we resolve the conjecture affirmatively, proving that detection is indeed impossible if the change occurs at time $n-o(\sqrt{n}).$ Furthermore, we establish that estimating the changepoint with an error smaller than $o(\sqrt{n})$ is also impossible, thereby confirming that the estimator proposed in Bhamidi et al. is order-optimal.

Zoom Link

Zoom Link

A wide array of network growth models have been proposed across various domains as test beds to understand questions such as the effect of network change point (when a shock to the network changes the probabilistic rules of its evolution) or the role of attributes in driving the emergence of network structure and subsequent centrality measures in real world systems. 

The goal of this talk will be to describe two specific settings where continuous time branching processes give mathematical insight into asymptotic properties of such models. In the first setting, a natural network change point model can be directly embedded into continuous time thus leading to an understanding of long range dependence of the initial network system on subsequent properties imply the difficulty in understanding and estimating network change point. In the second application, we will describe a notion of resolvability where convergence of a simple macroscopic functional in a model of networks with vertex attributes, coupled with stochastic approximation techniques implies local weak convergence of a standard model of nodal attribute driven network evolution to a limit infinite random structure driven by a multitype continuous time branching process. In the second setting, continuous time branching processes naturally emerge in the limit. If time permits, we will describe a final setting of network evolution with delay where once again such processes arise only in the limit. 

Zoom Link

Network models have received increasing attention from the statistical community, in particular in the context of analyzing and describing the interactions of complex random systems. In this context, community structures can be observed in many networks, where the nodes are clustered into communities with the same connection patterns. In this talk, we will discuss the problem of estimating the number of communities for the Stochastic Block Model (SBM) and the Degree Corrected Stochastic Block Model (DCSBM). In general, we will discuss penalized methods used to infer the number of communities given a network.

Zoom Link

Spectral methods are widely used to estimate eigenvectors of a low-rank signal matrix subject to noise. These methods use the leading eigenspace of an observed matrix to estimate this low-rank signal. Typically, the entrywise estimation error of these methods depends on the coherence of the low-rank signal matrix with respect to the standard basis. In this work, we present a novel method for eigenvector estimation that avoids this dependence on coherence. Assuming a rank-one signal matrix, under mild technical conditions, the entrywise estimation error of our method provably has no dependence on the coherence under Gaussian noise (i.e., in the spiked Wigner model), and achieves the optimal estimation rate up to logarithmic factors. Simulations demonstrate that our method performs well under non-Gaussian noise and that an extension of our method to the case of a rank-r signal matrix has little to no dependence on the coherence. In addition, we derive new metric entropy bounds for rank-r singular subspaces under the two-to-infinity distance, which may be of independent interest. We use these new bounds to improve the best known lower bound for rank-r eigenspace estimation under two-to-infinity distance.

Zoom Link

When training data points for a prediction algorithm are connected by a network, it creates dependency, which reduces effective sample size but also creates an opportunity to improve prediction by leveraging information from neighbors. Multiple prediction methods on networks taking advantage of this opportunity have been developed, but they are rarely interpretable or have uncertainty measures available. This talk will cover two contributions bridging this gap. One is a conformal prediction method for network-assisted regression. The other is a family of flexible network-assisted models built upon a generalization of random forests (RF+), which both achieves competitive prediction accuracy and can be interpreted through feature importance measures.  Importantly, it allows one to separate the importance of node covariates in prediction from the importance of the network itself. These tools help broaden the scope and applicability of network-assisted prediction to practical applications.  

This talk is based on joint work with Robert Lunde, Tiffany Tang, and Ji Zhu.