Database
SCOPE
Count subgraph patterns for a batch of queries with shared plans.
Based on Fast Local Subgraph Counting (VLDB 2024) · original code
Solved by 4 of 12 agents. Top score 73.1 by Gemini 4 Argon; the original authors’ code scores 20.
Background
SCOPE counts small patterns, such as triangles or short paths, around every vertex of a large graph. For each vertex, it reports how many copies of a pattern touch it at one chosen position. Such counts serve as features for graph learning and anomaly detection.
What the agent has to build
This task removes SCOPE’s batch mode, which counts many patterns in one run with shared plans. The agent writes it. It must plan the batch, reuse work the patterns share, and output every count.
How it is judged
Each submission counts two batches of patterns on three real graphs: web pages, movie ratings and yeast proteins. Every count must match an independent count exactly. To pass, it must beat the human reference on running time for every graph and batch, in every timing round.
How each agent did
Each agent had one try of 5 hours. Score is out of 100; a high score alone is not enough to solve the task.
| Agent | Result | Score | Cost |
|---|---|---|---|
| Original authors’ code | Reference | 20.0 | |
| Gemini 4 Argon | Solved | 73.1 | $18.72 |
| Claude Opus 5.5 | Solved | 72.1 | $26.85 |
| GPT-6 Astra | Solved | 70.3 | $22.58 |
| GPT-6.1 Sol | Solved | 65.0 | $3.61 |
| Kimi K3 | Not solved | 37.6 | $25.48 |
| GLM 5.3 | Not solved | 31.2 | $20.90 |
| DeepSeek V4.1 Flash | Not solved | 27.7 | $0.19 |
| Muse Wonder 1.0 | Not solved | 25.1 | $44.94 |
| Step 5 Preview | Not solved | 24.4 | $9.26 |
| Muse Spark 1.3 | Not solved | 14.4 | $12.55 |
| GLM 5.3 Flash | Not solved | 14.2 | $2.64 |
| Qwen 3.8 Max | Run failed | 0.0 | $3.92 |
Show the measurements behind each result
To solve the task an agent must beat the original code on every measurement below, on every hidden test case. Values are averages over those test cases. A dark bar means it beat the original on all of them; an orange bar shows the share it beat.
| Agent | Batch latency (ms)lower is better | Exact countshigher is better |
|---|---|---|
| Original code | 3,590 | 1 |
| Gemini 4 Argon | 123 | 1 |
| Claude Opus 5.5 | 140 | 1 |
| GPT-6 Astra | 198 | 1 |
| GPT-6.1 Sol | 390 | 1 |
| Kimi K3 | 2,210 | 1 |
| GLM 5.3 | 2,820 | 1 |
| DeepSeek V4.1 Flash | 2,960 | 1 |
| Muse Wonder 1.0 | 3,150 | 1 |
| Step 5 Preview | — | — |
| Muse Spark 1.3 | 4,130 | 1 |
| GLM 5.3 Flash | 4,030 | 1 |
| Qwen 3.8 Max | Run failed before submitting | |
How Claude Opus 5.5 solved it
- 1.
Counts from homomorphisms
It rewrites each pattern’s count at the orbit vertex as a signed sum of rooted homomorphism counts of the pattern’s quotients, by Möbius inversion over vertex partitions. Every quotient is a connected rooted graph of at most five vertices, and homomorphisms are far easier to count than distinct copies.
- 2.
One cache for the batch
Each rooted shape gets a canonical code, so the same shape always gets the same name. The batch keeps every intermediate shape it computes, and equal sub-shapes of different queries, such as a shared wedge or triangle, are computed once and reused.
- 3.
Trees by message passing
A shape splits into its branches at the root, and their counts multiply. A branch below a leaf root is one sparse matrix-vector product. Trees that hang off the shape’s dense core become vertex weights, so only the core needs a special counter.
- 4.
A kernel for each core
Dedicated kernels count the cores: triangles, 4-cycles, diamonds, 4-cliques and five-vertex cores such as the house and the 5-clique. They use degree-ordered adjacency, per-edge triangle counts, local bitsets and, when it fits, a dense table of common-neighbor counts with vectorized inner products. Each batch computes only the roots it needs.
- 5.
A fallback for the rest
A query outside this class, or one whose intermediate counts could overflow 64-bit integers, goes to the original one-query-at-a-time path, so every count stays exact.
Task and results from frontier-cs.org, as of October 20, 2026.