Source-linked AI summary
Subgraph Neural Networks
Emily Alsentzer, Samuel G. Finlayson, Michelle M. Li, Marinka Zitnik
TL;DR
Existing GNNs primarily represent nodes, edges, or whole graphs, leaving subgraph prediction difficult when subgraphs have variable, disconnected, internal, positional, and external structure. SUBGNN learns subgraph-level representations with property-aware message passing and evaluates them on newly designed benchmarks. Across eight datasets, it outperforms baselines substantially, including by 19.8% over the strongest baseline.
Problem
Subgraph prediction remains limited because subgraphs can vary in size, contain multiple components, and combine internal topology with external and positional information.
Method
SUBGNN propagates neural messages between anchor patches and subgraph components through property-aware channels for position, neighborhood, and structure.
Results
SUBGNN outperforms baselines across eight datasets, improving over the strongest baseline by 19.8%.
Takeaways & Limitations
The method supports inductive prediction for larger, variable-size subgraphs with multiple connected components and performs strongly on challenging biomedical tasks.
Takeaways & Limitations
Subgraph neural networks can enable harmful applications, including toxic-community prediction and high-resolution user profiling, while bias may arise throughout model development and deployment.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper frames subgraph prediction as an underdeveloped problem because subgraphs combine variable-size, possibly disconnected topology with internal, external, and positional structure. SUBGNN addresses this through subgraph-level, property-aware message passing and is evaluated on new synthetic and real-world datasets.
- Existing GNN representations primarily target nodes, edges, or entire graphs, leaving subgraph prediction comparatively underexplored.
- Subgraphs may vary in size, contain multiple distant components, and require joint predictions over structures that are not node-centered neighborhoods.
- Subgraph prediction must capture higher-order internal connectivity and external border interactions with the surrounding graph.
- SUBGNN propagates messages at the subgraph level through three property-aware channels for position, neighborhood, and structure.The method is inductive and operates on larger, variable-size subgraphs with multiple connected components.
- SUBGNN outperforms baselines by an average of 77.4% on synthetic datasets and 125.2% on real-world datasets across eight datasets.The study also introduces synthetic benchmarks and four real-world datasets spanning biological, medical, and social domains.
2 Related Work
Related work develops representations for nodes, graphs, localized subgraphs, higher-order structures, and extracted communities, but these approaches differ from general prediction over given subgraphs. SUBGNN targets large, variable-size subgraphs that may be distributed across the underlying graph.
- Subgraph embeddings and prediction: Prior subgraph representation methods commonly focus on small, localized structures such as 3-node or 4-node subgraphs.
- Subgraph embeddings and prediction: SUBGNN instead learns representations for large, variable-size subgraphs that can be distributed throughout the graph.
- Subgraph extraction and network community detection: Community detection and related extraction methods seek internally connected, externally separated groups and are typically limited to individual connected components.
- Learning representations of higher-order structures, ego nets, and enclosing subgraphs: Hypergraph neural networks formulate higher-order message passing using spectral theory or clique expansion.
- Subgraphs and patches in GNNs: Patch-based, ego-graph, enclosing-subgraph, and local-path methods use extracted substructures for graph learning tasks such as feature extraction and link prediction.
3 Formulating Subgraph Prediction
This section formulates subgraph prediction and introduces SUBGNN as a message-passing architecture for representing and classifying variable-size subgraphs, including those with multiple components. It identifies position, neighborhood, and structure as key topology properties and routes messages from anchor patches to subgraph components.
- 3 Formulating Subgraph Prediction: A subgraph S is a labeled subset of graph G that may contain multiple connected components whose number and size are bounded by, but do not directly depend on, G.The formulation uses G = (V, E) and S = (V′, E′), with connected components defined by node-pair paths.
- 3 Formulating Subgraph Prediction: Message-passing networks use MSG, AGG, and UPDATE to propagate signals between network elements and update their embeddings.In the typical formulation, messages are propagated to a node from its neighborhood before aggregation and updating.
- 3.1 SUBGNN: Problem Formulation: SUBGNN generates a ds-dimensional representation zS for every subgraph and uses it to classify subgraph labels.Its classifier maps subgraphs to one of C labels.
- 3.1 SUBGNN: Problem Formulation: The learned embedding function captures topology needed for prediction and can extend to supervised, unsupervised, and self-supervised subgraph tasks.The paper focuses on classification but presents the embedding function as more general.
- 3.1 SUBGNN: Problem Formulation: SUBGNN operates at the subgraph level by propagating messages to each connected component, enabling representations of subgraphs with multiple distinct components.This message-passing design explicitly captures aspects unavailable at only the node or whole-graph level.
- 3.1 SUBGNN: Problem Formulation: Subgraph topology includes internal structure, border connectivity, and position and neighborhood relative to the rest of the graph.The framework defines six properties whose relative importance depends on the downstream task.
- 3.1 SUBGNN: Problem Formulation: Position includes border distance to the rest of G and internal distance between components, while neighborhood includes internal and external elements around the subgraph.Each component can have its own border neighborhood, and internal neighborhoods vary in size and position.
- 3.1 SUBGNN: Problem Formulation: Structure comprises connectivity within each component and edges linking internal nodes to the surrounding border neighborhood.Table 1 distinguishes internal nodes from border nodes in the k-hop neighborhood of the subgraph.
4 SUBGNN: SUBGRAPH NEURAL NETWORK
SUBGNN learns subgraph representations by routing property-specific messages from sampled anchor patches to subgraph components and aggregating them into final embeddings. Its modular channels separately encode position, neighborhood, and structure.
- Property-aware channels: Three dedicated channels encode position, neighborhood, and structure, with channel outputs combined into a final subgraph representation.Each channel uses sampling, anchor encoding, and similarity weighting to route messages.
- Subgraph-level message passing: SUBGNN propagates neural messages from randomly sampled, channel-specific anchor patches to subgraph components before aggregating component representations into subgraph embeddings.The aggregation scheme is defined at the subgraph-component level.
- Similarity-weighted routing: Anchor messages are weighted by channel-specific similarity functions that measure the relevance of each anchor patch to a subgraph component.Position uses shortest-path distance, while structure compares ordered degree sequences with normalized dynamic time warping.
- Property-aware representations: Property-aware outputs preserve structural or positional information that order-invariant hidden representations alone cannot capture.SUBGNN routes internal and border properties through dedicated subchannels before concatenating the final outputs.
- Complexity and extensions: A fixed number of sampled anchor patches bounds message-passing memory and time complexity as the number and size of subgraphs grow.Structural anchor representations use fixed-length random walks and are shared across subgraphs.
5 Experiments
The experiments evaluate SUBGNN on four synthetic and four real-world subgraph-classification datasets. The benchmarks target internal structure, border connectivity, position, component structure, molecular function, disease diagnosis, and user profiling.
- Experimental design: The evaluation uses four synthetic and four real-world datasets for subgraph classification.The experimental workflow includes dataset construction, baseline comparison, and classification experiments.
- Synthetic datasets: Synthetic labels represent DENSITY, CUT RATIO, CORENESS, and COMPONENT, testing internal structure, border structure, position, and component count.CORENESS combines border structure and position, while COMPONENT measures the number of subgraph components.
- Real-world datasets: PPI-BP predicts cellular-function categories for protein subgraphs drawn from a human protein-protein interaction network.The dataset contains six cellular-function categories.
- Real-world datasets: HPO-METAB and HPO-NEURO predict metabolic or neurological disease subcategories from phenotype subgraphs in a rare-disease knowledge graph.The tasks include multiclass and multilabel disease classification.
- Real-world datasets: EM-USER predicts user characteristics from workout-history subgraphs in a social fitness network.Nodes represent workouts, and edges connect workouts completed by multiple users.
6 Results
SUBGNN outperforms strong baselines across synthetic and real-world benchmarks, while channel ablations show that its specialized channels align with the properties they are designed to encode. Performance is especially strong on challenging biomedical tasks, although generalization remains an open issue.
- Synthetic results: 77.4% average improvement over baselines is reported on synthetic datasets, with an 18.4% average improvement over the strongest baseline.GC performs well on DENSITY but poorly on position or border-connectivity tasks, while meta-node baselines perform best on COMPONENT.
- Channel ablation: The structure channel performs best on CUT RATIO and DENSITY, whereas the position channel performs best on COMPONENT.These outcomes align channel performance with the corresponding border, internal-structure, and internal-position task properties.
- Channel ablation: The channel ablation analysis reports that channels encoding properties relevant to each dataset yield the best performance on the corresponding tasks.This supports the intended property-awareness of SUBGNN’s channels.
- Real-world results: 125.2% average improvement over baselines is reported on real-world datasets, with a 21.2% improvement over the strongest baseline.SUBGNN performs especially well on HPO-NEURO and HPO-METAB, which require disease-subcategory discrimination and inductive inference.
7 Conclusion
SUBGNN combines subgraph representation learning and classification with a framework for subgraph-topology challenges, eight datasets, and strong benchmark performance.
- SUBGNN performs subgraph-level message passing with property-aware channels for subgraph representation learning and classification.
- Eight datasets span four synthetic and four real-world subgraph classification tasks.
- 125.2% average improvement over baselines is reported on real-world datasets, alongside 77.4% on synthetic datasets.
Broader Impact
The paper’s broader impact includes new application opportunities, technical design choices for subgraph learning, synthetic benchmark construction, and explicit risks requiring responsible use.
- Subgraph representations support applications that require reasoning about subgraphs within a larger underlying graph.
- Subgraph classification can enable beneficial applications but also raises risks involving malicious political or social use, profiling, and bias.
- SUBGNN uses channels for neighborhood, structure, and position, with internal and border subchannels for subgraph topology.
- Triangular random walks sample structure anchor patches by varying the probability of selecting triangular versus non-triangular successors.
- Synthetic subgraphs are generated through PLANT, STAPLE, and BFS procedures targeting properties such as density, cut ratio, k-coreness, and component count.
B.2 Novel, Real-World Datasets for Subgraph Classification
The paper introduces real-world subgraph datasets from biological, medical, and social domains, with disease, protein-interaction, and workout-co-occurrence examples.
- PPI-BP uses a human protein-protein interaction network in which subgraphs group proteins involved in the same biological process.
- HPO-NEURO models rare-disease diagnosis with phenotype subgraphs containing noise, distractors, and hierarchy-derived less-specific phenotypes.
- HPO-NEURO contains 10 neurological disease categories, while HPO-METAB contains 6 metabolic disease categories.
- EM-USER uses an Endomondo workout co-occurrence graph containing cliques of popular workout combinations.
Appendix C Details on Empirical Evaluation
Empirical evaluation uses AUROC and Micro F1 across synthetic and real-world datasets, including tests of node-overlap generalization and channel ablations.
- Baseline models and SUBGNN are evaluated using Micro F1 and AUROC, with AUROC results reported for synthetic, real-world, and ablation experiments.
- The generalizability analysis measures test performance as a function of node overlap between test subgraphs and training-related subgraphs.
- Zero node overlap occurs for test subgraphs in COMPONENT and CORENESS, yet SUBGNN performs strongly on both datasets.
- On HPO-METAB, SUBGNN outperforms majority-class and random baselines at the smallest overlap levels, while further generalization research remains needed.
Appendix D Implementation Details
The appendix documents the computing setup, embedding pretraining, hyperparameter selection, baseline configurations, and SUBGNN search ranges. It also reports channel ablation and overlap-related evaluation figures.
- Computing infrastructure: Models were developed with PyTorch Geometric 1.4.3 and PyTorch Lightning 0.7.1, using single GPUs from a heterogeneous SLURM cluster.The cluster included Tesla V100, Tesla M40, Tesla K80, and GeForce GTX 1080 GPUs.
- Embedding pretraining: Node embeddings were pretrained with a 2-layer GIN, while all baselines and SUBGNN used NEIGHBORSAMPLER with k = 1.The explored embedding configurations varied batch size, learning rate, weight decay, dropout, hidden dimension, and output dimension.
- Hyperparameter tuning: Hyperparameters were selected to optimize micro F1 scores on validation datasets, with model-specific best settings reported in the project repository.The appendix describes the ranges explored for baseline and SUBGNN models.
- Baseline configurations: Baseline configurations varied batch size, learning rate, weight decay, and feed-forward dimensions, with method-specific defaults for MN-GAT and Sub2Vec-based methods.S2V-NS concatenated embeddings produced by S2V-N and S2V-S.
- SUBGNN configuration: SUBGNN tuning covered optimization, architecture, neighborhood, anchor-patch, recurrent, and feed-forward parameters across specified search ranges.The explored parameters included layer count, k-hop neighborhood size, anchor-patch counts, LSTM layers, clipping, and dropout.
Appendix E Hyperparameter sensitivity analysis
The sensitivity analysis tests how SUBGNN validation performance depends on training hyperparameters by varying one parameter at a time around the best model for each channel.
- Sensitivity procedure: Sensitivity was evaluated on HPO-METAB by varying one training hyperparameter at a time from the best-performing model for the relevant channel.Wider ranges were tested to examine model behavior at parameter extremes.