Abstract: Frequent pattern mining(FPM) is a classical problem in graph theory,more attention has been paid on FPM on single large graphs,which is defined as discovering all the pattern graphs Q with occurrence frequencies above a user defined threshold,in a single large graph G.In recent years,people have witnessed wide applications of FPM,such as social network analysis and fraud detection.However,emerging applications keep calling for more expressive pattern graphs along with their mining techniques to capture more complex structures in a large graph.In light of this,we incorporate counting quantifiers in pattern graphs and introduce quantified pattern graphs(QGPs) which are able to express richer semantics.We then develop a distributive algorithm to mine QGPs in parallel.Furthermore,we introduce quantified graph pattern association rules(QGPARs) for linking prediction on large graphs.We conduct experimental studies to validate the computational efficiency of the QGPs mining algorithm by using real-world and synthetic graph data.By comparing with prior link prediction methods,we find that prediction with QGPARs achieves even higher accuracy.Finally,by comparing with the link prediction results of traditional graph pattern association rules,we verify that there is a significant difference between QGPARs and GPARs in terms of link prediction results,and further verify the effectiveness of QGPARs in link prediction.

Key words: Quantified pattern graph, Frequent pattern mining, Distribute mining, Quantified graph pattern association rules, Link prediction