{"id":"9daea13f-61bf-48fd-b3d0-3deee66ec3b5","arxiv_id":"2506.15709","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Directly predicting motif significance-profiles with message-passing GNNs is feasible but imprecise, and multi-target direct regression outperforms count-then-score in the paper's experiments.","lead":"This paper tests whether graph neural networks can predict the statistical significance of small network motifs directly, instead of first counting motifs. The networks are too imprecise for exact motif scores, but they can roughly identify which random process generated a network, and they run far faster than exact counting.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The count-then-score baseline in Table 4 is an analytic approximation of Z-scores, not an actual count-and-control-graph pipeline; if that approximation understates count-model error, the claimed advantage of direct SP estimation collapses.","rationale":"The reader's weakest assumption identified this exact issue, and I agree. The paper's strongest claim is that direct SP prediction is a viable fast surrogate, with stability and accuracy advantages over count-then-score. The evidence for this is Table 4. The expressivity argument in §3.2 is explicitly speculative ('we might have made the problem easier...'), and the real-world generator-matching results (§6.3) are interesting but not the main quantitative claim. So Table 4 is load-bearing. The approximation in §6.2 is not derived, mixes training error with null-model variability, and is applied to out-of-distribution real-world graphs; it cannot validate the count baseline. That said, the paper has real strengths: a large synthetic dataset, honest reporting of poor intra-generator prediction, and a plausible reformulation. The fix is straightforward—run the actual pipeline on a subset. If the result still favors direct SP, the paper's central claim is strengthened; if not, the quantitative advantage claim must be withdrawn or qualified. Therefore I recommend keeping the reader's CONDITIONAL verdict: the paper should not be accepted as-is until Table 4 is replaced or re-derived.","tokens_in":23980,"tokens_out":4344,"duration_ms":47357,"concrete_test":"Run the actual count-then-score pipeline on a representative subset of the real-world networks from Table 4 (e.g., 20 small-scale and 20 medium-large networks). Train the count model on the same ND synthetic split. For each test graph, generate 100–500 degree-preserving rewired control graphs, obtain predicted counts for the graph and controls, compute Z-scores, normalize as in §3.1, and compute absolute errors. Compare error percentiles (25/50/75%) with the direct SP model. If the actual count errors are no larger than the approximate values, the approximation was conservative and the claim stands; if they are larger, or if direct SP no longer wins by the reported margins, the Table 4 advantage is not supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 6.2 validates the central advantage claim (direct SP beats count-then-score) using Table 4, but the count baseline is not a real pipeline. Instead of generating control graphs and counting, the authors approximate the Z-score by 'decomposing' the count variable into actual frequency y and model error z, and use a formula (y − E[y]) ± σz / (Var(y)^2 + Var(z)^2)^1/2. This conflates the count model's prediction error (measured on the training distribution) with the deviation of counts under a degree-preserving null model. A Z-score requires the distribution of counts over control graphs, not the model's training error. Real-world graphs are out-of-distribution; there is no reason the training error distribution for z approximates the count model's errors on the real-world test set, nor does it capture the null-model count variance. The formula is not derived, and taking the minimum over 'all valid signal combinations' only optimizes the sign, not the magnitude. Consequently Table 4 does not establish that direct SP estimation is more accurate than an actual count-then-score baseline; the reported 50–90% error reductions could be an artifact of an overly favorable approximation.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a reformulation of network motif estimation as direct multi-target regression of normalized significance profiles (SPs), rather than first counting subgraph frequencies and then computing Z-scores against a null model. Using a large synthetic dataset from 23 graph generators and a collection of 115 real-world networks, with ground-truth SPs computed by G-Tries, the authors train MPNNs (GIN, GAT, GraphSage, GCN) and report: multi-target regression generally beats single-target training; direct SP estimation yields lower error than a count-based baseline (Table 4); models can distinguish synthetic generators and match some real-world networks to synthetic generators; and inference is orders of magnitude faster than G-Tries. The paper also argues that direct SP estimation may circumvent expressivity limits of subgraph-counting GNNs.","tokens_in":24231,"tokens_out":7909,"duration_ms":86780,"significance":"If the main empirical claims hold, the work provides a scalable surrogate for motif analysis and a new benchmark task for GNNs, supported by a substantial synthetic dataset with SP ground truths and reproducible code. The multi-target formulation and the explicit link to null-model-based significance are conceptually clean. However, the central advantage over count-then-score is not yet established because the comparison baseline is an unvalidated approximation, and the stability claim lacks supporting measurements; these issues need to be addressed before the contribution is fully supported.","major_comments":[{"comment":"The Table 4 comparison is load-bearing for the paper's central claim that direct SP estimation outperforms count-then-score, but the count baseline is an analytic approximation, not an actual pipeline. The authors approximate the Z-score that would be obtained from subgraph estimation by decomposing the frequency variable into actual frequency y and model error z and using (y − E[y]) ± σz / sqrt(Var(y)^2 + Var(z)^2). This assumes that the count model's training-error distribution can stand in for the distribution of counts over degree-preserving control graphs, which is the distribution a true Z-score requires. No derivation or validation of this approximation is given, and for real-world test graphs—which are out-of-distribution—there is no reason the training error variance should match null-model count variance. The minimum over signal combinations only fixes sign ambiguities, not the magnitude of the error. Consequently, the reported 50–90% error reductions in Table 4 do not establish that direct SP estimation is more accurate than a genuine count-then-score method. The authors should either implement the real baseline (generate control graphs and compute Z-scores from counts) or, if an approximation is retained, validate it against exact Z-scores on a hold-out subset and report that validation.","section":"Section 6.2, Table 4"},{"comment":"The stability claim—'the model remains stable, with errors increasing by at most ≈ 20% as networks scales up to 1000 times the train size'—is stated without any supporting measurements. No figure or table reports prediction error as a function of the ratio between test and training network size, and the source of the 20% figure is not identified. Since stability under out-of-distribution network sizes is one of the paper's key contributions (Introduction point 5), this claim needs direct evidence, such as error percentiles for real-world networks binned by node/edge count relative to the training distribution, or a plot of error versus size multiplier.","section":"Section 6.3"},{"comment":"The claim that the models can 'help identify the closest synthetic model for real networks based on significance-profiles' is supported only by three hand-selected examples (ia-escorts-dynamic, coauthor-CS, ia-primary-school-proximity) plus an unspecified reference to 'other correct matches.' No systematic evaluation is provided: the paper does not report the predicted nearest synthetic generator for all real-world networks, nor does it compare against a trivial baseline (e.g., matching by size or degree distribution). As it stands, this generalisation claim is anecdotal and should either be quantified or explicitly presented as a qualitative observation.","section":"Section 6.3"}],"minor_comments":[{"comment":"The tool is referred to as 'Gtrie', 'G-Trie', and 'G-tries' inconsistently; please unify the terminology.","section":"Section 6.4, Appendix A"},{"comment":"'This first study on GNN-based motif estimation' is overstated given the related works cited in Section 2.4 (e.g., SPMiner, MICRO-Graph, MotiFiesta); suggest 'the first benchmark for direct significance-profile prediction' or similar.","section":"Abstract"},{"comment":"The conclusion that multi-target regression is generally superior is not fully supported by the percentile table, since several entries show increased error for the multi-target model (e.g., rows at 100% and 50% for some graph types); consider reporting aggregate metrics or a paired significance test.","section":"Table 3"},{"comment":"The sentence 'Assuming that the difference between a value z ∼ z and µz is proportional to σz' is unclear as written; please rewrite to define z, µz, and σz explicitly.","section":"Section 6.2"},{"comment":"'Networks of of paper citations' contains a duplicated word.","section":"Appendix A.4"},{"comment":"In the normalization formula, the denominator is defined as the norm over the group Ω(i); consider clarifying that groups are the size-three and size-four subsets of Ω, and that the formula assumes the group is non-empty.","section":"Section 3.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript would benefit from a more careful framing of the contribution relative to existing motif-mining GNNs, and from toning down the 'first study' claim. The dataset and code release are valuable; if the authors can supply a proper count-then-score baseline and stability measurements, the paper's claims would be substantially stronger."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about arXiv:2506.15709. First, it does formulate something new: predicting normalized significance profiles over eight small connected motifs via multi-target regression, rather than estimating subgraph counts and then computing Z-scores. That framing is clean and could be a useful benchmark. Second, its central empirical claim—that direct SP estimation beats count-then-score—is not actually established, because the count baseline is an analytic approximation, not a real pipeline.\n\nWhat's good: the authors release a large synthetic dataset (23 generators, ~110k non-deterministic graphs plus 38.4k deterministic ones), and their negative result that 1-WL-limited models struggle at precise SP prediction is honestly reported and consistent with the tables. The observation that models can still match real-world networks to the right synthetic generator at the profile level is suggestive and worth following up. The speedups over exact G-Trie counting are real and expected—getting 10^5-10^6x by replacing a combinatorial algorithm with a forward pass is unsurprising, but the comparison is not misleading.\n\nThe soft spots are real. Section 6.2's count-baseline comparison (Table 4) is the load-bearing evidence for the advantage claim, and it is not a count-then-score pipeline. Instead of generating control graphs and counting, the authors approximate the Z-score by decomposing the count variable into actual frequency and model error, using a formula that is never derived and mixes training-set error with null-model variance. Taking the minimum over sign combinations doesn't fix magnitude problems. If that approximation is optimistic, the claimed 50-90% error reductions collapse. Section 6.3 also states, without supporting measurements, that error grows at most ~20% when graphs are 1000x larger; that stability claim needs an actual plot or table. And there are no error bars across random seeds for any of the headline numbers.\n\nMy take: the reformulation is plausible and worth engaging, but the advantage claim is unproven. The paper deserves a serious referee, but a revision needs to run a real count-then-score baseline on at least a subset of test graphs, report seed variance, and support the stability claim with data. I'd bring it to reading group to discuss the formulation, and I'd cite it if I worked on motif estimation or GNN expressivity. Serious thinker: yes—the reasoning is coherent and limitations are acknowledged; the flaws are in evidence, not in logic.","headline":"A genuinely new task formulation (direct SP regression) with an honest negative result, but the central quantitative comparison is built on an unvalidated approximation and needs repair.","tokens_in":24781,"tokens_out":3567,"would_cite":true,"duration_ms":40572,"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":"The paper argues that motif significance can be predicted directly as a multi-target regression of normalized Z-scores, decoupling motif analysis from subgraph counting and thereby escaping the expressivity limits that bound count-based…","keywords":["graph neural networks","network motifs","significance profiles","multi-target regression","subgraph counting","1-WL expressivity","network categorization","synthetic graph generators"],"falsifier":"Take a held-out real network, predict its SP directly, and also predict subgraph frequencies with a count-trained GNN; then generate actual degree-preserving rewired control graphs, count the eight patterns in them, and compute the true Z-scores. If the true count-based Z-scores agree with the direct SP predictions as well as or better than the training-error approximation in Table 4, the central claim of direct-estimation superiority is not supported.","tokens_in":1938,"feed_emoji":"🧩","tokens_out":2478,"duration_ms":137543,"temperature":0.7,"pith_summary":"This paper tries to establish that network motif analysis does not have to start from subgraph counting. The authors propose predicting the significance-profile of a graph directly: a vector of normalized Z-scores for all connected three- and four-node subgraphs, computed against a degree-preserving rewiring null model, learned as one multi-target regression by a message-passing GNN. Trained on a large synthetic corpus built from 23 graph generators and tested on more than 100 real networks, the model stays stable when network size grows to around 1000 times the training scale. If the claim is right, motif discovery becomes a fast, interpretable, single-pass surrogate that can run on very large graphs and that is not automatically bound by the known result that 1-WL-limited GNNs cannot count induced patterns of three or more nodes.","feed_headline":"Motif scores predicted directly, skipping subgraph counting","feed_subtitle":"Direct Z-score prediction stays stable at 1000x training size and reveals each network's generator.","key_machinery":"The machinery is the significance-profile vector s = (s_1,...,s_8) with s_i = z_i / (sum_{j in $\\Omega$(i)} $z_j^{2}$)^(1/2), where z_i is the Z-score of induced occurrences of pattern H_i under a degree-preserving rewiring null model and $\\Omega$(i) is the size group (three or four nodes). Normalization confines each profile to [-1,1], makes scores comparable across graph sizes, and imposes sum_i $s_i^{2}$ = 1 inside each group, which couples the targets and makes multi-task regression natural. The second load-bearing relation is the conservation law for size-three patterns: the induced 3-path count is the degree-sequence-determined count minus three times the triangle count, so the 3-path and triangle Z-scores are symmetric and size-four profiles are partly encoded in size-three profiles. The architecture is a standard MPNN with global addition pooling and an MLP head; among the backbones tried, GIN and SAGE performed best.","core_discovery":"The paper's central claim is that significance-profile estimation is a task in its own right and can be decoupled from frequency counting. Concretely, instead of predicting C(H,G) and then deriving significance, the model outputs the normalized profile s_i = z_i / (sum_{j in $\\Omega$(i)} $z_j^{2}$)^(1/2) for the eight connected graphs with three or four nodes, treating the whole vector as a single regression target. The experiments report three main results: multi-target regression generally beats training one model per subgraph; direct SP prediction beats a count-then-score pipeline on real-world graphs; and models with expressivity bounded by 1-WL, despite failing at precise intra-generator SP estimation, can match a real network to its closest synthetic generator through its predicted profile, with error growing by at most about 20% at 1000x out-of-distribution scale. The interpretive consequence the authors draw is that choosing a null model changes the difficulty of motif estimation, so expressivity lower bounds proved for subgraph counting need not transfer to significance-profile estimation.","pith_inferences":["A natural next experiment the paper does not run is to sweep null models, from the trivial null that always returns zero to a fully random one, and map where 1-WL models start to fail; that map would test the paper's claim that expressivity bounds depend on the null model.","The reported stability at 1000x size suggests a practical screening pipeline: train once on synthetic graphs, run direct SP prediction on very large real networks, and reserve exact counting for networks whose predicted profiles fall near motif boundaries.","Because the 3-path and triangle scores are algebraically tied under the configuration model, a two-scalar or even one-scalar target could replace the size-three block of the regression, potentially improving precision while reducing model size.","The real-world generator-matching results imply a lightweight network-similarity heuristic: compare predicted profiles to generator-typical profiles rather than to exact ground truth, which can label unfamiliar networks with a candidate generative process."],"forward_implications":["Direct SP estimation removes the need to generate control graphs at inference time; the paper reports speedups over the exact counting data structure of roughly 1.6 million on medium-large real networks and large core-efficiency gains.","Because profiles are normalized, predicted motif scores can be compared across networks of different sizes, enabling downstream uses such as grouping or screening networks.","The same model can serve as a network categorizer: even when precise profile values are off, the predicted profile points to the synthetic generator whose graphs most resemble the input network.","The conceptual decoupling means future motif estimators do not have to beat subgraph-counting expressivity bounds; they only need to approximate the significance-profile under a chosen null model.","The size-three conservation law implies that predicting one of the 3-path/triangle pair largely determines the other, so the regression target has hidden redundancy that could be exploited for efficiency."],"supporting_citations":[{"why":"Defines network motifs and the degree-preserving rewiring null model that the paper uses to compute Z-scores and to frame the task.","marker":"[Milo et al., 2004b]"},{"why":"Introduces significance profiles and the within-group L2 normalization that the paper adopts as its regression target.","marker":"[Milo et al., 2004a]"},{"why":"Proves that 1-WL-limited MPNNs cannot count induced patterns of three or more nodes, the expressivity bound the paper argues direct SP estimation can bypass.","marker":"[Chen et al., 2020]"},{"why":"Gives the k-WL dimensionality results for induced subgraph counting that ground the paper's expressivity discussion.","marker":"[Lanzinger and Barceló, 2023]"},{"why":"Provides the exact counting data structure used to compute ground-truth significance profiles for the synthetic and real datasets.","marker":"[Ribeiro and Silva, 2013]"},{"why":"Surveys subgraph-counting algorithms and motivates the intractability claim that argues for an ML-based estimation shortcut.","marker":"[Ribeiro et al., 2021]"},{"why":"Establishes correlations in randomization that the paper extends to show 3-path and triangle Z-scores are interdependent under the configuration model.","marker":"[Ginoza and Mugler, 2010]"},{"why":"States the conservation law for induced 3-paths as the number of degree-sequence-determined paths minus three times the triangle count.","marker":"[Wegner, 2014]"},{"why":"Classical result that 1-WL distinguishes random graphs with high probability, used to interpret the model's inter-generator prediction success.","marker":"[Babai and Kucera, 1979]"},{"why":"Analysis of GNN expressivity and global pooling that supports the choice of GIN backbone and add-pooling.","marker":"[Xu et al., 2019]"}],"fun_headline_variants":["Motif profiles predicted directly, no counting needed","GNNs learn motif significance profiles directly","Stable motif profiles at 1000x scale via direct SP","Direct SP estimation outscores count-then-score baselines","From motif counts to profiles: a direct GNN approach"],"cache_read_input_tokens":26880,"weakest_assumption_plain":"The load-bearing premise is that the comparison against the count-based approach is fair even though the paper approximates what that approach's standardized significance scores would be from its training error, rather than actually generating rewired control graphs and counting motifs in them; the comparison also assumes the synthetic training graphs are varied enough to represent real networks, and if either assumption fails the reported advantage of direct scoring over count-then-score weakens or disappears.","fun_headline_variants_meta":{"raw":{"variants":["Motif profiles predicted directly, no counting needed","GNNs learn motif significance profiles directly","Stable motif profiles at 1000x scale via direct SP","Direct SP estimation outscores count-then-score baselines","From motif counts to profiles: a direct GNN approach"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000229,"raw_usage":{"total_tokens":1473,"prompt_tokens":931,"completion_tokens":542,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":547,"completion_tokens_details":{"reasoning_tokens":464}},"tokens_in":547,"tokens_out":542,"duration_ms":6832,"temperature":1.0,"reasoning_tokens":464,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:16:14.356122+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a held-out real network, predict its SP directly, and also predict subgraph frequencies with a count-trained GNN; then generate actual degree-preserving rewired control graphs, count the eight patterns in them, and compute the true Z-scores. If the true count-based Z-scores agree with the direct SP predictions as well as or better than the training-error approximation in Table 4, the central claim of direct-estimation superiority is not supported.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Proves that 1-WL-limited MPNNs cannot count induced patterns of three or more nodes, the expressivity bound the paper argues direct SP estimation can bypass."},{"cited_title":"and Barceló, P","cited_arxiv_id":null,"evidence_quote":"Gives the k-WL dimensionality results for induced subgraph counting that ground the paper's expressivity discussion."},{"cited_title":"and Silva, F","cited_arxiv_id":null,"evidence_quote":"Provides the exact counting data structure used to compute ground-truth significance profiles for the synthetic and real datasets."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Surveys subgraph-counting algorithms and motivates the intractability claim that argues for an ML-based estimation shortcut."},{"cited_title":"and Mugler, A","cited_arxiv_id":null,"evidence_quote":"Establishes correlations in randomization that the paper extends to show 3-path and triangle Z-scores are interdependent under the configuration model."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States the conservation law for induced 3-paths as the number of degree-sequence-determined paths minus three times the triangle count."},{"cited_title":"and Kucera, L","cited_arxiv_id":null,"evidence_quote":"Classical result that 1-WL distinguishes random graphs with high probability, used to interpret the model's inter-generator prediction success."}],"review_version":1}