240902_Thuy_Labseminar[ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations].pptx

ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations

1. ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations Van Thuy Hoang Network Science Lab Dept. of Artificial Intelligence The Catholic University of Korea E-mail: [email protected] 2024-09-02 AAAI ’21

2. Problem: Sparse supervision signals Current GNNs are inherently flat and lack the capability of aggregating node information in a hierarchical manner

3. Contributions ASAP, a sparse pooling operator capable of capturing local subgraph information hierarchically to learn global features with better edge connectivity in the pooled graph. Master2Token (M2T), a new self-attention framework which is better suited for global tasks like pooling. a new convolution operator LEConv, that can adaptively learn functions of local extremas in a graph substructure.

4. BACKGROUND: Graph Convolutional Networks (GCNs) Key Idea: Each node aggregates information from its neighborhood to get contextualized node embedding. Limitation: Most GNNs focus on homogeneous graph. Neural Transformation Aggregate neighbor’s information

5. Pooling function ASAP, which has all the desirable properties of hierarchical pooling without compromising on sparsity in graph operations

6. ASAP: Proposed Method (b) ASAP initially clusters 1-hop neighborhood considering all nodes as medoid (c) Clusters are scored using LEConv (d) A fraction of top scoring clusters are selected (e) Output of ASAP (f) Overview of hierarchical graph classification architecture.

7. Cluster Assignment the cluster assignment matrix where S_{i,j} represents the membership of node v_i ∈ V in cluster c_h(v_j ) By employing such local clustering, we can maintain sparsity of the cluster assignment matrix S similar to the original graph adjacency matrix A

8. Cluster Formation using Master2Token Given a cluster ch(vi), we learn the cluster assignment matrix S through a self-attention mechanism. In M2T framework, we first create a master query m_i In this work we experiment with max master function defined as: This master query mi attends to all the constituent nodes vj The cluster representation x^c_i for ch(vi) is computed as follows:

9. Cluster Selection using LEConv we sample clusters based on a cluster fitness score φi calculated for each cluster in the graph G^c: The pooled graph Gp is formed by selecting these top k clusters. The pruned cluster assignment matrix, and the node feature matrix :

10. Maintaining Graph Connectivity once the clusters have been sampled, we find the new adjacency matrix Ap for the pooled graph Gp using Aˆc and Sˆ

11. Experimental Setup Datasets: on 5 graph classification datasets.

12. Comparison of ASAP with previous global and hierarchical pooling ASAP consistently outperforms all the baselines on all the datasets. ASAP has a smaller variance in performance which suggests that the training of ASAP is more stable.

13. Effect of different attention framework Effect of different attention framework on pooling evaluated on validation data of FRANKENSTEIN and NCI1. Token2Token (T2T): selects both the target and candidates from the input set h. Source2Token (S2T): finds the importance of each candidate to a specific global task which cannot be represented by any single entity.

14. CONCLUSION ASAP, a sparse and differentiable pooling method for graph structured data. ASAP clusters local subgraphs hierarchically which helps it to effectively learn the rich information present in the graph structure. Master2Token self-attention framework which enables our model to better capture the membership of each node in a cluster. LEConv, a novel GNN formulation that scores the clusters based on its local and global importance https://openaccess.thecvf.com/content_ICCV_2019/papers/Xiong_A_Graph-Based_Framework_to_Bridge_Movies_and_Synopses_ICCV_2019_paper.pdf