PaperlayerView exact revision on arXiv

Source-linked AI summary

Cardinality-Stratified Interaction Decomposition for Interpretable Pairwise and Higher-Order Structure in Transactional Basket Data

Hidetoshi Kawase, Toshihiro Ota

arXiv:2609.34191v1cs.LG

TL;DR

Transactional co-occurrence mixes item-specific association with basket-size structure and higher-order dependence. CSID decomposes rest-cardinality-stratified contrasts into item-set-specific and shared components. In partial transfer, its triple components show higher weighted concordance with later-period contrasts than the common-component baseline and CA-HOPL.

  • Problem

    Observed co-occurrence reflects item popularity, basket-size composition, lower-order associations, and higher-order interaction, limiting interpretation of item-specific signed relations.

    Source: §1 · p. 3

  • Method

    CSID uses an information-weighted, gauge-constrained ridge projection of rest-cardinality-stratified contrasts to estimate item-set-specific pair and triple components alongside shared components.

    Source: §1 · p. 4

  • Results

    CSID triple components yield higher weighted concordance with later-period H2 contrasts than both the common-component baseline and CA-HOPL in partial transfer.

    Source: Interpretive findings and empirical… · p. 24

  • Takeaways & Limitations

    The theoretical decomposition, simulations, and three temporal grocery analyses support CSID as an exploratory tool for signed pair and triple structure in transactional data.

    Source: §7 · p. 25

    Real-data conclusions concern multi-category baskets, because the analyses exclude baskets with fewer than two selected categories.

    Source: Limitations · p. 25

Abstract

from arXiv · show

Transactional basket data can reveal associations among items, but observed co-occurrence conflates item-specific relations with basket-size structure and unmodeled higher-order dependence. We introduce Cardinality-Stratified Interaction Decomposition (CSID), an interpretable framework that decomposes log-odds contrasts stratified by the number of remaining items into item-set-specific and cardinality-common components, without fitting a global joint distribution. CSID uses an information-weighted, gauge-constrained ridge projection to estimate pair and triple components and to diagnose higher-order contributions to pairwise structure. CSID is designed primarily for interpretable decomposition of association structure rather than for full-distribution prediction. In a simulation with zero pair effects, increasingly strong small-basket cardinality potentials drive ordinary Ising couplings spuriously negative, whereas CSID pair estimates remain centered near zero. Detection power rises with the magnitude of planted triple effects, and local deprojection reduces pair-coefficient RMSE from 0.244 to 0.073. Across three grocery datasets, high-information triple components are reproducible over time. In the matched cross-period partial-transfer evaluation, transferred CSID triple components show closer agreement with later-period stratified contrasts than the nodewise-symmetrized cardinality-aware higher-order pseudolikelihood comparator, with gains in weighted Lin's concordance correlation of 0.038--0.122. These results support CSID as an exploratory and interpretable decomposition framework for pairwise and higher-order association structure in transactional data.

1 Introduction

Basket co-occurrence mixes item-specific relations with popularity, basket-size composition, and higher-order interaction, making signed pair associations difficult to interpret. CSID stratifies interaction contrasts by rest cardinality to separate item-set-specific components from a shared environment and diagnose higher-order contributions.

1 Introduction

  • Ordinary Ising couplings can become negative to absorb common small-basket pressure, making pair-specific exclusion difficult to distinguish from basket-wide behavior.Observed co-occurrence also reflects item popularity, basket-size composition, and higher-order interaction.Source: §1 · p. 3
  • CSID stratifies fixed-rest log-odds contrasts by the number of purchased items outside the focal set, avoiding extremely sparse full rest-configuration cells.The decomposition separates interactions containing the focal set from a finite difference of the cardinality potential.Source: §1 · pp. 3–4
  • Its information-weighted, gauge-constrained ridge projection estimates pair and triple components without evaluating a global partition function.The framework also derives alternating updates and establishes uniqueness for the gauge-fixed item-set block and informative strata.Source: §1 · p. 4
  • CSID separates item-set-specific association from a rest-cardinality-common environment and diagnoses how higher-order structure alters lower-order projections.Its empirical comparison targets reproducibility and transferability of contrast components, not universal predictive superiority.Source: §1 · p. 4
  • The framework characterizes third-order contributions to pairwise projections and locally reweights pairs to adjust for estimated triple contributions before re-estimation.The evaluation includes simulations and analyses of three public grocery datasets.Source: §1 · p. 4

2 Related Work

