Structural Landmarking and Interaction Modelling: on Resolution Dilemmas in Graph Classification

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

Introduction

In Graph Neural Networks (GNNs), the standard approach to graph-level classification involves "pooling" node representations into a single global vector. While effective for simple tasks, this "super-node" approach often acts as a bottleneck, discarding the intricate blueprint of how substructures interact. The paper "Structural Landmarking and Interaction Modelling: on Resolution Dilemmas in Graph Classification" introduces SLIM, a framework designed to preserve these structural identities and model their explicit interactions.

The Resolution Dilemma in Graph Learning

The authors identify two primary challenges that hinder effective graph representation:

  1. Vanishing Spatial Resolution: Conventional GNNs use integration-based pooling (e.g., sum or mean) to collapse a graph into a single vector. This process obscures the identities of specific sub-graphs and their relative arrangements. For instance, in molecular biology, the specific interaction between two functional groups might determine toxicity; a simple sum-pooling may fail to capture this relational nuance.
  2. Exploding Structural Resolution: Conversely, traditional graph kernels often rely on discrete motif counting. This approach is overly rigid; two substructures that are nearly identical but differ by a single edge are treated as entirely distinct. This leads to a high-dimensional, sparse feature space that overfits to rare structures and fails to generalize.

The goal of SLIM is to find the "Goldilocks" zone: a representation flexible enough to recognize structural similarities while remaining detailed enough to preserve interaction patterns.

The SLIM Framework

The SLIM model addresses these dilemmas through a three-stage pipeline that moves from local node neighborhoods to a global interaction matrix.

The SLIM pipeline: from local substructure embedding to identity-preserving interaction modeling.

1. Substructure Embedding

Instead of processing nodes in isolation, SLIM extracts local $k$-hop neighborhoods for every node. These neighborhoods are mapped into a continuous latent space using a parametric transformation (such as an autoencoder). This allows the model to cluster similar structural "parts" together in a differentiable space.

2. Structural Landmarking

The model identifies $K$ "landmarks" within this continuous embedding space. These landmarks represent prototypical structural motifs found across the dataset. Using a soft-assignment mechanism (based on Student’s t-distribution), every substructure in a given graph is described by its similarity to these universal landmarks.

3. Identity-Preserving Interaction Modelling

This stage is the core innovation of SLIM. Rather than collapsing the graph into a single vector, the model generates an interaction matrix. This matrix explicitly encodes how the identified landmarks (the "parts") are connected to one another within the specific graph instance. This preserves the "identity" of the components while capturing the global "interaction" behavior, aligning with complex systems theory where system properties emerge from component interactions.

Experimental Results and the Resolution "Sweet Spot"

SLIM was evaluated on standard benchmarks including MUTAG, PTC, NCI1, PROTEINS, and D&D. The model consistently matched or outperformed state-of-the-art GNNs like GIN and DiffPool.

A key finding of the study is the empirical validation of the "resolution dilemma." The performance of the model follows a bell-shaped curve relative to the number of landmarks ($K$).

Classification accuracy as a function of structural resolution (number of landmarks K) on MUTAG and PTC datasets.

As shown in the figure above, setting $K$ too low leads to underfitting (coarse resolution), while setting it too high leads to overfitting (delicate resolution). The optimal performance is achieved in a medium-resolution "sweet spot," typically around $K=100$ to $150$ for the tested chemical datasets.

Conclusion

The SLIM framework offers a significant departure from traditional "blender-style" graph pooling. By explicitly modeling the interactions between structural landmarks, it provides a more stable, interpretable, and accurate method for graph classification. Future work may involve dynamically learning the optimal resolution ($K$) and extending the model to hierarchical interaction scales.

Summary updated

Abstract

Graph neural networks are promising architecture for learning and inference with graph-structured data. Yet difficulties in modelling the ``parts'' and their ``interactions'' still persist in terms of graph classification, where graph-level representations are usually obtained by squeezing the whole graph into a single vector through graph pooling. From complex systems point of view, mixing all the parts of a system together can affect both model interpretability and predictive performance, because properties of a complex system arise largely from the interaction among its components. We analyze the intrinsic difficulty in graph classification under the unified concept of ``resolution dilemmas'' with learning theoretic recovery guarantees, and propose ``SLIM'', an inductive neural network model for Structural Landmarking and Interaction Modelling. It turns out, that by solving the resolution dilemmas, and leveraging explicit interacting relation between component parts of a graph to explain its complexity, SLIM is more interpretable, accurate, and offers new insight in graph representation learning.
BibTeX
@misc{zhang2020structural,
  author = {Kai Zhang and Yaokang Zhu and Jun Wang and Jie Zhang and Hongyuan Zha},
  title = {{Structural Landmarking and Interaction Modelling: on Resolution Dilemmas in Graph Classification}},
  year = {2020},
  eprint = {2006.15763},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.15763},
}
Figure