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.
- 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.
- 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.
- 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