Year
2022
Location
Halıcıoğlu Data Science Institute, UC San Diego
Category
Research
Duration
3 Months
Graph Neural Networks (GNNs) have become an increasingly popular method in machine learning tasks in non-Euclidean domains, where data are represented as graphs containing complex interdependencies. GNNs can effectively exploit these interactions to solve problems including classification, recommendation, and node property prediction, nullifying the assumption of Euclidean deep learning that instances are independent of each other. This report provides a brief survey and details the implementation and benchmarking, using PyTorch Geometric and PyTorch Lightning, of three foundational GNN architectures: Graph Convolutional Network (GCN), Graph Attention Network (GAT), and Graph Isomorphism Network (GIN), as well as the message-passing paradigm they follow. Beyond the theoretical underpinnings of these architectures, this report attempts to quantify and visualize their difficulties with capturing long-range dependencies (as well as maintaining short-term ones). Finally, it investigates a simplified graph rewiring mechanism, drawing inspiration from curvature-based approaches, to mitigate scaling issues in GNNS caused by oversquashing and information bottlenecks.
Underlying the breakthroughs of artificial neural networks are their capabilities in learning from rich, high-dimensional feature sets (NKM+19), synthesizing complex non-linear functions, and flexible mappings from one vector space to another. These make ANNs most successful in picking up hidden patterns within input data in a Euclidean domain. For example, convolutional neural networks (CNNs), which employ local connections and shift-invariance, are leveraged in numerous image analysis tasks to extract meaningful latent representations from images, which are expressed as grids in Euclidean space. However, applications of non-Euclidean datasets rapidly developing in the machine learning space. These include molecular fingerprints (DMAI+15), community detection (YWJM22), and recommendation systems (GZL+21), and any other complex system of interactions that can be abstracted by a graph structure. Graph datasets pose challenges of different unordered node sets, edge and node weighting, and variable size node neighborhoods. As such, as deep learning approaches continue to extend to the irregularities within graph data, operations, such as convolution and attention, that have been exploited by traditional deep learning frameworks must become generalized.
View the source code here. Training functionality is provided by pytorch_lightning, and logging by Weights & Biases.
Read the full report here.
