Research map / Learning theory and algorithms / Combinatorial and search optimization
Trained Random Forests Completely Reveal your Dataset
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.
Formulates dataset reconstruction from a trained random forest as a maximum-likelihood constraint programming problem using only scikit-learn-visible node counts and tree structure, showing near-complete reconstruction on COMPAS, Adult and Default Credit.
Problem
Reconstructing the full training dataset of a random forest in the white-box setting, using only the tree structure and per-node class counts exposed by default libraries such as scikit-learn.
Approach
Treats reconstruction as a combinatorial maximum-likelihood problem over the whole forest, encoded as a CP-SAT model that links examples to leaves across trees and weights bootstrap multiplicities by their binomial-type probability; proves NP-completeness and shows that the problem is solvable at practical scale.
Key results
- Without bagging but with feature randomization, reconstruction error reaches 0 for the deepest forests on all three datasets.
- With bagging, reconstruction error plateaus at a non-zero threshold, so only a majority of the data is recovered.
- Without bagging, the CP model is faster than the MILP formulation on COMPAS (avg 49.7 s vs 188.3 s for unlimited depth).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Using CP formulation instead of MILP (Gurobi) for no-bagging reconstruction (ablation) | COMPAS reconstruction without bagging · COMPAS, no bagging, max depth None | average reconstruction time (s): 49.7 s (CP) vs 188.3 s (MILP) | Helped |
| Bagging enabled when training the target RF | Random forest reconstruction · Adult and Default Credit, 100 trees, no depth limit | solver runs without feasible solution: 0 to 1/5 (Adult), 0 to 4/5 (Default Credit) for reconstruction feasibility | Hurt |
| Bagging enabled when training the target RF (reconstruction error protection) | Random forest training data protection · COMPAS, Adult, Default Credit | reconstruction error: error plateaus above zero with bagging vs reaching 0 without bagging | Helped |
Surprising findings
- Even a single tree or few trees can leak much of the data when bagging is off, and deep default forests with no depth limit are often fully reconstructed.
- Bagging offers only partial protection: the error stops improving even for large forests, because multiplicities are hard to guess.
Limitations
- NP-hard in general and scalability is limited; bagging cases often hit the 5-hour time limit without proving optimality.
- Experiments use small training sets (N=100) and binarized features with some attributes removed.
- Assumes attacker knows per-node class counts, attribute domains, and split features (white-box, no defenses such as differential privacy evaluated).
Experimental setup
Datasets: COMPAS UCI Adult Income Default of Credit Card Clients
Benchmarks: COMPAS UCI Adult Income Default of Credit Card Clients
Metrics: reconstruction error (proportion of differing binary attribu solver run time number of infeasible runs
Baselines: random reconstruction baseline MILP formulation (Gurobi)
Builds on: OCEAN CP-SAT
Closest papers by meaning
- Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees (NeurIPS 2026 · similarity 0.85)
- Improving Private Random Forest Prediction Using Matrix Representation (AAAI 2025 · similarity 0.85)
- DynFrs: An Efficient Framework for Machine Unlearning in Random Forest (ICLR 2025 · similarity 0.85)
- From Counterfactuals to Trees: Competitive Analysis of Model Extraction Attacks (NeurIPS 2025 · similarity 0.84)
- Reconstruction Attacks on Machine Unlearning: Simple Models are Vulnerable (NeurIPS 2024 · similarity 0.84)
- High-Fidelity Gradient Inversion in Distributed Learning (AAAI 2024 · similarity 0.83)
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.