Graph Neural Networks (GNNs) are a class of deep models that operates on data with arbitrary topology and order-invariant structure represented as graphs. We introduce an efficient memory layer for GNNs that can learn to jointly perform graph representation learning and graph pooling. We also introduce two new networks based on our memory layer: Memory-Based Graph Neural Network (MemGNN) and Graph Memory Network (GMN) that can learn hierarchical graph representations by coarsening the graph throughout the layers of memory. The experimental results demonstrate that the proposed models achieve state-of-the-art results in six out of seven graph classification and regression benchmarks. We also show that the learned representations could correspond to chemical features in the molecule data. Graph Neural Networks (GNNs) (Wu et al., 2019; Zhou et al., 2018; are a class of deep architectures that operate on data with arbitrary topology represented as graphs such as social networks (Kipf & Welling, 2016) , knowledge graphs (Schlichtkrull et al., 2018) , molecules (Duvenaud et al., 2015) , point clouds (Hassani & Haley, 2019) , and robots . Unlike regular-structured inputs with spatial locality such as grids (e.g., images and volumetric data) and sequences (e.g., speech and text), GNN inputs are variable-size graphs consisting of permutationinvariant nodes and interactions among them. GNNs such as Gated GNN (GGNN) (Li et al., 2015) , Message Passing Neural Network (MPNN) (Gilmer et al., 2017) , Graph Convolutional Network (GCN) (Kipf & Welling, 2016) , and Graph Attention Network (GAT) (Velikovi et al., 2018) learn node embeddings through an iterative process of transferring, transforming, and aggregating the node embeddings from topological neighbors. Each iteration expands the receptive field by one hop and after k iterations the nodes within k hops influence the node embeddings of one another. GNNs are shown to learn better representations compared to random walks (Grover & Leskovec, 2016; Perozzi et al., 2014) , matrix factorization (Belkin & Niyogi, 2002; Ou et al., 2016) , kernel methods (Shervashidze et al., 2011; Kriege et al., 2016) , and probabilistic graphical models (Dai et al., 2016) . These models, however, cannot learn hierarchical representation as they do not exploit the graph compositionality. Recent work such as Differentiable Pooling (DiffPool) (Ying et al., 2018) , TopKPool (Gao & Ji, 2019) , and Self-Attention Graph Pooling (SAGPool) (Lee et al., 2019) define parametric graph pooling layers that let models learn hierarchical graph representation by stacking interleaved layers of GNN and pooling layers. These layers cluster nodes in the latent space such that the clusters are meaningful with respect to the task. These clusters might be communities in a social network or potent functional groups within a chemical dataset. Nevertheless, these models are not efficient as they require an iterative process of message passing after each pooling layer. In this paper, we introduce a memory layer for joint graph representation learning and graph coarsening that consists of a multi-head array of memory keys and a convolution operator to aggregate the soft cluster assignments from different heads. The queries to a memory layer are node embeddings from the previous layer and the outputs are the node embeddings of the coarsened graph. The memory layer does not explicitly require connectivity information and unlike GNNs relies on the global information rather than local topology. These properties make them more efficient and improve their performance. We also introduce two networks based on the proposed layer: Memory-based Graph Neural Network (MemGNN) and Graph Memory Network (GMN). MemGNN consists of a GNN that learns the initial node embeddings, and a stack of memory layers that learns hierarchical graph representation up to the global graph embedding. GMN, on the other hand, learns the hierarchical representation purely based on memory layers and hence does not require message passing. We proposed an efficient memory layer and two deep models for hierarchical graph representation learning. We evaluated the proposed models on nine graph classification and regression tasks and achieved state-of-the-art results on eight of them. We also experimentally showed that the learned representations can capture the well-known chemical features of the molecules. Our study indicated that node attributes concatenated with corresponding topological embeddings in combination with one or more memory layers achieves notable results without using message passing. We also showed that for the topological embeddings, the binary adjacency matrix is sufficient and thus no further preprocessing step is required for extracting them. Finally, we showed that although connectivity information is not directly imposed on the model, the memory layer can process node embeddings and properly cluster and aggregate the learned embeddings. Limitations: In section 4.2, we discussed that on the COLLAB dataset, kernel methods or deep models augmented with deterministic clustering algorithm achieve better performance compared to our models. Analyzing samples in this dataset suggests that in graphs with dense communities, such as cliques, our model lacks the ability to properly detect these dense sub-graphs. Moreover, the results of the DD dataset reveals that our MemGNN model outperforms the GMN model which implies that we need message passing to perform better on this dataset. We speculate that this is because the DD dataset relies more on local information. The most important features to train an SVM on this dataset are surface features which have local behavior. This suggest that for data with strong local interactions, message passing is required to improve the performance. Future Directions: We are planning to introduce a model based on the MemGNN and GMN architectures that can perform node classification by attending to the node embeddings and centroids of the clusters from different layers of hierarchy that the node belongs to. We are also planning to investigate the representation learning capabilities of the proposed models in self-supervised setting. A APPENDIX
We introduce an efficient memory layer that can learn representation and coarsen input graphs simultaneously without relying on message passing.
{"src": "scitldr-AIC_train", "paper_id": "r1laNeBYPB"}