Spectral Graph Drawings

This is a nice application of Linear Algebra (specifically the concepts of eigenvectors, quadratic forms, and optimization) applied to Graph Theory. A graph is simply an object with nodes and edges. Each graph has an associated symmetric matrix called the Laplacian. It turns out that the quadratic form defined by the Laplacian has a physical interpretation: the potential energy of the system if there was a mass at each node and each edge was a spring. The eigenvectors of this quadratic form associated with smallest eigenvalues are then minimizers of this energy. We can then take these eigenvectors to be the coordinates of nodes of the graph, creating a 2D plot of the graph (if we choose 2 eigenvectors) or a 3D plot (if we choose 3 eigenvectors). This plot is known as a spectral drawing of a graph. Given above is a smooth interpolation of a graph known as the buckyball from a random "high" energy drawing to a spectral drawing ("low" energy). Generally speaking, a spectral drawing may give better insight into the structure of the network.

Schrödinger Bridge Optimal Transport (Left) vs. Anisotropic Schrödinger Bridge Optimal Transport (Right)

Interpolation on the left is dictated by the geometry of the surface alone. On the right, anisotropy tensors (visualized by ellipses) make local modifications to the metric of the surface and influence the transport interpolation. Intuitively, along long axes of ellipses, the surface is "pinched" and along short axes of ellipses, the surface is "stretched." The algorithms used to produce these visuals were designed collaboratively by me, Juan Atehortúa, Faria Huq, Adrish Dey, and Dr. Justin Solomon at SGI 2021. Special thanks to Dr. Keenan Crane who created this mesh.