Research On Similarity-based Graph Pattern Mining

With dramatically increasing ability of producing and collecting data, the size of data expanded rapidly and the explosive growth of data has flooded us with a tremendous amount of information. As one of the key steps of large-scale data processing and decision support, data mining has attracted a great deal of attention. Frequent pattern mining is a significant research topic in this field, which focuses on discovering characteristic information in data. Over the years, frequent itemset discovery algorithms have been used to find interesting patterns in various application areas. However, as data mining techniques are being increasingly applied to nontraditional domains, existing frequent pattern discovery approaches cannot be used. This is because most of these works process the single item, while there are many relations among objects in the real world. A more suitable way of modeling the objects in these areas is to represent them using graphs. Within that model, one way of formulating the frequent pattern discovery problem is that of discovering subgraphs that occur frequently in the graph. In this paper, we present an algorithm based on graph similarity, called SBPM, for finding the graph pattern in a single large directed graph. The idea is to start with a method that efficiently enumerates all size-k subgraphs. Then the algorithm computes the similarity between two graphs based on the similarity of their nodes and the structures around the nodes. We then use the similarity values for clustering these subgraphs to different categories. Finally, the graph patterns are given by the frequent clusters in which the subgraphs are similar with each other. This approach allows people to discovery the special size pattern and avoids the subgraph isomorphism problem by measuring the graph similarity. Experimental evaluation on real network data from various domains shows that SBPM algorithm achieves good performance.