Cell Attention Networks

Lorenzo Giusti, Claudio Battiloro, Lucia Testa, Paolo Di Lorenzo, Stefania Sardellitti, Sergio Barbarossa

TL;DR

Cell Attention Networks (CANs) extend the power of graph attention to higher-order structures by representing data as "cell complexes." By moving beyond simple node-to-node relationships and incorporating hierarchical edge-level attention and pooling, CANs achieve state-of-the-art results on molecular and social network benchmarks with lower computational complexity than previous topological methods.

What Problem Does This Paper Address?

Standard Graph Neural Networks (GNNs) and Graph Attention Networks (GATs) are built on a fundamental assumption: data relationships are pairwise. They treat a graph as a collection of nodes connected by edges. However, many real-world systems—like the rings in a chemical molecule or multi-way interactions in a social group—involve "higher-order" relationships that a simple edge cannot fully capture.

While hypergraph-based methods exist, they often lack the rich algebraic structure needed for efficient processing. This paper addresses the gap in modeling these complex, multi-way interactions by leveraging Topological Deep Learning, specifically using cell complexes to represent the underlying geometry of data more faithfully than a standard graph.

Methods

The authors introduce Cell Attention Networks (CANs), a hierarchical architecture that operates primarily at the edge level. The process follows four main stages:

  1. Cellular Lifting Map: The input graph is "lifted" into a 2-dimensional cell complex. This means identifying "cells" like induced cycles (triangles, squares, etc.) and treating them as higher-order components (2-cells).
  2. Attentional Lift: Since most datasets only provide features for nodes, CANs use a symmetric self-attention mechanism to "lift" node features into edge features. This ensures the model starts with a rich representation of the connections themselves.
  3. Cell Attention Layers: This is the core innovation. Unlike standard GATs that look at neighboring nodes, CANs look at neighboring edges. It uses two independent masked self-attention mechanisms:
  4. Lower Attention: Focuses on edges that share a common vertex.
  5. Upper Attention: Focuses on edges that are part of the same polygon (2-cell).
  6. Hierarchical Edge Pooling: To reduce complexity and extract the most meaningful features, the model uses a self-attention-based pooling layer to downsample the edges, keeping only the most "important" ones for the final classification task.

Datasets

The authors evaluated CANs on five well-known benchmarks from the TUDataset collection, primarily focused on molecular and macromolecular classification:

  • MUTAG & PTC: Small molecules where the task is to identify mutagenicity or carcinogenicity.
  • PROTEINS: Secondary structure elements of proteins.
  • NCI1 & NCI109: Datasets aimed at identifying chemical compounds effective against lung and ovarian cancer cells.

Key Insights and Ideas

  • The Power of the "Upper" Neighborhood: By looking at edges that share a polygon (Upper Attention), the model can explicitly "see" the rings in a molecule. Standard GNNs can only infer these structures indirectly through multiple layers of message passing.
  • Explainability by Design: Because the model is fully attentional, researchers can inspect the attention coefficients. For example, in a chemistry task, high "upper attention" scores can highlight which specific rings in a molecule are driving its biological activity.
  • Efficiency vs. Expressivity: Previous topological models (like CW Networks) are powerful but computationally heavy. CANs provide a "low-complexity" alternative that remains permutation invariant (meaning the result doesn't change if you reorder the nodes or edges).
  • Lifting Matters: The ablation study revealed that the "Attentional Lift" (how node features become edge features) is often the most critical component for performance, especially on datasets like NCI1.

Key Results

CANs demonstrated superior performance compared to both traditional graph kernels and modern GNNs (like GIN and GSN).

  • Top Performance: CANs achieved the highest accuracy on 4 out of 5 benchmarks (MUTAG, PTC, PROTEINS, and NCI1).
  • Specific Gains: On the MUTAG dataset, CAN reached 94.1% accuracy, outperforming the previous best topological model (CIN) which scored 92.7%.
  • Consistency: Even on the NCI109 dataset where it didn't take the top spot, it performed within a fraction of a percent of the state-of-the-art, proving its robustness across different types of graph data.

Limitations and Future Work

The authors acknowledge a few areas for further exploration:

  • Expressivity Analysis: While CANs perform well, a formal theoretical analysis (using the Weisfeiler-Lehman framework) is needed to define exactly which graph isomorphisms CANs can and cannot distinguish compared to other models.
  • Spectral Perspectives: The current model is "non-spectral" (spatial). The authors suggest that reinterpreting CANs through the lens of Topological Signal Processing (using Hodge Laplacians) could yield even more sophisticated filtering techniques.
  • Scaling: While lower complexity than some peers, the process of finding all chordless cycles (the lifting map) can still be a bottleneck for extremely large, dense graphs. Future work may involve more efficient "lifting" heuristics.

Summary updated

Abstract

Since their introduction, graph attention networks achieved outstanding results in graph representation learning tasks. However, these networks consider only pairwise relationships among nodes and then they are not able to fully exploit higher-order interactions present in many real world data-sets. In this paper, we introduce Cell Attention Networks (CANs), a neural architecture operating on data defined over the vertices of a graph, representing the graph as the 1-skeleton of a cell complex introduced to capture higher order interactions. In particular, we exploit the lower and upper neighborhoods, as encoded in the cell complex, to design two independent masked self-attention mechanisms, thus generalizing the conventional graph attention strategy. The approach used in CANs is hierarchical and it incorporates the following steps: i) a lifting algorithm that learns {\it edge features} from {\it node features}; ii) a cell attention mechanism to find the optimal combination of edge features over both lower and upper neighbors; iii) a hierarchical {\it edge pooling} mechanism to extract a compact meaningful set of features. The experimental results show that CAN is a low complexity strategy that compares favorably with state of the art results on graph-based learning tasks.
BibTeX
@inproceedings{giusti2023cell,
  author = {Lorenzo Giusti and Claudio Battiloro and Lucia Testa and Paolo Di Lorenzo and Stefania Sardellitti and Sergio Barbarossa},
  title = {{Cell Attention Networks}},
  booktitle = {IJCNN},
  year = {2023},
  doi = {10.1109/ijcnn54540.2023.10191530},
}
Figure