Enhanced Graph Similarity Learning via Adaptive Multi-scale Feature Fusion

1 Introduction

Graph similarity computation is a fundamental task with diverse applications, including chemical molecular structure comparison, social network analysis, and code clone detection. In the chemical field, it aids in tasks like molecular activity prediction, drug discovery, and compound screening [Reiser et al., 2022; Herrera et al., 2024]. Social network analysis understands social dynamics and improves recommendation systems by comparing network structures [Wu et al., 2022; Du et al., 2020]. In the field of software engineering, it facilitates code optimization and maintenance by efficiently detecting code clones [Liu et al., 2023b; Zhang and Saber, 2024]. Its performance directly impacts downstream tasks such as molecular activity prediction, community dynamics analysis, and software optimization. However, the irregularity and complexity of graph data-characterized by diverse node and edge features as well as multi-scale structural dependencies-pose significant challenges for accurate and efficient similarity computation. Traditional methods and deep learning approaches each face unique limitations in this domain, motivating the need for novel solutions.

∗ Corresponding author

Traditional methods, such as graph isomorphism algorithms (e.g., VF2)[Wu et al., 2023] and approximate heuristic approaches (e.g., Graph Edit Distance, GED)[Blumenthal and Gamper, 2020], compute similarity based on graph structure. While graph isomorphism algorithms excel at exact matching, they suffer from high computational complexity and poor scalability to large-scale or attribute-rich graphs. Approximate methods like GED improve efficiency by estimating similarity via edit costs but struggle with noisy or heterogeneous graph data. Furthermore, these methods are often computationally prohibitive for large datasets and fail to capture subtle differences in complex graph structures due to their reliance on rigid matching criteria.

Deep learning-based methods, such as GCN[Bhatti et al., 2023], GAT[Dong et al., 2022], and GraphSAGE[Ding et al., 2021], have introduced a paradigm shift in graph similarity computation. These methods leverage the power of automatic feature learning to extract graph embeddings and capture complex associations between graph structures and node features. GCNs aggregate local information through convolutional operations, while GATs introduce attention mechanisms to adaptively assign weights to neighboring nodes. Despite these advances, existing deep learning methods still face three core challenges: (1)Inadequate multi-level feature fusion: Current methods often fail to integrate local and global structural features, leading to incomplete graph representations. (2)Limited robustness: Many models exhibit performance degradation when handling noisy, heterogeneous, or large-scale graphs[Liu et al., 2023c]. (3)Static fusion strategies: Methods relying on fixed feature fusion techniques (e.g., simple concatenation or weighted averaging) lack the adaptability needed to address the diverse characteristics of graph data[Ju et al., 2024].

To address these challenges, this paper proposes the Adaptive Multi-scale Feature Fusion (AMFF), a novel solution designed to enhance feature extraction, fusion, and similarity computation for complex graph data. The framework introduces three key components, each tailored to tackle a specific limitation:

(1)Residual Graph Neural Networks (R-GIN): By incorporating a residual mechanism, this module enhances multilayer feature representation, enabling the model to robustly capture both local and global structural dependencies while addressing gradient vanishing and over-smoothing issues.

(2)Multi-Pooling Attention Network: This module combines multi-scale feature aggregation with an attention mechanism to retain critical node information while minimizing information loss, ensuring a comprehensive representation of graph features.

(3)Adaptive Multi-scale Feature Fusion: A novel mechanism that dynamically adjusts attention weights based on interactions between node embeddings and graph embeddings, allowing for flexible and precise feature fusion. This approach improves the model's sensitivity and accuracy in similarity computation.

The proposed framework effectively bridges the gap between local and global information while ensuring robustness to complex graph data. Extensive experiments on benchmark datasets, including AIDS700nef, LINUX, IMDBMulti, and PTC, demonstrate that AMFF significantly outperforms existing methods across multiple metrics. These results highlight the efficiency and scalability of AMFF, establishing it as a promising solution for graph similarity computation tasks in diverse domains.

