Inductive and unsupervised graph learning is a critical technique for predictive or information retrieval tasks where label information is difficult to obtain. It is also challenging to make graph learning inductive and unsupervised at the same time, as learning processes guided by reconstruction error based loss functions inevitably demand graph similarity evaluation that is usually computationally intractable. In this paper, we propose a general framework SEED (Sampling, Encoding, and Embedding Distributions) for inductive and unsupervised representation learning on graph structured objects. Instead of directly dealing with the computational challenges raised by graph similarity evaluation, given an input graph, the SEED framework samples a number of subgraphs whose reconstruction errors could be efficiently evaluated, encodes the subgraph samples into a collection of subgraph vectors, and employs the embedding of the subgraph vector distribution as the output vector representation for the input graph. By theoretical analysis, we demonstrate the close connection between SEED and graph isomorphism. Using public benchmark datasets, our empirical study suggests the proposed SEED framework is able to achieve up to 10% improvement, compared with competitive baseline methods. Representation learning has been the core problem of machine learning tasks on graphs. Given a graph structured object, the goal is to represent the input graph as a dense low-dimensional vector so that we are able to feed this vector into off-the-shelf machine learning or data management techniques for a wide spectrum of downstream tasks, such as classification (Niepert et al., 2016) , anomaly detection (Akoglu et al., 2015) , information retrieval (Li et al., 2019) , and many others (Santoro et al., 2017b; Nickel et al., 2015) . In this paper, our work focuses on learning graph representations in an inductive and unsupervised manner. As inductive methods provide high efficiency and generalization for making inference over unseen data, they are desired in critical applications. For example, we could train a model that encodes graphs generated from computer program execution traces into vectors so that we can perform malware detection in a vector space. During real-time inference, efficient encoding and the capability of processing unseen programs are expected for practical usage. Meanwhile, for real-life applications where labels are expensive or difficult to obtain, such as anomaly detection (Zong et al., 2018) and information retrieval (Yan et al., 2005) , unsupervised methods could provide effective feature representations shared among different tasks. Inductive and unsupervised graph learning is challenging, even compared with its transductive or supervised counterparts. First, when inductive capability is required, it is inevitable to deal with the problem of node alignment such that we can discover common patterns across graphs. Second, in the case of unsupervised learning, we have limited options to design objectives that guide learning processes. To evaluate the quality of learned latent representations, reconstruction errors are commonly adopted. When node alignment meets reconstruction error, we have to answer a basic question: Given two graphs G 1 and G 2 , are they identical or isomorphic (Chartrand, 1977) ? To this end, it could be computationally intractable to compute reconstruction errors (e.g., using graph edit distance (Zeng et al., 2009) as the metric) in order to capture detailed structural information. Given an input graph, its vector representation can be obtained by going through the components. Previous deep graph learning techniques mainly focus on transductive (Perozzi et al., 2014) or supervised settings (Li et al., 2019) . A few recent studies focus on autoencoding specific structures, such as directed acyclic graphs (Zhang et al., 2019) , trees or graphs that can be decomposed into trees (Jin et al., 2018) , and so on. From the perspective of graph generation, You et al. (2018) propose to generate graphs of similar graph statistics (e.g., degree distribution), and Bojchevski et al. (2018) provide a GAN based method to generate graphs of similar random walks. In this paper, we propose a general framework SEED (Sampling, Encoding, and Embedding Distributions) for inductive and unsupervised representation learning on graph structured objects. As shown in Figure 1 , SEED consists of three major components: subgraph sampling, subgraph encoding, and embedding subgraph distributions. SEED takes arbitrary graphs as input, where nodes and edges could have rich features, or have no features at all. By sequentially going through the three components, SEED outputs a vector representation for an input graph. One can further feed such vector representations to off-the-shelf machine learning or data management tools for downstream learning or retrieval tasks. Instead of directly addressing the computational challenge raised by evaluation of graph reconstruction errors, SEED decomposes the reconstruction problem into the following two sub-problems. Q1: How to efficiently autoencode and compare structural data in an unsupervised fashion? SEED focuses on a class of subgraphs whose encoding, decoding, and reconstruction errors can be evaluated in polynomial time. In particular, we propose random walks with earliest visiting time (WEAVE) serving as the subgraph class, and utilize deep architectures to efficiently autoencode WEAVEs. Note that reconstruction errors with respect to WEAVEs are evaluated in linear time. Q2: How to measure the difference of two graphs in a tractable way? As one subgraph only covers partial information of an input graph, SEED samples a number of subgraphs to enhance information coverage. With each subgraph encoded as a vector, an input graph is represented by a collection of vectors. If two graphs are similar, their subgraph distribution will also be similar. Based on this intuition, we evaluate graph similarity by computing distribution distance between two collections of vectors. By embedding distribution of subgraph representations, SEED outputs a vector representation for an input graph, where distance between two graphs' vector representations reflects the distance between their subgraph distributions. Unlike existing message-passing based graph learning techniques whose expressive power is upper bounded by Weisfeiler-Lehman graph kernels (Xu et al., 2019; Shervashidze et al., 2011) , we show the direct relationship between SEED and graph isomorphism in Section 3.5. We empirically evaluate the effectiveness of the SEED framework via classification and clustering tasks on public benchmark datasets. We observe that graph representations generated by SEED are able to effectively capture structural information, and maintain stable performance even when the node attributes are not available. Compared with competitive baseline methods, the proposed SEED framework could achieve up to 10% improvement in prediction accuracy. In addition, SEED achieves high-quality representations when a reasonable number of small subgraph are sampled. By adjusting sample size, we are able to make trade-off between effectiveness and efficiency. In this paper, we propose a novel framework SEED (Sampling, Encoding, and Embedding distribution) framework for unsupervised and inductive graph learning. Instead of directly dealing with the computational challenges raised by graph similarity evaluation, given an input graph, the SEED framework samples a number of subgraphs whose reconstruction errors could be efficiently evaluated, encodes the subgraph samples into a collection of subgraph vectors, and employs the embedding of the subgraph vector distribution as the output vector representation for the input graph. By theoretical analysis, we demonstrate the close connection between SEED and graph isomorphism. Our experimental results suggest the SEED framework is effective, and achieves state-of-the-art predictive performance on public benchmark datasets. Proof. We will use induction on |E(G)| to complete the proof. Basic case: Let |E(G)| = 1, the only possible graph is a line graph of length 1. For such a graph, the walk from one node to another can cover the only edge on the graph, which has length 1 ≥ 2 · 1 − 1. Induction: Suppose that for all the connected graphs on less than m edges (i.e., |E(G)| ≤ m − 1), there exist a walk of length k which can visit all the edges if k ≥ 2|E(G)| − 1. Then we will show for any connected graph with m edges, there also exists a walk which can cover all the edges on the graph with length k ≥ 2|E(G)| − 1. Let G = (V (G), E(G)) be a connected graph with |E(G)| = m. Firstly, we assume G is not a tree, which means there exist a cycle on G. By removing an edge e = (v i , v j ) from the cycle, we can get a graph G on m − 1 edges which is still connected. This is because any edge on a cycle is not bridge. Then according to the induction hypothesis, there exists a walk w = v 1 v 2 . . . v i . . . v j . . . v t of length k ≥ 2(m − 1) + 1 which can visit all the edges on G (The walk does not necessarily start from node 1, v 1 just represents the first node appears in this walk). Next, we will go back to our graph G, as G is a subgraph of G, w is also a walk on G. By replacing the first appeared node v i on walk w with a walk v i v j v i , we can obtain a new walk As w can cover all the edges on G and the edge e with length k = k + 2 ≥ 2(m − 1) − 1 + 2 = 2m − 1, which means it can cover all the edges on G with length k ≥ 2|E(G)| − 1. Next, consider graph G which is a tree. In this case, we can remove a leaf v j and its incident edge e = (v i , v j ) from G, then we can also obtain a connected graph G with |E(G )| = m − 1. Similarly, according to the induction hypothesis, we can find a walk w = v 1 v 2 . . . v i . . . v t on G which can visit all the m − 1 edges of G of length k , where k ≥ 2(m − 1) − 1. As G is a subgraph of G, any walk on G is also a walk on G including walk w . Then we can also extend walk w on G by replacing the first appeared v i with a walk v i v j v i , which produce a new walk w can visit all the edges of G as well as the edge e with length k = k + 2 ≥ 2(m − 1) − 1 + 2 = 2m − 1. In other words, w can visit all the edges on G with length k ≥ 2|E(G)| − 1. Now, we have verified our assumption works for all the connected graphs with m edges, hence we complete our proof. (To give an intuition for our proof of lemma 1, we provide an example of 5 edges in Figure 5 Figure 5 (b1) shows an example graph G which is a tree on 5 edges. By removing the leaf v 4 and its incident edge (v 4 , v 3 ), we can get a tree G with 4 edges (Figure 5 (b2) ). G has a walk w = v 1 v 2 v 3 v 5 which covers all the edges of G , as w is also a walk on G, by replacing v 3 with v 3 v 4 v 3 in w we can get a walk w = v 1 v 2 v 3 v 4 v 3 v 5 which can cover all the edges of G.
This paper proposed a novel framework for graph similarity learning in inductive and unsupervised scenario.
{"src": "scitldr-AIC_train", "paper_id": "rkem91rtDB"}