Abstract: Graph similarity computation is a fundamental yet challenging task that reveals functional or behavioral similarities by quantifying the intrinsic structures and relational patterns of graph data. It plays a pivotal role in applications such as molecular structure alignment in bioinformatics, code plagiarism detection in software engineering, and community detection in social network analysis. Although methods based on Graph Neural Networks (GNN) offer effective approximations for classical metrics like Graph Edit Distance (GED), they often struggle to capture fine-grained topological relationships. This limitation constrains the representational capacity of learned graph embeddings, rendering them unable to adequately reflect structural discrepancies between graphs. To address this, this paper proposes a Graph Similarity Computation method based on Direct Structure Mining (DSM-GSC). At its core, the method constructs a product graph to explicitly model all potential node pairing relationships between two graphs. To overcome the limited representational capacity of traditional GNN embeddings, we introduce a structural learning module designed to identify and extract discriminative substructures—representing key topological correspondences—from the vast search space of the product graph. These structural patterns are subsequently utilized to guide the joint optimization of node alignment and similarity computation. This mechanism enables the model to break the reliance on global embeddings alone, achieving precise alignment driven by key structural patterns. Extensive experiments on multiple benchmark datasets demonstrate the unique advantages of the proposed method, verifying the feasibility and effectiveness of this new paradigm for graph similarity computation.

Key words: graph data, graph neural networks, graph similarity computation, graph structure learning