# MSTR: Multi-Scale Transformer for End-to-End
Human-Object Interaction Detection

Bumsoo Kim
LG AI Research
<EMAIL_ADDRESS>this work was done in Kakao Brain Jonghwan Mun
Kakao Brain
Kyoung-Woon On
Kakao Brain
Minchul Shin
Kakao Brain
Junhyun Lee
Korea University
Eun-Sol Kim
Department of Computer Science
Hanyang University

###### Abstract

Human-Object Interaction (HOI) detection is the task of identifying a set of
$\langle$human, object, interaction$\rangle$ triplets from an image. Recent
work proposed transformer encoder-decoder architectures that successfully
eliminated the need for many hand-designed components in HOI detection through
end-to-end training. However, they are limited to single-scale feature
resolution, providing suboptimal performance in scenes containing humans,
objects, and their interactions with vastly different scales and distances. To
tackle this problem, we propose a Multi-Scale TRansformer (MSTR) for HOI
detection powered by two novel HOI-aware deformable attention modules called
Dual-Entity attention and Entity-conditioned Context attention. While existing
deformable attention comes at a huge cost in HOI detection performance, our
proposed attention modules of MSTR learn to effectively attend to sampling
points that are essential to identify interactions. In experiments, we achieve
the new state-of-the-art performance on two HOI detection benchmarks.

##  1 Introduction

Figure 1: Multi-scale attention of MSTR on interactions including: (a) large
human with small object, (b) distant human and object, and (c) small human and
a large object. The top row (high resolution) and the bottom row (low
resolution) captures the context of the interaction in various scales. Best
viewed in color.

Human-Object Interaction (HOI) detection is a task to predict a set of
$\langle$human, object, interaction$\rangle$ triplets in an image [9].
Previous methods have indirectly addressed this task by detecting human and
object instances and individually inferring interaction labels for every pair
of the detected instances with either neural networks (_i.e_., two-stage HOI
detectors [8, 7, 10, 25, 27, 30, 23, 31, 24, 34, 19, 6, 1, 35, 22, 17, 20, 29,
37]) or triplet matching (_i.e_., one-stage HOI detectors [32, 21, 13]). The
additional complexity caused by this indirect inference structure and post-
processing (_e.g_., NMS) stage behaved as a major bottleneck in inference time
in HOI detection. To deal with this bottleneck, transformer-based HOI
detectors [14, 26, 4, 39] have been proposed to achieve end-to-end HOI
detection without the need for the post-processing stage mentioned above.
These works have shown competitive performance in both accuracy and inference
time with direct set-level prediction and transformer attentions that can
exploit the contextual information between humans, objects, and their
interactions.

However, due to the huge computational costs raised when processing multi-
scale feature maps (with about 20$\times$ more image tokens) with transformer
attention, current transformer-based HOI detectors are limited to using only
single-scale feature maps. Due to this limitation, previous transformer-based
approaches demonstrate suboptimal performance, especially for scenes where
humans, objects, and the contextual information for their interactions exist
at various scales.

In this paper, we propose Multi-Scale TRasnformer (MSTR), a transformer-based
HOI detector that can exploit multi-scale feature maps for HOI detection.
Inspired by previously proposed deformable attention for standard object
detection [38], we aim to efficiently explore multi-scale feature maps by
attending to only a small number of sampling points generated from the query
element instead of calculating the attention values for the entire spatial
dimension. Yet, we found out in our preliminary experiments that directly
applying naïve deformable attention in HOI detection leads to a serious
performance drop.

To overcome this deterioration, we equipped MSTR with two novel HOI-aware
deformable attentions, referred by Dual-Entity Attention and Entity-
conditioned Context Attention, which are designed to capture the complicated
semantics of Human-Object Interaction throughout multi-resolution feature maps
(see Figure 1). Specifically, precise entity-level semantics for humans and
objects are captured by Dual-Entity attention, while the contextual
information for the interaction is conditionally reimbursed by Entity-
conditioned Context attention. To further improve performance, we delve into
decoder architectures that can effectively handle the multiple semantics
obtained from the two HOI-aware attentions above.

The main contributions of our work are threefold:

  * •

We propose MSTR, the first transformer-based HOI detector that exploits multi-
scale visual feature maps.

  * •

We propose new deformable attention modules, called Dual-Entity attention and
Entity-conditioned Context attention, which effectively and efficiently
capture human, object, and context information associated with HOI queries.

  * •

We explore decoder architectures to handle the multiple semantics captured by
our proposed deformable attentions and further improve HOI detection
performance.

##  2 Preliminary

In this section, we start with a basic pipeline of a transformer-based end-to-
end HOI detector [26]. Then, we explain the deformable attention module [38]
that reduces computational cost in attention, thus enabling the transformer to
take multi-scale feature maps as an input. Afterward, we discuss why the
direct application of multi-scale deformable attentions is not suitable for
HOI detection.

###  2.1 End-to-End HOI Detection with Transformers

Out of the multiple candidates [14, 26, 4, 39] using transformers for HOI
detection, we adopt QPIC [26] as our baseline due to its simple structure and
good performance.

#### Set Prediction.

Transformer-based HOI detectors formulate the task as a set-level prediction
problem. It is achieved by exploiting a fixed number of HOI queries, each of
which generates four types of predictions: 1) the coordinate of the human
bounding box (_i.e_., subject of the interaction), 2) the coordinate of the
object bounding box (_i.e_., target of the interaction), 3) the object class
and 4) the interaction type. Note that the set-level predictions are learned
using losses based on Hungarian Matching with ground-truths.

#### Transformer Encoder-Decoder Architecture.

The architecture of QPIC [26] consists of a backbone CNN, a transformer
encoder, and a transformer decoder. Given an image, a single-scale visual
feature map is extracted by the backbone CNN, and then positional information
is added to the feature map. The transformer encoder takes the visual features
and returns contextualized visual features with self-attention layers. In the
transformer decoder, HOI queries are first processed by the self-attention
layer, and then the cross-attention layer associates the HOI queries with the
contextualized visual features (given by the encoder) to capture relevant HOI
representations. Finally, predictions for HOI are computed from individual
contextualized HOI query embeddings as mentioned above. Note that both self-
attention and cross-attention adopt multi-head attention.

To be specific, given a single-scale input feature map
$x\in\mathbb{R}^{C\times H\times W}$ where $C$ is the feature dimension, the
single-scale multi-head attention $f^{sg}_{q}=\mbox{SSAttn}(z_{q},x)$ for the
$q^{th}$ query feature $z_{q}$ (either an image token for the encoder or an
HOI query for the decoder) is calculated by

$f^{sg}_{q}=\sum_{m=1}^{M}{W_{m}}\big{[}\sum_{k\in\Omega_{k}}{A_{mqk}\cdot
W^{\prime}_{m}x_{k}}\big{]},$ (1)

where $A_{mqk}$ indicates an attention weight calculated with learnable
weights $U_{m},V_{m}\in\mathbb{R}^{C_{v}\times C}$ as
$\text{exp}\big{(}\frac{z_{q}^{T}U_{m}^{T}V_{m}x_{k}}{\sqrt{C_{v}}}\big{)}$.
Throughout this paper, for the attention module, we let $m$ index the
attention head ($1\leq m\leq M$), $q\in\Omega_{q}$ indexes a query element
with feature $z_{q}\in\mathbb{R}^{C}$, $k\in\Omega_{k}$ indexes a key element
with feature $z_{k}\in\mathbb{R}^{C}$, while $\Omega_{q}$ and $\Omega_{k}$
specify the set of query and key elements, respectively. $W_{m}$ and
$W^{\prime}_{m}$ are learnable embedding parameters for $m^{\text{th}}$
attention head, and $A_{mqk}$ is normalized as
$\sum_{k\in\Omega_{k}}A_{mqk}=1$.

#### Complexity.

Given an input feature map $x\in\mathbb{R}^{C\times H\times W}$ and $N$ HOI
queries, the complexity of transformer encoder and decoder are
$O(H^{2}W^{2}C)$ and $O(HWC^{2}+NHWC+2NC^{2}+N^{2}C)$, respectively. Since the
complexity grows in quadratic scale as the spatial resolution ($H$,$W$)
increases, it raises significant complexity when exploiting multi-resolution
feature maps where there are about 20$\times$ more features to process.

#### Towards Multi-Scale HOI detection.

In HOI detection, not only do humans and objects exist at various scales, but
they also interact at various distances in images. Therefore, it is essential
to exploit multi-scale feature maps $\\{x\\}_{l=1}^{L}$ (where
$x^{l}\in\mathbb{R}^{C\times H_{l}\times W_{l}}$, $l$ indexes the feature
level) to deal with the various scales of objects and contexts to capture
interactions precisely. However, as multi-scale feature maps have almost
$\times 20$ more elements to process than a single-scale feature map, it
provokes a serious complexity issue in calculating Eq. (1).

###  2.2 Revisiting Deformable Transformers

The deformable attention module is proposed to deal with the problem of high
complexity in the transformer attention. The core idea is to reduce the number
of key elements in the attention module by sampling the small number of
spatial locations related to regions of interest for each query element.

#### Sampling Locations for Deformable Attention.

Given a multi-scale input feature map $\\{x^{l}\\}_{l=1}^{L}$ where
$x^{l}\in\mathbb{R}^{C\times H_{l}\times W_{l}}$, the $K$ sampling locations
of interest for each attention head and each feature level are generated from
each query element $z_{q}\in\mathbb{R}^{C}$. Because direct prediction of
coordinates of sampling location is difficult to learn, it is formulated as
prediction of a reference point $r_{q}\in[0,1]^{2}$ and $K$ sampling offsets
$\Delta r_{q}\in\mathbb{R}^{M\times L\times K\times 2}$. Then, the
$k^{\text{th}}$ sampling location at $l^{\text{th}}$ feature level and
$m^{\text{th}}$ attention head for query element $z_{q}$ is defined by
$p_{mlqk}=\phi_{l}(r_{q})+\Delta r_{mlqk}$ where $\phi_{l}(\cdot)$ is a
function to re-scale the coordinate of reference point to the input feature
map of the $l^{\text{th}}$ level.

#### Deformable Attention Module.

Given a multi-scale input feature map $\\{x^{l}\\}_{l=1}^{L}$, the multi-scale
deformable attention
$f^{ms}_{q}=\mbox{MSDeformAttn}(z_{q},p_{q},\\{x^{l}\\}_{l=1}^{L})$ for query
element $z_{q}$ is calculated using a set of predicted sampling locations
$p_{q}$ as follows:

$\begin{split}f^{ms}_{q}=\sum_{m=1}^{M}{W_{m}}\big{[}\sum_{l=1}^{L}{\sum_{k=1}^{K}{A_{mlqk}\cdot
W^{\prime}_{m}\Phi_{mlqk}}}\big{]},\end{split}$ (2)

