# A Tale of Two Graphs: Freezing and Denoising Graph Structures for Multimodal
Recommendation

Xin Zhou  Alibaba-NTU Singapore Joint Research Institute
Nanyang Technological UniversitySingapore<EMAIL_ADDRESS>and  Zhiqi Shen
School of Computer Science and Engineering
Nanyang Technological UniversitySingapore<EMAIL_ADDRESS>
(2023)

###### Abstract.

Multimodal recommender systems utilizing multimodal features (_e.g._ , images
and textual descriptions) typically show better recommendation accuracy than
general recommendation models based solely on user-item interactions.
Generally, prior work fuses multimodal features into item ID embeddings to
enrich item representations, thus failing to capture the latent semantic item-
item structures. In this context, LATTICE proposes to learn the latent
structure between items explicitly and achieves state-of-the-art performance
for multimodal recommendations. However, we argue the latent graph structure
learning of LATTICE is both inefficient and unnecessary. Experimentally, we
demonstrate that freezing its item-item structure before training can also
achieve competitive performance. Based on this finding, we propose a simple
yet effective model, dubbed as FREEDOM, that FREEzes the item-item graph and
DenOises the user-item interaction graph simultaneously for Multimodal
recommendation. Theoretically, we examine the design of FREEDOM through a
graph spectral perspective and demonstrate that it possesses a tighter upper
bound on the graph spectrum. In denoising the user-item interaction graph, we
devise a degree-sensitive edge pruning method, which rejects possibly noisy
edges with a high probability when sampling the graph. We evaluate the
proposed model on three real-world datasets and show that FREEDOM can
significantly outperform current strongest baselines. Compared with LATTICE,
FREEDOM achieves an average improvement of 19.07% in recommendation accuracy
while reducing its memory cost up to 6$\times$ on large graphs. The source
code is available at: https://github.com/enoche/FREEDOM.

Multimodal Recommendation, Graph Freezing, Graph Denoising.

††journalyear: 2023††copyright: rightsretained††conference: Proceedings of the
31st ACM International Conference on Multimedia; October 29-November 3, 2023;
Ottawa, ON, Canada††booktitle: Proceedings of the 31st ACM International
Conference on Multimedia (MM ’23), October 29-November 3, 2023, Ottawa, ON,
Canada††doi: 10.1145/3581783.3611943††isbn: 979-8-4007-0108-5/23/10††ccs:
Information systems Recommender systems††ccs: Information systems Multimedia
and multimodal retrieval

##  1\. Introduction

The increasing availability of multimodal information (_e.g._ , images, texts
and videos) associated with items enables users to have a more in-depth and
comprehensive understanding of the items they are interested in. Consequently,
multimodal recommender systems (MRSs) leveraging multimodal information are a
recent trend in capturing the preferences of users for accurate item
recommendations in online platforms, such as e-commerce and instant video
platforms, etc. Studies (He and McAuley, 2016b; Zhang et al., 2021)
demonstrate that MRSs usually have better performance than general
recommendation models which only utilize the historical user-item
interactions.

The primary challenge in MRSs is how to effectively integrate the multimodal
information into the collaborative filtering (CF) framework. Conventional
studies either fuse the projected low-dimensional multimodal features with the
ID embeddings of items via concatenation, summation operations (He and
McAuley, 2016b; Liu et al., 2017) or leverage attention mechanisms to capture
users’ preferences on items (Chen et al., 2017; Liu et al., 2019; Chen et al.,
2019). The surge of research on graph-based recommendations (Wu et al., 2020;
Zhang et al., 2022; Zhou et al., 2023b, a) inspires a line of work (Wei et
al., 2020; Wang et al., 2021b; Zhang et al., 2021; Zhou et al., 2023e) that
exploits the power of graph neural networks (GNNs) to capture the high-order
semantics between multimodal features and user-item interactions.
Specifically, MMGCN (Wei et al., 2019) utilizes graph convolutional networks
(GCNs) to propagate and aggregate information on every modality of the item.
On top of MMGCN, GRCN (Wei et al., 2020) refines the user-item bipartite graph
by weighing the user-item edges according to the affinity between user
preference and item content. To achieve better recommendation performance,
researchers exploit auxiliary graph structures to explicitly capture the
relations between users or items. For instance, DualGNN (Wang et al., 2021b)
constructs the user-user relation graph to smoothen users’ preferences with
their neighbors via GNNs. Nonetheless, the authors of LATTICE (Zhang et al.,
2021) argue that the latent item-item structures underlying the multimodal
contents of items could lead to better representation learning. Hence, LATTICE
first dynamically constructs a latent item-item graph by considering raw and
projected multimodal features learned from multi-layer perceptrons (MLPs). It
then performs graph convolutions on the constructed latent item-item graph to
explicitly incorporate item relationships into representation learning. As a
result, LATTICE could exploit both the high-order interaction semantic from
the user-item graph and the latent item content semantic from the item-item
structure. Although this paradigm turns out to be effective, it poses a
prohibitive cost by requiring computation and memory quadratic in the number
of items.

In this paper, we first experimentally disclose that the item-item structure
learning of LATTICE is dispensable. Specifically, we build an item-item graph
directly from the raw multimodal contents of items and freeze it in training
LATTICE. Under the same evaluation settings and datasets of LATTICE, our
empirical experiments in Table 1 show that LATTICE with frozen item-item graph
structures (_i.e._ , LATTICE-Frozen) gains slightly better performance on two
out of three datasets. To further refine the structures in both user-item
bipartite graph and the item-item graph, we propose a graph structures
FREEzing and DenOising Multimodal model for recommendation, dubbed as FREEDOM.
To be specific, the item-item graph constructed by LATTICE retains the
affinities between items as the edge weights, which may be noisy as the
multimodal features are extracted from general pre-trained models (_e.g._ ,
Convolutional Neural Networks or Transformers). FREEDOM discretizes the
weighted item-item graph into an unweighted one to enable information
propagation in GCNs only depending on graph structure. For the user-item
graph, we further introduce a degree-sensitive edge pruning technique to
denoise its structure to remove the noise caused by unintentional interactions
or bribes (Zhou et al., 2022). Inspired by (Chen et al., 2020), we sample
edges following a multinomial distribution with pre-calculated parameters to
construct a sparsified subgraph. Finally, FREEDOM learns the representations
of users and items by integrating the unweighted item-item graph and the
sparsified user-item subgraph. We analyze FREEDOM via a spectral perspective
to demonstrate that FREEDOM is capable of achieving a tighter low-pass filter.
We conduct comprehensive experiments on three real-world datasets to show that
our proposed model can significantly outperform the state-of-the-art methods
in terms of recommendation accuracy.

Table 1. LATTICE with frozen item-item graph structures (_i.e._ , LATTICE-Frozen) shows slightly better performance than its original version on Baby and Sports in terms of Recall and NDCG (Refer Section 5 for detailed experiment settings). Dataset | Metric | LATTICE | LATTICE-Frozen
---|---|---|---
Baby | R@10 | 0.0547 | 0.0551
R@20 | 0.0850 | 0.0873
N@10 | 0.0292 | 0.0291
N@20 | 0.0370 | 0.0373
Sports | R@10 | 0.0620 | 0.0626
R@20 | 0.0953 | 0.0964
N@10 | 0.0335 | 0.0336
N@20 | 0.0421 | 0.0423
Clothing | R@10 | 0.0492 | 0.0434
R@20 | 0.0733 | 0.0635
N@10 | 0.0268 | 0.0227
N@20 | 0.0330 | 0.0279

##  2\. Related Work

###  2.1. Multimodal Recommendation

Multimodal recommendation models utilize deep or graph learning techniques to
effectively incorporate the multimodal information of items into the classic
CF paradigm for better recommendation performance. Previous work (He and
McAuley, 2016b; Liu et al., 2017) extends the BPR method (Rendle et al., 2009)
by fusing the visual and/or style content of items with their ID embeddings
and obtains a considerable performance boost. To further differentiate users’
preferences on multimodal information, attention mechanisms are exploited in
multimodal recommendation models. For instance, VECF (Chen et al., 2019)
utilizes the VGG model (Simonyan and Zisserman, 2014) to perform pre-
segmentation on images and captures the user’s attention on different image
regions. MAML (Liu et al., 2019) uses a two-layer neural network to capture
the user’s preference for textual and visual features of an item. Under the
surge of GNNs applied in recommendation systems (Wu et al., 2020), researchers
are inspired to inject high-order semantics into user/item representation
learning via GNNs. MMGCN (Wei et al., 2019) adopts the message passing
mechanism of GCNs and constructs a modality-specific user-item bipartite
graph, which can capture the information from multi-hop neighbors to enhance
the user and item representations. Following MMGCN, GRCN (Wei et al., 2020)
introduces a graph refine layer to refine the structure of the user-item
interaction graph by identifying the noise edges and corrupting the false-
positive edges. In DualGNN (Wang et al., 2021b), the authors argue that users’
preferences may dynamically evolve with time. They introduce a user co-
occurrence graph with a preference learning module to capture the user’s
preference for features from different modalities of an item. However, the
aforementioned models mine the semantic information between items in an
implicit manner and may lead to inferior performance. To this end, LATTICE
(Zhang et al., 2021) explicitly constructs item-item relation graphs for each
modality and fuses them together to obtain a latent item-item graph. It then
dynamically updates the item-item graph with projected multimodal features
from MLPs and achieves state-of-the-art recommendation accuracy. Recently, we
also see an emerging of applying self-supervised learning in multimodal
recommendations (Tao et al., 2022; Zhou et al., 2023c). For an in-depth
exploration of multimodal recommender systems, we recommend consulting the
comprehensive survey conducted by (Zhou et al., 2023d).

###  2.2. Denoising Graph Structures

Studies on denoising graph structures can be roughly categorized as either
permanent or temporary edge pruning. Edges are either pruned or retained based
on calculated scores. The former work (Wang et al., 2021a, b; Luo et al.,
2021; Xu et al., 2022) leverages attention mechanisms or pre-defined functions
to calculate a node’s attention or affinity scores with its neighbors. Based
on the scores, they either permanently prune the edges satisfying a pre-
defined condition or decrease the weights on the edges. The latter work
(Hamilton et al., 2017; Rong et al., 2020) iteratively prunes the edges of the
graph to extract a smaller subgraph for graph learning (Luo et al., 2021). It
is worth mentioning that DropEdge (Rong et al., 2020) is an intuitive and
widely-used method that prunes edges following a uniform distribution. Other
studies (Franceschi et al., 2019; Kazi et al., 2022) place a parameterized
distribution or function on edges of the graph and learn the parameters in a
supervised manner. A sparsified graph is sampled from the original graph
following the learned distributions or functions. For computational complexity
consideration, in this paper, we precalculate and fix the parameter of
distribution for subgraph sampling.

Figure 1. Comparison of our proposed a) FREEDOM and b) LATTICE (Zhang et al.,
2021). FREEDOM freezes the item-item graph and denoises the user-item graph
simultaneously for multimodal recommendation.

##  3\. Freezing and Denoising Graph Structures

In this section, we elaborate on each component of FREEDOM from graph
construction to item recommendation. Fig. 1 shows the overall architecture
compared with LATTICE.

###  3.1. Constructing Frozen Item-Item Graph

Following (Zhang et al., 2021), FREEDOM also uses $k$NN to construct an
initial modality-aware item-item graph $\bm{S}^{m}$ using raw features from
each modality $m$. Considering $N$ items, we calculate the similarity score
$\bm{S}^{m}_{ij}$ between item pair $i$ and $j$ with a cosine similarity
function on their raw features ($\bm{x}_{i}^{m}$ and $\bm{x}_{j}^{m}$) of
modality $m$. That is:

