Back to AI News
arxiv

Scaling Graph Similarity Learning with Graph Neural Networks

The paper addresses graph similarity computation, where exact Graph Edit Distance and Maximum Common Subgraph are NP-hard, and existing GNN approaches have mainly been tested on small graphs. It proposes FiLSim, a scalable GNN-based framework, and a sequential graph-editing strategy for constructing large-scale datasets with reliable GED labels. FiLSim is evaluated on four standard benchmarks and four newly created large-scale datasets, remaining accurate on graphs with more than 150,000 nodes where baselines run out of memory or fail to learn. It can score all test pairs within seconds on a single GPU.

AI Brief

It introduces a scalable GNN framework and large-scale labeled datasets for a computationally hard graph-learning task, offering useful evidence for researchers working on graph similarity at scale.

arXiv:2611.09805v1 Announce Type: cross 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.
Be the first to rate this article.

Comments & Questions (0)

Captcha
Please be respectful — let's keep the conversation friendly.

No comments yet

Be the first to comment!