FLAG: Towards Graph Query Autocompletion for Large Graphs

Peipei Yi*, Jianping Li, Byron Choi*, Sourav S. Bhowmick, Jianliang Xu

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

5 Citations (Scopus)


Graph query autocompletion (GQAC) takes a user’s graph query as input and generates top-k query suggestions as output, to help alleviate the verbose and error-prone graph query formulation process in a visual interface. To compose a target query with GQAC, the user may iteratively adopt suggestions or manually add edges to augment the existing query. The current state-of-the-art of GQAC, however, focuses on a large collection of small- or medium-sized graphs only. The subgraph features exploited by existing GQAC are either too small or too scarce in large graphs. In this paper, we present Flexible graph query autocompletion for LArge Graphs, called FLAG. We are the first to propose wildcard labels in the context of GQAC, which summarizes query structures that have different labels. FLAG allows augmenting users’ queries with subgraph increments with wildcard labels to form suggestions. To support wildcard-enabled suggestions, a new suggestion ranking function is proposed. We propose an efficient ranking algorithm and extend an index to further optimize the online suggestion ranking. We have conducted a user study and a set of large-scale simulations to verify both the effectiveness and efficiency of FLAG. The results show that the query suggestions saved roughly 50% of mouse clicks and FLAG returns suggestions in few seconds.

Original languageEnglish
Pages (from-to)175–191
Number of pages17
JournalData Science and Engineering
Issue number2
Publication statusPublished - Jun 2022

Scopus Subject Areas

  • Computational Mechanics
  • Computer Science Applications

User-Defined Keywords

  • Database usability
  • Large graphs
  • Query autocompletion
  • Subgraph query


Dive into the research topics of 'FLAG: Towards Graph Query Autocompletion for Large Graphs'. Together they form a unique fingerprint.

Cite this