(1)
$\bm{S}_{ij}^{m}=\frac{{(\bm{x}_{i}^{m})}^{\top}\bm{x}_{j}^{m}}{\|\bm{x}_{i}^{m}\|\|\bm{x}_{j}^{m}\|},$

where $\bm{S}^{m}_{ij}$ is the $i$-th row, $j$-th column element of matrix
$\bm{S}^{m}\in\mathbb{R}^{N\times N}$. We further employ $k$NN sparsification
(Chen et al., 2009) and convert the weighted $\bm{S}^{m}$ into an unweighted
matrix. That is, for each item $i$, we only retain the connection relations of
its top-$k$ similar edges:

(2)
$\widehat{\bm{S}}^{m}_{ij}=\begin{cases}1,\enspace&{\bm{S}}^{m}_{ij}\in\operatorname{top-}k({\bm{S}}^{m}_{i}),\\\
0,\enspace&\text{otherwise}.\end{cases}$

Each element in $\widehat{\bm{S}}^{m}$ is either 0 or 1, with 1 denoting a
latent connection between the two items. We empirically fixed the value of $k$
at 10. Note that $\widehat{\bm{S}}^{m}$ is different from the weighted
similarity matrix of LATTICE, which uses the affinity values between items as
its elements. We normalize the discretized adjacency matrix
$\widehat{\bm{S}}^{m}$ as
$\widetilde{\bm{S}}^{m}=({\bm{D}^{m}})^{-\frac{1}{2}}\widehat{\bm{S}}^{m}({\bm{D}^{m}})^{-\frac{1}{2}}$,
where $\bm{D}^{m}\in\mathbb{R}^{N\times N}$ is the diagonal degree matrix of
$\widehat{\bm{S}}^{m}$ and
$\bm{D}_{ii}^{m}=\sum_{j}\widehat{\bm{S}}^{m}_{ij}$. With the resulted
modality-aware adjacency matrices, we construct the latent item-item graph by
aggregating the structures from each modality:

(3) ${\bm{S}}=\sum_{m\in\mathcal{M}}\alpha_{m}\widetilde{\bm{S}}^{m},$

where $\bm{S}\in\mathbb{R}^{N\times N}$, $\alpha_{m}$ is the importance score
of modality $m$ and $\mathcal{M}$ is the set of modalities. Same as other
studies (Liu et al., 2019; Zhang et al., 2021), we consider visual and textual
modalities denoted by $\mathcal{M}=\\{v,t\\}$ in this paper. The importance
score can be learned via parametric functions. Here, we reduce the model
parameters by introducing a hyperparameter $\alpha_{v}$ denoting the
importance of visual modality in constructing $\bm{S}$. We let
$\alpha_{t}=1-\alpha_{v}$.

Finally, we freeze the latent item-item graph, which can greatly improve the
efficiency of FREEDOM. To be specific, the construction of the similarity
matrix under modality $m$ in Eq. (1) requires computational complexity of
$\mathcal{O}(N^{2}d_{m})$, where $d_{m}$ is the dimension of raw features. As
shown in Fig. 1, FREEDOM pre-calculates (dotted lines) the item-item graph
before training and freezes it during model training. As a result, it removes
the computational burden of $\mathcal{O}(N^{2}d_{m})$ for graph construction
in training.

###  3.2. Denoising User-Item Bipartite Graph

In this section, we introduce a degree-sensitive edge pruning to denoise the
user-item bipartite graph. The idea is derived from recent researches on model
sparsification (Rong et al., 2020) and simplification (Chen et al., 2020).
Specifically, DropEdge (Rong et al., 2020) randomly drops a certain ratio of
edges in training. In (Chen et al., 2020), the authors verify that popular
nodes are more likely to suffer from over-smoothing. Inspired by the finding,
we sparsify the graph by pruning superfluous edges following a degree-
sensitive probability.

Formally, we denote a user-item graph as
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of
nodes and $\mathcal{E}$ is the set of edges. The number of users and items in
the user-item graph is $M$ and $N$, respectively. We have $M+N=|\mathcal{V}|$,
where $|\cdot|$ denotes the cardinality of a set. We construct a symmetric
adjacency matrix $\bm{A}\in\mathbb{R}^{|\mathcal{V}|\times|\mathcal{V}|}$ from
the user-item interaction matrix $\bm{R}\in\mathbb{R}^{M\times N}$:

(4) $\bm{A}=\begin{pmatrix}\bm{0}&\bm{R}\\\
\bm{R}^{\top}&\bm{0}\end{pmatrix},$

and each entry $\bm{A}_{ui}$ of $\bm{A}$ is set to 1, if user $u$ has
interacted with item $i$, otherwise, $\bm{A}_{ui}$ is set to 0.

Given a specific edge $e_{k}\in\mathcal{E},(0\leq k<|\mathcal{E}|)$ which
connects node $i$ and $j$, we calculate its probability as
$p_{k}=\frac{1}{\sqrt{\omega_{i}}\sqrt{\omega_{j}}}$, where $\omega_{i}$ and
$\omega_{j}$ are the degrees of nodes $i$ and $j$ in graph $\mathcal{G}$,
respectively. Usually, we prune a certain proportion $\rho$ of edges of the
graph. That is, the number of edges should be pruned is
$\lfloor\rho|\mathcal{E}|\rfloor$, where $\lfloor\cdot\rfloor$ is the floor
function. As a result, the number of retained edges is
$n=\lceil|\mathcal{E}|(1-\rho)\rceil$. Thus, we sample edges from the
multinomial distribution with index $n$ and parameter vector $\bm{p}=\langle
p_{0},p_{1},\cdots,p_{|\mathcal{E}|-1}\rangle$. In this way, edges connecting
high-degree nodes have a low probability to be sampled from the graph. That
is, these edges are more likely to be pruned in $\mathcal{G}$. We then
construct a symmetric adjacency matrix $\bm{A}_{\rho}$ based on the sampled
edges following Eq. (4). In line with prior latent item-item graph, we also
perform the re-normalization trick on $\bm{A}_{\rho}$, resulting as
$\widehat{\bm{A}}_{\rho}$. Same as DropEdge, FREEDOM prunes the user-item
graph and normalizes the sampled adjacency matrix iteratively in each training
epoch. However, we resort to the original normalized adjacency matrix
$\widehat{\bm{A}}=\bm{D}^{-1/2}\bm{A}\bm{D}^{-1/2}$ in model inference.

###  3.3. Integration of Two Graphs for Learning

We perform graph convolutions on both graphs, that is, we employ a light-
weighted GCN (He et al., 2020) for information propagation and aggregation on
$\bm{S}$ and $\widehat{\bm{A}}_{\rho}$. Specifically, the graph convolution
over the item-item graph is defined as:

(5)
$\widetilde{\bm{h}}_{i}^{l}=\sum_{j\in\mathcal{N}(i)}{\bm{S}}_{ij}\widetilde{\bm{h}}_{j}^{l-1},$

where $\mathcal{N}(i)$ is the neighbor items of $i$,
$\widetilde{\bm{h}}_{i}^{l}\in\mathbb{R}^{d}$ is the $l$-th layer item
representation of item $i$, $\widetilde{\bm{h}}_{i}^{0}$ denotes its
corresponding ID embedding vector and $d$ is the dimension of an item or user
ID embedding. We stack $L_{ii}$ convolutional layers on the item-item graph
$\bm{S}$ and obtain the last layer representation
$\widetilde{\bm{h}}_{i}^{L_{ii}}$ as the representation
$\widetilde{\bm{h}}_{i}\in\mathbb{R}^{d}$ of $i$ from the multimodal view:

(6) $\widetilde{\bm{h}}_{i}=\widetilde{\bm{h}}_{i}^{L_{ii}}.$

Analogously, in the user-item graph, we perform $L_{ui}$ convolutional
operations on $\widehat{\bm{A}}_{\rho}$ and obtain embedding of a user
$\widehat{\bm{h}}_{u}\in\mathbb{R}^{d}$ or an item
$\widehat{\bm{h}}_{i}\in\mathbb{R}^{d}$ with a readout function on all the
hidden representations resulted in each layer:

(7)
$\begin{split}\widehat{\bm{h}}_{u}&=\operatorname{READOUT}(\widehat{\bm{h}}_{u}^{0},\widehat{\bm{h}}_{u}^{1},\cdots,\widehat{\bm{h}}_{u}^{L_{ui}}),\\\
\widehat{\bm{h}}_{i}&=\operatorname{READOUT}(\widehat{\bm{h}}_{i}^{0},\widehat{\bm{h}}_{i}^{1},\cdots,\widehat{\bm{h}}_{i}^{L_{ui}}),\end{split}$

where the $\operatorname{READOUT}$ function can be any differentiable
function, $\widehat{\bm{h}}_{u}^{0}$ and
$\widehat{\bm{h}}_{i}^{0}=\widetilde{\bm{h}}_{i}^{0}$ denotes the ID
embeddings of user $u$ and item $i$, respectively. We use the default mean
function of LightGCN (He et al., 2020) for embedding readout.

Finally, we use the user representation output by the user-item graph as its
final representation. For the item, we sum up the representations obtained
from the two graphs as its final representation.

(8) $\begin{split}{\bm{h}_{u}}&=\widehat{\bm{h}}_{u},\\\
{\bm{h}_{i}}&=\widetilde{\bm{h}}_{i}+\widehat{\bm{h}}_{i}.\end{split}$

To fully explore the raw features, we project multimodal features of item $i$
in each modality via MLPs.

(9) $\bm{h}_{i}^{m}=\bm{x}_{i}^{m}\bm{W}_{m}+\bm{b}_{m},$

where $\bm{W}_{m}\in\mathbb{R}^{d_{m}\times d},\bm{b}_{m}\in\mathbb{R}^{d}$
denote the linear transformation matrix and bias in the MLP. In this way, each
uni-modal representation $\bm{h}_{i}^{m}$ shares the same latent space with
its ID embedding $\bm{h}_{i}$.

For model optimization, we adopt the pairwise Bayesian personalized ranking
(BPR) loss (Rendle et al., 2009), which encourages the prediction of a
positive user-item pair to be scored higher than its negative pair:

$\displaystyle\mathcal{L}_{bpr}=\sum_{(u,i,j)\in\mathcal{D}}\Bigl{(}$
$\displaystyle-\operatorname{log}\sigma(\bm{h}_{u}^{\top}\bm{h}_{i}-\bm{h}_{u}^{\top}\bm{h}_{j})+$
(10)
$\displaystyle\lambda\sum_{m\in\mathcal{M}}-\operatorname{log}\sigma(\bm{h}_{u}^{\top}\bm{h}_{i}^{m}-\bm{h}_{u}^{\top}\bm{h}_{j}^{m})\Bigr{)},$

where $\mathcal{D}$ is the set of training instances, and each triple
$(u,i,j)$ satisfies $\bm{A}_{ui}=1~{}\text{and}~{}\bm{A}_{uj}=0$.
$\sigma(\cdot)$ is the sigmoid function and $\lambda$ is a hyperparameter of
FREEDOM to weigh the reconstruction losses between user-item ID embeddings and
projected multimodal features.

###  3.4. Top-$K$ Recommendation

To generate item recommendations for a user, we first predict the interaction
scores between the user and candidate items. Then, we rank candidate items
based on the predicted interaction scores in descending order, and choose $K$
top-ranked items as recommendations to the user. The interaction score is
calculated as:

