A Tale of Two Graph Distances: Effective Resistance and Biharmonic Distance
Mitchell Black (UCSD)
Monday, March 3rd 2025, 2-3pm
Abstract:
In this talk, we explore two distances on the vertices of a graph: effective resistance and biharmonic distance. The effective resistance and biharmonic distance are defined very similarly—the biharmonic distance simply replaces a matrix by its square and takes a square root. The effective resistance is a well-studied distance on graphs dating back to Kirchhoff's original work on electrical circuits, while the biharmonic distance was only defined about a decade and a half ago. Similarly, the effective resistance has a rich theory and applications spanning many areas of graph theory, while comparatively little was known about the biharmonic distance.
In this talk, we will see that despite the similarity in their definitions, these distances are very different. In short, the effective resistance measures how well-connected a pair of vertices is, and the biharmonic distance measures how important an edge is to the connectivity of the graph. I will begin the talk with a discussion of a recent paper where effective resistance was used in the theoretical analysis of a problem on graph neural networks called oversquashing, where graph neural networks struggle to communicate information due to the topology of the underlying graph. We will see that biharmonic distance appears in a proposed remedy for oversquashing, which aims to decrease the average effective resistance of the graph. Motivated by this surprising connection between the two distances, I will share some results from a recent paper that develops the theory of biharmonic distance. This paper shows several more surprising connections between the two distances, while also providing theoretical results that give intuition to what biharmonic distance is measuring. To conclude, I will discuss how these theoretical results suggest potential applications of biharmonic distance.