Research On K-Automorphic Framework In Graph Simulation

Subgraph pattern matching is an essential operation of graph data management and calculation.It mainly includes subgraph isomorphism and graph simulation.Subgraph iso-morphism requires that the subgraph and the pattern graph have exactly the same structure and label,so the computation complexity of subgraph isomorphism is very high.Graph simulation is a new subgraph pattern matching model which can lower the computation cost of subgraph isomorphism and its extensions have been proposed,including dual simula-tion,strong simulation,strict simulation and tight simulation,to satisfy different matching queries.With the development of the cloud technology and the decreasing of large-scale graph data,more and more users take use of cloud platform to storage graph data.However,although the current cloud platform support data storage and basic data management,the security of the cloud platform can not be guaranteed.Therefore,storing important graph data in cloud will face the risk of privacy leakage.In this paper,we study the privacy leakage problem during the subgraph pattern match-ing process in cloud.We propose a privacy-preserving framework based on k-automorphism which can well preserved both label privacy and structure privacy in graph data.In order to protect label privacy of both data graph and pattern graph,we use the label generalization method to anonymize the vertex labels of data graph and pattern graph.We also take use of the k-automorphic model to protect the structure privacy of graph data.To improve the time efficiency of the matching process,we optimize the basic framework and propose an optimized privacy-preserving framework.The framework designs a cost-based label gener-alization method and only uploads the outsourced graph to cloud.The efficiency of subgraph matching process has been greatly improved through the two optimization methods.Compared with the traditional privacy-preserving methods,the two proposed frame-works in this paper adapt to multiple subgraph pattern matching models.We evaluate the proposed frameworks on several real-world datasets and compare them on multiple sub-graph pattern matching models.Experimental results show that our frameworks can adapt to multiple subgraph pattern matching models and effectively protect the data privacy.