Graph Pattern Matching (GPM) aims to discover matches in a graph G that satisfy a query pattern C. It is increasingly used in various real-world applications such as social network analysis and cyberattack detection. However, since GPM relies on subgraph isomorphism, its computation becomes intractable for large graphs. Moreover, the potentially exponential number of matches makes exhaustive inspection infeasible. To address this, the diversified top-k GPM (dtkGPM) problem seeks to retrieve only the top-k most diversified matches for C in G. Existing solutions remain limited in terms of approximation guarantees, relevance expressiveness, and integration within commercial graph systems. This article investigates the dtkGPM problem in the context of a practical query language (Cypher) and a real graph system (Neo4j). We formalize the problem using an expressive range of relevance criteria and prove its NP-hardness. We then present three baseline algorithms: a fast heuristic with early termination, and two greedy-search methods offering a \(\frac{1}{2}\) -approximation ratio. While the heuristic is highly efficient, its quality can be suboptimal; conversely, the greedy approaches require computing all matches of C in G, which may be impractical. To overcome this limitation, we propose a local-search algorithm that preserves a \((1 - \frac{2}{k})\) approximation ratio. The key innovation lies in a query rewriting principle that avoids exhaustive match enumeration. Experimental results demonstrate that our local-search algorithm significantly outperforms existing approximations in both efficiency and scalability, while maintaining high solution quality. To our knowledge, this is the first approach to the dtkGPM problem that achieves a balanced trade-off between efficiency and approximation guarantee, with seamless integration into real-world graph applications.
