# CEGA: A Cost-Effective Approach for Graph-Based Model Extraction and Acquisition

arXiv: https://arxiv.org/abs/2506.17709 · HTML: https://mlsanity.com/paper/2506.17709/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 74 references that are in the map.
- First posted on arXiv 21 Jun 2025.

## Builds on (most cited first, 30 of 36)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Stealing Machine Learning Models via Prediction APIs](https://mlsanity.com/paper/1609.02943/) (2016)
- [GNNGuard: Defending Graph Neural Networks against Adversarial Attacks](https://mlsanity.com/paper/2006.08149/) (2020)
- [The Malicious Use of Artificial Intelligence: Forecasting, Prevention, and Mitigation](https://mlsanity.com/paper/1802.07228/) (2018)
- [PRADA: Protecting against DNN Model Stealing Attacks](https://mlsanity.com/paper/1805.02628/) (2018)
- [I Know What You Trained Last Summer: A Survey on Stealing Machine Learning Models and Defences](https://mlsanity.com/paper/2206.08451/) (2022)
- [Graph-Based Deep Learning for Medical Diagnosis and Analysis: Past, Present and Future](https://mlsanity.com/paper/2105.13137/) (2021)
- [Does GNN Pretraining Help Molecular Representation?](https://mlsanity.com/paper/2207.06010/) (2022)
- [Active Learning for Graph Embedding](https://mlsanity.com/paper/1705.05085/) (2017)
- [Model Stealing Attacks Against Inductive Graph Neural Networks](https://mlsanity.com/paper/2112.08331/) (2021)
- [Model Extraction Attacks on Graph Neural Networks: Taxonomy and Realization](https://mlsanity.com/paper/2010.12751/) (2020)
- [Are Defenses for Graph Neural Networks Robust?](https://mlsanity.com/paper/2301.13694/) (2023)
- [T2-GNN: Graph Neural Networks for Graphs with Incomplete Features and Structure via Teacher-Student Distillation](https://mlsanity.com/paper/2212.12738/) (2022)
- [Grain: Improving Data Efficiency of Graph Neural Networks via Diversified Influence Maximization](https://mlsanity.com/paper/2108.00219/) (2021)
- [Adversarial Model Extraction on Graph Neural Networks](https://mlsanity.com/paper/1912.07721/) (2019)
- [IDEA: A Flexible Framework of Certified Unlearning for Graph Neural Networks](https://mlsanity.com/paper/2407.19398/) (2024)
- [Graph Neural Network with Curriculum Learning for Imbalanced Node Classification](https://mlsanity.com/paper/2202.02529/) (2022)
- [Interpreting Unfairness in Graph Neural Networks via Training Node Attribution](https://mlsanity.com/paper/2211.14383/) (2022)
- [Multimodal Learning on Graphs for Disease Relation Extraction](https://mlsanity.com/paper/2203.08893/) (2022)
- [Molecular Property Prediction Based on Graph Structure Learning](https://mlsanity.com/paper/2312.16855/) (2023)
- [A Simple and Yet Fairly Effective Defense for Graph Neural Networks](https://mlsanity.com/paper/2402.13987/) (2024)
- [Advanced Financial Fraud Detection Using GNN-CL Model](https://mlsanity.com/paper/2407.06529/) (2024)
- [Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks](https://mlsanity.com/paper/2404.17947/) (2024)
- [GraphGuard: Detecting and Counteracting Training Data Misuse in Graph Neural Networks](https://mlsanity.com/paper/2312.07861/) (2023)
- [ATOM: A Framework of Detecting Query-Based Model Extraction Attacks for Graph Neural Networks](https://mlsanity.com/paper/2503.16693/) (2025)
- [MeaeQ: Mount Model Extraction Attacks with Efficient Queries](https://mlsanity.com/paper/2310.14047/) (2023)
- [Cluster-guided Contrastive Class-imbalanced Graph Classification](https://mlsanity.com/paper/2412.12984/) (2024)

## Built on by (most cited first, 10 of 10)

- [A Survey on Model Extraction Attacks and Defenses for Large Language Models](https://mlsanity.com/paper/2506.22521/) (2025)
- [CREDIT: Certified Ownership Verification of Deep Neural Networks Against Model Extraction Attacks](https://mlsanity.com/paper/2602.20419/) (2026)
- [GraphIP-Bench: How Hard Is It to Steal a Graph Neural Network, and Can We Stop It?](https://mlsanity.com/paper/2605.12827/) (2026)
- [Intellectual Property in Graph-Based Machine Learning as a Service: Attacks and Defenses](https://mlsanity.com/paper/2508.19641/) (2025)
- [CITED: A Decision Boundary-Aware Signature for GNNs Towards Model Extraction Defense](https://mlsanity.com/paper/2602.20418/) (2026)
- [DESIGN: Encrypted GNN Inference via Server-Side Input Graph Pruning](https://mlsanity.com/paper/2507.05649/) (2025)
- [A Systematic Study of Model Extraction Attacks on Graph Foundation Models](https://mlsanity.com/paper/2511.11912/) (2025)
- [Can Subgraph Explanations Be Weaponized to Steal Graph Neural Networks?](https://mlsanity.com/paper/2605.30470/) (2026)
- [AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network](https://mlsanity.com/paper/2606.19185/) (2026)
- [Dagger: Decoupling-based Model Stealing Attack against Graph Neural Networks](https://mlsanity.com/paper/2609.37972/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have demonstrated remarkable utility across diverse applications, and their growing complexity has made Machine Learning as a Service (MLaaS) a viable platform for scalable deployment. However, this accessibility also exposes GNN to serious security threats, most notably model extraction attacks (MEAs), in which adversaries strategically query a deployed model to construct a high-fidelity replica. In this work, we evaluate the vulnerability of GNNs to MEAs and explore their potential for cost-effective model acquisition in non-adversarial research settings. Importantly, adaptive node querying strategies can also serve a critical role in research, particularly when labeling data is expensive or time-consuming. By selectively sampling informative nodes, researchers can train high-performing GNNs with minimal supervision, which is particularly valuable in domains such as biomedicine, where annotations often require expert input. To address this, we propose a node querying strategy tailored to a highly practical yet underexplored scenario, where bulk queries are prohibited, and only a limited set of initial nodes is available. Our approach iteratively refines the node selection mechanism over multiple learning cycles, leveraging historical feedback to improve extraction efficiency. Extensive experiments on benchmark graph datasets demonstrate our superiority over comparable baselines on accuracy, fidelity, and F1 score under strict query-size constraints. These results highlight both the susceptibility of deployed GNNs to extraction attacks and the promise of ethical, efficient GNN acquisition methods to support low-resource research environments.