Prior work offers frequent-itemset rules, log-linear interaction models, and joint or conditional dependence models. CSID instead targets local pair and triple projection components, stratifying focal contrasts by rest cardinality and decomposing them into item-set-specific and shared components.

2 Related Work

  • Classical market-basket mining searches for frequent itemsets and implication-style rules, while subsequent dependence-rule methods explicitly distinguish association from statistical dependence.Source: §2 · p. 4
  • CSID aggregates over rest-item identities within cardinality strata to address sparse high-dimensional tables.It separates focal-set deviations from a common stratum environment while using higher-order estimates to diagnose contributions absorbed into lower-order projections.Source: §2 · p. 5
  • CSID builds on established marginal interaction contrasts and adds an information-weighted decomposition into item-set-specific and shared rest-cardinality components, with gauge fixing and higher-to-lower-order diagnostics.Hierarchical log-linear models provide the standard interaction parameterization for multiway contingency tables [7].Source: §2 · p. 5
  • Unlike joint or conditional model approaches, CSID targets local pair and triple projection components without evaluating a global partition function.Its empirical comparison with a cardinality-aware order-three pseudolikelihood model assesses transfer to a common later-period stratified contrast.Source: §2 · p. 5

3 Cardinality-Stratified Interaction Decomposition

The reference model separates item-set interactions from basket-cardinality structure, then expresses fixed-rest log-odds contrasts through focal-set interactions and a cardinality finite difference. CSID uses these contrasts to interpret pair and higher-order associations.

3.1 Reference model and gauge freedom

  • The cardinality-aware reference model represents item-label-invariant basket-size tendencies with α|x| and pair-specific deviations with Jij.Singleton parameters are fields, pair parameters are couplings, and terms of order three or higher are higher-order interactions.Source: §3.1 · p. 6
  • When every order-k subset is included, a gauge transformation can shift the interaction block against the cardinality potential without changing the distribution.This invariance does not generally hold for a restricted family of order-k subsets.Source: §3.1 · p. 6

3.2 Higher-order log-odds contrasts

  • For a focal item set, the order-k log-odds contrast fixes the configuration of remaining items; substituting the reference model makes its normalizing constant cancel.Only interactions whose index sets contain the full focal set survive the contrast, alongside a finite difference of the cardinality term.Source: §3.2 · p. 7
  • For pairs, the fixed-rest contrast is the conditional pair log-odds ratio; for triples, its sign indicates whether the pair association strengthens or weakens when the third item is present.Under K=3, the triple coefficient captures that change after removing the common cardinality contribution; K>3 adds further interactions involving all three focal items.Source: §3.2 · pp. 7–8

3.3 Projection after stratification by rest cardinality

Because resolving every remaining-item configuration creates sparse cells, CSID stratifies contrasts by rest cardinality and projects them into item-set-specific and common components. The resulting target depends on the candidate family, cell probabilities, and gauge convention.

3.3 Projection after stratification by rest cardinality

  • Full conditioning on every rest vector rapidly produces sparse cells, motivating stratification by the number of remaining items.Marginalizing rest-item identities introduces mediation and mixing effects in the residual, rather than assuming that residual vanishes.Source: §3.3 · p. 8
  • The additive projection represents each contrast with an item-set-specific component relative to a common order-k environment for that rest-cardinality stratum.This stratified summary differs from the model interaction at a fully resolved rest configuration.Source: §3.3 · p. 8

Population target.

  • The population CSID component is a weighted projection defined by the candidate family, cell probabilities, and gauge convention, and need not equal a natural parameter of the reference joint model.Projection-level nonidentifiability can persist even for restricted candidate families and is distinct from structural gauge freedom.Source: Population target · pp. 8–9

Cell contrasts and information weights

CSID estimates item-set-specific contrasts against rest-cardinality strata, downweighting sparse strata through information weights. A gauge constraint selects a reference-weighted representative, and ridge fitting yields components whose interpretation depends on the candidate family and fitting conventions.

Cell contrasts and information weights

3.4 Gauge-constrained estimation and closed-form updates

  • The finite-sample estimator imposes a gauge constraint using fixed positive reference weights, with information weights as a natural default.Source: §3.4 · p. 9

Cell contrasts and information weights

  • Within the chosen candidate family, a pair coefficient’s sign indicates whether its pair-specific projection is stronger or weaker than the reference-weighted average under the same rest-cardinality environment.Source: §3.4 · p. 9

3.4 Gauge-constrained estimation and closed-form updates

  • The resulting pair components depend on the candidate family, information weights, gauge, and ridge penalty.Source: §3.4 · p. 10
  • The objective decreases monotonically under block updates and converges to a unique optimum for the fitted components under the stated convention.Source: §3.4 · p. 10
  • The information-normalized score is used to prioritize candidates, not for formal inference, because its scale omits several sources of uncertainty.Source: §3.4 · p. 10