2 RelatedWork

2.1 Graph Representation Learning

Graph representation learning transforms the nodes, edges, and structures of a graph into low-dimensional embeddings that capture both structural and node-level features, supporting tasks such as node classification, graph classification, and graph similarity computation[Dong et al., 2020]. To handle large-scale graph data, graph embedding methods reduce computational complexity and enhance efficiency by automatically learning effective low-dimensional representations. These techniques can be broadly categorized into methods based on matrix decomposition, such as DeepWalk[Perozzi et al., 2014] and Metapath2Vec[Chen et al., 2023], and those based on deep neural networks, including GCN and GAT. In recent years, graph neural networks (GNNs), such as GCN, GAT, and GraphSAGE, have leveraged the message-passing mechanism to effectively capture local structural features of graphs, driving advancements in graph similarity computation. GNN-based methods evaluate inter-graph similarity by employing metrics like Euclidean distance or cosine similarity through graph embeddings that map node features into low-dimensional spaces. Additionally, models such as graph autoencoders (GAE)[Li et al., 2022a] and variational graph autoencoders (VGAE)[Kipf and Welling, 2016] further improve the efficiency of complex graph similarity evaluation through unsupervised learning.

2.2 Feature Fusion

Graph data contains a variety of complex features, and a single feature cannot fully describe the graph similarity[Wu et al., 2020]. Therefore, feature fusion is crucial in improving the accuracy and robustness of graph similarity computation. Graph data usually has node-level and graph-level features, and multi-scale feature fusion can generate a more comprehensive graph representation. Traditional GCNs mainly aggregate local information and tend to ignore the global structure. To enhance global perception, commonly employed feature fusion methods include weighted summation, concatenation and attention mechanism. Notably, models leveraging the attention mechanism can dynamically adjust feature weights, thereby optimizing the fusion effect. In recent years, methods such as multimodal graph embedding [Islam et al., 2023] and graph self-attention mechanism [Wu and Zhou, 2025] have further enhanced the feature fusion capability. However, feature fusion still faces challenges, such as information distortion due to differences in feature size and distribution, as well as computational efficiency and memory issues in large-scale graph data processing.

3 ProblemFormulation

Graph similarity computation aims to quantify the similarity between two graphs based on their structural and feature-level characteristics. A graph is defined as G = (V, E), where V is the set of nodes, E is the set of edges, and n = |V | is the number of nodes. We focus on undirected, unweighted graphs. The structural information is represented by the adjacency matrix A ∈ Rn×n , and the node features by the feature matrix X ∈ Rn×d , where d is the feature dimensionality.

Given a reference dataset D = {G1,G2, . . . ,Gm} and a query set Q = {Q1, Q2, . . . , Qk}, the goal is to define a similarity function s that assigns a normalized score Sij ∈ [0, 1] to each graph pair (Gi, Qj):

Here, the function s takes as input the Cartesian product D×Q of sets D and Q, which represents pairs of graphs from the datasetsDandQ. It outputs a scorewithin the range [0,1], where a score closer to 1 indicates high similarity between the graphs, and a score closer to 0 indicates dissimilarity.

4 Adaptive Multi-scale Feature Fusion for Graph Similarity Learning

To overcome the limitations existing in the current graph similarity computation, this paper proposes the AMFF framework shown in Fig. 1. The framework aims to achieve more efficient and accurate graph similarity assessment through deep feature extraction and adaptive multi-scale feature fusion techniques. In the following, the implementation details of the AMFF model are described in detail, including three parts: node feature extraction, multi-pooling attention network, and adaptive multi-scale feature fusion module.

4.1 Node Feature Extraction