where $l$, $k$ and $m$ index the input feature level, the sampling location
and the attention head, respectively, while $A_{mlqk}$ indicates an attention
weight for the $k^{th}$ sampling location at the $l^{th}$ feature level and
the $m^{th}$ attention head. $\Phi_{mlqk}$ means the sampled $k^{\text{th}}$
key element at $l^{\text{th}}$ feature level and $m^{\text{th}}$ attention
head using the sampling location, which is obtained by bilinear interpolation
as $\Phi_{mlqk}=x^{l}(p_{mlqk})=x^{l}(\phi_{l}(r_{q})+\Delta r_{mlqk})$. Note
that for each query element, the attention computation is performed with only
sampled regions of interest where the sampled number ($=LMK$) is much smaller
than the number of all the key elements ($\sum_{l=1}^{L}H_{l}W_{l}$), thus
leads to a reduced computational cost.

#### Problem with Direct Application to HOI Detection.

Deformable attention effectively reduces the complexity of exploiting multi-
scale features with transformers to an acceptable level. However, while the
sampling procedure above does not deteriorates performance in standard object
detection, it causes a serious performance drop in HOI detection (29.07
$\rightarrow$ 25.53) as shown in Table 3. We conjecture that this is partly
due to the following reasons. First, unlike the object detection task where an
object query is associated with a single object, an HOI query is entangled
with multiple semantics (_i.e_., human, object, and their interaction); thus
learning to sample the region of interest for multiple semantics with
individual HOI queries (especially with sparse information) is much
challenging compared to the counterpart of object detection. Second,
deformable attention is learned to attend only to the sampling points near the
localized objects; this leads to the loss of contextual information that is an
essential clue for precise HOI detection. The following sections describe how
we resolve these issues and improve performance.

##  3 Method

Figure 2:  Illustration of (a) Deformable Attention, (b) Dual-Entity
Attention, (c) Entity-conditioned Context Attention (abbrevieated as EC). The
sampling point for deformable attention is obtained by combining the reference
points with sampling offset. In (a), both reference points
$r_{q}=(r_{qx},r_{qy})$ and sampling offsets $\Delta r_{q}=(\Delta
r_{qx},\Delta r_{qy})$ are obtained from a single hoi query feature $z_{q}$.
In (b), the reference points and sampling offsets for the humans
$h_{q}=(h_{qx},h_{qy})$, $\Delta h_{q}=(\Delta h_{qx},\Delta h_{qy})$ and
objects $o_{q}=(o_{qx},o_{qy})$, $\Delta o_{q}=(\Delta o_{qx},\Delta o_{qy})$
are obtained from $z_{q}^{h}$ and $z_{q}^{o}$, respectively, which is obtained
by a linear projection of $z_{q}$ (dotted line). In (c), the sampling offsets
$\Delta c_{q}=(\Delta c_{qx},\Delta c_{qy})$ are obtained from $z_{q}$ while
the reference points are obtained in conditional to entities in (b).

In this section, we introduce MSTR, a novel deformable transformer
architecture that is suitable for multi-scale HOI detection. To resolve the
problems described in our preliminary, MSTR features new HOI-aware deformable
attentions designed for HOI detection, referred by Dual-Entity attention and
Entity-conditioned Context attention.

###  3.1 HOI-aware Deformable Attentions

The objective of our HOI-aware deformable attentions (Dual-Entity attention
and Entity-conditioned Context attention) is to efficiently and effectively
extract information of HOIs from multi-scale feature maps for a given HOI
query. Figure 2 shows conceptual illustrations of (a) deformable attention in
literature [38], (b) Dual-Entity attentions and (c) Entity-conditioned Context
attention.

#### Dual-Entity attention for Human/Object.

In HOI detection, the HOI query includes complex and entangled information of
multiple semantics: human, object, and interaction information. Therefore, it
is challenging to accurately predict sampling locations appropriate for each
semantic from a single HOI query. To make sampling locations easier, given an
HOI query feature $z_{q}$, our Dual-Entity attention separately identifies
sampling locations for the humans ($p^{h}_{q}$) and objects ($p^{o}_{q}$).
First, we project $z_{q}$ with two linear layers to obtain $z_{q}^{h}$ and
$z_{q}^{o}$. The $k^{\text{th}}$ sampling location at $l^{\text{th}}$ feature
level and $m^{\text{th}}$ attention head for human and object are represented
by

$\begin{split}p^{h}_{mlqk}=\phi_{l}(h_{q})+\Delta h_{mlqk},\\\
p^{o}_{mlqk}=\phi_{l}(o_{q})+\Delta o_{mlqk},\end{split}$ (3)

where $h_{q}$, $\Delta h$ is the reference point and sampling offsets for
humans, and $o_{q}$, $\Delta o$ is the reference point and sampling offsets
for objects, each obtained by a linear projection of $z_{q}^{h}$ and
$z_{q}^{o}$, respectively. Then, based on the sampled locations, attended
features for human ($f_{q}^{h}$) and object ($f_{q}^{o}$) are computed by

$\begin{split}f_{q}^{h}=\text{MSDeformAttn}(z_{q}^{h},p_{q}^{h},\\{x^{l}\\}_{l=1}^{L}),\\\
f_{q}^{o}=\text{MSDeformAttn}(z_{q}^{o},p_{q}^{o},\\{x^{l}\\}_{l=1}^{L}).\end{split}$
(4)

#### Entity-conditioned Context attention.

In HOI detection, contextual information often gives an important clue in
identifying interactions. From this point of view, utilizing the local
features obtained from near the human and object regions through the Dual-
Entity attention is not sufficient to capture contextual information (see our
experimental result in Table 3). To compensate for this, we define an
attention with an additional set of sampling points, namely Entity-conditioned
Context attention, that is designed to capture the contextual information in
specific.

Given the 2D reference points for the human $h_{q}=(h_{qx},h_{qy})$ and the
object $o_{q}=(o_{qx},o_{qy})$, the reference point for Entity-conditioned
Context attention is conditionally computed with the two references. Motivated
by existing works [32, 21, 36], we define the reference points for interaction
as the center of human and object, _i.e_.,
$c_{q}=\big{(}\frac{h_{qx}+o_{qx}}{2},\frac{h_{qy}+o_{qy}}{2}\big{)}$. Note
that we empirically observe that such simple reference points offer
competitive performance compared to ones predicted using an additional
network, while being much faster. Then, we predict the sampling offsets
$\Delta c_{q}$ from the HOI query feature, obtaining
$p^{c}_{mlqk}=\phi_{l}(c_{q})+\Delta c_{mlqk}$. Finally, the attended feature
for contextual information $f^{c}_{q}$ is computed using sampling location
$p_{q}^{c}$ as follows:

$\begin{split}f_{q}^{c}=\text{MSDeformAttn}(z_{q},p_{q}^{c},\\{x^{l}\\}_{l=1}^{L}).\end{split}$
(5)

Figure 3: Overall pipeline of MSTR. On top of the standard transformer
encoder-decoder architecture for HOI detection (_i.e_., QPIC), we leverage
deformable samplings for the encoder self-attention and the decoder cross-
attention modules to deal with the huge complexity caused by using multi-scale
feature maps. For the decoder cross-attention, we leverage three sets of key
elements sampled for our Dual-Entity attention (denoted as DE sampling, DE
attention) and Entity-conditioned Context attention (denoted as EC sampling,
EC attention).

###  3.2 MSTR Architecture

Figure 4:  Comparison of a simple 2-layer Decoder architecture for
Transformer-based HOI detectors: (a) conventional one introduced in QPIC, and
(b) HOI-aware one in MSTR. Entity-conditioned Context attention is abbreviated
as Context Attention. MSTR stacks decoder layers by merging the self attention
outputs, which further improves performance (see Table 3).

In this section, the overall architecture of MSTR with our suggested two
deformable attentions will be described (see Figure 3). MSTR follows the
previous transformer encoder-decoder architecture, where the encoder performs
self-attention given the image features while the decoder performs self-
attention for HOI queries followed by cross-attention between updated HOI
queries and the encoded image features.

#### Encoder.

The encoder of MSTR takes multi-scale input feature maps given by a backbone
CNN, performs a series of deformable attention modules in Eq.(2), and finally
generates encoded feature maps. Positional encoding [2] is added to preserve
spatial information while level embedding [38] is added to denote which
resolution did the image feature comes from.

#### Decoder.

By leveraging our HOI-aware deformable attentions, the cross-attention layer
in MSTR decoder extracts three different semantics (human, object, and
contextual information) for each HOI query from the encoded image features.
For each decoder layer, we discovered that compositing the multiple semantics
obtained from the previous cross-attention layer [5] by summing the semantics
after applying individual self-attention demonstrates the best performance
(see Table 3 and Appendix). The input for the $(k+1)$-th layer of our HOI-
aware deformable attention $\bar{z}_{q}^{k+1}$ is written as:

$\bar{z}_{q}^{k+1}=\mbox{SA}(f^{h}_{q}(k))+\mbox{SA}(f^{o}_{q}(k))+\mbox{SA}(f^{c}_{q}(k)),$
(6)

where $f^{h}_{q}(k)$, $f^{o}_{q}(k)$, $f^{c}_{q}(k)$ denotes the multiple
semantic outputs of the previous ($k$-th) decoder obtained by Eq.(6) and
Eq.(5), respectively. SA denotes Multi-Head Self-Attention operation with
Eq.(1) [28] and
$\bar{z}_{q}^{1}=\text{SA}(z_{q})+\text{SA}(z_{q}^{h})+\text{SA}(z_{q}^{o})$.

#### MSTR Inference.

Given the cross attention results of the final decoder layer where $f_{q}^{h}$
and $f_{q}^{o}$ is obtained by Eq. (6) and $f_{q}^{c}$ is obtained by Eq. (5),
the final prediction heads in MSTR predict the
$\langle\text{bbox}^{h}_{q},\text{bbox}^{o}_{q},\text{cls}^{o}_{q},\text{act}_{q}\rangle$
using FFN as follows:

$\displaystyle(u_{qx},u_{qy},u_{qw},u_{qh})=\mbox{FFN}_{\mbox{hbox}}(f^{h}_{q}),$
(7)
$\displaystyle(v_{qx},v_{qy},v_{qw},v_{qh})=\mbox{FFN}_{\mbox{obox}}(f^{o}_{q}),$
(8) $\displaystyle\mbox{cls}_{q}=\sigma(\mbox{FFN}_{\mbox{cls}}(f^{o}_{q})),$
(9) $\displaystyle\mbox{act}_{q}=\sigma(\mbox{FFN}_{\mbox{act}}(f^{c}_{q})),$
(10)

where $\text{cls}_{q}$ and $\text{act}_{q}$ each denote predictions for object
the class and the action class after sigmoid function, and final
$\text{bbox}^{h}_{q}$ is predicted with the center point
$\big{(}\sigma(u_{qx}+\sigma^{-1}(h_{qx})),\sigma(u_{qy}+\sigma^{-1}(h_{qy}))\big{)}$,
width $u_{qw}$, and height $u_{qh}$. Likewise, the $\text{bbox}^{o}_{q}$ is
predicted with center point as
$\big{(}\sigma(v_{qx}+\sigma^{-1}(o_{qx})),\sigma(v_{qy}+\sigma^{-1}(o_{qy}))\big{)}$,
width $v_{qw}$, and height $v_{qh}$. $\sigma$ and $\sigma^{-1}$ denote the
sigmoid and inverse sigmoid function, respectively, and is used to normalize
the reference points $h_{q},o_{q}$ and the predicted coordinates of human
boxes and object boxes $u_{q\\{x,y,w,h\\}},v_{q\\{x,y,w,h\\}}\in\mathbb{R}$.

