Interactive Visual Pattern Search on Graph Data via Graph Representation Learning
Huan Song, Zeng Dai, Panpan Xu, Liu Ren
External link (DOI)
View presentation:2021-10-28T18:15:00ZGMT-0600Change your timezone on the schedule page
2021-10-28T18:15:00Z
Fast forward
Direct link to video on YouTube: https://youtu.be/6dP9SR-ZSSc
Abstract
Graphs are a ubiquitous data structure to model processes and relations in a wide range of domains. Examples include social networks, knowledge graphs, control-flow graphs in programs, and semantic scene graphs in images. Identifying subgraph patterns (or motifs) in graphs is one important approach to understand their structural properties. We propose a visual analytics system, GraphQ to support human-in-the-loop, example-based, subgraph pattern search in a database containing many individual graphs. Our approach goes beyond a predefined set of motifs and allows users to interactively specify the patterns of interest. To support fast, interactive queries, we use graph neural networks (GNNs) to encode the topological and node attributes in a graph as fixed-length latent vector representations, and perform subgraph matching in the latent space. However, due to the complexity of the problem, it is still difficult to obtain accurate one-to-one node correspondence in the matching results, which is crucial for visualization and interpretation. We, therefore, propose a novel GNN for node-alignment called NeuroAlign, to facilitate easy validation and interpretation of the query results. GraphQ provides a visual query interface with a query editor and a multi-scale visualization of the results, as well as a user feedback mechanism for refining the results with additional constraints. We demonstrate GraphQ through two example usage scenarios in different application domains: analyzing reusable subroutines in program workflows and semantic scene graph search in images. Quantitative experiments show that NeuroAlign achieves 19%–29% improvement in node-alignment accuracy compared to baseline GNN and provides up to 100x speedup compared to combinatorial algorithms. Our qualitative study with domain experts confirms the effectiveness of GraphQ for both usage scenarios.