Simons Society Annual Retreat: Spring Break in San Juan

Following an amazing experience at the retreat in 2023, the Simons Foundation Society of Fellows 2024 retreat was held in San Juan, Puerto Rico during the spring semester break. The major goal of the retreat is to foster intellectual exchange and collaboration amongst the Junior and Senior fellows. We were treated to daily presentations from Senior and Junior Fellows and I learned a lot from the lectures. However, the informal gatherings—on the beach or in the pool—are probably why we enjoy the retreats.

The retreat was physically located in the Fairmont El San Juan hotel in Puerto Rico. The hotel is on the beach and has a night club! There is also a casino where I lost ~$50. (At some point, I was up by almost ~$200.) Better luck next time!

El Yunque National Forest

Objectives and Format

The primary goal of the retreat is to facilitate discussions and interactions that cross traditional academic boundaries, reflecting the foundation’s overarching mission to advance research in basic sciences and mathematics. The event features a series of 20-minute talks delivered by selected Fellows, showcasing a diverse range of research topics from theoretical physics to computational neuroscience.

Highlights from the 2024 Retreat

The 2024 retreat included presentations on various scientific and mathematical topics. I took notes during a subset of the presentations.

For instance, Michael Chapman discussed mathematical approximations and their limits in convergence, while Sanchit Chaturvedi reviewed the historical and mathematical evolution of the theory of gases. Emanuele Galiffi presented on the possibilities of manipulating light through temporal changes in matter, aiming to overcome traditional limitations in optical sciences. Jane Hubbard’s talk focused on how dietary choices and aging affect stem cells, using C. elegans as a model to understand cellular and molecular mechanisms. Isabel Low from Columbia University provided insights into the neural mechanisms that transform memories into actions in birds, a critical survival trait. Additionally, Carol Mason discussed the development of binocular vision and its molecular underpinnings and also discussed questions about the impact of melanin presence in retinal cells. Francesca Mignacco discussed the application of statistical physics to understand large populations of neurons, highlighting the challenges and advancements in interpreting complex neural data. Oliver Philcox’s presentation pondered the asymmetry of the universe, reflecting on how our perceptions are shaped by physical laws. And Andre Toussaint discussed some behavioral and neural signatures of chronic pain and abuse.

I am looking forward to the 2025 retreat! Will it be held in Hawaii?

Eigenvalues and Laplacian of a Graph: A Useful Lemma

Recently, for one of my projects I have been using the Laplacian matrix to study the spectra of graphs. For this post, I’ll review a tiny bit of background material on matrix theory for spectral graph theory. The majority of the material in this post can be found in the survey by Chung (1997).

What is the significance of eigenvalues and the Laplacian in understanding the properties and structure of graphs? Below, we highlight examples that show a connection between graph eigenvalues and the geometric aspects of graphs.

The Laplacian

Let G be a graph with vertex degree denoted by d_v for vertex v. Consider the following matrix L:

The Laplacian matrix \mathcal{L} is then defined by \mathcal{L} = T^{-1/2}LT^{-1/2}, where T is the diagonal matrix with (v, v)-th entry having value d_v. (This definition of the Laplacian is for graphs without loops and multiple edges.)

Examples

Examples of special graphs and the eigenvalues of their Laplacians:

  1. The star graph S_n on n vertices has eigenvalues 0, 1 (with multiplicity n-2), and 2.
  2. For the complete graph K_n on n vertices, the eigenvalues are 0 and \frac{n}{n - 1} with multiplicity n - 1.
  3. For the path P_n on n vertices, the eigenvalues are 1 - \cos\left(\frac{\pi k}{n-1}\right) for k = 0, 1, \ldots, n - 1.

Basic fact about the spectrum of a graph

Lemma (e.g., see Lemma 1.7 in [1]):
For a graph G on n vertices, we have:

  1. \sum_i \lambda_i \leq n with equality holding if and only if G has no isolated vertices.
  2. If G is connected, then \lambda_1 > 0. If \lambda_i = 0 and \lambda_{i+1} \neq 0, then G has exactly i + 1 connected components.
  3. The spectrum of a graph is the union of the spectra of its connected components.

Exercise for the reader: Can you rewrite the lemma in terms of the Laplacian?

[1] F.R.K. Chung. Spectral Graph Theory. Conference Board of Mathematical Sciences. American Mathematical Society, 1997.

On Semi-Supervised Node Labeling

Today is leap year day. I tried to weave the occasion into this short blog post but failed. Happy leap year day! I guess I have to wait until 2028 to write a blog post that has something to do with the day. The rest of the post has nothing to do with leap years.

Recently, I have been investigating the theory of the “node labeling” problem. The goal is to fully label the graph: use labels of some nodes in the graph to propagate labels to all the other nodes in the graph. Large network graphs display statistical characteristics that can be analyzed to gain deeper insights into complex systems. A key challenge within semi-supervised node classification involves allocating labels to all unlabeled nodes within a network graph.

Node Labeling Problem

The problem concerns classifying unlabeled nodes in a graph using information about the already-labeled nodes. Here are some applications:

  1. For recommendation systems based on interests of other individuals in the network
  2. Advertising systems
  3. Sociological studies of communities (e.g., inferring community affinity) and studying how ideas/memes spread

One could ask: Why not ask users to self-label? There are several issues with requiring self-labels: users may fail to update their labels; out of concerns for privacy, users may distort their information; users may put misleading information. As a side note, sociologists have historically used financial incentives to motivate individuals to provide accurate labels [1].

Now to actually solve the problem, there seems to be two broad types techniques used:

  1. Classification: Use graph information as features into a traditional classification system.
  2. Random Walks: Propagate existing labels via random walks.

Classification Methods

Essentially, these iterative methods use local neighborhood information to generate features that can be used to learn local classifiers. A problem with this approach, however, is that basing the labels
solely on labels of other nodes can lead to isolated components being unlabeled.

Random Walks

The method starts from a set of labeled nodes and performs a random walk on the graph. For this method to provide a complete labeling, every unlabeled node in the graph is assumed to be reachable (in finite steps) from some labeled node. This is called label connectivity.

[1] Wayne W. Zachary. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33(4):452–473, 1977