Structural Entropy Guided Graph Hierarchical Pooling

• URL: http://arxiv.org/abs/2206.13510v1
• Date: Sun, 26 Jun 2022 06:30:54 GMT
• Title: Structural Entropy Guided Graph Hierarchical Pooling
• Authors: Junran Wu, Xueyuan Chen, Ke Xu, Shangzhe Li
• Abstract summary: We propose a hierarchical pooling approach, SEP, to tackle the two issues of local structure damage and suboptimal problem. SEP outperforms state-of-the-art graph pooling methods on graph classification benchmarks and obtains superior performance on node classifications.
• Score: 8.080910755718511
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Following the success of convolution on non-Euclidean space, the corresponding pooling approaches have also been validated on various tasks regarding graphs. However, because of the fixed compression quota and stepwise pooling design, these hierarchical pooling methods still suffer from local structure damage and suboptimal problem. In this work, inspired by structural entropy, we propose a hierarchical pooling approach, SEP, to tackle the two issues. Specifically, without assigning the layer-specific compression quota, a global optimization algorithm is designed to generate the cluster assignment matrices for pooling at once. Then, we present an illustration of the local structure damage from previous methods in the reconstruction of ring and grid synthetic graphs. In addition to SEP, we further design two classification models, SEP-G and SEP-N for graph classification and node classification, respectively. The results show that SEP outperforms state-of-the-art graph pooling methods on graph classification benchmarks and obtains superior performance on node classifications.

Related papers

• HC-GAE: The Hierarchical Cluster-based Graph Auto-Encoder for Graph Representation Learning [24.641827220223682]
  We develop a novel Hierarchical Cluster-based GAE (HC-GAE) that can learn effective structural characteristics for graph data analysis. The proposed HC-GAE can generate effective representations for either node classification or graph classification, and the experiments demonstrate the effectiveness on real-world datasets.
  arXiv  Detail & Related papers  (2024-05-23T16:08:04Z)
• SSHPool: The Separated Subgraph-based Hierarchical Pooling [47.78745802682822]
  We develop a novel local graph pooling method, namely the Separated Subgraph-based Hierarchical Pooling (SSH) for graph classification. We individually employ the local graph convolution units as the local structure to further compress each subgraph into a coarsened node. We develop an end-to-end GNN framework associated with the SSHPool module for graph classification.
  arXiv  Detail & Related papers  (2024-03-24T13:03:35Z)
• Graph Parsing Networks [64.5041886737007]
  We propose an efficient graph parsing algorithm to infer the pooling structure, which then drives graph pooling. The resulting Graph Parsing Network (GPN) adaptively learns personalized pooling structure for each individual graph.
  arXiv  Detail & Related papers  (2024-02-22T09:08:36Z)
• Higher-order Clustering and Pooling for Graph Neural Networks [77.47617360812023]
  Graph Neural Networks achieve state-of-the-art performance on a plethora of graph classification tasks. HoscPool is a clustering-based graph pooling operator that captures higher-order information hierarchically. We evaluate HoscPool on graph classification tasks and its clustering component on graphs with ground-truth community structure.
  arXiv  Detail & Related papers  (2022-09-02T09:17:10Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  We propose a graph gradual pruning framework termed CGP to dynamically prune GNNs. Unlike LTH-based methods, the proposed CGP approach requires no re-training, which significantly reduces the computation costs. Our proposed strategy greatly improves both training and inference efficiency while matching or even exceeding the accuracy of existing methods.
  arXiv  Detail & Related papers  (2022-07-18T14:23:31Z)
• SIGMA: A Structural Inconsistency Reducing Graph Matching Algorithm [21.1095092767297]
  We propose a novel criterion to measure the graph matching accuracy, structural inconsistency (SI) Specifically, SI incorporates the heat diffusion wavelet to accommodate the multi-hop structure of the graphs. We show that SIGMA can be derived by using a mirror descent method to solve the Gromov-Wasserstein distance with a novel K-hop-structure-based matching costs.
  arXiv  Detail & Related papers  (2022-02-06T15:18:37Z)
• Towards Unsupervised Deep Graph Structure Learning [67.58720734177325]
  We propose an unsupervised graph structure learning paradigm, where the learned graph topology is optimized by data itself without any external guidance. Specifically, we generate a learning target from the original data as an "anchor graph", and use a contrastive loss to maximize the agreement between the anchor graph and the learned graph.
  arXiv  Detail & Related papers  (2022-01-17T11:57:29Z)
• Structure-Aware Hierarchical Graph Pooling using Information Bottleneck [2.7088996845250897]
  Graph pooling is an essential ingredient of Graph Neural Networks (GNNs) in graph classification and regression tasks. We propose a novel pooling method named as HIBPool where we leverage the Information Bottleneck (IB) principle. We also introduce a novel structure-aware Discriminative Pooling Readout (DiP-Readout) function to capture the informative local subgraph structures in the graph.
  arXiv  Detail & Related papers  (2021-04-27T07:27:43Z)
• Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
  This paper proposes a novel unsupervised approach called spatial-spectral clustering with anchor graph (SSCAG) for HSI data clustering. The proposed SSCAG is competitive against the state-of-the-art approaches.
  arXiv  Detail & Related papers  (2021-04-24T08:09:27Z)
• SimPool: Towards Topology Based Graph Pooling with Structural Similarity Features [0.0]
  This paper proposes two main contributions, the first is a differential module calculating structural similarity features based on the adjacency matrix. The second main contribution is on integrating these features with a revisited pooling layer DiffPool arXiv:1806.08804 to propose a pooling layer referred to as SimPool. Experimental results demonstrate that as part of an end-to-end Graph Neural Network architecture SimPool calculates node cluster assignments that resemble more to the locality.
  arXiv  Detail & Related papers  (2020-06-03T12:51:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.