Although estimation and inference methods from the field of statistical relational learning have been successfully applied in single-network domains, the theoretical foundation for learning in single network domains is scant. In addition, the development of predictive models has mainly focused on increasing classification accuracy and relatively little attention has been paid to the issues of feature selection and hypothesis testing. Lastly, the structure of a network dataset is affected by both the sampling process and the availability of node/link information. In single network domains, due to the complex dependencies among instances, these factors may have a large impact on the quality of learning/inference. This project aimed to explore these issues to strengthen the foundation for statistical relational learning.

Intellectual merit: We investigated these issues from several angles---analytical, empirical, and algorithmic---while trying to bridge the gap between structured machine learning methods and statistical network analysis. We thought carefully about the underlying assumptions, problem formulations, and methodology used for learning over networks, and used it to develop theoretical characterizations of network learning and inference methods. This analysis informed the development of diverse algorithms spanning the full machine learning spectrum, including sampling, learning, inference, hypothesis testing, model selection, descriptive modeling, and evaluation. We discuss two illustrative efforts from the project below.

Much of the work in relational learning has been based on an (implicit) assumption of the availability of a fully labeled network for learning. In this project, we focused on semi-supervised learning in partially-labeled networks. Although relational EM methods can significantly improve predictive performance in densely labeled networks, they could not achieve the same gains in sparsely labeled networks and often can performed worse than methods that ignore the relational information all together. We showed that the fixed-point methods that relational EM uses for approximate learning and inference result in errors that prevent convergence in sparsely labeled networks. A central finding is the tie between the stability of relational inference and the maximal eigenvalue of the inference solution, which can be used to determine if a particular network is prone to convergence issues based on the structure of label availability. As a solution, we develop a relational data augmentation method that represents uncertainty over label predictions and parameter estimates to ensure better convergence in all types of networks. To develop a more practical, scalable solution for massive networks, we had the key idea to augment the inference step of the fixed point EM algorithm to include a maximum entropy constraint, where the predicted label proportions (i.e., percentage predicted positive vs. negative) are forced to align with the proportions observed in the training set. The method adjusts the label predictions at every step of collective inference so they adhere to maximum entropy constraints. 

Another important task in network analysis is the detection of anomalous events in a network time series. Previous work has focused on detecting anomalies through the use of network statistics that summarize the behavior of the network. However, we show that many common network statistics are dependent on confounding factors like the total number of nodes or edges, and use of these statistics leads to incorrect conclusions (i.e., both false positives and false negatives). We formalize the use of network statistics in graphs of varying sizes and shows that detection errors are due to the use of size inconsistent or size divergent statistics. To remedy the issue, we introduce the statistical property of size consistency for network statistics and shows theoretically how the property ensures accurate detection of changes or anomalies in dynamic networks. We then propose three size consistent network statistics: mass shift, degree shift, and triangle probability, which are provably size consistent. With extensive synthetic and semi-synthetic experiments, we demonstrate that anomaly detectors using the new size-consistent statistics exhibit superior detection performance in dynamic networks where the message and edge counts vary.

Broader impact: The work described above, while published in data mining and machine learning venues, is likely to have a broad impact across network-centric fields where researchers study the properties of complex systems by modeling the data as a network or graph. In these fields, a deeper understanding of the statistical and theoretical properties of analytic methods, as well as improved algorithms, will increase the accuracy and robustness of these investigations. Moreover, this project has had a small, but important, impact on the education and training of several URMs students. As these individuals graduate and move to academic and industrial STEM settings, they will serve as role models in the areas of machine learning, graph mining, and network science more broadly.

Last Modified: 06/19/2019
Modified by: Jennifer Neville