In the AMFF framework, node feature extraction is a fundamental step in computing graph similarity. Inspired by the residual connectivity mechanism in Residual Neural Networks[Li et al., 2022b; Amelio et al., 2023], we design a novel Residual Graph Neural Network (R-GIN) for efficiently extracting node features and enhancing the stability of the model in complex graph structures. The input of the module consists of an adjacency matrix A and a node feature matrix X, where X uses a unique thermally encoded vector to represent the features of each node. The R-GIN enhances the model's learning capability by adapting the residual connectivity mechanism to graph convolutional layers. The output dimensions of the three R-GIN layers are 64, 32 and 16, respectively.

The first two layers aggregate the features of neighbouring nodes through graph convolution operations:

where X is the input node feature matrix, and A represents the adjacency matrix (or edge index). To effectively combine information frommultiple layers, the output of the first layer (H(1) ) is transformed using a linear operation and fused with the output of the second layer (H(2) ) via residual joins:

where Linear(·) is a linear transformation. This feature fusion strategy preserves the information from earlier layers and seamlessly integrates it into deeper features.

Finally, the fused features are passed through the third layer of the graph isomorphism network to generate the final node embeddings:

where un denotes the embedding vector of the n-th node. With this multi-layer design, the model is able to effectively capture shallow and deep node representations, while residual joins alleviate problems such as over-smoothing or gradient vanishing, and improve feature quality. These high-quality node features are subsequently used in downstream similarity assessment tasks.

4.2 Multi-Pooling Attention Network

Traditional pooling methods, such as average pooling (Pavg) and maximum pooling (Pmax), generate graph-level representations by aggregating node features, but may lose important information or pay excessive attention to extreme values[Woo et al., 2018; Liu et al., 2023a]. To address these issues, we design the Multi-Pooling Attention Network (MPA), which combines multi-pooling and attention mechanisms to dynamically adjust node contributions to the graph-level representation.

First, the module extracts global features and locally salient features of the graph through average pooling and maximum pooling:

where Pavg and Pmax are defined as:

Here, Pavg captures the overall distribution of features, and Pmax identifies the most salient features. u(i) n denotes the feature vector of the i-th node of graph g, N is the total number of nodes, and ⊕ represents the concatenation operation, which combines the results of the two pooling strategies.

The pooling results are then nonlinearly transformed by a multilayer perceptron (MLP)[Gardner and Dorling, 1998] to generate a more expressive global feature representation:

Next, the attention weights are computed, the global features are interacted with each node feature, and the node features are adjusted by weighting to finally generate a graphlevel representation, see Eq.9:

where σ is an activation function, W denotes a learnable weight matrix.

MPA combines global pooling with a local attention mechanism to enhance the robustness of graph-level representations, which plays an important role in graph similarity computation in the AMFF framework.

4.3 Adaptive Multi-scale Feature FusionModule

In order to further enhance the model's ability to assess graph similarity, the AMFF framework introduces an adaptive multi-scale feature fusion module. This module is divided into two parts: node-graph feature interaction and graph-level feature interaction.

Node-Graph Adaptive Feature Fusion(NGFusion)

The node-graph adaptive feature fusion module aims at the weighted fusion of node embedding and graph embedding information by means of an adaptive attention mechanism and generates a comprehensive representation for calculating similarity. This module mainly consists of the following steps:

For the input node embedding un and batch index, each batch of nodes is embedded into a graph-level node representation using a weighted aggregation operation.

where f is an aggregation function used to summarise dispersed node information into a graph-level representation by batch index. After splicing the node embeddings with the graph embeddings, the attention weights are generated by a linear transformation.

The node features are weighted using the attention weights α(i) to obtain an updated node representation. After splicing the weighted node embeddings with the graph embeddings again, the integrated graph-level features are generated by MLP:

where ⊙ is element-wise Multiplication.

Ultimately, the similarity of the composite features h(i) f usion and h(j) fusion of a graph pair is quantified by the Euclidean distance metric in the pairwise distance function, see Eq.13:

where d denotes the dimension of the embedding vector, and h(i) fusion,k and h(j) fusion,k are the components of the fusion features of the graphs gi and gj in the k-th dimension, respectively.