(11) $r(\bm{h}_{u},\bm{h}_{i})=\bm{h}_{u}^{\top}\bm{h}_{i}.$

A high score suggests that the user prefers the item. Note that we only use
user and item ID embeddings for prediction, because we empirically find the
adding of projected item multimodal features in prediction does not show
improvement on performance. However, the item multimodal representations can
partially benefit the learning of user representations in FREEDOM via Eq.
(10).

##  4\. Spectral Analysis

In this section, we examine the benefits of freezing the item-item graph in
FREEDOM through the lens of spectral analysis. We show that it possesses a
tighter upper bound on the graph spectrum. In addition, we empirically
calculate the largest eigenvalues of the normalized graph Laplacian on
experimental datasets to validate our analysis.

###  4.1. Preliminaries

Without loss of generality, we analyze the normalized item-item adjacency
matrix
$\widetilde{\bm{S}}^{m}=({\bm{D}^{m}})^{-\frac{1}{2}}\widehat{\bm{S}}^{m}({\bm{D}^{m}})^{-\frac{1}{2}}$
within a specific modality $m$. We denote the corresponding matrix of LATTICE
as $\widetilde{\bm{S}^{\prime}}^{m}=({\bm{D}^{\prime
m}})^{-\frac{1}{2}}\widehat{\bm{S}^{\prime}}^{m}({\bm{D}^{\prime
m}})^{-\frac{1}{2}}$. We omit $m$ for clarity in the following analysis.

###  4.2. Theoretical Analysis

###### Lemma 4.1.

The eigenvalues of the frozen matrix in FREEDOM possess a tighter upper bound.

###### Proof.

Let $\lambda$ be an eigenvalue of the non-negative matrix
$\widetilde{\bm{S}}$.

$\displaystyle\widetilde{\bm{S}}\bm{x}=\lambda\bm{x}$
$\displaystyle\Longrightarrow\lambda\left|x_{i}\right|=\left|\sum_{j=1}^{n}\tilde{s}_{ij}x_{j}\right|\leq\left(\sum_{j=1}^{n}\tilde{s}_{ij}\right)\max_{j}\left|x_{j}\right|$
$\displaystyle\Longrightarrow\lambda\max_{i}\left|x_{i}\right|\leq\max_{i}\left(\sum_{j=1}^{n}\tilde{s}_{ij}\right)\max_{j}\left|x_{j}\right|$
(12)
$\displaystyle\Longrightarrow\lambda\leq\max_{i}\left(\sum_{j=1}^{n}\tilde{s}_{ij}\right)\leq
n\max_{i,j}\tilde{s}_{ij}$

Each element in $\widetilde{\bm{S}}$ of FREEDOM and
$\widetilde{\bm{S}^{\prime}}$ of LATTICE is positive, with the form of
$\tilde{s}_{ij}/\sqrt{d_{ii}d_{jj}}$ and
$\tilde{s^{\prime}}_{ij}/\sqrt{d^{\prime}_{ii}d^{\prime}_{jj}}$. As function
$g(\tilde{s^{\prime}}_{ij})=\tilde{s^{\prime}}_{ij}/(\tilde{s^{\prime}}_{ij}+\sum_{k\neq
i}\tilde{s^{\prime}}_{kj})$ is monotonically increasing, and maximizing Eq.
(12) requires the maximized $\tilde{s^{\prime}}_{ij}\geq\bar{d_{ii}}$ (average
value of node degree). Hence, we can derive
$\max_{i,j}\tilde{s}_{ij}\leq\max_{i,j}\tilde{s^{\prime}}_{ij}$. ∎

In consideration of the page limit, we have moved the more detailed proof to
Appendix A. Readers can access it for a more comprehensive understanding of
our work.

Table 2. Comparison of the largest eigenvalues of FREEDOM and LATTICE on different datasets (lower is better). Model | Baby | Sports | Clothing
---|---|---|---
FREEDOM | 1.1685 | 1.1016 | 1.0932
LATTICE | 1.1796 | 1.1180 | 1.1210

###  4.3. Empirical Study

We compute the largest eigenvalues of the item-item matrix in both FREEDOM and
LATTICE, as shown in Table 2. The results validate our previous analysis. A
tighter upper bound of eigenvalues in the item-item graph ensures that the
frozen item-item graph in FREEDOM can act as a low-pass filter, eliminating
the effect of negative coefficients at large frequencies. We further
investigate the impact of the frozen item-item graph in FREEDOM and the
learnable graph in LATTICE on validation accuracy. The plots in Fig. 2 reveal
that graphs in FREEDOM trained with this property achieve higher accuracy and
more stable performance than LATTICE.

(a)

(b)

Figure 2. Validation accuracy (_i.e._ , Recall@20) of FREEDOM and LATTICE
using frozen and learnable item-item matrices, respectively.

##  5\. Experiments

To evaluate the effectiveness and efficiency of our proposed FREEDOM, we
conduct experiments to answer the following research questions on three real-
world datasets.

  * •

RQ1: How does FREEDOM perform compared with the state-of-the-art methods for
recommendation? As our model improves LATTICE (Zhang et al., 2021) by freezing
and denoising the graph structures, how about its improvement over LATTICE?

  * •

RQ2: How efficient of our proposed FREEDOM in terms of computational
complexity and memory cost?

  * •

RQ3: How do different components in FREEDOM influence its recommendation
accuracy?

  * •

RQ4: How sensitive is our model under the perturbation of hyperparameters?

Table 3. Statistics of the experimental datasets. Dataset | # Users | # Items | # Interactions | Sparsity
---|---|---|---|---
Baby | 19,445 | 7,050 | 160,792 | 99.88%
Sports | 35,598 | 18,357 | 296,337 | 99.95%
Clothing | 39,387 | 23,033 | 278,677 | 99.97%

###  5.1. Experimental Datasets

Following (Zhang et al., 2021), we conduct experiments on three categories of
the Amazon review dataset (He and McAuley, 2016a): (a) _Baby_ , (b) _Sports
and Outdoors_ , and (c) _Clothing, Shoes and Jewelry_. For simplicity, we
denote them as _Baby_ , _Sports_ and _Clothing_ , respectively. The Amazon
review dataset provides both visual and textual information about the items
and varies in the number of items under different categories. The raw data of
each dataset are pre-processed with a 5-core setting on both items and users,
and their filtered results are presented in Table 3. We directly use the
4,096-dimensional visual features extracted by pre-trained Convolutional
Neural Networks (He and McAuley, 2016a). For the textual modality, we extract
a 384-dimensional textual embedding by utilizing sentence-transformers
(Reimers and Gurevych, 2019) 111We use all-MiniLM-L6-v2 because it is much
faster and offers better quality than the pre-trained model used in LATTICE.
Except for the pre-trained model, our experimental setting completely follows
LATTICE (Zhang et al., 2021). on the concatenation of the title, descriptions,
categories, and brand of each item.

###  5.2. Baseline Methods

To demonstrate the effectiveness of FREEDOM, we compare it with the state-of-
the-art recommendation methods in two categories.

First category comprises two general CF models that recommend personalized
items to users solely based on user-item interactions:

  * •

BPR (Rendle et al., 2009) optimizes the latent representations of users and
items under the framework of matrix factorization (MF) with a BPR loss.

  * •

LightGCN (He et al., 2020) simplifies the vanilla GCN by removing its non-
linear activation and feature transformation layers for recommendation.

While the second line of work includes six multimodal recommendation models
that leverage both user interactions and multimodal information about items
for recommendation:

  * •

VBPR (He and McAuley, 2016b) incorporates visual features for user preference
learning under the MF framework and BPR loss. Following (Zhang et al., 2021;
Wang et al., 2021b), we concatenate the multimodal features of an item as its
visual feature for user preference learning.

  * •

MMGCN (Wei et al., 2019) fuses the representations generated by GCNs in each
modality of items for recommendation.

  * •

GRCN (Wei et al., 2020) refines the user-item bipartite graph with the removal
of false-positive edges for multimodal recommendation. Based on the refined
graph, it then learns user and item representations by performing information
propagation and aggregation via GCNs.

  * •

DualGNN (Wang et al., 2021b) augments the representations of users in GCNs
with an additional user-user correlation graph that is extracted from the
user-item graph.

  * •

LATTICE (Zhang et al., 2021) learns the latent semantic item-item structures
from the multimodal features for recommendation. As FREEDOM improves LATTICE,
we highlight its improvement over LATTICE in Table 4.

  * •

SLMRec (Tao et al., 2022) incorporates self-supervised learning into
multimedia recommendation. It proposes three data augmentations to uncover the
multimodal patterns in data for contrastive learning.

###  5.3. Evaluation Protocols

For a fair comparison, we adopt the same evaluation settings of (Wang et al.,
2021b; Zhang et al., 2021; Tao et al., 2022). Specifically, we use two widely-
used evaluation protocols for top-$K$ recommendation: Recall@$K$ and NDCG@$K$,
which we refer to as R@$K$ and N@$K$ in brief. We report the average metrics
of all users in the test set under both $K=10$ and $K=20$. For each user in
the evaluated dataset, we randomly split 80% of historical interactions for
training, 10% for validation and the remaining 10% for testing. During
training, we conduct the negative sampling strategy to pair each observed
user-item interaction in the training set with one negative item that the user
does not interact with before. We use the all-ranking protocol to compute the
evaluation metrics for recommendation accuracy comparison.

###  5.4. Implementation and Hyperparameter Settings

Following existing work (He et al., 2020; Zhang et al., 2021), we fix the
embedding size of both users and items to 64 for all models, initialize the
embedding parameters with the Xavier method (Glorot and Bengio, 2010), and use
Adam (Kingma and Ba, 2015) as the optimizer. For a fair comparison, we
carefully tune the parameters of each model following their published papers.
All models are implemented by PyTorch (Paszke et al., 2019) and evaluated on a
Tesla V100 GPU card with 32 GB memory. To reduce the hyperparameters searching
space of FREEDOM, we fix the number of GCN layers in the user-item bipartite
graph and the item-item graph at $L_{ui}=2$ and $L_{ii}=1$, respectively. We
empirically fix the hyperparameter of $\lambda$ at $1e-03$ and the visual
feature ratio $\alpha_{v}$ at 0.1. We then perform a grid search on other
hyperparameters of FREEDOM across all datasets to conform to its optimal
settings. Specifically, the ratio $\rho$ of the degree-sensitive edge pruning
is searched from {0.8, 0.9}. For convergence consideration, the early stopping
and total epochs are fixed at 20 and 1000, respectively. Following (Zhang et
al., 2021), we use R@20 on the validation data as the training stopping
indicator. To ensure a fair comparison, all baseline models as well as our
proposed model have been integrated into the unified multimodal recommendation
framework, MMRec (Zhou, 2023).

