Mining Frequent Geo-Subgraphs in a Knowledge Graph

Frequent subgraph mining aims to find all subgraphs that occur frequently in a graph database or in a single large graph. It finds applications in social networks, citation networks, protein interaction networks, etc. This paper studies frequent subgraph mining in a knowledge graph, where some vertices are associated with geo-coordinates, called geo-vertices. We introduce geo-constraints and propose the problem of frequent geo-subgraph (FGS) mining to find each subgraph in a knowledge graph that (i) contains at least two geo-vertices, (ii) has no pairs of geo-vertices with a distance that exceeds \(\tau \) , and (iii) has support at least \(\delta \) . Such frequent geo-subgraphs can be used to analyze the relationships among geo-entities in spatial regions, enabling downstream applications such as classification, clustering, and recommendation of geo-entities. To solve the FGS problem in a large knowledge graph efficiently, we propose algorithm \(\textsf{FreGeoSubgraphAlg}\) and three optimizations. Extensive evaluations on real datasets demonstrate that the proposed algorithms can solve the FGS problem efficiently on large graphs and outperform the state-of-the-art algorithm by several orders of magnitude.