Structure and Attribute Based Graph Partitioning As Applied in Walmart Assortment Analytics

Walmart provides a huge assortment of products to its customers. For many analyses, it is useful to group products within similar substitutable groups rather than considering them independently. One such outcome of the analysis is a tree like structure, called the Customer Behavioral Tree (referred hereafter as CBT) with the items as the leaf-nodes. The tree is such that, child nodes of the same parent must be more substitutable than the child nodes of different parents (represented best by a dendrogram). This CBT acts as a useful grouping for all further assortment and pricing decisions. While grouping millions of items itself is challenging, complexity multiplies as Walmart has 4500 odd stores in the US, with more than 90 departments, aggregating to around 7200 odd categories, serving to millions of customers. Apart from the scale of Walmart, some categories, notably General Merchandise categories, don't have sufficient repeat purchase information for a given household, leading to restriction in the usability of market basket analysis and association rules. Obviously, people would not buy items like Hammers or Infant Furniture, as frequently as they would buy Yogurt or Canned Beans. We wanted an algorithm that would hold irrespective of the sparsity of POS data, hence the introduction of Graph Partitioning