Structural Entropy Guided Graph Hierarchical Pooling

1. Introduction

• Graph neural networks apply convolution to graph data, while pooling hierarchically compresses nodes into compact representations.The paper situates pooling alongside convolution as a key direction in graph neural networks.Source: §1 · p. 1
• Existing pooling methods can lose information through node dropping, damage local structure under fixed compression quotas, and produce suboptimal assignments by optimizing each layer without considering relationships among layers.The authors identify fixed cluster counts for clustering-based methods and fixed compression ratios for node-drop methods.Source: §1 · pp. 1–2
• SEP uses structural-entropy minimization to generate all hierarchical cluster assignments through a globally optimized algorithm, without learning or fixed layer-specific compression quotas.The method depends on the number of compression layers rather than a quota for each layer.Source: §1 · p. 2
• SEP surpasses state-of-the-art hierarchical pooling methods on most graph-classification benchmarks, especially social-network datasets, and outperforms the same-architecture g-U-Nets and most baselines on node classification.The authors also report an illustration of local-structure damage from previous methods.Source: §1 · p. 2
• The paper presents SEP as a structural-information-theory-inspired hierarchical pooling approach designed to address local-structure damage and suboptimal pooling.The authors describe validation across graph reconstruction, graph classification, and node classification tasks.Source: §1 · p. 2

2. Related Work

• Node-dropping methods select important nodes but can lose information and create isolated subgraphs, while node-clustering methods merge nodes into clusters.Examples include TopKPool, SAGPool, and ASAP for node dropping, and DiffPool and MinCutPool for clustering.Source: §2 · p. 2
• Node clustering avoids the information loss associated with dropping nodes, but fixed compression quotas can still damage local graph structure.The cited clustering approaches include DiffPool and MinCutPool.Source: §2 · p. 2
• Structural entropy measures the complexity of a graph's hierarchical structure and serves as a natural node-clustering method.Two- and three-dimensional structural entropy assess two- and three-level hierarchies, respectively.Source: §2 · p. 2

3.1. Preliminaries

• Hierarchical pooling coarsens a graph into representative nodes and a new graph using cluster assignments; the next feature matrix merges current hidden features, while the next adjacency uses current node connectivities.Source: §3.1 · p. 3

3.2. Cluster Assignments via Structural Entropy Minimization

• The optimal coding tree encodes a graph’s hierarchical division, and avoiding layer-specific compression quotas is stated to retain local structure.Structural entropy is the minimum entropy over coding trees for the graph.Source: §3.2 · p. 3
• Structural entropy minimization builds a coding tree in three stages—merge to reduce entropy, compress to height k, then fill cross-layer gaps—and yields the cluster assignments.The fill stage preserves information transmission without changing the tree’s structural entropy.Source: §3.2 · p. 4
• Algorithm 1 has runtime O(2n + hmax(m log n + n)); with hmax around log n and m ≫ n, runtime almost scales linearly with edges.The authors attribute hmax’s approximate log n scale to the coding tree tending to be balanced.Source: §3.2 · p. 5

3.3. Graph Neural Network for Graph Classification

• SEP-G stacks three GCN–SEP blocks and summarizes outputs from each block into a graph-level representation for classification.The SEP layer is permutation invariant, so permuting node order does not change its output when the adjacency and features are permuted accordingly.Source: §3.3 · p. 5, Figure 2 · p. 5

3.4. Graph Neural Network for Node Classification

• SEP-N is an encoder–decoder for node classification, using SEP to downsample, SEP-U to unpool, same-level skip connections, and a final GCN prediction layer.The skip connections are described as enabling spatial information transmission for better performance.Source: §3.4 · p. 5, Figure 3 · p. 5

4.1. Graph Reconstruction

• In ring and grid reconstruction, node drop loses the original shape, MinCutPool distorts key regions, and SEP nearly reconstructs the ring while retaining the grid center.The experiments use synthetic graphs with node coordinates as features and an autoencoder trained to minimize reconstruction MSE.Source: §4.1 · p. 6, Figure 4 · p. 6

4.2. Graph Classification

