3rd workshop on Graphs and more Complex structures for Learning and Reasoning

Graphical Dynamical Systems

Real-world bio-social habitats are often represented as co-evolving complex networks. Reasoning about such complex systems is complicated and scientifically challenging due to their size, co-evolutionary nature and multiple contagions spreading simultaneously. Examples include: human immune system, The 2019 COVID-19 pandemic, 2009 financial crisis, 2003 Northeast power blackout, global migration,  information propagation over social media,  societal impacts of natural and human initiated disasters and the effect of climate change.

Graphical Dynamical systems (GDS) can be used to model and represent large co-evolving bio-social habitats. The talk will describe a computational theory of GDS, with a particular focus on inference problems. We will discuss how GDS can aid in the development of practical decision support systems to reason about coevolving bio-social habitats.

New ML models for Networks in Public Health and Beyond

Networks are an important abstraction for problems in many domains including public health, urban computing and other areas. They are ubiquitous, from online social networks, gene-regulatory networks, to router graphs. Dynamical processes on networks are also widespread across several domains. Understanding such propagation processes will eventually enable us to manipulate them for our benefit e.g., understanding dynamics of epidemic spreading over graphs helps design more robust policies for immunization. 

In this talk, we will go over some of our recent work on developing new network ML models and algorithms under uncertainty such as: learning latent graphs from multi-variate time-series, developing differentiable network-based agent models, autoregressive models for graph generation and stochastic algorithms for network design. 

MultiBiSage: A Web-Scale Recommendation System Using Multiple Bipartite Graphs at Pinterest

Abstract: Recently, graph based recommendation systems have been successfully developed and deployed in industry. At Pinterest, a data-efficient GCN, PinSage, learns pin embeddings from the Pin-Board graph. Pinterest relies heavily on PinSage which in turn only leverages the Pin-Board graph.  However, there exist several entities at Pinterest and heterogeneous interactions among these entities. These diverse entities and interactions provide important signals for recommendations and modeling. In this work, we show that training deep learning models on graphs that capture these diverse interactions can result in learning higher-quality pin embeddings than training PinSage on only the Pin-Board graph. However, building a large-scale heterogeneous graph engine that can process the entire Pinterest size data has not yet been done. In this work, we present a clever and effective solution where we break the heterogeneous graph into multiple disjoint bipartite graphs and then develop a novel data-efficient MultiBiSage model that combines the signals from them. MultiBiSage can capture the graph structure of multiple bipartite graphs to learn high-quality pin embeddings. The benefit of our approach is that individual bipartite graphs can be processed with minimal changes to Pinterest’s current infrastructure, while being able to combine information from all the graphs while achieving high performance. We train MultiBiSage on six bipartite graphs including our Pin-Board graph and show that it significantly outperforms the deployed latest version of PinSage on multiple user engagement metrics. We also perform experiments on two public datasets to show that MultiBiSage is generalizable and can be applied to datasets outside of Pinterest.

Learning mechanisms on graph neural networks

How do the weights of a graph neural network (GNN) evolve during learning? Through the use of the neural tangent kernel neural tangent kernel, I will discuss the precise weight dynamics of a wide graph neural network during learning. But how does this kernel evolve as the underlying graph grows, for instance, as in the case of a growing social network? I investigate this in the limit of large graphs by introducing the graphon-neural tangent kernel, and proving convergence of the graph-kernel to the graphon-kernel. Through this, I show how one can train a GNN on a smaller network and transfer rapidly to a larger network with theoretical performance guarantees. 

Despite theoretical guarantees on transfer learning from small to large graphs, conventional optimization of GNNs is still relatively slow. One might ask whether, given a finite size graph, backpropagation is the optimal learning mechanism. Here, I present a novel learning rule that uses a combination of gating, and local learning, inspired by neuroscience, to propose a significantly faster alternative to backpropagation. This learning rule, called Dendritic Gated Networks, applies to a variety of neural networks including GNNs and results in rapid, efficient, and intuitive weight updates, and presents several performance advantages like prevention of overfitting and resistance to catastrophic forgetting.

How to Leverage Network Structure to Improve Reasoning & Prediction

Networks are a natural representation of complex systems across domains, from social, to biological, to technological. Modeling the structure and relationships in networks is central to the understanding of these systems and have a huge economic impact with many applications. However, the characteristics of network data captured from these complex systems present a number of challenges to the design graph machine learning methods. In this talk, I will discuss recent work on reasoning about relationships in network data, with applications in knowledge graphs, social networks, and system problems.