Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

8-2026

Abstract

Subgraph counting, which involves determining the frequency of a query graph within a data graph, has numerous applications such as query optimization, fraud detection, and evaluating the expressiveness of graph neural networks. Despite its importance, there has been no systematic study on the impact of adversarial graph perturbations on subgraph counts. In this work, we examine the kSub problem, which aims to identify k edge additions that maximize the count of a query graph. We prove that kSub is intractable due to its NP-hardness, even for constant approximation. To address this, we relax the problem into a top-k selection, termed topkSub. Depending on the structure of the relaxed query graph, we distinguish two possible processing scenarios (namely, the connected and the disconnected case), and design dedicated search space pruning strategies for each scenario. Additionally, we develop sampling techniques on the pruned search space to scale topkSub for handling large graphs. In the form of a case study, we demonstrate that topkSub effectively uncovers vulnerabilities in state-of-the-art GNN models for subgraph counting, providing a significant advantage over alternative graph perturbation methods. The efficiency analysis shows that our pruning techniques achieve substantial speedups for exact processing in both connected and disconnected cases, while our sampling methods reduce estimation errors by 1-2 orders of magnitude compared to state-of-the-art samplers.

Keywords

Graph perturbation; Subgraph counting

Discipline

Artificial Intelligence and Robotics | Databases and Information Systems

Advisors/Committee Chairs

NA

Degree Awarded

PhD in Computer Science

First Page

1638

Last Page

1649

Identifier

10.1145/3770854.3780256

Publisher

ACM

Additional URL

https://doi.org/10.1145/3770854.3780256

Download

Share

COinS