Subgraph Neural Networks

Abstract

Deep learning methods for graphs achieve remarkable performance on many node-level and graph-level prediction tasks. However, despite the proliferation of the methods and their success, prevailing Graph Neural Networks (GNNs) neglect subgraphs, rendering subgraph prediction tasks challenging to tackle in many impactful applications. Further, subgraph prediction tasks present several unique challenges: subgraphs can have non-trivial internal topology, but also carry a notion of position and external connectivity information relative to the underlying graph in which they exist. Here, we introduce SubGNN, a subgraph neural network to learn disentangled subgraph representations. We propose a novel subgraph routing mechanism that propagates neural messages between the subgraph's components and randomly sampled anchor patches from the underlying graph, yielding highly accurate subgraph representations. SubGNN specifies three channels, each designed to capture a distinct aspect of subgraph topology, and we provide empirical evidence that the channels encode their intended properties. We design a series of new synthetic and real-world subgraph datasets. Empirical results for subgraph classification on eight datasets show that SubGNN achieves considerable performance gains, outperforming strong baseline methods, including node-level and graph-level GNNs, by 19.8% over the strongest baseline. SubGNN performs exceptionally well on challenging biomedical datasets where subgraphs have complex topology and even comprise multiple disconnected components.

arXiv commentE.A. and S.G.F. contributed equally

References in corpus (22)

• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Graph Embedding Techniques, Applications, and Performance: A Survey
• Modeling polypharmacy side effects with graph convolutional networks
• Graph Neural Networks: A Review of Methods and Applications
• Higher-order organization of complex networks
• Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks
• Fast Graph Representation Learning with PyTorch Geometric
• Representation Learning on Graphs with Jumping Knowledge Networks
• Learning Convolutional Neural Networks for Graphs
• Structure and inference in annotated networks
• Learning Structural Node Embeddings Via Diffusion Wavelets
• MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing
• Strategies for Pre-training Graph Neural Networks
• Position-aware Graph Neural Networks
• Learning Graph-Level Representation for Drug Discovery
• Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputs
• Genetic Co-Occurrence Network across Sequenced Microbes
• Unsupervised Inductive Graph-Level Representation Learning via Graph-Graph Proximity
• Graph Warp Module: an Auxiliary Module for Boosting the Power of Graph Neural Networks in Molecular Graph Analysis
• Ripple Walk Training: A Subgraph-based training framework for Large and Deep Graph Neural Network
• Online Dense Subgraph Discovery via Blurred-Graph Feedback

Cited by in corpus (8)

• SumGNN: Multi-typed Drug Interaction Prediction via Efficient Knowledge Graph Summarization
• Anomaly Detection in Dynamic Graphs: A Comprehensive Survey
• RoSGAS: Adaptive Social Bot Detection with Reinforced Self-Supervised GNN Architecture Search
• SUREL+: Moving from Walks to Sets for Scalable Subgraph-based Graph Representation Learning
• Recognizing Predictive Substructures with Subgraph Information Bottleneck
• RegionGCN: Spatial-Heterogeneity-Aware Graph Convolutional Networks
• Hybrid Focal and Full-Range Attention Based Graph Transformers
• Methodology for Identifying Social Groups within a Transactional Graph