Pilos: Scalable Large-Subgraph Matching by Online Spectral Filtering

Subgraph matching seeks all the occurrences of a query graph inside another graph. As it reduces to subgraph isomorphism, it is NP-hard. Current methods reduce the computation by filtering the candidates on which they run subgraph isomorphism. Nevertheless, when the query is large, the number of candidates grows rapidly, rendering current methods largely ineffective in pruning and incapable to answer even within one hour. A primary reason for this ineffectiveness is their inability to effectively consider the query graph structure in the computation.

In this paper, we propose PILOS, a novel matching algorithm that substantially improves the filtering phase of a typical matching algorithm and computes up to 60% fewer candidates for verification. PILOS uses (i) an offline light-weight index-based phase, which leverages the top graph Laplacian eigenvalues of query and data node neighborhoods to reduce candidates via neighborhood filtering and (ii) an online phase, which further prunes candidates stored in an auxiliary data structure; both phases apply the interlacing theorem on graph Laplacian spectra. Our thorough experimental study shows that, on average, PILOS resolves queries in 19% less time and leaves 23% fewer unresolved queries after a lapse of 10 minutes than the best previous work.