Octet: Online Catalog Taxonomy Enrichment with Self-Supervision

There is rich structural information for online catalog taxonomy enrichment which comes from two sources. First, the neighborhood (e.g., parent and siblings) of a node $v\in V$ on $T$ can serve as a meaningful supplement for the semantics of $v$. For example, one may not have enough knowledge of node $v=$ “Makgeolli” (Korean rice wine); but if she perceives that “Sake” (Japanese rice wine) is $v$’s sibling and “Wine” is $v$’s parent, she would have more confidence in considering “Makgeolli” as one type of “Alcoholic Beverages”. Second, there exist abundant user behavior data, providing even richer structural information than that offered by the core taxonomy $T$. Specifically, items $I$ are associated with the existing taxonomy nodes $V$. New terms $V^{\prime}$ are related to items $I$ and user queries $Q$ since $V^{\prime}$ are extracted from the two sources. Furthermore, $I$ and $Q$ are also connected via clicks. Based on the observations above, we propose to learn a structural term pair representation to capture the structure in the core taxonomy and the query-item-taxonomy interactions as follows.

Graph Construction. We construct a graph ${\mathcal{G}}$ where the nodes consist of the existing terms $v\in V$ and new terms $v^{\prime}\in V^{\prime}$. There are two sets of edges: one set is the same as $R$ in the core taxonomy $T$, which captures the ontological structure in $T$. The other set leverages the query-item-taxonomy interactions: for each new term $v^{\prime}\in V^{\prime}$, we find the user queries $Q_{v^{\prime}}$ that mention $v^{\prime}$ and collect the clicked items $I_{Q_{v^{\prime}}}$ in the queries $Q_{v^{\prime}}$. Then, we find the taxonomy nodes $\{v_{i}\}$ that $I_{Q_{v^{\prime}}}$ is associated with. Finally, we add an edge between each $(v_{i},v^{\prime})$ pair. For instance, when determining the parent of a new term “Figs”, we find that some queries mentioning “Figs” lead to clicked items associated with the taxonomy node “Fruits”, evincing strong relations between the two terms.

Graph Embedding. We leverage graph neural networks (GNNs) to aggregate the neighborhood information in ${\mathcal{G}}$ when measuring the relationship between a term pair. Specifically, we take the rationales in relational graph convolutional networks (RGCNs) (Kipf and Welling, 2016; Schlichtkrull et al., 2018). Let ${\mathcal{R}}$ denote the set of relations, including ($r_{1}$) The neighbors of $v$ on the core taxonomy $T$. The neighbors can be the (grand)parents or children of $v$ and we compare different design choices in Sec. 4.4.2; ($r_{2}$) the interactions between $v\in V$ and $v^{\prime}\in V^{\prime}$ discovered in user behavior. We confine the interactions to be unidirectional (from $v$ to $v^{\prime}$) since the terms $v\in V$ are already augmented with $r_{1}$ while there might be noise in the user behavior; and ($r_{3}$) the self-loop of node $v$. The self-loop of $v$ ensures that the information of $v$ itself is preserved and those isolated nodes without any connections can still be updated using its own representation.

Relationship Measure. One straightforward way of utilizing the structural representation is to use the graph embeddings ${\bm{g}}_{v}$ and ${\bm{g}}_{v^{\prime}}$ as the representation of term $v$ and $v^{\prime}$. Instead, we propose to measure the relationship between a term pair explicitly by cosine similarity and norm distance (more details in App. A). We denote the relationship measure between two embeddings as $s({\bm{v}},{\bm{v}}^{\prime})$. One benefit of using $s({\bm{g}}_{v},{\bm{g}}_{v^{\prime}})$ is that empirically we observe $s({\bm{g}}_{v},{\bm{g}}_{v^{\prime}})$ alleviates overfitting compared with directly using ${\bm{g}}_{v}$ and ${\bm{g}}_{v}^{\prime}$. Also, using $s({\bm{g}}_{v},{\bm{g}}_{v^{\prime}})$ makes the final output size much smaller and reduces the number of parameters in the following layer significantly.

