Topological Message Passing for Higher - Order and Long - Range Interactions

Lorenzo Giusti, Teodora Reu, Francesco Ceccarelli, Cristian Bodnar, Pietro Liò

TL;DR

CIN++ is an upgraded message-passing framework for Graph Neural Networks (GNNs) that operates on cell complexes rather than just simple graphs. By introducing "lower messages"—allowing higher-order structures like rings to communicate directly—it effectively captures long-range and group interactions, achieving state-of-the-art results on major molecular and peptide benchmarks.

What Problem Does This Paper Address?

Standard GNNs treat data as a collection of nodes and edges. While powerful, this "pairwise" view has two major flaws when dealing with complex systems like molecules:

  1. Oversquashing: When information has to travel across many edges to connect distant nodes, the fixed-size feature vectors become a bottleneck, losing critical information.
  2. Missing Group Interactions: In chemistry, structures like aromatic rings (e.g., benzene) behave as single units. Standard GNNs struggle to model these "higher-order" interactions in a principled way.

Previous work introduced Cellular Isomorphism Networks (CINs), which lift graphs into "cell complexes" (adding 2D "cells" or rings to the graph). However, CINs were hierarchical: rings could only talk to edges, and edges to nodes. This created a bottleneck where rings couldn't interact directly, slowing down learning and limiting the model's ability to capture the complex dynamics of supramolecular assemblies.

Methods

The authors propose CIN++, which enhances the topological message-passing scheme by adding a missing piece of the puzzle: Lower Messages.

In a cell complex, cells can now communicate in three ways:

  • Boundary Messages: Information flows from lower-dimensional cells to higher ones (e.g., an edge tells a ring about its features).
  • Upper Messages: Cells of the same dimension talk if they share a higher-dimensional boundary (e.g., two nodes talking via a shared edge).
  • Lower Messages (The Innovation): Cells of the same dimension talk if they share a lower-dimensional boundary. Crucially, this allows rings to talk directly to adjacent rings if they share a common edge, and edges to talk if they share a node.

The architecture uses Multi-Layer Perceptrons (MLPs) for message functions and updates, ensuring the model remains permutation-invariant. Theoretically, the authors prove that CIN++ is at least as expressive as the Cellular Weisfeiler-Lehman (CWL) test and provide a categorical interpretation of the model using Sheaf Theory.

Datasets

The model was evaluated on several high-impact benchmarks:

  • ZINC (Subset and Full): A standard molecular graph regressor task for predicting solubility.
  • Peptides-func & Peptides-struct: Benchmarks specifically designed to test a model's ability to handle long-range interactions in large peptide chains.
  • TUDatasets: A collection of smaller graph classification tasks (MUTAG, PTC_MR, PROTEINS, NCI1, NCI109).
  • MOLHIV: A large-scale molecular dataset from the Open Graph Benchmark (OGB).

Key Insights and Ideas

  • Direct Ring Communication: By allowing rings to exchange messages directly, CIN++ bypasses the "wait-and-see" approach of previous models. This leads to faster convergence and a better representation of aromatic stacking and other group-level chemical phenomena.
  • Topological Shortcuts: Higher-order cells (rings) act as "express lanes" for information. Instead of a message hopping through ten atoms, it can jump across a ring structure, significantly mitigating the oversquashing problem.
  • Natural Symmetry: The model's structure mirrors the physical reality of chemistry. Atoms are 0-cells, bonds are 1-cells, and rings are 2-cells. This alignment makes the model's inductive bias particularly well-suited for molecular discovery.

Key Results

CIN++ demonstrated dominant performance across the board:

  • SOTA on ZINC-Subset: Achieved a Mean Absolute Error (MAE) of 0.077, significantly outperforming previous topological and subgraph-based GNNs.
  • SOTA on Peptides: On the long-range Peptides-func task, it reached a Test AP of 0.6569. On Peptides-struct, it achieved a Test MAE of 0.2523, proving its effectiveness at capturing long-distance dependencies.
  • TUDatasets: It achieved the best results on four out of five datasets (MUTAG, PTC_MR, PROTEINS, and NCI109), showing its versatility across different types of graph data.

Limitations and Future Work

The primary limitation is computational overhead. Lifting a graph into a cell complex (identifying all rings) and passing extra messages increases the complexity compared to a simple GNN.

However, the authors note that:

  1. The "lifting" process is a one-time pre-processing step.
  2. The operations within a layer are naturally decoupled, meaning they can be executed concurrently on modern hardware to amortize the cost.

Future work could involve exploring even higher-dimensional cells (3D volumes) or developing more efficient "lifting" maps that don't require identifying every cycle in a graph.

Summary updated

Abstract

Graph Neural Networks (GNNs) have demonstrated remarkable success in learning from graph-structured data. However, they face significant limitations in expressive power, struggling with long-range interactions and lacking a principled approach to modeling higher-order structures and group interactions. Cellular Isomorphism Networks (CINs) recently addressed most of these challenges with a message passing scheme based on cell complexes. Despite their advantages, CINs make use only of boundary and upper messages which do not consider a direct interaction between the rings present in the underlying complex. Accounting for these interactions might be crucial for learning representations of many real-world complex phenomena such as the dynamics of supramolecular assemblies, neural activity within the brain, and gene regulation processes. In this work, we propose CIN++, an enhancement of the topological message passing scheme introduced in CINs. Our message passing scheme accounts for the aforementioned limitations by letting the cells receive also lower messages within each layer. By providing a more comprehensive representation of higher-order and long-range interactions, our enhanced topological message passing scheme achieves state-of-the-art results on large-scale and long-range chemistry benchmarks.
BibTeX
@inproceedings{giusti2024topological,
  author = {Lorenzo Giusti and Teodora Reu and Francesco Ceccarelli and Cristian Bodnar and Pietro Liò},
  title = {{Topological Message Passing for Higher - Order and Long - Range Interactions}},
  booktitle = {IJCNN},
  year = {2024},
  doi = {10.1109/ijcnn60899.2024.10650343},
}

Loading related content...

Figure