Towards proximity pattern mining in large graphs

Mining graph patterns in large networks is critical to a vari-ety of applications such as malware detection and biological module discovery. However, frequent subgraphs are often ineffective to capture association existing in these applica-tions, due to the complexity of isomorphism testing and the inelastic pattern definition. In this paper, we introduce proximity pattern which is a significant departure from the traditional concept of fre-quent subgraphs. Defined as a set of labels that co-occur in neighborhoods, proximity pattern blurs the boundary be-tween itemset and structure. It relaxes the rigid structure constraint of frequent subgraphs, while introducing connec-tivity to frequent itemsets. Therefore, it can benefit from both: efficient mining in itemsets and structure proximity from graphs. We developed two models to define proximity patterns. The second one, called Normalized Probabilistic Association (NmPA), is able to transform a complex graph mining problem to a simplified probabilistic itemset min-ing problem, which can be solved efficiently by a modified FP-tree algorithm, called pFP. NmPA and pFP are evalu-ated on real-life social and intrusion networks. Empirical results show that it not only finds interesting patterns that are ignored by the existing approaches, but also achieves high performance for finding proximity patterns in large-scale graphs