We use the word embedding ${\bm{w}}_{v}$ of each term $v$ to capture its semantics. For grouping nodes consisting of several item types (e.g., “Fresh Flowers & Live Indoor Plants”) and multi-word terms with qualifiers (e.g., “Fresh Cut Bell Pepper”), we employ dependency parsing to find the noun chunks (“Fresh Flowers”, “Live Indoor Plants”, and “Fresh Cut Bell Pepper”) and respective head words (“Flowers”, “Plants”, and “Pepper”). Intuitively, $(v,v^{\prime})$ tends to be related as long as one head word of $v$ is similar to that of $v^{\prime}$. We thus use the relationship measure $s({\bm{v}},{\bm{v}}^{\prime})$ defined in Sec. 3.3.1 to measure the semantic relationship of the head words: ${\bm{H}}(v,v^{\prime})=\max_{i,j}s({\bm{w}}_{\text{head}^{i}(v)},{\bm{w}}_{\text{head}^{j}(v^{\prime})})$, where ${\bm{w}}_{\text{head}^{i}(v)}$ denotes the word embedding of the i-th head word in the term $v$. Finally, the overall semantic representation ${\bm{S}}(v,v^{\prime})$ is defined as ${\bm{S}}(v,v^{\prime})=[{\bm{H}}(v,v^{\prime}),{\bm{w}}_{v},{\bm{w}}_{v^{\prime}}]$, where “,” denotes the concatenation operation.

String-level measures prove to be very effective in hypernymy detection (Bansal et al., 2014; Bordea et al., 2016; Gupta et al., 2017; Mao et al., 2018). For online catalog taxonomies, we also find many cases where lexical similarity provides strong signals for hypernymy identification. For example, “Black Tea” is a hyponym of “Tea” and “Fresh Packaged Green Peppers” is a sibling of “Fresh Packaged Orange Peppers”. Therefore, we take the following lexical features (Mao et al., 2018) to measure the lexical relationship between term pairs: Ends with, Contains, Suffix match, Longest common substring, Length difference, and Edit distance. Values in each feature are binned by range and each bin is mapped to a randomly initialized embedding, which would be updated during model training. We denote the set of lexical features by ${\mathcal{M}}$ and compute lexical representation as the concatenation of the lexical features: ${\bm{L}}(v,v^{\prime})=[{\bm{L}}_{i}(v,v^{\prime})]_{i\in{\mathcal{M}}}$.

For each term pair $(v,v^{\prime})$, we generate a heterogeneous term pair representation ${\bm{R}}(v,v^{\prime})$ by combining the representations detailed above. ${\bm{R}}(v,v^{\prime})$ captures several orthogonal aspects of the term pair relationship, which contribute to hypernymy detection in a complementary manner (Sec. 4.4.1). To summarize, the structural representation models the core taxonomy structure as well as underlying query-item-taxonomy interactions, whilst the semantic and lexical representations capture the distributional and surface information of the term pairs, respectively. We further calculate $s({\bm{v}},{\bm{v}}^{\prime})$ between the graph embedding ${\bm{g}}_{v}$ (${\bm{g}}_{v}^{\prime}$) of one term and the word embedding ${\bm{w}}_{v^{\prime}}$ (${\bm{w}}_{v}$ ) of the other term in the term pair, which measures the relationship of the term pair in different forms and manifests improved performance. Formally, the heterogeneous term pair representation ${\bm{R}}(v,v^{\prime})$ is defined as follows.

Similar to prior works (Shwartz et al., 2016; Mao et al., 2018), we feed ${\bm{R}}(v,v^{\prime})$ into a two-layer feed-forward network and use the output after the sigmoid function as the probability of hypernym relationship between $v$ and $v^{\prime}$. To train the term attachment module, we permute all the term pairs $(v_{i},v_{j})$ in $V$ as training samples and utilize the existing hypernym pairs $R$ on $T$ for self-supervision – the pairs in $R$ are regarded as positive samples and other pairs are negative. The heterogeneous term pair representation, including the structural representation, is learned in an end-to-end fashion. We use binary cross-entropy loss as the objective function due to the classification formulation. An alternative formulation is to treat term attachment as a hierarchical classification problem where the positive labels are all the ancestors of the term (instead of only its parent). We found, however, that hierarchical classification does not outperform standard classification and thus opt for the simpler formulation following (Wang et al., 2014; Bansal et al., 2014). For inference, we choose $v_{i}\in V$ with the highest probability among all the permuted term pairs $(v_{i},v^{\prime})$ as the predicted hypernym of $v^{\prime}$.

We take the Grocery & Gourmet Food taxonomy (2,163 terms) on Amazon.com as the major testbed for term extraction. We design three different evaluation setups with closed-world or open-world assumption as follows.

Closed-world Evaluation. We first conduct a closed-world evaluation that holds out a number of terms on the core taxonomy $T$ as the virtual $V^{\prime}$. In this way, we can ensure that the test set follows a similar distribution as the training set and the evaluation can be done automatically. Specifically, we match the terms on $T$ with the titles of active items belonging to Grocery & Gourmet Food (2,995,345 in total).²²2We also observed positive results on term extraction from user queries at Amazon.com but omit the results in the interest of space. 948 of the 2,163 terms are mentioned in at least one item title and 948,897 (item title, term) pairs are collected. We split the pairs by the 948 matched terms into training set $V$ and test set $V^{\prime}$ with a ratio of 80% / 20% and evaluate term recall on the unseen set $V^{\prime}$. Splitting the pairs by terms (instead of items) ensures that $V$ and $V^{\prime}$ have no overlap, which is much more challenging than typical named entity recognition (NER) tasks but resembles the real-world use cases for online catalog taxonomy enrichment.

