Unsupervised Inductive Whole-Graph Embedding by Preserving Graph Proximity

Recent years we have witnessed the great popularity of graph representation learning with success in not only node-level tasks such as node classification (Kipf & Welling, 2016a) and link prediction (Zhang & Chen, 2018) but also graph-level tasks such as graph classification (Ying et al., 2018) and graph similarity/distance computation (Bai et al., 2019). There has been a rich body of work (Belkin & Niyogi, 2003; Qiu et al., 2018) on node-level embeddings that turn each node in a graph into a vector preserving node-node proximity (similarity/distance). It is thus natural to raise the question: Can we embed an entire graph into a vector in an unsupervised way, and how? However, most existing methods for graph-level, i.e. whole-graph, embeddings assume a supervised model (Zhang & Chen, 2019), with only a few exceptions such as G KERNELS(Yanardag & Vishwanathan, 2015), which typically count subgraphs for a given graph and can be slow, and GRAPH2VEC(Narayanan et al., 2017), which is transductive. A key challenge facing designing an unsupervised graph-level embedding model is the lack of graphlevel signals in the training stage. Unlike node-level embedding which has a long history in utilizing the link structure of a graph to embed nodes, there lacks such natural proximity (similarity/distance) information between graphs. Supervised methods, therefore, typically resort to graph labels as guidance and use aggregation based methods, e.g. However, this assumption is problematic, as simple aggregation of node embeddings can only preserve limited graph-level properties, which is, however, often insufficient in measuring graphgraph proximity ("inter-graph" information). Inspired by the recent progress on graph proximity modeling (Ktena et al., 2017; Bai et al., 2019), we propose a novel framework, UG RAPHEMBthat employs multi-scale aggregations of node-level embeddings, guided by the graph-graph proximity defined by well-accepted and domain-agnostic graph proximity metrics such as Graph Edit Distance (GED) (Bunke, 1983), Maximum Common Subgraph (MCS) (Bunke & Shearer, 1998), etc. RAPHEMBis to learn high-quality graph-level representations in a completely unsupervised and inductive fashion: During training, it learns a function that maps a graph into a universal embedding space best preserving graph-graph proximity, so that after training, any new graph can be mapped to this embedding space by applying the learned function. Inspired by the recent success of pre-training methods in the text domain, such as ELMO (Peters et al., 2018), B RAPHEMBfirst computes the graph-graph proximity scores, (c) yielding a "hyper-level graph" where each node is a graph in the dataset, and each edge has a proximity score associated with it, representing its weight/strength. RAPHEMBthen trains a function that maps each graph into an embedding which preserves the proximity score.