Speaker:

Arlei Silva - Assistant Professor of Computer Science, Rice University

Title:

Link Prediction with Autocovariance

Abstract:

Machine learning on graphs supports various structured-data applications including social network analysis, recommender systems, and natural language processing. One could argue that link prediction is the most fundamental among the graph-related tasks. This is because link prediction not only has many concrete applications (e.g. friendship and product recommendation, uncovering protein-protein interactions) but can also be considered an (implicit or explicit) step of most graph-based machine learning pipelines due to the fact that the observed graph is often incomplete. Earlier link prediction approaches relied on expert-designed heuristics (e.g., Common Neighbors, Adamic-Adar, Preferential Attachment) to extract topological information from the network. More recently, representation learning on graphs and Graph Neural Networks (GNNs) have emerged as the predominant solutions for link prediction.

In this talk, we will introduce link prediction methods based on autocovariance, which is a multiscale random-walk-based node similarity metric. We will show that the proposed approaches achieve state-of-the-art performance on simple, signed, and attributed graphs. As some of our key findings, we show that representation learning results for node classification do not generalize to link prediction. Moreover, autocovariance is especially accurate at predicting negative links in polarized signed graphs. Finally, our results illustrate how existing approaches for training and evaluation of supervised link prediction, including those based on GNNs, picture an overly optimistic picture of their performance. We show that a simple approach combining autocovariance and attribute information outperforms several recent GNN-based link prediction methods.

Speaker Bio:

Arlei Silva is an Assistant Professor of Computer Science at Rice University. His research focuses on developing algorithms and models for mining and learning from complex datasets, broadly defined as data science, especially for data represented as graphs/networks. He is particularly interested in problems motivated by computational social science, infrastructure, and healthcare. The tools that he applies to address these problems include machine learning, network science, graph theory, linear algebra, optimization, and statistics. Professor Silva received a Ph.D in Computer Science from the University of California, Santa Barbara, advised by Ambuj Singh, where he was also a postdoctoral scholar.

Location:

In person: Chambers Hall, 600 Foster Street, Lower Level
Remote option: https://northwestern.zoom.us/j/98973037019
Passcode: NICO22

About the Speaker Series:

Wednesdays@NICO is a vibrant weekly seminar series focusing broadly on the topics of complex systems and data science. It brings together attendees ranging from graduate students to senior faculty who span all of the schools across Northwestern, from applied math to sociology to biology and every discipline in-between. Please visit: https://bit.ly/WedatNICO for information on future speakers.

Related Info