IDEAL Special Program on Networks and Inference 2024 Winter/Spring kick-off Event

Tentative Schedule:

Virtual link: 

Morning workshop session:

 https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=3e828f39-568f-4e55-87ae-b0f901775a8b 

TTIC Research Talk  

 https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=78fbfe3a-fb78-4b17-88f5-b067015a9b3c 

Afternoon workshop session: TBD

Details:

1. Reza Gheissari (Northwestern) 

Title: Emergent low-dimensional subspaces for high-dimensional SGD

Abstract: It has been empirically observed that the spectrum of neural network Hessians along training trajectories have a bulk concentrated near zero, and a few outlier eigenvalues. Moreover, the eigenspaces associated to these outliers have been associated to a low-dimensional subspace in which most of the training occurs, and this implicit low-dimensional structure has been used as a heuristic for the success of high-dimensional classification. We will describe rigorous results in this direction, establishing emergence of outliers in the Hessian spectrum over the course of the training by SGD in high-dimensional classification tasks with one and two-layer networks. Based on joint work with Ben Arous, Huang, and Jagannath.

Title: Representation Learning on Networks: Methods and directions

Abstract: Networks (or graphs) are a powerful tool to model complex systems such as social networks, transportation networks, and the Web. The accurate modeling of such systems enables us to improve infrastructure, reduce conflicts in social media, and make better decisions in high-stakes settings. Traditionally, researchers in network science have heavily relied on manually defining how to extract features from networks to make predictions on networks. However, recent years have witnessed a notable advancement in approaches that automatically learn to encode network structure into low-dimensional embeddings. These techniques leverage modern tools such as deep learning and they are known as network representation learning (NRL) methods. NRL eliminates the need for laborious feature engineering and has produced good performance in various network-related tasks, including node classification, node clustering, and link prediction.  In this talk, I will discuss some of the advancements in NRL over the past few years. The discussion will involve algorithms based on random walks and the most recent advances in graph neural networks (GNNs). The second half of the talk will explore exciting future directions involving GNN explanations and prompting in GNNs.

Title: Exact Community Recovery in the Geometric SBM

Abstract: We study the problem of exact community recovery in the Geometric Stochastic Block Model (GSBM), where each vertex has an unknown community label as well as a known position, generated according to a Poisson point process in $\mathbb{R}^d$. Edges are formed independently conditioned on the community labels and positions, where vertices may only be connected by an edge if they are within a prescribed distance of each other. The GSBM thus favors the formation of dense local subgraphs, which commonly occur in real-world networks, a property that makes the GSBM qualitatively very different from the standard Stochastic Block Model (SBM). We propose a linear-time algorithm for exact community recovery, which succeeds down to the information-theoretic threshold, confirming a conjecture of Abbe, Baccelli, and Sankararaman. The algorithm involves two phases. The first phase exploits the density of local subgraphs to propagate estimated community labels among sufficiently occupied subregions, and produces an almost-exact vertex labeling. The second phase then refines the initial labels using a Poisson testing procedure. Thus, the GSBM enjoys local to global amplification just as the SBM, with the advantage of admitting an information-theoretically optimal, linear-time algorithm.