Table 4. Overall performance achieved by different recommendation methods in terms of Recall and NDCG. We mark the global best results on each dataset under each metric in boldface and the second best is underlined. Improvement percentage (_improv._) is calculated as the ratio of performance increment from LATTICE to FREEDOM under each dataset and metric. To verify the stability of our method, we conduct experiments across 5 different seeds and state the improvements are statistically significant at the level of $p$ ¡ 0.01 with a paired $t$-test. Dataset | Metric | General CF model | Multimodal model |
---|---|---|---|---
BPR | LightGCN | VBPR | MMGCN | GRCN | DualGNN | SLMRec | LATTICE | FREEDOM | _improv._
Baby | R@10 | 0.0357 | 0.0479 | 0.0423 | 0.0421 | 0.0532 | 0.0513 | 0.0521 | 0.0547 | 0.0627 | 14.63%
R@20 | 0.0575 | 0.0754 | 0.0663 | 0.0660 | 0.0824 | 0.0803 | 0.0772 | 0.0850 | 0.0992 | 16.71%
N@10 | 0.0192 | 0.0257 | 0.0223 | 0.0220 | 0.0282 | 0.0278 | 0.0289 | 0.0292 | 0.0330 | 13.01%
N@20 | 0.0249 | 0.0328 | 0.0284 | 0.0282 | 0.0358 | 0.0352 | 0.0354 | 0.0370 | 0.0424 | 14.59%
Sports | R@10 | 0.0432 | 0.0569 | 0.0558 | 0.0401 | 0.0599 | 0.0588 | 0.0663 | 0.0620 | 0.0717 | 15.65%
R@20 | 0.0653 | 0.0864 | 0.0856 | 0.0636 | 0.0919 | 0.0899 | 0.0990 | 0.0953 | 0.1089 | 14.27%
N@10 | 0.0241 | 0.0311 | 0.0307 | 0.0209 | 0.0330 | 0.0324 | 0.0365 | 0.0335 | 0.0385 | 14.93%
N@20 | 0.0298 | 0.0387 | 0.0384 | 0.0270 | 0.0413 | 0.0404 | 0.0450 | 0.0421 | 0.0481 | 14.25%
Clothing | R@10 | 0.0206 | 0.0361 | 0.0281 | 0.0227 | 0.0421 | 0.0452 | 0.0442 | 0.0492 | 0.0629 | 27.85%
R@20 | 0.0303 | 0.0544 | 0.0415 | 0.0361 | 0.0657 | 0.0675 | 0.0659 | 0.0733 | 0.0941 | 28.38%
N@10 | 0.0114 | 0.0197 | 0.0158 | 0.0120 | 0.0224 | 0.0242 | 0.0241 | 0.0268 | 0.0341 | 27.24%
N@20 | 0.0138 | 0.0243 | 0.0192 | 0.0154 | 0.0284 | 0.0298 | 0.0296 | 0.0330 | 0.0420 | 27.27%

###  5.5. Performance Comparison

#### Effectiveness (RQ1)

Table 4 reports the comparison of recommendation accuracy in terms of Recall
and NDCG, from which we have the following observations: 1). Although LATTICE
obtains the second best results on Baby and Clothing datasets, FREEDOM
improves LATTICE by an average of 19.07% across all datasets and outperforms
other baselines as well. The improvements attribute to the graph structures
denoising and freezing components of FREEDOM. Denoising the user-item graph in
$\bm{A}$ reduces the impact of noise signal in false-positive interactions.
The frozen item-item graph in FREEDOM ensures the items are relevant to each
other if linked because it built on the raw multimodal features. On the
contrary, the latent item-item graph is dynamically learned via projecting the
raw multimodal features into a low-dimensional space. The affinity of two
items in the graph depends on not only the raw multimodal features but also
the projectors (_i.e._ , MLPs). 2). Generally, both general MF (_i.e._ , BPR)
and graph-based (_i.e._ , LightGCN) models can benefit from the multimodal
information. For example, VBPR leveraging multimodal features outperforms BPR
by up to 27.63% on average. Most graph-based multimodal models except MMGCN
show better recommendation results than MF models (_i.e._ , BPR and VBPR) and
general CF models. However, we observe that the performance of MMGCN is
inferior to that of BPR on Sports dataset. One potential reason for this might
be that the textual and visual representations extracted from the texts and
images of products in the Sports dataset are less informative than those of
the Baby and Clothing datasets. Another reason may be the fusion mechanism
used in MMGCN, which sums up the features from all modalities, making it
difficult to discern the prominent contribution of individual modalities. Our
proposed FREEDOM utilizing LightGCN as its backbone network gains a
significant margin of 42.79% over the original LightGCN on average. 3). In
graph-based multimodal models, compared with MMGCN, GRCN utilizes simplified
graph convolutional operations and refines the user-item bipartite graph by
assigning weights based on the affinities of user preferences and item
contents. It shows better performance in dense datasets, but is inferior in
Clothing dataset. The reason is that the assignments of low weights on less
similar user-item edges impede the information propagation of GCNs in a sparse
dataset. DualGNN and SLMRec utilize auxiliary information to augment the
representation learnings on users and items. They have comparable performance
with each other on the evaluated dataset except Sports. One potential reason
is that the extracted textual and visual representations from the texts and
images of products in Sports are less informative than that of Baby and
Clothing datasets. The evidence is that in Table 4, the improvements achieved
by GRCN and DualGNN over LightGCN in Sports are not as significant as that of
Baby and Clothing. SLMRec augments the representation from each modality of an
item with self-supervised learning and gains better results than GRCN and
DualGNN in Sports. Analogously, both LATTICE and FREEDOM augment the
representations of items via a latent item-item graph and show competitive
results.

Overall, the experiment results in Table 4 validate the effectiveness of
augmenting item representation with multimodal information. Furthermore,
freezing the latent graph structure of the item as in FREEDOM can help achieve
even better performance.

#### Efficiency (RQ2)

We report the memory and training time consumed by FREEDOM and baselines in
Table 5. From the table, we observe: 1). Multimodal models usually utilize
more memory than the general CF models as they need to process modality-aware
features. Graph-based models perform convolutional operations on graphs and
cost more time on training. DualGNN consumes even more time in training
because the convolutional operations are performed not only on the user-item
graph but also on the user-user relationship graph. MMGCN propagates
convolutional operators on each modality, resulting in increased training
time. 2). Compared FREEDOM with LATTICE, the proposed FREEDOM can reduce the
memory cost and training time of LATTICE on Clothing by 6$\times$ and
4$\times$, respectively. FREEDOM removes the construction of latent item-item
graph in each training epoch, it pre-builds the graph before training and
freezes it during training. With the removal of item-item graph construction
in training, FREEDOM is preferable with large graphs.

Table 5. Comparison of FREEDOM against state-of-the-art baselines on model efficiency. Dataset | Metric | General CF model | Multimodal model
---|---|---|---
BPR | LightGCN | VBPR | MMGCN | GRCN | DualGNN | SLMRec | LATTICE | FREEDOM
Baby | Memory (GB) | 1.59 | 1.69 | 1.89 | 2.69 | 2.95 | 2.05 | 2.08 | 4.53 | 2.13
Time ($s$/epoch) | 0.47 | 0.99 | 0.57 | 3.48 | 2.36 | 7.81 | 1.91 | 1.61 | 1.25
Sports | Memory (GB) | 2.00 | 2.24 | 2.71 | 3.91 | 4.49 | 2.81 | 3.04 | 19.93 | 3.34
Time ($s$/epoch) | 0.95 | 2.86 | 1.28 | 16.60 | 6.74 | 12.60 | 5.52 | 10.71 | 3.46
Clothing | Memory (GB) | 2.16 | 2.43 | 3.02 | 4.24 | 4.58 | 3.02 | 3.40 | 28.22 | 4.15
Time ($s$/epoch) | 0.97 | 2.94 | 1.29 | 16.71 | 7.21 | 13.44 | 5.09 | 15.96 | 3.67

###  5.6. Ablation Study (RQ3)

In this section, we decouple the proposed FREEDOM and evaluate the
contribution of each component with regard to recommendation accuracy. We
design the following variants of FREEDOM based on its architecture:

  * •

FREEDOM-D denoises the user-item graph in FREEDOM without freezing the item-
item graph.

  * •

FREEDOM-F improves LATTICE merely by the freezing component of FREEDOM, which
freezes the item-item graph as introduced in Section 3.

  * •

FREEDOM-R replaces the denoising method of degree-sensitive edge pruning in
FREEDOM with random edge dropout (Rong et al., 2020).

  * •

FREEDOM-0 ablates the contribution of multimodal losses in Eq. (10) by setting
$\lambda$ to 0.

We report the comparison results in terms of R@20 and N@20 with Fig. 4. The
results show that the freezing component of FREEDOM attributes significantly
to its overall performance. However, denoising the user-item graph can further
improve the performance. Freezing the item-item graph in FREEDOM (_i.e._ ,
FREEDOM-F) gains consistent improvements over LATTICE on three datasets, but
not for the denoising component. We speculate that without the freezing
component, the denoising component may affect graph connectivity on sparse
graphs and result in performance degradation. FREEDOM-R with random edge
dropout shows slight improvement over FREEDOM-F but is still worse than
FREEDOM, showing the effectiveness of degree-sensitive edge pruning. The
performance of FREEDOM-0 is comparable to FREEDOM, indicating the effective
design of FREEDOM in freezing and denoising graph structures for
recommendation. However, FREEDOM can benefit slightly from the inclusion of
multimodal losses.

Figure 3. Comparison of LATTICE with FREEDOM variants.

Figure 4. Performance of FREEDOM changes with the ratio of visual features in
constructing the item-item graph.

(a) Baby

(b) Clothing

Figure 5. Performance of FREEDOM with regard to different loss weights
$\lambda$ and edge pruning ratios $\rho$ on Baby and Clothing datasets.

###  5.7. Hyperparameter Sensitivity Study (RQ4)

Multimodal Features. FREEDOM uses the raw textual and visual features
extracted from pre-trained models to construct the latent item-item graph. We
first study how information from different modalities could affect the
performance of FREEDOM by adjusting the ratio of visual features from 0.0 to
1.0 with a step of 0.1 in constructing the graph. A ratio of 0.0 on visual
features means that the construction of item-item graph depends only on
textual features. The item-item graph, on the other hand, is based on visual
features if the ratio is 1.0. The recommendation results on R@20 and N@20 for
three evaluated datasets are shown in Fig. 4. From the results, we may infer
that the textual features are more informative than the visual features in
constructing an effective item-item graph.

The Dropout Ratio and Loss Weight. We vary the edge pruning ratio $\rho$ in
the denoising component of FREEDOM from 0.6 to 0.9 with a step of 0.1, and
vary the loss weight $\lambda$ in {1e-04, 1e-03, 1e-02, 1e-01}. Fig. 5(a) and
5(b) show the performance achieved by FREEDOM under different combinations of
embedding dropout ratios and weights on Baby and Clothing, respectively. The
results suggest a high edge pruning ratio of FREEDOM on large graphs. Compared
with the edge pruning ratio, the performance of FREEDOM is less sensitive to
the settings of loss trade-off $\lambda$. However, placing a high weight on
multimodal loss might limit the expressive power of FREEDOM and results in
performance degradation.

##  6\. Conclusion

In this paper, we experimentally reveal that the graph structure learning in a
state-of-the-art multimodal recommendation model (_i.e._ , LATTICE (Zhang et
al., 2021)) plays a trivial role in its performance. It is the item-item graph
constructed from raw multimodal features that contributes to the
recommendation accuracy. Based on the finding, we propose a model that freezes
the item-item graph and denoises the user-item graph simultaneously for
multimodal recommendation. Through both theoretical and empirical analysis, we
demonstrate that freezing the item-item graph in FREEDOM can yield various
benefits. In denoising, we devise a degree-sensitive edge pruning method to
sample the user-item graph, which shows better performance than the random
edge dropout (Rong et al., 2020) for recommendation. Finally, we conduct
extensive experiments to demonstrate the effectiveness and efficiency of
FREEDOM in multimodal recommendation.

###### Acknowledgements.

This work was supported by Alibaba Group through Alibaba Innovative Research
(AIR) Program and Alibaba-NTU Singapore Joint Research Institute (JRI),
Nanyang Technological University, Singapore.

