Source-linked AI summary
Graph U-Nets
Hongyang Gao, Shuiwang Ji
TL;DR
Graph representation learning lacks natural pooling and up-sampling operations for building encoder-decoder architectures analogous to image U-Nets. The paper proposes gPool and gUnpool, which select graph nodes and restore graph structure, and develops graph U-Nets for node and graph classification. Experiments report consistently better performance than previous models across these tasks.
Problem
Graph data lack natural pooling and up-sampling operations, limiting encoder-decoder architectures despite the correspondence between node classification and image pixel-wise prediction.
Method
The paper introduces gPool for trainable projection-based node selection, gUnpool for restoring the original graph structure, and graph U-Nets that combine them with graph convolution.
Results
Experiments on node and graph classification report consistently better performance than previous models, including improvements over GCN of 2.9%, 2.9%, and 0.6% on Cora, Citeseer, and Pubmed.
Takeaways & Limitations
Graph U-Nets provide an encoder-decoder architecture for graph representation learning using graph-specific pooling and unpooling operations.
Abstract
from arXiv · showhide
We consider the problem of representation learning for graph data. Convolutional neural networks can naturally operate on images, but have significant challenges in dealing with graph data. Given images are special cases of graphs with nodes lie on 2D lattices, graph embedding tasks have a natural correspondence with image pixel-wise prediction tasks such as segmentation. While encoder-decoder architectures like U-Nets have been successfully applied on many image pixel-wise prediction tasks, similar methods are lacking for graph data. This is due to the fact that pooling and up-sampling operations are not natural on graph data. To address these challenges, we propose novel graph pooling (gPool) and unpooling (gUnpool) operations in this work. The gPool layer adaptively selects some nodes to form a smaller graph based on their scalar projection values on a trainable projection vector. We further propose the gUnpool layer as the inverse operation of the gPool layer. The gUnpool layer restores the graph into its original structure using the position information of nodes selected in the corresponding gPool layer. Based on our proposed gPool and gUnpool layers, we develop an encoder-decoder model on graph, known as the graph U-Nets. Our experimental results on node classification and graph classification tasks demonstrate that our methods achieve consistently better performance than previous models.
1. Introduction
Graph representation learning seeks CNN-like methods for graph data, where node-level prediction parallels image segmentation but graph pooling and up-sampling are not natural. The paper introduces gPool and gUnpool to build graph U-Nets for encoding and decoding graph representations.
- Graphs model real-world data such as social and biological networks, motivating extensions of convolutional neural networks to graph representation learning.
- Images are graphs whose nodes lie on regular 2D lattices, creating a correspondence between node classification and pixel-wise prediction tasks such as segmentation.
- Graph data lack the grid structure that makes U-Net-style pooling and up-sampling natural for image pixel-wise prediction.
- gPool selects nodes using scalar projection values on a trainable projection vector to form a smaller graph.
- gUnpool uses the locations of nodes selected by gPool to restore the graph to its original structure, enabling graph U-Net encoding and decoding.
2. Related Work
Related work extends graph convolution and pooling from methods developed for graph representation learning and image-like data. Existing graph pooling approaches use fixed indexing, deterministic clustering, or assignment matrices to coarsen graphs.
- Graph neural network research includes graph convolutional methods for learning node representations and performing node classification.
- GCNs aggregate and transform node features using normalized adjacency matrices, self-loops, and trainable weight matrices rather than learned filters.
- Graph pooling methods have used binary tree indexing, deterministic clustering, or assignment matrices to determine coarsened graph structures.
3. Graph U-Nets
Graph U-Nets introduce graph-specific pooling and unpooling operations to support U-Net-like encoder-decoder architectures. The model adaptively selects nodes, restores their original positions, and combines graph convolutions with skip connections for graph representation learning.
- 3.1. Graph Pooling Layer: Graph pooling operations designed for grid-like data do not transfer directly because graph nodes lack locality, and k-max selection can disrupt connectivity.Global pooling collapses all nodes into one, while partition-based pooling assumes a structure unavailable on general graphs.
- 3.1. Graph Pooling Layer: gPool adaptively selects a smaller graph by ranking node projections onto a trainable vector and extracting the selected nodes and edges.The projection vector is trained through a sigmoid gate that controls information flow from selected nodes.
- 3.2. Graph Unpooling Layer: gUnpool restores the original graph resolution by recording selected-node positions and placing pooled features back into an initially empty feature matrix.Selected rows receive the pooled features, while unselected rows remain zero.
- 3.3. Graph U-Nets Architecture: Graph U-Nets stack gPool-GCN encoder blocks with gUnpool-GCN decoder blocks and use skip connections to transmit lower-level spatial information.An initial embedding layer reduces high-dimensional node features, and a final GCN produces predictions.
- 3.4. Graph Connectivity Augmentation via Graph Power: Pooling can isolate nodes after edge removal, so graph U-Nets augment connectivity with the second graph power before sampling.The second graph power links nodes within two hops, matching the preceding GCN's first-order aggregation.
4. Experimental Study
The study evaluates graph U-Nets across transductive node classification and inductive graph classification, alongside ablations of pooling, unpooling, connectivity augmentation, depth, and parameter cost.
- Datasets and settings: Experiments cover transductive node classification on Cora, Citeseer, and Pubmed, plus inductive graph classification on D&D, PROTEINS, and COLLAB.The transductive setting uses unlabeled nodes from the same graph during training, whereas inductive testing graphs are unavailable during training.
- Performance study: 2.9%, 2.9%, and 0.6% are the reported improvements of g-U-Nets over GCN on Cora, Citeseer, and Pubmed node classification, respectively.The compared g-U-Nets use GCN, gPool, and gUnpool layers without more advanced graph convolution layers such as GAT.
- Performance study: 1.79% and 1.43% are the margins by which gPool outperforms DiffPool on D&D and PROTEINS graph classification, respectively.On all three datasets, the model outperforms baseline models including DiffPool; DiffPool-DET performs significantly higher than other methods on COLLAB.
- Ablation study: Removing gPool and gUnpool produces a GCN-only network with skip connections, enabling an ablation of the proposed encoder-decoder components.The study attributes the improvement to higher-level feature encoding and better generalization and performance.
- Network depth study: Deeper networks improve performance until over-fitting prevents further gains beyond a certain depth.The authors relate this behavior to common U-Net depths of 3 or 4 and the receptive-field enlargement and high-level encoding of gPool and gUnpool.
- Parameter study: 0.12% additional parameters from gPool layers correspond to a 2.3% performance improvement on Cora.The comparison is between g-U-Nets with and without gPool or gUnpool layers.
5. Conclusion
The paper introduces gPool and gUnpool layers for graph U-Nets, enabling encoder-decoder network embedding with adaptive node selection and graph-structure restoration.
- gPool adaptively selects important nodes using scalar projections onto a trainable projection vector.
- gUnpool uses original-node positions to invert gPool and restore the original graph structure.
- Graph U-Nets use these layers in a U-Net-like encoder-decoder architecture for network embedding.
- Experiments report improved performance over other GNNs on transductive learning tasks.