Research map / Graph learning / GNN architectures
CEGA: A Cost-Effective Approach for Graph-Based Model Extraction and Acquisition
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes CEGA, an iterative active node-querying strategy that extracts GNN node classifiers from a MLaaS-style target under strict initial, per-cycle and total query budgets, combining centrality, entropy/perturbation-based uncertainty, and diversity.
Problem
Graph neural network model extraction under realistic limited query budgets where bulk queries are prohibited and only a small initial node set is available; also framed as cost-effective acquisition for research settings with expensive labels.
Approach
Iteratively selects queried nodes by a weighted average rank of three criteria: PageRank-based representativeness, history-based uncertainty (entropy of an interim GCN, or a Gaussian-perturbation prediction-stability alternative), and a cluster-based diversity score, with weights shifting from structure to history as cycles progress.
Key results
- At 20C queried nodes, CEGA reaches the best fidelity on all six datasets, e.g., 95.83% on Coauthor-Physics and 78.50% on DBLP (AGE 77.18%).
- On Cora-Full with 20C queries, CEGA's accuracy gap to the full subgraph model is -1.36%, i.e., the budget-constrained model slightly exceeds the full model.
- Ablation on fidelity at 20C shows removing centrality or uncertainty lowers results; on DBLP, removing uncertainty drops fidelity from 78.5% to 65.1%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Adding the uncertainty (entropy/perturbation) ranking to the CEGA selection (ablation) | CEGA node selection · Ablation on 6 datasets at 20C | fidelity: CoP 95.8 vs 90.2; DBLP 78.5 vs 65.1 without uncertainty | Helped |
| Adding the centrality (PageRank) ranking to the CEGA selection (ablation) | CEGA node selection · Ablation on 6 datasets at 20C | fidelity: Cora_Full 77.9 vs 75.3; DBLP 78.5 vs 74.2 without centrality | Helped |
| Adding the diversity ranking to the CEGA selection (ablation) | CEGA node selection · Ablation on 6 datasets at 20C | fidelity: Mean fidelity within about 1 point; No Div slightly higher on Cora_Full (78.3 vs 77.9) and DBLP (78.6 vs 78.5) | No clear effect |
| CEGA full method vs AGE baseline (fidelity on 6 datasets at 20C) | CEGA · Cora_Full and DBLP | fidelity: Cora_Full 77.90 vs 75.67; DBLP 78.50 vs 77.18 | Helped |
| CEGA vs AGE on accuracy at 20C | CEGA · CoCS, the one dataset where AGE is higher | accuracy: AGE 90.68 vs CEGA 90.57 on CoCS; CEGA wins on other 5 datasets | Mixed |
| CEGA vs AGE on performance gap to full subgraph model (accuracy) | CEGA · Table 3, 20C, 6 datasets | accuracy gap: CEGA -1.36 on Cora_Full vs AGE 0.90; AGE gap lower on CoCS (0.78 vs 0.91) | Mixed |
Surprising findings
- On Cora-Full, the budget-constrained CEGA model slightly outperforms the full subgraph model in accuracy and F1 (negative gap).
Limitations
- Assumes transductive setting; extension to inductive GNNs left for future work.
- Ablation and tuning use fixed hyperparameters (alpha, Delta, lambda, rho=0.8) chosen across datasets, with limited sensitivity analysis.
- Theoretical stability result is an existence guarantee for the perturbation scale epsilon rather than a practical selection rule.
Experimental setup
Datasets: Coauthor-CS Coauthor-Physics Amazon-Computer Amazon-Photo Cora-Full DBLP
Benchmarks: Coauthor-CS Coauthor-Physics Amazon-Computer Amazon-Photo Cora-Full DBLP
Metrics: accuracy fidelity F1 score
Baselines: Random GRAIN(NN-D) GRAIN(ball-D) AGE
Builds on: AGE GRAIN PageRank GCN
Closest papers by meaning
- Value at Adversarial Risk: A Graph Defense Strategy against Cost-Aware Attacks (AAAI 2024 · similarity 0.88)
- If You Want to Be Robust, Be Wary of Initialization (NeurIPS 2024 · similarity 0.88)
- A Simple and Yet Fairly Effective Defense for Graph Neural Networks (AAAI 2024 · similarity 0.87)
- Can Graph Neural Networks Expose Training Data Properties? An Efficient Risk Assessment Approach (NeurIPS 2024 · similarity 0.87)
- GraphIP–Bench: How Hard Is It to Steal a Graph Neural Network, and Can We Stop It? (NeurIPS 2026 · similarity 0.87)
- Highly Imperceptible Black-Box Graph Injection Attacks with Reinforcement Learning (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.