# Multi-Label Zero-Shot Product Attribute-Value Extraction

Jiaying Gong  Virginia TechBlacksburgU.S<EMAIL_ADDRESS>and  Hoda Eldardiry
Virginia TechBlacksburgU.S<EMAIL_ADDRESS>
(2024)

###### Abstract.

E-commerce platforms should provide detailed product descriptions (attribute
values) for effective product search and recommendation. However, attribute
value information is typically not available for new products. To predict
unseen attribute values, large quantities of labeled training data are needed
to train a traditional supervised learning model. Typically, it is difficult,
time-consuming, and costly to manually label large quantities of new product
profiles. In this paper, we propose a novel method to efficiently and
effectively extract unseen attribute values from new products in the absence
of labeled data (zero-shot setting). We propose HyperPAVE, a multi-label zero-
shot attribute value extraction model that leverages inductive inference in
heterogeneous hypergraphs. In particular, our proposed technique constructs
heterogeneous hypergraphs to capture complex higher-order relations (i.e. user
behavior information) to learn more accurate feature representations for graph
nodes. Furthermore, our proposed HyperPAVE model uses an inductive link
prediction mechanism to infer future connections between unseen nodes. This
enables HyperPAVE to identify new attribute values without the need for
labeled training data. We conduct extensive experiments with ablation studies
on different categories of the MAVE dataset. The results demonstrate that our
proposed HyperPAVE model significantly outperforms existing classification-
based, generation-based large language models for attribute value extraction
in the zero-shot setting.

attribute value extraction; zero-shot learning; heterogeneous hypergraph;
inductive link prediction

††journalyear: 2024††copyright: rightsretained††conference: Proceedings of the
ACM Web Conference 2024; May 13–17, 2024; Singapore, Singapore.††booktitle:
Proceedings of the ACM Web Conference 2024 (WWW ’24), May 13–17, 2024,
Singapore, Singapore††isbn: 979-8-4007-0171-9/24/05††doi:
10.1145/3589334.3645649††ccs: Computing methodologies Information extraction

##  1\. Introduction

Product attribute value extraction (AVE) aims to extract attribute-value pairs
(i.e. ¡color: red¿) from e-Commerce product descriptions, which provides a
better search and recommendation experience for customers. Existing studies on
AVE mainly focus on supervised-learning models such as sequence labeling (Yan
et al., 2021; Jain et al., 2021), extractive question answering (Wang et al.,
2020; Shinzato et al., 2022) and multi-modal learning (Wang et al., 2022; Liu
et al., 2023d; Ghosh et al., 2023; Wang et al., 2023) models. These supervised
learning models are trained to only predict seen attribute value pairs.
However, new products with unseen attribute-value pairs enter the market every
day in real-world e-commerce platforms. It is time-consuming and costly to
manually label large quantities of new products for training.

Some recent works focus on open mining models (Zhang et al., 2022c; Xu et al.,
2023b) to directly extract attribute values from product titles or
descriptions. However, these approaches can not discover attribute values that
are not explicitly mentioned in the text. In other words, these open mining
models can not extract values that never appear in the product profile. To
extract unseen attribute values, these open mining models use self-supervised
learning, but they still need a high-quality seed attribute set bootstrapped
from existing resources. Besides these open mining models, some generative
large language models (LLM) are fine-tuned to autoregressively decode unseen
attribute values from the input text. However, fine-tuning such LLM (i.e. T5
(Raffel et al., 2020)) requires a lot of time and computing resources.

Figure 1.  An example of zero-shot product attribute-value extraction by semi-
inductive link predictions.

To address the above challenges, we propose HyperPAVE, a multi-label zero-shot
attribute value extraction model that leverages inductive inference in
heterogeneous hypergraphs to recognize unseen (new) attribute-value pairs
(aspects) for which there is no available labeled training data. Motivated by
the inductive graph learning, which shows the superiority of GNN to
inductively adapt to infer unseen nodes (Fan et al., 2023; Xu et al., 2020),
we build inductive heterogeneous hypergraphs employing inductive link
prediction mechanisms to infer missing or future connections (e.g., from new
‘product’ node to unseen ‘aspect’ node). The top part of Figure 1 shows an
example comparison between supervised (Figure 1a) and zero-shot (Figure 1b)
attribute value extraction. Existing works formulate relation propagation as a
transductive link prediction task (Figure 1a), where links can only be
predicted between seen nodes (products and aspects) (Ma et al., 2020; Chen and
Zhang, 2020). To recognize unseen (new) aspects for new products, negative
links are added in the original graph and the model is trained to predict
whether an edge exists between two nodes based on the node features. HyperPAVE
aims to learn the connections between both the nodes’ features that are
obtained from the fine-tuned LLM-based encoder and the complex graph
structure. Motivated by the success of combining inductive GNNs and pre-
trained BERT models (Huang et al., 2022), HyperPAVE is designed to enhance the
inductive hypergraph-based model with fine-tuned BERT contextual embeddings
for each node. Then, HyperPAVE is updated with zero-shot products and aspects
with fine-tuned contextual embeddings, where message-passing is conducted
directly on the updated graph, ensuring the inductive inference ability.

In addition, given the complexity of product data, it is important to design a
model that can capture the heterogeneous, interconnected, and higher-order
representation of both product data and user behavior data. Therefore, our
proposed model HyperPAVE consists of various types of nodes including
‘category’, ‘product’, and ‘aspect’. The product node records information
including both product titles and descriptions. To fully express the semantic
information for attribute-value pairs, the aspect nodes record detailed
attribute-value descriptions generated by a generator. The proposed hypergraph
representation uses higher-order relations to capture complex and
interconnected user behavior information (e.g., ‘also buy’, ‘also view’) and
product inventory information (e.g., ‘product has aspects’, ‘category includes
products’). The bottom part of Figure 1 shows an example comparison between
graph-based (Figure 1c) and hypergraph-based (Figure 1d) attribute value
extraction. To capture complex interconnected user behavior information,
instead of using multiple graphs (one for each behavior e.g., “also buy” and
“also view”), we construct hypergraphs using hyperedges to represent user
behavior information as higher-order relations. Compared to using several
different graphs to capture complex relations, using a hypergraph (1) can
include more (i.e. user behavior) information for the final node
representation, (2) does not need to include user nodes in the graph, and (3)
relations are not limited to binary connections. The contributions are
summarized as:

  * •

We propose a multi-label zero-shot model HyperPAVE to extract unseen attribute
values for new products without labeled training data. HyperPAVE leverages an
inductive link prediction mechanism combined with a fine-tuned BERT encoder to
obtain unseen contextual node features.

  * •

We build heterogeneous hypergraphs with higher-order relations to capture the
complex and interconnected user behavior and structured product inventory
information.

  * •

Extensive experiments on the public dataset MAVE demonstrate that HyperPAVE
significantly outperforms the classification model, generative LLMs, and
graph-based models in zero-shot learning. Besides, HyperPAVE also shows the
effectiveness and efficiency of training.

##  2\. Related Works

###  2.1. Attribute Value Extraction

Attribute value extraction (AVE) aims at extracting attribute-value pairs
(aspects) based on the product information. Early works use rule-based methods
with domain-specific dictionaries to match target attribute value pairs
(Putthividhya and Hu, 2011; Wong et al., 2009; Ghani et al., 2006). With the
development of neural networks, some studies view AVE as a sequence labeling
problem (Rezk et al., 2019; Zheng et al., 2018; Yan et al., 2021; Jain et al.,
2021). Then, question-answering-based models are built to treat attributes as
questions and values as answers (Xu et al., 2019; Wang et al., 2020; Shinzato
et al., 2022). Multimodal fusion utilizing product images as visual features
are learned to integrate visual semantics for products (Zhu et al., 2020; Lin
et al., 2021; Wang et al., 2022; Cui et al., 2023; Liu et al., 2023d; Ghosh et
al., 2023; Wang et al., 2023; Liu et al., 2023b). Some studies formulate AVE
as a multi-label classification task to extract multiple aspects for the
products (Chen et al., 2022a; Deng et al., 2022; Gong et al., 2023). To handle
unseen attribute values, open mining models (Zhang et al., 2022c; Xu et al.,
2023b) extract aspects directly from the text with limited/weak supervision,
and generation models (Shinzato et al., 2023) decode aspects as target
sequences. However, all of these approaches (1) require large quantities of
labeled data for training and (2) miss higher-order relations between
products, such as ‘also buy’ or ‘also view’ products.

###  2.2. Zero-shot Learning

Zero-shot learning has been widely applied in the field of computer vision
(CV) (Pourpanah et al., 2023) and natural language processing (NLP) (Chen et
al., 2021). Existing works for zero-shot learning in information extraction
can be roughly divided into three categories: (1) Embedding-based models,
where representations of both seen and unseen classes are learned based on the
auxiliary information such as class information (Chen and Li, 2021; Sainz et
al., 2021) and other external information (Gong and Eldardiry, 2021; Liu et
al., 2022b). However, high-quality external knowledge is required for training
the model, resulting in an increase in training time and resources. (2)
Generative-based models, where augmented samples are generated for unseen
classes by generation models (i.e. GAN (Mirza and Osindero, 2014), VAEs
(Kingma and Welling, 2013), and GPT-2 (Radford et al., 2019)) based on the
samples of seen classes. Then, the zero-shot learning problem is converted
into a conventional supervised learning problem (Chia et al., 2022; Gong and
Eldardiry, 2023). However, these models suffer from the noise of augmented
samples and performance highly depends on generative models. (3) Graph-based
models, where GNNs (Scarselli et al., 2008) are directly used to predict
unseen classes by inductive link prediction (Chen et al., 2021). Most studies
view this problem as zero-shot knowledge graph completion (Geng et al., 2023)
or zero-shot item recommendation (Fan et al., 2023). Attentive GCN is used to
transfer features from seen classes to unseen classes (Gromann et al., 2021).
Ontologies or topologies are utilized to augment ZSL by capturing
relationships between classes (Geng et al., 2022; Chen et al., 2023a).
Motivated by this, we build a product heterogeneous hypergraph to identify
unseen aspects with inductive inference ability while capturing higher-order
relations.

###  2.3. Heterogeneous Hypergraph

Hypergraphs are generalizations and extensions of ordinary graphs, where
hyperedges can accommodate an arbitrary number of nodes to capture the higher-
order relations (Zhang et al., 2022b). To handle different types of nodes and
edges, heterogeneous hypergraphs are learned by attention mechanisms (Liu et
al., 2023c; Li et al., 2023; Khan et al., 2023; Ding et al., 2020), wavelets
(Sun et al., 2021), and variational auto-encoder (Liu et al., 2022a; Fan et
al., 2021). Though, all of these works are widely applied for social networks
(Wei et al., 2023; Li et al., 2022a), academic citations (Wu et al., 2022;
Zhang et al., 2022a; Wenping et al., 2022), biological networks (Guzzi and
Zitnik, 2022; Milano et al., 2022) or product recommendation in e-commerce (Xu
et al., 2023a; Cheng et al., 2022; Liu et al., 2023a; Chen et al., 2023b),
heterogeneous hypergraphs are never applied to attribute value extraction in
e-commerce. Different from the above hypergraphs that build hyperedges by
close neighbors or meta-paths, we construct e-commerce related hyperedges by
using user behavior and product inventory data to capture higher-order
relations among categories, products, and aspects, to recognize unseen
attribute values for new products.

##  3\. Methodology

Figure 2.  Overall framework of our proposed model HyperPAVE. The framework
includes three key components: (a) Hypergraph Construction (b) Heterogeneous
Hypergraph Relation Learning and (c) Inductive Link Prediction.

###  3.1. Problem Definition

In this section, we introduce the problem statement and some necessary
definitions and notations for heterogeneous hypergraphs and multi-label zero-
shot learning.

##### Problem Statement.

Let $D=\left\\{c_{i},p_{i},a_{i}\right\\}$ denote a corpus of e-commerce
product records, where $c_{i}$, $p_{i}$, $a_{i}$ represent sub-category,
product and attribute value pair (aspect), respectively. We use $C$, $P$, and
$A$ to denote the sets of sub-categories, products, and aspects. Hence, the
task of attribute value extraction can be formulated as follows: Input: The
product records $D$. Output: A model to estimate the probability that a new
product $p$ in sub-category $c$ will have the unseen attribute value $a$. The
goal of attribute value extraction is to learn a model
$\mathcal{M}(p_{i},a_{j})\rightarrow\hat{y}\left[0,1\right]$ to score the
probability that a product $p_{i}$ has the attribute value $a_{j}$ based on
$\mathcal{G}$, which includes all the relations from user behavior and product
inventory information. Given several different graphs (i.e. user behavior
graphs, product inventory graphs, etc.), we first build a heterogeneous
hypergraph $\mathcal{G}$ to capture the higher-order and non-binary relations
contained in $\mathcal{G}$. Then, we aim to learn the representations for
nodes on a heterogeneous hypergraph $\mathcal{G}$ for an inductive link
prediction task.

##### DEFINITION 1 (Heterogeneous Hypergraph):

A heterogeneous hypergraph can be defined as
$\mathcal{G}=\left\\{\mathcal{V},\mathcal{E},\mathcal{T}_{v},\mathcal{T}_{e},W\right\\}$,
where $\mathcal{V}=\left\\{v_{1},v_{2},\cdots,v_{N}\right\\}$ is the node set,
and $\mathcal{T}_{v}$ is the node type set.
$\mathcal{E}=\left\\{e_{1},e_{2},\cdots,e_{M}\right\\}$ is the hyperedge set,
and $\mathcal{T}_{e}$ is the hyperedge type set, where
$|\mathcal{T}_{v}|+|\mathcal{T}_{e}|>2$. $N$ and $M$ represent the maximum
numbers of hyperedge nodes and edges.
$W=diag(w_{e_{1}},w_{e_{2}},\cdots,w_{e_{M}})$ denotes the diagonal matrix
representing the hyperedge weight. We use incidence matrix
$H\in\mathbb{R}^{\left|\mathcal{V}\right|\times\left|\mathcal{E}\right|}$ to
represent relationships between nodes and hyperedges, with entries defined as:

(1) $H(v,e)=\begin{cases}1&\text{ if }v\in e\\\ 0&\text{ if
}otherwise.\end{cases}$

