Structural Landmarking and Interaction Modelling: A "SLIM" Network for Graph Classification

Yaokang Zhu, Kai Zhang, Jun Wang, Haibin Ling, Jie Zhang, Hongyuan Zha

Introduction

Graph classification is a critical task in domains ranging from drug discovery to social network analysis. Most modern Graph Neural Networks (GNNs) follow a "collapsing-style" pooling paradigm: they aggregate node features into a single fixed-length vector to represent the entire graph. However, this approach often destroys the structural relationships and organizational logic that define complex systems. In a molecule, for instance, the toxicity might emerge from the specific interaction between two functional groups, not just their presence.

To address this, we present the SLIM (Structural Landmarking and Interaction Modelling) network. SLIM shifts from "collapsing" graphs to "projecting" them onto a learned dictionary of structural landmarks, preserving the vital interaction data that standard pooling methods lose.

The SLIM Framework

The SLIM network employs a three-step pipeline designed to capture both the identity of sub-structures and their global relationships within a graph.

The SLIM pipeline: from sub-structure embedding to interaction-preserving projection.
  1. Sub-structure Identification and Embedding: Rather than processing individual nodes, SLIM identifies $k$-hop rooted subtrees. These are mapped into a continuous metric space using a nonlinear transformation. To ensure these embeddings reflect both topology and context, a parametric node2vec loss is utilized, encouraging sub-structures that are frequently connected to reside closer in the embedding space.
  2. Structural Landmarking: To manage the vast diversity of possible sub-structures, SLIM learns a "codebook" of $K$ structural landmarks (representative cluster centers) across the entire dataset via unsupervised deep clustering. Every sub-structure in an input graph is then "soft-assigned" to these landmarks.
  3. Interaction Preserving Projection: This is the core innovation. Instead of a single vector, SLIM represents each graph as a $K \times K$ interaction matrix. This matrix quantifies how the $K$ types of landmarks interact with each other within a specific graph instance. This "landmark graph" has a fixed size regardless of the original graph's complexity, making it compatible with standard fully connected layers for final classification.

Experimental Results

The authors evaluated SLIM against state-of-the-art GNNs (such as GIN, DiffPool, and SAG) across eight benchmark datasets in bioinformatics and social networks.

  • Bioinformatics/Cheminformatics: SLIM achieved top performance on MUTAG (93.28%), PTC (72.41%), and NCI1 (80.53%). These results highlight its effectiveness in domains where chemical sub-structures and their interactions are primary drivers of properties.
  • Social Networks: While competitive on IMDB datasets, SLIM was slightly less dominant on COLLAB. This suggests that the model's reliance on rich node features to identify landmarks may be a bottleneck in social graphs where such features are often sparse.

Key Insights

  • Interaction Over Density: Ablation studies demonstrate that the interaction between landmarks is a significantly more powerful feature for classification than simply counting landmark occurrences (density).
  • Global Coordinate System: By learning landmarks across the entire dataset, SLIM establishes a common "platform." Every graph is projected onto the same $K$ landmarks, facilitating direct comparison across varying topologies.
  • Stability and Convergence: The integration of unsupervised regularization (deep clustering and node2vec losses) allows SLIM to reach peak performance earlier and with lower variance compared to purely supervised models like GIN.

Conclusion and Future Work

SLIM offers a robust alternative to standard pooling by focusing on the emergent properties of interacting sub-structures. Future work will explore more complex sub-structure shapes beyond $k$-hop subtrees and investigate adaptive methods for determining the optimal number of landmarks ($K$). By moving away from "squeezing" graphs into vectors, SLIM paves the way for more structurally-aware graph representation learning.

Summary updated

Abstract

Graph neural networks are a promising architecture for learning and inference with graph-structured data. Yet, how to generate informative, fixed dimensional features for graphs with varying size and topology can still be challenging. Typically, this is achieved through graph-pooling, which summarizes a graph by compressing all its nodes into a single vector. Is such a “collapsing-style” graph-pooling the only choice for graph classification? From complex system’s point of view, properties of a complex system arise largely from the interaction among its components. Therefore, we speculate that preserving the interacting relation between parts, instead of pooling them together, could benefit system level prediction. To verify this, we propose SLIM, a graph neural network model for Structural Landmarking and Interaction Modelling. The main idea is to compute a set of end-to-end optimizable sub-structure landmarks, so that any input graph can be projected onto these (spatially) local structural representatives for a faithful, global characterization. By doing so, explicit interaction between component parts of a graph can be leveraged directly in generating discriminative graph representation. Encouraging results are observed on benchmark datasets for graph classification, demonstrating the value of interaction modelling in the design of graph neural networks.
BibTeX
@inproceedings{zhu2022structural,
  author = {Yaokang Zhu and Kai Zhang and Jun Wang and Haibin Ling and Jie Zhang and Hongyuan Zha},
  title = {{Structural Landmarking and Interaction Modelling: A "SLIM" Network for Graph Classification}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i8.20912},
}
Figure