NGFusion enables the capture of global interaction features of nodes with the graph and weights and integrates them to make the generated graph-level representation more robust and informative, thus improving the accuracy of similarity computation.

Graph-Level Adaptive Feature Fusion (GLFusion)

The graph-level adaptive feature fusion module combines weighted differences and cosine similarities of graph embeddings to capture key relationships between graph pairs. This design, based on GSLSim [Zou et al., 2025], enhances the feature representation of graph embeddings for a more thorough understanding of graph relationships.

GLFusion first computes the weighted differences between the graph pair embeddings:

where ∆h represents the weighted feature differences that highlight dissimilarities between graph embeddings, h(i) g and h(j) g are the graph-level embeddings of the input graphs, and W is a learnable tensor weight matrix used to enhance feature interactions.

The cosine similarity is then computed to evaluate the directional alignment between the two graph embeddings in a normalized vector space:

Finally, the graph similarity score is obtained by integrating the weighted differences and cosine similarity:

where σ is the relu activation function, ⊙ denotes elementwise multiplication, and b is a bias vector.

By combining graph embedding disparities and alignments, GLFusion effectively captures both differences and similarities between graph pairs, thereby improving the accuracy and robustness of graph similarity computation.

4.4 Similarity Score Calculation

The model combines node-graph and graph-level adaptive information to derive representative similarity features. First, the node-graph adaptive fusion score sNG and the graph-level adaptive fusion score sGL are concatenated to form a unified feature representation. These features are then passed through a fully connected layer to compute the final similar-

where p(gi, gj) is the predicted similarity score, ⊕ denotes the concatenation operation, and FC represents the fully connected layer.

Algorithm 1 The Algorithm of AMFF.

Input: Node features X, adjacency matrix A

Output: Graph similarity score p(gi, gj)

• 1: Step 1: Node embedding generation
• 2: for l = 1, 2 do
• 3: Update node embeddings using Eq.(2).
• 4: end for
• 5: Perform dense feature fusion H(dense) using Eq.(3).
• 6: Generate final node embeddings un using Eq. (4).
• 7: Step 2: Graph-level embedding generation
• 8: Performmulti-pooling using Eq.(5-8).
• 9: Generate graph embeddings hg using Eq.(9).
• 10: Step 3: Adaptive multi-scale feature fusion
• 11: for Each graph pair (gi, gj) do
• 12: Enter u(i) n , u(j) n , h(i) g and h(j) g into NGFusion and calculate score sNG using Eq. (13).
• 13: Input h(i) g , h(j) g into GLFusion and compute score sGL by Eq.(16).
• 14: end for
• 15: Step 4: Similarity score calculation
• 16: Final prediction score p(gi, gj) using Eq.(17).
• 17: Step 5: Loss calculation
• 18: Compute loss L using Eq.(18).
• 19: Ground truth similarity t(gi, gj) using Eq.(19).

To optimize the model, the error between the predicted similarity score and the true similarity score is minimized using the Mean Squared Error (MSE) loss function:

where N is the total number of graph pairs in the training set. The true similarity score t(gi, gj) is computed based on the normalized Graph Edit Distance (GED) as follows:

Here, λ represents an exponential function, dGED(·) is the Graph Edit Distance function [Riesen et al., 2013], and |gi|, |gj| are the number of nodes in graph gi and gj, respectively. The comprehensive training methodology for the introduced approach is outlined in Algorithm 1.

5 Experiment

5.1 Datasets

AIDS700nef, 700 chemical graphs with 2-10 atoms (C, O, H) and bonds, suitable for small-scale molecular similarity tasks. LINUX, 1000 hierarchical file system graphs with 410 nodes (files/folders) and parent-child edges, ideal for testing tree-structured GNNs. IMDBMulti, 1500 movie social networks with 4-89 actor nodes and co-occurrence edges, labeled with 29 genres (e.g., action, comedy) for graph similarity and classification. PTC, 344 chemical graphs with 2-109 atoms and bonds, labeled with 19 toxicity or chemical properties, benchmark for complex molecular graph processing.