$D_{v}\in\mathbb{R}^{\left|\mathcal{V}\right|\times\left|\mathcal{V}\right|}$
and
$D_{e}\in\mathbb{R}^{\left|\mathcal{E}\right|\times\left|\mathcal{E}\right|}$
are the diagonal matrices representing the degree matrix of nodes and
hyperedges, where $D_{v}(i,i)=\sum_{e\in\mathcal{E}}W(e)H(i,e)$ and
$D_{e}(i,i)=\sum_{v\in\mathcal{V}}H(v,i)$. The normalized hypergraph adjacency
matrix $A\in\mathbb{R^{\mathcal{V}\times\mathcal{V}}}$, representing the
connection relationship between nodes, is defined as:

(2) $A=D_{v}^{-1/2}HWD_{e}^{-1}H^{T}D_{v}^{-1/2}$

##### DEFINITION 2 (Zero-Shot Learning in Graph):

For multi-label zero-shot attribute-value (aspect) prediction, let
$A^{s}=\left\\{a_{1}^{s},\cdots,a_{m}^{s}\right\\}$ and
$A^{u}=\left\\{a_{1}^{u},\cdots,a_{m}^{u}\right\\}$ denote the node sets of
seen and unseen aspects, where $A^{s}\cap A^{u}=\emptyset$. Only $A^{s}$ is
included in the training graph $\mathcal{G}_{tr}$ and only $A^{u}$ is included
in the testing graph $\mathcal{G}_{t}$. Product $p_{i}$ with any $a_{i}^{u}$
will be removed from $\mathcal{G}_{tr}$ to $\mathcal{G}_{t}$, to ensure all
unseen aspect nodes are not in the training graph $\mathcal{G}_{tr}$. Details
for multi-label zero-shot sampling are introduced in Algorithm 1.

###  3.2. Multi-Label Zero-Shot Data Sampling

Multi-label zero-shot data sampling includes (1) data splitting to ensure that
there is no overlap of aspect and product nodes in training and
validation/testing sets, and (2) negative sampling to balance the dataset. For
data splitting, we first randomly generate $N$ aspect nodes $A_{N}$ as unseen
attribute values. Then, we remove both the nodes $A_{N}$ and their
corresponding products $P_{M}$ as unseen products, and all edges on $A_{N}$
and $P_{M}$ from the original graph $\mathcal{G}$, where $N\neq M$. This step
ensures that the zero-shot products and attribute values are never shown in
the training graph. We update the validation and testing graphs with the zero-
shot nodes and links separately so that there’s no overlap of zero-shot nodes
and links between the validation and testing sets. To balance the dataset, we
do negative sampling and add negative links for all training, validation, and
testing graphs. Details for multi-label zero-shot data sampling are shown in
Algorithm 1.

Input : Graph $\mathcal{G}$ with categories nodes $C$, product nodes $P$ and
aspect nodes $A$, unseen aspect number $N$

Output : Train graph $\mathcal{G}_{tr}$, val graph $\mathcal{G}_{v}$, test
graph $\mathcal{G}_{t}$

Initialize $\mathcal{G}_{tr}$, $\mathcal{G}_{v}$, $\mathcal{G}_{t}$

for  _$i$ in $Random(N)$_ do

$P_{i}=get\\_node(\mathcal{G},A_{i})$

$link_{pos}=get\\_edge(\mathcal{G},P_{i},A_{i})$

$link_{neg}=Sampling(get\\_complement(link_{pos}))$

$\mathcal{G}$.remove($A_{i},P_{i},link_{pos}$)

if  _$i$ //2=0_ then

$\mathcal{G}_{v}$.update($A_{i},P_{i},link_{pos},link_{neg}$)

else

$\mathcal{G}_{t}$.update($A_{i},P_{i},link_{pos},link_{neg}$)

$\mathcal{G}_{tr}=\mathcal{G}.add\\_negatives()$

return $\mathcal{G}_{tr}$, $\mathcal{G}_{v}$, $\mathcal{G}_{t}$

Algorithm 1 Multi-label Zero-shot Data Sampling

###  3.3. Overall Framework

Figure 2 shows our proposed framework HyperPAVE with three main components: a)
hypergraph construction, b) heterogeneous hypergraph relation learning, and c)
inductive link prediction. We introduce each component in detail below.

####  3.3.1. Heterogeneous Hypergraph Construction

As shown in Figure 2(a), there are three types of nodes: categories, products,
and attribute values (aspects), and four types of hyperedges: ‘also view’,
‘also buy’, ‘product with all aspects’ and ‘category with all products and
aspects’, which are constructed from two main data sources: user behavior
information and product inventory information as:

1) User Behavior Data. User behaviors have multiple types related to item-to-
item relationships: people who bought X also bought Y (‘also buy’) and people
who viewed X also viewed Y (‘also view’). To well handle different user
behaviors, we construct two types of hyperedges
$\mathcal{T}_{e}^{u}=\left\\{\mathcal{E}^{V},\mathcal{E}^{B}\right\\}$, where
$\mathcal{E}^{V}$ represents ‘also view’ and $\mathcal{E}^{B}$ represents
‘also buy’. For example, given the record of user1 in ‘also view’ graph shown
in Figure 2(a), we construct a hyperedge
$\mathcal{E}^{V}_{i}=\left\\{p_{1},p_{2},\cdots,p_{n}\right\\}\in\mathcal{E}^{V}$
to model the interactions between users and products. That is, each hyperedge
in $\mathcal{E}^{V}$ corresponds to one user. These hyperedges are homogeneous
because all nodes represent products.

2) Product Inventory Data. Product inventory data refers to the existing
product information records, including category, product, attribute values,
etc. We construct hyperedges $\mathcal{E}^{P}$ to connect all attribute values
to one product (P-A) and hyperedges $\mathcal{E}^{C}$ to connect all product
information to one sub-category (C-P-A). For example, given a product $p_{i}$,
we construct a hyperedge
$\mathcal{E}^{P}_{i}=\left\\{p_{i},a_{1},a_{2},\cdots,a_{n}\right\\}\in\mathcal{E}^{P}$
to indicate the relationships between product and its attribute values. These
heterogeneous hyperedges record the non-binary relations among categories,
products, and attribute values. To summarize it, we obtain hyperedge sets as:

(3)
$~{}\mathcal{T}_{e}=\left\\{\mathcal{E}^{V},\mathcal{E}^{B},\mathcal{E}^{P},\mathcal{E}^{C}\right\\}$

####  3.3.2. Heterogeneous Hypergraph Relation Learning

##### Embedding Module.

As shown in Figure 2(b), a heterogeneous hypergraph encoder first initializes
the node embeddings. Since the attribute values (aspects) may lose contextual
information due to the simple format, GPT-2 (Radford et al., 2019) is adopted
as the text generator to generate more detailed descriptions for attribute
values. For example, the attribute value: ‘connectivity: wireless’ can be
elaborated to a more detailed explanation: ‘connectivity is wireless
communication between the user’s device, which has an independent, physical
signal to the user’. We then adopt a pre-trained language model BERT (Devlin
et al., 2019) as all nodes’ input encoder to generate the initial contextual
representation. For the product node, we construct a string [CLS;$t$;SEP;$d$]
by concatenating the product title and description as the input, where CLS and
SEP are special tokens. The initial output representation for the category
node $c_{i}$, product node $p_{i}$ and aspect node $a_{i}$ can be formulated
as follows:

(4) $~{}h_{v_{c_{i}}}=tanh(W\cdot f_{\varnothing}(c_{i})+b)$ (5)
$~{}h_{v_{p_{i}}}=tanh(W\cdot f_{\varnothing}(t_{i},d_{i})+b)$ (6)
$~{}h_{v_{a_{i}}}=tanh(W\cdot f_{\varnothing}(g_{\varnothing}(a_{i}))+b)$

where $f_{\varnothing}$ is BERT encoder, $g_{\varnothing}$ is GPT-2 generator,
$c$ is category, $t$ is product title, $d$ is product description, $a$ is
‘attribute value’, $W$ and $b$ are trainable weights and bias. To simplify the
notations, we use $h_{v_{i}}$ to denote the initial feature embeddings of all
different nodes.

##### Message Passing Module.

Table 1. Dataset statistics over ten categories. The number of hyperedges is reported in the format of: #nodes / #hyperedges. Category | Number of Nodes | Number of Edges | Number of Hyperedges
---|---|---|---
#C | #P | #A | #CP | #PA | Density |  P-Palso view |  P-Palso buy | P-A | C-P-A
Arts | 980 | 11,625 | 2,184 | 50,652 | 28,932 |  7.2$\times 10^{-4}$ | 970/624 | 1,448/1,248 | 13,809/11,643 | 14,789/979
Books | 410 | 16,220 | 255 | 48.271 | 23,438 |  5.03$\times 10^{-4}$ | 1,247/1,433 | 2,432/2,550 | 16,475/16,222 | 16,885/409
Cellphones | 145 | 8,499 | 1,484 | 27,620 | 20,329 |  9.35$\times 10^{-4}$ | 366/362 | 171/160 | 9,983/8,507 | 10,128/144
Giftcards | 5 | 131 | 11 | 378 | 311 | 0.06 | 17/20 | 19/32 | 142/130 | 147/1
Grocery | 742 | 18,315 | 4,686 | 75,362 | 47,745 |  4.37$\times 10^{-4}$ | 3,162/2,431 | 3,392/3,314 | 23,001/4,686 | 23,743/741
Industrial | 433 | 3002 | 1573 | 12,429 | 8,453 |  1.67$\times 10^{-3}$ | 152/106 | 210/205 | 4,539/3,063 | 5,008/432
Pet | 508 | 14,299 | 2,575 | 64,947 | 46,370 |  7.34$\times 10^{-4}$ | 1,614/1,670 | 820/600 | 16,874/14,675 | 17,382/507
Software | 303 | 254 | 98 | 1,182 | 607 |  8.35$\times 10^{-3}$ | 19/20 | 2/1 | 352/287 | 655/302
Tools | 975 | 34,076 | 7,538 | 143,683 | 101,475 |  2.7$\times 10^{-4}$ | 3,176/2,648 | 1,998/1,704 | 41,614/34,705 | 42,589/974
Videogames | 910 | 731 | 353 | 4,446 | 2,152 |  3.32 $\times 10^{-3}$ | 113/139 | 14/9 | 1,084/752 | 1,994/909

