  The phenomenal growth of graph data from a wide variety of real-world
applications has rendered graph querying to be a problem of paramount
importance. Traditional techniques use structural as well as node similarities
to find matches of a given query graph in a (large) target graph. However,
almost all existing techniques have tacitly ignored the presence of
relationships in graphs, which are usually encoded through interactions between
node and edge labels. In this paper, we propose RAQ -- Relationship-Aware Graph
Querying, to mitigate this gap. Given a query graph, RAQ identifies the $k$
best matching subgraphs of the target graph that encode similar relationships
as in the query graph. To assess the utility of RAQ as a graph querying
paradigm for knowledge discovery and exploration tasks, we perform a user
survey on the Internet Movie Database (IMDb), where an overwhelming 86% of the
170 surveyed users preferred the relationship-aware match over traditional
graph querying. The need to perform subgraph isomorphism renders RAQ NP-hard.
The querying is made practical through beam stack search. Extensive experiments
on multiple real-world graph datasets demonstrate RAQ to be effective,
efficient, and scalable.
