{"id":"99b69647-7311-43b0-a0f6-512c43aa7134","arxiv_id":"2412.02196","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Seed-architecture expansion via Kendall-tau subgraph matching and entropy-guided node splitting scales graph neural architecture search to billion-edge graphs in about 8 GPU hours.","lead":"SA-GNAS is a two-stage graph neural architecture search method that finds a good building-block cell by searching on a small sampled subgraph, then grows the cell by splitting its least stable nodes. It reports up to 8 GPU hours of search on a billion-edge graph, a 2.8x speedup over the prior GAUSS method, with accuracy gains on five benchmarks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Reported 8.46-GPU-hour search time on Papers100M is unverifiable because Algorithm 1 requires full-graph evaluations of K candidate architectures, and the paper never specifies the cost or training protocol for those evaluations, so the central efficiency claim may omit substantial compute.","rationale":"The reader's weakest_assumption focuses on the Kendall-tau seed-selection heuristic, which is indeed a heuristic without theoretical guarantee. However, the empirical ablations in Table VII do provide some support for that heuristic on five datasets, so I consider it less load-bearing than the search-time accounting. The reader's rationale also explicitly mentions 'potentially incomplete search-time accounting' and a 'GAUSS comparison that relies on numbers from another paper without a shared protocol,' which aligns with the concern I raise. I do not disagree with the Kendall-tau concern, but I think the more immediate threat to the paper's central claim is the ambiguity in what 'evaluate on the original graph' costs and whether the reported 8.46 GPU hours include all computation. This is a concrete, checkable issue: if the full-graph evaluations are cheap inference, the efficiency number may hold, but if they require training, the claim collapses. The paper's own Algorithm 1 makes this ambiguity material rather than cosmetic. My recommendation therefore does not change the reader's conditional acceptance, but it sharpens the condition: the authors must provide a runtime breakdown and the exact evaluation protocol for Algorithm 1. The GAUSS comparison, while a limitation, is secondary because the paper discloses it; the internal accounting issue is more damaging because it threatens the credibility of the reported number even in isolation.","tokens_in":23248,"tokens_out":7607,"duration_ms":76037,"concrete_test":"Instrument the released public code and rerun the full two-stage search on ogbn-papers100M with the reported hyperparameters, logging GPU-hours separately for: (i) the K=9 differentiable architecture searches on subgraphs, (ii) the K full-graph evaluations in Algorithm 1 (distinguishing training from inference), and (iii) the architecture/subgraph expansion stage. If the sum of logged components exceeds 8.46 GPU-hours, or if component (ii) involves full-graph training whose cost is non-negligible, the reported search-time claim is incomplete and the 2.8x speedup over GAUSS is not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline efficiency claim is the 2.8x speedup over GAUSS and the 8.46-GPU-hour search cost on ogbn-papers100M (Table V). The search pipeline in Algorithm 1 includes, at line 8, 'evaluate all candidate architectures in A on the original graph' to build the performance sequence P used for Kendall-tau matching. For Papers100M, Table III sets K=9 sampled subgraphs, so this entails 9 evaluations on a 111M-node, 1.6B-edge graph. The paper does not state whether these evaluations involve training each architecture from scratch on the full graph, fine-tuning subgraph-trained weights, or only inference on a validation subset. If full-graph training is required, 9 such runs alone would likely exceed the reported 8.46 GPU hours, making the search-time number implausible. If instead the evaluations use subgraph-trained weights and only run validation inference on the full graph, the performance ranking P is not based on models trained on the original graph, weakening the justification for selecting the seed architecture via ranking consistency. The paper also adopts GAUSS's reported ~24 GPU hours from the original paper without a shared hardware/protocol baseline, compounding the uncertainty. Without a component-wise runtime breakdown or a precise evaluation protocol, the central efficiency claim cannot be confirmed from the manuscript.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes SA-GNAS, a two-stage graph neural architecture search method for large-scale graphs. In the first stage, K subgraphs are sampled from the original graph via GraphSAINT, a differentiable cell-based architecture search is run independently on each subgraph, and the resulting K candidate architectures are then evaluated on all subgraphs and on the original graph. A weighted Kendall tau coefficient (Eq. 6) ranks the consistency between each subgraph's performance sequence and the original graph's performance sequence, and the architecture searched on the most consistent subgraph is selected as the seed architecture. In the second stage, the seed architecture is iteratively expanded by splitting the highest-entropy intermediate node and running a localized differentiable search with an entropy regularization term, while the seed subgraph is expanded by adding 1-hop neighbors. Experiments on five datasets (CS, Physics, ogbn-arxiv, ogbn-products, ogbn-papers100M) report accuracy improvements over human-designed GNNs and existing GNAS methods, and a search cost of 8.46 GPU hours on the 111M-node, 1.6B-edge ogbn-papers100M, claimed to be a 2.8x speedup over GAUSS. The code is made publicly available.","tokens_in":23493,"tokens_out":5050,"duration_ms":53642,"significance":"If the reported results hold, SA-GNAS would be a meaningful step toward practical GNAS on billion-edge graphs: it demonstrates that a two-stage subgraph-proxy search followed by entropy-guided architecture expansion can find architectures that outperform both hand-crafted GNNs and prior GNAS methods on five public benchmarks, with one of the first reported sub-10-GPU-hour searches on ogbn-papers100M. The paper also provides useful ablations (seed selection strategies, expansion strategies, sampling methods), hyperparameter sensitivity studies, and a parallelization analysis. A notable strength is the public code release, which supports reproducibility of the SA-GNAS pipeline itself. The main weakness is that the central efficiency claim, especially the 2.8x speedup and the 8.46-hour figure, rests on an under-specified evaluation protocol and an uncontrolled comparison with the non-open-source GAUSS baseline.","major_comments":[{"comment":"The headline efficiency claim is not verifiable from the manuscript. Algorithm 1 requires 'evaluate all candidate architectures in A on the original graph' to construct the performance sequence P, and Table III sets K=9 for ogbn-products and ogbn-papers100M. The paper never states whether these nine full-graph evaluations involve training each architecture from scratch on the full graph, fine-tuning subgraph-trained weights, or only running validation inference with subgraph-trained models. If full-graph training is required, nine such runs on a 111M-node, 1.6B-edge graph would almost certainly dominate the reported 8.46 GPU hours, making that number implausible unless a very short training protocol is used. If instead subgraph-trained weights are used directly for full-graph validation, then the ranking P is not based on models trained on the original graph, which weakens the justification for using ranking consistency as a proxy. The authors must provide a component-wise runtime breakdown (subgraph search, per-architecture full-graph evaluation, expansion iterations) and specify the exact training/evaluation protocol, including epochs, batch sizes, and hardware, for each dataset.","section":"Section III-C2 / Algorithm 1 (line 8)"},{"comment":"The 2.8x speedup over GAUSS is an uncontrolled comparison. Section IV-A2 states that 'GAUSS is not open-source, we directly adopt the performance presented in the original paper [19]', and Table V lists GAUSS's search time as approximately 24 GPU hours, taken from the original paper. Because GAUSS was not re-run on the same Tesla V100 GPU, with the same training protocol, or using the same codebase, the reported speedup mixes hardware generations and implementation details. This is especially problematic because the absolute search-time numbers for the other baselines in Table V are also not accompanied by a description of how they were measured on the stated V100. The authors should either reproduce GAUSS under identical conditions, or explicitly re-frame the speedup as an approximate comparison across different reported settings and remove the implication of a controlled benchmark.","section":"Section IV-A2 / Table V"},{"comment":"The Kendall-tau-based seed selection is a heuristic whose validity is not established beyond the three ablated baselines in Table VII. The method assumes that a subgraph whose performance ranking of searched architectures best matches the full-graph ranking will also yield a final architecture that transfers well. While the ablation shows this criterion outperforms random selection, highest-validation-accuracy selection, and average-subgraph-accuracy selection on the five tested datasets, there is no evidence about when this proxy might fail, for example on graphs with very different train/validation distributions or non-stationary label shifts. This is not a fatal flaw, but the authors should temper the claim of 'most closely represents the characteristics of the original graph' and acknowledge that the selection criterion is an empirical heuristic.","section":"Section III-C2 / Equation (6)"}],"minor_comments":[{"comment":"The text says 'We initially set the number of intermediate nodes in the cell to 3', but Table III lists 6-8 intermediate nodes per cell for the different datasets. Please clarify whether the table reports the final cell size after expansion or the initial size before the expansion stage, and reconcile the discrepancy.","section":"Section IV-A3 / Table III"},{"comment":"Algorithm 2 (line 6) says it expands the seed subgraph using the graph sampler π(G), but Section III-D2 describes expanding the subgraph by randomly adding M 1-hop neighbors per node. These two descriptions should be unified so that the exact subgraph expansion mechanism is unambiguous.","section":"Section III-D2 / Algorithm 2"},{"comment":"There is a typo: 'rand-orders' should be 'rank-orders'. Also, near Equation (6), the phrase 'when they are concordant but the △-differences are disproportionate' is vague; please define what 'disproportionate' means quantitatively.","section":"Section III-C2"},{"comment":"The reference to 'Figure IX' in the text should be 'Table IX', since the entropy trajectories are displayed in a table, not a figure.","section":"Section IV-D2"},{"comment":"The header of Table X uses 'SA-NAS' in the method columns, but the paper's method is called SA-GNAS. Please correct this inconsistency.","section":"Table X"},{"comment":"Some axis labels contain duplicated or garbled tick labels (e.g., '1 1' in Figures 7(c)-(e), 8, and 9) and one panel is labeled 'Proucts' instead of 'Products'. These should be corrected for clarity.","section":"Figures 7-9"},{"comment":"Proposition 2 is presented as a formal statement, but the text immediately acknowledges it is based on an 'intuitive conjecture' and that it is only validated experimentally. Either provide formal assumptions under which the inequality provably holds, or relabel it as an empirical observation to avoid overclaiming.","section":"Section III-D3 / Proposition 2"}],"recommendation":"major_revision","confidential_remarks":"The paper is from a group with a track record in GNAS (e.g., PSP), and the experimental apparatus is generally solid with five datasets and multiple ablations. The central concern is that the efficiency claim, which is the main selling point, is not backed by a reproducible protocol for the full-graph evaluations in Algorithm 1 or a controlled comparison with GAUSS. In revision, I would expect a component-wise runtime breakdown and either a re-run of GAUSS under identical conditions or a clearly qualified speedup statement. If the authors cannot provide such evidence, the 2.8x speedup wording should be substantially softened. The 'Proposition 2' framing is also worth fixing as a minor matter of accuracy."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: SA-GNAS is a sensible two-stage GNAS framework that shows real, if modest, accuracy gains on large graphs and reports a big search-time reduction. The experiments are mostly careful. The main weakness is that the headline efficiency claim—8.46 GPU hours on Papers100M—depends on two things the paper doesn't fully pin down: the cost of the full-graph evaluations inside Algorithm 1, and the GAUSS comparison, which is adopted from the original paper with no shared protocol.\n\nWhat's actually new: the combination of Kendall-tau-based subgraph/architecture selection with entropy-guided node splitting for progressive cell expansion. The ingredients individually resemble existing ideas—subgraph-proxy search in EGAN and GAUSS, entropy-based discretization in SGAS—but I don't know of a prior method that puts them together in a two-stage seed-expansion loop. The paper also does the right empirical legwork: five datasets, five runs with mean and variance, ablations for both stages, hyperparameter sensitivity, compatibility with training tricks, and a code link. Accuracy improvements over GAUSS on ogbn-products and ogbn-papers100M are consistent if not huge (about 0.4 and 0.5 points), and a 2.8x speedup on a billion-edge graph would be practically meaningful if it holds.\n\nSoft spots in proportion. First and most important: the search-time accounting. Algorithm 1 evaluates all K searched architectures on the original graph. For Papers100M, K=9, and the paper never states whether those evaluations train from scratch, fine-tune subgraph-trained weights, or only run inductive inference on validation nodes. If they're full training runs, the 8.46-hour figure is implausible. If they're inference-only, the ranking P underlying the Kendall-tau match comes from models not trained on the full graph, which weakens the matching logic. The paper needs a component-wise runtime breakdown. This is the main thing a referee should ask for. Second, the GAUSS comparison uses numbers lifted from the original paper. No shared hardware or training protocol. That's a limitation, though perhaps unavoidable since GAUSS isn't open-source; still, it should be stated more prominently. Third, Proposition 2 is explicitly built on an unproven conjecture and is only validated empirically. Calling it a proposition overstates it. Minor, but it should be relabeled. Fourth, several hyperparameters—λ, M, the stopping condition Φ—are missing from the text. The code helps, but the manuscript should list them.\n\nNo circularity issue; the method is an empirical heuristic, not a derivation. Overall, I'd send this to a serious referee. The empirical core is credible and the efficiency claim is checkable if the authors provide the missing details. My recommendation: conditional acceptance with requests for a runtime breakdown and complete hyperparameter reporting.","headline":"SA-GNAS is a credible two-stage GNAS framework with solid experiments, but the headline 8.46-GPU-hour search time needs a runtime breakdown and a fairer GAUSS comparison before I'd trust it.","tokens_in":24081,"tokens_out":3624,"would_cite":true,"duration_ms":33200,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A two-stage seed-expansion search finds graph architectures that beat hand-designed GNNs on graphs up to 111 million nodes, in 8.46 GPU hours.","keywords":["graph neural architecture search","large-scale graphs","seed architecture expansion","weighted Kendall tau","entropy minimization","differentiable architecture search","graph sampling","node classification"],"falsifier":"Run SA-GNAS on a large heterophilic or class-imbalanced graph with its Kendall-tau seed selection and with random seed selection (Mrand) under the same expansion budget; if the Kendall-tau seed does not beat Mrand on full-graph test accuracy beyond run-to-run variance, the central transfer premise of the method is falsified.","tokens_in":22972,"feed_emoji":"🧬","tokens_out":7528,"duration_ms":70345,"temperature":0.7,"pith_summary":"This paper claims that graph neural architecture search can be made practical on graphs with billions of edges by splitting the search into two stages. First, several subgraphs are sampled and a differentiable search runs on each; the subgraph whose ranking of candidate architectures best matches the ranking on the full graph is picked as the seed, and its architecture becomes the seed architecture. Second, the seed architecture is expanded by repeatedly splitting the cell node with the highest operation entropy and searching only the local edges around the split, while the subgraph is also enlarged so the proxy keeps pace with the growing model. On five node-classification benchmarks, the method reports higher accuracy than human-designed GNNs and existing graph NAS methods, and on the largest graph it reduces search cost to about 8 GPU hours, a 2.8x speedup over the prior large-scale method.","feed_headline":"Graph architecture search hits billion-edge graphs in 8 GPU hours","feed_subtitle":"Two-stage seed expansion beats hand-built GNNs and prior graph NAS while cutting search cost on the largest benchmark.","key_machinery":"The load-bearing object is a cell-based micro search space in which each cell is a directed acyclic graph whose edges are candidate graph message-aggregation operations, softened into a continuous mixture exactly as in DARTS-style differentiable search. Two quantities drive the search: the weighted Kendall tau coefficient of Equation (6), which measures whether the ranking of candidate architectures on a sampled subgraph agrees with their ranking on the full graph and thereby selects the seed subgraph and seed architecture; and node entropy of Equation (10), defined as the average entropy of the operation distributions on a node's incoming edges, which identifies which node to split during expansion and acts as a regularizer in the localized bi-level search of Equation (13). The expansion stage also grows the seed subgraph by adding 1-hop neighbors, so the proxy data and the architecture complexity increase together.","core_discovery":"The paper's central claim is that searching a GNN architecture on a small sampled subgraph and then growing it in place is both faster and more accurate than searching the full large-scale graph directly. The discovery is a two-stage procedure: stage one samples several subgraphs, runs differentiable graph architecture search on each, forms a performance sequence for each subgraph and for the full graph, and picks the subgraph whose weighted Kendall tau against the full graph is highest, together with the architecture found on it, as the seed. Stage two repeatedly splits the seed cell's intermediate node with the highest node entropy (the average Shannon entropy of its incoming edge-operation distributions), searches only the local edges around the split, and grows the subgraph by adding 1-hop neighbors so the proxy keeps up with the model. The paper reports that on five OGB and co-authorship benchmarks the final architectures outperform human-designed GNNs and seven GNAS baselines, and that on the billion-edge ogbn-papers100M the search costs 8.46 GPU hours on one GPU, a 2.8x speedup over the prior large-scale GNAS method.","pith_inferences":["By extension, the weighted Kendall tau between proxy and full-graph performance rankings could serve as a reusable proxy-fidelity diagnostic for any subgraph-based training pipeline, not just architecture search.","The paper leaves untested whether entropy-guided node splitting acts as a general capacity-scheduling rule; a natural extension would apply the same expansion schedule to heterophilic graphs or link prediction, where sampled-neighborhood distributions differ.","The 2.8x speedup versus GAUSS inherits the experimental conditions of the GAUSS paper, since GAUSS is not open-source; an independent reimplementation under identical hardware and evaluation settings would be needed to confirm the comparison.","The ablation comparing ranking-consistency selection with random selection suggests a stress test: deliberately bias the sampling distribution so subgraph and full-graph rankings diverge, and check whether Kendall-tau selection degrades toward random selection as predicted."],"forward_implications":["The reported results imply that large-scale graph architecture search no longer requires day-long GPU runs: on the five tested datasets the search finishes in 0.043 to 8.46 GPU hours on a single V100.","Because the K subgraph searches in the seed-selection stage are independent, the wall-clock cost divides almost evenly across GPUs; the paper reports 2.31 GPU hours on four GPUs for ogbn-papers100M.","The final architectures differ across datasets and mix several aggregators, supporting the paper's claim that automatic search is necessary because no single hand-designed GNN dominates.","The reported monotone decrease of cell entropy during expansion is presented as evidence that splitting high-entropy nodes yields progressively more stable architectures, which is the basis for Proposition 2."],"supporting_citations":[{"why":"Supplies the differentiable relaxation of discrete operations into a continuous softmax mixture; both the seed search and the localized expansion search optimize the same bi-level objective.","marker":"[34]"},{"why":"Graph sampling method whose unbiased aggregation property is cited to justify that sampled subgraphs are low-bias proxies for the original graph.","marker":"[23]"},{"why":"GAUSS, the previous large-scale GNAS method; its reported accuracy and roughly 24 GPU-hour search cost on ogbn-papers100M are the baselines for the 2.8x speedup and accuracy comparisons.","marker":"[19]"},{"why":"Open Graph Benchmark source of the three ogbn datasets (arxiv, products, papers100M) used to evaluate scalability and performance.","marker":"[20]"},{"why":"Provide the definition and properties of the weighted Kendall tau coefficient used in Equation (6) for performance-ranking-consistency-based seed selection.","marker":"[68]–[70]"},{"why":"SGAS cell-based micro search space with greedy discretization, which the paper's cell design and search space closely follow.","marker":"[59]"},{"why":"EGAN, the sampling-based GNAS method said to suffer performance consistency collapse on large graphs; it serves as both a motivating problem and a baseline.","marker":"[25]"},{"why":"Cluster-GCN sampling baseline used in the ablation that compares subgraph sampling strategies and shows GraphSAINT's advantage.","marker":"[22]"}],"fun_headline_variants":["Seed expansion makes graph NAS 2.8x faster on billion-edge graphs","2.8x speedup in graph NAS via seed expansion on billion-edge graphs","Grow a seed architecture to search billion-edge graphs efficiently","Seed expansion searches billion-edge graphs in 8 GPU hours"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method assumes that the ranking of candidate architectures on a sampled subgraph, compared with their ranking on the full graph, reliably identifies a seed architecture whose quality transfers to the full graph; this empirical heuristic has no theoretical guarantee and could degrade on graphs whose sampled subgraphs are not representative.","fun_headline_variants_meta":{"raw":{"variants":["Seed expansion makes graph NAS 2.8x faster on billion-edge graphs","2.8x speedup in graph NAS via seed expansion on billion-edge graphs","Grow a seed architecture to search billion-edge graphs efficiently","Seed expansion searches billion-edge graphs in 8 GPU hours"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000545,"raw_usage":{"total_tokens":2656,"prompt_tokens":1042,"completion_tokens":1614,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":658,"completion_tokens_details":{"reasoning_tokens":1538}},"tokens_in":658,"tokens_out":1614,"duration_ms":10720,"temperature":1.0,"reasoning_tokens":1538,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T23:44:07.355192+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run SA-GNAS on a large heterophilic or class-imbalanced graph with its Kendall-tau seed selection and with random seed selection (Mrand) under the same expansion budget; if the Kendall-tau seed does not beat Mrand on full-graph test accuracy beyond run-to-run variance, the central transfer premise of the method is falsified.","supporting_citations":[{"cited_title":"Darts: Differentiable architecture search,","cited_arxiv_id":null,"evidence_quote":"Supplies the differentiable relaxation of discrete operations into a continuous softmax mixture; both the seed search and the localized expansion search optimize the same bi-level objective."},{"cited_title":"Graph- saint: Graph sampling based inductive learning method,","cited_arxiv_id":null,"evidence_quote":"Graph sampling method whose unbiased aggregation property is cited to justify that sampled subgraphs are low-bias proxies for the original graph."},{"cited_title":"Large-scale graph neural architecture search,","cited_arxiv_id":null,"evidence_quote":"GAUSS, the previous large-scale GNAS method; its reported accuracy and roughly 24 GPU-hour search cost on ogbn-papers100M are the baselines for the 2.8x speedup and accuracy comparisons."},{"cited_title":"Open graph benchmark: Datasets for machine learning on graphs,","cited_arxiv_id":null,"evidence_quote":"Open Graph Benchmark source of the three ogbn datasets (arxiv, products, papers100M) used to evaluate scalability and performance."},{"cited_title":"Sgas: Sequential greedy architecture search,","cited_arxiv_id":null,"evidence_quote":"SGAS cell-based micro search space with greedy discretization, which the paper's cell design and search space closely follow."},{"cited_title":"Efficient graph neural architecture search,","cited_arxiv_id":null,"evidence_quote":"EGAN, the sampling-based GNAS method said to suffer performance consistency collapse on large graphs; it serves as both a motivating problem and a baseline."}],"review_version":1}