## References

  * (1)
  * Chen et al. (2009) Jie Chen, Haw-ren Fang, and Yousef Saad. 2009.  Fast Approximate kNN Graph Construction for High Dimensional Data via Recursive Lanczos Bisection.  _Journal of Machine Learning Research_ 10, 9 (2009).
  * Chen et al. (2017) Jingyuan Chen, Hanwang Zhang, Xiangnan He, Liqiang Nie, Wei Liu, and Tat-Seng Chua. 2017\.  Attentive collaborative filtering: Multimedia recommendation with item-and component-level attention. In _Proceedings of the 40th International ACM SIGIR conference on Research and Development in Information Retrieval_. 335–344.
  * Chen et al. (2020) Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. 2020.  Simple and deep graph convolutional networks. In _International Conference on Machine Learning_. PMLR, 1725–1735.
  * Chen et al. (2019) Xu Chen, Hanxiong Chen, Hongteng Xu, Yongfeng Zhang, Yixin Cao, Zheng Qin, and Hongyuan Zha. 2019.  Personalized fashion recommendation with visual explanations based on multimodal attention network: Towards visually explainable recommendation. In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_. 765–774.
  * Franceschi et al. (2019) Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. 2019.  Learning discrete structures for graph neural networks. In _International conference on machine learning_. PMLR, 1972–1982.
  * Glorot and Bengio (2010) Xavier Glorot and Yoshua Bengio. 2010.  Understanding the difficulty of training deep feedforward neural networks. In _Proceedings of the thirteenth international conference on artificial intelligence and statistics_. JMLR Workshop and Conference Proceedings, 249–256.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017\.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ 30 (2017).
  * He and McAuley (2016a) Ruining He and Julian McAuley. 2016a.  Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. In _proceedings of the 25th international conference on world wide web_. 507–517.
  * He and McAuley (2016b) Ruining He and Julian McAuley. 2016b.  VBPR: visual bayesian personalized ranking from implicit feedback. In _Proceedings of the AAAI conference on artificial intelligence_ , Vol. 30.
  * He et al. (2020) Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. 2020\.  Lightgcn: Simplifying and powering graph convolution network for recommendation. In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_. 639–648.
  * Kazi et al. (2022) Anees Kazi, Luca Cosmo, Seyed-Ahmad Ahmadi, Nassir Navab, and Michael Bronstein. 2022.  Differentiable graph module (dgm) for graph convolutional networks.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ (2022).
  * Kingma and Ba (2015) Diederik P Kingma and Jimmy Ba. 2015.  Adam: A method for stochastic optimization. In _International Conference on Learning Representations_.
  * Liu et al. (2019) Fan Liu, Zhiyong Cheng, Changchang Sun, Yinglong Wang, Liqiang Nie, and Mohan Kankanhalli. 2019\.  User diverse preference modeling by multimodal attentive metric learning. In _Proceedings of the 27th ACM international conference on multimedia_. 1526–1534.
  * Liu et al. (2017) Qiang Liu, Shu Wu, and Liang Wang. 2017.  Deepstyle: Learning user preferences for visual recommendation. In _Proceedings of the 40th international acm sigir conference on research and development in information retrieval_. 841–844.
  * Luo et al. (2021) Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong, Jingchao Ni, Haifeng Chen, and Xiang Zhang. 2021.  Learning to drop: Robust graph neural network via topological denoising. In _Proceedings of the 14th ACM International Conference on Web Search and Data Mining_. 779–787.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019\.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ 32 (2019).
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-bert: Sentence embeddings using siamese bert-networks. In _EMNLP_. 3980–3990.
  * Rendle et al. (2009) Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. 2009.  BPR: Bayesian Personalized Ranking from Implicit Feedback. In _Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence_. 452–461.
  * Rong et al. (2020) Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. 2020\.  Dropedge: Towards deep graph convolutional networks on node classification. In _International Conference on Learning Representations_.
  * Simonyan and Zisserman (2014) Karen Simonyan and Andrew Zisserman. 2014.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ (2014).
  * Tao et al. (2022) Zhulin Tao, Xiaohao Liu, Yewei Xia, Xiang Wang, Lifang Yang, Xianglin Huang, and Tat-Seng Chua. 2022.  Self-supervised Learning for Multimedia Recommendation.  _IEEE Transactions on Multimedia_ (2022).
  * Wang et al. (2021b) Qifan Wang, Yinwei Wei, Jianhua Yin, Jianlong Wu, Xuemeng Song, and Liqiang Nie. 2021b.  DualGNN: Dual Graph Neural Network for Multimedia Recommendation.  _IEEE Transactions on Multimedia_ (2021).
  * Wang et al. (2021a) Wenjie Wang, Fuli Feng, Xiangnan He, Liqiang Nie, and Tat-Seng Chua. 2021a.  Denoising implicit feedback for recommendation. In _Proceedings of the 14th ACM international conference on web search and data mining_. 373–381.
  * Wei et al. (2020) Yinwei Wei, Xiang Wang, Liqiang Nie, Xiangnan He, and Tat-Seng Chua. 2020.  Graph-refined convolutional network for multimedia recommendation with implicit feedback. In _Proceedings of the 28th ACM international conference on multimedia_. 3541–3549.
  * Wei et al. (2019) Yinwei Wei, Xiang Wang, Liqiang Nie, Xiangnan He, Richang Hong, and Tat-Seng Chua. 2019\.  MMGCN: Multi-modal graph convolution network for personalized recommendation of micro-video. In _Proceedings of the 27th ACM International Conference on Multimedia_. 1437–1445.
  * Wu et al. (2020) Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. 2020.  Graph neural networks in recommender systems: a survey.  _ACM Computing Surveys (CSUR)_ (2020).
  * Xu et al. (2022) Zhe Xu, Boxin Du, and Hanghang Tong. 2022.  Graph sanitation with application to node classification. In _Proceedings of the ACM Web Conference 2022_. 1136–1147.
  * Zhang et al. (2021) Jinghao Zhang, Yanqiao Zhu, Qiang Liu, Shu Wu, Shuhui Wang, and Liang Wang. 2021\.  Mining Latent Structures for Multimedia Recommendation. In _Proceedings of the 29th ACM International Conference on Multimedia_. 3872–3880.
  * Zhang et al. (2022) Lingzi Zhang, Yong Liu, Xin Zhou, Chunyan Miao, Guoxin Wang, and Haihong Tang. 2022\.  Diffusion-Based Graph Contrastive Learning for Recommendation with Implicit Feedback. In _International Conference on Database Systems for Advanced Applications_. Springer, 232–247.
  * Zhou et al. (2023d) Hongyu Zhou, Xin Zhou, Zhiwei Zeng, Lingzi Zhang, and Zhiqi Shen. 2023d.  A Comprehensive Survey on Multimodal Recommender Systems: Taxonomy, Evaluation, and Future Directions.  _arXiv preprint arXiv:2302.04473_ (2023).
  * Zhou et al. (2023e) Hongyu Zhou, Xin Zhou, Lingzi Zhang, and Zhiqi Shen. 2023e.  Enhancing Dyadic Relations with Homogeneous Graphs for Multimodal Recommendation.  _arXiv preprint arXiv:2301.12097_ (2023).
  * Zhou (2023) Xin Zhou. 2023.  MMRec: Simplifying Multimodal Recommendation.  _arXiv preprint arXiv:2302.03497_ (2023).
  * Zhou et al. (2023a) Xin Zhou, Donghui Lin, Yong Liu, and Chunyan Miao. 2023a.  Layer-refined graph convolutional networks for recommendation. In _2023 IEEE 39th International Conference on Data Engineering (ICDE)_. IEEE, 1247–1259.
  * Zhou et al. (2022) Xin Zhou, Shigeo Matsubara, Yuan Liu, and Qidong Liu. 2022\.  Bribery in Rating Systems: A Game-Theoretic Perspective. In _Pacific-Asia Conference on Knowledge Discovery and Data Mining_. Springer, 67–78.
  * Zhou et al. (2023b) Xin Zhou, Aixin Sun, Yong Liu, Jie Zhang, and Chunyan Miao. 2023b.  Selfcf: A simple framework for self-supervised collaborative filtering.  _ACM Transactions on Recommender Systems_ 1, 2 (2023), 1–25.
  * Zhou et al. (2023c) Xin Zhou, Hongyu Zhou, Yong Liu, Zhiwei Zeng, Chunyan Miao, Pengwei Wang, Yuan You, and Feijun Jiang. 2023c.  Bootstrap latent representations for multi-modal recommendation. In _Proceedings of the ACM Web Conference 2023_. 845–854.

##  Appendix A Proof of LEMMA 4.1

Let $s^{\prime}_{ij}$ represent the element in the adjacency matrix of LATTICE
and let $s_{ij}$ represent the corresponding element in FREEDOM. We can derive
that $s_{ij}=1\geq s^{\prime}_{ij}$. As defined in the paper,
$\bm{D}^{\prime}=\mathrm{diag}(d^{\prime}_{11},\cdots,d^{\prime}_{nn})$ is a
diagonal matrix where each entry on the diagonal is equal to the row-sum of
the adjacency matrix $d^{\prime}_{ii}=\sum_{j}s^{\prime}_{ij}$. The normalized
adjacency matrix $\widetilde{\bm{S}^{\prime}}$ in LATTICE can be denoted as
follows:

$\displaystyle\widetilde{\bm{S}^{\prime}}=\begin{bmatrix}1/d^{\prime}_{11}&{s^{\prime}}_{12}/\sqrt{d^{\prime}_{11}d^{\prime}_{22}}&\dots&{s^{\prime}}_{1n}/\sqrt{d^{\prime}_{11}d^{\prime}_{nn}}\\\
{s^{\prime}}_{21}/\sqrt{d^{\prime}_{22}d^{\prime}_{11}}&1/d^{\prime}_{22}&\dots&{s^{\prime}}_{2n}/\sqrt{d^{\prime}_{22}d^{\prime}_{nn}}\\\
\vdots&\vdots&&\vdots\\\
{s^{\prime}}_{n1}/\sqrt{d^{\prime}_{nn}d^{\prime}_{11}}&{s^{\prime}}_{n2}/\sqrt{d^{\prime}_{nn}d^{\prime}_{22}}&\dots&1/d^{\prime}_{nn}\end{bmatrix}$

Analogously, we can derive the normalized adjacency matrix in FREEDOM. We
denote the elements in the normalized adjacency matrices of
$\widetilde{\bm{S^{\prime}}}$ and $\widetilde{\bm{S}}$ as
$\tilde{s^{\prime}}_{ij}$ and $\tilde{s}_{ij}$, respectively. As stated in the
paper, the function
$g(\tilde{s^{\prime}}_{ij})=\tilde{s^{\prime}}_{ij}/(\tilde{s^{\prime}}_{ij}+\sum_{k\neq
i}\tilde{s^{\prime}}_{kj})$ is monotonically increasing. To maximize Eq. (13)
in the paper, $\tilde{s^{\prime}}_{ij}$ must also be maximized. From the above
equations, we can deduce that the maximum value for either
$\widetilde{\bm{S}}$ or $\widetilde{\bm{S^{\prime}}}$ lies on its diagonal.
Therefore, we can derive that
$max_{i,j}\tilde{s}_{ij}=1/d_{ii}=1/\sum_{j}s_{ij}\leq
max_{i,j}\tilde{s^{\prime}}_{ij}=1/d^{\prime}_{ii}=1/\sum_{j}s^{\prime}_{ij}$.


