CoChat

Deep Learning Approaches for Similarity Computation: A Survey

Yang, Peilun, Wang, Hanchen, Yang, Jianye, Qian, Zhengping, Zhang, Ying, Lin, Xuemin · 2024 · IEEE Transactions on Knowledge and Data Engineering

The DOI matches its Crossref record; 121 of the 121 references it cites were found in a registry or an index.

Abstract

The requirement for appropriate ways to measure the similarity between data objects is a common but vital task in various domains, such as data mining, machine learning and so on. Driven by abundant real-world applications, many well-known similarity (distance) metrics are proposed to measure the pairwise similarity of data pairs, e.g., graph edit distance for graphs and dynamic time warping for time series. However, many similarity metrics suffer from the high time complexity. More specifically, most of the well-known similarity metrics often need quadratic time or even much more time to compute the ground truth similarity and some of them are proven to be NP-hard. With the development of deep learning techniques, there is an emerging research trend on the learning for similarity computation on various data types in the field of database (DB) and data mining, which is quite different with the metric learning studies in the machine learning (ML) literature. Specifically, the studies in the ML focus on the learning for semantic similarity in specific tasks, which is implicitly indicated by the training data, on the data in the feature space. While the studies in the DB literature usually consider the learning for well-defined similarity metrics (e.g., graph edit distance) on the data objects (e.g., graphs), such that it can benefit the similarity computation on data in terms of multiple aspects, such as computation time, metric quality and search heuristic, and the learned representation of data can also be naturally fed to downstream tasks. This survey paper provides a comprehensive review of similarity computation learning on several data types, including set, sequence and graph. Moreover, we first classify the learning-based approaches in terms of their learning target into three categories, i.e., similarity learning, cost matrix learning and search heuristic learning. Then we detail some representative approaches for each category on every data type, and analyze some key features that are utilized by these approaches. Finally, we discuss some challenges and future directions towards the learning for similarity learning on these data types.

Overview

Integrity signals

Registry

Crossref · 10.1109/tkde.2024.3422484

Cites

121 of 121 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Citations

Cites

Research works printed but not linked: 1

  1. Li, LES3: Learning-based exact set similarity search, 14, 2073

Cited by

See all 36

Metadata

Authors
Yang, P., Wang, H., Yang, J., Qian, Z., Zhang, Y., & Lin, X.
Affiliations
  • Zhejiang Lab (CN)
  • Zhejiang Gongshang University (CN)
  • Guangzhou University (CN)
  • Alibaba Group (China) (CN)
  • Shanghai Jiao Tong University (CN)
Venue
IEEE Transactions on Knowledge and Data Engineering
Published
2024-12
Volume
36
Issue
12
Pages
7893-7912
ISSN
  • 1041-4347 (ISSN-L)
  • 1558-2191
  • 2326-3865
OpenAlex
W4400275701
Cited by
28
References
117
Citations by year
2026: 7 · 2025: 18 · 2024: 3
FWCI
8.52
Type
journal article
Language
en
Open access
closed
Locations
IEEE Transactions on Knowledge and Data Engineering (publishedVersion)
Funders
  • Major Key Project of PCL (PCL2022A03)
  • Basic and Applied Basic Research Foundation of Guangdong Province (2023A1515011655)
  • Guangzhou Research Foundation (2023A03J0115)
Topics
  • Physical Sciences › Computer Science › Information Systems › Data Quality and Management
  • Physical Sciences › Computer Science › Information Systems › Advanced Database Systems and Queries
  • Physical Sciences › Computer Science › Information Systems › Data Management and Algorithms
Keywords
similarity measurement, metric learning, graph edit distance, dynamic time warping, set similarity, sequence similarity, graph similarity, pairwise similarity, NP-hardness, computational complexity

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.