5.2 Baselines

We compare our model with traditional GED methods (A*-beam search[Neuhaus et al., 2006], Hungarian algorithm[Kuhn, 1955], VJ algorithm[Fankhauser et al., 2011]) and neural network baseline methods: SimGNN[Bai et al., 2019], combines graph-level embeddings and nodelevel attention for similarity computation. GraphSim[Bai et al., 2020], directly matches two sets of node embeddings without relying on fixed graph-level representations. GENN[Wang et al., 2021], combines traditional search with learned embeddings to efficiently solve GED. MGMN[Ling et al., 2021], integrates node-graph and global graph interactions to enhance performance and robustness. H2MN[Zhang et al., 2021], transforms graphs into hypergraphs, enabling high-order representations and multi-perspective subgraph matching. NA-GSL[Tan et al., 2023], uses multiple attention mechanisms for node embeddings, interaction modeling, and similarity prediction. CLSim[Zou et al., 2025], aligns graph pair features via attention, aggregates node features, and integrates node-level and graph-level embeddings for detailed interaction modeling.

5.3 EvaluationMetrics

To comprehensively measure the model's performance, we employ the following evaluation metrics: (1) Mean Squared Error (MSE) quantifies the deviation between predicted and ground truth values, providing an intuitive measure of prediction accuracy. (2) Spearman's Rank Correlation Coefficient (ρ)[Spearman, 1961] and Kendall's Rank Correlation Coefficient (τ)[Kendall, 1938] assess the consistency between predicted and true rankings. These metrics are crucial for evaluating the model's performance on ranking tasks. (3) kAccuracy (p@k) evaluates the overlap between the top-k predicted results and the top-k ground truth results, reflecting the model's ability to identify relevant items in recommendation or retrieval tasks. These formulas are calculated as follows:

• p@k = |Top-k(ˆ y)∩Top-k(y)| k

where n is the total number of samples, ˆ yi and yi are the predicted and true values for the i-th sample, and di is the difference between their ranks. C and D denote concordant and discordant pairs, and (n2 ) is the total number of pairwise comparisons. Top-k(ˆ y) and Top-k(y) are the top-k predicted and ground truth results, respectively, with k set to 10 and 20 in this study.

5.4 Effectiveness

We conducted experiments on simple (AIDS700nef, LINUX) and complex (IMDBMulti, PTC) graph-structured datasets to validate the model. The experimental results are clearly presented in Table 1, showing that AMFF performs well on all datasets. Specifically, it outperforms traditional GED methods and deep learning methods in terms of accuracy and error metrics. On simple graph-structured datasets, AMFF shows excellent adaptability and efficiency. For complex graph-structured datasets, the model maintains leading performance, fully demonstrating its ability to handle complex graph structures. It is worth noting that some baseline methods (e.g., GENN and NA-GSL) fail to run due to excessive memory when processing complex datasets, while AMFF runs smoothly, which further highlights its storage efficiency and computational stability. In conclusion, the robust performance of AMFF on both simple and complex graphstructured datasets confirms its wide applicability. The model has made great strides in balancing complexity and computational efficiency, highlighting its potential and advantages in graph similarity computation tasks.

5.5 Efficiency

As shown in Fig. 2, AMFF shows strong performance on various datasets in the efficiency analysis. On simple datasets (Linux, AIDS700nef), its running time is comparable to SimGNN and GraphSim, and better than GENN and MGMN. on complex datasets (IMDBMulti, PTC), AMFF outperforms GENN and NA-GSL, and is more efficient than H2MN on PTC, and comparable to CLSim. It is worth noting that AMFF successfully handles all datasets, while some do not, highlighting its stability and reliability in handling graphs of varying complexity.