• SEP-G is better or competitive overall and improves uniformly on social-network benchmarks; on NCI1, pooling does not surpass GIN.Across backbones, SEP variants are overall superior; SEP with GAT obtains better performance on IMDB-MULTI, PROTEINS, DD, and NCI1.Source: §4.2 · pp. 6–7, Table 1 · p. 7
• On MUTAG, DiffPool and MinCutPool break molecular ring structures into pieces, whereas SEP preserves these essential structures after the first coarsening.The comparison shows clustering results for samples from MUTAG.Source: §4.2 · p. 7, Figure 5 · p. 7

4.3. Node Classification

• SEP-N is not best on any of the three datasets, but beats GCN, GAT, and GIN on all three and g-U-Nets on Cora and Pubmed using five GCN layers.Its best performance across the three datasets occurs with at most two blocks; SEP-N also achieves superior performance on Citeseer with one encoder-decoder pair.Source: §4.3 · pp. 8–9, Table 3 · p. 8, Table 4 · p. 9

• SEP uses structural entropy minimization to capture connectivity among pooling layers and address local-structure damage associated with node-compression hyperparameters.The conclusion identifies combining structural entropy with node features as a future-work direction.Source: §5 · p. 9
• The paper introduces SEP-G for graph classification and SEP-N for node classification, both built on the proposed pooling method.Source: §5 · p. 9
• Experiments report significant improvements for SEP-G on graph classification and superior performance for SEP-N compared with other GNNs on node-classification tasks.Source: §5 · p. 9

• The appendix section is devoted to experimental details for three graph tasks.Source: A. Experiment Setup · p. 11
• Graph reconstruction is one of the covered experimental tasks.Source: A. Experiment Setup · p. 11
• Graph classification and node classification are also covered.Source: A. Experiment Setup · p. 11

• The synthetic ring and grid graphs use 2-D node coordinates as features and adjacency to encode connectivity; the goal is to restore node locations after pooling.Source: §A.1 · p. 11
• The autoencoder minimizes MSE between input and reconstructed features; experiments compare node-drop and clustering methods with SEP under a 25% pooling ratio.Models use two message-passing layers before pooling and after unpooling; the synthetic graph setup trains and tests on the same given graph.Source: §A.1 · p. 11
• SEP nearly reconstructs the ring and retains the essential grid-center structure, while node-drop methods lose graph shape and clustering baselines distort key regions.Source: §A.1 · p. 11

A.2. Graph Classification

• Social-network benchmarks include actor collaboration graphs from movie genres and scientific collaboration ego networks labeled by research field.IMDB-BINARY and IMDB-MULTI represent movie collaborations; COLLAB combines three scientific collaboration datasets.Source: §A.2 · p. 11
• Bioinformatics benchmarks cover protein structures and chemical-compound graphs, with labels for protein type, carcinogenicity, or compound category.The described datasets include D&D, PROTEINS, PTC, NCI1, and MUTAG.Source: §A.2 · pp. 11, 13
• Initial node features are degree one-hots for social graphs and degree one-hots combined with categorical labels for bioinformatics graphs.Source: §A.2 · p. 13
• The evaluation uses 10-fold cross-validation, a 10% training-data validation split, and test averages across 10 runs.Baselines use a 25% pooling ratio per layer, while SEP uses Algorithm 1’s natural cluster assignments at height 3.Source: §A.2 · p. 13

A.3. Node Classification

• Cora, Citeseer, and Pubmed are citation networks with document nodes, undirected citation edges, bag-of-words features, and node class labels.Cora and Citeseer use one-hot word features, while Pubmed uses TF-IDF weighted word vectors.Source: §A.3 · p. 13
• The transductive setup allows 20 training nodes per class and evaluates predictions on 1,000 test nodes, with 500 nodes for validation.SEP-N uses assignment matrices guided by three-dimensional structural entropy and the first two pooling layers.Source: §A.3 · p. 13
• With 5 GCN layers, SEP-N outperforms S2GC and GCNII using similar convolution-layer counts on node classification.The compared methods require 16 layers for S2GC and 64 for GCNII on Cora, 32 on Citeseer, and 16 on Pubmed.Source: §A.3 · p. 13, Table A.1 · p. 14