SCE-KG cuts tail error by up to 40×—but its training bill is the benchmark’s missing half

The result

SCE-KG reports as much as a 40× reduction in 95th-percentile q-error for star queries and 37× for chain queries against the paper’s comparison methods. That tail result matters more than a tidy median: cardinality estimators hurt query plans most when they are catastrophically wrong, and similarity thresholds add another source of skew that an equality-only estimator cannot represent.

The primary paper evaluates SCE-KG on three real graphs—SWDF, Yelp and a roughly 160,000-node UK-people slice of Wikidata—plus synthetic LUBM data. Queries use Levenshtein similarity, and the comparison includes LMKG after stripping similarity values, an extended SG encoding called SGsim-MLP, and SCE-KG’s split encoding. The paper reports results separately for star and chain shapes; it does not turn those numbers into a claim about arbitrary production SPARQL workloads.

A better stress test than one generator

The most useful design choice is a second evaluation around workload generation. Gemini 2.5 Flash produced training queries, while two held-out sets were generated from different prompts: 1,707 Gemini queries and 1,404 GPT-4o queries. On the full training set, a 50/50 mixture of random walks and LLM-generated queries reduced median q-error 12–22% and 95th-percentile q-error 28–35% relative to random walks alone across both test sets.

With training reduced to 30,000 samples, pure LLM-generated data did better: median q-error fell 34–62% and the 95th percentile fell 47–74% relative to random walks. The same ordering on GPT-4o-generated tests weakens the easy objection that Gemini merely learned its own query distribution. It does not eliminate generator bias: both held-out sets are synthetic LLM workloads, not traces from deployed graph applications.

Accuracy is not free

The paper is unusually clear about offline cost. On five-join Wikidata training, LMKG took about 27 minutes, SGsim-MLP 22 minutes, and SCE-KG 52 minutes on a 24-core Threadripper server with 256GB RAM and an RTX 2080 Ti. Online estimation remained sub-millisecond and below 0.05% of average execution time and 1% of average planning time in the measured setup.

That makes the deployment contract fairly crisp: SCE-KG buys much better tail estimates by training a more complex family of models, while keeping inference cheap. What remains unmeasured is the maintenance bill—retraining under graph drift, changing similarity functions, and workloads beyond the tested star and short-chain shapes. Until those appear, the 40× headline is strong benchmark evidence, not a production guarantee.