# Debiased Novel Category Discovering and Localization

Juexiao Feng1,2,3, Yuhong Yang1,2,3, Yanchun Xie4, Yaqian Li4, Yandong Guo4,
Yuchen Guo1,2, Yuwei He1,2, Liuyu Xiang5, Guiguang Ding1,222footnotemark: 2
Corresponding Authors.

###### Abstract

In recent years, object detection in deep learning has experienced rapid
development. However, most existing object detection models perform well only
on closed-set datasets, ignoring a large number of potential objects whose
categories are not defined in the training set. These objects are often
identified as background or incorrectly classified as pre-defined categories
by the detectors. In this paper, we focus on the challenging problem of Novel
Class Discovery and Localization (NCDL), aiming to train detectors that can
detect the categories present in the training data, while also actively
discover, localize, and cluster new categories. We analyze existing NCDL
methods and identify the core issue: object detectors tend to be biased
towards seen objects, and this leads to the neglect of unseen targets. To
address this issue, we first propose an Debiased Region Mining (DRM) approach
that combines class-agnostic Region Proposal Network (RPN) and class-aware RPN
in a complementary manner. Additionally, we suggest to improve the
representation network through semi-supervised contrastive learning by
leveraging unlabeled data. Finally, we adopt a simple and efficient mini-batch
K-means clustering method for novel class discovery. We conduct extensive
experiments on the NCDL benchmark, and the results demonstrate that the
proposed DRM approach significantly outperforms previous methods, establishing
a new state-of-the-art.

## Introduction

Object detection (Girshick et al. 2013; Girshick 2015; Redmon et al. 2015)
technology is a fundamental research area of computer vision and is now widely
used in security (He et al. 2022), autonomous driving (Gu et al. 2021),
medical (Guo et al. 2022) field and other areas.

Figure 1: For current mainstream object detection models, they do not detect
new objects in unlabeled data. The existing NCDL methods tend to extract
biased proposals for unlabeled data. Our proposed model not only localizes
unknown objects but also clusters different unknown objects, thereby achieving
the discovery of new categories.

Existing object detection methods are trained on closed-set datasets with a
fixed number of categories. The majority of research focuses on improving
detection performance on closed-set datasets. In closed-set datasets
scenarios, object detectors are evaluated on a test set that contains the same
set of categories as the training set. However, in the in real-world scenario,
object detectors are faced with both known objects and potential unknown
objects that have never appeared or been annotated in the training set. Once
trained, they are unaware of any objects that they have not seen during
training. They either treat the unknown objects as background or misclassify
them as known categories. By contrast, humans have the capability of
perceiving, discovering, and recognizing unknown novel objects. Therefore, the
Novel Category Discovery problem, which aims to not only detect known objects,
but also discover novel categories unsupervisedly, has attracted much
attention

Most NCD methods involve a pre-training step on labeled sets and then perform
on unlabeled data. For example, (Han, Vedaldi, and Zisserman 2019) adds
partial information from known classes to unknown classes, pretending that
some parts are unlabeled, and then runs clustering algorithms in the expansion
phase for model inference. This approach of handling unlabeled data during
pre-training will cause the model to learn from unknown data. While this can
improve the model’s ability to discover unknown data, the model should not
have prior knowledge of the unlabeled dataset, which is not applicable in
real-world scenarios. (Han et al. 2020) utilizes all data, including labeled
and unlabeled data, for pre-training. However, such methods require repetitive
pre-training on all data after modifying the unlabeled set, resulting in
expensive training costs. Most NCD methods (Han et al. 2021; Han, Vedaldi, and
Zisserman 2019) have three steps. First, the object detector is pre-trained on
a closed set. Second, localize and discover potential unknown new objects.
Finally, the discovered objects are categorized into new categories by
clustering. While this approach proves its effectiveness, most methods only
utilize known objects and categories for pre-training and localization, which
may introduce bias. Such methods use detection heads for closed sets which may
introduce biased feature representations. Similarly, training RPNs only on
labeled closed-set objects may also lead to biased localization.

To address the aforementioned issues, we propose debiased NCD methods to
mitigate bias in both feature representation and object localization.
Specifically, from the localization perspective, we introduce a self-
supervised contrastive learning method. This method enables the model to learn
similar features for similar data instances and differentiate unknown class
objects from known class objects. Regarding feature representation, we propose
dual RPN strategy to simultaneously detect target objects in the image. One
RPN is designed to be class-aware, which aims to obtain accurate localization
information for known classes. The other RPN is designed to be class-agnostic,
where the classification loss is replaced with IOU regression to locate
unlabeled target objects. The resulting bounding boxes from both detectors are
selected as reliable confidence intervals, leading to improved performance for
both known and unknown classes.

Finally, we conduct extensive experiments on NCDL benchmarks and demonstrate
that the proposed debiased region mining method outperforms previous methods
significantly, establishing a new state-of-the-art.

Our contribution can be summarized as follows:

  * $\bullet$

We revisit the problem of novel category discovery in an open world and
investigate the bias problem in existing methods.

  * $\bullet$

We propose using dual object detectors together to obtain a good area proposal
that can effectively find all target objects in the image and locate them
better.

  * $\bullet$

We design a Semi-Supervised Instance-level Contrastive Learning method to
obtain image representations better than before and make the model rely on
unlabeled image information to learn image features.

  * $\bullet$

Based on this approach we have conducted a large number of experiments, which
show that our method outperforms other baseline methods.

Figure 2: Our Model Architecture. The category discovery and localization
pipeline includes three necessary components: 1) learning a feature extractor,
2) discovering boxes from unlabelled images, 3) grouping and categorizing the
extracted boxes.

## Related Works

### Open-set Recognition

Scheirer (Scheirer et al. 2012) found that the field of machine vision in
real-world scenarios is more of an ”open set” recognition phenomenon, in which
open set recognition requires identifying known classes while determining to
reject unknown classes, and the model gradually rejects unknown classes in the
process of recognition. In this paper, the authors discuss the definition of
the open set recognition problem as an empirical risk + open space risk
minimization problem. Jain (Jain, Scheirer, and Boult 2014) further discusses
the open set recognition problem in the above work, they believe that the
unknown class can be effectively rejected if the known class can be fully
modeled, so statistical extreme value theory is used to evaluate the posterior
probabilities. Dhamija (Dhamija et al. 2020) redefined the open set object
detection problem (OSOD), in which the authors argue that the traditional
object detection classifier can effectively reduce the model to discriminate
unknown classes as known classes with high confidence while proposing a new
metric to evaluate the performance of the detector at the time of analysis.

### Open-world Recognition

Although the open set recognition can identify unknown categories, the dataset
is dynamic for object detection in real scenarios, and the system detects and
adds new categories for objects that are continuously inputted. Bendale
(Bendale and Boult 2014) proposed the open world recognition problem and used
the nearest non-outlier (NNO) method, by which the model can be effectively
optimized and can enable the model to gradually add new categories after
balancing the spatial risk of the open world after detecting outliers. Joseph
(Joseph et al. 2021) extends the theory of the open world to the field of
object detection and proposes Open World Object Detection (OWOD) The model
achieves incremental learning by a simple and practical method of instant
playback, which enables the model to reduce the recognition accuracy of old
categories while learning new ones. Subsequently, for the subsequent work Zhao
(Zhao et al. 2022) improved the experimental setup and thought about more
basic principles to guide the construction of the OWOD benchmark. Firstly, the
test set for VOC and COCO should contain a perfect unknown label, if there is
no complete labeling, the detected images will be considered as False
Positive.

However, OWOD and OSOD for the unknown category identification process, the
model is known the number of categories of unknown categories to carry out the
statistics of unknown categories, when the number of unknown categories in
advance will have an impact on the effect of clustering, and in the real open
world scenario, we and the model can not know the number of unknown categories
in advance, so such a statistical process is still open to question. Moreover,
for learning new categories, OWOD and OSOD require additional staff to re-
label the new target images, while our model does not need to know the exact
number of unknown categories and does not need to re-label the new targets.

### Category Discovering

Mining for new classes is also one of the foundations of open-world detection,
where new classes are mined for the recognition of localization on unlabeled
data in images. In image recognition, the mining of unknown classes starts
with region proposals for the search of objects. In the beginning, region
search was mainly done by sliding window approach (Alexe, Deselaers, and
Ferrari 2012) to obtain the boxes of the object, by returning the better boxes
as offers or by classifying them by models. However, it has been found that
usually in a downstream task for object detection task, the target is usually
extracted using low-level features such as texture features, edge features,
etc. However, the region extraction network in Faster-RCNN (Ren et al. 2015),
which directly uses the features generated in the object detection task, but
faster-RCNN will target the prior knowledge of the model to improve the
extraction of known categories, is not a good choice for the identification
and localization of unknown categories.

### Novel Category Discovery

The concept of Novel Category Discovery (NCD) was first introduced in (Hsu,
Lv, and Kira 2018), where the authors proposed clustering unlabeled samples in
a given labeled dataset without class overlap. In (Hsu, Lv, and Kira 2018), a
prediction network is trained in advance on the labeled data, and then the
network predicts pairwise similarity between unlabeled data to discriminate
unknown classes and identify new categories. Many subsequent NCD papers (Zhao
and Han 2021; Zhong et al. 2021) have followed a two-step training strategy.
In (Zhao and Han 2021), a dual-branch learning framework is used to learn from
the target data, with one branch focusing on local fine-grained information
and the other branch focusing on global image features. Pseudo-labels are
generated through dual-ranking on the two branches for training on unknown
data. Currently, NCD problems assume that the objects of interest to the model
are known (pre-cropped) and do not exist in the training images. However, we
believe that in real-world scenarios, the objects of interest to the model
should be detected and localized in the images. Therefore, we adopt the Dual
RPN approach to extract information about unknown classes from the images and
perform localization and recognition, which improves the model’s
generalization.

Figure 3: The effect of three kinds of RPN. The object detector in (a) is used
a class-aware RPN. The object detector. In (b) uses an object detector that
removes the classification head and learns objectness alone. In (c) is our
proposed object detector based on IOU regression.

## Framework Details

### Overview

In this section, we illustrate our approach in Figure 2. The image passes
through two branches: the dual RPN module, which consists of two object
detectors that generate boxes for different requirements. Both sets of boxes
are processed and used as the final proposal input. Simultaneously, the image
features are extracted by the feature extractor and compared with the
extracted image features through semi-supervised contrastive learning. This
process helps determine whether the features belong to known or unknown
categories. The Region Proposal Network (RPN) extracts image proposals, and
the features are then pooled using ROI pooling to associate the proposals with
the features. Finally, the proposals and features are sent to the clustering
module, where all instances are clustered. This clustering ensures that
instances with similar features are grouped together, allowing for the
discovery of different unknown categories.

### Debiased Region Mining

In the field of object detection, the Region Proposal Network (RPN) is
commonly used for detecting objects in images. The requirement for an object
detector is to predict the positions of all the objects of interest in the
image. As a two-stage method, the RPN was designed from the beginning of the
algorithm with the expectation that it would propose all categories of objects
in the image. However, in practical tasks, we have observed two scenarios with
RPN. Firstly, when encountering unannotated images, the model tends to
classify them as background without localizing any objects. Secondly, when the
model recognizes unknown objects, it mistakenly classifies them as known
objects with high confidence. In Faster R-CNN, the object localizer is used
for the upstream task of the classification head, extracting known classes
that the model is interested in, which leads to a preference for recognizing
known objects and severely affects the model’s generality.