To support representation learning on the constructed heterogeneous
hypergraphs in the previous step, we design a heterogeneous hypergraph
relation learning module (shown in Figure 2(b) in HyperPAVE to explore the
complex higher-order relationships based on many-to-many node message passing
in the product graph by taking full advantage of the structure information in
Figure 2(a). HyperPAVE learns node representations with two different
aggregation functions:

(7) $\displaystyle h_{v_{i}}^{l}$
$\displaystyle=AGGR_{edge}^{l}\begin{pmatrix}h_{v_{i}}^{l-1},\left\\{h_{e_{j}}^{l}|\forall_{e_{j}}\in\mathcal{E}_{i}\right\\}\end{pmatrix}$
(8) $\displaystyle h_{e_{j}}^{l}$
$\displaystyle=AGGR_{node}^{l}\begin{pmatrix}\left\\{h_{v_{k}}^{l-1}|\forall_{v_{k}}\in
e_{j}\right\\}\end{pmatrix}$

where $AGGR$ is the aggregation function, $\mathcal{E}_{i}$ is the hyperedge
sets connected to node $v_{i}$ and $h_{e_{j}}^{l}$ is the representation of
hyperedge $e_{j}$ in layer $l$. Since not all the nodes in a hyperedge will
contribute equally, the message passing is calculated from nodes to
hyperedges:

(9) $\displaystyle\alpha_{v_{i}}^{e_{i}}$
$\displaystyle=\frac{exp(LeakyReLU(w_{1}^{T}\cdot
h_{v_{i}}^{l-1}))}{\sum_{v\in V_{e_{i}}}exp(LeakyReLU(w_{1}^{T}\cdot
h_{v}^{l-1}))}$ (10) $\displaystyle h_{e_{i}}^{l}$
$\displaystyle=||_{n=1}^{N}\sigma(\sum_{v\in V_{e_{i}}}\alpha_{v}^{e_{i}}\cdot
h_{v}^{l-1})$

where $\alpha_{v_{i}}^{e_{i}}$ is the weight factor of node $v_{i}$ to
hyperedge $e_{i}$, $V_{e_{i}}$ is the node set of hyperedges $e_{i}$,
$w_{1}^{T}$ is a trainable attention parameter, $||$ denotes concatenation
with $N$ heads, and $\sigma$ is a non-linear function. $h_{e_{i}}^{l}$ is the
$l^{th}$ layer of hyperedge representation. Similarly, the message passing
from hyperedges to nodes is calculated as:

(11) $\displaystyle\alpha_{e_{i}}^{v_{i}}$
$\displaystyle=\frac{exp(LeakyReLU(w_{2}^{T}\cdot(h_{v_{i}}^{l-1}||h_{e_{i}}^{l-1})))}{\sum_{e\in\mathcal{E}_{v_{i}}}exp(LeakyReLU(w_{1}^{T}\cdot(h_{v_{i}}^{l-1}||h_{e}^{l-1})))}$
(12) $\displaystyle h_{v_{i}}^{l}$
$\displaystyle=||_{n=1}^{N}\sigma(\sum_{e\in\mathcal{E}_{v_{i}}}\alpha_{e}^{v_{i}}\cdot
h_{e}^{l-1})$

where $\alpha_{e_{i}}^{v_{i}}$ is the weight factor of hyperedge $e_{i}$ to
node $v_{i}$, $\mathcal{E}_{v_{i}}$ is the connected hyperedge set of node
$v_{i}$. $w_{2}^{T}$ is a trainable attention parameter and $h_{v_{i}}^{l}$ is
the $l^{th}$ layer of node representation, which includes the information from
the hyperedge $\mathcal{E}$.

##### Fusion Module

Instead of directly adding a readout layer and a linear prediction layer after
obtaining the $L$ layers node representations (Xu et al., 2023a), we argue
that different types of hyperedges from $\mathcal{T}_{e}$ have different
importance to the final node representations. Thus, we propose fusion modules
to fuse node representations learned from different hypergraphs constructed in
Sec. 3.3.1. The updated node representations for product node
$\hat{h_{v_{p_{i}}}}$ and aspect node $\hat{h_{v_{a_{i}}}}$ are:

(13) $\hat{h_{v_{p_{i}}}}=\alpha\cdot
h_{v_{p_{i}}}^{\mathcal{E^{P}}}+\beta\cdot
h_{v_{p_{i}}}^{\mathcal{E^{C}}}+(1-\alpha-\beta)(\gamma\cdot
h_{v_{p_{i}}}^{\mathcal{E^{V}}}+(1-\gamma)\cdot
h_{v_{p_{i}}}^{\mathcal{E^{B}}})$ (14) $\hat{h_{v_{a_{i}}}}=\delta\cdot
h_{v_{a_{i}}}^{\mathcal{E^{P}}}+(1-\delta)\cdot
h_{v_{a_{i}}}^{\mathcal{E^{C}}}$

where $h_{v_{p_{i}}}^{\mathcal{E^{P}}}$, $\cdot
h_{v_{p_{i}}}^{\mathcal{E^{C}}}$, $h_{v_{p_{i}}}^{\mathcal{E^{V}}}$,
$h_{v_{p_{i}}}^{\mathcal{E^{B}}}$ are product node representations and
$h_{v_{a_{i}}}^{\mathcal{E^{P}}}$, $h_{v_{a_{i}}}^{\mathcal{E^{C}}}$ are
aspect node representations from different hyperedges in Equ. 3, respectively.
$\alpha$, $\beta$, $\gamma$, and $\delta$ are weights learnt from the
validation sets. They are different for different categories of the dataset.
These weights are also explored and studied in Sec. 4.2.4. After the above
fusion steps, the node embeddings contain the features from neighbors defined
by different hyperedges $\mathcal{T}_{e}$, which can well capture the high-
order relations communicated among different types of nodes and hyperedges.

####  3.3.3. Inductive Link Prediction

After heterogeneous hypergraph relation learning, each node includes the
higher-order features related to user behavior and product inventory
information. Then, all the nodes go through $L$ GNN layers to compute the
final node representations. After generating the final embeddings of
$\tilde{h_{v_{p}}}$ and $\tilde{h_{v_{a}}}$, the likelihood of the link
between product $p$ and aspect $a$ is measured by the cosine similarity to
decide the possibility $\hat{R}_{ij}$ of whether product $p_{i}$ will have the
aspect $a_{j}$:

(15)
$f_{score}((\tilde{h_{v_{p}}})_{i},(\tilde{h_{v_{a}}})_{j})=\frac{(\tilde{h_{v_{p}}})_{i}\cdot(\tilde{h_{v_{a}}})_{j}}{\left\|(\tilde{h_{v_{p}}})_{i}\right\|\left\|(\tilde{h_{v_{a}}})_{j}\right\|}$

We use the negative sampling strategy introduced in Sec. 3.2 to train
HyperPAVE and employ a binary cross entropy loss to optimize our model:

(16) $\mathcal{L}=\sum_{p_{i}\in P,a_{i}\in
A}R_{ij}log\hat{R}_{ij}+(1-R_{ij})(1-log\hat{R}_{ij})$

Table 2. Experimental Results F1 / mAP (%) of multi-label zero-shot learning over ten categories on MAVE. The results are reported as mean $\pm$ standard deviation over ten times of experiments. The best results are in bold. | Arts | Books | Cellphones | Giftcards | Grocery
---|---|---|---|---|---
BERT-MLC (Chen et al., 2022b) |  24.11$\pm$0.09 / 10.31$\pm$0.16 |  36.72$\pm$0.08 / 27.17$\pm$0.37 |  22.92$\pm$0.25 / 28.67$\pm$0.37 |  36.54$\pm$0.07 / 41.15$\pm$0.08 |  19.74$\pm$0.24 / 12.07$\pm$0.09
Bart (Lewis et al., 2019) |  27.88$\pm$0.36 / 23.16$\pm$0.46 |  38.82$\pm$0.44 / 44.90$\pm$0.20 |  32.71$\pm$0.35 / 24.54$\pm$0.37 |  15.73$\pm$0.19 / 8.75$\pm$0.36 |  10.80$\pm$0.18 / 6.95$\pm$0.12
T5small (Raffel et al., 2020) |  30.85$\pm$0.31 / 23.16$\pm$0.17 |  36.17$\pm$0.45 / 42.60$\pm$0.13 |  30.95$\pm$0.31 / 24.27$\pm$0.30 |  10.14$\pm$0.26 / 8.08$\pm$0.23 |  23.53$\pm$0.27 / 17.32$\pm$0.25
HGCN (Ragesh et al., 2021) |  16.87$\pm$0.10 / 25.30$\pm$0.33 |  39.39$\pm$0.18 / 37.40$\pm$0.12 |  17.23$\pm$.24 / 14.67$\pm$0.31 |  30.92$\pm$0.07 / 45.42$\pm$0.06 |  25.60$\pm$0.13 / 39.77$\pm$ 0.18
HAN (Wang et al., 2019) |  14.26$\pm$0.10 / 26.42$\pm$0.25 |  43.73$\pm$0.16 / 49.48$\pm$0.16 |  22.49$\pm$0.20 / 33.69$\pm$0.17 |  42.47$\pm$0.31 / 54.05$\pm$0.13 |  17.23$\pm$0.20 / 34.67$\pm$0.24
HGT (Hu et al., 2020) |  30.81$\pm$0.13 / 38.53$\pm$0.16 |  48.06$\pm$0.11 / 41.67$\pm$0.17 |  14.53$\pm$0.16 / 23.73$\pm$0.20 |  42.30$\pm$0.40 / 42.39$\pm$0.19 |  27.30$\pm$0.11 / 40.76$\pm$0.24
HGNN+ (Gao et al., 2023) |  27.90$\pm$0.28 / 36.91$\pm$0.13 |  46.79$\pm$0.20 / 58.33$\pm$0.15 |  32.10$\pm$0.17 / 36.40$\pm$0.26 |  37.18$\pm$0.07 / 57.20$\pm$0.04 |  32.40$\pm$0.14 / 38.60$\pm$0.15
HyperGCN (Yadati et al., 2019) |  20.20$\pm$0.17 / 38.45$\pm$0.21 |  48.97$\pm$0.13 / 45.18$\pm$0.16 |  20.90$\pm$0.25 / 26.00$\pm$0.40 |  52.74$\pm$0.19 / 45.97$\pm$0.09 |  35.90$\pm$0.22 / 42.20$\pm$0.21
HyperPAVE | 43.33$\pm$0.22 / 40.99$\pm$0.18 |  49.75$\pm$0.18 / 56.45$\pm$0.11 |  39.01$\pm$0.16 / 35.81$\pm$0.18 |  52.34$\pm$0.22 / 65.03$\pm$0.13 |  33.43$\pm$0.28 / 42.71$\pm$0.30
| Industrial | Pet | Software | Tools | Videogames
BERT-MLC (Chen et al., 2022b) |  10.94$\pm$0.19 / 6.69$\pm$0.16 |  18.14$\pm$0.55 / 12.08$\pm$0.16 |  27.76$\pm$0.09 / 25.37$\pm$0.09 |  20.43$\pm$0.26 / 18.41$\pm$0.17 |  11.86$\pm$0.31 / 9.66$\pm$0.35
BART (Lewis et al., 2019) |  10.78$\pm$0.32 / 7.84$\pm$0.32 |  12.50$\pm$0.25 / 10.42$\pm$0.67 |  22.50$\pm$0.03 / 20.00$\pm$0.02 |  11.11$\pm$0.16 / 6.25$\pm$0.09 |  23.57$\pm$0.32 / 20.02$\pm$0.25
T5small (Raffel et al., 2020) |  15.81$\pm$0.47 / 15.35$\pm$0.16 |  25.28$\pm$0.20 / 25.72$\pm$0.26 |  26.19$\pm$0.42 / 24.60$\pm$0.31 |  37.78$\pm$0.26 / 22.46$\pm$0.52 |  14.41$\pm$0.15 / 9.90$\pm$0.27
HGCN (Ragesh et al., 2021) |  10.67$\pm$0.24 / 14.60$\pm$0.14 |  17.62$\pm$0.15 / 24.63$\pm$0.24 |  19.29$\pm$0.22 / 30.97$\pm$0.15 |  18.07$\pm$0.20 / 39.32$\pm$0.18 |  8.78$\pm$0.40 / 13.61$\pm$0.25
HAN (Wang et al., 2019) |  15.35$\pm$0.20 / 30.45$\pm$0.50 |  16.82$\pm$0.13 / 23.33$\pm$0.25 |  28.24$\pm$0.31 / 29.03$\pm$0.14 |  19.78$\pm$0.03 / 41.40$\pm$0.14 |  9.68$\pm$0.16 / 16.29$\pm$0.21
HGT (Hu et al., 2020) |  21.09$\pm$0.13 / 23.20$\pm$0.16 |  18.02$\pm$0.13 / 23.66$\pm$0.20 |  30.15$\pm$0.20 / 27.16$\pm$0.08 |  13.61$\pm$0.18 / 35.23$\pm$0.22 |  14.75$\pm$0.05 / 19.97$\pm$0.11
HGNN+ (Gao et al., 2023) |  25.90$\pm$0.26 / 28.60$\pm$0.12 |  27.60$\pm$0.14 / 35.58$\pm$.16 |  39.90$\pm$0.26 / 28.76$\pm$.16 |  31.00$\pm$0.15 / 42.20$\pm$0.23 |  10.35$\pm$0.11 / 17.21$\pm$0.08
HyperGCN (Yadati et al., 2019) |  29.20$\pm$0.13 / 33.20$\pm$.11 |  22.20$\pm$0.12 / 31.37$\pm$0.14 |  42.10$\pm$0.31 / 38.70$\pm$0.13 |  31.10$\pm$0.18 / 44.05$\pm$0.19 |  10.90$\pm$0.13 / 15.30$\pm$0.10
HyperPAVE |  27.70$\pm$0.10 / 33.29$\pm$0.17 | 28.45$\pm$0.13 / 38.46$\pm$0.20 | 47.62$\pm$0.21 / 51.64$\pm$0.10 |  34.00$\pm$0.28 / 47.83$\pm$0.29 | 25.31$\pm$0.19 / 21.19$\pm$0.17

Note that HyperPAVE follows the multi-label zero-shot settings in Sec. 3.2 to
eliminate the mandatory access of testing node features during training,
making the model access the inductive inference ability. For unseen attribute
values (aspects) and products, we can directly feed their corresponding
contextual node embeddings by fine-tuned BERT encoder to HyperPAVE instead of
representing product and aspect nodes with one-hot vectors. Then, we only
conduct message-passing and compute the probability of connections between the
product node and the aspect node. Hence, we can handle the newly added
products and attribute values in an inductive way instead of retraining the
model.

##  4\. Experiments

###  4.1. Experimental Setup

####  4.1.1. Dataset

We evaluate our model 111The code is available:
https://github.com/gjiaying/HyperPAVE. over ten different categories (Arts,
Books, Cellphones, etc) of a public dataset MAVE (Yang et al., 2022), which is
a large e-Commerce dataset derived from Amazon Review Dataset (Ni et al.,
2019). To simulate the zero-shot situation, we reconstruct the dataset into
multi-label zero-shot learning settings followed by Sec. 3.2, where there is
no overlap of products and attribute values between the training set and
validation/testing set. Note that each time we train the model, the dataset
will be randomly re-splitted for the zero-shot setting, so we report the whole
data statistics in Table 1. A sample of data statistics for training,
validation, and testing sets for each category is shown in Appendix 6.1.

####  4.1.2. Evaluation Metrics

Following other AVE tasks in the multi-label zero-shot setting (Shinzato et
al., 2023), we choose to report macro-F1 and mAP (mean Average Precision)
compared with classification and generation-based models in the main results
as F1 score is the balance of both precision and recall. In Sec. 4.2.2
ablation study, we also report AUC (Area Under Curve), Hits@K, NDCG@K
(Normalized Discounted Cumulative Gain), and MRR (Mean Reciprocal Ran), which
are widely used metrics in graph-based recommendation tasks (Fan et al., 2023;
Han et al., 2023; Li et al., 2022b). We also report training time to evaluate
the efficiency in Sec. 4.2.3 efficiency study.

####  4.1.3. Baselines

We compare our proposed model HyeprPAVE with the following baselines in the
zero-shot setting:

  * •

Classification-based Models: Original classification-based models do not have
any zero-shot abilities. We follow the baseline BERT-MLC in (Shinzato et al.,
2023), then we add synthetic data for unseen classes (attribute values)
following (Chia et al., 2022). In this way, the zero-shot learning problem is
translated into a supervised learning problem.

  * •

Generation-based Models: Following generative models in zero-shot AVE task
(Shinzato et al., 2023), we implement and fine-tune two text-to-text
transformer-based encoder decoder architecture models: BART (Lewis et al.,
2019) and T5small (Raffel et al., 2020), to generate unseen attribute values
directly.

  * •

Graph-based Models 222Implemented on DHG: https://deephypergraph.com/: As
inductive graph can predict unseen nodes (zero-shot learning), we compare
HyperPAVE with three heterogeneous graph neural networks: HGCN (Ragesh et al.,
2021), HAN (Wang et al., 2019), HGT (Hu et al., 2020), and two representative
hypergraph networks: hyperGCN (Yadati et al., 2019), HGNN+ (Gao et al., 2023).

###  4.2. Results and Discussions

