Research map / Graph learning / Graph algorithms and clustering
Surprisingly Strong Performance Prediction with Neural Graph Features
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 neural graph features (GRAF), simple data-independent architecture-graph statistics (operation counts, min/max path lengths, node degrees over operation subsets) that, fed to a random forest with zero-cost proxies, outperform ZCP and common encodings for NAS performance prediction.
Problem
Zero-cost proxies for NAS performance prediction are poorly understood, biased toward network properties such as convolution counts, and inconsistent across tasks; existing predictors need trained networks or are costly and uninterpretable.
Approach
Analyze zero-cost proxy biases (dependence on number of convolutions), then propose interpretable graph features computed over all operation subsets (operation counts, min/max path lengths, input/output node degrees) that are data-independent and cheap to compute, and combine them with ZCP in a random forest predictor.
Key results
- On NB201 cifar-10 with 1024 training samples, ZCP+GRAF achieves Kendall tau 0.84 versus 0.81 for ZCP alone (random forest).
- On NB101 cifar-10 with 32 training samples, GRAF reaches Kendall tau 0.54 versus 0.24 for one-hot encoding and 0.48 for ZCP.
- GRAF with random forest outperforms ZCP and one-hot on most benchmarks and tasks, and ZCP+GRAF is the best predictor in the NASLib comparison across settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add GRAF features to ZCP | Random-forest validation-accuracy predictor · NB101 CIFAR-10, train size 1024 | Kendall tau: 0.63 -> 0.73 | Helped |
| Add GRAF features to ZCP | Random-forest validation-accuracy predictor · NB201 CIFAR-10, CIFAR-100, and ImageNet16-120 | Kendall tau | Helped |
| Use GRAF instead of ZCP | Random-forest validation-accuracy predictor · NB201, smaller training sample sizes | Kendall tau | Hurt |
| Add path encoding to GRAF (ablation) | Validation-accuracy predictor · CIFAR-10 on NB101, NB201, and NB301; CIFAR-100 on NB201; largest sample size | Kendall tau | Mixed |
| Add path encoding to GRAF (ablation) | Validation-accuracy predictor · ImageNet16-120 and TNB101-micro | Kendall tau | No clear effect |
| Add path encoding to ZCP without GRAF (ablation) | Validation-accuracy predictor · NAS benchmarks | Kendall tau | Helped |
| Add Weisfeiler-Lehman features or arch2vec to GRAF (ablation) | Validation-accuracy predictor · NAS benchmarks | Kendall tau | No clear effect |
| Add node-degree features (ablation) | ZCP + GRAF predictor · NB201 CIFAR-10, train size 1024 | Kendall tau | Helped |
| Remove minimum-path-length features (ablation) | ZCP + GRAF predictor · NB201 CIFAR-10, train size 1024 | Kendall tau | Hurt |
| Remove operation-count features (ablation) | ZCP + GRAF predictor · NB201 CIFAR-10, train size 1024 | Kendall tau | No clear effect |
| Replace the full GRAF feature set with its linearly independent subset (ablation) | Random-forest predictor using GRAF alone · NB101, NB201, and NB301 | Kendall tau | Hurt |
| Replace the full GRAF feature set with its linearly independent subset (ablation) | ZCP + GRAF predictor · NB101 and NB201 | Kendall tau | No clear effect |
Surprising findings
- Several zero-cost proxies (e.g., nwot, l2_norm) are essentially direct functions of the number of convolutions in NAS-Bench-201, rather than capturing other useful information.
- GRAF features alone are sufficient for some non-classification tasks, and the features on NB201 are highly redundant in a linear sense, yet reducing them hurts performance on NB301.
Limitations
- Zero-cost proxies are still needed for best results, indicating GRAF does not capture all relevant properties.
- New graph features must be designed for search spaces that differ significantly from the cell-based and macro spaces studied, and transfer across operation sets is limited.
- Results rely on precomputed ZCP and benchmark subsets (e.g., limited NB101/NB301 subsets, unreachable-branch networks removed), limiting generality.
Experimental setup
Datasets: NAS-Bench-101 NAS-Bench-201 NAS-Bench-301 TransNAS-Bench-101 micro TransNAS-Bench-101 macro HW-NAS-Bench NAS-Bench-201 robustness dataset cifar-10 cifar-100 ImageNet16-120
Benchmarks: NAS-Bench-101 NAS-Bench-201 NAS-Bench-301 TransNAS-Bench-101 micro TransNAS-Bench-101 macro HW-NAS-Bench NAS-Bench-201 robustness
Metrics: Kendall tau Spearman correlation search sample efficiency
Baselines: zero-cost proxies (ZCP) one-hot encoding path encoding arch2vec BRP-NAS TA-GATES XGB+ SemiNAS BANANAS GCN predictor
Builds on: NAS-Bench-Suite-Zero NASLib BRP-NAS NASBOWL
Closest papers by meaning
- NAS-Bench-Suite-Zero: Accelerating Research on Zero Cost Proxies (NeurIPS 2022 · similarity 0.89)
- AZ-NAS: Assembling Zero-Cost Proxies for Network Architecture Search (CVPR 2024 · similarity 0.89)
- EZNAS: Evolving Zero-Cost Proxies For Neural Architecture Scoring (NeurIPS 2022 · similarity 0.89)
- ParZC: Parametric Zero-Cost Proxies for Efficient NAS (AAAI 2025 · similarity 0.87)
- NEAR: A Training-Free Pre-Estimator of Machine Learning Model Performance (ICLR 2025 · similarity 0.87)
- Encodings for Prediction-based Neural Architecture Search (ICML 2024 · similarity 0.86)
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.