Computational cost.

CSID’s pairwise deprojection removes estimated third-order contributions locally before refitting pair structure. Its empirical version is an approximation, while candidate-generation and storage costs constrain scaling to larger item universes.

Computational cost.

  • Exhaustive order-k candidate generation costs O(N^k), while larger universes use frequent-pair triangles and bounded neighborhoods before exact counting.Source: Computational cost · p. 11

3.5 Pairwise deprojection of third-order effects

  • At a fixed rest configuration, reweighting removes the third-order contribution exactly from the pair contrast.Source: §3.5 · p. 11
  • In empirical data, the method reweights the 11 cell using estimated triple effects and aggregates over rest-cardinality strata, producing a pair-specific approximation rather than a global pairwise model.Source: §3.5 · pp. 11–12

4 Synthetic Validation

Synthetic tests examine cardinality-driven pair contamination, triple detection, and recovery of pair structure under third-order saturation. They show that cardinality-aware estimation limits spurious negative pair estimates, while local deprojection improves recovery when omitted triples distort pairwise projections.

4 Synthetic Validation

  • The synthetic validation sampled baskets from the exact categorical distribution on nonempty states, using fixed fitting settings unless stated otherwise.Source: §4 · p. 12

4.1 Negative contamination of ordinary Ising couplings by cardinality structure

  • With true pair effects set to zero, ordinary Ising couplings shifted downward as cardinality constraints strengthened, while CSID-2 stayed near zero with lower RMSE.At s = 0.5, 99.7% of fitted Ising pairs were negative; for s ≥ 0.75, every fitted pair was negative.Source: §4.1 · p. 12, Figure 1 · p. 13

4.2 Detection of randomized sparse third-order signals

  • The detection experiment fitted all 120 triples and treated |zT| ≥ 2 as a detection, with non-planted exceedance measuring flags without a directly planted coefficient rather than a global-null type-I error rate.Source: §4.2 · p. 13
  • Triple-detection power rose with planted effect size, while non-planted triples were rarely flagged; weak effects were often missed, making screening suited to prioritizing candidates rather than exhaustive detection.Source: §4.2 · p. 14, Figure 2 · p. 14

4.3 Recovery of pairwise structure under third-order saturation

  • Reweighted CSID-2 tracked generating pair coefficients more closely than CSID-2 alone in a controlled realization with third-order saturation.The pairwise projection that omits the triple underestimates generating pair coefficients.Source: §4.3 · p. 15, Table 3 · p. 15

5 Evaluation on Public Transaction Data

Across three public grocery datasets, the evaluation examines temporal reproducibility and transfer of CSID pair and triple structure, then interprets triple modulation, pairwise deprojection, and robustness to expanding the item universe.

5.1 Datasets and evaluation design

  • Each public dataset was restricted to 20 categories; baskets were binarized, baskets with fewer than two selected categories excluded, and candidate sets fixed for H2 evaluation.The datasets used matched temporal splits and the same candidate family for H2 and full-period evaluation.Source: §5.1 · pp. 15–16

5.2 Cross-period transfer of third-order effects

  • High-information CSID-3 effects showed positive temporal correlation in all three datasets, and overlap among the 20 most negative effects exceeded random expectation.The reported category-omission sensitivity ranges were directionally consistent.Source: §5.2 · p. 16, Table 5 · p. 16
  • The partial-transfer comparison combines an H2-estimated common component with the target triple’s H1-specific component, while excluding that target from common-component estimation.CA-HOPL was fit to H1 and compared using the same H2 contrasts and evaluation weights.Source: §5.2 · pp. 17–18
  • CSID-3 information-weighted CCC exceeded both the common-component baseline and CA-HOPL by 0.038 (Complete Journey), 0.122 (Ta-Feng), and 0.049 (Instacart).The comparison used identical triples, layers, and evaluation weights.Source: Table 6 · p. 19, §5.2 · p. 19, Figure 3 · p. 19

5.3 Full H1-only transfer

  • Adding the H1 triple component improved H1-only reconstruction CCC over the H1 common component in every dataset, though it remained below partial transfer.This H1-only evaluation also reflects any period shift in the common basket-cardinality environment.Source: §5.3 · p. 20, Table 8 · p. 20