Table 3. Ablation study over HyperPAVE components in the zero-shot setting across three categories on MAVE dataset. | F1 | mAP | AUC | MRR | NDCG | Hits@5 | Hits@10 | Hits@100
---|---|---|---|---|---|---|---|---
| Books
nodeID |  11.54 $\pm$ 1.59 |  28.52 $\pm$ 1.29 |  95.31 $\pm$ 1.15 |  6.64 $\pm$ 1.07 |  48.41 $\pm$ 0.97 |  35.26 $\pm$ 0.63 |  53.85 $\pm$ 0.62 |  99.42 $\pm$ 0.05
BERT |  23.87 $\pm$ 1.29 |  38.63 $\pm$ 0.57 |  97.07 $\pm$ 0.60 |  11.39 $\pm$ 0.83 |  57.31 $\pm$ 0.65 |  47.05 $\pm$ 0.42 |  63.59 $\pm$ 0.40 |  100.00 $\pm$ 0.00
BERT (Fine-tuned) |  28.28 $\pm$ 0.81 |  40.32 $\pm$ 0.59 |  97.87 $\pm$ 0.21 |  14.44 $\pm$ 0.40 |  58.89 $\pm$ 0.41 |  50.90 $\pm$ 0.82 |  78.33 $\pm$ 0.38 |  100.00$\pm$ 0.00
Hyper (Product) |  30.44 $\pm$ 0.25 |  40.65 $\pm$ 0.41 |  98.03 $\pm$ 0.19 |  14.23 $\pm$ 0.19 |  59.49 $\pm$ 0.30 |  49.36 $\pm$ 0.14 |  80.51 $\pm$ 0.17 |  100.00$\pm$ 0.00
Hyper (Behavior) |  34.46 $\pm$ 0.29 |  35.93 $\pm$ 0.49 | 98.40 $\pm$ 0.20 |  19.37 $\pm$ 0.27 |  54.23 $\pm$ 0.31 |  63.67 $\pm$ 0.40 |  93.67 $\pm$ 0.24 |  100.00$\pm$ 0.00
HyperPAVE | 49.75 $\pm$ 0.18 | 56.45 $\pm$ 0.11 |  96.47 $\pm$ 0.02 | 32.99 $\pm$ 0.14 | 69.35 $\pm$ 0.18 | 85.27 $\pm$ 0.12 | 94.04 $\pm$ 0.08 | 100.00 $\pm$ 0.00
| Giftcards
nodeID |  6.67 $\pm$ 0.21 |  22.35 $\pm$ 0.20 |  41.94 $\pm$ 0.29 |  18.18 $\pm$ 0.30 |  42.92 $\pm$ 0.15 |  25.00 $\pm$ 0.00 |  97.50 $\pm$ 0.08 |  100.00$\pm$ 0.00
BERT |  26.41 $\pm$ 0.17 |  44.79 $\pm$ 0.14 |  71.94 $\pm$ 0.05 |  24.15 $\pm$ 0.18 |  62.47 $\pm$ 0.13 |  75.00 $\pm$ 0.00 |  100.00$\pm$ 0.00 |  100.00$\pm$ 0.00
BERT (Fine-tuned) |  34.43 $\pm$ 0.17 |  41.67 $\pm$ 0.15 |  71.53 $\pm$ 0.16 |  23.17 $\pm$ 0.30 |  59.57 $\pm$ 0.11 |  67.50 $\pm$ 0.12 |  100.00$\pm$ 0.00 |  100.00$\pm$ 0.00
Hyper (Product) |  39.77 $\pm$ 0.12 |  45.74 $\pm$ 0.10 |  84.55 $\pm$ 0.10 |  35.65 $\pm$ 0.17 |  61.83 $\pm$ 0.08 |  100.00$\pm$ 0.00 |  100.00$\pm$ 0.00 |  100.00$\pm$ 0.00
Hyper (Behavior) |  45.43$\pm$ 0.15 |  60.50 $\pm$ 0.13 |  77.92 $\pm$ 0.12 |  29.13 $\pm$ 0.15 |  73.02 $\pm$ 0.07 |  71.00 $\pm$ 0.12 |  100.00$\pm$ 0.00 |  100.00$\pm$ 0.00
HyperPAVE | 52.34 $\pm$ 0.22 | 65.03 $\pm$ 0.13 | 90.08 $\pm$ 0.05 | 44.56 $\pm$ 0.16 | 75.07 $\pm$ 0.11 | 100.00 $\pm$ 0.00 | 100.00 $\pm$ 0.00 | 100.00 $\pm$ 0.00
| Pets
nodeID |  6.95 $\pm$ 0.82 |  13.46 $\pm$ 0.92 |  98.51 $\pm$ 0.27 |  7.47 $\pm$ 0.19 |  42.17 $\pm$ 0.62 |  30.33 $\pm$ 0.46 |  50.00 $\pm$ 0.13 |  96.15 $\pm$ 0.10
BERT |  9.93 $\pm$ 0.30 |  19.93 $\pm$ 0.51 |  99.73 $\pm$ 0.20 |  6.71 $\pm$ 0.27 |  41.16 $\pm$ 0.68 |  31.67$\pm$ 0.54 |  65.00 $\pm$ 0.50 |  100.00$\pm$ 0.00
BERT (Fine-tuned) |  12.12 $\pm$ 0.29 |  19.99 $\pm$ 0.74 |  99.39 $\pm$ 0.11 |  10.79 $\pm$ 0.37 |  40.52 $\pm$ 0.61 |  25.00$\pm$ 0.29 |  56.67 $\pm$ 0.14 |  100.00$\pm$ 0.00
Hyper (Product) |  17.58 $\pm$ 0.26 |  37.40 $\pm$ 0.32 |  99.03 $\pm$ 0.09 |  16.45 $\pm$ 0.19 |  45.67 $\pm$ 0.21 |  41.67 $\pm$ 0.17 | 71.67 $\pm$ 0.15 |  98.33 $\pm$ 0.12
Hyper (Behavior) |  18.66 $\pm$ 0.14 |  24.71 $\pm$ 0.14 |  99.16 $\pm$ 0.10 |  19.01 $\pm$ 0.28 |  42.38 $\pm$ 0.35 |  36.07 $\pm$ 0.22 |  65.00 $\pm$ 0.09 |  100.00$\pm$ 0.00
HyperPAVE | 28.45 $\pm$ 0.13 | 38.46 $\pm$ 0.20 | 99.82 $\pm$ 0.06 | 29.92 $\pm$ 0.13 | 61.55 $\pm$ 0.20 | 56.67 $\pm$ 0.09 |  67.77 $\pm$ 0.03 | 100.00$\pm$ 0.00

####  4.2.1. Main Results

From the results shown in Table 2 and data statistics shown in Table 1, we
observe that:

