---
_id: '18213'
abstract:
- lang: eng
  text: "What is the best way to match the nodes of two graphs? This graph alignment
    problem generalizes graph isomorphism and arises in applications from social network
    analysis to bioinformatics. Some solutions assume that auxiliary information on
    known matches or node or edge attributes is available, or utilize arbitrary graph
    features. Such methods fare poorly in the pure form of the problem, in which only
    graph structures are given. Other proposals translate the problem to one of aligning
    node embeddings, yet, by doing so, provide only a single-scale view of the graph.\r\nIn
    this article, we transfer the shape-analysis concept of functional maps from the
    continuous to the discrete case, and treat the graph alignment problem as a special
    case of the problem of finding a mapping between functions on graphs. We present
    GRASP, a method that first establishes a correspondence between functions derived
    from Laplacian matrix eigenvectors, which capture multiscale structural characteristics,
    and then exploits this correspondence to align nodes. We enhance the basic form
    of GRASP by altering two of its components, namely the embedding method and the
    assignment procedure it employs, leveraging its modular, hence adaptable design.
    Our experimental study, featuring noise levels higher than anything used in previous
    studies, shows that the enhanced form of GRASP outperforms scalable state-of-the-art
    methods for graph alignment across noise levels and graph types, and performs
    competitively with respect to the best non-scalable ones. We include in our study
    another modular graph alignment algorithm, CONE, which is also adaptable thanks
    to its modular nature, and show it can manage graphs with skewed power-law degree
    distributions."
article_number: '50'
article_processing_charge: No
article_type: original
author:
- first_name: Judith
  full_name: Hermanns, Judith
  last_name: Hermanns
- first_name: Konstantinos
  full_name: Skitsas, Konstantinos
  last_name: Skitsas
- first_name: Anton
  full_name: Tsitsulin, Anton
  last_name: Tsitsulin
- first_name: Marina
  full_name: Munkhoeva, Marina
  last_name: Munkhoeva
- first_name: Alexander
  full_name: Kyster, Alexander
  last_name: Kyster
- first_name: Simon
  full_name: Nielsen, Simon
  last_name: Nielsen
- first_name: Alexander
  full_name: Bronstein, Alexander
  id: 58f3726e-7cba-11ef-ad8b-e6e8cb3904e6
  last_name: Bronstein
  orcid: 0000-0001-9699-8730
- first_name: Davide
  full_name: Mottin, Davide
  last_name: Mottin
- first_name: Panagiotis
  full_name: Karras, Panagiotis
  last_name: Karras
citation:
  ama: 'Hermanns J, Skitsas K, Tsitsulin A, et al. GRASP: Scalable graph alignment
    by spectral corresponding functions. <i>ACM Transactions on Knowledge Discovery
    from Data</i>. 2023;17(4). doi:<a href="https://doi.org/10.1145/3561058">10.1145/3561058</a>'
  apa: 'Hermanns, J., Skitsas, K., Tsitsulin, A., Munkhoeva, M., Kyster, A., Nielsen,
    S., … Karras, P. (2023). GRASP: Scalable graph alignment by spectral corresponding
    functions. <i>ACM Transactions on Knowledge Discovery from Data</i>. Association
    for Computing Machinery. <a href="https://doi.org/10.1145/3561058">https://doi.org/10.1145/3561058</a>'
  chicago: 'Hermanns, Judith, Konstantinos Skitsas, Anton Tsitsulin, Marina Munkhoeva,
    Alexander Kyster, Simon Nielsen, Alex M. Bronstein, Davide Mottin, and Panagiotis
    Karras. “GRASP: Scalable Graph Alignment by Spectral Corresponding Functions.”
    <i>ACM Transactions on Knowledge Discovery from Data</i>. Association for Computing
    Machinery, 2023. <a href="https://doi.org/10.1145/3561058">https://doi.org/10.1145/3561058</a>.'
  ieee: 'J. Hermanns <i>et al.</i>, “GRASP: Scalable graph alignment by spectral corresponding
    functions,” <i>ACM Transactions on Knowledge Discovery from Data</i>, vol. 17,
    no. 4. Association for Computing Machinery, 2023.'
  ista: 'Hermanns J, Skitsas K, Tsitsulin A, Munkhoeva M, Kyster A, Nielsen S, Bronstein
    AM, Mottin D, Karras P. 2023. GRASP: Scalable graph alignment by spectral corresponding
    functions. ACM Transactions on Knowledge Discovery from Data. 17(4), 50.'
  mla: 'Hermanns, Judith, et al. “GRASP: Scalable Graph Alignment by Spectral Corresponding
    Functions.” <i>ACM Transactions on Knowledge Discovery from Data</i>, vol. 17,
    no. 4, 50, Association for Computing Machinery, 2023, doi:<a href="https://doi.org/10.1145/3561058">10.1145/3561058</a>.'
  short: J. Hermanns, K. Skitsas, A. Tsitsulin, M. Munkhoeva, A. Kyster, S. Nielsen,
    A.M. Bronstein, D. Mottin, P. Karras, ACM Transactions on Knowledge Discovery
    from Data 17 (2023).
date_created: 2024-10-08T12:48:38Z
date_published: 2023-02-24T00:00:00Z
date_updated: 2024-10-09T11:24:50Z
day: '24'
doi: 10.1145/3561058
extern: '1'
intvolume: '        17'
issue: '4'
language:
- iso: eng
month: '02'
oa_version: None
publication: ACM Transactions on Knowledge Discovery from Data
publication_identifier:
  eissn:
  - 1556-472X
  issn:
  - 1556-4681
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'GRASP: Scalable graph alignment by spectral corresponding functions'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 17
year: '2023'
...