UCLA

Networks or graphs are often used to represent relational phenomena in numerous domains, and relational phenomena by nature progress in time. Devising powerful models and tools for dynamic graphs can provide valuable insights into real-world phenomena that benefit decision-making. Moreover, change point detection plays an indispensable role in identifying discrepancies in the data generating processes. Without taking the structural changes across dynamic networks into account, learning from the time series may lead to ambiguity. Thence, it is practical for researchers to first localize the change points, and then analyze the dynamic networks, rather than neglecting where the network patterns have substantially changed.

We first consider the change point detection problem for dynamic graphs using the Separable Temporal Exponential-family Random Graph Model (STERGM). The STERGM that utilizes network statistics to represent the network structures is a flexible model to fit dynamic graphs. We propose a new estimator derived from the Alternating Direction Method of Multipliers (ADMM) and Group Fused Lasso to simultaneously detect multiple time points, where the parameters of a time-heterogeneous STERGM have changed.

Then we study the change point detection problem for dynamic graphs under a generative framework. The proposed model consists of learnable prior distributions for graph-level representations and of a decoder that can generate dynamic graphs from the low-dimensional representations. The informative prior distributions in the latent spaces are learned from the observed graphs as empirical Bayes, and the expressive power of a generative model is exploited to assist change point detection.

Furthermore, we consider an exponential-family model to fit dynamic valued networks, as relations by nature often have degree of strength. To facilitate the modeling of dyad value increment and decrement, a Partially Separable Temporal Exponential-family Random Graph Model is proposed. The parameter learning algorithms approximate the maximum likelihood, by drawing Markov chain Monte Carlo (MCMC) samples conditioning on the valued network from the previous time step.

Throughout the dissertation, we use both simulated and real-world data to evaluate the methodology and the learning algorithms. The results demonstrate the effectiveness of the proposed frameworks.