Research On Feature-based Large-scale Graph Similarity

The size of a graph generated in the fields of biology,chemistry,internet,and transportation has exploded violently with the development of science and technology.Analyzing and mining of a large-scale graph to obtain some valuable information is a hot topic,where graph comparison is one of the most important research branches.The accuracy and efficiency of graph comparison have a significant impact on the analyzing and understanding of time series graphs,World Wide Web,biological networks.For a graph with millions of nodes and billions of edges,the computational cost of the similarity measure will increase significantly.It is a very critical issue to reduce the computational cost while the comparison is performed between some large-scale graph.In our research,tow novel methods of graph comparison are presented to meet different requirements.First,a graph comparison method based on feature extract is suggested to insight the coarse-grained difference at the macro level.Second,another graph comparison method,based Network representation learning,is proposed to insight the fine-grained difference at the micro level.Experiments show that both methods proposed by us can effectively reduce the computational cost and quality of graph comparison.(1)In order to insight the similarity of large-scale graphs,a novel method based on topological features is proposed.The method first performs global structural similarity metrics using the global topological features of a given graph.Secondly,the vertex topological features of a given graph are extracted,and the vertex structure similarity metric is measured by the numerical characteristics of the eigenvalue distribution.Finally,the global similarity and vertex structure similarity are applied to obtain the similarity.The experimental results show that the proposed method can effectively measure the similarity of large-scale graphs in a short time,and sensitive to changes in a graph topology(2)In order to solve the problem of measurement with a small difference in topology,a method of similarity judgment based on graph embedding is proposed.The method firstly projects the graph topology information into the embedding space by GraRep algorithm and represents it as a vertex feature vector.Then,a feature matrix is built according to the vertex correspondence relationship.Finally,the calculation method of matrix similarity is applied to measure the similarity between the graphs.Experiments show that the method is more strict on the similarity measure of the graph topology,and the similarity measure can be efficiently performed in the case the vertices within the graph is known.