{"id":"4f979927-cd5f-41ff-bc47-39eb59649932","arxiv_id":"2507.00039","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"In a benchmark of eight graph datasets, the measures AbsSupDif and Sup rank discriminative subgraphs best, while widely used measures such as GR, Acc, and InfGain perform worse, and footprint-based clustering reduces the number of patterns with comparable F1.","lead":"This paper compares 38 scoring formulas used to pick the most informative subgraph patterns for classifying graphs, and shows a clustering step can shrink the pattern set without hurting accuracy. A reader would use it to choose which pattern-quality measure to trust and to cut computational cost in graph classification pipelines.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No train/test split or cross-validation is described; the F1-based comparisons supporting the main recommendations may be in-sample estimates.","rationale":"The reader's weakest assumption was the SAGE/LossSHAP gold standard, which is reasonable but not the most load-bearing issue: the ranking comparisons in Section 6.4.1 depend on it, but the main conclusion that AbsSupDif and Sup are safe choices and that GR/Acc/InfGain are less relevant is drawn primarily from the F1-score curves in Figure 11, which do not require the gold standard. The more serious problem is that no evaluation protocol is described for those F1 curves. If the classifier is evaluated on the same graphs it was trained on, the performance numbers are in-sample and cannot support any ranking of measures. The clustering-threshold selection on the same curves compounds this. Because the paper does release code, the concern is empirically checkable; if the repository contains proper cross-validation, the objection does not land. This keeps the verdict CONDITIONAL, but shifts the primary reason from gold-standard validity to missing train/test separation.","tokens_in":47271,"tokens_out":4986,"duration_ms":55665,"concrete_test":"Open the released repository (github.com/CompNet/gpQualMeasComp) and run the classification experiments in Figures 8 and 11 under stratified 10-fold cross-validation with the same SVM and thresholds; if the relative F1 ordering of AbsSupDif/Sup versus GR/Acc/InfGain changes across datasets, or the margins are within run-to-run variance, the paper's recommendations are not supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing problem is not the SAGE approximation but the absence of any described evaluation protocol for the F1-score comparisons. Sections 6.2.3 and 6.4.2 state that the authors 'train a classifier' and 'compute the classification performance' after building vector representations, but neither Section 6.1 nor Section 5.3 specifies a train/test split, cross-validation, repeated runs, or error bars. Under a literal reading, the F1 curves in Figures 8 and 11 and the subsequent comparison of AbsSupDif/Sup versus GR/Acc/InfGain are computed on the same graphs used for training. If so, the F1 values reflect overfitting and the measure ordering cannot be interpreted. Even if the code silently performs cross-validation, the manuscript text is insufficient to support the central empirical claim. Additionally, the clustering threshold is selected per dataset from these same F1 curves (Section 6.2.3) and then reused for the ranking comparisons and the gold standard comparison; without a nested or independent validation, the reported benefit of clustering is at risk of selection bias.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a comparative study of 38 quality measures for pattern-based graph classification. It introduces four theoretical properties (Contrastivity, Jumpiness, Class Symmetry, Pattern Symmetry), proposes a clustering-based preprocessing step that groups patterns with similar footprints, and constructs a gold standard ranking from Shapley-value-based importance scores. The measures are evaluated on eight public graph datasets by comparing their rankings with the gold standard (using Kendall's Tau and Rank-Biased Overlap) and by measuring F1-score when the top-ranked patterns are used as features for an SVM classifier. The main claims are that AbsSupDif and Sup are safe choices across datasets, that popular measures such as GR, Acc, and InfGain are comparatively less effective, and that the clustering preprocessing reduces the number of patterns while maintaining or improving classification performance.","tokens_in":47462,"tokens_out":6601,"duration_ms":70482,"significance":"If the empirical claims were fully supported, the paper would provide a useful reference for practitioners choosing quality measures for subgraph-based classification, and the clustering preprocessing idea is sensible and potentially valuable. The theoretical characterization through four properties is a genuine contribution, and the public release of code, datasets, and experimental results is a strength that aids reproducibility. However, the central F1-based conclusions currently rest on an underspecified and potentially in-sample evaluation protocol, and the gold standard used for ranking comparisons is itself an approximation whose validity is not established. These issues must be resolved before the recommendations can be accepted as reliable.","major_comments":[{"comment":"No train/test split, cross-validation, repeated runs, or error bars are described for any of the F1-based evaluations. Section 6.2.3 states that the authors 'train a classifier' and 'assess its classification performance with the F1-Score', and Section 6.4.2 similarly says that the authors 'train the classifier and compute the classification performance', but neither section nor Section 6.1 specifies which graphs are used for training and which for testing. Under a literal reading, the F1 curves in Figures 8 and 11 are computed on the same graphs used for training. If so, the ordering of measures in Section 6.4.2 and the conclusion that AbsSupDif and Sup are safe choices while GR and Acc are less relevant cannot be interpreted as predictive performance. Even if the released code performs cross-validation, the manuscript must state the protocol explicitly and report variance across runs.","section":"Section 6.1, 6.2.3, 6.4.2"},{"comment":"The per-dataset clustering threshold is selected from the very same F1 curves that are later used to evaluate the clustering benefit and the quality measures. In Section 6.2.3, the vertical dotted lines in Figure 8 are chosen as the 'best trade-off' between minimizing the number of representatives and maximizing classification performance; these thresholds are then reused for the ranking comparisons in Section 6.3 and the gold standard comparison in Section 6.4. Selecting a parameter on the evaluation data creates a selection bias that can inflate the apparent benefit of clustering and can distort the subsequent comparisons between measures. A nested or independent validation scheme is needed to support the conclusions.","section":"Section 6.2.3, 6.3, 6.4"},{"comment":"The gold standard used throughout Section 6.4 is described as based on the Shapley Value via SAGE, but the actual implementation uses LossSHAP, which the paper states 'only provides a local version of SAGE' and is averaged over all patterns to obtain global scores. Averaging local SHAP values over data points is not equivalent to computing SAGE values, which are defined globally with respect to the model loss. The validity of the RBO comparisons and the claim that AbsSupDif and Sup are close to the gold standard depends on this approximation. The paper itself notes in Appendix D.2 that Dep outperforms the gold standard on IMDb, indicating that the gold standard is imperfect. The authors should either compute genuine SAGE values or explicitly justify and quantify the error introduced by the local approximation.","section":"Section 5.2.1, Section 6.1, Appendix D.2"},{"comment":"The Rank-Biased Overlap is defined in Eq. (3) as an infinite sum, and the text states that 'in our case' the upper bound is s, but no finite-list correction or normalization is provided. With the truncated sum, the maximum possible RBO when both rankings are identical at all depths s is 1-p^s, not 1, so the upper bound depends on s. This means the increasing RBO curves in Figure 10 may be partly a mechanical consequence of the truncation. In addition, the value of the parameter p is never specified in Section 6.1, even though it controls the top-weighting and therefore directly affects the numerical comparisons. The authors should state the chosen p, use a proper finite-list variant of RBO, and report sensitivity to p.","section":"Section 5.2.2, Eq. (3)"}],"minor_comments":[{"comment":"The conclusion cites InfGain as originating from [85], but in Table 2 InfGain is attributed to [18]; the reference should be corrected.","section":"Section 7"},{"comment":"The text refers to 'Figure 6.3 from Section 9' when discussing the minimum Kendall's Tau matrix; this should be Figure 9 from Section 6.3.","section":"Appendix B.2"},{"comment":"The sentence 'This choice allows us to focus on the impact of the clustering process on classification, rather than on rather than on the nature of the classifier' contains a duplicated phrase and should be rewritten.","section":"Section 6.2.3"},{"comment":"The conclusion states that the authors 'also show empirically that restricting pattern mining to specific types of patterns, such as induced or closed ones, also results in a smaller selection of patterns for equal performance', but no such experiments are presented in Section 6 or in the appendices; this claim should be removed or supported with results.","section":"Section 7"},{"comment":"The introductory sentence says that 'Figures 15 and 16 show the F1-Score' for each measure, but those figures display RBO values; the F1-Score plots are Figures 17 and 18 and the cross-reference should be fixed.","section":"Appendix C.2"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nShort version: this is one of the more useful papers on quality measures for pattern-based graph classification, but its headline recommendations rely on an evaluation protocol that is not described. Before the AbsSupDif/Sup result becomes a default, the authors need to show that the F1 comparisons are not in-sample.\n\nWhat's genuinely new: the first systematic comparison of 38 quality measures on graph patterns rather than tabular itemsets, a clean typology with four mathematical properties (Jumpiness is original), and a footprint-clustering preprocessing step that groups patterns with similar presence vectors. They release code and data, and they are honest about the SAGE gold standard being an approximation. The clustering idea is sensible and the reduction in pattern counts is real on several datasets.\n\nThe soft spot is load-bearing. Section 6.1 describes datasets and mining parameters, but nowhere does it say how train/test splits or cross-validation were done for the classification experiments. Figures 8 and 11 show F1 curves with no error bars. Under a literal reading, the classifier is trained and evaluated on the same graphs. If so, the F1 ordering of measures is largely reflecting overfitting, and the central claim that AbsSupDif and Sup are 'safe choices' while GR and Acc are 'considerably less relevant' is not supported. The clustering threshold is also selected from these same F1 curves and then reused, which adds selection bias. The RBO ranking comparisons are less affected by the missing protocol, but they depend on the SAGE approximation, which the authors themselves note is imperfect on IMDb.\n\nThese are fixable problems, not fatal ones. The ranking-based analysis, the correlation blocks, and the theoretical properties stand on their own. The paper deserves a serious referee and the authors should be asked to add a proper evaluation protocol with cross-validation, repeated runs, and error bars, plus a nested or independent threshold selection. The RBO parameter p should also be stated.\n\nFor a reader working on interpretable graph classification, this is worth reading now; for anyone relying on the specific measure recommendations, wait until the evaluation protocol is clarified.","headline":"Useful graph-specific comparison of quality measures, but the F1-based recommendations need a documented train/test protocol before they can be trusted.","tokens_in":47970,"tokens_out":2187,"would_cite":true,"duration_ms":22545,"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 comparison of 38 quality measures for pattern-based graph classification finds that AbsSupDif and Sup are the safest choices, while popular measures such as GR, Acc, and InfGain perform considerably worse.","keywords":["graph classification","pattern mining","quality measures","subgraph patterns","Shapley value","hierarchical clustering","preprocessing","binary classification"],"falsifier":"Compute exact Shapley values for all patterns on a small dataset and compare them with the approximate gold standard; if the two rankings disagree substantially, or if AbsSupDif and Sup no longer rank near the top under the exact values, the central recommendation collapses.","tokens_in":47077,"feed_emoji":"📊","tokens_out":7016,"duration_ms":62751,"temperature":0.7,"pith_summary":"The paper asks which of the many quality measures used to rank subgraph patterns actually helps graph classification. It compares 38 measures on eight datasets, characterizes them with four mathematical properties, and builds a gold-standard pattern ranking from Shapley values. Its empirical conclusion is that AbsSupDif (the absolute difference between pattern presence in the positive and negative classes) and Sup (presence in the positive class) are safe choices across datasets, while popular measures such as GR, Acc, and InfGain are considerably less effective. The paper also proposes a clustering preprocessing step that groups patterns with similar footprints, and shows that this reduces the number of patterns while achieving comparable or better classification performance.","feed_headline":"Two quality measures beat popular rivals for graph classification","feed_subtitle":"On eight datasets, ranking subgraph patterns with AbsSupDif or Sup keeps F1 scores high while GR, Acc, and InfGain lag.","key_machinery":"The footprint of a pattern is the binary vector recording, for every graph in the collection, whether that pattern occurs. The paper's clustering step groups patterns whose footprints are close under Manhattan distance using complete-linkage hierarchical clustering, selects one medoid per cluster as representative, and ranks only representatives, removing patterns that are interchangeable from the classifier's perspective. The gold standard uses Shapley values, approximated globally, to score each representative's contribution to classification performance; measure rankings are compared with Kendall's Tau for pairwise equivalence and with Rank-Biased Overlap against the gold standard. Four properties—Contrastivity, Jumpiness, Class Symmetry, and Pattern Symmetry—are introduced to explain why measures differ.","core_discovery":"The paper's central empirical claim is that, among 38 quality measures used to rank mined subgraph patterns for binary graph classification, AbsSupDif and Sup are consistently good choices across eight datasets, while several popular measures are not. Using a gold-standard ranking built from Shapley values approximated over pattern contributions, the paper compares measures two ways: how well their rankings of cluster representatives agree with the gold standard, and how fast F1-score rises when the top-ranked patterns feed a classifier. It finds that GR, Acc, and InfGain, despite being widespread, rank patterns poorly relative to the gold standard and need many more patterns to reach similar performance. It also claims that clustering patterns by footprint distance before ranking reduces the number of patterns by up to 92% while achieving comparable or better classification performance, and that groups of measures produce identical rankings, collapsing 38 measures to 21 informative ones.","pith_inferences":["Because the equivalence blocks imply that some measures are interchangeable, a testable extension is to replace an arbitrary measure with AbsSupDif and check whether classification performance and runtime improve on unseen datasets, not just the eight studied.","The clustering step may serve as a general denoising preprocessing for any pattern-based representation, not only quality-measure ranking; one could test it before graph-kernel or graph-neural-network input construction.","The gold standard is only as good as the Shapley approximation; if exact Shapley values were computed on small graphs, the ranking comparisons could be re-run to check whether the top measures remain AbsSupDif and Sup.","The paper's evidence that Dep beats the gold standard on IMDb suggests the approximate gold standard may be less reliable on social-network-style graphs, so the safe-choice recommendation may be strongest on molecular datasets."],"forward_implications":["Practitioners with no prior knowledge about a graph dataset can safely pick AbsSupDif or Sup to rank patterns; the paper reports they perform well on all eight datasets.","Popular choices such as GR, Acc, and InfGain are not reliable defaults for pattern-based graph classification and can require many more patterns to reach the F1-score of the better measures.","Many of the 38 measures are redundant: six blocks of measures produce identical rankings, so future studies can restrict attention to one representative per block.","A footprint-based clustering preprocessing step can shrink the pattern set substantially, for example by about 92% on MUTAG, while keeping or slightly improving classification performance, making larger graph collections computationally feasible.","The natural next steps stated by the paper are extending the comparison to imbalanced and multiclass settings and benchmarking against methods that mine discriminative patterns directly."],"supporting_citations":[{"why":"Provides the previous empirical comparison of quality measures and the baseline list of measures that the paper extends to graph data.","marker":"[63]"},{"why":"Supplies one of the surveys from which the set of 38 quality measures and the three excluded measures are drawn.","marker":"[16]"},{"why":"Defines the global Shapley-value approximation used to construct the gold standard pattern ranking.","marker":"[20]"},{"why":"Origin of the Shapley value on which the gold standard ranking is formally based.","marker":"[82]"},{"why":"The frequent subgraph mining algorithm that produces the pattern set ranked by the quality measures.","marker":"[100]"},{"why":"Introduces AbsSupDif, one of the two measures the paper identifies as the safest choices.","marker":"[86]"},{"why":"Defines Rank-Biased Overlap, the coefficient used to compare measure rankings with the gold standard.","marker":"[95]"},{"why":"Defines Kendall's Tau, used to find the blocks of measures that rank patterns identically.","marker":"[50]"},{"why":"The hierarchical agglomerative clustering method underlying the footprint-based preprocessing step.","marker":"[35]"}],"fun_headline_variants":["AbsSupDif and Sup beat popular graph measures by wide margin","Graph classification: preprocessing boosts accuracy, cuts patterns","GR, Acc, InfGain underperform in graph pattern ranking","Two quality measures shine in graph classification benchmark"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The conclusions rely on the Shapley-value approximation being a true gold standard for which patterns are most useful for classification, even though the paper notes that one measure, Dep, beats that gold standard on IMDb.","fun_headline_variants_meta":{"raw":{"variants":["AbsSupDif and Sup beat popular graph measures by wide margin","Graph classification: preprocessing boosts accuracy, cuts patterns","GR, Acc, InfGain underperform in graph pattern ranking","Two quality measures shine in graph classification benchmark"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001235,"raw_usage":{"total_tokens":5099,"prompt_tokens":1000,"completion_tokens":4099,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":616,"completion_tokens_details":{"reasoning_tokens":4034}},"tokens_in":616,"tokens_out":4099,"duration_ms":30047,"temperature":1.0,"reasoning_tokens":4034,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:28:38.899092+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute exact Shapley values for all patterns on a small dataset and compare them with the approximate gold standard; if the two rankings disagree substantially, or if AbsSupDif and Sup no longer rank near the top under the exact values, the central recommendation collapses.","supporting_citations":[{"cited_title":"Loyola-González, M","cited_arxiv_id":null,"evidence_quote":"Provides the previous empirical comparison of quality measures and the baseline list of measures that the paper extends to graph data."},{"cited_title":"Thoma, H","cited_arxiv_id":null,"evidence_quote":"Introduces AbsSupDif, one of the two measures the paper identifies as the safest choices."}],"review_version":1}