# VerSaChI: Finding Statistically Significant Subgraph Matches using Chebyshev's Inequality

Source: [VerSaChI: Finding Statistically Significant Subgraph Matches using Chebyshev's Inequality](<https://www.sota2.com/research/paper/68fa6a8e1e209131cea28c9f>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T23:27:27.413Z

Authors: Shubhangi Agarwal, Sourav Dutta, Arnab Bhattacharya

Published: 2021-08-18T06:53:39.000Z

## Abstract

Approximate subgraph matching, which is an important primitive for many applications like question answering, community detection, and motif discovery, often involves large labeled graphs such as knowledge graphs, social networks, and protein sequences. Effective methods for extracting matching subgraphs, in terms of label and structural similarities to a query, should depict accuracy, computational efficiency, and robustness to noise. In this paper, we propose VerSaChI for finding the top-k most similar subgraphs based on 2-hop label and structural overlap similarity with the query. The similarity is characterized using Chebyshev's inequality to compute the chi-square statistical significance for measuring the degree of matching of the subgraphs. Experiments on real-life graph datasets showcase significant improvements in terms of accuracy compared to state-of-the-art methods, as well as robustness to noise.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2108.07996>)

[PDF](<https://arxiv.org/pdf/2108.07996.pdf>)