5.4 Conditional-odds interpretation

  • Across examples, CSID-3 transfer generally reproduced the direction and approximate magnitude of H2 pair modulation better than the common-component baseline, with errors remaining for small effects.Examples included both negative and positive moderator contrasts.Source: §5.4 · p. 20, Figure 4 · p. 21

5.5 Effect of third-order structure on pairwise projections

  • Third-order deprojection changed pairwise projections in both directions; H1-based corrections correlated positively with H2-based corrections and strongly with the full-period reference.The correction depended on the signs and locations of triples containing each pair.Source: §5.5 · pp. 21–22, Table 10 · p. 22

5.6 Robustness to expansion of the item universe

  • Focal coefficients correlated above 0.95 with the all-aisle reference even at 20 context aisles, while transfer-gain differences reflected the changed rest-cardinality definition.The CCC gain was 0.286 in the 20-aisle representation versus 0.163–0.172 in expanded contexts.Source: §5.6 · p. 22, Table 11 · p. 23, Figure 5 · p. 23

6 Discussion

CSID components show transfer to later-period stratified contrasts and support diagnosis of higher-order effects on pairwise projections. The discussion also limits these interpretations to associative, projection-based analysis and partial transfer.

Interpretive findings and empirical validation.

  • Temporal stability, transfer, and pairwise correction analyses provide evidence that CSID components are not merely in-sample algebraic decompositions.The transferred component is reported to capture information about both the direction and magnitude of third-item modulation of pair associations.Source: Interpretive findings and empirical… · p. 24
  • CSID-3 yields higher weighted concordance with H2 contrasts than both the common-component baseline and CA-HOPL in a partial-transfer evaluation.The comparison targets agreement with H2 stratified contrasts, not equality of model coefficients or universal predictive superiority.Source: Interpretive findings and empirical… · p. 24

Interpretation and use.

  • Local reweighting identifies pair projections whose apparent strength depends materially on overlapping triples, but does not produce a common deprojected joint distribution.The correction is therefore a diagnostic decomposition rather than a replacement generative model; signs and conditional-odds contrasts can prioritize item sets for review, while information scores distinguish well-supported candidates from sparse ones.Source: Interpretation and use · p. 24

Limitations.

  • CSID coefficients are item-set-specific projection components of marginalized contrasts, not necessarily natural parameters, and the estimated interactions are associative rather than causal.The residual captures mediation and mixing from marginalizing rest-item identities, and z scores are screening statistics rather than calibrated independent-test p-values.Source: Limitations · p. 24
  • Real-data analyses exclude baskets with fewer than two selected categories, and the local correction depends on the retained triple family and omitted higher-order interactions.The contrast is relative to the chosen item universe and candidate family; exhaustive enumeration grows combinatorially, and the 134-aisle scaling audit relied on candidate restriction.Source: Limitations · p. 25

Outlook.

  • Further work could quantify projection residuals, calibrate candidate screening under dependence, and compare CSID with coherent joint models on predictive and interpretive criteria.Extensions to customer segments or time-varying strata could separate context-specific interaction changes from shifts in the overall basket-size environment.Source: Outlook · p. 25

7 Conclusion

The paper concludes that CSID is an exploratory framework for interpretable pairwise and higher-order association structure in transactional data.

7 Conclusion

  • CSID separates item-set-specific association from a rest-cardinality-common environment and makes explicit how omitted higher-order structure enters lower-order projections.The theoretical decomposition, simulations, and three temporal grocery analyses support its use as an exploratory tool for signed pair and triple structure.Source: §7 · p. 25

A Parameter and design sensitivity

The tested outcomes remained positive and close to their default values across the reported one-factor sensitivity variations.

A Parameter and design sensitivity

  • All three outcomes remained positive and close to their default values across the tested smoothing, ridge, and singleton-category inclusion variations.The outcomes were temporal ρ, the CSID–CA-HOPL partial-transfer gap, and the H1–H2 correlation of third-order-induced pairwise-projection changes.Source: A Parameter and design sensitivity · p. 25

B Scaling audit

The scaling audit reports candidate-restricted aisle-level performance on 373,133 Instacart baskets, rather than exhaustive or SKU-level scalability.

B Scaling audit

  • At 134 aisles, candidate generation capped at 250,000 candidates, retained 156,735 after support filtering, and completed measured stages in 49.9 seconds using 178 MB of stratified array storage.At 20 and 40 aisles, sparse generation retained every supported exhaustive triple; the 134-aisle result demonstrates candidate-restricted aisle-level scaling, not exhaustive or SKU-level scalability.Source: B Scaling audit · pp. 25–26, Table 13 · p. 26
Loading 2609.34191v1…