##  4 Experiment

In this section, we show the experimental results of our model in HOI
detection. We first describe the experimental settings such as datasets and
evaluation metrics. Next, we compare MSTR with state-of-the-art works on two
different benchmarks (V-COCO and HICO-DET) and provide detailed ablation study
for each component. Through the experiments, we demonstrate that MSTR
successfully extends conventional transformer-based HOI detectors to utilize
multi-scale feature maps, and emphasize that each component of MSTR
contributes to the final HOI detection performance. Lastly, we provide
extensive qualitative results of MSTR.

###  4.1 Datasets and Metrics

We evaluate our model on two widely-used public benchmarks: the V-COCO (Verbs
in COCO) [9] and HICO-DET [3] datasets. V-COCO is a subset of COCO composed of
5,400 trainval images and 4,946 test images. For V-COCO dataset, we report the
$\text{AP}_{\text{role}}$ over $25$ interactions in two scenarios. HICO-DET
contains 37,536 and 9,515 images for each training and test split with
annotations for 600 $\langle verb,object\rangle$ interaction types. We follow
the previous settings and report the mAP over two evaluation settings (Default
and Known Object), each with three different category sets: (1) all 600 HOI
categories in HICO (Full), (2) 138 HOI categories with less than 10 training
instances (Rare), and (3) 462 HOI categories with 10 or more training
instances (Non-Rare). See Appendix for details of the evaluation settings.

