{"id":"b9b4cad6-5073-4a84-8c41-4cccd12e4028","arxiv_id":"1908.06418","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"A portfolio that runs parallel CPU and GPU versions of the McSplit algorithm together solves more maximum common subgraph benchmark instances within time limits than any single version.","lead":"The paper combines several versions of a graph-matching algorithm so that they run at the same time on a computer's CPU and GPU. The combined portfolio solves more of the test problems within a time limit than any single version.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Portfolio comparison lacks resource-normalized baseline: vP uses CPU and GPU simultaneously, so its dominance may reflect extra hardware, not portfolio design.","rationale":"The paper contains substantial engineering work: a careful parallel CPU implementation, a GPU adaptation with explicit handling of recursion and memory limits, and a portfolio harness. The profiling data (stall reasons, branch divergence) are plausible and give credit to the implementation effort. However, the publish-or-perish claim is the portfolio's superiority, and that claim rests entirely on wall-clock comparisons in Fig. 12. The most load-bearing assumption is that wall-clock time is a fair metric when the portfolio is the only configuration allowed to use both the multicore CPU and the GPU at once. That assumption is not defended anywhere in the paper. The reader's verdict already flagged missing variance statistics and benchmark representativeness; my concern is distinct and more fundamental: even with ideal representative benchmarks and repeated runs, the reported comparison would not establish that the portfolio methodology, rather than the simple addition of hardware, is responsible for the gains. This is testable with a trivial concurrent baseline, and the outcome determines whether the central claim survives. I therefore agree with the conditional verdict: the paper should be accepted only if the authors supply such a baseline or explicitly restrict their claim to 'using all available hardware.' The concern is addressable, not a rejection of the paper's other contributions.","tokens_in":18270,"tokens_out":3737,"duration_ms":39608,"concrete_test":"Run a trivial concurrent baseline on the same machine and benchmark subsets: launch mc2 (parallel CPU, 8 threads) and v5 (GPU) as two independent processes on each graph pair, terminate both as soon as either produces a result, and record wall-clock time. Plot the cumulative number of solved instances against the vP curves in Fig. 12a (small graphs, 10 s limit) and Fig. 12b (small+medium, 1000 s limit). If the trivial baseline matches or exceeds vP, the advantage attributed to the portfolio's online decision-making and heuristics is not supported. If vP solves a strictly larger set within the limits, the resource-normalization concern is resolved.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central empirical claim is that vP 'is faster on average and able to solve more instances than any other method' (Section V-C, Fig. 12). The comparison, however, is not resource-normalized: vP is the only configuration that simultaneously uses the 8-thread CPU pool (through v2/v4 and the modified CPU versions) and the GTX 980 GPU (through v5). Every non-portfolio baseline uses either the CPU alone (mc1, mc2, v1-v4) or the GPU alone (v5). The paper explicitly states that CPU and GPU versions 'run on separated platforms' to avoid bandwidth contention, confirming that vP consumes strictly more hardware than any individual alternative. Wall-clock time alone therefore cannot distinguish a better algorithm from a configuration that has been given more compute resources. This is not a pedantic point: the paper's own Fig. 11 shows that the proposed heuristics (reordering, dead-end prediction, restarts) do not improve average performance over the base version. Thus the measured advantage of vP over mc2 and v5 could in principle be reproduced by a trivial scheduler that simply runs mc2 and v5 concurrently and returns whichever finishes first, without any of the paper's online selection or modified engines. The paper provides no such baseline, so the portfolio claim is unsupported as stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper extends the McSplit branch-and-bound algorithm for the maximum common subgraph problem to parallel multi-core CPU and CUDA GPU implementations. It introduces three heuristics: adjacency-matrix reordering, dead-end prediction with bound correction, and randomized restarts. It then proposes a portfolio (vP) that runs sequential, multi-core CPU, and GPU variants concurrently under a Python orchestrator. Experiments on a subset of the ARG benchmark (2,750 small and 240 medium undirected unlabeled graph pairs) are used to claim that vP is faster on average and solves more instances than any individual version.","tokens_in":18508,"tokens_out":6241,"duration_ms":61101,"significance":"If the central empirical claim were established with proper controls, the paper would offer practical engineering insights for parallelizing branch-and-bound MCS solvers, particularly the GPU adaptation and the online portfolio. The paper is transparent about algorithmic details and shows that the individual heuristics do not improve average performance (Fig. 11), which is an honest limiting result. However, the headline claim about the portfolio rests on a comparison that is not resource-normalized and on single-run randomized measurements, so the current evidence does not fully support the conclusion.","major_comments":[{"comment":"The comparison is not resource-normalized. vP simultaneously uses the sequential pre-run, the 8-thread CPU pool (via v2/v4), and the GPU (via v5), while each baseline (mc1, mc2, v2, v5) uses only a single engine/hardware type. The paper explicitly notes that CPU and GPU versions run on separated platforms to avoid bandwidth contention, confirming that vP consumes strictly more hardware than any individual alternative. The superior wall-clock performance of vP could therefore be an artifact of using more hardware rather than of the portfolio's online selection or modified engines. A trivial control that runs mc2 and v5 concurrently and returns the first result is never evaluated; without it, the portfolio claim is unsupported as stated.","section":"V-C, Fig. 12"},{"comment":"The restart heuristic is explicitly randomized (''random selection of the another tree branch''), and vP includes versions augmented with this heuristic. Yet every data point in the cumulative plots comes from a single run, with no variance statistics, confidence intervals, or repeated-run medians. MCS solver runtimes are known to be heavy-tailed, and a single run can change the ordering of methods, especially for randomized algorithms. The authors should report repeated runs with different random seeds and present medians and a spread measure for the randomized versions and for vP.","section":"IV-A and Figs. 6-12"},{"comment":"Several thresholds (PART_LEVEL, the dead-end recursion threshold, the restart trigger factor, the portfolio pre-run time, thread-pool size) are hand-tuned, and the evaluation is performed on the same ARG subset used to observe these settings, with no training/test separation or cross-benchmark robustness check. The concluding claim in Section VI that ''the portfolio approaches is beneficial in the domain'' is therefore only supported for this particular benchmark subset and configuration. A sensitivity analysis over the thresholds and an evaluation on at least one additional benchmark family (e.g., directed or labeled graphs) would be needed to support the general claim.","section":"V-A and V-C"}],"minor_comments":[{"comment":"The text states that the plot covers ''the small and the medium graph sets considered together,'' but the y-axis maximum is 80, which cannot represent the combined 2,990 instances; the caption should state which subset is actually shown.","section":"V-B, Fig. 8"},{"comment":"In the paragraph describing the thread pool, ''the the working thread'' should be ''the working thread.''","section":"III-A"},{"comment":"''in the time range fro 0 to 10 seconds'' should be ''from 0 to 10 seconds.''","section":"V-C"},{"comment":"''the portfolio approaches is beneficial'' should be ''the portfolio approach is beneficial.''","section":"VI"},{"comment":"''orchestrated by a a Python interface'' should be ''by a Python interface.''","section":"IV"},{"comment":"The name ''McCreesh'' is sometimes spelled ''Mc Creesh'' (e.g., Section IV-A); please unify the spelling.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper's main contribution is empirical; if the resource-normalization and variance issues are addressed, it could be a useful addition to the MCS literature. The narrow benchmark subset and the absence of a code/data availability statement also limit reproducibility; the editor may wish to encourage the authors to release the code and expand the evaluation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the genuinely new pieces here are the iterative CUDA implementation of McSplit and the CPU+GPU portfolio that orchestrates several variants. The paper is worth a serious look, but the central claim that vP \"is faster on average and able to solve more instances than any other method\" is not fully supported as stated.\n\nWhat it does well: the CUDA port is a real piece of engineering. Removing recursion by keeping a stack of bidomains, using unsigned char compactness, and handling workload imbalance through a task queue are all sensible and non-obvious. The heuristics (adjacency reordering, dead-end prediction, restarts) are well-motivated, and the authors are honest that they don't help on average but do help on specific instances. That is exactly the kind of diversity a portfolio can exploit. The literature coverage is fair: they build on Trimble's parallel McSplit and Kotthoff's subgraph-isomorphism portfolio and say so.\n\nThe soft spots are mostly experimental. The biggest one is resource normalization. vP runs eight CPU threads plus the GPU simultaneously; every individual baseline uses either the CPU pool or the GPU, not both. So the wall-clock advantage of vP could be reproduced by a trivial \"run mc2 and v5 concurrently, return whichever finishes\" scheduler, without any of the paper's online selection or modified engines. The paper does not include that baseline, and without it the portfolio claim is underdetermined. This is not a nitpick; it's the main evidence for the paper's headline.\n\nAlso: the restart heuristic is randomized, yet every data point comes from a single run, with no variance statistics. On heavy-tailed MCS runtime distributions, a different seed or a slightly different benchmark slice could change the ordering. The parameter tuning (PART_LEVEL, restart trigger, dead-end threshold, pre-run time) is done on the same ARG subset used for evaluation, so the measured gains may partly reflect overfitting to that slice. The benchmark set is also narrow: undirected, unlabeled pairs up to 50 vertices. The pseudo-code in Algorithm 1 has an apparent depth-handling bug: when enqueuing a task it passes depth rather than depth+1, which, taken literally, would never advance past a shallow level. I assume the real code does something else, but the pseudocode should be fixed. No code is released, which makes all of this harder to check.\n\nWho this is for: practitioners who need exact MCS on small graphs and have a GPU available. It is an incremental but useful contribution, and the CUDA details are the most valuable part. It deserves a serious referee, and I would accept it with major revision: add the trivial CPU+GPU baseline, report repeated runs, and release the code.\n\nMy vote: send it to review, but expect the authors to earn the portfolio claim with a fairer comparison.","headline":"A useful CUDA + portfolio extension of McSplit, but the portfolio's dominance claim needs a resource-normalized baseline before it can be taken at face value.","tokens_in":19065,"tokens_out":2188,"would_cite":false,"duration_ms":25171,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C60","05C85","68R10","68W10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A portfolio that runs several CPU and GPU solvers at once solves more maximum-common-subgraph instances than any single variant tested.","keywords":["maximum common subgraph","McSplit","branch and bound","parallel computing","CUDA","GPU","portfolio algorithms","graph isomorphism"],"falsifier":"Run the same seven versions plus the portfolio on a different benchmark family, for example directed, labeled, or 50-100 vertex pairs, with multiple random seeds, and record cumulative solved counts under 10-second and 1,000-second limits; if any single version matches the portfolio, or if changing seeds reverses the ordering, the paper's dominance claim would be refuted.","tokens_in":18029,"feed_emoji":"🧩","tokens_out":7760,"duration_ms":71687,"temperature":0.7,"pith_summary":"This paper claims that the exact maximum common subgraph problem, which is NP-hard and already computationally unfeasible at around 40 vertices without extra information, can be tackled more effectively by a portfolio that runs several variants of the McSplit branch-and-bound procedure in parallel instead of betting on one. It reports multi-core and GPU (CUDA) implementations, plus heuristics that reorder the adjacency matrix, predict dead-ends, and restart the search, and then combines them in an online portfolio. In experiments on 2,750 small and 240 medium graph pairs from a standard benchmark database, the portfolio solves more instances within 10-second and 1,000-second limits than any individual sequential or parallel version. If the claim holds, the practical message is that heterogeneous hardware can be used as a solver strategy rather than just as a speed-up device.","feed_headline":"CPU+GPU solver portfolio outperforms every single MCS solver","feed_subtitle":"On 2,750 small and 240 medium test graph pairs, the combined portfolio solves the most within time limits.","key_machinery":"The load-bearing object is McSplit's branch-and-bound search driven by label classes: a vertex pair can enter the mapping only if the two vertices share the same label, meaning the same adjacency pattern to already mapped vertices, and the pruning bound is computed by Equation (1) as the current mapping size $|M|$ plus, for every label class, the smaller of the numbers of remaining vertices in the two graphs carrying that label. On top of this the paper adds a thread pool with a priority task queue for the CPU, an explicit stack of compact bidomain records for the GPU, three heuristics (block-oriented adjacency matrix reordering, dead-end forecasting with bound correction, and randomized restarts), and finally the portfolio vP, which runs several engines concurrently and lets the first finisher decide.","core_discovery":"On the paper's own terms, the discovery is that none of the individual McSplit variants dominates: different heuristics win on different instances, CPU parallel versions are strongest on easy and medium cases, and the GPU version, though slow to start, overtakes CPU versions on harder cases. Because these strengths are complementary, the paper proposes a portfolio, vP, in which all engines run concurrently under a Python orchestrator and algorithm selection happens online, by whichever process finishes first. The paper reports that this portfolio is faster on average and solves more instances than any other method on both wall-clock time and graph-size ranges tested.","pith_inferences":["Because the paper's runtime data are single runs of a randomized restart procedure, a natural test is to run the portfolio with several seeds; variance in heavy-tailed distributions could change the exact ordering even if the portfolio's complementarity persists.","The same online portfolio recipe, run CPU and GPU engines concurrently and let the first finisher win, could transfer to other recursive search problems such as subgraph isomorphism, connected MCS, or SAT, where portfolio methods currently rely heavily on offline algorithm selection.","The matrix-reordering heuristic based on block triangularization suggests a cheap feature, component block structure, that could feed a per-instance scheduler mixing offline selection with online racing.","The portfolio's dominance is demonstrated only on undirected, unlabeled graphs up to 50 vertices, so extending the same race-based design to labeled, directed, or larger instances is an untested but promising direction."],"forward_implications":["The portfolio vP solves more instances within wall-clock limits and is faster on average than every individual version tested.","The multi-core version speeds up McSplit without changing its search behavior, with speedups approaching an order of magnitude on harder instances.","The GPU version is uncompetitive on small and easy instances because of fixed transfer and launch overhead, but becomes faster than CPU versions in the tested harder range.","The new heuristics do not improve average runtime by themselves; their value is that each wins on a distinct subset of instances, which is exactly what makes the portfolio win overall.","Dead-end prediction converts long unproductive searches into bound refinement, either by raising the bound or by binary search between known lower and upper bounds."],"supporting_citations":[{"why":"Supplies the McSplit branch-and-bound algorithm that every version in the paper derives from.","marker":"[3]"},{"why":"Supplies the ARG database and the mcs10-mcs90 graph pair classes used in the experiments.","marker":"[8]"},{"why":"Supplies the companion description of the graph database and its benchmarking use.","marker":"[7]"},{"why":"Introduces portfolios of subgraph isomorphism algorithms, the concept the paper adapts to MCS.","marker":"[6]"},{"why":"Supplies the top-down goal-size search strategy used for dead-end handling.","marker":"[26]"},{"why":"Supplies the matrix reordering procedure used to permute adjacency matrices.","marker":"[27]"},{"why":"Supplies the randomized-restart strategy borrowed from SAT solving.","marker":"[28]"},{"why":"Supplies clique and constraint encodings of MCS considered alongside the McSplit variants.","marker":"[25]"}],"fun_headline_variants":["Portfolio of CPU and GPU solvers wins on MCS instances","Concurrent CPU+GPU solvers beat any single MCS method","Online solver selection: portfolio outperforms individual MCS solvers","Parallel portfolio solves more MCS instances than any single tool","Complementary CPU/GPU engines make MCS portfolio champion"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the tested benchmark slice, undirected, unlabeled graph pairs with up to 50 vertices from the ARG database, represents real maximum-common-subgraph workloads well enough that solving more of them within time limits is a genuine general benefit.","fun_headline_variants_meta":{"raw":{"variants":["Portfolio of CPU and GPU solvers wins on MCS instances","Concurrent CPU+GPU solvers beat any single MCS method","Online solver selection: portfolio outperforms individual MCS solvers","Parallel portfolio solves more MCS instances than any single tool","Complementary CPU/GPU engines make MCS portfolio champion"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000467,"raw_usage":{"total_tokens":2307,"prompt_tokens":902,"completion_tokens":1405,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":518,"completion_tokens_details":{"reasoning_tokens":1319}},"tokens_in":518,"tokens_out":1405,"duration_ms":10109,"temperature":1.0,"reasoning_tokens":1319,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:46:10.587115+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same seven versions plus the portfolio on a different benchmark family, for example directed, labeled, or 50-100 vertex pairs, with multiple random seeds, and record cumulative solved counts under 10-second and 1,000-second limits; if any single version matches the portfolio, or if changing seeds reverses the ordering, the paper's dominance claim would be refuted.","supporting_citations":[{"cited_title":"A partitioning algorithm for maximum common subgraph problems,","cited_arxiv_id":null,"evidence_quote":"Supplies the McSplit branch-and-bound algorithm that every version in the paper derives from."},{"cited_title":"A database of graphs for iso- morphism and sub-graph isomorphism benchmarking,","cited_arxiv_id":null,"evidence_quote":"Supplies the ARG database and the mcs10-mcs90 graph pair classes used in the experiments."},{"cited_title":"A large database of graphs and its use for benchmarking graph isomorphism algorithms,","cited_arxiv_id":null,"evidence_quote":"Supplies the companion description of the graph database and its benchmarking use."},{"cited_title":"Portfolios of subgraph iso- morphism algorithms,","cited_arxiv_id":null,"evidence_quote":"Introduces portfolios of subgraph isomorphism algorithms, the concept the paper adapts to MCS."},{"cited_title":"Between subgraph isomor- phism and maximum common subgraph,","cited_arxiv_id":null,"evidence_quote":"Supplies the top-down goal-size search strategy used for dead-end handling."},{"cited_title":"The partitioned preassigned pivot proce- dure (p4),","cited_arxiv_id":null,"evidence_quote":"Supplies the matrix reordering procedure used to permute adjacency matrices."},{"cited_title":"Boosting combinatorial search through randomization,","cited_arxiv_id":null,"evidence_quote":"Supplies the randomized-restart strategy borrowed from SAT solving."},{"cited_title":"Clique and constraint models for maximum common (connected) subgraph prob- lems,","cited_arxiv_id":null,"evidence_quote":"Supplies clique and constraint encodings of MCS considered alongside the McSplit variants."}],"review_version":1}