In Figure 3, the utilization of the object extractor in the standard Faster-
RCNN for locating image information is evident in (a). This extractor is
pretrained on the VOC dataset and subsequently applied to the COCO dataset,
with the inferred box serving as the proposal. Such proposals exhibit higher
confidence for known objects in the VOC, resulting in improved proposal
quality. However, proposals with average confidence tend to be aggregated,
often containing only a partial portion of the target object. Consequently,
the detected objects demonstrate limited generalization to the categories in
the VOC. In (b), an attempt was made to generate proposals by removing the
classification head and solely learning the objectness of the images within
the network. Notably, the number of proposals obtained by the network
surpasses that of the baseline and necessitates subsequent filtering. Despite
an enhancement in proposal generalization compared to the baseline, the
accuracy in locating VOC categories remains sub-optimal, and numerous
proposals still exhibit clustering. In (c), we propose a merging approach for
the aforementioned boxes. By selecting the box with a reliable confidence
region from both boxes and scaling the confidence of each box, the final
proposal is unified through non-maximum suppression (NMS). This method
significantly improves the quality of the proposals, enabling the extraction
of more target objects without compromising the accuracy for known VOC
categories. Additionally, it effectively resolves the issue of proposal
clustering.

We believe that the NCDL problem in real-world scenarios should be more
aligned with the object detection scenario in an open world, where the object
extractor should not be limited by classification heads to improve the
extraction performance of the RPN. Therefore, we draw inspiration from the
ideas proposed by (Kim et al. 2021) and others, and introduce a class-agnostic
RPN that can generate more generalizable objectness scores and retrieve more
objects. In our approach, we replace the class-related losses with a class-
agnostic loss in Faster-RCNN. This loss only estimates the objectness of a
region by: 1) using centerness regression instead of the classification loss
in the RPN, and 2) using IoU regression instead of the classification loss in
the ROI head. By enforcing the detector to focus solely on localization-aware
IoU/centerness, the resulting class-agnostic RPN can reduce bias and discover
more potential unknown objects. After obtaining two sets of detection boxes
for the same image using the detector, we conducted reliability analysis on
these two sets of boxes. The distribution of the boxes on the confidence
interval graph is different (detailed in the supplementary material),
indicating that each set of boxes has its own advantages and disadvantages.
Therefore, we propose a method called ”Debiased Region Mining” (DRM) to obtain
two different sets of boxes through class-aware RPN and class-agnostic RPN. As
shown in the figure, the boxes obtained by the class-aware RPN have higher
accuracy on known classes but poor generalization, and they also perform
poorly on unknown classes. On the other hand, the boxes obtained by the class-
agnostic RPN may not perform as well on known classes as the former, but they
have stronger generalization on unknown classes. This inspires us to combine
these two sets of boxes to obtain a new set of boxes that combines the
advantages of both.

Denote the above two sets of boxes and their confidence scores as
$\lambda_{1}$ and $\lambda_{2}$. We assume that the scores obey two different
distributions $\phi_{1}$and $\Phi_{2}$, respectively, and we first need to map
these two distributions to a uniform $\Phi$ to remove the gap between
different box generation methods. To keep the boxes with high confidence
itself and screen out the boxes with very low confidence, we also set the
threshold $\alpha_{i}$, $\beta_{i}(i=1,2)$ to filter the confidence levels.
After this, we merged the two sets of boxes and used Class-agnostic NMS to
merge the redundant boxes to get the post-fusion results.

### Semi-supervised Contrastive Finetuning

After we get the bbox on the Discovery set, we adopt a Semi-Supervised
Instance-level Contrastive Learning approach in order to extract more
generalized and expressive features.

First, we crop images in VOC dataset into patches according to ground truth
boxes to form our labeled set $B_{\mathcal{L}}$. Then, proposals we generated
on COCO train split are used to process patches in unlabeled set
$B_{\mathcal{U}}$. After that, given two different views of the same patch
$\mathbf{x},\mathbf{x}^{\prime}$ generated by random augmentations, we
formalize the unsupervised contrastive loss as:

$\mathcal{L}_{i}^{u}=-\log\frac{\exp(\mathbf{z}_{i}\cdot\mathbf{z}_{i}^{\prime}/\tau)}{\sum_{n}\mathit{1}_{[n\not=i]}\exp(\mathbf{z}_{i}\cdot\mathbf{z}_{n}/\tau)}$
(1)

where $\mathbf{z},\mathbf{z}^{\prime}$ are corresponding feature and $\tau$ is
temperature hyperparameter.

For images in supervised dataset, annotations are utilized to form supervised
contrastive loss:

$\mathcal{L}_{i}^{s}=-\frac{1}{|\mathcal{N}(i)|}\sum_{q\in\mathcal{N}(i)}\log\frac{\exp(\mathbf{z}_{i}\cdot\mathbf{z}_{q}/\tau)}{\sum_{n}\mathit{1}_{[n\not=i]}\exp(\mathbf{z}_{i}\cdot\mathbf{z}_{n}/\tau)},$
(2)

Where $\mathcal{N}(i)$ denotes the indices of which has the same label as
$\mathbf{x}_{i}$. Finally, the total loss is constructed as following:

$\mathcal{L}^{t}=(1-\lambda)\sum_{i\in B}\mathcal{L}_{i}^{u}+\lambda\sum_{i\in
B_{\mathcal{L}}}\mathcal{L}_{i}^{s}.$ (3)

This loss will supervise the training of our feature extractor.

Method |<EMAIL_ADDRESS>|<EMAIL_ADDRESS>| #Disc. Cls. | CorLoc |<EMAIL_ADDRESS>|<EMAIL_ADDRESS>| #Disc. Cls. | CorLoc
---|---|---|---|---|---|---|---|---
#cluster | 80 | 1000
Vplow | 0.0548 | 0.1229 | 18 | 0.9413 | 0.0818 | 0.0961 | 40 | 0.9413
DualMem | 0.0503 | 0.1174 | 16 | 0.9433 | 0.0025 | 0.0055 | 42 | 0.0746
OLN | 0.0517 | 0.1076 | 18 | 0.9713 | 0.0971 | 0.1427 | 45 | 0.9713
Ours | 0.0613 | 0.1203 | 20 | 0.9934 | 0.1052 | 0.2381 | 57 | 0.9934
Table 1: Comparison with contemporary discovery methods using AuC and CorLoc
for unknown classes in COCO train2014.

### Clustering

After completing the contrastive learning for unknown category objects, the
model performs clustering analysis on the obtained information, aggregating
unknown images with similar feature representations into clusters. We
initially use a clustering method similar to K-means but with two
modifications. Firstly, we employ an over-clustering strategy by forcing the
generation of another finer-grained partition of unlabeled data and increasing
the number of K (estimated number of clusters) to improve clustering purity
and feature representation quality. Over-clustering is beneficial in reducing
supervision, allowing the neural network to decide how to partition the data.
This separation is effective in the presence of noisy data or when
intermediate classes are randomly assigned to neighboring categories.
Secondly, using K-means in our task is time-consuming. So we use Minibatch
K-means, which is an optimization algorithm for K-means in large-scale data,
to reduce training computation time by randomly sampling a subset of data
during training while optimizing the objective function.

The main steps of the algorithm are as follows: 1) Initially, a subset of
training data is extracted, and K cluster centers are constructed using
K-means. 2) Sample data is further extracted from the training set and added
to the model, assigning them to the nearest cluster center. 3) The cluster
centers of each cluster are updated. 4) Iteratively repeat steps 2 and 3 until
the cluster centers stabilize or reach the maximum number of iterations.

Figure 4: We validate our method on the COCO dataset and present the results
of its visualization (in the visualization results we remove the boxes with
too low confidence). It can be clearly seen that our method can effectively
localize more target objects than the standard Faster R-CNN. Compared with
OLN-Box, our method is more accurate in locating known classes.

## Experiments

### Datasets

The datasets we mainly used are (1) the Pascal VOC 2007 dataset (Everingham et
al. 2010) contains 10k images with 20 labeled categories. The dataset is
mainly focused on classification and detection tasks for the targets. (2) The
COCO 2014 dataset (Lin et al. 2014) contains 80 annotated categories with 80k
images in the training set and 5k images in the validation set.

In our experiments, we consider the 20 categories in the VOC dataset as known
categories for our model, while the remaining 60 categories in the COCO
dataset, which do not overlap with VOC, are treated as unknown categories to
represent unfamiliar images in the open world. We train our dual RPN using the
VOC dataset to provide prior knowledge to the target extractor. However, the
model cannot learn the remaining 60 unknown categories in advance.

Extending the model to handle these 60 unknown categories presents a
challenging problem. Firstly, the images in the COCO dataset exhibit greater
diversity and complexity compared to those in the VOC dataset. Each image in
COCO contains multiple categories of targets and a complex environment.
Secondly, replicating a real-world target detection setup is not feasible.
Although the VOC and COCO datasets have similar category distributions, the
COCO dataset visually encompasses all the labels of the 20 categories in VOC.
This allows for a comprehensive evaluation of the model’s ability to discover
new categories.

Figure 5: The impact of the two clustering methods on AuC with varying sample
sizes and total number of clusters.

### Experimental Metrics

We summarize the metrics used in our experiments.

Localization Metrics: We employ the CorLoc metric to evaluate the accuracy of
object localization. CorLoc (correct localization) (Cho et al. 2015) measures
the percentage of images where the intersection over union (IoU) between the
predicted bounding box and the ground truth bounding box is greater than 0.5.
The CorLoc metric assesses the ability of the RPN to accurately localize
objects but does not reflect the model’s capability to discover new
categories.

Discovery Metrics: Mean Average Precision (mAP) is a commonly used metric in
object detection to measure the accuracy of object detectors such as Faster
R-CNN and SSD (Liu et al. 2015). It calculates the average precision value
across different recall levels from 0 to 1. By computing mAP, we can evaluate
whether the model successfully detects the target objects. However, for the
clustering of unknown categories, we need a metric to assess the clustering
effect. Therefore, we utilize the area under the curve (AuC) mentioned in
(Doersch, Gupta, and Efros 2014) to indicate the purity and coverage of the
discovered objects. In (Doersch, Gupta, and Efros 2014), it was observed that
clusters with a coverage value below 0.5 are usually not target objects. Thus,
a higher AuC value indicates higher purity of the target objects in the
corresponding clusters, suggesting that the objects within the target clusters
are more likely to belong to the same class. Additionally, we report the
number of unknown classes discovered by the model to evaluate its
effectiveness in mining new classes in an open world. Together, these metrics
provide a comprehensive evaluation of the model’s performance in an open world
setting.

### Results and Analysis

We compared our method with DualMem (Rambhatla, Chellappa, and Shrivastava
2021), Vplow111https://rssaketh.github.io/project pages/obj disc new.html, OLN
(Kim et al. 2021). Vplow replaces the clustering method with K-means, while
the remaining steps are the same as DualMem. We also compared clustering with
80 categories and clustering with 1000 categories to demonstrate the
superiority of the over-clustering strategy. Since the K-means algorithm does
not scale well to large datasets like COCO, we randomly sampled 10,000
instances from all input instances and fed them into the model, then made
predictions on all images to obtain the final clustering results. In Table 2,
we report the AuC, the number of discovered unknown categories, and the CorLoc
localization metric on the COCO 2014 training set to evaluate the overall
performance of different methods in the large-scale setting. Since DualMem
does not provide open-source code, we reproduced its dual-memory mechanism
based on the description in the paper. From Table 1, we can see that our
method outperforms the baseline methods in all metrics under the same
settings.