Method | Backbone | $AP_{\text{role}}^{\\#1}$ | $AP_{\text{role}}^{\\#2}$
---|---|---|---
Models with external features
TIN (R$\text{P}_{\text{D}}\text{C}_{\text{D}}$) [20] | R50 | 47.8 | -
Verb Embedding [34] | R50 | 45.9 | -
RPNN [37] | R50 | - | 47.5
PMFNet [29] | R50-FPN | 52.0 | -
PastaNet [19] | R50-FPN | 51.0 | 57.5
PD-Net [35] | R50 | 52.0 | -
ACP [15] | R152 | 53.0 | -
FCMNet [22] | R50 | 53.1 | -
ConsNet [23] | R50-FPN | 53.2 | -
Sequential HOI Detectors
VSRL [9] | R50-FPN | 31.8 | -
InteractNet [8] | R50-FPN | 40.0 | 48.0
BAR-CNN [16] | R50-FPN | 43.6 | -
GPNN [25] | R152 | 44.0 | -
iCAN [7] | R50 | 45.3 | 52.4
TIN (R$\text{C}_{\text{D}}$) [20] | R50 | 43.2 | -
DCA [31] | R50 | 47.3 | -
VCL [12] | R50-FPN | 48.3 | -
DRG [6] | R50-FPN | 51.0 | -
VSGNet [27] | R152 | 51.8 | 57.0
IDN [18] | R50 | 53.3 | 60.3
Parallel HOI Detectors
UnionDet [13] | R50-FPN | 47.5 | 56.2
IPNet [32] | HG104 | 51.0 | -
HOI Transformer [39]† | R101 | 52.9 | -
ASNet [4]† | R50 | 53.9 | -
GGNet [36] | HG104 | 54.7 | -
HOTR [14]† | R50 | 55.2 | 64.4
QPIC [26]† | R50 | 58.8 | 61.0
MSTR (Ours) | R50 | 62.0 | 65.2
Table 1: Comparison of performance on V-COCO test set. $AP_{\text{role}}^{\\#1}$, $AP_{\text{role}}^{\\#2}$ denotes the performance under Scenario 1 and Scenario 2 in V-COCO, respectively. $\dagger$ denotes end-to-end HOI detectors with transformers, which are the main baselines for our work. | Default | Known Object
---|---|---
Method | Detector | Backbone | Feature | Full | Rare | Non Rare | Full | Rare | Non Rare
Sequential HOI Detectors
Functional Gen. [1] | HICO-DET | R101 | A+S+L | 21.96 | 16.43 | 23.62 | - | - | -
TIN [20] | HICO-DET | R50 | A+S+P | 22.90 | 14.97 | 25.26 | - | - | -
VCL [12] | HICO-DET | R50 | A+S | 23.63 | 17.21 | 25.55 | 25.98 | 19.12 | 28.03
ConsNet [23] | HICO-DET | R50-FPN | A+S+L | 24.39 | 17.10 | 26.56 | 30.34 | 23.40 | 32.41
DRG [6] | HICO-DET | R50-FPN | A+S | 24.53 | 19.47 | 26.04 | 27.98 | 23.11 | 29.43
IDN [18] | HICO-DET | R50 | A+S | 24.58 | 20.33 | 25.86 | 27.89 | 23.64 | 29.16
Parallel HOI Detectors
UnionDet [13] | HICO-DET | R50-FPN | A | 17.58 | 11.72 | 19.33 | 19.76 | 14.68 | 21.27
PPDM [21] | HICO-DET | HG104 | A | 21.10 | 14.46 | 23.09 | 24.81 | 17.09 | 27.12
HOI Transformer [39]† | HICO-DET | R50 | A | 23.46 | 16.91 | 25.41 | 26.15 | 19.24 | 28.22
HOTR [14]† | HICO-DET | R50 | A | 25.10 | 17.34 | 27.42 | - | - | -
GGNet [36] | HICO-DET | HG104 | A | 28.83 | 22.13 | 30.84 | 27.36 | 20.23 | 29.48
AS-Net [4]† | HICO-DET | R50 | A | 28.87 | 24.25 | 30.25 | 31.74 | 27.07 | 33.14
QPIC [26]† | HICO-DET | R50 | A | 29.07 | 21.85 | 31.23 | 31.68 | 24.14 | 33.93
MSTR (Ours) | HICO-DET | R50 | A | 31.17 | 25.31 | 32.92 | 34.02 | 28.83 | 35.57
Table 2:  Performance comparison in HICO-DET. The Detector column is denoted
as ‘HICO-DET’ to show that the object detector is fine-tuned on the HICO-DET
training set. Each letter in Feature column stands for A: Appearance (Visual
Features), S: Interaction Patterns (Spatial Correlations), P: Pose Estimation,
L: Linguistic Priors, V: Volume. $\dagger$ denotes end-to-end HOI detectors
with transformers. Note that all the baseline models without $\dagger$ are
already based on multi-scale feature maps.

###  4.2 Quantitative Results

We use the standard evaluation code 111https://github.com/YueLiao/PPDM
following the previous works [14, 26, 4, 39] to calculate metric scores for
both V-COCO and HICO-DET.

#### Comparison to State-of-The-Art.

We compare MSTR with state-of-the-art methods in Table 1 and Table 2. In Table
1, MSTR outperforms the previous state-of-the-art method in V-COCO dataset by
a large margin (+3.2p in $\text{AP}_{\text{role}}^{\\#1}$ and +4.2p in
$\text{AP}_{\text{role}}^{\\#1}$). Similar to this, in Table 2, MSTR achieves
the highest mAP on HICO-DET dataset in all Full, Rare, and Non-Rare classes
obtaining +2.1p, +3.46p, and +1.69p gain for each compared to the previous
state-of-the-art. We use the same scoring function as QPIC without any
modification for a fair comparison. Note that MSTR benefits from the
advantages of using deformable attention: the fast convergence for training
[38] (see more details and the convergence graph in our Appendix).

Method | MS | DA | DE | EC | mAP
---|---|---|---|---|---
(a) QPIC |  |  |  |  | 29.07
(b) SS-Baseline |  | ✓ |  |  | 25.53
(c) SS-Baseline + DE |  | ✓ | ✓ |  | 27.06
(d) SS-Baseline + DE + EC |  | ✓ | ✓ | ✓ | 27.70
(e) MS-Baseline | ✓ | ✓ |  |  | 27.52
(f) MS-Baseline + DE | ✓ | ✓ | ✓ |  | 28.30
(g) MS-Baseline + DE + EC | ✓ | ✓ | ✓ | ✓ | 30.14
(h) MSTR (Ours) | ✓ | ✓ | ✓ | ✓ | 31.17

Table 3:  Comparison of MSTR with our baseline QPIC and its variants in the
HICO-DET test set. SS and MS denote the models using single scale feature map
and multi-scale feature maps, respectively. DE and EC indicate our proposed
Dual-Entity attention and Entity-conditioned Context attention, respectively.

###  4.3 Ablation Study

We perform ablations to check the effects of our proposed Dual-Entity
attention, Entity-conditioned Context attention, and our proposed decoder
architecture that merges the self-attention of the multiple semantics.

#### Baselines.

On basis of QPIC [26] structure, we define several variants for baselines by
applying different combinations of sub-components from MSTR: multi-scale
feature maps (MS), Deformable Attention (DA), Dual-Entity attention (DE), and
Entity-conditioned Context attention (EC). Specifically, since deformable
attention can be also applied to a single-scale feature map, SS-Baseline
denotes QPIC where the attention in the transformer is replaced by DA. Our
work can be seen as a process of improving the score to the state-of-the-art
by adapting MS, DE, EC step by step to SS-Baseline. MS-Baseline+DE+EC
represents MSTR without merging with self-attention, instead simply passing
the sum of the outputs to the next decoder layer.

#### HOI-Aware Deformable Attentions.

In Table 3, we explore the effect of our proposed HOI-Aware Deformable
Attentions: Dual-Entity attention and Entity-conditioned Context attention. As
deformable attentions can also be applied in a single-scale feature map, we
verify the effectiveness of our proposed deformable attentions on both single-
scale and multi-scale baselines. As we described in our preliminary, the naïve
implementation of deformable attention on top of QPIC (for single-scale)
significantly degrades the score in both single-scale and multi-scale
environments (see (a vs. b) and (a vs. e)). The use of Dual-Entity attention
(DE) consistently improves the score in both single-scale (+1.53p in (b vs.
c)) and multi-scale environments (+0.78p in (e vs. f)). As well, Entity-
conditioned Context attention (EC) contributes in the multi-scale environment
when jointly used with DE (+0.64p in SS and +1.84p in MS). Therefore, we
conclude that disentangling the references (DE) and conditionally reimbursing
context information (EC) each gradually contributes to the final performance
of HOI detection in both single-scale and multi-scale environments, enabling
MSTR to effectively explore multi-scale feature maps to achieve state-of-the-
art performance.

#### Single-scale vs. Multi-scale.

In Table 1 and Table 2, we demonstrate that our method using the multi-scale
feature maps outperform all previous methods, including transformer-based
methods [14, 4, 26, 39] and the ones that already use multi-scale feature maps
heavily [13, 6, 12, 36, 18, 23]. To analyze further, Table 3 compares single-
scale version and the multi-scale version of our baselines (see (b-e) and
(e-h)). In all cases of converting the single-scale feature map to the multi-
scale one, we observe consistent performance gains (see (b vs. e), (c vs. f),
and (d vs. g,h)). The gain is maximized when DE and EC are used together. We
further provide a detailed analysis of the effectiveness of MSTR in multi-
scale environments in our Appendix.

#### Decoder Architecture.

We verify the effectiveness of Figure 4 (b) architecture in Table 3 (g vs. h).
As MSTR considers multiple semantics with two suggested deformable modules, it
is important to find suitable decoder architecture which can effectively merge
the semantics [5]. According to the possible combination ways when merging
three kinds of semantics, various types of decoder architecture can be
candidates for the decoder architectures (described in Appendix). In our
Appendix, we empirically verify that Figure 4 (b) architecture shows the most
powerful and robust performance across all datasets.

Figure 5:  Visualization of our Entity-conditioned Context attentions on
different levels of feature map (1 being the highest and 4 being the lowest
resolution). Best viewed in color and scale.  Figure 6: Visualization of the
HOI-aware attention of MSTR on different scales of humans and objects.

###  4.4 Qualitative Results

We conduct qualitative analysis of MSTR to observe how MSTR captures
interactions. Figure 1 and Figure 5 show the visualization of the attention
map in MSTR in various feature levels. Interestingly, we can observe that in
the higher resolution feature maps, the sampling points capture the detail of
the interacting human and object while the lower resolution feature maps tend
to capture the overall pose or context of the interaction. In Figure 1 and
Figure 6, we can observe how MSTR attends to test images that include various
scales of humans, target objects, and distances. More details along with
quantitative results will be provided in our Appendix.

##  5 Related Work

#### Transformer Based HOI Detectors.

Human-Object Interaction detection has been initially proposed in [9], and has
been developed in two main streams: sequential methods [8, 7, 10, 25, 27, 30,
23, 31, 24, 34, 19, 6, 1, 35, 22, 17, 20, 29, 37] and parallel methods [32,
21, 13]. However, since these works required hand-crafted post-processing, HOI
detectors with transformers have been proposed to eliminate the post-
processing step through an end-to-end fashioned set prediction approach [14,
26, 4, 39]. Yet, all these methods are limited to a single-scale feature map
due to the complexity caused when processing multi-scale feature maps with
transformer attention.

#### Deformable Transformers for Object Detection.

DETR has been recently proposed to eliminate the need for many hand-designed
components in object detection [2]. Deformable DETR [38] mitigates the slow
convergence and high complexity issues of DETR and successfully exploits
multi-resolution feature maps. The deformable attention modules in [38] attend
to a small set of sampling locations as a pre-filter for prominent key
elements out of all the feature map pixels. However, unlike object detection,
we observed that this pre-filter seriously deteriorates performance when
applied to HOI detection. Therefore, in this paper, we focus on finding a
proper way to incorporate deformable attention into HOI detection for
exploiting multi-scale feature maps.

##  6 Conclusion

In this paper, we present MSTR, the first multi-scale approach in transformer-
based HOI detectors. MSTR overcomes the issues of extending transfomer-based
HOI detectors to multi-scale feature maps with novel HOI-Aware Deformable
attentions named as Dual-Entity attention and Entity-conditioned Context
attention. In virtue of the two attention modules and our decoder architecture
that effectively collects the multiple semantics from each of the attentions,
MSTR achieves the state-of-the-art performance in two benchmark datasets in
HOI detection.

## References

  * [1] Ankan Bansal, Sai Saketh Rambhatla, Abhinav Shrivastava, and Rama Chellappa.  Detecting human-object interactions via functional generalization.  In AAAI, pages 10460–10469, 2020.
  * [2] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers.  arXiv preprint arXiv:2005.12872, 2020.
  * [3] Yu-Wei Chao, Yunfan Liu, Xieyang Liu, Huayi Zeng, and Jia Deng.  Learning to detect human-object interactions.  In 2018 ieee winter conference on applications of computer vision (wacv), pages 381–389. IEEE, 2018.
  * [4] Mingfei Chen, Yue Liao, Si Liu, Zhiyuan Chen, Fei Wang, and Chen Qian.  Reformulating hoi detection as adaptive set prediction.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9004–9013, 2021.
  * [5] Qi Dong, Zhuowen Tu, Haofu Liao, Yuting Zhang, Vijay Mahadevan, and Stefano Soatto.  Visual relationship detection using part-and-sum transformers with composite queries.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 3550–3559, 2021.
  * [6] Chen Gao, Jiarui Xu, Yuliang Zou, and Jia-Bin Huang.  Drg: Dual relation graph for human-object interaction detection.  In European Conference on Computer Vision, pages 696–712. Springer, 2020.
  * [7] Chen Gao, Yuliang Zou, and Jia-Bin Huang.  ican: Instance-centric attention network for human-object interaction detection.  arXiv preprint arXiv:1808.10437, 2018.
  * [8] Georgia Gkioxari, Ross Girshick, Piotr Dollár, and Kaiming He.  Detecting and recognizing human-object interactions.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 8359–8367, 2018.
  * [9] Jitendra Gupta, Saurabh Malik.  Visual semantic role labeling.  arXiv preprint arXiv:1505.04474, 2015.
  * [10] Tanmay Gupta, Alexander Schwing, and Derek Hoiem.  No-frills human-object interaction detection: Factorization, layout encodings, and training techniques.  In Proceedings of the IEEE International Conference on Computer Vision, pages 9677–9685, 2019.
  * [11] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [12] Zhi Hou, Xiaojiang Peng, Yu Qiao, and Dacheng Tao.  Visual compositional learning for human-object interaction detection.  arXiv preprint arXiv:2007.12407, 2020.
  * [13] Bumsoo Kim, Taeho Choi, Jaewoo Kang, and Hyunwoo Kim.  Uniondet: Union-level detection towards real-time human-object interaction detection.  In Proceedings of the European conference on computer vision (ECCV), 2020.
  * [14] Bumsoo Kim, Junhyun Lee, Jaewoo Kang, Eun-Sol Kim, and Hyunwoo J Kim.  Hotr: End-to-end human-object interaction detection with transformers.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 74–83, 2021.
  * [15] Dong-Jin Kim, Xiao Sun, Jinsoo Choi, Stephen Lin, and In So Kweon.  Detecting human-object interactions with action co-occurrence priors.  arXiv preprint arXiv:2007.08728, 2020.
  * [16] Alexander Kolesnikov, Alina Kuznetsova, Christoph Lampert, and Vittorio Ferrari.  Detecting visual relationships using box attention.  In Proceedings of the IEEE International Conference on Computer Vision Workshops, pages 0–0, 2019.
  * [17] Yong-Lu Li, Xinpeng Liu, Han Lu, Shiyi Wang, Junqi Liu, Jiefeng Li, and Cewu Lu.  Detailed 2d-3d joint representation for human-object interaction.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10166–10175, 2020.
  * [18] Yong-Lu Li, Xinpeng Liu, Xiaoqian Wu, Yizhuo Li, and Cewu Lu.  Hoi analysis: Integrating and decomposing human-object interaction.  Advances in Neural Information Processing Systems, 33, 2020.
  * [19] Yong-Lu Li, Liang Xu, Xinpeng Liu, Xijie Huang, Yue Xu, Shiyi Wang, Hao-Shu Fang, Ze Ma, Mingyang Chen, and Cewu Lu.  Pastanet: Toward human activity knowledge engine.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 382–391, 2020.
  * [20] Yong-Lu Li, Siyuan Zhou, Xijie Huang, Liang Xu, Ze Ma, Hao-Shu Fang, Yanfeng Wang, and Cewu Lu.  Transferable interactiveness knowledge for human-object interaction detection.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3585–3594, 2019.
  * [21] Yue Liao, Si Liu, Fei Wang, Yanjie Chen, Chen Qian, and Jiashi Feng.  Ppdm: Parallel point detection and matching for real-time human-object interaction detection.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 482–490, 2020.
  * [22] Y Liu, Q Chen, and A Zisserman.  Amplifying key cues for human-object-interaction detection.  Lecture Notes in Computer Science, 2020.
  * [23] Ye Liu, Junsong Yuan, and Chang Wen Chen.  Consnet: Learning consistency graph for zero-shot human-object interaction detection.  In Proceedings of the 28th ACM International Conference on Multimedia, pages 4235–4243, 2020.
  * [24] Julia Peyre, Ivan Laptev, Cordelia Schmid, and Josef Sivic.  Detecting unseen visual relations using analogies.  In Proceedings of the IEEE International Conference on Computer Vision, pages 1981–1990, 2019.
  * [25] Siyuan Qi, Wenguan Wang, Baoxiong Jia, Jianbing Shen, and Song-Chun Zhu.  Learning human-object interactions by graph parsing neural networks.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 401–417, 2018.
  * [26] Masato Tamura, Hiroki Ohashi, and Tomoaki Yoshinaga.  Qpic: Query-based pairwise human-object interaction detection with image-wide contextual information.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10410–10419, 2021.
  * [27] Oytun Ulutan, ASM Iftekhar, and Bangalore S Manjunath.  Vsgnet: Spatial attention network for detecting human object interactions using graph convolutions.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13617–13626, 2020.
  * [28] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In Advances in neural information processing systems, pages 5998–6008, 2017.
  * [29] Bo Wan, Desen Zhou, Yongfei Liu, Rongjie Li, and Xuming He.  Pose-aware multi-level feature network for human object interaction detection.  In Proceedings of the IEEE International Conference on Computer Vision, pages 9469–9478, 2019.
  * [30] Hai Wang, Wei-shi Zheng, and Ling Yingbiao.  Contextual heterogeneous graph network for human-object interaction detection.  arXiv preprint arXiv:2010.10001, 2020.
  * [31] Tiancai Wang, Rao Muhammad Anwer, Muhammad Haris Khan, Fahad Shahbaz Khan, Yanwei Pang, Ling Shao, and Jorma Laaksonen.  Deep contextual attention for human-object interaction detection.  arXiv preprint arXiv:1910.07721, 2019.
  * [32] Tiancai Wang, Tong Yang, Martin Danelljan, Fahad Shahbaz Khan, Xiangyu Zhang, and Jian Sun.  Learning human-object interaction detection using interaction points.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4116–4125, 2020.
  * [33] Tao Wang, Li Yuan, Yunpeng Chen, Jiashi Feng, and Shuicheng Yan.  Pnp-detr: Towards efficient visual analysis with transformers.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4661–4670, 2021.
  * [34] Bingjie Xu, Yongkang Wong, Junnan Li, Qi Zhao, and Mohan S Kankanhalli.  Learning to detect human-object interactions with knowledge.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019.
  * [35] Xubin Zhong, Changxing Ding, Xian Qu, and Dacheng Tao.  Polysemy deciphering network for human-object interaction detection.  In Proc. Eur. Conf. Comput. Vis, 2020.
  * [36] Xubin Zhong, Xian Qu, Changxing Ding, and Dacheng Tao.  Glance and gaze: Inferring action-aware points for one-stage human-object interaction detection.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13234–13243, 2021.
  * [37] Penghao Zhou and Mingmin Chi.  Relation parsing neural network for human-object interaction detection.  In Proceedings of the IEEE International Conference on Computer Vision, pages 843–851, 2019.
  * [38] Xizhou Zhu, Weijie Su, Lewei Lu, Bin Li, Xiaogang Wang, and Jifeng Dai.  Deformable detr: Deformable transformers for end-to-end object detection.  arXiv preprint arXiv:2010.04159, 2020.
  * [39] Cheng Zou, Bohan Wang, Yue Hu, Junqi Liu, Qian Wu, Yu Zhao, Boxun Li, Chenguang Zhang, Chi Zhang, Yichen Wei, et al.  End-to-end human object interaction detection with hoi transformer.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11825–11834, 2021.

##  Appendix A Appendix

In this Appendix, we provide i) extended quantitative analysis of MSTR
capturing HOI detection in a multi-scale environment, ii) exploration for
various possible decoder architectures, iii) implementation details of MSTR,
iv) details on experimental datasets and metrics, v) details of training, vi)
analysis on convergence speed, vii) additional qualitative result on our Dual-
Entity attention and Entity-conditioned Context attention, and finally, viii)
limitations of our work.

