From grids to Graph nodes: The motivation

Observations that are obtained from satellites, radars, and other sources are often in the form of irregularly spaced data points. When the data sources are irregularly spaced, it is often more appropriate to represent the data as a graph, where the nodes represent the data points and the edges represent the relationships between them. The gridded products are obtained from these irregularly spaced data points through interpolation and other techniques. By representing the data as a graph, we can directly work with the observation network based data to capture the underlying relationships and dependencies between the data points.

GNN: they allow us to encode relationships via connectivity, beyond purely spatial proximity. This is particularly useful in scientific applications where the relationships between data points may be complex and not solely based on their spatial locations. GraphCast was a recent work that used Graph Neural Networks for weather forecasting by Google.

Reduced Gaussian Grid:

  • lats are determined by the roots of the Legendre polynomial of degree N, where N is the number of latitudes. The lons are determined by dividing the circumference of the Earth into equal segments based on the number of longitudes. Thus the number of longitudes decreases as we move towards the pole. The reduced Gaussian grid is a type of grid that is used in numerical weather prediction and climate modeling. It is designed to reduce the number of grid points in regions where the data is less important, while maintaining a high resolution in regions where the data is more important. This allows for more efficient computations and better representation of important features in the data.

A priori choice of the node connectivity is a challenge. We want to explore the use of topological descriptors, such as Morse Complex, to determine the connectivity of the graph nodes.

  1. Bipartite Structure - Partition the graph into two sets of nodes, where one set represents the input features and the other set represents the output features. We create edgaes that pass information from the coarse grid to the fine grid.

Positional encoding for Graphs:

In laguage tasks, we have positional encoding which captures the positional importance of different words and their order becomes important. For graphs, the design of unique node positions is challenging as there are symmetries which prevent canonical node positional information (Murphy et al. 2019). In fact, most of the GNNs which are trained on graph datasets learn structural node information that are invariant to the node position. Such an approach( such as GAT) where the attention is a function of local neighborhood connectivity are not comptetive.

To learn both structural and positional features, the Laplacian eigenvectors of the graph structure can provide node positional information. Since Laplacian PEs encode distance-aware information (i.e., nearby nodes have similar positional features and farther nodes have dissimilar positional features), our choice is using the Laplacian eigenvectors as PE in Graph Transformer. We pre-compute the Laplacian eigenvectors of all graphs in the dataset. These eigenvectors are defined via the factorization of the graph Laplacian matrix.

$$ \Delta = I - D^{-1/2} A D^{-1/2} $$ where A is the adjecency matrix.

What was new to me:

The Laplacian matrix is defined as follows: Given a graph $G:=(V,E)$ where $V:={v_1,v_2,…,v_n}$ is the set of nodes/vertices and $E:={e_1,e_2,…,e_m}$ is the set of edges, with an adjacency matrix $A∈{0,1}^{n×n}$ , where

$A_{i,j}:=1$,if there is an edge between $v_i$ and $v_j$
$ 0,$ otherwise

Degree matrix $$D∈Z^{n×n}$$ where

$D_{i,j}:=${degree(v_i), $0$,if i=jotherwise the Laplacian matrix is defined as

$$L:=D−A$$ This definition is super simple, but it describes something quite deep: it’s the discrete analogue to the Laplacian operator on multivariate continuous functions. How does such a simple definition capture such a complex idea? We will demonstrate this in the remainder of this post.

Graph Transformer Architecture

GNNs are useful for modeling problems where there is unstructured data or data in form of a graph instead of regular gridded data. With transformer architecture has shown great skill in capturing complex relationship in language, expoliting it to extend it to graphs is natural. Original transformer does not not leverage the graph connectivity inductive bias. It can perform poorly when the graph topology is important and has not been encoded into the node features.

Graph transformer extended the traditional transformer with four new properties:

  • the attention mechanism is a function of the neighborhood connectivity for each node in the graph.
  • the positional encoding is represented by the Laplacian eigenvectors, a generalization of the sinusoidal positional encodings in NLP.
  • the layer normalization is replaced by a batch normalization layer for faster training and better generalization performance.
  • extended to edge feature representation, which can be critical to tasks s.a. chemistry (bond type) or link prediction (entity relationship in knowledge graphs).

Attentional Convolutional Networks (ACNs) are a type of neural network architecture that combines the strengths of convolutional neural networks (CNNs) and attention mechanisms.

In transformer based models,

** Project Ideas: ** Downscaling the rainfall data in Indian region from the coarse resolution of the ERA5 reanalysis to a finer resolution using Graph Neural Networks. The goal is to improve the spatial resolution of the rainfall data while preserving important features and patterns in the data. This can be useful for applications such as hydrological modeling, flood forecasting, and climate impact assessments.

** Project Ideas: extended analysis with morse complex built from the rainfall data ** Related: Predicting the rainfall in the Indian region using Graph Neural Networks. The goal is to develop a model that can accurately predict rainfall patterns based on historical data and other relevant features. This can be useful for applications such as agriculture, water resource management, and disaster preparedness.

** Project Ideas: Can you apply consistency model framework to the rainfall data where you leverage a pre-trained model on the ERA5 reanalysis data and fine-tune it on the rainfall data to improve the accuracy of the predictions.**

What You will Learn:

  • How to represent irregularly spaced data as a graph and work with graph-based representations.
  • VIT : Visiion Transformer
  • Graph Neural Networks (GNNs)
  • Sparse Attention( quadratic scaling limits the number of tokens one can process, so we want to explore sparse attention mechanisms that can reduce the computational complexity while maintaining performance. This can be useful for processing large graphs with many nodes and edges, where the number of tokens can be very large.)
  • Shared KV, Quantization, and other techniques to reduce the memory footprint of the model.

Cons of Transformers: They require more data for the same task because of no inductive bias. They also have high memory footprints.

References:

Tools

https://pytorch-geometric.readthedocs.io/en/2.8.0/tutorial/graph_transformer.html

On Graphs based Transformer Models https://arxiv.org/pdf/2012.09699