  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. Subgraph classification has applications such as predicting the cellular
function of a group of proteins or identifying rare diseases given a collection
of phenotypes. Graph neural networks (GNNs) are the de facto solution for node,
link, and graph-level tasks but fail to perform well on subgraph classification
tasks. Even GNNs tailored for graph classification are not directly
transferable to subgraph classification as they ignore the external topology of
the subgraph, thus failing to capture how the subgraph is located within the
larger graph. The current state-of-the-art models for subgraph classification
address this shortcoming through either labeling tricks or multiple
message-passing channels, both of which impose a computation burden and are 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 without any computationally expensive operations such as
labeling tricks. To improve scalability and generalization further, we also
propose a simple data augmentation pre-processing step for SSNP that creates
multiple sparse views of the subgraph neighborhood. We show that our model is
more expressive than GNNs without labeling tricks. Our extensive experiments
demonstrate that our models outperform current state-of-the-art methods (with a
margin of up to 2%) while being up to 3X faster in training.