###  A.1 Additional Quantitative Results for MSTR

First, we perform an extended quantitative analysis on the HICO-DET test set
to validate the effectiveness of MSTR in a multi-scale environment. MSTR uses
multi-scale feature maps to explore the semantics of HOI existing in different
scales. In this section, we provide extensive quantitative results that shows
the effectiveness of MSTR in capturing the interactions between humans and
objects not only at different scales, but in various distances also (_e.g_.,
adjacent interaction such as ‘holding a book’ or remote interaction such as
‘throwing a frisbee’). To this end, we show quantitative results for multi-
scale interactions according to 1) relative area of the human and the object,
2) the size of humans/objects, 3) distance between the human and object. For
each criterion, we measure the performance across three bins where each bin
has an equal and sufficient amount of HOI ground-truth labels to cover
($\sim$11,000 HOIs). For comparison, we set QPIC [26], the state-of-the-art
transformer-based approach that uses a single-scale feature map, as our
baseline. Note that in this appendix, the size, area, and distance are all
calculated in normalized image coordinates.

#### Relative area of human vs. object.

To observe how MSTR handles interaction between humans and objects with
different scales, we first calculate the average precision (AP) over
interaction labels that have different relative areas of humans and objects
($\frac{\text{area(hbox)}}{\text{area(obox)}}$). We cover three main cases
according to their relative areas: i) $\text{AP}_{h<o}$ where the object area
is significantly larger than the human area (_e.g_., human sitting on a
bench), ii) $\text{AP}_{h=o}$ where the human and the object exists in
comparable sizes, and iii) $\text{AP}_{h>o}$ where the object area is
significantly smaller than the human area (_e.g_., human throwing a ball). We
set the threshold for the relative areas so that each bin has an equal number
of ground-truth instances (_i.e_.,
$\frac{\text{area(hbox)}}{\text{area(obox)}}<0.48$ for $\text{AP}_{h<o}$ and
$\frac{\text{area(hbox)}}{\text{area(obox)}}>4.33$ for $\text{AP}_{h>o}$). In
Table 4, MSTR outperforms QPIC in all three types of interaction categories.
Note that the improvement is more substantial in cases where the human and
object have vastly different scales (+3.01p for $\text{AP}_{h<o}$ and +1.85p
for $\text{AP}_{h>o}$), verifying that MSTR is effectively utilizing multi-
scale feature maps.

Method | $\text{AP}_{h<o}$ | $\text{AP}_{h=o}$ | $\text{AP}_{h>o}$
---|---|---|---
QPIC | 34.10 | 30.57 | 25.22
MSTR | 37.11 | 31.68 | 27.07
$\Delta$AP | +3.01 | +1.11 | +1.85
Table 4:  Comparison of MSTR with QPIC under interactions with different
human/object scale ratio.

#### Human & object size.

Here, we compare the average precision over the sizes of humans and objects.
$\text{AP}_{\text{L}}$, $\text{AP}_{\text{M}}$, $\text{AP}_{\text{S}}$ each
denotes the average precision for Large, Middle, and Small humans and objects.
In Table 5, MSTR outperforms QPIC in all three categories in both human and
object scales. For the human scales, the improvement is more recognizable in
interactions including small human areas (+3.06p in $\text{AP}_{\text{S}}$)
while for object scales, the improvement is consistent over all three scales.

| Human Size | Object Size
---|---|---
Method | $\text{AP}_{\text{L}}$ | $\text{AP}_{\text{M}}$ | $\text{AP}_{\text{S}}$ | $\text{AP}_{\text{L}}$ | $\text{AP}_{\text{M}}$ | $\text{AP}_{\text{S}}$
QPIC | 28.65 | 35.36 | 24.14 | 33.09 | 28.65 | 24.87
MSTR | 30.04 | 37.02 | 27.20 | 34.87 | 30.48 | 26.60
$\Delta$AP | +1.39 | +1.66 | +3.06 | +1.78 | +1.83 | +1.73
Table 5:  Comparison of MSTR with QPIC under different sizes of humans and
objects.

#### Interactions in various distances.

Not only does MSTR capture interactions with various sized participants, but
MSTR also captures interactions with various sized contexts, _i.e_.,
interaction in various distances. To correctly measure how remote an
interaction is, we note that the distance between center points [26] should be
normalized by both the image size and the size of the human and object box
participating in the interaction. Given the interaction between hbox
($hx_{1},hy_{1},hx_{2},hy_{2}$) and obox ($ox_{1},oy_{1},ox_{2},oy_{2}$), the
normalized box area as area (hbox) and area (obox), we define the distance
$d_{\text{interaction}}$ as

$\displaystyle\begin{split}&d_{\footnotesize\mbox{center}}=\scriptstyle\sqrt{\left(\frac{hx_{1}+hx_{2}}{2}-\frac{ox_{1}+ox_{2}}{2}\right)^{2}+\left(\frac{hy_{1}+hy_{2}}{2}-\frac{oy_{1}+oy_{2}}{2}\right)^{2}},\\\
&d_{\footnotesize\mbox{interaction}}=d_{\footnotesize\mbox{center}}/(\footnotesize\mbox{area(hbox)}\cdot\mbox{area(obox)}).\end{split}$
(11)

Then, we measure the average precision over three categories: i)
$\text{AP}_{\text{adjacent}}$ where the human is interacting with a nearby
object, ii) $\text{AP}_{\text{distant}}$ where the interacting human/object is
within moderate distance, and $\text{AP}_{\text{remote}}$ where the human is
interacting with an object sufficiently far away. As in previous sections, we
set the distance threshold so that each bin has an equal number of ground-
truth instances. Table 6 shows the improvement of MSTR over QPIC. Note that
while MSTR shows improvement across all three categories, the improvement is
more distinguishable in cases where humans are interacting with objects in
considerable distance (+2.23p for $\text{AP}_{\text{distant}}$ and +1.89p for
$\text{AP}_{\text{remote}}$, respectively).

Method | $\text{AP}_{\text{adjacent}}$ | $\text{AP}_{\text{distant}}$ | $\text{AP}_{\text{remote}}$
---|---|---|---
QPIC | 31.09 | 31.25 | 21.81
MSTR | 32.66 | 33.48 | 23.70
$\Delta$AP | +1.57 | +2.23 | +1.89
Table 6:  Comparison of MSTR with QPIC under interactions with various
distances.

###  A.2 Analysis on Decoder Architecture

As MSTR considers multiple semantics with two suggested deformable modules
(Dual-Entity attention and Entity-conditioned Context attention), it is
important to find a suitable decoder architecture that effectively merges the
semantics. Here, we explore the possible combinations and various types of
decoder architecture candidates when merging the three kinds of semantics. We
empirically verify that MSTR architecture shows the most powerful performance.

#### Architecture for Dual-Entity attention.

Figure 7:  Comparison of a simple 2-layer Decoder architecture for: (a) QPIC,
and (b) Direct application of Deformable DETR on QPIC, (c) Dual-Entity
attention with two streams of decoder layers and (d) Dual-Entity attention
that shares the self-attention layer.

In Figure 7, we explore different architectures for Dual-Entity attention. We
start with the most basic form: (a) is the architecture of QPIC, and (b) shows
a straightforward application of the deformable attention [38] to QPIC.
However, as we discussed in our main paper, (b) degrades the performance a lot
from (a), because unlike its counterpart in object detection, multiple
localizations need to be entangled to a single reference point in architecture
(b). Therefore, we first use Dual-Entity attention to disentangle sampling
points and attention weights for the participating entities (_i.e_., human and
object), respectively, to improve HOI detection performance. In Figure 7, (c)
and (d) shows two options of dealing with the dual semantics obtained from
dual reference points (each for humans and objects). In (c), each reference
point is dealt with a separate stack of decoder layers (_i.e_., Double-
stream), while in (d) they are handled within a single-stream by sharing the
self-attention layer where the input is simply the sum of the multiple
semantics from the previous decoder layer. In Table 9, we show that our Dual-
Entity attention shows a valid improvement (see (d) vs. (b)), while it even
shows better performance than (c) requiring twice the number of decoder
parameters.

Method | Default (Full)
---|---
(a) QPIC | 29.07
(b) QPIC + Deformable attention [38] | 27.52
(c) Double-stream | 28.15
(d) Dual-Entity attention | 28.30
Table 7:  Comparison of Dual-Entity attention performance (d) against
architecture in Figure 7 (a-c).

#### Modeling Conditional Context attention.

In HOI detection, contextual information often gives an important clue in
identifying interactions. In Table 8, we study the two different methods of
obtaining context attention using (a) standard deformable attention and (b)
our Entity-conditioned Context attention; note that in standard deformable
attention, context reference points are directly obtained from HOI queries
with a linear projection while our method conditionally obtain it from human
and object reference points (see Figure 8). It can be observed that despite
its simple structure and minimal delay, our Entity-conditioned Context
attention achieves an +0.78p improvement compared to its counterpart. This
implies that the guidance by human and object points is important to
effectively model contextual information.

Figure 8:  Comparison of: (a) context sampling with deformable attention, and (b) Entity-conditioned Context attention.  Method | Default (Full)
---|---
(a) Standard Deformable attention | 29.36
(b) Entity-conditioned Context attention | 30.14
Table 8:  Comparison of the performance of Entity-conditioned Context
attention against standard deformable attention [38]. Both (a) and (b)
leverage Dual-Entity attention and follow the architectural design of Figure 9
(a) for fair comparison.

#### Merging the semantics.

Figure 9 shows two different ways of how to merge the three semantics obtained
from our Dual-Entity attention and Entity-conditioned Context attention. In
MSTR, we merge the multiple semantics after applying self-attention separately
to each of the semantic features obtained in the previous layer (Figure 9 (b))
instead of forcedly composing the input features of the self-attention layer
(Figure 9 (a)). Table 9 shows that MSTR architecture (b) outperforms (a) by a
margin of +1.03p, achieving the final performance. Note that while (b) is
better, MSTR outperforms competing algorithms (presented in Table 2 of main
paper) even with architecture (a).

