GED-Consistent Disentanglement of Aligned and Unaligned Substructures for Graph Similarity Learning

Abstract--Graph Similarity Computation (GSC) is a fundamental graph-related task where Graph Edit Distance (GED) serves as a prevalent metric. GED is determined by an optimal alignment between a pair of graphs that partitions each into aligned (zero-cost) and unaligned (cost-incurring) substructures. However, the solution for optimal alignment is intractable, motivating Graph Neural Network (GNN)-based GED approximations. Existing GNN-based GED approaches typically learn node embeddings for each graph and then aggregate pairwise node similarities to estimate the final similarity. Despite their effectiveness, we identify a fundamental mismatch between this prevalent node-centric matching paradigm and the core principles of GED. This discrepancy leads to two critical limitations: (1) a failure to capture the global structural correspondence for optimal alignment, and (2) a misattribution of edit costs by learning from spurious node-level signals. T o address these limitations, we propose GCGSim, a GED-consistent graph similarity learning framework that reformulates the GSC task from the perspective of graph-level matching and substructure-level edit costs. Specifically, we make three core technical contributions. First, we design a Graph-Node Cross Matching (GNCM) mechanism to learn pair-aware contextual-ized graph representations. Second, we introduce a principled Prior Similarity-Guided Disentanglement (PSGD) mechanism, justified by variational inference, to unsupervisedly separate graph representations into their aligned and unaligned substructures. Finally, we employ an Intra-Instance Replicate (IIR) consistency regularization to learn a canonical representation for the aligned substructures.