ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations

By Ekagra Ranjan, Soumya Sanyal, Partha P. Talukdar. AAAI Conference on Artificial Intelligence, 2019

414 citations recorded by the source corpus.

Graph Neural Networks (GNN) have been shown to work effectively for modeling graph structured data to solve tasks such as node classification, link prediction and graph classification. There has been some recent progress in defining the notion of pooling in graphs whereby the model tries to generate a graph level representation by downsampling and summarizing the information present in the nodes. Existing pooling methods either fail to effectively capture the graph substructure or do not easily scale to large graphs. In this work, we propose ASAP (Adaptive Structure Aware Pooling), a sparse and differentiable pooling method that addresses the limitations of previous graph pooling architectures. ASAP utilizes a novel self-attention network along with a modified GNN formulation to capture the importance of each node in a given graph. It also learns a sparse soft cluster assignment for nodes at each layer to effectively pool the subgraphs to form the pooled graph. Through extensive experiments on multiple datasets and theoretical analysis, we motivate our choice of the components used in ASAP. Our experimental results show that combining existing GNN architectures with ASAP leads to state-of-the-art results on multiple graph classification benchmarks. ASAP has an average improvement of 4%, compared to current sparse hierarchical state-of-the-art method. We make the source code of ASAP available to encourage reproducible research 1.

Subfields: Artificial Intelligence, Cognitive Neuroscience, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/442db0ef2d0ff9d45aeed77010315396c34960aa

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Xiangnan He
2. Xiang Wang
3. Tat-seng Chua
4. Yong Li
5. Chen Gao
6. Depeng Jin
7. Yu Zheng
8. Jianxin Chang

In Cognitive Neuroscience

1. Xiangnan He

In Statistical and Nonlinear Physics

1. Tat-seng Chua
2. Lan Wei
3. Huan Zhao
4. Yang Song
5. Quanming Yao
6. Yong Li
7. Zhiqiang He
8. Chen Gao

Citations in the corpus

• Sequential Recommendation with Graph Neural Networks (2021, methodology): “To obtain the pooled graph, a cluster assignment matrix is necessary [22, 37].”
• Discovering Invariant Rationales for Graph Neural Networks (2022, methodology): “We thoroughly compare DIR with Empirical Risk Minimization (ERM) and two classes of baselines: • Interpretable Baselines: Graph Attention (Veliˇckovi´c et al., 2018) and graph pooling operations including ASAP (Ranjan et al., 2020), Top-k Pool (Gao & Ji, 2019) and SAG Pool (Lee et al., 2019).”
• Pooling Architecture Search for Graph Classification (2021, methodology): “For these hierarchical pooling methods, SAGPool [22], Graph U-Net [10] and ASAP [32] sample a set of nodes based on diverse node score functions and form corresponding coarse graphs; DiffPool [47] and STRUCTPOOL [50] focus on grouping nodes into clusters with different assignment functions, re-gener”