{"id":"7bfa00f1-7604-4cc5-8c35-6a1fb0256b1d","arxiv_id":"2412.18522","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"SHARQ defines and efficiently computes a Shapley-value-based contribution score for each element in a set of association rules, enabling element, rule, and attribute level explanations.","lead":"SHARQ is a new Shapley-based score that measures how much each individual data element (an attribute-value pair) contributes to the interestingness of a set of association rules. The paper also presents an exact algorithm, SHARQ*, that computes this score in roughly linear time in the number of rules, plus a multi-element version and use cases for finding redundant rules and important attributes.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Exactness of SHARQ* is conditional on the unenforced \"no duplicate attributes in a rule\" assumption; a violated rule set makes C* include invalid coalitions and Proposition 3.1 fail.","rationale":"I read the proof of Proposition 3.1 line by line; under Section 2.2's attribute-disjointness condition the pruning argument is valid. Any nonzero marginal must come from a coalition that is exactly a rule or a rule minus the queried element, and each such coalition has size at least |E(r)|−1. The complexity analysis is also internally consistent, and the single-element and multi-element algorithms correctly implement the pruned formula under that assumption. The one place the central claim can genuinely break is the input contract: C* drops the valid-coalition disjointness test because it assumes all rule subsets are attribute-disjoint. If that assumption fails, the optimized formula is not exact, and the paper neither proves the assumption follows from relational tuple mining nor provides a validation step. The reader's numerical inconsistencies (45 vs 67 instances, IS score mismatch, Section 4.2 arithmetic) are real but presentation-level; they do not shake the core theorem within the stated model. A brute-force counterexample settles the role of the assumption. Since the assumption is stated in Section 2.2, this does not overturn the reader's verdict but reinforces the CONDITIONAL reading: the paper should explicitly state the precondition in Proposition 3.1 and add a validator to the released code.","tokens_in":25664,"tokens_out":21342,"duration_ms":210307,"concrete_test":"Run a brute-force comparison of the original SHARQ formula and the SHARQ* formula on a small adversarial rule set containing one duplicate-attribute rule, e.g. R={r: (A,a1),(A,a2)→(B,b)}, E={(A,a1),(A,a2),(B,b)}, e=(B,b). The two values should differ, demonstrating that Proposition 3.1 fails whenever the Section 2.2 assumption is violated. Then scan every rule in the released benchmark for duplicate attributes and report whether any instance violates the assumption; if none does, the theorem's condition is satisfied empirically but must still be documented as a precondition, and the code should validate and reject or flag violating inputs.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Proposition 3.1 is sound when the Section 2.2 property holds: no rule contains two elements with the same attribute. The single load-bearing point is that this property is an unvalidated input condition, not a consequence of the algorithm. Equations (1)-(3) define C*(e,E) using only S⊆E(r), |S|≥|E(r)|−1, and attr(e)∉attr(S); they drop the |attr(S)|=|S| condition from C(e,E). If a rule r has two elements sharing an attribute, a subset S of E(r) of size |E(r)|−1 can contain that duplicate and still enter C*(e,E). Such S is not in C(e,E), so including it in the sum can change the result and Proposition 3.1's equality fails. Concretely, let attributes A,B, E={a1,a2,b}, R={a1,a2→b}, e=b. SHARQ(e)=0 because the only valid coalitions are ∅,{a1},{a2}, none of which forms a rule with or without e; SHARQ* sums S={a1,a2} (invalid, since two A-elements) with weight 1/3·score(r) and returns a nonzero value. The paper states the assumption but does not derive it from relational tuples, check it in the mining pipeline, or guard against violation (multi-valued attributes, overlapping bins). Thus the central exactness claim is conditional on an input contract the manuscript never enforces.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces SHARQ, a Shapley-value-based measure of a data element's contribution to the interestingness of a set of association rules. It defines SHARQ over valid coalitions of elements with disjoint attributes, proves an equivalent optimized formula SHARQ* (Proposition 3.1), and presents a single-element algorithm with cost O(|R|·τ·(τ+γ)), called practically linear in the rule count, plus a multi-element variant that amortizes coalition construction over elements sharing an attribute. The paper also defines rule-level and attribute-level importance scores built from SHARQ and reports experiments on rule sets mined from several datasets, claiming that SHARQ* is orders of magnitude faster than naive computation and that multi-element SHARQ* gives roughly a 12–14× speedup over sequential computation. The central theoretical claim is that SHARQ* computes exactly the SHARQ score while avoiding the exponential enumeration of all valid coalitions.","tokens_in":25836,"tokens_out":8270,"duration_ms":68587,"significance":"If the correctness and complexity claims hold, SHARQ is a useful explainability primitive for association rules: it gives exact Shapley-based element attributions in a setting where naive enumeration is infeasible, and the rule- and attribute-level aggregates provide concrete downstream use cases. The paper's strengths include a direct equivalence proof of SHARQ* (Proposition 3.1), a complexity analysis consistent with the algorithm pseudocode, and an evaluation that compares coalition counts and running times on diverse rule sets rather than relying on fitted parameters. The benchmark of mined rule sets is a useful contribution, though the reported instance counts are currently inconsistent. The main correctness concern is that the exactness proof is conditional on an unstated and unchecked assumption about duplicate attributes in rules; the main empirical concern is a tangle of numerical inconsistencies in the example, the redundancy use case, and the evaluation-set size.","major_comments":[{"comment":"The number of evaluation instances is inconsistent: the abstract and the contributions list say 45 instances, while Section 5.1 first says '45 different rule mining results' and then says the pipelines 'generated a total of 67 distinct rules sets'; Table 5 lists dataset counts summing to 67; and Section 5.3 refers both to 'our 45⟨D,R⟩ evaluation instances' and to 'all 67 instances.' Because the averaged results (e.g., 6.6s per element, 13.8X multi-element speedup) depend on which set is used, this inconsistency must be fixed and the per-dataset counts reconciled before the experimental claims can be evaluated.","section":"Abstract and Section 5.1"},{"comment":"The exactness of SHARQ* is conditional on the assumption, stated in Section 2.2, that 'a rule never contains two elements with the same attribute.' Equation (3) sums over C*(e,E), which is defined in Equations (1)–(2) without the |attr(S)|=|S| condition used in C(e,E). Under the stated assumption the proof is sound, and for rules mined from tuples with positive support the assumption follows from the tuple model. However, the paper does not state that derivation, does not check the condition when rules are supplied from an external mining pipeline, and does not discuss what happens when the condition fails (e.g., multi-valued attributes or overlapping bins). Please state the assumption as an explicit input contract, add a validation step, and discuss the limitation; otherwise Proposition 3.1 is not a guarantee for all inputs accepted by the algorithms.","section":"Section 2.2 and Proposition 3.1"},{"comment":"The running example's IS scores contradict the formal IS definition. Section 2.1 defines IS(r)=sqrt(support(r)·lift(r)); for r1 this is sqrt(0.2·5.25)≈1.02, yet Table 2 reports 'IS score (×10^2)' = 105 and Example 2.1 uses values 1.05 and 1.02. The reported numbers match support·lift (not its square root), and the example's calculation '3!(6−3−1)!/6!·(1.05−1.02)=0.05' is also arithmetically wrong: the factorial ratio is 1/60 and the difference is 0.03, giving 0.0005 (or 0.05 only if the difference is 3). This inconsistency undermines the illustrative example used to explain SHARQ; please correct the formula, the table values, or the example so that all numbers are internally consistent.","section":"Section 2.1 and Example 2.1 / Table 2"},{"comment":"The redundancy use case contains an arithmetic error. The text states that at a rule-level SHARQ threshold of 0.21, 'a total of 68250 (95%) rules fall below the threshold' and that eliminating them leaves '3140 important, non-redundant rules.' With 84,479 total rules, 84,479−68,250=16,229 (not 3,140), and 68,250/84,479≈80.8% (not 95%). The claimed pruning effectiveness of the rule-importance use case is therefore not supported by the reported numbers; please correct the counts or the threshold and recompute the stated percentages.","section":"Section 4.2"}],"minor_comments":[{"comment":"The text says the evaluation set is built from 'four underlying datasets' but then lists six datasets (Adult, Spotify, Flights, Isolet, Covid-19, Adult-ACS); please correct the number.","section":"Section 5.1"},{"comment":"In the 'Number of Coalitions' paragraph, 'each subset E⊆E(r) of size≥|E(r)|' should read 'each subset S⊆E(r) of size |S|≥|E(r)|−1'; the current wording is confusing.","section":"Section 3.1"},{"comment":"In the sentence 'Given an element e, and a set of elements E∈E(D)', the symbol E should be a subset of E(D), not an element of it; please write E⊆E(D).","section":"Section 2.2"},{"comment":"In the definition of A-SHARQ, the denominator is written as 'E_a', a set; it should be the number of elements of attribute a that appear in at least one rule, e.g., |E_a ∩ E(R)|.","section":"Section 4.3"},{"comment":"The paper uses 'Shapely' in several places (e.g., the abstract); it should be 'Shapley.'","section":"General"},{"comment":"The per-dataset speedup factors listed in the text (13.6X, 17.5X, 20.4X, 16.2X, 8X, 12.6X) do not average to the stated 13.8X; please verify the numbers or the averaging method.","section":"Section 5.3"}],"recommendation":"major_revision","confidential_remarks":"The paper's core idea and algorithm are likely salvageable, and Proposition 3.1's proof is sound under the intended relational model. However, the experimental section currently contains contradictory instance counts and arithmetic inconsistencies that a careful reader cannot reconcile, and the exactness claim needs to be scoped to an explicit, validated input condition. These are fixable within the manuscript's scope, but they are load-bearing for the paper's empirical and theoretical promises, so I recommend major revision rather than accept or minor revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know: SHARQ is a genuine new measure — Shapley values over element coalitions for association rule sets — and the exact pruning in Section 3 is correct under the paper's stated assumption that rules never contain two elements with the same attribute. I checked Proposition 3.1's logic. If that assumption holds, any subset of a rule's elements automatically has distinct attributes, so the simplified coalitions C* are exactly the contributing ones. The stress-test counterexample with a rule containing two same-attribute elements violates the assumption and would break the proof, but such a rule cannot have positive support in the intended setting (relational tuples with one value per attribute). The authors should say that explicitly and add a small validation check, but this is not a flaw in the central argument.\n\nThe multi-element algorithm is a natural but useful amortization, and the reported 12–14x speedup is plausible. The rule-importance and attribute-importance use cases are reasonable, and the paper is honest that user studies are deferred.\n\nWhat needs fixing is presentation. The abstract and contributions say 45 benchmark instances; Section 5.1 and Table 5 add up to 67. Example 2.1 uses IS scores scaled by 100 (105 vs 1.05), and the shown arithmetic (3!(6−3−1)!/6! · (1.05−1.02) = 0.05) is wrong under the formal definition. Section 4.2 says 68,250 rules (95%) fall below a threshold yet 3,140 remain, which does not add up for a total of 84,479 rules. None of these touch the core math, but they undercut confidence in the experimental numbers.\n\nThe paper's exactness proof is checkable from the text, the complexity analysis is consistent, and the experiments are extensive and reproducible in principle. With the numbers fixed and the input assumption formally stated, this is a solid contribution to a mature subfield. I'd send it to a data-mining or database venue; a careful referee can push the revision in the right directions.","headline":"New Shapley-based measure for association rule elements with an exact linear-time shortcut; the math holds under a stated input assumption, but the paper needs cleanup on inconsistent numbers and example scaling.","tokens_in":26476,"tokens_out":4291,"would_cite":true,"duration_ms":37584,"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":"Exact, fast Shapley scores for association rule elements","keywords":["association rules","Shapley value","explainability","element importance","rule importance","attribute importance","rule-set interestingness","exact algorithm"],"falsifier":"Take a rule set containing one rule with two elements of the same attribute, compute the original SHARQ definition directly, and compare with the optimized SHARQ*; because $\\mathcal{C}^*$ and the proof rely on distinct attributes inside rules, a nonzero difference (or an undefined coalition) would refute Proposition 3.1.","tokens_in":25357,"feed_emoji":"📊","tokens_out":6313,"duration_ms":55555,"temperature":0.7,"pith_summary":"This paper tries to establish that a data element's contribution to a set of mined association rules can be measured exactly by a Shapley-value score, called SHARQ, and that this otherwise exponential computation can be made practical. The score works by asking how a rule set's aggregate interestingness changes when an element is added to any attribute-disjoint coalition of elements. If the paper is right, analysts can rank elements, flag redundant rules, and rank attributes in rule sets containing hundreds of thousands of rules, not just hand-picked examples. The key practical claim is that the exact score can be computed in time that is practically linear in the number of rules.","feed_headline":"Exact Shapley scores for rule elements are now fast to compute","feed_subtitle":"A pruning identity makes element importance in mined rule sets exact and practically linear in rules.","key_machinery":"The load-bearing object is the pruned coalition set $\\mathcal{C}^*(e,E)=\\{S: \\exists r\\in R,\\ S\\subseteq E(r),\\ |S|\\ge|E(r)|-1,\\ attr(e)\\notin attr(S)\\}$, paired with a coalition-to-rules index built in one pass. This restricts the Shapley sum to coalitions that are either a full rule's elements or one element short of a rule, because only those can change the utility difference $I(R_{S\\cup\\{e\\}})-I(R_S)$. The index stores, for each coalition $S$, the rules whose elements equal $S$, so utility lookups are $O(1)$ and the factorial Shapley weights are applied only to surviving coalitions.","core_discovery":"The central claim is Proposition 3.1: for every element $e$, the optimized formula $\\mathrm{SHARQ}^*_{(E,R)}(e)$ equals the original definition $\\mathrm{SHARQ}_{(E,R)}(e)$. The paper argues that any coalition of elements that is not contained in some rule, or is two or more elements short of a rule, contributes zero to the Shapley sum, because both the coalition and the coalition with $e$ match no rules; hence those coalitions can be pruned without changing the result. The resulting single-element algorithm runs in $O(|R|\\cdot\\tau\\cdot(\\tau+\\gamma))$ time, essentially $O(|R|\\cdot\\tau^2)$ and called practically linear in the number of rules $|R|$, where $\\tau$ is maximum rule size and $\\gamma\\le1$ is the fraction of rules lacking $e$'s attribute. The paper also claims a multi-element algorithm amortizes coalition generation across elements sharing an attribute, giving an average 13.8x speedup over sequential single-element runs in experiments.","pith_inferences":["If the disjoint-attribute assumption could be relaxed to allow multi-valued attributes, the same coalition-pruning idea would need a corrected validity condition; the paper does not explore this, but the exactness proof's reliance on non-repeated attributes pinpoints where the change would land.","The normalized rule-level score R-SHARQ is demonstrated at a threshold of 0.21, which reduces an 84,479-rule set to 3,140 rules; a natural next step the paper leaves implicit is a principled way to set that threshold from a false-discovery or coverage target.","The multi-element algorithm's amortization by attribute suggests SHARQ scores could be maintained incrementally when rules are added or removed; the paper names updates as future work but gives no algorithm.","Because kernel-weighted permutation sampling preserves element ranking almost as well as exact SHARQ at comparable cost, a practical deployment could use the approximation to screen elements and exact SHARQ only for the top candidates; the paper reports the quality numbers but does not advocate this pipeline."],"forward_implications":["Exact element-level SHARQ scores become computable for large mined rule sets: average 6.6-6.8 seconds per element versus hours or days for the naive calculation.","Element importance rankings can differentiate elements that generic measures like I_TOP and Influence cannot, as in the running example where one element scores -0.6 and two others score 4.6.","Rule-level R-SHARQ flags redundant rules: in the Adult use case, 95% of rules fall below the demonstrated threshold, leaving 3,140 non-redundant rules.","Attribute-level A-SHARQ gives a global view of which columns drive rule generation, supporting dimensionality reduction.","Direct Shapley approximations, especially kernel weighting, preserve element rankings (p@10 0.92, rank correlation 0.93) better than generic contribution measures, with comparable running time."],"supporting_citations":[{"why":"Defines Shapley values, the game-theoretic contribution concept that SHARQ adapts to rule elements.","marker":"[59]"},{"why":"Apriori rule mining algorithm used to generate the rule sets on which SHARQ and SHARQ* are evaluated.","marker":"[3]"},{"why":"IS interestingness measure used as the default rule score in the framework and experiments.","marker":"[67]"},{"why":"Lift measure combined into IS and used to filter mined rules during benchmark construction.","marker":"[10]"},{"why":"Provides the kernel-weighting Shapley approximation that the paper compares against alternative contribution measures.","marker":"[46]"},{"why":"Prior adaptation of Shapley values to database query tuples, which motivates the game-theoretic framing but requires a different computation.","marker":"[43]"}],"fun_headline_variants":["Exact Shapley for rule elements now practically linear","SHARQ: pruning makes Shapley rule scores exact and fast","13x speedup for exact Shapley values in mined rules","Linear-time exact element importance for association rules","Pruning identity unlocks fast Shapley for rule elements"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The framework assumes that every rule contains at most one element per attribute, i.e., a rule never lists two different values of the same column; if a rule ever does, the definition of valid coalitions, the pruning set, and the exactness proof all stop working.","fun_headline_variants_meta":{"raw":{"variants":["Exact Shapley for rule elements now practically linear","SHARQ: pruning makes Shapley rule scores exact and fast","13x speedup for exact Shapley values in mined rules","Linear-time exact element importance for association rules","Pruning identity unlocks fast Shapley for rule elements"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000157,"raw_usage":{"total_tokens":1230,"prompt_tokens":965,"completion_tokens":265,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":581,"completion_tokens_details":{"reasoning_tokens":182}},"tokens_in":581,"tokens_out":265,"duration_ms":3402,"temperature":1.0,"reasoning_tokens":182,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T04:42:59.469483+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a rule set containing one rule with two elements of the same attribute, compute the original SHARQ definition directly, and compare with the optimized SHARQ*; because $\\mathcal{C}^*$ and the proof rely on distinct attributes inside rules, a nonzero difference (or an undefined coalition) would refute Proposition 3.1.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"IS interestingness measure used as the default rule score in the framework and experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Lift measure combined into IS and used to filter mined rules during benchmark construction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the kernel-weighting Shapley approximation that the paper compares against alternative contribution measures."},{"cited_title":"The Shapley Value of Tuples in Query Answering","cited_arxiv_id":"1904.08679","evidence_quote":"Prior adaptation of Shapley values to database query tuples, which motivates the game-theoretic framing but requires a different computation."}],"review_version":1}