Stochastic Subgraph Neighborhood Pooling for Subgraph Classification

Subgraph classification is an emerging field in graph representation learning where the task is to classify a group of nodes (i.e., a subgraph) within a graph (e.g., identifying rare diseases given a collection of phenotypes). Graph neural network (GNN) solutions for node, link, and graph tasks fail to perform well on subgraph classification as they do not capture the external topology of the subgraph (i.e., how the subgraph is located within the larger graph). The current state-of-the-art models address this shortcoming through either labeling tricks or multiple message-passing channels, which are computationally expensive and not scalable to large graphs. To address the scalability issue while maintaining generalization, we propose Stochastic Subgraph Neighborhood Pooling (SSNP), which jointly aggregates the subgraph and its neighborhood (i.e., external topology) information while removing the need for any computationally expensive operations (e.g. labeling tricks). Our extensive experiments demonstrate that SSNP outperforms or is comparable to state-of-the-art methods while being up to 13x faster in runtime.