PhD Defense: Collective Multi-relational Network Mining

Our world is becoming increasingly interconnected, and the study of networks and graphs are becoming more important than ever. Domains such as biological and pharmaceutical networks, online social networks, the World Wide Web, recommender systems, and scholarly networks are just a few examples that include explicit or implicit network structures. Most networks are formed between different types of nodes and contain different types of links. Leveraging these multi-relational and heterogeneous structures is an important factor in developing better models for these real-world networks. Another important aspect of developing models for network data to make predictions about entities such as nodes or links, is the connections between such entities. Unlike models for non-network data where predictions about entities with unknown labels are provided independently of each other, the entities with unknown labels in networks are interconnected and inferred information about one entity should change the models belief about other related entities.
In this dissertation, I present models that can effectively leverage the multi-relational nature of networks and collectively make predictions on links and nodes. In the first part, I present models to make predictions on nodes in multi-relational networks motivated by the task of spammer detection in evolving multi-relational social networks. In the second part, I present a generalized augmented multi-relational bi-typed network and propose a template for link inference models motivated by pharmaceutical and recommender systems domain. In both network-based node classification and link inference sections, I highlight the effect of two important aspects: (1) Heterogeneous entities and multi-relational structures, (2) Joint inference and collective classification of the unlabeled data. Finally, I show that the collective link prediction task is an instance of a general graph-based prediction model that relies on a neighborhood graph for predictions, and propose a framework that can dynamically adapt the neighborhood graph based on the state of variables from intermediate inference results, as well as structural properties of the relations connecting them to improve the performance of the model.
Examining Committee:
Chair: Dr. Lise Getoor
Dean’s rep: Dr. Louiqa Raschid
Members: Dr. Hector Corrada Bravo
Dr. Hal Daume III
Dr. Larry Davis