Research On Efficient Graph Summarization Algorithm Based On Tensor Decomposition

Graph summarization is a concise representation of a graph,which can effectively solve the problems of analysis,query and storage of large-scale graph data in practical applications.In order to compute the summarization of dynamic graphs,the researchers model the dynamic graph as tensor and use the tensor decomposition algorithm to mine the multidimensional information of dynamic graphs,and then use the information to compute the summary of the graph.However,many current tensor decomposition algorithms often ignore the binary characteristics of the data of the graph without permission.The calculated real value factor matrix is not interpretable for the original graph data.Therefore,this paper proposes to use the boolean tensor decomposition method to calculate the graph summary of dynamic unweighed graph.Boolean tensor decomposition is a tensor decomposition algorithm special for binary data,which is evolved from boolean matrix decomposition algorithm.Compared with the real value tensor decomposition method,the advantages of boolean tensor decomposition are the interpretability and sparsity of the decomposition results.However,current boolean tensor decomposition algorithms focus on the decomposition of static Boolean tensor,and the tensor data in practical application system is far from static,but increasing and accumulating constantly.The efficiency of static boolean tensor decomposition algorithm will drop a lot when it is faced with the increasing dynamic tensor.In order to solve the problem of incremental decomposition of binary tensor,this paper designs an incremental distributed boolean tensor factorization method called ICDBTF(Incremental Distributed Boolean Tensor Factorization).ICDBTF is mainly divided into three processes: sampling,decomposition and merging.Through the sampling method,the large-scale dynamic tensors are sampled to generate multiple sub tensors,and each sub tensor enters the decomposition process in parallel.Finally,the sub tensor binary factor matrix is merged with the whole tensor binary factor matrix in turn,and each merging process can be regarded as a factor matrix update operation.ICDBTF algorithm greatly improves the efficiency of the algorithm by reducing the size of decomposition tensor and parallel computation of multi tensor decomposition.Finally,the correctness of the algorithm is ensured by heuristic merging strategy.At the same time,this paper applies ICDBTF to the process of dynamic unweighted graph summarization,and designs a new graph summarization method BTen Clust S(Boolean Tensor Cluster Summarization).BTen Clust S algorithm uses boolean tensor decomposition algorithm to improve the interpretability of decomposition results,and improves the computational efficiency of algorithm process through incremental computing.The experiments show that ICDBTF can improve the efficiency of boolean tensor decomposition by 2.2 ～ 4.6 times without losing accuracy.Compared with baseline algorithm,BTen Clust S can get better graph summarization with lower compression cost.