This Week's Seminars and Colloquia

On Expressivity and Stability of Positional Encoding for Graph Neural Networks and Graph Transformers

Series
Applied and Computational Mathematics Seminar
Time
Monday, February 26, 2024 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 005 and https://gatech.zoom.us/j/98355006347
Speaker
Pan LiGeorgia Institute of Technology

Designing effective positional encodings for graphs is key to building powerful graph transformers and enhancing message-passing graph neural networks’ expressive power. However, since there lacks a canonical order of nodes in the graph-structure data, the choice of positional encodings for graphs is often tricky. For example, Laplacian eigenmap is used as positional encodings in many works. However, it faces two fundamental challenges: (1) Non-uniqueness: there are many different eigen-decompositions of the same Laplacian, and (2) Instability: small perturbations to the Laplacian could result in completely different eigenvectors, leading to unpredictable changes in positional encoding. This is governed by the Davis-Kahan theorem, which further negatively impacts the model generalization. In this talk, we are to introduce some ideas on building stable positional encoding and show their benefits in model out-of-distribution generalization. The idea can be extended to some other types of node positional encodings. Finally, we evaluate the effectiveness of our method on molecular property prediction, link prediction, and out-of-distribution generalization tasks, finding improved generalization compared to existing positional encoding methods.

I will mainly talk about three papers:

1. Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning,NeurIPS20, Pan Li, Yanbang Wang, Hongwei Wang, Jure Leskovec

2. Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks, ICLR22 Haorui Wang, Haoteng Yin, Muhan Zhang, Pan Li

3. On the Stability of Expressive Positional Encodings for Graphs, ICLR24 Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, Pan Li

 

 

Splitting of vector bundles on toric varieties

Series
Algebra Seminar
Time
Tuesday, February 27, 2024 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Mahrud SayrafiUniversity of Minnesota

In 1964, Horrocks proved that a vector bundle on a projective space splits as a sum of line bundles if and only if it has no intermediate cohomology. Generalizations of this criterion, under additional hypotheses, have been proven for other toric varieties, for instance by Eisenbud-Erman-Schreyer for products of projective spaces, by Schreyer for Segre-Veronese varieties, and Ottaviani for Grassmannians and quadrics. This talk is about a splitting criterion for arbitrary smooth projective toric varieties, as well as an algorithm for finding indecomposable summands of sheaves and modules in the more general setting of Mori dream spaces.

On the well-posedness of the Mortensen observer for a defocusing cubic wave equation

Series
PDE Seminar
Time
Tuesday, February 27, 2024 - 14:00 for 1 hour (actually 50 minutes)
Location
Online: https://gatech.zoom.us/j/95574359880?pwd=cGpCa3J1MFRkY0RUeU1xVFJRV0x3dz09
Speaker
Jesper SchröderTechnische Universität Berlin

In this presentation the analytical background of nonlinear observers based on minimal energy estimation is discussed. Originally, such strategies were proposed for the reconstruction of the state of finite dimensional dynamical systems by means of a measured output where both the dynamics and the output are subject to white noise. Our work aims at lifting this concept to a class of partial differential equations featuring deterministic perturbations using the example of a wave equation with a cubic defocusing term in three space dimensions. In particular, we discuss local regularity of the corresponding value function and consider operator Riccati equations to characterize its second spatial derivative.

Recent advances on extremal problems of k-critical graphs (Jie Ma, University of Science and Technology of China)

Series
Graph Theory Seminar
Time
Tuesday, February 27, 2024 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Jie MaUniversity of Science and Technology of China

 A graph is called k-critical if its chromatic number is k but any proper subgraph has chromatic number less than k. There have been extensive reseaches on k-critical graphs over the past decades, yet several basic problems remain widely open. One of such problems is to determine the maximum number of edges in an n-vertex k-critical graph. In this talk, we will discuss some recent results on extremal aspects of k-critical graphs, including improvments on the extremal number of edges/cliques/critical subgraphs in k-critical graphs.  This is based on some joint works with Jun Gao, Cong Luo and Tianchi Yang. 

Smooth Fine Curve Graphs

Series
Geometry Topology Student Seminar
Time
Wednesday, February 28, 2024 - 14:00 for 1 hour (actually 50 minutes)
Location
Speaker
Katherine BoothGeorgia Tech

The curve graph provides a combinatorial perspective to study surfaces. Classic work of Ivanov showed that the automorphisms of this graph are naturally isomorphic to the mapping class group. By dropping isotopies, more recent work of Long-Margalit-Pham-Verberne-Yao shows that there is also a natural isomorphism between the automorphisms of the fine curve graph and the homeomorphism group of the surface. Restricting this graph to smooth curves might appear to be the appropriate object for the diffeomorphism group, but it is not. In this talk, we will discuss why this doesn’t work and some progress towards describing the group of homeomorphisms that is naturally isomorphic to automorphisms of smooth fine curve graphs.

Load Balancing under Data Locality: Extending Mean-Field Framework to Constrained Large-Scale Systems

Series
Stochastics Seminar
Time
Thursday, February 29, 2024 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Debankur MukherjeeGeorgia Tech

Large-scale parallel-processing infrastructures such as data centers and cloud networks form the cornerstone of the modern digital environment. Central to their efficiency are resource management policies, especially load balancing algorithms (LBAs), which are crucial for meeting stringent delay requirements of tasks. A contemporary challenge in designing LBAs for today's data centers is navigating data locality constraints that dictate which tasks are assigned to which servers. These constraints can be naturally modeled as a bipartite graph between servers and various task types. Most LBA heuristics lean on the mean-field approximation's accuracy. However, the non-exchangeability among servers induced by the data locality invalidates this mean-field framework, causing real-world system behaviors to significantly diverge from theoretical predictions. From a foundational standpoint, advancing our understanding in this domain demands the study of stochastic processes on large graphs, thus needing fundamental advancements in classical analytical tools.

In this presentation, we will delve into recent advancements made in extending the accuracy of mean-field approximation for a broad class of graphs. In particular, we will talk about how to design resource-efficient, asymptotically optimal data locality constraints and how the system behavior changes fundamentally, depending on whether the above bipartite graph is an expander, a spatial graph, or is inhomogeneous in nature.

Essentially tight bounds for rainbow cycles in proper edge-colourings (Matija Bucic, Princeton)

Series
Combinatorics Seminar
Time
Friday, March 1, 2024 - 15:15 for 1 hour (actually 50 minutes)
Location
Skiles 308
Speaker
Matija BucicPrinceton University

An edge-coloured graph is said to be rainbow if it uses no colour more than once. Extremal problems involving rainbow objects have been a focus of much research as they capture the essence of a number of interesting problems in a variety of areas. A particularly intensively studied question due to Keevash, Mubayi, Sudakov and Verstraëte from 2007 asks for the maximum possible average degree of a properly edge-coloured graph on n vertices without a rainbow cycle. Improving upon a series of earlier bounds, Tomon proved an upper bound of (log n)^(2+o(1)) for this question. Very recently, Janzer-Sudakov and Kim-Lee-Liu-Tran independently removed the o(1) term in Tomon's bound. We show that the answer to the question is equal to (log n)^(1+o(1)).  
Joint work with: Noga Alon, Lisa Sauermann, Dmitrii Zakharov and Or Zamir.