Open-world Evaluation. Open-world evaluation tests on new terms that do not currently exist in $T$, which is preferable since it evaluates term extraction methods in the same scenario as in production. The downside is that it requires manual annotations as there are no labels for the newly extracted terms. Therefore, we ask experts and workers on Amazon Mechanical Turk (MTurk) to verify the quality of the new terms. As we would like to take new terms with high confidence for term attachment, we ask our taxonomists to measure the precision of top-ranked terms that each method is most confident at. The terms that are already on the core taxonomy $T$ are excluded and the top 100 terms of each compared method are carefully verified. To evaluate from the average customers’ perspective, we sample 1,000 items and ask MTurk workers to extract the item types in the item titles. Different from expert evaluation, items are used as the unit for evaluation rather than terms. Precision and recall, weighted by the votes of the workers, are measured. More details of crowdsourcing are provided in App. C.

Baseline Methods. For the evaluation on term extraction, we compare with two approaches widely used for taxonomy construction, namely noun phrase (NP) chunking and AutoPhrase (Shang et al., 2018). Pattern-based methods (Liu et al., 2019) and classification-based methods with simple n-gram and click count features (Wang et al., 2014) perform poorly in our preliminary experiments and are thus excluded. More details and discussions of the baselines are provided in App. B.

For closed-world automatic evaluation, we calculate recall@K and show the comparison results in Fig. 3 (Left). We observe that Octet consistently achieves the highest recall@K on the held-out test set. The overall recall of all compared methods, however, is relatively low. Nevertheless, we argue that the low recall is mainly due to the wording difference between the terms in the core taxonomy $T$ and item titles. As we will demonstrate in the open-world evaluation below, many extracted terms are valid but not on $T$, which also confirms that $T$ is very sparse and incomplete.

For term attachment, we also conduct both closed-world and open-world evaluations, which involves ablating the core taxonomy $T$ and attaching newly extracted terms, respectively. In contrast, most of prior studies (Bansal et al., 2014; Jurgens and Pilehvar, 2016; Mao et al., 2018) only perform closed-world evaluation.

Closed-world Evaluation. We take four taxonomies actively used in production as the datasets: Grocery & Gourmet Food, Home & Kitchen, and Beauty & Personal Care taxonomies at Amazon.com, and the Business Categories at Yelp.com.³³3The taxonomies are available online. We use five-month user behavior logs on Amazon.com for structural representation and do not leverage user behavior on Yelp.com due to accessibility. See App. A for more details on data availability. Amazon Grocery & Gourmet Food is used for framework analysis unless otherwise stated. As the taxonomies are used in different domains and constructed according to their own business needs, they exhibit a wide spectrum of characteristics and almost have no overlap. Considering the real-world use cases where fine-grained terms are missing, we hold out the leaf nodes as the new terms $V^{\prime}$ to be attached as in (Jurgens and Pilehvar, 2016). We split $V^{\prime}$ into training, development, and test sets with a ratio of 64% / 16% / 20%, respectively. Detailed statistics of the datasets can be found in Table 3. Note that if we regard term attachment as a classification problem, each class would have very few training samples (e.g., 1193 / 298 $\approx$ 4 in Amazon Grocery & Gourmet Food), which calls for a significant level of model generalizability.

Open-world Evaluation. We conduct an open-world evaluation for term attachment on Amazon Grocery & Gourmet Food. Specifically, we ask the taxonomists to identify valid new terms among those discovered in the term extraction stage with frequency greater than 20. 106 terms are thus labeled as valid. We then ask the taxonomists to attach the 106 terms manually to the core taxonomy as ground truth and evaluate systems on these new terms with the same criteria as in the closed-world evaluation.

