Hierarchical Representation Learning in Graph Neural Networks With Node Decimation Pooling.

Area of Science:

• Graph Neural Networks (GNNs)
• Machine Learning
• Graph Theory

Background:

• Pooling operators are crucial for GNNs to learn hierarchical representations by summarizing local graph structures.
• Existing pooling methods face challenges in preserving graph topology while achieving efficiency.

Purpose of the Study:

• To introduce Node Decimation Pooling (NDP), a novel pooling operator for GNNs.
• To develop a method that generates coarser graphs with preserved topology for improved GNN training.
• To enhance the efficiency and performance of graph classification tasks.

Main Methods:

• NDP employs a three-step process: node decimation using a MAXCUT approximation, graph coarsening via Kron reduction, and adjacency matrix sparsification.
• The GNN learns node representations on a pyramid of offline-computed coarsened graphs.
• A sparsification procedure prunes the dense graph to reduce computational cost without significant structural alteration.

Main Results:

• NDP effectively generates coarser graphs while preserving overall graph topology.
• The proposed sparsification procedure removes edges without substantially altering the graph structure.
• Experimental results demonstrate NDP's superior efficiency compared to state-of-the-art pooling operators.

Conclusions:

• NDP offers a computationally efficient and effective pooling strategy for GNNs.
• The method achieves competitive performance across various graph classification tasks.
• NDP facilitates the learning of hierarchical representations in deep GNNs by providing a topology-preserving coarsening mechanism.