Graph U-Net

The core innovation of Graph U-Net is the gPool layer, which adaptively selects a subset of nodes to form a coarser graph. Unlike global pooling, gPool projects node features onto a learnable vector p to generate scalar projection scores. The top-k nodes with the highest scores are retained, and the adjacency matrix is reconstructed using only the edges between these selected nodes. This operation is fully differentiable, allowing the network to learn which nodes are most important for the task.

To restore the original graph topology in the decoder, gUnpool performs the inverse operation of gPool. It uses the indices of the nodes selected during the corresponding pooling step to place node features back into their original positions in a larger, zero-initialized feature matrix. This symmetric skip-connection architecture ensures that spatial information is preserved, enabling precise node-level predictions for tasks like node classification.

Inspired by the classic U-Net for image segmentation, Graph U-Net introduces bridge connections between corresponding encoder and decoder layers. The feature maps from a gPool layer are concatenated or added to the feature maps of the symmetric gUnpool layer. This mechanism fuses high-resolution, local structural information from the encoder with the upsampled, global semantic information from the decoder, mitigating the loss of fine-grained details.

The node selection mechanism is driven by a trainable projection vector. The scalar projection score y = X p / ||p|| determines node importance. To make this discrete selection trainable via backpropagation, the gate operation ŷ = sigmoid(y) is applied, and the selected features are gated as X̃ = X ⊙ ŷ. This allows gradients to flow through the projection vector p, enabling the network to learn a task-specific node ranking function.

A known issue with top-k node pooling is that the resulting graph may become disconnected, losing structural information. Graph U-Net addresses this by using a graph powering technique. The adjacency matrix of the pooled graph is augmented to A' = A², which adds edges between nodes that share a common neighbor. This simple operation significantly improves connectivity in the coarsened graph without adding substantial computational overhead.

Graph U-Net is designed for whole-graph classification tasks. The encoder progressively coarsens the graph, and a final global pooling or readout layer aggregates the remaining node features into a fixed-size graph-level representation. This hierarchical feature extraction captures motifs at multiple scales—from individual atoms to functional groups—making it highly effective for molecular property prediction and social network analysis.

A foundational learnable graph pooling method that hierarchically clusters nodes into a smaller graph using a soft assignment matrix. DiffPool enables end-to-end training for whole-graph prediction tasks by making the coarsening process differentiable.

• Learns a dense assignment matrix mapping nodes to clusters
• Generates a new adjacency matrix for the pooled graph
• Often used as a baseline comparison for Graph U-Net's top-k pooling approach

The core pooling operation used in Graph U-Net that selects the top-k nodes based on a learnable projection score. Unlike DiffPool's dense clustering, gPool drops less important nodes entirely, creating a sparser, more interpretable coarsened graph.

• Projects node features onto a trainable vector to compute importance scores
• Retains only the k highest-scoring nodes and their connecting edges
• Enables the symmetric unpooling operation by restoring nodes to their original positions

An architecture that aggregates node representations from all intermediate layers to combine local and global neighborhood information. This prevents the over-smoothing problem where deep GNNs produce indistinguishable node embeddings.

• Concatenates or max-pools outputs from every layer
• Directly addresses the depth limitation that Graph U-Net's skip connections also mitigate
• Particularly useful for graphs with diverse neighborhood structures

A theoretically maximally powerful GNN under the Weisfeiler-Lehman test, designed to capture graph structure by learning injective aggregation functions. GIN layers can serve as the convolutional backbone within a Graph U-Net encoder.

• Uses a multi-layer perceptron after summing neighbor features
• Achieves discriminative power equal to the 1-WL test
• Provides theoretical guarantees that complement Graph U-Net's hierarchical pooling

A GNN variant that employs self-attention mechanisms to assign learnable importance weights to different neighboring nodes during message aggregation. GAT layers can replace standard graph convolutions in the Graph U-Net encoder for adaptive neighborhood weighting.

• Computes attention coefficients between node pairs
• Allows nodes to focus on the most relevant neighbors
• Multi-head attention stabilizes learning and captures different relationship types

A model-agnostic explainability tool that identifies the most relevant subgraph structure and node features contributing to a GNN's specific prediction. For Graph U-Net models, GNNExplainer can validate whether the pooling operation correctly identifies structurally important nodes.

• Generates compact subgraph explanations via mutual information maximization
• Highlights critical edges and node features for each prediction
• Provides interpretability for the hierarchical representations learned by Graph U-Net