For the localization metric, Vplow and DualMem both use Faster R-CNN to
extract object proposals from images, while OLN uses a class-agnostic detector
for object region extraction. From the data and Figure 4, we can observe that
all methods perform well in object localization. However, Vplow and DualMem
have biases in box extraction, performing much better in localizing known
categories than unknown categories, and there may be omissions and
misjudgments in localizing unknown categories. To address this issue, DualMem
introduces low-confidence proposals into the network’s input to improve
localization and clustering when the number of unknown categories increases.
Although this approach allows DualMem to discover more categories, other
metrics are significantly reduced (as DualMem does not have a specific cluster
number setting, we set the memory slots based on the clustering categories).
Overall, our proposed debiased classification method not only effectively
explores unknown categories but also improves the localization of known
categories. For the AuC metric, Vplow and DualMem use a DINO-initialized ViT
as the feature extractor for instances. Due to the severe clustering bias in
the instance localization of previous Vplow, the extracted proposals naturally
have similar features, resulting in purer clustering in K-means. Therefore,
compared to DualMem, Vplow performs better in terms of AuC.

Method (#cluster=1000) | AP | AP50
---|---|---
Faster R-CNN box + DINO feature | 1.6 | 4.8
Faster R-CNN + Contrastive feature | 1.9 | 5.2
OLN-Box + DINO feature | 1.5 | 4.0
OLN-Box + Contrastive feature | 1.5 | 4.2
DRM box + DINO feature | 3.4 | 7.7
DRM box + Contrastive feature | 8.7 | 20.19
Table 2: Compare the improvement in mAP values for novel category recognition
in object discovery on COCO test2014 for each module.

### Ablation Study

Analysis for mAP Table 2 presents the impact of using different methods at
different stages on the experimental results, with Minibatch K-means being the
unified clustering method. From Table 2, it can be seen that the effects of
using different detectors’ boxes as input proposals for object localization
are consistent with our expectations. The use of fused boxes as input
proposals significantly improves target localization. Additionally, the
baseline performs better for known categories in VOC, while replacing the
classification head yields poorer results for known categories in VOC but can
enhance the generalization ability for other unknown objects. For known
categories in VOC, the baseline performs poorly but shows improved generality
for other unknown objects. Using features extracted from contrastive learning
is also better for the model compared to using features extracted solely from
DINO, and the experiments demonstrate that our proposed module significantly
enhances the performance of the model.

Analysis for time of cluster Table 3 demonstrates the clustering time
performance of different clustering methods under varying numbers of clusters
and total sample sizes. The table reveals that for the K-means clustering
method, the clustering time significantly increases as the sample size grows,
and increasing the number of clusters also leads to a noticeable increase in
clustering time. On the other hand, for the Minibatch K-means clustering
method, it can significantly reduce the time cost of clustering while having a
minor impact on the clustering time with an increase in the number of clusters
and sample size.

Figure 5 shows the accuracy results of clustering methods with varying numbers
of clusters and sample sizes. The over-clustering method improves cluster
purity for similar clustering with the same sample size. Increasing the sample
size slightly enhances the AuC index with the same number of clusters.
Additionally, the Minibatch K-means method dynamically updates cluster centers
based on input instances, saving time compared to regular K-means and better
approximating complex real-world scenarios.

Method (#cluster) | Sample Size | Time (s)
---|---|---
K-means (80) | 10k | 16.371
K-means (80) | 50k | 127.162
K-means (80) | 100k | 209.706
K-means (1000) | 10k | 141.129
K-means (1000) | 50k | 675.414
K-means (1000) | 100k | 1864.456
Minibatch (80) | 10k | 3.316
Minibatch (80) | 50k | 3.661
Minibatch (80) | 100k | 3.997
Minibatch (1000) | 10k | 17.282
Minibatch (1000) | 50k | 23.436
Minibatch (1000) | 100k | 24.026
Table 3: Effect of different sample size and total number of clusters on
clustering time.

## Conclusion

In this paper, we propose a new region proposal named Debiased Region Mining
(DRM) and a Semi-Supervised Instance-level Contrastive Learning approach. In
the former, we use a dual RPN to extract the target objects in the image and
use DRM to process them, obtaining a box with accurate localization of the
known classes and good generalization to the unknown classes as the proposal.
In the latter, we employ semi-supervised Instance-based Contrastive Learning
to extract image features with better generalization and expressiveness. We
have conducted extensive experiments to validate our claims. The experiments
demonstrate that our approach currently outperforms other novel class mining
and localization algorithms in the open world. Our work provides an idea for
target detection in realistic and complex environments.

## Acknowledgements

This work was supported by National Key R&D Program of China (No.
2022ZD0119401), National Natural Science Foundation of China (No. 61925107,
U1936202, 62021002, 62301066), Key R&D Program of Xinjiang, China (No.
2022B01006), Zhejiang Provincial Natural Science Foundation of China under
Grant (No. LDT23F01013F01) and Tsinghua-OPPO JCFDT.

## References

  * Alexe, Deselaers, and Ferrari (2012) Alexe, B.; Deselaers, T.; and Ferrari, V. 2012.  Measuring the Objectness of Image Windows.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 34(11): 2189–2202.
  * Bendale and Boult (2014) Bendale, A.; and Boult, T. E. 2014.  Towards Open World Recognition.  _CoRR_ , abs/1412.5687.
  * Cho et al. (2015) Cho, M.; Kwak, S.; Schmid, C.; and Ponce, J. 2015.  Unsupervised Object Discovery and Localization in the Wild: Part-based Matching with Bottom-up Region Proposals.  _CoRR_ , abs/1501.06170.
  * Dhamija et al. (2020) Dhamija, A. R.; Günther, M.; Ventura, J.; and Boult, T. E. 2020.  The Overlooked Elephant of Object Detection: Open Set.  In _2020 IEEE Winter Conference on Applications of Computer Vision (WACV)_ , 1010–1019.
  * Doersch, Gupta, and Efros (2014) Doersch, C.; Gupta, A.; and Efros, A. A. 2014.  Context as Supervisory Signal: Discovering Objects with Predictable Context.  In _European Conference on Computer Vision (ECCV)_ , 362–377. Springer.
  * Everingham et al. (2010) Everingham, M.; Van Gool, L.; Williams, C. K.; Winn, J.; and Zisserman, A. 2010.  The pascal visual object classes (voc) challenge.  _International journal of computer vision_ , 88(2): 303–338.
  * Girshick (2015) Girshick, R. B. 2015.  Fast R-CNN.  _CoRR_ , abs/1504.08083.
  * Girshick et al. (2013) Girshick, R. B.; Donahue, J.; Darrell, T.; and Malik, J. 2013.  Rich feature hierarchies for accurate object detection and semantic segmentation.  _CoRR_ , abs/1311.2524.
  * Gu et al. (2021) Gu, X.; Lin, T.; Kuo, W.; and Cui, Y. 2021.  Zero-Shot Detection via Vision and Language Knowledge Distillation.  _CoRR_ , abs/2104.13921.
  * Guo et al. (2022) Guo, Y.; He, Y.; Lyu, J.; Zhou, Z.; Yang, D.; Ma, L.; Tan, H.-t.; Chen, C.; Zhang, W.; Hu, J.; et al. 2022.  Deep learning with weak annotation from diagnosis reports for detection of multiple head disorders: a prospective, multicentre study.  _The Lancet Digital Health_ , 4(8): e584–e593.
  * Han et al. (2020) Han, K.; Rebuffi, S.-A.; Ehrhardt, S.; Vedaldi, A.; and Zisserman, A. 2020.  Automatically discovering and learning new visual categories with ranking statistics.  _arXiv preprint arXiv:2002.05714_.
  * Han et al. (2021) Han, K.; Rebuffi, S.-A.; Ehrhardt, S.; Vedaldi, A.; and Zisserman, A. 2021.  Autonovel: Automatically discovering and learning novel visual categories.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 44(10): 6767–6781.
  * Han, Vedaldi, and Zisserman (2019) Han, K.; Vedaldi, A.; and Zisserman, A. 2019.  Learning to discover novel visual categories via deep transfer clustering.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 8401–8409.
  * He et al. (2022) He, T.; Shen, L.; Guo, Y.; Ding, G.; and Guo, Z. 2022.  SECRET: Self-Consistent Pseudo Label Refinement for Unsupervised Domain Adaptive Person Re-identification.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, 879–887.
  * Hsu, Lv, and Kira (2018) Hsu, Y.-C.; Lv, Z.; and Kira, Z. 2018.  Learning to cluster in order to transfer across domains and tasks.  _arXiv preprint arXiv:1711.10125_.
  * Jain, Scheirer, and Boult (2014) Jain, L. P.; Scheirer, W. J.; and Boult, T. E. 2014.  Multi-class open set recognition using probability of inclusion.  In _European Conference on Computer Vision_ , 393–409. Springer.
  * Joseph et al. (2021) Joseph, K. J.; Khan, S. H.; Khan, F. S.; and Balasubramanian, V. N. 2021.  Towards Open World Object Detection.  _CoRR_ , abs/2103.02603.
  * Kim et al. (2021) Kim, D.; Lin, T.; Angelova, A.; Kweon, I. S.; and Kuo, W. 2021.  Learning Open-World Object Proposals without Learning to Classify.  _CoRR_ , abs/2108.06753.
  * Lin et al. (2014) Lin, T.-Y.; Maire, M.; Belongie, S.; Hays, J.; Perona, P.; Ramanan, D.; Dollár, P.; and Zitnick, C. L. 2014.  Microsoft coco: Common objects in context.  In _European conference on computer vision_ , 740–755. Springer.
  * Liu et al. (2015) Liu, W.; Anguelov, D.; Erhan, D.; Szegedy, C.; Reed, S. E.; Fu, C.; and Berg, A. C. 2015.  SSD: Single Shot MultiBox Detector.  _CoRR_ , abs/1512.02325.
  * Rambhatla, Chellappa, and Shrivastava (2021) Rambhatla, S. S.; Chellappa, R.; and Shrivastava, A. 2021.  The Pursuit of Knowledge: Discovering and Localizing Novel Categories using Dual Memory.  _CoRR_ , abs/2105.01652.
  * Redmon et al. (2015) Redmon, J.; Divvala, S. K.; Girshick, R. B.; and Farhadi, A. 2015.  You Only Look Once: Unified, Real-Time Object Detection.  _CoRR_ , abs/1506.02640.
  * Ren et al. (2015) Ren, S.; He, K.; Girshick, R. B.; and Sun, J. 2015.  Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks.  _CoRR_ , abs/1506.01497.
  * Scheirer et al. (2012) Scheirer, W. J.; de Rezende Rocha, A.; Sapkota, A.; and Boult, T. E. 2012.  Toward open set recognition.  _IEEE transactions on pattern analysis and machine intelligence_ , 35(7): 1757–1772.
  * Zhao and Han (2021) Zhao, B.; and Han, K. 2021.  Novel visual category discovery with dual ranking statistics and mutual knowledge distillation.  _Advances in Neural Information Processing Systems_ , 34: 22982–22994.
  * Zhao et al. (2022) Zhao, X.; Liu, X.; Shen, Y.; Qiao, Y.; Ma, Y.; and Wang, D. 2022.  Revisiting Open World Object Detection.  _CoRR_ , abs/2201.00471.
  * Zhong et al. (2021) Zhong, Z.; Fini, E.; Roy, S.; Luo, Z.; Ricci, E.; and Sebe, N. 2021.  Neighborhood contrastive learning for novel class discovery.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 10867–10875.