Method | Default (Full)
---|---
(a) Merge self-attention input | 30.14
(b) Merge self-attention output | 31.17
Table 9:  Comparison of a simple 2-layer Decoder architecture for Transformer-
based HOI detectors: (a) Merging the input of the self-attention, and (b)
architecture of MSTR (merging the output of self-attention).  Figure 9:
Comparison of a simple 2-layer Decoder architecture for Transformer-based HOI
detectors: (a) Merging the input of the self-attention, and (b) architecture
of MSTR (merging the output of self-attention).

###  A.3 Implementation Details

Following implementation details in Deformable DETR [38], we use ImageNet pre-
trained ResNet-50 [11] as our backbone CNN and extract multi-scale feature
maps without FPN. The number of attention heads and sampling offsets for
deformable attentions are set to $M=8$ and $K=4$, respectively. The AdamW
optimizer is used with the initial learning rate of 2e-4 and weight decay of
1e-4. All transformer weights are initialized with weights pre-trained in MS-
COCO. For a fair comparison with QPIC [26], we use only 100 HOI queries
instead of using 300 ones as in Deformable DETR [38].

###  A.4 Details on Datasets and Metrics

We evaluate our model on two widely-used public benchmarks: the V-COCO (Verbs
in COCO) [9] and HICO-DET [3] datasets. V-COCO is a subset of COCO composed of
5,400 trainval images and 4,946 test images. For V-COCO dataset, we report the
$\text{AP}_{\text{role}}$ over $25$ interactions in two scenarios. In Scenario
1 (denoted as $\text{AP}_{\text{role}}^{\\#1}$), detectors should predict an
output indicating the non-existence of an object ([0,0,0,0]) when the target
object is occluded, while in Scenario 2 (denoted as
$\text{AP}_{\text{role}}^{\\#2}$), only the localization of human and
interaction classification is scored for such cases. HICO-DET contains 37,536
and 9,515 images for each training and test splits with annotations for 600
$\langle verb,object\rangle$ interaction types. In HICO-DET dataset, there are
two different evaluation settings: Default and Known object. The former
measures AP on all the test images, while the latter only considers the images
with the object class corresponding to each AP. We report our score with both
settings. Note that the Default is a more challenging setting as we also need
to distinguish background images. We follow the previous settings and report
the mAP over three different category sets: (1) all 600 HOI categories in HICO
(Full), (2) 138 HOI categories with less than 10 training instances (Rare),
and (3) 462 HOI categories with 10 or more training instances (Non-Rare).

###  A.5 Training Details of MSTR

In this section, we explain the details of MSTR training. MSTR follows a set
prediction approach as in previous transformer-based HOI detectors [14, 4, 39,
26]. We first introduce the cost matrix of Hungarian Matching for unique
matching between the ground-truth HOI triplets and HOI set predictions.

#### Hungarian Matching for HOI Detection.

MSTR predicts a fixed number $K$ of HOI triplets that consist of a human box,
object box, and binary classification for the $a$ types of actions (where
$a$=25 in V-COCO and $117$ for HICO-DET). Each prediction captures a unique
$\langle$human,object$\rangle$ pair with multiple interactions. $K$ is set to
be larger than the typical number of interacting pairs in an image (in our
experiment, $K=100$). Let $\mathcal{Y}$ denote the set of ground truth HOI
triplets and $\hat{\mathcal{Y}}=\\{\hat{y_{i}}\\}_{i=1}^{K}$ as the set of $K$
predictions. As $K$ is larger than the number of unique interacting pairs in
the image, we consider $\mathcal{Y}$ also as a set of size $K$ padded with
$\varnothing$ (there are no ground-truth that matches the prediction). Let
$y=(b^{h},b^{o},c^{o},a)$ where the ground-truth interaction $y_{i}$ consists
of $b^{h}_{i}$ and $b^{o}_{i}$ which denotes the normalized coordinates for
the interacting human/object box, $c^{o}_{i}$ denotes the target object class.
and $a_{i}$ denotes the one-hot for multiple actions. To find a bipartite
matching between these two sets we search for a permutation of $K$ elements
$\sigma\in\mathfrak{S}_{K}$ with the lowest cost:

$\hat{\sigma}=\mathop{\mathrm{argmin}}_{\sigma\in\mathfrak{S}_{K}}\sum_{i}^{K}\mathcal{C}_{\text{match}}(y_{i},\hat{y}_{\sigma(i)}),$
(12)

where $\mathcal{C}_{\text{match}}$ is a pair-wise matching cost between ground
truth $y_{i}$ and a prediction with index $\sigma(i)$. Now, the ground-truth
is written as $y_{i}=(b_{i}^{h},b_{i}^{o},c_{i}^{o},a_{i})$ and the prediction
is written as
$\hat{y}_{\sigma(i)}=(\hat{b}_{\sigma(i)}^{h},\hat{b}_{\sigma(i)}^{o},\hat{c}_{\sigma(i)}^{o},\hat{a}_{\sigma(i)})$
where $\hat{y}_{\sigma(i)}$ is the prediction that has the minimal matching
cost with $y_{i}$. $\hat{b}_{\sigma(i)}^{h}$ and $\hat{b}_{\sigma(i)}^{o}$ are
the normalized box coordinates for humans and objects, respectively,
$\hat{c}^{o}_{\sigma(i)}$ is the classification for the target object of the
interaction, and $\hat{a}_{\sigma(i)}$ is the predicted actions.

#### Final Cost/Loss function for MSTR.

Based on $\mathcal{C}_{\text{match}}$, we calculate the final loss function
for all pairs matched. The cost/loss function for the HOI triplets consists of
the localization loss, object classification loss, and the action
classification loss as
$\mathcal{L}_{\text{H}}=\mathcal{L}_{\text{loc}}+\mathcal{L}_{\text{cls}}+\mathcal{L}_{\text{act}}$
where each function is written as

$\displaystyle\begin{split}&\mathcal{L}_{\text{loc}}=\sum_{i=1}^{K}\big{[}\mathcal{L}_{\text{loc}}(b^{h}_{i},\hat{b}^{h}_{\sigma(i)})+\mathcal{L}_{\text{loc}}(b^{o}_{i},\hat{b}^{o}_{\sigma(i)})\big{]},\\\
&\mathcal{L}_{\text{cls}}=\sum_{i=1}^{K}\text{BCELoss}(c_{i},\hat{c}_{\sigma(i)}),\\\
&\mathcal{L}_{\text{act}}=\sum_{i=1}^{K}\text{BCELoss}(a_{i},\hat{a}_{\sigma(i)}).\end{split}$
(13)

Identical to previous works [2, 38, 14, 4, 39, 26], the localization loss is
defined by the weighted sum of the L1-loss and the gIoU loss.

###  A.6 Convergence speed

One of the advantages that deformable attention provides is the fast
convergence at training. Figure 10 shows the convergence curve of MSTR
compared to QPIC. Specifically, MSTR requires a much short number of epochs
(50 epochs) compared to QPIC (150 epochs) to reach its best score. Note that
MSTR achieves a competitive score to QPIC only with 20 epochs, outperforming
QPIC with approximately $\times 4$ shorter training time.

Figure 10: Comparison of convergence curves of QPIC and MSTR in the HICO-DET
dataset. MSTR shows faster convergence than QPIC under various training
schedules for both methods.

###  A.7 Qualitative Analysis for MSTR

Figure 11: Visualization of the attention for the Dual-Entity attention and
Entity-conditioned Context attention of MSTR in multi-scale feature maps for
adjacent interaction: ride.  Figure 12: Visualization of the attention for the
Dual-Entity attention and Entity-conditioned Context attention of MSTR in
multi-scale feature maps for remote interaction: fly. It can be seen that in
both adjacent interaction and remote interaction, MSTR successfully captures
the multiple semantics of the human, object, and contextual information across
the multi-resolution feature maps.  Figure 13: MSTR attentions (Dual-Entity
attention and Entity-conditioned Context attention) of different scales all
visualized at once.

In this section, we conduct extensive qualitative analysis of MSTR to observe
how Dual-Entity attention and the Entity-conditioned Context attention capture
different semantics for interactions in a multi-scale environment.

#### MSTR attentions on multi-scale feature maps.

We conduct a qualitative analysis of MSTR on both Dual-Entity attention and
the Entity-conditioned Context attention in HOI detection to observe how MSTR
captures interactions. Figure 11 shows the visualization of each attention in
an adjacent interaction: ride. Figure 12 shows the visualization of each
attention in an remote interaction: fly. For both cases, we can see that the
Dual-Entity attention captures the appearance of the human and object across
multiple scales of feature maps. In contrast, the Entity-conditioned Context
attention tends to capture an inclusive area that covers both two regions and
their intermediate background, effectively capturing the context of the
interaction.

#### MSTR attentions on multi-scale feature maps.

In Figure 13, we provide more qualitative visualizations for the multi-scale
attentions of MSTR in various scenes with 1) large human and small object, 2)
small human and large object, 3) distant interactions, 4) adjacent
interactions.

###  A.8 Limitations

The main limitation of our work is the bottleneck caused by the extensive size
of the query element (multi-scale image features, there are about $\times 20$
more image tokens to process compared to the single-scale feature map).
Despite our proposed deformable attentions, MSTR suffers from an estimated
$10\%$ increase in parameters and $\sim\times 2$ GFLOPs compared to the
single-scale baseline, QPIC [26]. Although recent related works have tackled
the efficiency problem in deformable attentions by sampling the query element
as well [33], the research scope of this work did not cover this issue.


generalised effect algebras [DGS15].

Finally, it seems interesting to generalise Jónsson-Tarski duality to our
weighted setting and study in particular the role played by the weight algebra
$Q$ in this setting.

