Scaling Graph Similarity Learning with Graph Neural Networks
arXiv cs.AI · 7 Nov 2026, 03:55 AEST
Graph similarity computation is crucial for various applications but is computationally challenging due to NP-hard problems. The proposed FiLSim framework aims to enhance scalability in Graph Neural Networks for large-scale graph datasets while maintaining competitive performance.
Key facts
- 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.
- 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.
- 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.
- 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.
Read aloud
Graph similarity computation is crucial for various applications but is computationally challenging due to NP-hard problems. The proposed FiLSim framework aims to enhance scalability in Graph Neural Networks for large-scale graph datasets while maintaining competitive performance. 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. 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. 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. FiLSim remains accurate on graphs with more than one hundred fifty thousand nodes, where the baseline methods run out of memory or fail to learn, and scores all test pairs within seconds on a single G P U.
Sources in this cluster
- Scaling Graph Similarity Learning with Graph Neural Networks
arXiv cs.AI · 7 Nov 2026, 03:55 AEST