Abstract 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.

Graph query autocompletion (gQAC) generates a small list of ranked query suggestions during the graph query formulation process in a visual environment. The current state-of-the-art ofgQACprovides suggestions that are formed by adding subgraph increments to arbitrary places of an existing (partial) user query. However, according to the research results on human-computer interaction (HCI), humans can only interact with a small number of recent software artifacts in hand. Hence, many of such suggestions could be irrelevant. In this paper, we present theGFocusframework that exploits a novel notion ofuser focus of graph query formulation(or simplyfocus). Intuitively, the focus is the subgraph that a user is working on. We formulatelocality principlesinspired by the HCI research to automatically identify and maintain the focus. We propose novel monotone submodular ranking functions for generatingpopularandcomprehensivequery suggestions only at the focus. In particular, the query suggestions ofGFocushave high result counts (when they are used as queries) and maximally cover the possible suggestions at the focus. We propose efficient algorithms and an index for ranking the suggestions. Our results show thatGFocussaves 12-32 percent more mouse clicks and is 35× more efficient than the state-of-the-art competitor.

Composing queries is evidently a tedious task. This is particularly true of graph queries as they are typically complex and prone to errors. This is compounded by the fact that graph schemas can be missing or too loose to be helpful for query formulation. Graph Query AutoCompletion (gQAC) alleviates users from the potentially painstaking task of graph query formulation. This demonstration presents an interactive visual Focused GRaph quEry AutocompleTion framework, called FGreat. Its novelty relies on the user focus for gQAC, which is a subgraph of the current query that a user is focusing on. FGreat automatically computes a focus and completes the query at the focus, as opposed to an arbitrary query subgraph. This demonstration presents two complementary approaches to compute the user focus for different circumstances. It computes the focus from either (i) the sequence of edges that a user recently added to his/her query, or (ii) the position of the mouse cursor, if it is available. We demonstrate that the user focus enhances both the effectiveness and efficiency of graph query autocompletion.

This paper studies privacy-preserving reachability query services under the paradigm of data outsourcing. Specifically, graph data have been outsourced to a third-party service provider (SP), query clients submit their queries to the (SP), and the (SP) returns the query answers to the clients. However, the (SP) may not always be trustworthy. Hence, this paper investigates protecting the structural information of the graph data and the query answers from the (SP). Existing techniques are either insecure or not scalable. This paper proposes a privacy-preserving labeling, called ppTopo. To our knowledge, ppTopo is the first work that can produce reachability index on massive networks and is secure against known plaintext attacks (KPA). Specifically, we propose a scalable index construction algorithm by employing the idea of topological folding, recently proposed by Cheng et al. We propose a novel asymmetric scalar product encryption in modulo 3 (ASPE3). It allows us to encrypt the index labels and transforms the queries into scalar products of encrypted labels. We perform an experimental study of the proposed technique on the SNAP networks. Compared with the existing methods, our results show that our technique is capable of producing the encrypted indexes at least 5 times faster for massive networks and the client's decryption time is 2-3 times smaller for most graphs.

Composing queries is evidently a tedious task. This is particularly true of graph queries as they are typically complex and prone to errors, compounded by the fact that graph schemas can be missing or too loose to be helpful for query formulation. Despite the great success of query formulation aids, in particular, automatic query completion , graph query autocompletion has received much less research attention. In this demonstration, we present a novel interactive visual subgraph query autocompletion framework called A uto G which alleviates the potentially painstaking task of graph query formulation. Specifically, given a large collection of small or medium-sized graphs and a visual query fragment q formulated by a user, A uto G returns top- k query suggestions Q ′ as output at interactive time. Users may choose a query from Q ′ and iteratively apply A uto G to compose their queries. We demonstrate various features of A uto G and its superior ability to generate high quality suggestions to aid visual subgraph query formulation.

Subgraph queries have been a fundamental query for retrieving patterns from graph data. Due to the well known NP hardness of subgraph queries, those queries may sometimes take a long time to complete. Our recent investigation on real- world datasets revealed that the performance of queries on graphs generally varies greatly. In other words, query clients may occasionally encounter “unexpectedly” long execution from a subgraph query processor. This paper aims to demonstrate a tool that alleviates the problem by monitoring subgraph query progress. Specifically, we present a novel subgraph query progress indicator called PIGEON that exploits query-time information to report to users accurate estimated query progress. In the demonstration, users may interact with PIGEON to gain insights on the query evaluation, which include the following: Users are enabled to (i) monitor query progress; (ii) analyze the causes of long query times; and (iii) abort queries that run abnormally long, which may sometimes contain human errors.