Exploratory Search on Graph Databases through Subgraph Query Feedback

The research on graph data has been rejuvenated with a wide range of recent real-world applications, ranging from biological and chemical databases (as of 2012, there are at least 1500 online data sources), social networks (Twitter), co-purchase networks (Amazon.com) to hbinformation networks (DBpedia). Such research results in a bloom of graph platforms from research labs (Trinity), startup companies (GraphX (Hadoop)), life science companies, and projects funded by the Hong Kong RGC.

As consistently reported in self assessments of database research, among others, usability has always been a major issue of database platforms. The usability issue is more pressing for graphs because graph schemas may be too loose to be useful for query formulation; the queries can be too complex to compose manually; or the user may simply fall victim to human error. To address this, we propose to provide useful feedback to guide users to retrieve and/or explore graph repositories.

The first part of this research formalizes subgraph query feedback into two novel and fundamental queries, namely what-if and why-not subgraph similarity queries. Consider a co- purchase network as an example. A user may have purchased a mobile phone and obtained a long recommendation list of co-purchased earlier versions of that particular phone, which tells nothing but hardware upgrades. However, users may prefer to know different product types (e.g., the most compatible laptops of the phone). Ideally, the graph platform automatically tunes its internal parameters of recommendations. This project proposes what-if scenarios for users to choose from to explore the network. Next, when laptops are not returned, users may issue a co- purchase pattern with a laptop of the same brand. The why-not query returns to users a minimal change of recommendation parameters and/or query graphs in order to retrieve the laptop. For instance, the why-not query may explain that the threshold on the co-purchase frequency was set too high. Users may modify their preference accordingly to explore the network.

Our pioneering effort [BTC+15,HBT+14,BCZ13,JBC+12,JBX+11,JBX+10] on a graphical user interface (GUI) of a graph platform has been a natural means of graph querying. In addition to publishing a series of scholarly works, the second part of this research is to integrate and optimize the query feedback into a working GUI as a case study. To our knowledge, the query feedback module has not been investigated. We shall adopt database methodologies to solve the research problems. Comprehensive experimental and usability investigations are planned.