(1) The classification-based model generally performs worst among all models.
BERT-MLC, which uses synthetic data for zero-shot prediction, only has
competitive performance to generation-based models when the class number (#A)
is small. We conjecture that as the number of classes grows, BERT-MLC needs to
make distinctions among more classes, making it harder to find clearer
decision boundaries. The average micro F1 of BART and T5 small across all ten
categories is worse than T5 base in (Shinzato et al., 2023). This is because
T5 base is pre-trained over 220 million parameters whereas T5 small has only
60 million parameters. Generation-based models perform much better than
classification-based models in most cases. BART and T5 small show different
performances over different categories. They can achieve similar performance
with HyperPAVE when the dataset size is large enough. (2) Combining inductive
graph-based models with LLM encoders can perform zero-shot prediction and
achieve competitive performance with generative models. This inspires us that
instead of fine-tuning the popular generative models (Shinzato et al., 2023;
Zhang et al., 2023; Roy et al., 2022, 2021) to extract attribute values, the
inductive graph for link prediction can also be explored for zero-shot
prediction. Besides, using the attention mechanism shows better performance
than using fixed and uniform weights for aggregation. This is probably because
assigning different weights to neighboring nodes can capture varying levels of
influence. (3) Compared with graph-based baselines, adding complex structured
data to capture higher-order relationships demonstrates significant
performance improvement over all ten categories. This is probably because
hyperedges can model relationships that go beyond pairwise connections,
resulting in more semantic node representations. Besides, our proposed model
HyperPAVE achieves the best performance among all models in most categories,
indicating that our proposed hypergraph construction from both user behavior
data and product inventory data is important and worth recording and
exploring. The effectiveness of different hyperedges is studied in Sec. 4.2.2.

####  4.2.2. Ablation Study

To evaluate the performance of each component in HyperPAVE, we conduct an
ablation study over three categories in the zero-shot setting. Table 3 shows
the performance of each component in HyperPAVE. More results are shown in
Table 7 in the Appendix. We have the following observations based on Table 3:
(1) Adding node features can significantly improve the performance. We perform
a model ‘nodeID’, which doesn’t use any pre-trained encoder for providing node
features. The model ‘nodeID’ uses a simple embedding-lookup encoder, mapping
each node to a unique low-dimensional vector. We can observe that among all
models, ‘nodeID’ shows the worst performance. After adding node features, such
as BERT or fine-tuned BERT, the performance increases significantly. We think
that this is because, for link prediction in the zero-shot setting, pre-
trained embeddings provide richer and more semantically meaningful
representations for node features in graphs than simple one-hot encoding. (2)
Fine-tuning the pre-trained encoders for node features results in a big
performance improvement when the dataset (graph) is large enough. This is
reasonable because a larger dataset (graph with more nodes) provides more
diverse and representative data, enabling better generalization for unseen
nodes in the zero-shot setting. However, as shown in Sec. 4.2.3, fine-tuning
the pre-trained encoder may result in more time for model training. A balance
of model performance and efficiency needs to be considered for different
tasks/situations. (3) We explore the importance of different hypergraphs. We
find out that adding different hyperedges built from user behavior data or
product inventory data results in a significant performance improvement. We
conjecture that this is because different hyperedges capture more complex
higher-order information than the original binary-relation graph. For example,
hyperedge ’P-Palso_view’ built from user behavior data includes information on
products with potential similar attributes because users may probably view
similar products at the same time for their needs. Hyperedge ‘C-P-A’, built
from product inventory data, aggregates all products and aspects in the same
sub-category. Attribute values such as ‘Chew Type: Bones’ may only happen in a
sub-category of ‘Dog Treats’ instead of ‘Cat Food’. By using hyperedges, more
complex relations can be included in the representation for each single node.

####  4.2.3. Efficiency Study

Table 4. Comparison of computational efficiency. The batch size is set to 4. Model | Memory Consumption | Model Parameters
---|---|---
Classification-based | 5037MB | 110M
Generation-based | 8305MB / 5831MB | 140M / 60M
Graph-based (ours) | 1405MB / 1915 MB | 5M / 115M

Table 4 presents the GPU computational cost and model parameter comparison
between classification-based (BERT-MLC), generation-based (BART/T5small) and
graph-based (nodeID/HyperPAVE) models on Arts category of MAVE. Different
categories (different sizes of graphs) may result in a slight difference. From
the reported results, we can find that compared with classification or
generation-based models, our proposed graph-based model HyperPAVE, has a
significant computational advantage in terms of memory consumption. The main
reason is that the zero-shot ability of generative LLMs is based on their
extensive pretraining and understanding of the diverse data. When fine-tuning
these LLMs, large quantities of model parameters need to be updated, resulting
in a huge GPU memory consumption cost. However, the zero-shot ability of
HyperPAVE results from the inductive inference that can generalize to unseen
product and aspect nodes without retraining the whole model. The inductive
HyperPAVE divides the hypergraphs into batches and only consumes per-batch
memory when training. Note that for the classification model BERT-MLC,
preprocessing steps for generating synthetic data from generation models are
required to predict unseen aspects. We have not counted the computational cost
for these preprocessing steps.

Figure 3.  Time Efficiency Performance (GPU Time of Model Learning in Seconds
for One Training Epoch).

To evaluate the computation time of our graph-based model HyperPAVE and other
classification-based and generation-based models, we record the model training
time for one epoch in seconds across the ten categories on MAVE as shown in
Figure 3. All models use the same input max_length and batch size for
training. From Figure 3, we observe that graph-based models show better model
training efficiency. Compared with other graph-based models (i.e. GNN, HGNN),
HyperPAVE can achieve the best prediction performance as shown in Table 2 with
only sacrificing a little more time for training as shown in Figure 3. The
slopes of BART, T5, and BERT-MLE are much larger than graph-based models,
indicating that much more time is needed for training or fine-tuning with the
increase in dataset size when updating the model parameters. More details are
shown in Table 6 in Appendix 6.3.

####  4.2.4. Parameter Sensitivity Analysis

The key hyperparameters of HyperPAVE are the weights of the different
hyperedges. Thus, we explore the importance of different types of hyperedges
in the category of Giftcards as shown in Figure 4.

Figure 4. Effects on weights of different hyperedges on the category of
giftcards.

The left figure explores the weights of ‘P-Palso view’ and ‘P-Palso buy’
hyperedges from user behavior information. The right figure explores the
weights of user behavior hyperedges (P-P) and product inventory hyperedges
(‘P-A’ and ‘C-P-A’). From Figure 4, we observe that both ‘P-Palso view’ and
‘P-Palso buy’ contribute to the model’s performance. The best weight for
‘P-Palso view’ falls in the [0.2, 0.5] interval, which means ‘P-Palso buy’ is
slightly more important than ‘P-Palso view’. This is probably because ‘P-Palso
buy’ records users’ history preference while ‘P-Palso view’ may include some
noise such as accidental clicks. We can also observe from the right 4 that the
best weight for user behavior data falls in the [0.6, 0.8] interval,
indicating that user behavior is much more important than product inventory
data. As shown in Table 1, the number of user behavior hyperedges is much
smaller than the number of product inventory hyperedges (‘P-A’ and ‘C-P-A’).
But they show more importance in Figure 4, demonstrating that user behavior
information is worth recording and exploring for extracting unseen attribute
values for new products.

##  5\. Conclusion and Future Work

In this paper, we formulate the AVE task in a zero-shot learning scenario to
identify unseen attribute values from new products with no corresponding
labeled data available for training. We propose an inductive heterogeneous
hypergraph (HyperPAVE) for multi-label zero-shot attribute value extraction.
Specifically, the heterogeneous hypergraph captures the higher-order
relationships among users and products, and the inductive mechanism infers the
future connections between unseen nodes. Extensive experimental results on ten
different categories across the public dataset MAVE demonstrate that our
proposed model HyperPAVE outperforms other state-of-the-art classification-
based and generation-based models. The ablation study validates the efficiency
and effectiveness of different hypergraphs constructed from user behavior and
product inventory data. We plan to explore the following directions in future
work: (1) Including multimodal features (i.e. product images) as node
attributes to capture more semantic information from the products. (2)
Building dynamic graphs by including timestamps to make the product graph
adapt to the developing market.

## References

  * (1)
  * Chen and Li (2021) Chih-Yao Chen and Cheng-Te Li. 2021.  ZS-BERT: Towards Zero-Shot Relation Extraction with Attribute Representation Learning. In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_. Association for Computational Linguistics, Online, 3470–3479.  https://doi.org/10.18653/v1/2021.naacl-main.272
  * Chen et al. (2021) Jiaoyan Chen, Yuxia Geng, Zhuo Chen, Ian Horrocks, Jeff Z. Pan, and Huajun Chen. 2021\.  Knowledge-aware Zero-Shot Learning: Survey and Perspective. In _Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21_ , Zhi-Hua Zhou (Ed.). International Joint Conferences on Artificial Intelligence Organization, 4366–4373.  https://doi.org/10.24963/ijcai.2021/597 Survey Track.
  * Chen and Zhang (2020) Jiayi Chen and Aidong Zhang. 2020.  Hgmf: heterogeneous graph-based fusion for multimodal data with incompleteness. In _Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining_. 1295–1305.
  * Chen et al. (2023b) Mengru Chen, Chao Huang, Lianghao Xia, Wei Wei, Yong Xu, and Ronghua Luo. 2023b.  Heterogeneous Graph Contrastive Learning for Recommendation. In _Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining_ (Singapore, Singapore) _(WSDM ’23)_. Association for Computing Machinery, New York, NY, USA, 544–552.  https://doi.org/10.1145/3539597.3570484
  * Chen et al. (2022a) Wei-Te Chen, Yandi Xia, and Keiji Shinzato. 2022a.  Extreme Multi-Label Classification with Label Masking for Product Attribute Value Extraction. In _Proceedings of The Fifth Workshop on e-Commerce and NLP (ECNLP 5)_. 134–140.
  * Chen et al. (2022b) Wei-Te Chen, Yandi Xia, and Keiji Shinzato. 2022b.  Extreme Multi-Label Classification with Label Masking for Product Attribute Value Extraction. In _Proceedings of the Fifth Workshop on e-Commerce and NLP (ECNLP 5)_. Association for Computational Linguistics, Dublin, Ireland, 134–140.  https://doi.org/10.18653/v1/2022.ecnlp-1.16
  * Chen et al. (2023a) Ziyi Chen, Yutong Gao, Congyan Lang, Lili Wei, Yidong Li, Hongzhe Liu, and Fayao Liu. 2023a.  Integrating Topology beyond Descriptions for Zero-shot Learning.  _Pattern Recognition_ (2023), 109738\.
  * Cheng et al. (2022) Dian Cheng, Jiawei Chen, Wenjun Peng, Wenqin Ye, Fuyu Lv, Tao Zhuang, Xiaoyi Zeng, and Xiangnan He. 2022\.  IHGNN: Interactive Hypergraph Neural Network for Personalized Product Search. In _Proceedings of the ACM Web Conference 2022_. 256–265.
  * Chia et al. (2022) Yew Ken Chia, Lidong Bing, Soujanya Poria, and Luo Si. 2022\.  RelationPrompt: Leveraging Prompts to Generate Synthetic Data for Zero-Shot Relation Triplet Extraction. In _Findings of the Association for Computational Linguistics: ACL 2022_. Association for Computational Linguistics, Dublin, Ireland, 45–57.  https://doi.org/10.18653/v1/2022.findings-acl.5
  * Cui et al. (2023) Hejie Cui, Rongmei Lin, Nasser Zalmout, Chenwei Zhang, Jingbo Shang, Carl Yang, and Xian Li. 2023.  PV2TEA: Patching Visual Modality to Textual-Established Information Extraction.  arXiv:2306.01016 [cs.CL]
  * Deng et al. (2022) Zhongfen Deng, Wei-Te Chen, Lei Chen, and S Yu Philip. 2022\.  AE-smnsMLC: Multi-Label Classification with Semantic Matching and Negative Label Sampling for Product Attribute Value Extraction. In _2022 IEEE International Conference on Big Data (Big Data)_. IEEE, 1816–1821.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_. Association for Computational Linguistics, Minneapolis, Minnesota, 4171–4186.  https://doi.org/10.18653/v1/N19-1423
  * Ding et al. (2020) Kaize Ding, Jianling Wang, Jundong Li, Dingcheng Li, and Huan Liu. 2020.  Be More with Less: Hypergraph Attention Networks for Inductive Text Classification. In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. Association for Computational Linguistics, Online, 4927–4936.  https://doi.org/10.18653/v1/2020.emnlp-main.399
  * Fan et al. (2021) Haoyi Fan, Fengbin Zhang, Yuxuan Wei, Zuoyong Li, Changqing Zou, Yue Gao, and Qionghai Dai. 2021.  Heterogeneous hypergraph variational autoencoder for link prediction.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 44, 8 (2021), 4125–4138.
  * Fan et al. (2023) Ziwei Fan, Zhiwei Liu, Shelby Heinecke, Jianguo Zhang, Huan Wang, Caiming Xiong, and Philip S Yu. 2023.  Zero-shot Item-based Recommendation via Multi-task Product Knowledge Graph Pre-Training.  _arXiv preprint arXiv:2305.07633_ (2023).
  * Gao et al. (2023) Yue Gao, Yifan Feng, Shuyi Ji, and Rongrong Ji. 2023\.  HGNN+: General Hypergraph Neural Networks.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 45, 3 (2023), 3181–3199.  https://doi.org/10.1109/TPAMI.2022.3182052
  * Geng et al. (2022) Yuxia Geng, Jiaoyan Chen, Wen Zhang, Yajing Xu, Zhuo Chen, Jeff Z. Pan, Yufeng Huang, Feiyu Xiong, and Huajun Chen. 2022.  Disentangled ontology embedding for zero-shot learning. In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_. 443–453.
  * Geng et al. (2023) Yuxia Geng, Jiaoyan Chen, Xiang Zhuang, Zhuo Chen, Jeff Z Pan, Juan Li, Zonggang Yuan, and Huajun Chen. 2023\.  Benchmarking knowledge-driven zero-shot learning.  _Journal of Web Semantics_ 75 (2023), 100757.
  * Ghani et al. (2006) Rayid Ghani, Katharina Probst, Yan Liu, Marko Krema, and Andrew Fano. 2006.  Text Mining for Product Attribute Extraction.  _SIGKDD Explor. Newsl._ 8, 1 (jun 2006), 41–48.  https://doi.org/10.1145/1147234.1147241
  * Ghosh et al. (2023) Pushpendu Ghosh, Nancy Wang, and Promod Yenigalla. 2023\.  D-Extract: Extracting Dimensional Attributes From Product Images. In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_. 3641–3649.
  * Gong et al. (2023) Jiaying Gong, Wei-Te Chen, and Hoda Eldardiry. 2023\.  Knowledge-Enhanced Multi-Label Few-Shot Product Attribute-Value Extraction.  _arXiv preprint arXiv:2308.08413_ (2023).
  * Gong and Eldardiry (2021) Jiaying Gong and Hoda Eldardiry. 2021.  Zero-Shot Relation Classification from Side Information. In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_ (Virtual Event, Queensland, Australia) _(CIKM ’21)_. Association for Computing Machinery, New York, NY, USA, 576–585.  https://doi.org/10.1145/3459637.3482403
  * Gong and Eldardiry (2023) Jiaying Gong and Hoda Eldardiry. 2023.  Prompt-based Zero-shot Relation Extraction with Semantic Knowledge Augmentation.  arXiv:2112.04539 [cs.CL]
  * Gromann et al. (2021) Dagmar Gromann, Yuxia Geng, Jiaoyan Chen, Zhiquan Ye, Zonggang Yuan, Wei Zhang, and Huajun Chen. 2021.  Explainable Zero-Shot Learning via Attentive Graph Convolutional Network and Knowledge Graphs.  _Semant. Web_ 12, 5 (jan 2021), 741–765.  https://doi.org/10.3233/SW-210435
  * Guzzi and Zitnik (2022) Pietro Hiram Guzzi and Marinka Zitnik. 2022.  Editorial deep learning and graph embeddings for network biology.  _IEEE/ACM Transactions on Computational Biology and Bioinformatics_ 19, 2 (2022), 653–654.
  * Han et al. (2023) Zhongxuan Han, Xiaolin Zheng, Chaochao Chen, Wenjie Cheng, and Yang Yao. 2023.  Intra and Inter Domain HyperGraph Convolutional Network for Cross-Domain Recommendation. In _Proceedings of the ACM Web Conference 2023_. 449–459.
  * Hu et al. (2020) Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. 2020\.  Heterogeneous graph transformer. In _Proceedings of the web conference 2020_. 2704–2710.
  * Huang et al. (2022) Yen-Hao Huang, Yi-Hsin Chen, and Yi-Shin Chen. 2022\.  ConTextING: Granting Document-Wise Contextual Embeddings to Graph Neural Networks for Inductive Text Classification. In _Proceedings of the 29th International Conference on Computational Linguistics_. 1163–1168.
  * Jain et al. (2021) Mayank Jain, Sourangshu Bhattacharya, Harshit Jain, Karimulla Shaik, and Muthusamy Chelliah. 2021\.  Learning Cross-Task Attribute - Attribute Similarity for Multi-task Attribute-Value Extraction. In _Proceedings of the 4th Workshop on e-Commerce and NLP_. Association for Computational Linguistics, Online, 79–87.  https://doi.org/10.18653/v1/2021.ecnlp-1.10
  * Khan et al. (2023) Bilal Khan, Jia Wu, Jian Yang, and Xiaoxiao Ma. 2023\.  Heterogeneous Hypergraph Neural Network for Social Recommendation using Attention Network.  _ACM Transactions on Recommender Systems_ (2023).
  * Kingma and Welling (2013) Diederik P Kingma and Max Welling. 2013.  Auto-encoding variational bayes.  _arXiv preprint arXiv:1312.6114_ (2013).
  * Lewis et al. (2019) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer. 2019\.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  _arXiv preprint arXiv:1910.13461_ (2019).
  * Li et al. (2023) Mengran Li, Yong Zhang, Xiaoyong Li, Yuchen Zhang, and Baocai Yin. 2023.  Hypergraph transformer neural networks.  _ACM Transactions on Knowledge Discovery from Data_ 17, 5 (2023), 1–22.
  * Li et al. (2022a) Yongkang Li, Zipei Fan, Du Yin, Renhe Jiang, Jinliang Deng, and Xuan Song. 2022a.  HMGCL: Heterogeneous multigraph contrastive learning for LBSN friend recommendation.  _World Wide Web_ (2022), 1–24.
  * Li et al. (2022b) Yongkang Li, Zipei Fan, Jixiao Zhang, Dengheng Shi, Tianqi Xu, Du Yin, Jinliang Deng, and Xuan Song. 2022b.  Heterogeneous Hypergraph Neural Network for Friend Recommendation with Human Mobility. In _Proceedings of the 31st ACM International Conference on Information & Knowledge Management_. 4209–4213.
  * Lin et al. (2021) Rongmei Lin, Xiang He, Jie Feng, Nasser Zalmout, Yan Liang, Li Xiong, and Xin Luna Dong. 2021.  PAM: understanding product images in cross product category attribute extraction. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_. 3262–3270.
  * Liu et al. (2022b) Fangchao Liu, Hongyu Lin, Xianpei Han, Boxi Cao, and Le Sun. 2022b.  Pre-training to Match for Unified Low-shot Relation Extraction. In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. Association for Computational Linguistics, Dublin, Ireland, 5785–5795.  https://doi.org/10.18653/v1/2022.acl-long.397
  * Liu et al. (2023a) Jiongnan Liu, Zhicheng Dou, Guoyu Tang, and Sulong Xu. 2023a.  JDsearch: A Personalized Product Search Dataset with Real Queries and Full Interactions. In _Proceedings of the SIGIR 2023_. ACM.  https://doi.org/10.1145/3539618.3591900
  * Liu et al. (2022a) Jingquan Liu, Xiaoyong Du, Yuanzhe Li, and Weidong Hu. 2022a.  Hypergraph Variational Autoencoder for Multimodal Semi-supervised Representation Learning. In _Artificial Neural Networks and Machine Learning–ICANN 2022: 31st International Conference on Artificial Neural Networks, Bristol, UK, September 6–9, 2022, Proceedings; Part IV_. Springer, 395–406.
  * Liu et al. (2023c) Jie Liu, Lingyun Song, Guangtao Wang, and Xuequn Shang. 2023c.  Meta-HGT: Metapath-aware HyperGraph Transformer for heterogeneous information network embedding.  _Neural Networks_ 157 (2023), 65–76.
  * Liu et al. (2023d) Mengyin Liu, Chao Zhu, Hongyu Gao, Weibo Gu, Hongfa Wang, Wei Liu, and Xu cheng Yin. 2023d.  Boosting Multi-Modal E-commerce Attribute Value Extraction via Unified Learning Scheme and Dynamic Range Minimization.  arXiv:2207.07278 [cs.CV]
  * Liu et al. (2023b) Shilei Liu, Lin Li, Jun Song, Yonghua Yang, and Xiaoyi Zeng. 2023b.  Multimodal Pre-Training with Self-Distillation for Product Understanding in E-Commerce. In _Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining_. 1039–1047.
  * Ma et al. (2020) Yuqing Ma, Shihao Bai, Shan An, Wei Liu, Aishan Liu, Xiantong Zhen, and Xianglong Liu. 2020.  Transductive Relation-Propagation Network for Few-shot Learning.. In _IJCAI_ , Vol. 20. 804–810.
  * Milano et al. (2022) Marianna Milano, Giuseppe Agapito, and Mario Cannataro. 2022\.  Challenges and limitations of biological network analysis.  _BioTech_ 11, 3 (2022), 24.
  * Mirza and Osindero (2014) Mehdi Mirza and Simon Osindero. 2014.  Conditional generative adversarial nets.  _arXiv preprint arXiv:1411.1784_ (2014).
  * Ni et al. (2019) Jianmo Ni, Jiacheng Li, and Julian McAuley. 2019.  Justifying recommendations using distantly-labeled reviews and fine-grained aspects. In _Proceedings of the 2019 conference on empirical methods in natural language processing and the 9th international joint conference on natural language processing (EMNLP-IJCNLP)_. 188–197.
  * Pourpanah et al. (2023) Farhad Pourpanah, Moloud Abdar, Yuxuan Luo, Xinlei Zhou, Ran Wang, Chee Peng Lim, Xi-Zhao Wang, and Q. M. Jonathan Wu. 2023\.  A Review of Generalized Zero-Shot Learning Methods.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 45, 4 (2023), 4051–4070.  https://doi.org/10.1109/TPAMI.2022.3191696
  * Putthividhya and Hu (2011) Duangmanee (Pew) Putthividhya and Junling Hu. 2011.  Bootstrapped Named Entity Recognition for Product Attribute Extraction. In _Proceedings of the Conference on Empirical Methods in Natural Language Processing_ (Edinburgh, United Kingdom) _(EMNLP ’11)_. Association for Computational Linguistics, USA, 1557–1567.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019\.  Language models are unsupervised multitask learners.  _OpenAI blog_ 1, 8 (2019), 9.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _The Journal of Machine Learning Research_ 21, 1 (2020), 5485–5551.
  * Ragesh et al. (2021) Rahul Ragesh, Sundararajan Sellamanickam, Arun Iyer, Ramakrishna Bairi, and Vijay Lingam. 2021\.  Hetegcn: heterogeneous graph convolutional networks for text classification. In _Proceedings of the 14th ACM international conference on web search and data mining_. 860–868.
  * Rezk et al. (2019) Martin Rezk, Laura Alonso Alemany, Lasguido Nio, and Ted Zhang. 2019.  Accurate Product Attribute Extraction on the Field. In _2019 IEEE 35th International Conference on Data Engineering (ICDE)_. 1862–1873.  https://doi.org/10.1109/ICDE.2019.00202
  * Roy et al. (2021) Kalyani Roy, Pawan Goyal, and Manish Pandey. 2021.  Attribute value generation from product title using language models. In _Proceedings of The 4th Workshop on e-Commerce and NLP_. 13–17.
  * Roy et al. (2022) Kalyani Roy, Tapas Nayak, and Pawan Goyal. 2022.  Exploring Generative Models for Joint Attribute Value Extraction from Product Titles.  _arXiv preprint arXiv:2208.07130_ (2022).
  * Sainz et al. (2021) Oscar Sainz, Oier Lopez de Lacalle, Gorka Labaka, Ander Barrena, and Eneko Agirre. 2021.  Label Verbalization and Entailment for Effective Zero and Few-Shot Relation Extraction. In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, Online and Punta Cana, Dominican Republic, 1199–1212.  https://doi.org/10.18653/v1/2021.emnlp-main.92
  * Scarselli et al. (2008) Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. 2008\.  The graph neural network model.  _IEEE transactions on neural networks_ 20, 1 (2008), 61–80.
  * Shinzato et al. (2022) Keiji Shinzato, Naoki Yoshinaga, Yandi Xia, and Wei-Te Chen. 2022.  Simple and Effective Knowledge-Driven Query Expansion for QA-Based Product Attribute Extraction. In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_. 227–234.
  * Shinzato et al. (2023) Keiji Shinzato, Naoki Yoshinaga, Yandi Xia, and Wei-Te Chen. 2023.  A Unified Generative Approach to Product Attribute-Value Identification.  _arXiv preprint arXiv:2306.05605_ (2023).
  * Sun et al. (2021) Xiangguo Sun, Hongzhi Yin, Bo Liu, Hongxu Chen, Jiuxin Cao, Yingxia Shao, and Nguyen Quoc Viet Hung. 2021.  Heterogeneous hypergraph embedding for graph classification. In _Proceedings of the 14th ACM international conference on web search and data mining_. 725–733.
  * Wang et al. (2023) Kai Wang, Jianzhi Shao, Tao Zhang, Qijin Chen, and Chengfu Huo. 2023.  MPKGAC: Multimodal Product Attribute Completion in E-commerce. In _Companion Proceedings of the ACM Web Conference 2023_. 336–340.
  * Wang et al. (2020) Qifan Wang, Li Yang, Bhargav Kanagal, Sumit Sanghai, D Sivakumar, Bin Shu, Zac Yu, and Jon Elsas. 2020\.  Learning to extract attribute value from product via question answering: A multi-task approach. In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 47–55.
  * Wang et al. (2022) Qifan Wang, Li Yang, Jingang Wang, Jitin Krishnan, Bo Dai, Sinong Wang, Zenglin Xu, Madian Khabsa, and Hao Ma. 2022.  SMARTAVE: Structured Multimodal Transformer for Product Attribute Value Extraction. In _Findings of the Association for Computational Linguistics: EMNLP 2022_. 263–276.
  * Wang et al. (2019) Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. 2019.  Heterogeneous graph attention network. In _The world wide web conference_. 2022–2032.
  * Wei et al. (2023) Xuemei Wei, Yezheng Liu, Jianshan Sun, Yuanchun Jiang, Qifeng Tang, and Kun Yuan. 2023\.  Dual subgraph-based graph neural network for friendship prediction in location-based social networks.  _ACM Transactions on Knowledge Discovery from Data_ 17, 3 (2023), 1–28.
  * Wenping et al. (2022) Zheng Wenping, Liu Meilin, and Liang Jiye. 2022\.  Hypergraphs: Concepts, Applications and Analysis. In _2022 IEEE 13th International Symposium on Parallel Architectures, Algorithms and Programming (PAAP)_. 1–6.  https://doi.org/10.1109/PAAP56126.2022.10010428
  * Wong et al. (2009) Yuk Wah Wong, Dominic Widdows, Tom Lokovic, and Kamal Nigam. 2009.  Scalable Attribute-Value Extraction from Semi-Structured Text. In _ICDM Workshop on Large-scale Data Mining: Theory and Applications_.  http://www.computer.org/portal/web/csdl/doi/10.1109/ICDMW.2009.81
  * Wu et al. (2022) Hanrui Wu, Yuguang Yan, and Michael Kwok-Po Ng. 2022.  Hypergraph collaborative network on vertices and hyperedges.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 45, 3 (2022), 3245–3258.
  * Xu et al. (2020) Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. 2020.  Inductive representation learning on temporal graphs.  _arXiv preprint arXiv:2002.07962_ (2020).
  * Xu et al. (2019) Huimin Xu, Wenting Wang, Xinnian Mao, Xinyu Jiang, and Man Lan. 2019.  Scaling up open tagging from tens to thousands: Comprehension empowered attribute value extraction from product title. In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_. 5214–5223.
  * Xu et al. (2023b) Liyan Xu, Chenwei Zhang, Xian Li, Jingbo Shang, and Jinho D Choi. 2023b.  Towards Open-World Product Attribute Mining: A Lightly-Supervised Approach.  _arXiv preprint arXiv:2305.18350_ (2023).
  * Xu et al. (2023a) Zixuan Xu, Penghui Wei, Shaoguo Liu, Weimin Zhang, Liang Wang, and Bo Zheng. 2023a.  Correlative Preference Transfer with Hierarchical Hypergraph Network for Multi-Domain Recommendation. In _Proceedings of the ACM Web Conference 2023_. 983–991.
  * Yadati et al. (2019) Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar. 2019.  Hypergcn: A new method for training graph convolutional networks on hypergraphs.  _Advances in neural information processing systems_ 32 (2019).
  * Yan et al. (2021) Jun Yan, Nasser Zalmout, Yan Liang, Christan Grant, Xiang Ren, and Xin Luna Dong. 2021\.  AdaTag: Multi-Attribute Value Extraction from Product Profiles with Adaptive Decoding. In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_. Association for Computational Linguistics, Online, 4694–4705.  https://doi.org/10.18653/v1/2021.acl-long.362
  * Yang et al. (2022) Li Yang, Qifan Wang, Zac Yu, Anand Kulkarni, Sumit Sanghai, Bin Shu, Jon Elsas, and Bhargav Kanagal. 2022\.  MAVE: A product dataset for multi-source attribute value extraction. In _Proceedings of the fifteenth ACM international conference on web search and data mining_. 1256–1265.
  * Zhang et al. (2022a) Jiying Zhang, Yuzhao Chen, Xi Xiao, Runiu Lu, and Shu-Tao Xia. 2022a.  Learnable hypergraph laplacian for hypergraph learning. In _ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 4503–4507.
  * Zhang et al. (2022b) Liyan Zhang, Jingfeng Guo, Jiazheng Wang, Jing Wang, Shanshan Li, and Chunying Zhang. 2022b.  Hypergraph and uncertain hypergraph representation learning theory and methods.  _Mathematics_ 10, 11 (2022), 1921.
  * Zhang et al. (2022c) Xinyang Zhang, Chenwei Zhang, Xian Li, Xin Luna Dong, Jingbo Shang, Christos Faloutsos, and Jiawei Han. 2022c.  OA-Mine: Open-World Attribute Mining for E-Commerce Products with Weak Supervision. In _Proceedings of the ACM Web Conference 2022_ (Virtual Event, Lyon, France) _(WWW ’22)_. Association for Computing Machinery, New York, NY, USA, 3153–3161.  https://doi.org/10.1145/3485447.3512035
  * Zhang et al. (2023) Yupeng Zhang, Shensi Wang, Peiguang Li, Guanting Dong, Sirui Wang, Yunsen Xian, Zhoujun Li, and Hongzhi Zhang. 2023\.  Pay attention to implicit attribute values: a multi-modal generative framework for AVE task. In _Findings of the Association for Computational Linguistics: ACL 2023_. 13139–13151.
  * Zheng et al. (2018) Guineng Zheng, Subhabrata Mukherjee, Xin Luna Dong, and Feifei Li. 2018.  OpenTag: Open Attribute Value Extraction from Product Profiles. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_ (London, United Kingdom) _(KDD ’18)_. Association for Computing Machinery, New York, NY, USA, 1049–1058.  https://doi.org/10.1145/3219819.3219839
  * Zhu et al. (2020) Tiangang Zhu, Yue Wang, Haoran Li, Youzheng Wu, Xiaodong He, and Bowen Zhou. 2020\.  Multimodal Joint Attribute Prediction and Value Extraction for E-commerce Product. In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. Association for Computational Linguistics, Online, 2129–2139.  https://doi.org/10.18653/v1/2020.emnlp-main.166

##  6\. Appendix

Table 5. Example of zero-shot dataset statistics in training, validation and testing sets, respectively. Category | Training | Validation | Testing | All
---|---|---|---|---
#P | #A | #PA | #P | #A | #PA | #P | #A | #PA | Ave #A/P
Arts | 10,250 | 1,796 | 8,400 | 3 | 6 | 6 | 15 | 23 | 30 | 2.48
Books | 9,310 | 158 | 5,210 | 4 | 3 | 8 | 413 | 54 | 852 | 1.44
Cellphones | 6,772 | 1,149 | 5,187 | 91 | 109 | 192 | 157 | 175 | 332 | 2.38
Giftcards | 84 | 8 | 74 | 8 | 2 | 16 | 11 | 3 | 9 | 2.37
Grocery | 15,834 | 3,945 | 13,933 | 8 | 16 | 16 | 18 | 33 | 36 | 2.56
Industrial | 2,644 | 1,264 | 2,381 | 16 | 27 | 33 | 8 | 14 | 17 | 2.76
Pet | 12,878 | 2,193 | 13,187 | 24 | 42 | 48 | 73 | 117 | 150 | 3.16
Software | 187 | 87 | 152 | 2 | 4 | 4 | 8 | 14 | 16 | 2.11
Tools | 30,236 | 6,210 | 29,759 | 14 | 24 | 28 | 58 | 97 | 120 | 2.92
Videogames | 559 | 240 | 477 | 35 | 45 | 75 | 57 | 67 | 128 | 2.86
Table 6. Model Training Time in One Epoch (second). Model | Giftcards | Software | Videogames | Industrial | Cellphones | Arts | Pet | Books | Grocery | Tools
---|---|---|---|---|---|---|---|---|---|---
BERT-MLC | 2.37 | 15.48 | 42.12 | 291.60 | 578.78 | 797.11 | 1004.53 | 1073.65 | 1266.68 | 2391.12
BART | 3.66 | 24.48 | 66.60 | 304.56 | 873.36 | 1152.00 | 1292.95 | 1604.52 | 1910.52 | 3521.88
T5small | 2.21 | 19.14 | 58.23 | 256.70 | 698.10 | 967.87 | 1209.27 | 1355.23 | 1576.67 | 2890.03
GNN | 0.09 | 0.19 | 1.00 | 5.46 | 16.46 | 30.02 | 57.50 | 12.80 | 73.33 | 150.91
HGNN | 0.72 | 1.60 | 6.28 | 27.59 | 64.24 | 122.06 | 209.28 | 94.52 | 235.20 | 504.61
HyperPAVE | 0.90 | 1.66 | 6.71 | 30.06 | 70.18 | 133.43 | 224.40 | 89.22 | 251.14 | 543.07

###  6.1. Dataset

Table 5 reports an example of dataset statistics in training, validation, and
testing sets, where $\\#P$, $\\#A$, and $\\#PA$ denotes the number of product
nodes, the number of aspect nodes and the number of product to aspect edges,
respectively. The last column Ave $\\#A/p$ indicates the average number of
attribute value pairs for each product. Because training, validation, and
testing sets for the multi-label zero-shot setting are randomly generated for
each run of the experiment, there exist different dataset statistics.

###  6.2. Parameter Settings

We randomly select unseen attribute value pairs with unseen products following
the sampling rule in Sec. 3.2. For the hyperparameter and configuration of
HyperPAVE, we implement HyperPAVE in PyTorch and optimize it with AdamW
optimizer. We train HyperPAVE and all baselines on the training set and we use
a validation set to select the optimal hyper-parameter settings, and finally
report the performance on the test set. We follow the early stopping strategy
when selecting the model for testing. For all methods, we run 10 times with
different random seeds and report the average results with standard deviation.
Our proposed model HyperPAVE achieves its best performance with the following
setup. The nodes’ features are initialized by a BERT encoder with a
768-dimension size. The max length for category, product, and attribute values
are 32, 512, and 32, respectively. The initial learning rate is selected via
grid search within the range of
$\begin{Bmatrix}5e-1,5e-3,5e-4,5e-5\end{Bmatrix}$ with 1e-6 weight decay for
minimizing the loss. The hidden sizes for convolution layers are 768 in both
HyperConv and GraphConv. The activation function is ReLU. The dropout rate is
0.5 and the batch size is 4. We set the number of neighbors to 20 and the
negative sampling rate is 2.0. For the fusion module, the weights of the
product node embeddings from hyperedges of ‘also buy’, ‘also view’, ‘products
with all aspects’, and ‘category with all products and aspects’ are
dynamically changed for different categories. Experiments are conducted in
Sec. 4.2.4 to explore the weights in these fusion modules.

###  6.3. Experiments

Table 7. Ablation study over HyperPAVE components in the zero-shot setting across seven categories on MAVE dataset. | F1 | mAP | AUC | MRR | NDCG | Hit@5 | Hits@10 | Hits@100
---|---|---|---|---|---|---|---|---
| Arts
nodeID |  1.35 $\pm$ 0.29 |  10.73 $\pm$ 0.52 |  92.03 $\pm$ 0.12 |  0.86 $\pm$ 0.03 |  21.92 $\pm$ 0.58 |  15.00 $\pm$ 1.23 |  28.33 $\pm$ 1.10 |  61.67 $\pm$ 0.64
BERT |  8.23 $\pm$ 0.24 |  26.30 $\pm$ 0.14 |  92.69 $\pm$ 0.06 |  11.48 $\pm$ 0.19 |  40.27 $\pm$ 0.15 |  35.43 $\pm$ 0.27 |  52.86 $\pm$ 0.14 |  82.43 $\pm$ 0.10
BERT (Fine-tuned) |  19.87 $\pm$ 0.15 |  34.77 $\pm$ 0.39 | 99.84 $\pm$ 0.04 |  13.16 $\pm$ 0.17 |  53.84 $\pm$ 0.25 |  75.00 $\pm$ 0.00 |  75.00 $\pm$ 0.00 |  100.00 $\pm$ 0.00
Hyper (Product) |  30.93 $\pm$ 0.26 |  42.33 $\pm$ 0.27 |  99.06 $\pm$ 0.01 |  22.95 $\pm$ 0.27 |  57.84 $\pm$ 0.24 |  57.50 $\pm$ 0.31 |  75.00 $\pm$ 0.03 |  93.75 $\pm$ 0.04
Hyper (Behavior) |  37.03 $\pm$ 0.67 |  42.39 $\pm$ 0.62 |  98.35 $\pm$ 0.02 |  28.51 $\pm$ 0.50 |  60.47 $\pm$ 0.46 |  56.67 $\pm$ 0.29 | 83.33 $\pm$ 0.24 |  100.00 $\pm$ 0.00
HyperPAVE | 43.33 $\pm$ 0.22 | 40.99 $\pm$ 0.18 |  99.22 $\pm$ 0.01 | 47.52 $\pm$ 0.30 | 64.87 $\pm$ 0.39 | 75.00 $\pm$ 0.00 |  82.50 $\pm$ 0.12 | 100.00 $\pm$ 0.00
| Cellphones
nodeID |  19.75 $\pm$ 0.67 |  22.88 $\pm$ 0.20 |  97.72 $\pm$ 0.01 |  10.65 $\pm$ 0.45 |  38.33 $\pm$ 0.23 |  38.33 $\pm$ 0.50 |  57.22 $\pm$ 0.15 |  80.00 $\pm$ 0.11
BERT |  24.21 $\pm$ 0.15 |  26.15 $\pm$ 0.16 |  97.60 $\pm$ 0.02 |  17.02 $\pm$ 0.47 |  40.97 $\pm$ 0.24 |  41.11 $\pm$ 0.05 |  70.05 $\pm$ 0.30 |  86.11 $\pm$ 0.36
BERT (Fine-tuned) |  22.77 $\pm$ 0.16 |  26.80 $\pm$ 0.31 |  98.09 $\pm$ 0.04 |  16.50 $\pm$ 0.43 |  43.03 $\pm$ 0.37 |  50.00 $\pm$ 0.00 |  75.00 $\pm$ 0.00 |  92.50 $\pm$ 0.12
Hyper (Product) |  32.27 $\pm$ 0.28 |  33.32 $\pm$ 0.09 |  98.94 $\pm$ 0.04 |  22.26 $\pm$ 0.30 | 54.17 $\pm$ 0.25 |  70.25 $\pm$ 0.27 | 90.00 $\pm$ 0.00 |  100.00 $\pm$ 0.00
Hyper (Behavior) |  28.32 $\pm$ 0.38 |  33.88 $\pm$ 0.22 | 99.63 $\pm$ 0.01 |  22.57 $\pm$ 0.10 |  47.81 $\pm$ 0.26 |  52.50 $\pm$ 0.14 |  61.67 $\pm$ 0.04 |  97.50 $\pm$ 0.08
HyperPAVE | 39.91 $\pm$ 0.16 | 35.81 $\pm$ 0.18 |  99.22 $\pm$ 0.02 | 23.54 $\pm$ 0.20 |  52.88 $\pm$ 0.18 | 72.50 $\pm$ 0.08 |  75.00 $\pm$ 0.00 | 100.00 $\pm$ 0.00
| Grocery
nodeID |  6.50 $\pm$ 0.49 |  23.31 $\pm$ 0.27 |  95.48 $\pm$ 0.04 |  15.33 $\pm$ 0.19 |  21.98 $\pm$ 0.38 |  22.50 $\pm$ 0.28 |  35.00 $\pm$ 0.31 |  65.00 $\pm$ 0.27
BERT |  14.65 $\pm$ 0.40 |  22.85 $\pm$ 0.34 |  96.18 $\pm$ 0.08 |  15.80 $\pm$ 0.33 |  22.55 $\pm$ 0.42 |  30.10 $\pm$ 0.31 |  35.10 $\pm$ 0.17 |  75.00 $\pm$ 0.51
BERT (Fine-tuned) |  19.42 $\pm$ 0.46 |  25.84 $\pm$ 0.18 |  99.20 $\pm$ 0.01 |  17.78 $\pm$ 0.20 |  27.93 $\pm$ 0.29 |  25.00 $\pm$ 0.10 |  35.50 $\pm$ 0.13 | 87.50 $\pm$ 0.13
Hyper (Product) |  22.41 $\pm$ 0.62 |  32.41 $\pm$ 0.37 |  99.48 $\pm$ 0.02 |  18.82 $\pm$ 0.28 |  35.64 $\pm$ 0.40 |  33.33 $\pm$ 0.71 |  35.50 $\pm$ 0.21 |  66.67 $\pm$ 0.10
Hyper (Behavior) |  29.20 $\pm$ 0.29 |  32.85 $\pm$ 0.49 |  98.34 $\pm$ 0.04 |  14.41 $\pm$ 0.16 |  37.66 $\pm$ 0.37 |  35.05 $\pm$ 0.16 |  50.00 $\pm$ 0.00 |  70.00 $\pm$ 0.11
HyperPAVE | 33.43 $\pm$ 0.28 | 42.71 $\pm$ 0.30 | 99.56 $\pm$ 0.00 | 22.52 $\pm$ 0.38 | 52.64 $\pm$ 0.36 | 50.00 $\pm$ 0.00 | 50.00 $\pm$ 0.00 |  75.50 $\pm$ 0.50
| Industrial
nodeID |  10.40 $\pm$ 0.38 |  16.44 $\pm$ 0.22 |  93.16 $\pm$ 0.05 |  2.59 $\pm$ 0.17 |  30.07 $\pm$ 0.24 |  28.75 $\pm$ 0.49 |  35.00 $\pm$ 0.35 |  68.75 $\pm$ 0.27
BERT |  1.48 $\pm$ 0.24 |  5.37 $\pm$ 0.16 |  89.75 $\pm$ 0.11 |  0.66 $\pm$ 0.10 |  13.58 $\pm$ 0.32 |  8.13 $\pm$ 0.31 |  11.87 $\pm$ 0.54 |  55.63 $\pm$ 0.71
BERT (Fine-tuned) |  14.06 $\pm$ 0.11 |  18.82 $\pm$ 0.50 |  99.05 $\pm$ 0.01 |  4.99 $\pm$ 0.14 |  41.11 $\pm$ 0.50 |  25.00 $\pm$ 0.00 |  50.00 $\pm$ 0.04 |  100.00 $\pm$ 0.00
Hyper (Product) |  19.78 $\pm$ 0.19 |  14.15 $\pm$ 0.17 |  94.34 $\pm$ 0.08 |  7.63 $\pm$ 0.16 |  26.68 $\pm$ 0.16 |  24.73 $\pm$ 0.29 |  37.50 $\pm$ 0.20 |  75.00 $\pm$ 0.40
Hyper (Behavior) |  15.70 $\pm$ 0.31 |  31.42 $\pm$ 0.30 |  96.57 $\pm$ 0.04 |  7.19 $\pm$ 0.33 |  45.26 $\pm$ 0.22 |  41.25 $\pm$ 0.31 |  55.00 $\pm$ 0.35 |  87.50 $\pm$ 0.00
HyperPAVE | 27.70 $\pm$ 0.10 | 33.29 $\pm$ 0.17 | 99.71 $\pm$ 0.01 | 16.10 $\pm$ 0.08 | 54.08 $\pm$ 0.26 | 52.50 $\pm$ 0.18 | 80.00 $\pm$ 0.16 | 100.00 $\pm$ 0.00
| Software
nodeID |  1.97 $\pm$ 0.22 |  18.11 $\pm$ 0.25 |  76.27 $\pm$ 0.18 |  4.39 $\pm$ 0.32 |  30.12 $\pm$ 0.53 |  23.75 $\pm$ 0.58 |  62.50 $\pm$ 0.05 |  100.00 $\pm$ 0.00
BERT |  7.38 $\pm$ 0.14 |  14.10 $\pm$ 0.31 |  74.89 $\pm$ 0.14 |  6.38 $\pm$ 0.29 |  34.19 $\pm$ 0.44 |  26.70 $\pm$ 0.20 |  36.25 $\pm$ 0.11 |  100.00 $\pm$ 0.00
BERT (Fine-tuned) |  11.78 $\pm$ 0.31 |  15.29 $\pm$ 0.50 |  76.70 $\pm$ 0.03 |  6.75 $\pm$ 0.46 |  36.52 $\pm$ 0.45 |  23.75 $\pm$ 0.23 |  37.50 $\pm$ 0.16 |  100.00 $\pm$ 0.00
Hyper (Product) |  35.88 $\pm$ 0.37 |  40.72 $\pm$ 0.16 | 84.40 $\pm$ 0.10 |  21.25 $\pm$ 0.46 |  59.51 $\pm$ 0.18 |  46.25 $\pm$ 0.26 | 63.75 $\pm$ 0.40 |  100.00 $\pm$ 0.00
Hyper (Behavior) |  12.22 $\pm$ 0.36 |  36.33 $\pm$ 0.48 |  81.25 $\pm$ 0.10 |  6.09 $\pm$ 0.27 |  34.19 $\pm$ 0.20 |  25.00 $\pm$ 0.31 |  38.75 $\pm$ 0.51 |  100.00 $\pm$ 0.00
HyperPAVE | 47.62 $\pm$ 0.21 | 51.64 $\pm$ 0.10 |  77.80 $\pm$ 0.12 | 26.66 $\pm$ 0.15 | 63.48 $\pm$ 0.10 | 61.25 $\pm$ 0.40 |  62.50 $\pm$ 0.25 | 100.00 $\pm$ 0.00
| Tools
nodeID |  8.90 $\pm$ 0.37 |  17.00 $\pm$ 0.24 |  97.91 $\pm$ 0.10 |  2.36 $\pm$ 0.19 |  22.27 $\pm$ 0.37 |  50.00 $\pm$ 0.02 |  50.00 $\pm$ 0.00 |  50.00 $\pm$ 0.00
BERT |  14.53 $\pm$ 0.17 |  18.51 $\pm$ 0.25 |  96.21 $\pm$ 0.09 |  6.51 $\pm$ 0.18 |  21.30 $\pm$ 0.48 |  48.50 $\pm$ 0.15 |  52.05 $\pm$ 0.33 |  80.00 $\pm$ 0.20
BERT (Fine-tuned) |  21.33 $\pm$ 0.14 |  23.85 $\pm$ 0.36 |  99.19 $\pm$ 0.05 |  6.81 $\pm$ 0.31 |  26.88 $\pm$ 0.32 |  49.15 $\pm$ 0.26 |  55.70 $\pm$ 0.39 | 87.07 $\pm$ 0.25
Hyper (Product) |  32.86 $\pm$ 0.24 |  29.20 $\pm$ 0.47 |  98.27 $\pm$ 0.06 |  12.26 $\pm$ 0.14 |  43.96 $\pm$ 0.26 |  49.53 $\pm$ 0.35 |  65.00 $\pm$ 0.24 |  83.87 $\pm$ 0.17
Hyper (Behavior) |  31.43 $\pm$ 0.27 |  25.13 $\pm$ 0.25 | 99.30 $\pm$ 0.07 |  11.51 $\pm$ 0.17 |  28.11 $\pm$ 0.23 |  50.06 $\pm$ 0.25 |  58.20 $\pm$ 0.34 |  86.40 $\pm$ 0.18
HyperPAVE | 34.00 $\pm$ 0.28 | 47.83 $\pm$ 0.29 |  98.00 $\pm$ 0.06 | 12.93 $\pm$ 0.18 | 59.05 $\pm$ 0.27 | 52.00 $\pm$ 0.34 | 65.37 $\pm$ 0.25 |  84.72 $\pm$ 0.20
| Videogames
nodeID |  3.25 $\pm$ 0.47 |  7.31 $\pm$ 0.38 |  79.00 $\pm$ 0.58 |  1.49 $\pm$ 0.22 |  17.27 $\pm$ 0.19 |  10.00 $\pm$ 1.21 |  20.00 $\pm$ 1.26 |  70.00 $\pm$ 0.62
BERT |  6.67 $\pm$ 0.41 |  10.25 $\pm$ 0.27 |  85.83 $\pm$ 0.21 |  3.01 $\pm$ 0.52 | 33.30 $\pm$ 0.35 |  30.05 $\pm$ 0.26 |  43.50 $\pm$ 0.35 |  100.00 $\pm$ 0.00
BERT (Fine-tuned) |  12.87 $\pm$ 0.21 |  11.44 $\pm$ 0.17 |  76.84 $\pm$ 0.15 |  4.21 $\pm$ 0.41 |  25.26 $\pm$ 0.29 |  15.71 $\pm$ 0.54 |  37.86 $\pm$ 0.30 |  73.70 $\pm$ 0.26
Hyper (Product) |  20.00 $\pm$ 0.23 |  16.45 $\pm$ 0.19 |  91.51 $\pm$ 0.20 |  8.76 $\pm$ 0.39 |  28.61 $\pm$ 0.25 |  45.00 $\pm$ 0.16 |  50.00 $\pm$ 0.15 | 100.00 $\pm$ 0.00
Hyper (Behavior) |  16.83 $\pm$ 0.26 |  12.38 $\pm$ 0.11 |  86.73 $\pm$ 0.36 |  7.33 $\pm$ 0.16 |  27.28 $\pm$ 0.17 |  15.00 $\pm$ 0.55 |  40.71 $\pm$ 0.38 |  80.71 $\pm$ 0.35
HyperPAVE | 25.31 $\pm$ 0.19 | 21.19 $\pm$ 0.17 |  84.32 $\pm$ 0.05 | 9.31 $\pm$ 0.30 |  23.99 $\pm$ 0.16 | 50.00 $\pm$ 0.50 | 50.00 $\pm$ 0.50 |  85.71 $\pm$ 0.12

Due to limited space in the main context, we only demonstrate ablation study
over three categories (Books, Giftcards, and Pets) in Table 3. Here in Table
7, we report the ablation study over the other seven categories on MAVE. We
also demonstrate the model training time for one epoch across the ten
categories on MAVE in Table 6. All models use the same input max_length as 512
and batch size as 4. For different graph-based models, they show similar
efficiency performance. Thus, we only demonstrate two representative graph-
based models (GNN and HGNN) for training efficiency comparison.


# Implementing an intelligent version of the classical sliding-puzzle game for
unix terminals using Golang’s concurrency primitives

Pravendra Singh
Department of Computer Science and Engineering
Indian Institute of Technology, Roorkee
<EMAIL_ADDRESS>
## Abstract

An intelligent version of the sliding-puzzle game is developed using the new
Go programming language, which uses a concurrent version of the $A^{*}$
Informed Search Algorithm to power solver-bot that runs in the background. The
game runs in computer system’s terminals. Mainly, it was developed for UNIX-
type systems but it works pretty well in nearly all the operating systems
because of cross-platform compatibility of the programming language used.
The game uses language’s concurrency primitives to simplify most of the hefty
parts of the game. A real-time notification delivery architecture is developed
using language’s built-in concurrency support, which performs similar to event
based context aware invocations like we see on the web platform.

##  1 Introduction

Sliding puzzles[1] have their own reputation in the world of artificial
intelligence and graph theory since a long. The oldest type of sliding puzzle
game is known as fifteen puzzle[1]. It is believed to be invented in 1874 by
Noyes Palmer Chapman[2], a postmaster in New York state. The game consists of
a 4x4 board with 16 tiles in it. Each tile have numbers drawn on it except one
tile, which is either blank or sometimes have digit 0 on it. The task for the
game is to re-order all the tiles in a particular manner, where you are only
allowed to move the blank tile at a time.

This type of puzzles have many variants also. The 3x3 board puzzle being
fairly popular among them, also known as the 8-puzzle game. In this type, the
game board consists of 9 tiles. In this paper, we will use the 8-puzzle game
board into consideration.

On the other hand, Go is a new[3] programming language initially developed at
Google, also known as Golang[4]. It’s a compiled and statically-typed language
with built-in support for concurrent programming. Golang is gaining popularity
as the language for system programming and developer operations.

##  2 Solvability

Here, the standard 8-puzzle game board is being considered, where the task of
the game is to put the tiles in such a way that the last tile is blank and all
other tiles have numbers in increasing order(from 1 to 8). A total of
362880(9!) board configurations are possible but only half of them are
actually solvable according to our constraints[23].

So the game generates random configurations of the game board and uses an
built-in package named scanner[5] to scan the board for its solvability. If
the board is not really solvable then it generates a new one recursively.

For its implementation, package scanner uses the discussion from the paper
Notes on the 15 puzzle[6]. A simplified version of this, can be found on the
Analysis of Sixteen Puzzle[7].

Package scanner implements an algorithm to check for solvability of any board
configuration, with time complexity being equivalent to O($n^{2}$). Algorithm
returns a boolean value and an integer value, respectively implying whether a
board is solvable or not and the index of blank tile in the board, if any.

    func isLegal(size int, values []int) (bool, int) {
      var inversions int
      n := len(values)

      for i := 0; i < (n - 1); i++ {
        if (values[i] != 0) && (values[i] != 1) {
          for j := i + 1; j < n; j++ {
            if (values[j] != 0) && (values[i] > values[j]) {
              inversions++
            }
          }
        }
      }

      if (size%2 == 1) && (inversions%2 == 0) {
        return true, zeroIndex(values)
      }
      return false, -1
    }

Function isLegal that returns whether the configuration is legal or not

##  3 Puzzle Solution

The game comes with an built-in package named solver[5] that powers some
features of it. For example, using the solver, the game shows optimal number
of moves to solve any board configuration in real time. All the player moves
are tracked and scored accordingly with the help of the solver.

The package solver is implemented using Golang’s native data structures and
interfaces. It uses $A^{*}$ algorithm[9] for traversing game’s state space.

###  3.1 Heuristic Function

The heuristic function used in the implementation is Misplaced Tiles[8]. Which
is an admissible function[11]. So it will never overestimate the actual
travelling distance and the solution will be always optimal.

h(n) $<=$ $h^{*}$(n) For an Admissible Function
Where h(n) is the Heuristic Function

    func heuristicScore(b board.Board) int {
      var score int
      for i := 0; i < 3; i++ {
        for j := 0; j < 3; j++ {
          if b.Rows[i].Tiles[j].Value != ((3*i + j + 1) % 9) {
            score++
          }
        }
      }

      return score
    }

Function heuristicScore that implements the Misplaced Tiles heuristic function

###  3.2 Open List Data Structure

In the implementation, the game uses a custom data structure to accomplish the
open-list required in the $A^{*}$ algorithm execution. Open List maintains a
collection of game-state nodes to be traversed at any given time.

    type OpenList struct {
      nodeTable map[board.Board]Node
      table map[board.Board]bool

      queue *PriorityQueue
    }

Struct as collection of fields for Open List

####  3.2.1 nodeTable

Golang provides a built-in map[10] type that implements a hash table.

A map is an unordered group of elements of one type, called the element type,
indexed by a set of unique keys of another type, called the key type. The
value of an uninitialized map is nil.[10]

nodeTable maps a board configuration to a node in game’s state space. No node
appears twice when we move from start to goal state, so there is not any
ambiguity. It helps us traversing the path once the search is complete.

####  3.2.2 table

table is also a map which maps board configurations a boolean value. It is
used to check that whether a board configuration is present there in the open-
list or not. By default it returns false whenever the board is absent.

####  3.2.3 queue

queue represents a Priority Queue[12] data structure, precisely it’s a minimum
priority queue. It is used to select a child node of node, having least
travelling cost. Values of travelling cost are used as priorities for nodes.
It is built using golang’s container/heap[13] package.

###  3.3 Close List Data Structure

Similar to Open List, the solver also uses a Close List data structure. It is
used to label nodes as Already Traversed.

    type CloseList struct {
      table map[board.Board]bool
    }

Struct as collection of fields for Close List

####  3.3.1 table

table here is similar to the one used in Open List Data Structure. It maps a
board configuration to a boolean value, indicating whether a board is present
in closed list or not.

##  4 Path Traversing

The search algorithm terminates when the node to enter in the close list is
the goal node. While traversing all the nodes in the game’s state space, it
keeps a track of all the nodes and their respective child nodes.

For this, it keeps a map from child-board configuration to parent-board
configuration, generating a many-to-one mapping because a board configuration
can have 2 to 4 new board configurations as child.

    //Mapping from child to parent’s board configuration
    relation map[board.Board]board.Board

To collect the exact moves from start to the goal state, it forms a linked
list structure of board configurations, where the goal state is at the tail of
the list and at the head it has the board to move next, from the current board
configuration. It is built using the container/list[14] package of Golang.

    state := s.Goal

    for s.relation[state] != start {
      state = s.relation[state]
      s.Path.PushFront(state)
    }

    s.Path.PushBack(s.Goal)

Generating the linked list representing path to move on

##  5 Scoring Function

The game has its own scoring function. The package score[15] helps
implementing this. At any state space node(n), the score for the game can be
calculated by the function, score(n).

$score(n)=ACS(n)/(TotalMoves)$ (1)

$ACS(n)=\begin{cases}0&\quad\text{if }\text{node }n\text{ is start state}\\\
ACS(parent(n))+1&\quad\text{if }\text{last move was correct}\\\
ACS(parent(n))-1&\quad\text{if }\text{last move was incorrect}\\\ \end{cases}$

Where ACS(n) = Accumulated Correct Score for the node n

So in the game, the maximum possible score of 1 will be scored in only one
case when all the moves from player were correct throughout the goal state.
When the total number of moves is 0, the score will also be 0.

##  6 Game Interface

The graphic user interface for the game is built using Box-drawing
characters[16], like it was used in early text-mode video hardware emulators,
also known as Semigraphics[17].

It uses Golang port of the termbox library[18] for writing text-based user
interfaces. Coloring the interfaces is done using normal 8-colors, with
foreground and background attributes for special formatting.

##  7 Real Time Notification

Golang provides built-in support to simplify concurrent programming with the
help goroutines and channels.

A goroutine is a lightweight thread of execution. Channels are the pipes that
connect concurrent goroutines. You can send values into channels from one
goroutine and receive those values into another goroutine.[19]

In this case, the game uses goroutines to provide an asynchronous or non-
blocking experience. So that the graphic interface of game can be drawn and
acted upon as soon as the game starts while the solver stays busy solving the
puzzle in the background at the same time.

Now, this can lead to a problem in slow systems. For example, when the game’s
interface is visible but the solver is taking its time to solve the puzzle and
the player gives any input event, the game is not likely to handle the request
properly. Because the other sections of the game like ’score’ package needs
the puzzle to be solved first.

To solve this, the other concurrency primitive, Channel of the language is
used. It works with the goroutines and implements the notification system for
the game and helps manitaining the asynchronous characteristic of the game.

The game consists of packages notification[20] and surface[21] that implements
this functionality. Package notification has a channel named Tunnel, which let
us flow string objects through it.

Golang has the keyword go to run any portion of code as a goroutine and chan
is the keyword for channels.

    type Notification struct {
      Tunnel chan string
    }

Structure of the Notification entity

The start of the game initiates a goroutine which listens to any object
passing through the channel and update the notification in real-time.

    go func() {
      for e := range s.Notifier.Tunnel {
        s.solvableMoves = s.gameSolver.Path.Len()
        s.currentBoard = s.gameSolver.Path.Front()

        // updates the notification message
        s.Message = e
        s.drawBoard()
      }
    }()

Goroutine helps running the message exchange

So whenever a player moves in wrong direction, the game starts a new goroutine
to solve the new board configuration. If the user tries to move when the
solver has not yet solved the puzzle, it notifies the player to wait for a
while. It invokes the Ready To Play notification as soon as the solver is done
solving for the configuration to let the player know that he is ready to play.
Here[22], you can see list of all the notifications used in the game.

    s.gameSolver = solver.New(s.gameBoard)

    go func() {
      s.gameSolver.Solve()
      s.solved = false
      s.solvableMoves = s.gameSolver.Path.Len()

      s.NotificationColor = termbox.ColorGreen

      // PASS THE NOTIFICATION INTO THE CHANNEL
      s.Notifier.Tunnel <- notification.ReadyToPlayMessage
    }()

Handling of a wrong move by player

The notification channel Tunnel is closed when the game is complete or
whenever player quits the game.

    close(s.Notifier.Tunnel)

##  8 Acknowledgements

The author is grateful to his Artificial Intelligence course instructor Mr.
Partha Pratim Roy. Rob Pike, Ken Thompson, Robert Griesemer and many Golang
contributors to make the language such stupendous. nsf(https://github.com/nsf)
for developing the termbox-go library.

##  9 References

  1. 1.

http://en.wikipedia.org/wiki/Sliding_puzzle - Sliding Puzzle

  2. 2.

The 15 Puzzle, by Jerry Slocum & Dic Sonneveld, 2006. ISBN 1-890980-15-3

  3. 3.

Release History The Go Programming Language -
https://golang.org/doc/devel/release.html

  4. 4.

The Go Programming Language - https://golang.org/

  5. 5.

Package ’solver’ - https://github.com/pravj/puzzl/blob/master/solver/solver.go

  6. 6.

Notes on the ”15” Puzzle - Wm. Woolsey Johnson and William E. Story

  7. 7.

Analysis of the Sixteen Puzzle, Kevin Gong -
http://kevingong.com/Math/SixteenPuzzle.html

  8. 8.

Heuristicwiki - Misplaced Tiles -
http://heuristicswiki.wikispaces.com/Misplaced+Tiles

  9. 9.

A* search algorithm - http://en.wikipedia.org/wiki/A*_earch_algorithm

  10. 10.

The Go Programming Language Specification - Map types -
https://golang.org/ref/spec#Map_types

  11. 11.

Admissible heuristic - http://en.wikipedia.org/wiki/Admissible_heuristic

  12. 12.

Priority queue - http://en.wikipedia.org/wiki/Priority_queue

  13. 13.

Package heap - The Go Programming Language -
http://golang.org/pkg/container/heap/

  14. 14.

Package list - The Go Programming Language -
http://golang.org/pkg/container/list/

  15. 15.

Package ’score’ - https://github.com/pravj/puzzl/blob/master/score/score.go

  16. 16.

Box-drawing character - http://en.wikipedia.org/wiki/Box-drawing_character

  17. 17.

Semigraphics - http://en.wikipedia.org/wiki/Semigraphics

  18. 18.

Package termbox - http://godoc.org/github.com/nsf/termbox-go

  19. 19.

Go By Example - https://gobyexample.com/channels

  20. 20.

Package ’notification’ -
https://github.com/pravj/puzzl/blob/master/notification/notification.go

  21. 21.

Package ’surface’ -
https://github.com/pravj/puzzl/blob/master/surface/surface.go

  22. 22.

Notification Messages -
https://github.com/pravj/puzzl/blob/development/notification/notification.go#L5-L14

  23. 23.

M. Gardner. The Mathematical Puzzles of Sam Loyd. Dover, 1959