Source-linked AI summary
Global to Local: Topology-Preserving Adaptive Graph Pooling via Granular-Ball
Sen Zhao, Gaojie Xu, Shuyin Xia, Yifan Guan, Yi Liu, Yi Wang, Wei Wang
TL;DR
Existing pooling methods can neglect global-to-local topology and adaptive granularity by progressively coarsening overly fine-grained node representations. TPAGP dynamically partitions graphs into granular-balls using node features and topology, while its multi-granularity network optimizes information across levels. Across benchmark datasets, TPAGP achieves the highest accuracy and outperforms existing baselines, including by over 3% on DD and PTC_MR versus the best alternatives.
Problem
Existing pooling methods progressively coarsen fine-grained node representations, neglecting global-to-local topological patterns and adaptive granularity.
Method
TPAGP dynamically partitions graphs into granular-balls using node features and topology, then jointly processes features across granularities with a multi-granularity graph network.
Results
TPAGP achieves the highest accuracy on all benchmark datasets, surpassing the best alternative models by over 3% on DD and PTC_MR.
Takeaways & Limitations
TPAGP adaptively preserves crucial node and edge information while capturing local and global patterns for graph representation learning.
Abstract
from arXiv · showhide
Graph pooling aims to compress the graph, including both node embeddings and their underlying topological patterns, into a more compact representation. Previous works focus primarily on the overly fine-grained representation of nodes, progressively coarsening the graph by removing nodes or merging them into clusters, thus neglecting the global-to-local patterns and adaptive granularity of the graph's topological structure. In the real scenario, graphs as a whole can be considered the coarsest level of granularity, encapsulating the global topological structure, with progressively finer-grained local topological structures represented from top to bottom. This process continues until the adaptive granularity for each subdomain is reached. To this end, we propose a novel Topology-Preserving Adaptive Graph Pooling (TPAGP) method that dynamically partitions graphs into granular balls by integrating node features and topological information, enabling the generation of multi-granularity representations that effectively capture both local and global structural patterns. Additionally, we design a multi-granularity graph network model that facilitates feature interaction and optimization across different granularities, significantly enhancing performance in graph classification tasks. Experimental results demonstrate that TPAGP outperforms existing pooling methods across various benchmark datasets, effectively mitigating information loss caused by fixed-granularity strategies.
1 Introduction
Graph pooling must preserve topology across global-to-local scales while adapting granularity to heterogeneous subregions. TPAGP addresses this by partitioning graphs into multi-granularity granular-balls and jointly optimizing representations across levels.
- Existing hierarchical methods progressively remove nodes or merge clusters, emphasizing local information while neglecting global-to-local topology and adaptive granularity.
- Real-world graphs contain subregions with distinct topological structures and varying granularities, with similar nodes indicating local topological coherence.
- Graphs can be represented hierarchically from a coarsest whole-graph level to finer structures until each subdomain reaches its adaptive granularity.
- TPAGP adaptively partitions graphs into granular-balls by integrating node features and topology, producing representations that capture local and global structural patterns.
- Its multi-granularity graph network collaboratively processes and optimizes features across granular-balls to facilitate information transfer between levels.
2 Relation work
Graph pooling produces graph-level representations by aggregating or selecting nodes, while hierarchical methods progressively map graphs to coarser versions. These approaches include global aggregation, node dropping, and node clustering, each targeting compact higher-level representations.
- Graph pooling downscales graphs through node aggregation or selection to support graph-level representations for classification.
- Global pooling commonly sums or averages node representations but can miss intricate structural dependencies and hierarchical multi-scale organization.
- Hierarchical pooling progressively maps graphs to coarser versions, enabling higher-level representations through node dropping or node clustering.
3 Our Method
TPAGP builds graph representations from a globally initialized hierarchy of granular-balls, then adaptively refines locally while evaluating granularity with topological data analysis. Its graph model combines granular-ball pooling with hierarchical graph convolution to preserve structural information across scales.
- Topology-Preserving Adaptive Graph Pooling: TPAGP proposes topology-preserving adaptive graph pooling using granular-balls to represent graph structure across multiple granularities.The method is designed to preserve both local and global structural patterns through adaptive partitioning.
- Global Topology-Aware Granular Initialization: The process begins with the whole graph as one coarse granular-ball and initializes N granular-balls while preserving intrinsic topological characteristics.The initialization follows a global-precedence principle before producing an initial partition.
- Global Topology-Aware Granular Initialization: Initial centers are selected from high-degree nodes, and multi-source BFS assigns each node to its closest center using shortest-path distances.This topology-aware assignment encourages structurally important centers and cohesive granular-ball regions.
- Local Topology-Preserving Granular Optimization: Local optimization splits a granular-ball when its quality is lower than the combined quality of two candidate child balls, using high-degree centers and topology-aware BFS.Recursive splitting continues until granular-balls satisfy the quality condition.
- Adaptive Granularity Quality Evaluation: Granular-ball quality is evaluated with TDA by constructing Rips complexes from node features and summing persistence-bar durations across dimensions.Adjusting the Rips-complex distance threshold captures feature-point-cloud structure at different granularities.
- Model Architecture: The model alternates graph convolution and granular-ball pooling to learn bottom-up representations from local regions to global structures, then trains end-to-end.The resulting architecture is intended to preserve structural information at different granularities while supporting graph classification.
4 Experiment
Experiments evaluate TPAGP against graph neural network and pooling baselines, ablate its components, test layer-depth sensitivity, and visualize adaptive granular-ball pooling across datasets. TPAGP achieves the highest accuracy across benchmark datasets, while ablations and sensitivity analysis support the importance of its multi-granularity design and three-layer setting.
- Comparison Experiments: TPAGP achieves the highest accuracy on all benchmark datasets, outperforming the best alternatives by over 3% on DD and PTC_MR.The comparison includes GNN-based methods and graph pooling methods; Table 2 reports test accuracy and statistically significant improvements at p-value < 0.01.
- Comparison Experiments: TPAGP dynamically refines pooling granularity according to intrinsic graph structure, retaining crucial node and edge information across diverse graph domains.The reported datasets include molecular and social-network graphs, where TPAGP maintains consistently high accuracy despite other methods’ performance fluctuations.
- Ablation Studies: Removing granular-ball pooling and multi-granularity interaction causes a significant performance drop, showing that these mechanisms support preservation of local and global graph patterns.The ablation study compares the full model with configurations excluding granular-ball pooling or the multi-granularity graph network model.
- Ablation Studies: Excluding the multi-granularity graph network model produces particularly poor performance, especially in AUC, underscoring the role of topology and feature interactions.The complete TPAGP architecture is reported as essential for robust graph representation learning.
- Hyper-parameter Sensitivity Analysis: Increasing GNN depth from 2 to 3 layers consistently improves performance across datasets, whereas 4 layers degrade performance, likely because of over-smoothing.The authors identify 3 layers as the balance between expressive power and topological fidelity for TPAGP.
- Case Study: The case-study visualization represents distinct node categories by colors and TPAGP-generated granular balls by circles, with each ball aggregated into a pooled super node.The visualization illustrates adaptive granular balls formed from local and global topological features for multi-level pooling.
5 Conclusion
TPAGP provides an adaptive graph-pooling solution that adjusts granular-ball granularity for diverse graph characteristics. Experiments report superior graph-classification performance against state-of-the-art methods.
- TPAGP dynamically adjusts granular-ball granularity to adapt graph pooling to diverse graph characteristics.
- Extensive experiments validate TPAGP’s superior performance in graph classification compared with state-of-the-art methods.
A Dataset Introduction
The evaluation uses six graph datasets spanning molecular, semantic image, biological, protein, carcinogenicity, and social-network applications.
- MUTAG is a small molecular graph dataset for predicting molecular mutagenicity.
- MSRC_9 is a semantic graph dataset for predicting region categories in image segmentation.
- BZR focuses on studying interactions among bioactive molecules.
- DD contains protein structures for biological graph-learning tasks.
- PTC_MR is a molecular graph dataset for predicting carcinogenicity in rodents.
- IMDB-MULTI is a social-network dataset for graph-based movie-genre classification.