Seminar: Distance Encoding

Pan Li, Ph.D., recently joined the Computer Science Department faculty at Purdue University, will present a seminar titled "Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning"

Online Meeting Link: https://purdue-edu.zoom.us/j/96294915839

Abstract:

Learning representations of sets of nodes in a graph is crucial for applications ranging from node-role discovery to link prediction and molecule classification. Graph Neural Networks (GNNs) have achieved great success in graph representation learning. However, expressive power of GNNs is limited by the 1-Weisfeiler-Lehman (WL) test and thus GNNs generate identical representations for graph structures that may be very different. More powerful GNNs, proposed recently by mimicking higher-order-WL tests, only focus on representing entire graphs and they are computationally inefficient as they cannot utilize sparsity of the underlying graph.

In this talk, I will introduce a general class of structure-related features, termed Distance Encoding (DE). DE assists GNNs in representing any set of nodes, while providing strictly more expressive power than the 1-WL test. DE captures the distance between the node set whose representation is to be learned and each node in the graph. To capture the distance DE can apply important graph-distance measures such as shortest path distance or generalized PageRank scores. We propose two ways for GNNs to use DEs (1) as extra node features, and (2) as controllers of message aggregation in GNNs. Both approaches can utilize the sparse structure of the underlying graph, which leads to computational efficiency and scalability. We also prove that DE can distinguish node sets embedded in almost all regular graphs where traditional GNNs always fail. We evaluate DE on three tasks over six real networks: structural role prediction, link prediction, and triangle prediction. Results show that our models significantly outperform the traditional GNNs and other state-of-the-art methods particularly designed for the above tasks. 

Joint work with Y. Wang, H. Wang, J. Leskovec.

 

Bio:

Pan Li joined the Department of Computer Science (CS) at Purdue University as an Assistant Professor in 2020 Fall (Pan's faculty page). Before that, he did a one-year postdoc at Stanford University. Before that, he got his Ph.D. in the Department of Electrical and Computer Engineering at the University of Illinois Urbana-Champaign. Dr. Li works on a broad range of problems related to algorithms to process structured data, particularly graph and network data. His research mainly focuses on connecting theory and practice by developing principled algorithms, pumping up their computational efficiency and digging out new applications for structured data processing. Specifically, his recent research results included spectral theory and scalable algorithms for higher-order graphs, theory and new applications for graph neural networks and scalable ranking algorithms for large-scale recommender systems. His works got published in JMLR, TIT, NeurIPS, ICML, KDD, WSDM, AISTATS.