cs.LGNov 6, 2026

Scaling Graph Similarity Learning with Graph Neural Networks

Authors: Ahmet Tüzen, Helge Langseth, Kjetil Nørvåg

Organizations: Department of Computer Science, Norwegian University of Science and Technology, Trondheim, Norway.

Abstract

Graph similarity computation is an important task in graph mining with many real-world applications, such as chemical compound analysis, program dependence comparison, and social network analysis. The problem is computationally challenging: Graph Edit Distance (GED) and Maximum Common Subgraph (MCS), which quantify the distance between graphs and identify their largest shared subgraph, respectively, are NP-hard to compute exactly. To address these computational challenges, Graph Neural Networks (GNNs) have been applied to this problem. However, existing GNN-based approaches have primarily focused on small-scale graph datasets, while scalability to larger scales remains underexplored. In this work, we propose FiLSim, a scalable GNN-based framework, and investigate whether a simplified GNN pipeline can maintain competitive performance on standard benchmarks while scaling to large graphs. We additionally propose a sequential graph-editing strategy to construct large-scale graph datasets with reliable GED labels to evaluate scalability. The proposed framework is evaluated on four benchmark datasets and four newly created large-scale datasets, demonstrating its effectiveness and scalability. FiLSim remains accurate on graphs with more than 150{,}000 nodes, where the baseline methods run out of memory or fail to learn, and scores all test pairs within seconds on a single GPU.

Figures & tables

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Not All Neighbors Matter: Understanding the Impact of Graph Sparsification on GNN Pipelines

    Mar 7, 2026Yuhang Song, Naima Abrar Shami, Romaric Duvignau +1Graph SparsificationGraph Neural Networks

  2. Reforge: Low-Latency Distributed GNN Serving with Selective Embedding Recomputation

    Jan 15, 2025Geon-Woo Kim, Donghyun Kim, Jeongyoon Moon +5Efficient Neural Network InferenceGraph Neural Networks

  3. Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks

    Sep 25, 2026Siddhartha Shankar Das, Sai Karthik Navuluru, S M Ferdous +7Graph SparsificationGraph Neural Networks