Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
82,509 characters · 30 sections · 37 citation commands
Extracting Complements and Substitutes from Sales Data: A Network Perspective
\xdef\shorttitle{Extracting Complements and Substitutes: A Network Perspective} \xdef\shortauthors{Tian et al.}
Understanding the hidden relations existing between products is fundamental in both economics and marketing research as well as in retail elrod_inferring_2002. This question lies at the core of market structure analysis and finds numerous applications. Retailers must regularly make decisions taking product relationships into account manrali_assortment_2009, for instance to design their product catalogue and to determine the number of products to offer in each category Kok_assortplanning_2015. Brick-and-mortar retailers seek to identify the best way to arrange the product layout in aisles and stock their shelves nierop_shelf_2008, and online retailers also strive to optimise the grouping of products in their online shops Breugelmans_online-retail_2007. Furthermore, they must \textcolor{black}{decide} which products to bundle or promote together. These assortment-related decisions have significant influence on customers' choices, sales of products, and finally, profits manrali_assortment_2009, Kok_assortplanning_2015, briesch_choice_2009.
Complements and substitutes are two central concepts to characterise relationships between products, with well-established definitions in economics nilcholson_microeco_2012. Complementary products are sold separately but used together, each creating a demand for the other, such as hot dogs and hot dog buns. Substitute products serve the same purpose and can be used in place of one another, such as Brand A tomatoes and Brand B tomatoes. \textcolor{black}{In the economics literature}, the degree of complementarity (substitutability) is formally defined \textcolor{black}{through} the negative (positive) cross-price elasticity of demand, where the rise in the demand of one product is recorded after the price of the other product is reduced (increased) by a unit. The mechanisms of complements and substitutes are also referred to as the halo effect and demand transfer, respectively, in the retail context ailawadi_halo_2007.
Despite its practical importance, the algorithmic problem of identifying the relationship between products in retail is not well known. For a long time, researchers and practitioners have selected the set of possible complementary or substitute products by means of, for instance, field expertise and simple statistics, and the analysis has usually been restricted to a fairly small number of products song_discretecontinuous_2007, berry_structural_2014. Recent development and application of natural language processing and machine learning (ML) algorithms, especially those based on word embedding, bring in new visions and opportunities, which makes it possible to analyse thousands of products gabel_p2vmap_2019, ruiz_shopper_2019, chen_studying_2020. These methods use the transactions, some require customer information, as the original feature space, and apply ML algorithms to essentially reduce the dimension of these feature vectors. The resulting reduced dimensional embeddings can then be used to identify the relationship between products and also in customer choice models.
However, there are several limitations in these applications. Firstly, the interpretation of the selected features in the related ML algorithms is difficult. This makes it challenging to develop metrics in this space, in particular to verify the property of triangle inequality, and further use metric invariants to define measures between products. In practice, these methods often rely on the definition of similarity measures (not necessarily metrics) for complementarity and exchangeability\footnote{{Exchangeability is an additional concept in order to verify whether two products are substitutes, and \textcolor{black}{researchers} postulate that they are if they have low complementarity and high exchangeability.}} ruiz_shopper_2019, chen_studying_2020. Secondly, these methods lack specific criteria to determine whether two products are complements, substitutes, or just independent, despite trying to quantify the effects by their similarities. Thirdly, they do not explore the \textcolor{black}{connection} between complements and substitutes, which is of great significance to improve the understanding of the relationships and their further applications. Furthermore, these methods are based on co-purchase patterns, but the other valuable information in the sales data remains unused.
In our study, we \textcolor{black}{propose an alternative to the classic approach based on cross-price elasticity, and take instead} a network perspective in order to define complementarity and substitutability between products. As a starting point, we model the sales data as a bipartite product-purchase network, with both transactions (or baskets) and products as nodes. We then perform our analysis directly on the network, without having to rely on low-dimensional embeddings which may lead to uncontrolled loss of information. We use the connectivity patterns between products to characterise complements and substitutes. To do so, we define null models on the bipartite network to determine significant relationships between products, and propose measures induced by random walks on networks to quantify the intensity of these relationships. This approach can be seen as a generalisation of the classic bipartite network projection where we focus on different notions of connectivity induced by the bipartite structure. We also take an initial step to explicitly incorporate noise effects in our measures. As we show later, the resulting projections onto unipartite networks, based both on complementary and substitute connections, allow us to find groups of similar products with standard tools like community detection.
The aim of our work is to provide insights into product relationships from a network perspective with simple assumptions, and to further extract both complements and substitutes efficiently from easily accessible sales data. It is our belief that a network approach opens up a promising new angle on this problem due to its flexibility, e.g. in determining significant relationships, and the vast network science toolbox. The insights derived from our methods have applications in assortment-related decision making, not only for retailers but also general firms with long product lines. Furthermore, our set of methods can also be applied to other contexts, such as trading networks, ecological systems and social networks, where both \textcolor{black}{the identification of cooperative and competitive relations} are of interest.
\textcolor{black}{In this section, we present the different datasets that we use to perform our analysis, the sales data in Sect. (ref) to extract the product relationships, the product hierarchy data in Sect. (ref) and the flavour compound and recipe data in Sect. (ref) to validate the results.}
We used anonymised grocery sales data from Tesco, the UK's largest supermarket chain. The data consists of timestamped transactions of stores, and it has been anonymised for general research purposes, i.e. each customer's personal identifiable information has been removed. For each store, the transaction data comprises a transaction ID, which gives a unique code to each shopping trip, the date when the transaction was made, the product IDs, and their purchased quantities; \textcolor{black}{see the top of Fig. (ref)}.
The data used for this study is from a generic convenience store in \textcolor{black}{an} urban area, and spans a three-month period avoiding major holidays such as Christmas and Easter. The time window is chosen to be long enough to be representative of the underlying customer population's product purchase patterns, but also sufficiently short to avoid seasonal effects as well as change of behaviour over time. Furthermore, to facilitate the interpretation of the results, we restrict our analysis to fresh fruit, vegetables and salads where we believe complementary and substitute products commonly exist. We also exclude products that are purchased less than once a month, and those in almost every transaction. These result in the final dataset of $43837$ transactions and $253$ products.
In retail, it is common to organise products in a hierarchy, where similar products are grouped into increasingly generic categories. Products that are close together in the hierarchy are typically sold next to each other in a store. At the lowest hierarchical level, each unique code corresponds to a different product, including the same products of different sizes or flavours. Overall, we have $4$ levels, from L1 to L4 (excluding the product level). The higher a level is, the more generic the corresponding category. For example, "apple" is a category in the L1 hierarchy, and "fruit" is a category in the L3 hierarchy. Hence, a natural way to validate our product relationships and to explore their features would be to compare them to the corresponding product hierarchy.
Ahn et al Ahn_flavor_2011 provide a systematic list of $1107$ flavour compounds and their natural occurrences in terms of $1525$ ingredients overall from Fenaroli's handbook of flavour ingredients Fenaroli_flavor_2004. They also provide $56498$ recipes belonging to geographically distinct cuisines (North American, Western European, Southern European, Latin American and East Asian), which were obtained from epicurious.com, allrecipes.com and menupan.com; see the bottom of Fig. (ref). Hence, to validate our results from the features in both flavour compounds and recipes, we match our products to their ingredients.
To construct the correspondence between our products and the flavour compounds, we match each product to as many ingredients as possible. For example, "Loose Peppers" is matched to all possibly equivalent peppers including "bell pepper" and "green bell pepper"; \textcolor{black}{see the middle left of Fig. (ref)}. This results in our ingredients of interest to be $140$, with their corresponding flavour compounds being $865$, and each ingredient is linked to $57$ flavour compounds on average. Note that there are $11$ products which do not have exactly matched ingredients, hence we match them to generic ones\footnote{{In the recipe data, there are both specific ingredients, e.g. "apple", and generic ones, e.g. "fruit".}}. For example, we match the product "Single Pomegranate" to the ingredient "fruit". There are also $44$ complex products whose ingredients cannot be directly inferred from their names, thus we match them to their main ingredients on the website. For example, we match the product "Cheddar Coleslaw" to the ingredients "cheddar cheese", "cabbage", "carrot" and "onion".
For the recipe data, we match each product to as few and simple ingredients as possible. For example, "Loose Peppers" is now only matched to "bell pepper"; \textcolor{black}{see the middle right of Fig. (ref)}. We then restrict to products only corresponding to one ingredient, and also remove products that are matched to unrepresentative generic ingredients (e.g. "vegetable"). We take a (generic) ingredient to be unrepresentative, if it shares less than half of its flavour compounds with the ingredients in the same category. As an example, if the product "Loose Aubergine" were only matched to the generic ingredient "vegetable" which shared less than half of its flavour compounds with all other vegetable ingredients, such as "asparagus", "lettuce" and "onion", we would exclude this product. This further reduces the number of products and ingredients of interest to \textcolor{black}{be} $175$ and $69$ respectively, with $47222$ corresponding recipes, and each recipe being expected to contain $3$ such ingredients.
We model the structure in the sales transaction data as a bipartite network, where we have two subsets of nodes, one corresponding to transactions and the other to products. A transaction node and a product node are connected, if the product is purchased in that particular transaction; see Figs. (ref) (top) and (ref). We call it the product-purchase network, and aim to extract product relationships from how product nodes are connected to each other in the network. This problem is generally related to the projection of bipartite networks to unipartite ones Zhou_bipartiteproj_2007. Different strategies exist depending on the nature of the relationship that one wants to infer Zhou_bipartiteproj_2007, li_weighted_2005, newman_scientific_2001, newman_scientific-2_2001, newman_coauthorship_2004, leicht_vertexsim_2006. While a majority of works look for assortative relations, in the sense that two nodes are connected in the unipartite network if they tend to share many neighbours in the bipartite one, more general types of projections can be defined, which are associated to the role played by the nodes in the \textcolor{black}{bipartite} network, and are particularly relevant to extracting complements and substitutes. In the following section, we will specify our assumptions about the product relationships, which can be further interpreted as the \textcolor{black}{specific} connectivity patterns in the product-purchase network; see typical examples in Fig. (ref).
We use the biadjacency matrix $\mathbf{A}^{(b)} = (A_{li})\in \{0,1\}^{n_t\times n_p}$ to represent the product-purchase network, where $n_t$ is the number of transaction nodes, $n_p$ is the number of product nodes, and $A_{li} = 1$ if product $i$ is purchased in transaction $l$ and $0$ otherwise.
\textcolor{black}{To characterise the product relationships, we consider the purchase patterns of products. Specifically,} in the context when prices change frequently, complements can be identified through sufficient co-purchases athey_comtheory_1998, while substitutes have almost no co-purchases. The feature of substitutes that have similar interactions with other products is commonly used in practice ruiz_shopper_2019, chen_studying_2020, and \textcolor{black}{combined with} the almost-no-co-purchase characteristics, it can be used to determine the substitute relationship. \textcolor{black}{Note that the formal definition through cross-price elasticity is expected to emerge from such purchase patterns, where, for example, two products always purchased together implies that the decrease in one’s price will result in an increase of the other’s demand\footnote{{The demand of a product is generally a decreasing function of its own price. This statement is true for the products analysed here.}}. Based on these arguments, we propose the following assumptions 1-4 to characterise complements and substitutes in the product-purchase network.}
\textcolor{black}{In addition, we define noise to be the purchase patterns that are caused by other, often unknown, factors and cannot be explained by complementarity and substitutability. Thus to capture the product relationships and their degrees, it is essential to control the noise effect. In networks, local structure usually refers to the information around a node, and global structure characterises the whole network. For intermediate scales, one often refers to the notion of mesoscale structure, which is associated to groups of nodes that share similar connectivity patterns. Here, we consider particularly the community structure, where groups of nodes are densely connected internally but sparsely connected externally. Within our context, we exploit the fact that the mesoscale structure is much more robust to noise than the local information donnat_scale_2018 Hence, we further propose the following assumptions 5 and 6 to restrict the noise effect. }
\textcolor{black}{Hence, in Sect. (ref), we will determine whether each pair of} products are complements or substitutes by applying significance tests on the number of common neighbours between each pair of nodes in the product-purchase network (i.e. the same transactions they are in, assumptions 1 and 3). This step corresponds to projecting the bipartite network on the product side to form two unweighted unipartite networks, showing the existence of the two relationships. Further, in Sect. (ref), we will quantify the degrees of complementarity and substitutability by local measures based on the product nodes’ neighbourhood structure in the bipartite and projected networks, respectively (assumptions 2 and 4). This step further adds weights to the corresponding unipartite networks.
We propose the following null models on the product-purchase network, to determine whether the number of common neighbours, $cn_{ij}$, between each pair of product nodes $i$ and $j$, is significantly more or significantly less, with significance levels $\alpha_m$ or $\alpha_l$, respectively. Accordingly, two unweighted unipartite networks only consisting of product nodes can be obtained: (i) $\mathbf{A}^{(m)} = (A^{(m)}_{ij}) \in \{0,1\}^{n_p\times n_p}$ where $A^{(m)}_{ij} = 1$ if and only if $cn_{ij}$ is significantly more; (ii) $\mathbf{A}^{(l)} = (A^{(l)}_{ij}) \in \{0,1\}^{n_p\times n_p}$ where $A^{(l)}_{ij} = 1$ if and only if $cn_{ij}$ is significantly less. Finally, by assumptions 1 and 3 in Sect. (ref), two networks indicating the existence of product relationships can be constructed: (i) $\mathbf{A}^{(c)} = (A^{(c)}_{ij}) \in \{0,1\}^{n_p\times n_p}$ where $A^{(c)}_{ij} = 1$ if and only if products $i,j$ are complements; (ii) $\mathbf{A}^{(s)} = (A^{(s)}_{ij}) \in \{0,1\}^{n_p\times n_p}$ where $A^{(s)}_{ij} = 1$ if and only if products $i,j$ are substitutes.
The ER model assumes a fixed probability for each edge to appear, independently of the others erdos_renyi_1959, while bipartite ER models only allow edges between the two subsets of nodes.
In our variant, we assign a different connecting probability $p_{i}$ for each product $i$. Then, the probability that a transaction node is connected with both product nodes $i$ and $j$ is $p_{i}p_{j}$; the number of their common neighbours, $cn_{ij}$, is a random variable $X_{ij}$, s.t. $X_{ij} \sim B(n_t, p_{i}p_{j})$. We further assume $n_t$ is sufficiently large, and approximate the distribution by $N(\mu_{ij}, \sigma_{ij}^2)$, where $\mu_{ij} = n_tp_{i}p_{j}$, $\sigma_{ij}^2 = n_tp_{i}p_{j}(1-p_{i}p_{j})$, from the Central Limit Theorem Grimmett_probability_2001. Hence, $cn_{ij}$ is significantly more if
and is significantly less if
where $\Phi^{-1}(\cdot)$ is the inverse cumulative function of $N(0,1)$, and the maximum likelihood estimate for each $p_i$ is
where $d_i^{(p)}$ is the degree of product node $i$.
The configuration model creates a network with a given degree sequence $\{d_i\}$, by assigning $d_i$ half-edges (or stubs) to each node $i$ and joining two chosen stubs uniformly at random until no more stubs are left newman_networks_2018, newman_randomg_2001. The BiCM takes the bipartite features into account, where two degree sequences are given, dividing the nodes into two subsets, and edges are only allowed between the two subsets of nodes. Note that multi-edges are allowed here, but since we assume finite variance in both degree distributions, they are negligible in large networks (see \textcolor{black}{Appendix (ref) for details}).
The probability of product nodes $i,j$ sharing a transaction node $l$ is
where the superscripts $t,p$ stand for transaction nodes and product nodes respectively, $d_h^{(\cdot)}$ is the degree of node $h$, and $m = \sum_{l=1}^{n_t}d_l^{(t)} = \sum_{i=1}^{n_p}d_i^{(p)}$ is the number of edges (see \textcolor{black}{Appendix (ref)} for details). The variant of bipartite ER models in Sect. (ref) can be seen as an approximation of this model, where we assume that the degree of each transaction node is constant.
The number of common neighbours between product nodes $i$ and $j$, $cn_{ij}$, is the sum of $Bernoulli(p_{ilj})$ over $l$, where $p_{ilj}$ \textcolor{black}{possibly varies for different transaction node $l$}. We assume independence between different transaction nodes to connect with them both. Hence, $cn_{ij}$ is a Poisson binomial random variable, $X_{ij}$, with the mean value
where $<d^{(t)}> = (\sum_{l=1}^{n_t}d_l^{(t)})/n_t$, and $<d^{(t)2}> = (\sum_{l=1}^{n_t}d_l^{(t)2})/n_t$.
\textcolor{black}{The Poisson binomial distribution can be well approximated, with an exact error bound, by a Poisson distribution with the same mean, if the composing Bernoulli probabilities, $p_{ilj}$, are sufficiently small lecam_poisson_1960. Since real networks are sparse, the $p_{ilj}$s are generally small (see our particular case in Appendix (ref)). Hence, we use $Y_{ij}\sim Poisson(\mu_{ij})$ for the significance tests here, and determine} $cn_{ij}$ to be significantly more if
and to be significantly less if
\textcolor{black}{where $F_{ij}(y) = e^{-\mu_{ij}}\sum_{k=0}^{\floor*{y}}\mu_{ij}^k/k!$ is the cumulative distribution function of $Y_{ij}$.}
\textcolor{black}{The two null models are proposed to explain the purchase patterns purely from noise; with more information about the noise factors, one can propose more customised null models to explain more of such patterns. Currently, our null models are only based on difference in product popularity, and the BiCM also uses the heterogeneity in basket sizes: both are sufficiently general to incorporate additional noise factors, but could possibly not be sufficient in their current form, as hidden factors, e.g. correlated preference, could cause more common neighbours between product nodes in the product-purchase networks. Hence, by assumption 5 in Sect. (ref), we accompany these null models with extra rules of significance-level selection: (i) $\alpha_m$ is chosen to be the smallest value that maintains the same community structure as that obtained from a baseline significance level, to exclude the above spurious signal; (ii) $\alpha_l$ is chosen to be the largest such value, in order not to accidentally filter out genuine patterns.}
\textcolor{black}{Finally, we can obtain the unweighted network of complementary relationship, $\mathbf{A}^{(c)}$, and that of substitute relationship, $\mathbf{A}^{(s)}$.} By assumption 1,
by assumption 3,
where $\mathbf{I}_{\{\cdot\}}$ is the element-wise indicator matrix, and $\odot$ represents element-wise (Hadamard) matrix product.
The degrees of complementarity and substitutability matter. A significant relationship is not necessarily a strong relationship, and stronger relationships should be given higher weights to be more dominant in the networks. By assumption 2 in Sect. (ref), the degree of complementarity is not directly correlated with how significant the co-purchase pattern is, but its relative frequency; by assumption 4 in Sect. (ref), neither is the degree of substitutability, which causes the results in Sect. (ref) not to be applicable here. Hence, in this section, we further propose measures to quantify both degrees, in order to convert the unweighted unipartite networks, $\mathbf{A}^{(c)}$ and $\mathbf{A}^{(s)}$, to weighted ones, $\mathbf{W}^{(c)}$ and $\mathbf{W}^{(s)}$, respectively, where $\mathbf{W}^{(c)}, \mathbf{W}^{(s)} \in [0,1]^{n_p\times n_p}$.
We propose several measures for the degree of complementarity by interpreting assumption 2, where the more similar their neighbours in the product-purchase network are, the more complementary they are.
\textcolor{black}{We start from an enhanced version of assumption 6 in Sect. (ref): the noise factors change frequently and erratically so that their bias on the relative number of co-purchases between pairs of products can be neglected. We then propose the following measures,} derived from the weighted cosine similarity between random walkers starting from \textcolor{black}{pairs} of nodes after one step. \textcolor{black}{Specifically,} for each product node $i$, suppose that an impulse $\mathbf{y}_i(0) = \mathbf{e}_i\in \{0,1\}^{n_p}$, with value $1$ only in its $i$-th element, is injected on the product side at time $t=0$. We record the response of the system after a one-step random walk $\mathbf{y}_i(1) = \mathbf{P}^T\mathbf{y}_i(0)$, where $\mathbf{P} = \mathbf{D}^{(p)-1}\mathbf{A}^{(b)T}$, $\mathbf{A}^{(b)} = (A_{li})$ is the biadjacency matrix from the transaction nodes to the product nodes, and $\mathbf{D}^{(p)} = \mathbf{Diag}(d^{(p)}_i)$ is the diagonal matrix with the degrees of product nodes on its diagonal schaub_multiscale_2019. We set the relative importance of each transaction $l$ as the inverse of its degree $d^{(t)}_l$, hence the weighted cosine similarity between \textcolor{black}{the responses $\mathbf{y}_i(1)$ and $\mathbf{y}_j(1)$} is
where $\mathbf{W}_{cos} = \mathbf{Diag}(1/d^{(t)}_l)$ is the weight matrix for the cosine similarity, and $||\mathbf{y}||_{\mathbf{W}} = \sqrt{\mathbf{y}^T\mathbf{W}\mathbf{y}} = ||\mathbf{W}^{1/2}\mathbf{y}||_2$ with $\mathbf{W}$ (symmetric) positive-definite. This \textcolor{black}{introduces the first measures we propose, the} original measure,
where $\mathbf{A}^{(b)} = (A_{li})$, $\{d^{(t)}_l\}_{l=1}^{n_t}$ and $n_t$ are the same as before. Hence, each common neighbour $A_{li}A_{lj}$ between each pair of product nodes $i,j$ \textcolor{black}{in the product-purchase network} is discounted by the degree of the corresponding transaction node $l$, and this quantity is further scaled so that each product is at the maximum level of complementarity to itself, i.e value $1$, in a symmetric manner. A higher value means relatively more common neighbours of lower degrees. Naturally, we also propose the original directed measure,
where each $(i,j)$ entry measures the degree of complementarity of product $i$ to product $j$. Compared with those in the literature, our measures are globally comparable, where node pairs with no common node can also be compared.
\textcolor{black}{The above enhanced version of assumption 6 is reasonable for our choice of fresh food, since the price has been changed frequently and erratically, as required, during the chosen time period. For a general product, in contrast, it would be necessary to implement assumption 6, in order to properly remove the noise effect from} our measures. However, most literature followed the direction of filtering out insignificant edges, rather than removing noise from network measures. In this article, we take an initial step in the latter direction by deducting the mean value with some noise models.
First, we should determine which quantity to subtract the mean from. If we consider the original measure as the geometric mean,
where $\Gamma(i) = \{l: A_{li} = 1\}$ is the set of node $i$'s neighbours in the product-purchase network, then we can propose the corresponding randomised measure,
where $\mathbf{A}^{(b)} = (A_{li})$, $\mathbf{A}^{(r)} = (A^{(r)}_{li})$ is the corresponding biadjacency matrix of a random product-purchase network with each $A^{(r)}_{li}$ being a random variable, and $d^{(r)}_{l} = \sum_{i=1}^{n_p}A^{(r)}_{li}$. The randomised directed measure naturally follows to be
Next, we should determine the noise model. For example, assuming fixed basket sizes (transaction node degrees) and product purchase frequencies (product node degrees), naturally leads us to \textcolor{black}{the} BiCM (cf. Sect. (ref)) as our noise model. In this particular case,
where $d^{(p)}_i$ is the degree of product node $i$, and $m$ is the number of edges in the product-purchase network. With Equations ((ref)), ((ref)) and ((ref)), we accordingly introduce the randomised configuration measure and the randomised configuration directed measure.
\textcolor{black}{Since the measures can be computed for any product pairs, but by assumption 2, only product pairs with value $1$ in $\mathbf{A}^{(c)}$ can be assigned positive degrees. Hence, the weighted adjacency matrix of complement unipartite network is obtained by}
where the subscript $\dagger$ can be $o$, $r$, $od$ or $rd$, \textcolor{black}{and $\mathbf{sim}_{\dagger} = (sim_{\dagger}(i,j))\in [0,1]^{n_p\times n_p}$}. We call the values in $\mathbf{W}^{(c)}$ the complementarity scores, and determine a pair of products to be complements if they have a positive complementarity score.
We propose measures for the degree of substitutability by assumption 4, where the more similar their complements are, the more substitutable they are. \textcolor{black}{Here, we characterise each product by a vector of its complementarity scores with the other products, and use the (unweighted) cosine similarity between these vectors to indicate the degree of substitutability between pairs of products}. Specifically, for \textcolor{black}{a} pair of nodes $i,j$,
where $\mathbf{W}^{(c)} = (W_{ij}^{(c)})$ is the weighted adjacency matrix of complement unipartite network, and $n_p$ is the number of products. The substitutability measures are named after the complementarity measure used in $\mathbf{W}^{(c)}$. For example, with the original measure, we have the original substitutability measure; with the randomised configuration measure, we have the randomised configuration substitutability measure. Naturally, we also propose the directed version, where for \textcolor{black}{a} pair of nodes $i,j$,
\textcolor{black}{where the minimum function is used to guarantee that the measure reaches its maximum value when the complementarity degrees of product $i$ to others are no less than the corresponding degrees of product $j$.}
\textcolor{black}{Since these measures can also be computed for any product pairs, but by assumption 4, only product pairs of value $1$ in $\mathbf{A}^{(s)}$ can be assigned positive degrees. Hence the weighted adjacency matrix of substitute unipartite network is obtained by}
where the subscript $\dagger$ stands for $s$ or $sd$, \textcolor{black}{and $\mathbf{sim}_{\dagger} = (sim_{\dagger}(i,j))\in [0,1]^{n_p\times n_p}$}. We name the values in $\mathbf{W}^{(s)}$ the substitutability scores, and define a pair of products to be substitutes if they have a positive substitutability score.
Note the measures of substitutability are based on those of complementarity \textcolor{black}{and we do not apply extra noise removing strategies here, thus} it is critical that the complementarity degree is thresholded appropriately so that the substitutability degree is not biased by low-complementarity-degree products. \textcolor{black}{Hence, by assumption 5 in Sect. (ref), we accompany these measures with the following rules of threshold selection in analysing real data: (i) the threshold of the complementarity measures, $\theta_c$, is chosen to be the largest value that maintain the same community structure as that obtained from a baseline threshold value; (ii) the threshold of the substitutability measures, $\theta_s$, is chosen to be the smallest such value, for general noise removing purpose.}
Since both the null models in Sect. (ref) and the measures in Sect. (ref) are based on local patterns in the product-purchase network directly or indirectly, so are the complement unipartite network, $\mathbf{W}^{(c)}$, and the substitute unipartite network, $\mathbf{W}^{(s)}$. It is then interesting to go beyond local patterns and explore the features between the node level and the whole network, the mesoscale structure, in such networks, i.e. groups of complements and groups of substitutes.
One important type of mesoscale feature is the community structure, as in Sect. (ref), where communities are groups of nodes that are densely connected internally but sparsely connected externally porter_communities_2009, fortunato_cdg_2010, fortunato_cdn_2016. Various algorithms exist by virtue of interdisciplinary expertise newman_cdeig_2006, traag_leiden_2019, lambiotte_markpvst_2014, rosvall_map_2009, peixoto_bayesian_2019, \textcolor{black}{generally aiming to optimise a quality function with respect to different partitions of the network}. Here, we choose the information-theoretic (hierarchical) map equation rosvall_map_2009, which aims to describe the trajectory of random walkers on the network most efficiently, thereby capturing the right community structure of the underlying network, and is known for being not affected by a common problem of community detection algorithms, the resolution limit kawamoto_estimating_2015. From the detected structure, we will also examine the underlying assumption that groups are clique-like.
Considering the problem of extracting these two kinds of \textcolor{black}{product} groups in the bipartite product-purchase network, it corresponds to a more general problem, role extraction. Roles are general versions of communities, where nodes inside the same role share similar connectivity patterns across the network lorrain_structural_1971, white_graph_1983, holland_expofam_1981. Hence, it contains both classic assortative communities, as described before, and disassortative communities, where nodes are loosely connected internally while densely connected externally. We define the role adjacency as $\mathbf{B} = (B_{rs})$, where
$\mathcal{C}^r$, $r = 1,2,\dots$, are the roles, $n^{(r)} = |\mathcal{C}^r|$ for each role $r$, and $\mathbf{W} = (W_{ij})$ is the (weighted) adjacency matrix of the underlying network. The matrix \textcolor{black}{$\mathbf{B}$} is induced by the maximum-likelihood estimate of the expected weights between nodes \textcolor{black}{inside} the corresponding role(s) in the standard stochastic block model karrer_sbm-cd_2011. Then, $\mathcal{C}^r$ is an assortative community if $B_{rs} \ll B_{rr},\ \forall s\ne r$; $\mathcal{C}^r$ is a disassortative community if $B_{rs} \gg B_{rr},\ \exists s$, \textcolor{black}{i.e. community $r$ is much more densely connected with at least one other community $s$ than itself}. Thus, our set of methods establishes an indirect solution to the role extraction in bipartite networks. We call our detected groups of complements, the complement roles, and our detected groups of substitutes, the substitute roles.
We start from the product hierarchy information to characterise both complement roles and substitute roles, and then check if the characteristics are consistent with the common understanding of complements and substitutes. Specifically, we exclusively use the L3 product hierarchy, consisting of fruit (F), organic produce (OP), prepared produce (PP), salad (S), and vegetable (V).
Next, we use the correspondence between flavour compounds and products to compute the Jaccard index, i.e. the relative number of shared flavour compounds, $rf_{ij}$, between each pair of products $i$ and $j$,
where $C(i)$ is the set of all flavour compounds in product i. We then consider the cases in which $rf_{ij} = 0$ and $rf_{ij} = 1$, and check if the complementary pairs have a higher probability to share no flavour compounds and if the substitute pairs have a higher probability to share all their flavour compounds. Furthermore, we examine the relationship between $rf_{ij}$ and $W_{ij}^{(c)}, W_{ij}^{(s)}$, in terms of the Pearson correlation, as well as the Spearman correlation.
Subsequently, we use the recipe data to evaluate the relative number of shared recipes, $rr_{ij}$, between each pair of products $i$ and $j$,
where $R(i)$ is the set of all recipes including product i, and we set $rr_{ij} = 0$ if products $i$ and $j$ are matched to the same ingredient. We then assess if the complementary pairs and substitute pairs have significantly higher and lower probabilities to co-appear in relatively more recipes, respectively. This is achieved by the Mann-Whitney-Wilcoxon (MWW) tests, where
and $X$, $Y$ are two independent random variables mann_two_variable_test, fay_wmw-t_2010. For example, let $X$ be the relative number of shared recipes from all product pairs $\{rr_{ij}\}$, and $Y$ be that from only complementary pairs $\{rr_{ij}: W_{ij}^{(c)} > 0\}$. Then, we will use the alternative hypothesis $H_1: P(X > Y) < P(Y > X)$. Similarly, we also explore the relationship between $rr_{ij}$ and $W_{ij}^{(c)}, W_{ij}^{(s)}$.
Finally, we apply our overall framework to the recipe data, where we treat recipes as transactions and ingredients as products. This stems from the hypothesis that customers purchase products to cook dishes following recipes, and thus the recipe data should be a restriction of the sales data. We compare the values of complementarity scores by recipes, the recipe complementarity scores $\mathbf{W}^{(cr)} = (W_{ij}^{(cr)})$, with those by sales, $\mathbf{W}^{(c)}$, and similarly, the recipe substitutability scores $\mathbf{W}^{(sr)} = (W_{ij}^{(sr)})$, with $\mathbf{W}^{(s)}$. Note that we set $W_{ij}^{(cr)} = 0$ and $W_{ij}^{(sr)} = 1$ if product $i$ and $j$ are matched to the same ingredient. We finish the validation stage by comparing the role assignments (of products) from both datasets, where $l$ complement roles and $l_1$ substitute roles (from the recipe data) are obtained from applying community detection on $\mathbf{W}^{(cr)}$ and $\mathbf{W}^{(sr)}$, respectively. We construct extra $l_0$ substitute roles by grouping together products that are matched to the same ingredients, for reference; see Fig. (ref) for details.
Before investigating noisy real data, we first validate our overall framework in a controlled "ideal world" where the relationship between products is known. Specifically, we simulate a consumer population characterised by a set of rules in this world, and ask whether our null models capture the right relationship between each pair of products, whether our measures give the right degree between them, and finally, whether our complement and substitute roles provide insights into the groups of complements, and the groups of substitutes, respectively.
The simulated world is summarised as follows, similar to the one in ruiz_shopper_2019.
With these specifications, we simulate $1000$ transactions from this customer population. For a single transaction, each independent product has an $80\%$ chance of being marked up to a high price; there is a $50\%$ chance that all complementary pairs are of low price, a $10\%$ chance that all are of high price, and accordingly a $40\%$ chance that some are marked up, where the lowest priced one is chosen uniformly at random.
We provide the complementarity scores, $\mathbf{W}^{(c)}$, induced by the original measure, $\mathbf{sim}_o$, and by the randomised configuration measure, $\mathbf{sim}_r$, together with the number of co-purchases, $(cn_{ij})$, in Fig. (ref). We choose the variant of ER model as the underlying null model, since it better explains the noise here\footnote{{Hence, the significance level for the significantly more co-purchases, $\alpha_c$, for the variant of ER model can be chosen as high as $0.9$ with the same results. While for the BiCM, a much lower significance level (e.g. $10^{-4}$ for $\alpha_c$) is needed in order to extract the true product relationships.}}. Note that independent products are bought more frequently, and their numbers of co-purchases with other products are fairly similar to those \textcolor{black}{within} complementary pairs. However, our extracted complementary pairs $\{(i,j): W_{ij}^{(c)} > 0\}$ successfully retrieve the ground-truth complementary pairs. Accordingly, our extracted substitute pairs $\{(i,j): W_{ij}^{(s)} > 0\}$ successfully retrieve the ground-truth substitute pairs. Furthermore, the complementarity scores of the hot-dog-and-hot-dog-bun complementary pairs is between $0.3$ and $0.5$, and those of the taco-shell-and-taco-seasoning complementary pairs is around $0.5$. These values are approaching the inverse of the number of products in the corresponding substitute groups, which is consistent with the assuming complete substitution.
Finally, our substitute roles exactly agree with the ground-truth substitute groups; see Fig. (ref). Our complement roles reproduce the ground-truth complementary pairs including their corresponding groups of substitutes. Note that there are no groups of complements beyond the pairwise relationship.
This example demonstrates the ability of our overall framework to determine both product relationships and their corresponding degrees, which paves the way for us to continue the analysis on real-world data. From a mesoscale perspective, our complement roles and substitute roles have much overlap with the groups of complements and those of substitutes, respectively. Furthermore, the fact that we already have complement roles involving substitutes indicates that the interaction between the two relationships is not negligible. For instance, it is entirely possible that we may find substitute roles including complements in real data.
\textcolor{black}{Hereafter, we use the variant of ER model as the underlying null model, since its assumptions are generally applicable in real-world purchases, and we only show the results from the original measure, because both have very similar behaviour; see Appendix (ref) for the parameter calibration and the results from the randomised measure.} We \textcolor{black}{first} examine the ranking power of our scores, $\mathbf{W}^{(c)}$ and $\mathbf{W}^{(s)}$, by checking the top complementary pairs and substitute pairs for each product. This is done by choosing several query products $j$ at random, and output the products of the three highest complementarity scores $W_{ij}^{(c)}$ and the ones of the three highest substitutability scores $W_{ij}^{(s)}$; see Table (ref) for one run. The substitute pairs of scores $>0.1$ largely agree with common sense\footnote{{Here we refer to the notion that products that are essentially the same are substitutes, for example, Brand A apples and Brand B apples.}}. For example in Table (ref), the top substitute of organic blueberries is blueberries, and the top substitutes of salad tomatoes are other types of tomatoes. Additionally, the ranking indicates that common-sense substitutes have high complementarity scores with the same products. For example salad tomatoes, baby plum tomatoes and tomatoes on the vine are the top three complements of loose cucumbers. These findings justify our assumption 3 in Sect. (ref). There are also some nontrivial substitutes, of lower score values, from general understanding, which we will discuss in Sect. (ref).
We proceed for the mesoscale structure, i.e. the complement roles and substitute roles. From an averaged perspective, the complement roles and the substitute roles constitute assortative communities in the unipartite networks $\mathbf{W}^{(c)}$ and $\mathbf{W}^{(s)}$, respectively; substitute roles form disassortative communities in $\mathbf{W}^{(c)}$; see Fig. (ref). The latter observation also justifies \textcolor{black}{the} assumption 3. Furthermore, the overlap between the two roles is not negligible, with the normalised mutual information (NMI vinh_information_nodate) $0.49$. Hence, as mentioned in Sect. (ref), substitutes may appear in the same complement role by their strong complements, and complements may be assigned to the same substitute role for their strong substitutes.
Finally, we explore the internal structure of complement roles and substitute roles. Generally, strong complements\footnote{{Note we determine two products $i,j$ as complements if $W_{ij}^{(c)} > 0$, and measure their degree of complementarity (from weak to strong) by the value of $W_{ij}^{(c)}$; substitutes are treated similarly.}} do not tend to form complete graphs in the complement unipartite network $\mathbf{W}^{(c)}$, where there are many products that are complements of the same products but are not complements of each other. For example, blueberries (Blueb) and organic blueberries (Or Blueb) in the complement role of berries (3) are substitutes, but both are complements of raspberries (Raspb), stawberries (Strawb), etc; see Fig. (ref). There are also cases in which they constitute some complete graph, and further exploration indicates that these products are highly likely to be consumed together. For example, mushroom stir fry (Mushroom SF), vegetable and beansprout stir fry (V Beansprout SF), and egg noodles form a triangle in the complement role of stir-fry (9); see the blue polygon in Fig. (ref).
Strong substitutes are expected to form complete graphs in the substitute unipartite network $\mathbf{W}^{(s)}$, and our results are largely consistent with the expectation. For example, loose Braeburn apples (LB Apples), loose Pink Lady apples (LPL Apples), and bagged organic Gala apples (BOrG Apples) constitute a triangle in the substitute role of apples (23); see the blue polygon in Fig. (ref). Note this expectation is only valid if the substitutes are consumed for the same purpose; if this assumption is violated, seemingly substitute products may end up being complements. For example, loose brown onions (LBr Onions) and loose red onions (LR Onions) in the substitute role of onions (4) are both substitutes of products such as bagged red onions (BR Onions) and bagged organic brown onions (BOrBr Onions), but are complements of each other; see Fig. (ref). The difference between their quantities and their common substitutes may be the key factor here. Likewise, even with the common substitute bagged organic Gala apples (BOrG Apples), loose ripe pears (LR Pears) is a complement of loose Pink Lady apples (LPL Apples), loose Braeburn apples (LB Apples) and loose Gala apples (LG Apples). The above observations confirms the complexity of the interaction between complements and substitutes.
The distribution of L3 categories in each complement role is consistent with products being complements; see Fig. (ref). Most complement roles involve more than one category, which could be explained by the complementarity across categories. For example, the complement role of nuts & fruits (2) contains both fruit and prepared produce, the complement roles of berries & grapes (3) and of grapes & oranges (5) consist of both fruit and organic produce, and the complement role of potatoes, beans & carrots (6) includes both prepared produce and vegetables. There are also complement roles only involving one category, and the related products are either in fruit or in the prepared produce category. Further, this is in agreement with the notion that products in prepared produce, for instance prepared vegetables and vegetable dips, go well together; similar for products in fruit.
The proportion of L3 categories in each substitute role also accords with products being substitutes; see Fig. (ref). Some of them only or mostly involve prepared produce, and some others largely consist of fruit, such as the substitute role of apples (23). This agrees with the tendency of grouping products into categories based on shared characteristics. Other substitute roles contain more than one category, with one of them being prepared produce. For example, the substitute role of grapes (5) includes both fruit and prepared produce, the substitute role of carrots (13) comprises both prepared produce and vegetables, the substitute role of peppers (19) involves prepared produce, salad\footnote{{Here the salad category contains products like cucumber, pepper, lettuce and tomatoes.}} and vegetables, and the substitute role of avocado salad (25) is composed of fruit, prepared produce and salad. Further investigation shows that products in prepared produce include fresh-cut fruits, prepared salads and prepared vegetables, i.e. prepared versions of products in fruit, salad and vegetable categories.
We observe that the substitute pairs have a significantly higher probability to share all their flavour compounds with each other, i.e, $rf_{ij} = 1$, than all product pairs, while complementary pairs have a significantly higher probability to share no flavour compounds with each other, \textcolor{black}{i.e, $rf_{ij} = 0$}; see Fig. (ref). These characteristics are consistent with the functional definition of complements and substitutes: complements are consumed together, thus tend to have different flavours in order to accompany each other; while substitutes can replace each other, thus tend to have the same flavours. The distributions of $rf_{ij}$ values between $0$ and $1$ have roughly the same shapes for the three types of pairs.
Further, we investigate the correlations between the relative number of shared flavour compounds $(rf_{ij})$ and \textcolor{black}{the score values $(W_{ij}^{(c)}), (W_{ij}^{(s)})$; see Table (ref)}. The Pearson correlation indicates that the product pairs of higher substitutability scores have a significant tendency to share larger portions of their flavour compounds, while the patterns when changing the complementarity scores is more heterogeneous, \textcolor{black}{with} a mild negative correlation between the ranking of the complementarity scores and that of the relative number of shared flavour compounds.
We then discern that the complementary pairs have higher probability to co-appear in relatively more recipes, $\{rr_{ij}: W_{ij}^{(c)} > 0\}$, than all product pairs, $\{rr_{ij}\}$, while the substitute pairs have \textcolor{black}{lower} probability to co-appear in relatively \textcolor{black}{more} recipes, $\{rr_{ij}: W_{ij}^{(s)} > 0\}$; see Fig. (ref). Both trends are significant by the MWW test (p-values: $2.8\times 10^{-123}$ and $3.1\times 10^{-4}$ for the complementary pairs and the substitute pairs respectively). These features also accord with the interpretation of complements or substitutes from the cooking perspective: complements go \textcolor{black}{well} with one another, thus are more likely to be appear in the same recipe together; while substitutes can be used in place of each other, thus tend to be cooked together with some others but not each other.
Moreover, we examine the correlations between the relative number of shared recipes $(rr_{ij})$ and \textcolor{black}{the score values; see Table (ref)}. The Spearman correlation suggests that product pairs of higher rankings in the complementarity scores tend to co-appear in relatively more recipes, which agrees with the Pearson correlation. The trend when increasing the substitutability ranking of product pairs is a mild propensity towards co-appearing in relatively less recipes.
Additionally, we explore the correlations between our complementarity scores $(W_{ij}^{(c)})$ and the recipe complementarity scores $(W_{ij}^{(cr)})$, and between our substitutability scores $(W_{ij}^{(s)})$ and the recipe substitutability scores $(W_{ij}^{(sr)})$; \textcolor{black}{see Table (ref)}. The Spearman correlations \textcolor{black}{of both score pairs indicate significant positive relationships within each pair, which is consistent with the information suggested by their Pearson correlations}.
Finally, we compare the complement and substitute role assignments from different data sources, in particular the sales and recipe data, \textcolor{black}{where we use the NMI and adjusted mutual information (AMI vinh_information_nodate) to measure the consistency between role assignments}; see Table (ref). Our substitute roles (from the sales data) are more similar to the complete substitution, i.e. $l_0$ substitute roles obtained from the recipe data. Although our complement roles are more in agreement with the $l_0$ substitute roles than the $l$ complement roles by NMI, this may be caused by the number of $l_0$ substitute roles being larger than that of $l$ complement roles, since the AMI shows a significant opposite direction. \textcolor{black}{To conclude,} the relatively large NMI and AMI values demonstrate the consistency between the extracted product relationship from these two different sources, and also provide evidence that customers buy products corresponding to ingredients in particular recipes.
Extracting complements and substitutes is part of the broad family of unsupervised learning problems, since the relationship between any pair of products is unknown hastie_unsupervised_2009 (see \textcolor{black}{Appendix (ref)} for the detailed formulation). This makes the validation process ill-defined, as there is no ground truth. Hence in our study, not only do we compare the results with heuristic arguments based on common understanding of the product relationships, but we also resort to external data sources -- the product hierarchy data, the flavour compound and recipe data. Since these datasets focus on different aspects of the products, this is a well-grounded validation process. The seemingly heterogeneous observations from such datasets are well-explained by the product relationships, and thus provide further validation of our results.
Our assumption that complements are products purchased together significantly more frequently could appear simplistic, because it does not explicitly exclude other factors that may result in co-purchases, e.g. correlated preference. However, from a network perspective, these effects are expected to be removed implicitly by the statistical tests associated \textcolor{black}{with} our null models. Moreover, we also propose a family of randomised measures to explicitly remove various sorts of noise \textcolor{black}{effects}. Compared with the state-of-the-art, another advantage offered by a network perspective is the definition of exact criteria to determine whether products are complements or substitutes. \textcolor{black}{In this article}, we have shown that both relationships can be effectively extracted from the simple notions of whether two products are purchased together significantly more frequently, or less frequently but share common strong complements (assumptions 1 and 3 in Sect. (ref)).
Once unipartite networks of products have been built, we may proceed from pairwise relationships to the mesoscale structure, via the notion of complement roles and substitute roles. The observations justify our assumption \textcolor{black}{3} that substitutes share common strong complements. They also indicate that complement products do not generally constitute complete graphs, while substitute products typically do, though such complete graphs can be destroyed, \textcolor{black}{for example,} by substitutes consumed for different purposes. These results demonstrate the possibility of the complement relationship to go beyond pairwise relationship, and also the complex interaction between complements and substitutes.
Finally, let us emphasise that we only use basket data to extract the product relationships, without additional information such as the customer profile and the price change, information that are typically required for existing methods and may cause privacy issues de2015unique. Our method to extract complements and substitutes is then solely based on sales data, as stated in the assumptions in Sect. (ref). Hence, the quality of our results is dependent on the mutual information between the sales data (through our assumptions) and the criteria, where some discrepancy may exist. For example, there may be products that are not generally recognised as complements, but are purchased together significantly more frequently, so are treated as "complements" from the sales angle. However, most applications of product relationships are from a sales perspective, such as stocking shelves and marketing in sales promotions, and our validation further confirms the rationality of our extracted complements and substitutes.
For these reasons, we believe that the network-based approach is a promising research avenue within the field of retail. Among the research directions that this article has opened, \textcolor{black}{an important one would be to consider the bipartite network from a temporal perspective, in order to explore further the connection between structure and cross-elasticity (see Appendix (ref))}. It would also be interesting to design a method that directly uncovers the degrees of complementarity and substitutability from the bipartite network, without any intermediary steps as it is done here, \textcolor{black}{and to explore more of the directed scores, since our focus is on the symmetric ones here. Another is to characterise the products by their centrality in the projected networks, for instance by the average complementarity and substitutability scores of their relations. Moreover,} our current analysis focused on fresh food where prices changed frequently throughout the period. \textcolor{black}{Yet}, we did not explicitly include price \textcolor{black}{as a} factor, but either ignored its \textcolor{black}{bias} or removed it by some random models athey_comtheory_1998. In order to analyse a more general range of products in the future, it \textcolor{black}{would be} necessary to incorporate price information in our framework in a meaningful way.
We thank Yong-Yeol Ahn for providing the flavour compound and recipe data, and for his assistance.
YT is supported by the EPSRC Centre for Doctoral Training in Industrially Focused Mathematical Modelling (EP/L015803/1) in collaboration with Tesco PLC.
AMI, adjusted mutual information; BiCM, bipartite configuration model; ER, Erd\H{o}s-R\'enyi; ML, machine learning; NMI, normalised mutual information; MWW, Mann-Whitney-Wilcoxon.
The flavour compound and recipe data is available from Ahn_flavor_2011, yy_flavour_2011. The other datasets generated and analysed during the current study are not publicly available due to the terms of use in Tesco PLC.
The authors declare that they have no competing interests.
All authors read and approved the final manuscript.