## References

  * [Bro06] R. Brown.  Topology and Groupoids.  www.groupoids.org, 2006.
  * [CDS20a] J. Cranch, S. Doherty, and G. Struth.  Convolution and concurrency.  CoRR, abs/2002.02321, 2020.
  * [CDS20b] J. Cranch, S. Doherty, and G. Struth.  Relational semigroups and object-free categories.  CoRR, abs/2001.11895, 2020.
  * [CGMS20] C. Calk, E. Goubault, P. Malbos, and G. Struth.  Algebraic coherent confluence and globular Kleene algebras.  CoRR, abs/2006.16129, 2020.
  * [Con95] A. Connes.  Noncommutative Geometry.  Academic Press, 1995.
  * [DGHS17] B. Dongol, V. B. F. Gomes, I. J. Hayes, and G. Struth.  Partial semigroups and convolution algebras.  Archive of Formal Proofs, 2017.
  * [DGS15] B. Dongol, V. B. F. Gomes, and G. Struth.  A program construction and verification tool for separation logic.  In MPC 2015, volume 9129 of LNCS, pages 137–158. Springer, 2015.
  * [DHS16] B. Dongol, I. J. Hayes, and G. Struth.  Convolution as a unifying concept: Applications in separation logic, interval calculi, and concurrency.  ACM Transactions of Computational Logic, 17(3):15:1–15:25, 2016\.
  * [DHS21] B. Dongol, I. J. Hayes, and G. Struth.  Convolution algebras: Relational convolution, generalised modalities and incidence algebras.  Logical Methods in Computer Science, 17(1), 2021.
  * [DJS09] J. Desharnais, P. Jipsen, and G. Struth.  Domain and antidomain semigroups.  In RelMiCS 2009, volume 5827 of LNCS, pages 73–87. Springer, 2009.
  * [DKV09] M. Droste, W. Kuich, and H. Vogler.  Handbook of Weighted Automata.  EATCS Monographs in Theoretical Computer Science. Springer, 2009.
  * [DMS06] J. Desharnais, B. Möller, and G. Struth.  Kleene algebra with domain.  ACM TOCL, 7(4):798–833, 2006.
  * [DS11] J. Desharnais and G. Struth.  Internal axioms for domain semirings.  Science of Computer Programming, 76(3):181–203, 2011.
  * [Elg76] C. C. Elgot.  Matricial theories.  Journal of Algebra, 42(2):391–421, 1976.
  * [FDC13] M. P. Fiore and M. Devesas Campos.  The algebra of directed acyclic graphs.  In Computation, Logic, Games, and Quantum Foundations. The Many Facets of Samson Abramsky - Essays Dedicated to Samson Abramsky on the Occasion of His 60th Birthday, volume 7860 of LNCS, pages 37–51. Springer, 2013.
  * [FJST20] U. Fahrenberg, C. Johansen, G. Struth, and R. B. Thapa.  Generating posets beyond N.  In RAMiCS 2020, volume 12062 of LNCS, pages 82–99. Springer, 2020.
  * [FJSZ20] U. Fahrenberg, C. Johansen, G. Struth, and K. Ziemiański.  Domain semirings united.  CoRR, abs/2011.04704, 2020.
  * [FR07] U. Fahrenberg and M. Raussen.  Reparametrizations of continuous paths.  J. Homotopy Related Struct., 2(2):93–117, 2007.
  * [Gau57] N. D. Gautam.  The validity of equations in complex algebras.  Archiv für mathematische Logik und Grundlagenforschung, 3:117–124, 1957.
  * [Gog67] J. A. Goguen.  L-fuzzy sets.  J. Mathematical Analysis and Applications, 18:145–174, 1967.
  * [Gol89] R. Goldblatt.  Varieties of complex algebras.  Annals of Pure and Applied Logic, 44:173–242, 1989.
  * [Gra81] J. Grabowski.  On partial languages.  Fundamenta Informaticae, 4(2):427, 1981.
  * [Gra09] M. Grandis.  Directed algebraic topology: models of non-reversible worlds.  New mathematical monographs. Cambridge Univ. Press, 2009.
  * [Hei25] W. Heisenberg.  Über quantentheoretische Umdeutung kinematischer und mechanischer Beziehungen.  Z. Physik, 33:879–893, 1925.
  * [HMSW11] T. Hoare, B. Möller, G. Struth, and I. Wehrman.  Concurrent Kleene algebra and its foundations.  J. Logic and Algebraic Programming, 80(6):266–296, 2011.
  * [Hot65] G. Hotz.  Eine Algebraisierung des Syntheseproblems von Schaltkreisen I.  J. Inf. Process. Cybern., 1(3):185–205, 1965.
  * [HOvdW06] B. Heidergott, G. J. Olsder, and J. van der Woude.  Max Plus at Work.  Princeton University Press, 2006.
  * [HP96] J. Hedlíková and S. Pulmannová.  Generalized difference posets and orthoalgebras.  Acta Mathematica Universitatis Comenianae, 65(2):247–279, 1996\.
  * [HS91] J. Y. Halpern and Y. Shoham.  A propositional modal logic of time intervals.  J. ACM, 38(4):935–962, 1991.
  * [JT51] B. Jónsson and A. Tarski.  Boolean algebras with operators. Part I.  American Journal of Mathematics, 73(4):891–939, 1951.
  * [JT52] B. Jónsson and A. Tarski.  Boolean algebras with operators. Part II.  American Journal of Mathematics, 74(1):127–162, 1952.
  * [Kah08] W. Kahl.  Relational semigroupoids: Abstract relation-algebraic interfaces for finite relations between infinite types.  J. Log. Algebraic Methods Program., 76(1):60–89, 2008.
  * [KM15] G. Kudryavtseva and V. Mazorchuk.  On multisemigroups.  Portugaliae Mathematica, 71(1):47–80, 2015.
  * [Lam58] J. Lambek.  The mathematics of sentence structure.  Americal Mathematical Monthly, 65:154–170, 1958.
  * [ML98] S. Mac Lane.  Categories for the Working Mathematician.  Springer, second edition, 1998.
  * [Mos12] B. C. Moszkowski.  A complete axiom system for propositional interval temporal logic with infinite time.  Logical Methods in Computer Science, 8(3), 2012.
  * [Ros90] K. L. Rosenthal.  Quantales and Their Applications.  Longman Scientific $\&$ Technical, 1990.
  * [Ros97] K. L. Rosenthal.  Relational monoids, multirelations, and quantalic recognizers.  Cahiers de Topologie et Géométrie Différentielle Catégoriques, 38(2):161–171, 1997.
  * [Rot64] G.-C. Rota.  On the foundations of combinatorial theory I: Theory of Möbius functions.  Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 2(4):340–368, 1964.
  * [RS71] C. P. Rourke and B. J. Sanderson.  $\Delta$-sets I: Homotopy Theory.  The Quarterly Journal of Mathematics, 22(3):321–338, 09 1971.
  * [Ser51] J.-P. Serre.  Homologie singulière des espaces fibrés.  PhD thesis, École Normale Supérieure, 1951.
  * [SS67] B. Schweizer and A. Sklar.  Function systems.  Mathemathische Annalen, 172:1–16, 1967.
  * [Win77] J. Winkowski.  Algebras of partial sequences - A tool to deal with concurrency.  In FOCS 1977, volume 56 of LNCS, pages 187–198. Springer, 1977.
  * [ZH04] C. Zhou and M. R. Hansen.  Duration Calculus: A Formal Approach to Real-Time Systems.  EATCS: Monographs in Theoretical Computer Science. Springer, 2004.

##  Appendix A Glossary of Algebraic Structures

### Multisemigroups and $\ell r$-Semigroups

  * •

A _multimagma_ $(X,\odot)$ is a set $X$ equipped with a multioperation
$\odot:X\times X\to\mathcal{P}X$.

  * •

A _multisemigroup_ is an associative multimagma: for all $x,y,z\in X$,

$\bigcup\\{x\odot v\mid v\in y\odot z\\}=\bigcup\\{v\odot z\mid v\in x\odot
y\\}.$

  * •

A _multimonoid_ $(X,\odot,E)$ is a multisemigroup with a set $E\subseteq X$ of
units such that, for all $x\in X$,

$\bigcup\\{e\odot x\mid e\in E\\}=\\{x\\}=\bigcup\\{x\odot e\mid e\in E\\}.$

  * •

A multimagma $X$ is a _partial magma_ if $|x\odot y|\leq 1$ and a _magma_ if
$|x\odot y|=1$ for all $x,y\in X$. These definitions extend to multisemigroups
and multimonoids.

  * •

A multimagma, multisemigroup or multimonoid $X$ is _local_ if $u\in x\odot
y\land y\odot z\neq\emptyset\Rightarrow u\odot z\neq\emptyset$.

  * •

An $\ell r$-_multimagma_ $(X,\odot,\ell,r)$ is a multimagma $(X,\odot)$
equipped with two operations $\ell,r:X\to X$ such that, for all $x,y\in X$,

$x\odot y\neq\emptyset\Rightarrow r(x)=\ell(y),\qquad\ell(x)\odot
x=\\{x\\},\qquad x\odot r(x)=\\{x\\}.$

The definition extends to $\ell r$-multisemigroups, partial and total
algebras.

  * •

An $\ell r$-semigroup is _local_ if

$\ell(x\odot\ell(y))=\ell(x\odot y)\qquad\text{ and }\qquad r(r(x)\odot
y)=r(x\odot y).$

### Function Systems and Modal Semigroups

  * •

A _function system_ [SS67] is a structure $(X,\cdot,L,R)$ such that
$(X,\cdot)$ is a semigroup and the following axioms hold (using Schweizer and
Sklar’s notation):

$\displaystyle L(R(x))$ $\displaystyle=R(x),$ $\displaystyle R(L(x)$
$\displaystyle=L(x),$ (2a) $\displaystyle L(x)\cdot x$ $\displaystyle=x,$
$\displaystyle x\cdot R(x)$ $\displaystyle=x,$ (2b) $\displaystyle L(x\cdot
L(y))$ $\displaystyle=L(x\cdot y),$ $\displaystyle R(R(x)\cdot y)$
$\displaystyle=R(x\cdot y),$ (3a) $\displaystyle L(x)\cdot R(y)$
$\displaystyle=R(y)\cdot L(x),$ (3b) $\displaystyle y\cdot R(x\cdot y)$
$\displaystyle=R(x)\cdot y.$ (3c)

In addition, Schweizer and Sklar consider the identity

$L(x\cdot y)\cdot x=x\cdot L(y),$ (D3c)

which is valid in some function systems, but not in all. They point out that
all axioms except (3c), which has subsequently been called _twisted axiom_ ,
hold of binary relations. Schweizer and Sklar’s axioms use function
composition $\circ$ instead of $\cdot$.

  * •

A _domain semigroup_ [DJS09] is a semigroup $(X,\cdot)$ with a binary
operation $\textit{dom}:X\to X$ that satisfies

$\displaystyle\textit{dom}(x)\cdot x$ $\displaystyle=x,$ (D1)
$\displaystyle\textit{dom}(x\cdot y)$
$\displaystyle=\textit{dom}(x\cdot\textit{dom}(y)),$ (D2)
$\displaystyle\textit{dom}(\textit{dom}(x)\cdot y)$
$\displaystyle=\textit{dom}(x)\cdot\textit{dom}(y),$ (D3)
$\displaystyle\textit{dom}(x)\cdot\textit{dom}(y)$
$\displaystyle=\textit{dom}(y)\cdot\textit{dom}(x).$ (D4)

  * •

A _modal semigroup_ is a domain semigroup $X$ equipped with a codomain
operation $\textit{cod}:X\to X$ that satisfies opposite laws, in which the
arguments of composition have been swapped, and the compatibility laws
$\textit{dom}\circ\textit{cod}=\textit{cod}$ and
$\textit{cod}\circ\textit{dom}=\textit{dom}$.

The axioms (D3) and (D4) as well as the dual codomain axioms are derivable in
function systems. Conversely, the function system axiom (3b) is derivable in
modal semigroups. Disregarding the twisted law, function systems are therefore
a more compact, but equivalent axiomatisation of domain semigroups.

### Dioids and Modal Semirings

  * •

A _dioid_ is an additively idempotent semiring $(S,+,\cdot,0,1)$, that is, a
semiring $S$ in which $x+x=x$ for all $x\in S$. As $(S,+,0)$ is a semilattice,
the relation $x\leq y\Leftrightarrow x+y=y$ is a partial order with least
element $0$ and in which $+$ and $\cdot$ preserve the order in both arguments.

  * •

A _modal semiring_ is a semiring $S$ equipped with operations
$\textit{dom},\textit{cod}:S\to S$ that satisfy

$\displaystyle x\leq\textit{dom}(x)\cdot
x,\qquad\textit{dom}(x\cdot\textit{dom}(y))=\textit{dom}(x\cdot
y),\qquad\textit{dom}(x)\leq 1,\qquad\textit{dom}(0)=0,$
$\displaystyle\textit{dom}(x+y)=\textit{dom}(x)+\textit{dom}(y),$

as well as opposite axioms for cod and in which dom and cod are compatible in
the sense that $\textit{dom}\circ\textit{cod}=\textit{cod}$ and
$\textit{cod}\circ\textit{dom}=\textit{dom}$. Adding these axioms to any
semiring and defining $x\leq y\Leftrightarrow x+y=y$ forces additive
idempotency. Every modal semiring is therefore a dioid.

### Quantales and Modal Quantales

  * •

A _prequantale_ is a structure $(Q,\leq,\cdot,1)$ such that $(Q,\leq)$ is a
complete lattice, $1$ a unit of composition and $\cdot$ preserves all sups in
both arguments.

  * •

A _quantale_ is a prequantale $Q$ in which composition is associative (hence
$(Q,\cdot,1)$ is a monoid).

  * •

A _modal prequantale_ is a prequantale $Q$ with operations
$\textit{dom},\textit{cod}:Q\to Q$ such that the modal semiring axioms hold
(replacing $0$ with $\bot$ and $+$ with $\vee$), yet the second axiom (the
locality axiom) for dom and its opposite for cod are replaced by the export
axiom

$\textit{dom}(\textit{dom}(x)\cdot y))=\textit{dom}(x)\cdot\textit{dom}(y)$

