Gragnostics: Fast, Interpretable Features for Comparing Graphs

摘要

Many analytical tasks, such as social network analysis, depend on comparing graphs. Existing methods are slow, or can be difficult to understand. To address these challenges, this paper proposes gragnostics, a set of 10 fast, layperson-understandable graph-level features. Each can be computed in linear time. To evaluate the ability of these features to discriminate different topologies and types of graphs, this paper compares a machine learning classifier using gragnostics to alternative classifiers, and the evaluation finds that the gragnostics classifier achieves higher performance. To evaluate gragnostics' utility in interactive visualization tools, this paper presents Chiron, a graph visualization tool that enables users to explore the subgraphs of a larger graph. Example usage scenarios of Chiron demonstrate that using gragnostics in a rank-by-feature framework can be effective for finding interesting subgraphs.