5.6 Ablation Study

GNN selection in node feature extraction module

Node feature extraction is crucial for improving model performance. To this end, we compare the performance of several mainstream GNN models (GCN [Bhatti et al., 2023], GAT [Vrahatis et al., 2024], GraphSAGE [Bhatkar et al., 2023] and GIN [Liao et al., 2024]) on the same benchmark dataset (see Table 2). The experimental results show that RGIN performs best on the AIDS700nef and LINUX datasets, especially on the MSE and ρ metrics, demonstrating strong feature extraction capabilities. While on the IMDBMulti and PTC datasets, GCN and two-layer GIN slightly dominate in some metrics (e.g., MSE and p@10). Overall, R-GIN and GIN family perform particularly well in graph structure learning and ranking accuracy.

Impact of individual modules on overall performance

This experiment evaluates the impact of each component in the AMFF framework on model performance, and observes its performance changes on the PTC dataset by gradually disabling the module, see Table 3. The conclusions are summarised as follows: (1) R: after disabling, the feature learning ability decreases and the model accuracy and ranking relevance are slightly affected, which verifies the importance of the residual mechanism on the model performance. (2) MP: the significantly increased error and performance degradation indicate that this module is crucial in capturing multi-scale features. (3) GL: its removal has the largest negative impact on performance, indicating the critical role of graph-level feature fusion in integrating global features. (4) NG: the model accuracy decreases after its disabling, demonstrating the importance of node and graph feature fusion in improving accuracy and robustness. (5) Dis : a slight decrease in performance after removal, showing its positive role in feature fusion. In summary, the best model performance is achieved when all modules are enabled, indicating that these components complement each other in graph similarity computation, and together improve the accuracy and robustness of the model.

5.7 Case Study

Randomly select query graphs in the test set, pair them with all graphs in the training set to generate graph pairs and calculate similarity scores. By sorting, ideally, the true matching graphs of the Query Graph should be ranked top. In order to analyse the model performance intuitively, we designed a visual display (see Fig. 3). For clarity, only the top two query graphs are displayed for each dataset. Each case includes: (1) Real matching results (top): the query graph and its true matching graph set, annotated with real similarity scores ranging from 0 to 1 (where values closer to 1 indicate higher similarity); and (2) Predicted matching results (bottom): the query graph and the most relevant graphs predicted by the model, ordered by ranking and annotated with the predicted rankings. This case study demonstrates the model's applicability across various graph similarity tasks and its ability to handle different data scenarios effectively. The alignment between the predicted and real rankings further underscores the model's robustness and accuracy in graph similarity computation.

IMDBMulti

Figure 3: Case study.

6 Conclusion

In this paper, a graph similarity computation framework based on adaptive multi-scale feature fusion (AMFF) is proposed to solve the similarity assessment and feature extraction problems of existing models in complex graph structures. By introducing the residual mechanism and multi-pooling attention mechanism, the feature expression ability and feature aggregation effect are enhanced. Meanwhile, the proposed adaptive feature enhancement fusion strategy dynamically adjusts the attention weights of node embeddings and graph embeddings, which significantly improves the model's sensitivity to graph similarity and computational accuracy. Experimental results show that the framework exhibits significant performance enhancement on multiple datasets, verifying its efficiency and wide applicability.

Acknowledgments

The work is supported partly by the Project of Guangxi Science and Technology (2025GXNSFFA069015), National Natural Science Foundation of China (No. 62372119, 62166003), the Key Lab of Education Blockchain and Intelligent Technology, Ministry of Education(No. EBME24-03), Open Research Fund of Guangxi Key Lab of Human-machine Interaction and Intelligent Decision (No.GXHIID2206), Innovation Project of Guangxi Graduate Education (JGY2024080, JGY2022046), the Guangxi Collaborative Innovation Center of Multi-Source Information Integration, Innovation Project of Guangxi Graduate Education (YCSW2025220).