and its opposite for cod.

  * •

A _weakly local modal quantale_ is a modal prequantale that is also a
quantale.

  * •

A _modal quantale_ is a quantale $Q$ equipped with operations
$\textit{dom},\textit{cod}:Q\to Q$ that satisfy the modal semiring axioms
(with the obvious syntactic replacements).

##  Appendix B Multioperations and Ternary Relations

We briefly outline the relationship between multioperations and ternary
relations. A relational magma $(X,R)$ is a set $X$ with a ternary relation
$R$. We write $R^{x}_{yz}$ instead of $(x,y,z)\in R$ and $D_{yz}$ whenever
$R^{x}_{yz}$ holds for some $x$. We have previously set up the relationship
between object-free categories and such relational structures [CDS20b]. The
association with multioperations is obtained via

$x\in y\odot z\Leftrightarrow R^{x}_{yz}.$

Accordingly, the ternary relation $R$ is relationally associative if $\forall
u,x,y,z.\exists v.\ R^{u}_{xv}\land R^{v}_{yz}\Leftrightarrow\exists v.\
R^{v}_{xy}\land R^{u}_{vz}$. It is local if for all $u,x,y,z$, $R^{u}_{xy}$
and $D_{yz}$ imply $D_{uz}$. It is weakly functional if $|\\{x\mid
R^{x}_{yz}\\}|\leq 1$ and functional if $|\\{x\mid R^{x}_{yz}\\}|=1$, for all
$x,y$. These properties correspond to partiality and totality of
multirelations. Element $e\in X$ is a relational left unit if $R^{x}_{ex}$ for
some $x$ and $R^{x}_{ey}$ implies $x=y$ for all $x,y$; it is a relational
right unit if $R^{x}_{xe}$ for some $x$ and $R^{x}_{ye}$ implies $x=y$ for all
$x,y$. Definitions of relational magmas, unitality, relational semigroups and
relational monoids are then analogous to those for multimagmas. Similar
notions have been studied in [DHS21].

A relational magma morphism $f:(X,R)\to(Y,S)$ satisfies
$\smash[t]{R^{x}_{yz}\Rightarrow S^{f(x)}_{f(y)f(z)}}$ for all $x,y,z\in X$.
It is bounded if $\smash[t]{S^{f(x)}_{uv}}$ implies that there are $x,y\in X$
such that $R^{x}_{yz}$, $u=f(y)$ and $v=f(z)$, for all $x\in X$ and $u,v\in
Y$.

######  Lemma B.1.

Categories of relational magmas and those of multimagmas are isomorphic (both
for morphisms and for bounded ones).

###### Proof.

Relations of type $X\times Y\times Z$ are in bijective correspondence with
functions of type $Y\times Z\to\mathcal{P}X$ via the maps

$\mathcal{F}(R)=\lambda y,z.\ \\{x\mid R^{x}_{yz}\\}\qquad\text{ and
}\qquad\mathcal{R}(F)=\\{(x,y,z\mid x\in F(y,z)\\}.$

We extend $\mathcal{F}$ and $\mathcal{R}$ to functors between categories of
relational magmas and multimagmas by stipulating
$\mathcal{F}(f)=f=\mathcal{R}(f)$. Suppose $f$ is a relational magma morphism.
Then $\mathcal{F}(f)$ is a multimagma morphism because

$f\left(\mathcal{F}(R)(y,z)\right)=\left\\{f(x)\middle|R^{x}_{yz}\right\\}\subseteq\left\\{f(x)\middle|S^{f(x)}_{f(y)f(z)}\right\\}=\mathcal{F}(S)(f(y),f(z)).$

Suppose $f$ is a multimagma morphism. Then $\mathcal{R}(f)$ is a relational
magma morphism because

$(\mathcal{R}(\odot_{X}))^{x}_{yz}\Leftrightarrow x\in y\odot_{X}y\Rightarrow
f(x)\in
f(y)\odot_{Y}f(z)\Leftrightarrow(\mathcal{R}(\odot_{Y}))^{f(x)}_{f(y)f(z)}.$

Moreover, if the relational magma morphism $f$ is bounded, then so is
$\mathcal{F}(f)$, because

$\displaystyle f(x)\in\mathcal{F}(S)(u,v)$ $\displaystyle\Leftrightarrow
S^{f(x)}_{uv}$ $\displaystyle\Rightarrow R^{x}_{yz},\,u=f(y)\text{ and
}v=f(z)\text{ for some }y,z$ $\displaystyle\Leftrightarrow
x\in\mathcal{F}(R)(y,z),\,u=f(y)\text{ and }v=f(z)\text{ for some }y,z.$

Finally, if the multimagma morphism $f$ is bounded, then so is
$\mathcal{R}(f)$, because

$\displaystyle(\mathcal{R}(\odot_{Y}))^{f(x)}_{uv}$
$\displaystyle\Leftrightarrow f(x)\in u\odot_{Y}v$ $\displaystyle\Rightarrow
x\in y\odot_{X}z,\,u=f(y)\text{ and }v=f(z)\text{ for some }y,z$
$\displaystyle\Leftrightarrow(\mathcal{R}(\odot_{X}))^{x}_{yz}\land
u=f(y)\land v=f(z)\text{ for some }y,z.$

It is then easy to check that $\mathcal{F}$ and $\mathcal{R}$ are mutually
inverse functors. This shows that the categories of relational magmas with
(bounded) morphisms and those of multimagmas with (strong) morphisms are
isomorphic. ∎

The isomorphisms extend to relational and multisemigroups, relational monoids
and multimonoids, and their local, partial and total variants. They transfer
theorems between relational structures [CDS20b] and the corresponding
multialgebras.

##  Appendix C Proofs of Lemmas 6.2 and 6.3

###### Proof of Lemma 6.2.

We show proofs up-to opposition.

  1. 1.

$\ell(r(A))=\\{\ell(r(x))\mid x\in A\\}=\\{r(x)\mid x\in A\\}=r(A)$.

  2. 2.

$\displaystyle\ell(A)A$ $\displaystyle=\bigcup\\{\ell(x)y\mid x,y\in A\text{
and }D_{\ell(x)y}\\}$ $\displaystyle=\bigcup\\{\ell(x)y\mid x,y\in
A,\,D_{\ell(x)y}\text{ and }r(\ell(x))=\ell(y)\\}$
$\displaystyle=\bigcup\\{\ell(x)y\mid x,y\in A,\,D_{\ell(x)y}\text{ and
}\ell(x)=\ell(y)\\}$ $\displaystyle=\bigcup\\{\ell(y)y\mid y\in A\\}$
$\displaystyle=\bigcup\\{\\{y\\}\mid y\in A\\}$ $\displaystyle=A.$

  3. 3.

$\ell\left(\bigcup\mathcal{A}\right)=\\{\ell(x)\mid
x\in\bigcup\mathcal{A}\\}=\\{\ell(x)\mid x\in A\text{ for some
}A\in\mathcal{A}\\}=\bigcup\\{\ell(A)\mid A\in\mathcal{A}\\}$.

  4. 4.

Immediate from (3).

  5. 5.

We only prove the identity for $\ell(A)r(B)$; the remaining ones then follow
from (1).

$\displaystyle\ell(A)r(B)=\bigcup\\{\ell(x)r(y)\mid x\in A\text{ and }y\in
B\\}=\bigcup\\{r(y)\ell(x)\mid x\in A\text{ and }y\in B\\}=r(B)\ell(A).$

  6. 6.

$\ell(A)=\\{\ell(x)\mid x\in A\\}\subseteq\\{\ell(x)\mid x\in
X\\}=\\{x\mid\ell(x)=x\\}=E$.

  7. 7.

$\displaystyle\ell(\ell(A)B)$ $\displaystyle=\bigcup\\{\ell(\ell(x)y)\mid x\in
A,\,y\in B\text{ and }D_{\ell(x)y}\\}$
$\displaystyle=\bigcup\\{\ell(x)\ell(y)\mid x\in A,\,y\in
B,\,D_{\ell(x)y}\text{ and }r(\ell(x))=\ell(y)\\}$
$\displaystyle=\bigcup\\{\ell(x)\ell(y)\mid x\in A,\,y\in
B,\,D_{\ell(x)y}\text{ and }\ell(x)=\ell(y)\\}$
$\displaystyle=\bigcup\\{\ell(x)\ell(y)\mid x\in A,\,y\in B\text{ and
}D_{\ell(y)y}\\}$ $\displaystyle=\bigcup\\{\ell(x)\ell(y)\mid x\in A\text{ and
}y\in B\\}$ $\displaystyle=\ell(A)\ell(B).$

∎

###### Proof of Lemma 6.3.

Suppose $X$ is an $\ell r$-multisemigroup. For the first inclusion, it is
routine to derive (lla) from Lemma 6.2. The claim then follows from
Proposition 4.1 and the adjunction for domain. The second inclusion holds by
opposition.

Finally, suppose that $X$ is local. Then, writing $r(x)=\ell(y)$ in place of
$D_{xy}$ owing to locality,

$\displaystyle\ell(A\ell(B))$ $\displaystyle=\bigcup\\{\ell(x\ell(y))\mid x\in
A,\,y\in B\text{ and }r(x)=\ell(\ell(y))\\}$
$\displaystyle=\bigcup\\{\ell(xy)\mid x\in A,\,y\in B\text{ and
}r(x)=\ell(y)\\}$ $\displaystyle=\ell(AB)$

and the opposite result is obvious. ∎