Evaluation Metrics. We use Edge-F1 and Ancestor-F1 (Mao et al., 2018) to measure the performance of term attachment. Edge-F1 compares the predicted edge $(v,v^{\prime})$ with the gold edge $(p(v^{\prime}),v^{\prime})$, i.e., whether $v=p(v^{\prime})$. We use $P_{\text{Edge}}$, $R_{\text{Edge}}$, and $F1_{\text{Edge}}$ to denote the precision, recall, and F1-score, respectively. In particular, $P_{\text{Edge}}=R_{\text{Edge}}=F1_{\text{Edge}}$ if the number of predicted edges is the same as gold edges, i.e., when all the terms in $V^{\prime}$ are attached. Ancestor-F1 is more relaxed than Edge-F1 as it compares all the term pairs $(v_{\text{sys}},v^{\prime})$ with $(v_{\text{gold}},v^{\prime})$, where $v_{\text{sys}}$ represents the terms along the system predicted path (ancestors) to the root node, and $v_{\text{gold}}$ denotes those terms on the gold path. Similarly, we denote the ancesor-based metrics as $P_{\text{Ancestor}}=\frac{|v_{\text{sys}}\wedge v_{\text{gold}}|}{|v_{\text{sys}}|}$ and $R_{\text{Ancestor}}=\frac{|v_{\text{sys}}\wedge v_{\text{gold}}|}{|v_{\text{gold}}|}$.

Baseline Methods. As discussed earlier, there are few existing methods for taxonomy enrichment. MSejrKu (Schlichtkrull and Alonso, 2016) is the winning method in the SemEval-2016 Task 14 (Jurgens and Pilehvar, 2016). HiDir (Wang et al., 2014) is the state-of-the-art method for online catalog taxonomy enrichment. In addition, we compare with the substring method Substr (Bordea et al., 2016), and I2T that finds one’s hypernym by examining where its related items are assigned to. Two naïve baselines are also tested to better understand the difficulty of the task following convention (Bansal et al., 2014; Jurgens and Pilehvar, 2016), where Random attaches $v^{\prime}\in V^{\prime}$ randomly to $T$ and Root attaches every term to the root node of $T$. More details of the baselines are in App. B.

We first evaluate different methods under the closed-world assumption (Tables 4 &  5). We observe that the Edge-F1 of two naïve baselines is very low since there are hundreds of $v\in V$ as candidates. The performance of I2T is similar to Substr but still far from satisfactory, implying that there might be noise in the matching between $V^{\prime}$ and $I$, and the associations between $I$ and $V$. HiDir (Wang et al., 2014) and MSejrKu (Schlichtkrull and Alonso, 2016) achieve better performance than other baselines, especially in Edge-F1, while Octet outperforms all the compared methods by a large margin on both development and test sets across all of the four domains.

We analyze the contribution of each representation for the term pair (Table 8). As one can see, only using word embedding (W) does not suffice to identify hypernymy relations while adding the semantics of head words (H) explicitly boosts the performance significantly. Lexical (L) features are very effective and combining lexical representation with semantic representation (L + W + H) brings 17.2 absolute improvement in Edge-F1. The structural information is very useful in that even if we use word embedding (W) as the input of the structural representation (G), the Edge-F1 improves by 4.8x and the Ancestor-F1 improves by 59.3% upon W. The full model that incorporates various representations performs the best, indicating that they capture different aspects of the term pair relationship and are complementary to each other.

We analyze different variants regarding the design choices in the structural representation. As shown in Table 9, considering multi-hop relations (e.g., grandparents and siblings) is better than only considering immediate family (i.e., parent and children). The directionality of edges does not have a huge effect on the model performance, although the information of the ancestors tends to be more benefitial for Ancestor-F1 and descendants for Edge-F1. Adding the query-item-taxonomy interactions in the user behavior ($r_{2}$) in addition to the structure in the core taxonomy further improves model performance, showing the benefits of leveraging user behavior for term attachment.

Precision recall trade-off answers the practical question in production “how many terms can be attached if a specific precision of term attachment is required”, by filtering predictions with $\max_{v\in V}P(v^{\prime}\mid v,\Theta)<c$, where $c\in[0,1]$ is a thresholding constant. As depicted in Fig 4 (Left), more than 15% terms can be recalled and attached perfectly. Over 60% terms can be recalled when an edge precision of 80% is achieved.

We inspect correct and incorrect term attachments to better understand model behavior and the contribution of each type of representation. As shown in Table 10, Octet successfully predicts “Fresh Cut Flowers” as the hypernym of “Fresh Cut Carnations”, where lexical representation possibly helps with the matching of “Fresh Cut” and semantic representation identifies “Carnations” is a type of “Flowers”. When lexical clues are lacking, Octet can still use semantic representation to recognize that “Tilapia” is a type of “Fresh Fish”. Without structural representation, Octet detects that “Bock Beer” is closely related to “Beer” and “Ales”. By adding the structural representation Octet could narrow down its prediction to the more specific type “Lager & Pilsner Beers”. For the wrongly attached terms, Octet is unconfident in distinguishing “Russet Potatoes” from “Fingerling & Baby Potatoes”, which is undoubtfully a harder case and requires deeper semantic understanding. Octet also detects a potential error in the core taxonomy itself as we found the siblings of “Pinto Beans” all start with “Dried”, which might have confused Octet during training.