Similarity-Guided Structural Matching Learning for Graph Dataset Condensation

1 Introduction

Graph-structured data have become ubiquitous in modern machine learning applications [Gilmer et al., 2017], covering diverse fields such as social network analysis [Liu et al., 2021], bioinformatics [Fout et al., 2017; Huang et al., 2023], compound modeling, and recommendation systems [Fan et al., 2019; Ying et al., 2018]. These datasets encode complex relational patterns that are critical to advancing scientific and industrial applications. At the same time, as artificial intelligence advances, neural networks exhibit strong expressive power for graph data [Hamilton et al., 2017]. Therefore, Graph Neural Networks (GNNs) [Kipf and Welling, 2017;

Velickovic et al., 2018] have been proposed and rapidly developed. However, training GNNs isincreasingly challenging as dataset sizes have grown significantly in recent years [Wu et al., 2021; Bojchevski et al., 2020]. For example, the ogbgppa dataset [Hu et al., 2020] has 158,100 graphs, 243.4 nodes, and 2,266.1 edges on average.

Training high-performance GNNs [Yang et al., 2024] on such large real-world graphs requires substantial computational resources and time, which are unacceptable to many researchers. As a result, many graph condensation methods have been proposed, such as trajectory matching [Jin et al., 2022a; Gao et al., 2024], distribution matching [Zhao and Bilen, 2023], and kernel-based distillation [Xu et al., 2023]. They address this challenge by synthesizing a significantly smaller, highly informative set of graphs that preserves the essential structural and semantic information of the original large graph repository [Hashemi et al., 2024; Dai et al., 2019]. The ultimate goal is to enable GNNs trained on this small set of synthetic graphs to achieve performance comparable to that of GNNs trained on large-scale data [Lei and Tao, 2024; Khoshraftar and An, 2024].

Although existing condensation methods [Sun et al., 2024] have shown promise in reducing training costs, they often incur high memory costs in the condensing phase and fail to preserve the structural information in the original dataset.

and our method. The triplets in the figure represent the average degree, average number of triangles, and average clustering coefficient of each graph repository, respectively. We can see that the graph compressed by the current method retains almost no structural information. They primarily focus on optimizing the synthetic dataset by aligning the training gradients between the original large graph repository and the condensed graph set within each class [Jin et al., 2022a]. Although effective in preserving task-related characteristics, this core optimization strategy suffers from a critical limitation. It largely neglects crucial structural information during gradient matching, resulting in insufficient discrimination in the condensed graph set [Gao et al., 2025]. Therefore, these methods fail to explicitly encourage the condensed graph to learn representations from its structure that can effectively distinguish among different classes. This leads to insufficient discriminative power in the synthesized graph, hindering optimal performance on downstream tasks. This shortcoming becomes particularly pronounced when dealing with complex or large-scale graph repositories [Ma et al., 2025]. Therefore, how to condensate a large graph repository to higher quality while preserving structural information is becoming a major challenge in graph dataset condensation.

In this work, we propose a novel approach, Similarityguided Structural Matching Learning for Graph Dataset Condensation (SSGDC), that addresses these limitations. First, we develop a similarity-based mechanism that intelligently selects high-quality graph subsets from the original repository, identifying the most representative samples for structure matching. This selective approach ensures that the condensation process focuses on informative graphs rather than treating all samples equally. Second, we formulate a dual-objective optimization framework that combines gradient matching with structural preservation via Fused GromovWasserstein (FGW) alignment. This co-optimization strategy ensures that the condensed repository maintains both the training dynamics and structural characteristics of the original dataset. Moreover, our approach leverages GNNs for feature extraction and employs latent-space optimization to address the discrete nature of graph data. By optimizing in continuous latent spaces and decoding back to graph structures, our method overcomes the inherent challenges of directly optimizing the graph's discrete structure matrix while fully preserving structural integrity. This paper makes the following four major contributions:

• We introduce the novel framework for graph repository condensation that simultaneously addresses structural preservation and feature distillation through bi-level optimization in the latent space.
• We propose a novel similarity-based pruning mechanism that identifies high-quality graph subsets for targeting structure matching, improving the efficiency and effectiveness of the condensation process.
• We develop a dual-loss optimization strategy that combines gradient matching with FGW-based structural alignment, ensuring that condensed graphs preserve both task-relevant information and structural relationships.
• We conduct extensive experiments across multiple realworld graph repositories, demonstrating that our approach outperforms other methods across a range of condensation ratios and preserves structural information.

2 RelatedWork

Graph Condensation. For the condensation of large single graph datasets [Jin et al., 2022b], existing methods can be divided into three categories: trajectory matching, distribution matching, and gradient matching. Trajectory matching methods match the entire training trajectory of models trained on original and condensed data [Zheng et al., 2023; Zhang et al., 2024]. The distribution matching methods [Liu et al., 2022] align the feature distributions of the condensed and original data in a latent space [Liu et al., 2023]. Gradient matching methods [Yin et al., 2025; Fang et al., 2024] align training gradients between the original and condensed data, ensuring similar optimization behaviors [Jin et al., 2022b; Jin et al., 2022a]. However, these graph condensation methods, designed for single large networks, are often inadequate for multi-graph datasets, as their independent application to each graph fails to account for the critical dimension of intergraph relationships.

Condensation for the Graph Repository. Existing approaches can be broadly categorized into sampling-based methods [Peleg and Sch¨affer, 1989; Karger, 1994] and condensation-based [Loukas, 2019; Loukas and Vandergheynst, 2018] methods. They employ distinct strategies to reduce dataset size while preserving essential information for downstream tasks. Sampling-based approaches [Sener and Savarese, 2018a] represent the most straightforward compression strategy, selecting representative subsets from the original graph repository. Random sampling [Ribeiro and Towsley, 2010] serves as the simplest baseline, uniformly selecting graphs without considering their structural or feature characteristics. Herding methods [Welling, 2009] offer a more principled alternative by sequentially selecting samples that minimize the distance to the mean of all samples in the feature space. These approaches [Sener and Savarese, 2018b] fail to capture the diversity and representativeness of the original repository. Condensation-based methods [Liu et al., 2022; Zheng et al., 2023] represent a more sophisticated approach that generates synthetic graphs rather than simply selecting existing ones. DosCond [Jin et al., 2022a] was the first to apply gradient matching to graph dataset condensation, thereby extending the dataset condensation framework to graph-structured data repositories. KiDD [Xu et al., 2023] employs a kernel-based approach using graph neural tangent kernels (GNTK) to approximate the training behavior of GNNs. Mirage [Gupta et al., 2024; Liu et al., 2023] introduces a model-agnostic graph distillation framework based on frequent computational tree patterns. Their condensed graphs perform well on downstream tasks. However, they have critical limitations for graph repository condensation [Wang et al., 2024; Xiao et al., 2025] because they do not consider the structural information of the original graphs. Therefore, it remains difficult to improve the quality of compressed graphs.

3 Our Method

Figure 2 details the workflow of our proposed SSGDC method. First, we apply graph data pruning based on similarity to make the sizes of the original and compressed datasets more similar for subsequent structural information matching. Next, we introduce the module for generating condensed graphs. By weighting graph-embedding vectors with similarity scores, we obtain more informative graph representations, which are then reconstructed into graph structures via a decoder. Furthermore, we introduce structure informationmatching and gradient-matching modules, enabling the training process to effectively preserve both structural properties and task-discriminative information.

3.1 Similarity-based Graph Pruning

Prior to the formal training phase, we perform a pruning step to extract a representative subset from the original dataset. The size of this subset is designed to match the scale of the subsequently condensed dataset, thereby providing a properly scaled and information-rich sample foundation for structure matching. Because not all graphs contribute equally to the learning objective, some may contain redundant information, whereas others may serve as crucial exemplars of particular structural patterns or feature distributions. By leveraging the expressive power of multi-head linear layers, our method captures diverse aspects of graph importance across multiple representation subspaces, enabling a more effective pruning process than conventional approaches.

Given an original graph dataset G = {g1, g2, . . . , gN} where each graph gi = (Ai,Xi) consists of an adjacency matrix Ai ∈ Rni×ni and node feature matrix Xi ∈ Rni×d , we first obtain graph-level representations through a graph neural network encoder:

where hi ∈ Rdh is the graph embedding for Gi. The encoding process involves multiple layers of feature transformation and neighborhood aggregation, allowing the model to capture both local substructure patterns and global graph properties. We then apply a global pooling operation to aggregate nodelevel representations into a single graph-level embedding vector. These final graph embeddings serve as the input features for our similarity-based graph pruning module.

The core of our pruning module uses multi-head linear layers to compute graph similarity scores. For each head m ∈ 1, 2, . . . ,M, we first project the input graph embeddings into two distinct spaces. These projections are achieved through separate linear transformations, each with its own set of learnable parametersW:

where Wm 1 ,Wm 2 ∈ Rdh×dk are learnable projection matrices for head m, and dk = dh/M is the dimension per head. The vector H1 represents the current graphs for which we want to compute importance, while the vector H2 represents all graphs in the dataset that can be attended to. The similarity scores between graph i and graph j in head m can be computed as a scaled dot product of their representations:

where the similarity computation begins by measuring the compatibility between each vector pair through a scaled dotproduct operation. This produces raw similarity scores indicating how much focus each graph should place on each other graph in the dataset, from the perspective of the current similarity head. These raw scores are then normalized using the softmax function to create proper probability distributions that sum to one. We then obtain the similarity weights using softmax normalization, which can be expressed as:

The resulting similarity weights determine how much information from each graph's value vector to incorporate into the output representation for each target graph. The output for graph i from head m is computed as:

Following the independent similarity computations across all heads, we aggregate the outputs of the multiple similarity heads to form a comprehensive representation for each graph. The standard approach concatenates the output vectors from all heads and projects them through a final linear transformation. This aggregation step combines the diverse perspectives captured by different linear heads into a unified representation that encapsulates multiple facets of each graph's characteristics and its relationship to other graphs in the dataset:

whereWO ∈ RMdk×dh is the output projection matrix. The aggregated representations are subsequently fed into a scoring network that computes a scalar importance score for each graph. This scoring network consists of several fully connected layers with non-linear activation functions, followed by a final projection to a single-dimensional output. The importance scores quantitatively reflect the estimated value of each graph for the compression objective, with higher scores indicating that a graph contains more essential information to preserve during condensation:

where Ws ∈ Rds×dh , ws ∈ Rds , and σ is the sigmoid function. Then we need to select graphs with a higher score. We can clearly extract the graphs with higher similarity. Traditional top-k pruning operations are inherently non-differentiable, which would prevent gradient flow from the compression objectives back to the similarity parameters. We address this challenge by implementing a relaxed pruning mechanism that approximates the discrete top-k operation with a continuous, differentiable function. The pruning probability for each graph is defined as:

where τ is a temperature parameter that controls the smoothness of pruning. The final selected subset Gp is obtained by:

The pruning module outputs both the indices of selected graphs and their corresponding pruning weights, which can be used to weight each selected graph's influence during the subsequent gradient-matching phase. This differentiable formulation enables optimization of the similarity parameters with respect to the final compression quality, ensuring that the pruning criteria align with the overall learning objective.

3.2 Similarity-Guided Graph Aggregation and Generation

After obtaining the similarity matrix, we apply the derived similarity scores to weight the graph embedding vectors. Since it is not feasible to perform gradient descent directly on the adjacency matrix, we employ a GNN model fdecoder that captures the underlying structural distribution of the original graph. This approach ensures that the generated graph adheres to the distribution of real graph structures.

For each selected graph gk (k ∈ {1, 2, . . . , K}), we extract the corresponding similarity vector sk ∈ RN from the k-th row of the similarity matrix S. This similarity vector encodes the relative importance of each original graph with respect to the current selected graph gk. The aggregated embedding for the compressed graph corresponding to selected graph gk is computed by Equation 5. This weighted aggregation ensures that the compressed graph embedding zk captures the most relevant information from the entire dataset as determined by the similarity mechanism.

The aggregated embeddings Z = {z1, z2, . . . , zK} serve as the latent representations for the compressed graphs. Then we employ a graph decoder fdecoder : Rd → G that maps the compressed embeddings back to the graph domain. The reconstruction process involves generating both the adjacency structure and node features for each compressed graph. For a compressed graph embedding zk, the decoding operation is formalized as follows:

where ˆAk ∈ Rnc×nc is the reconstructed adjacency matrix and ˆXk ∈ Rnc×df represents the reconstructed node feature matrix for the compressed graph. Here, nc denotes the number of nodes in the compressed graph (typically smaller than the original graph), and df is the feature dimension. Since the decoder fdecoder has been trained to generate graphs that conform to the distribution of the original dataset, its parameter remains fixed throughout the process, ensuring that the reconstructed graph retains intra-graph information.

3.3 FGWMatching for Graph Repositories

After initializing the condensed dataset, we perform structure matching between it and a subset of the original dataset. To provide a foundational account of graph similarity, we adopt the structured data formalism proposed by Vayer et al. In this framework, a graph G is not only a set of nodes and edges but also a structured object that explicitly decouples feature and structural information. Formally, we define a graph G with N nodes as a triplet (A,X, h). X ∈ RN∗d is the matrix of all features, and A ∈ RN∗N is a matrix that encodes a notion of similarity between nodes. h = (h1, ..., hN) is a histogram that assigns an importance weight to each node. Without prior knowledge, uniform weights can be chosen so that h = 1N 1N. This representation provides a unified lens for viewing graphs as probability distributions over coupled featurestructure spaces, enabling comparison via optimal transport. The Wasserstein distance is well-suited for comparing features. Let G1 = (A1, X1, h1) and G2 = (A2, X2, h2) be two structured graphs. The Wasserstein distance can be formu-

where the coupling π ∈ Π(h1, h2) is a joint distribution, where πi,j indicates how much node i in G1 is matched to node j in G2. The coupling π that achieves the infimum is called the optimal transport plan. The GromovWasserstein distance is well-suited for comparing structures. Let C1 ∈ Rn×n , C2 ∈ Rm×m be the intra-graph structural distance matrices where C1(i, k) = dA(Ai1 ,Ak1 ) and C2(j, l) = dA(Aj2 ,Al2 ). The Gromov-Wasserstein distance can be formulated as follows:

The structure cost |C1(i, k) - C2(j, l)| punishes matching pairs of nodes (i, k) and (j, l) if the internal structural distance within G1 (C1(i, k)) differs from that within G2 (C2(j, l)). This ensures that, if two nodes are matched, their relational contexts within their respective graphs are similar.

While GW provides a powerful framework for comparing structures, it entirely ignores node-level features and attributes that may be present in the data. Therefore, in this case, we use the Fused Gromov-Wasserstein (FGW) distance to unify them, enabling a joint comparison.The FGW distance of order p, with trade-off parameter α ∈ [0, 1] and internal cost exponent q ≥ 1, is defined as:

where the parameter α plays a key role: it balances the trade-off between feature similarity and structural consistency. When α = 0, FGW reduces to the Wasserstein distance on features; when α = 1, it reduces to the GromovWasserstein distance on structures. Then the optimal transport plan π∗ provides a soft, semantic matching between the nodes of the two graphs, aligning them based on both their attributes and their relative positions within the graph topology.

In our compression task, we aim to ensure that the set of condensed graphs ˆ G is structurally and feature-wise representative of a high-quality subset Gp selected from the original data via a similarity mechanism. We define the FGW Structural Matching Loss as follows:

For each high-quality original graph gs in the attended subset Gp, we find its closest counterpart in the condensed set ˆ G based on the FGW distance. We then compute the average of these minimum distances over the entire subset Gp. This equation forces every condensed graph to represent a region of the original graph space, and ensures that every graph in Gp has a close representative in the condensed set. The use of FGW ensures that this representation is faithful with respect to both features and structure.

3.4 Gradient Matching for Graph Repository

Finally, we need to make the networks trained on the two repositories closer. Let Gp = {g1, g2, ..., gK} be the highquality subset selected by our similarity mechanism from the original graph collection, and let ˆ G = {ˆ g1, ˆ g2, ..., ˆ gM} be our compressed graph set with M ≪ K. For a given parameter initialization θ0, we define the gradient matching progress as:

where ∆ refers to the update step in gradient descent. The network trained by the synthetic graph repository can also have similar effects on the large repository. However, the overhead of directly matching network parameters is very high. Our approach aims to match the network parameters between large-real and small-synthetic training data by matching their gradients at each training step:

where ∇ is the gradient of the network's descent at the corresponding step, and µ is the learning rate. In this way, the training trajectory on the small synthetic graph repository DS can mimic that on the large real graph repository DO. The gradients matching process for GNN can be modeled as:

where ∇tDS represents the gradient of the repository DS at the t-th step of the network, and Dis is a function that calculates the distance between two gradients. This phase is designed to preserve critical inter-graph relational information. To achieve this, we use gradient matching to ensure that synthetic data produces model update directions equivalent to those of the original data in downstream task training.

4 Experiment

To evaluate the effectiveness of our approach, we implemented our framework on top of Pytorch (version 2.5.0). All experiments were carried out on a workstation with an Ubuntu operating system, an Intel i9-12900K CPU, 128GB of memory, and a NVIDIA GeForce RTX4090 GPU. In this section, we present comprehensive experiments designed to address the following four Research Questions (RQs).

RQ1 (Superiority) What benefits does SSGDC offer in comparison to state-of-the-art (SOTA) methods?

RQ2 (Effectiveness) Can SSGDC effectively condense a graph repository so that the condensed dataset exerts a similar impact on various GNNs as the original dataset?

RQ3 (Necessity) Do the separate modules in SSGDC each play distinct roles in improving the effectiveness of graph dataset condensation?

4.1 Experimental Settings

Datasets . We investigated five real-world graph classification datasets: NCI1 and DD from TUDataset [Morris et al., 2020], as well as ogbg-molhiv, ogbg-molbbbp, and ogbgmolbace from the Open Graph Benchmarks [Hu et al., 2020]. The statistics for these datasets are summarized in Table 1. For each dataset, the data are randomly split into training, validation, and test sets at 80/10/10%.

Baselines . To comprehensively evaluate the performance of our condensation method on the graph repository using the multiple-graphs approach, we compared it against a diverse set of baselines, including state-of-the-art methods in graph dataset condensation and sampling. The baselines are categorized as follows. For the condensation methods, we selected representative methods from each of the classic compression types. DosCond [Jin et al., 2022a] is a graph dataset condensation method based on gradient matching. KiDD [Xu et al., 2023] is based on kernel ridge regression. Mirage [Gupta et al., 2024] extracts frequent computational tree patterns. We consider several straightforward baselines: full-data training, random subsampling, and k-center.

Hyperparameter Settings . We configured the hyperparameters of the proposed condensation method on the graph repository using both the multiple-graphs strategy and the baseline methods. The main hyperparameter choices for our experiments are outlined below. For the condensation method, the number of condensed graphs per class was set to 1, 5, 10, 20, and 50. The learning rates for the structure and feature components were fixed at 0.001 and 0.0001, respectively, and we employed the Adam optimizer with a weight decay of 5 × 10-4 . During evaluation, we trained the same network for 1,000 epochs on the condensed graph using a learning rate of 0.001.

4.2 Comparison with State-of-the-Arts (RQ1)

To highlight the effectiveness of our approach, we performed extensive comparative experiments on graph classification tasks, benchmarking our method against existing graph condensation approaches and sampling strategies. The detailed results are summarized in Table 2. This table includes five commonly used graph classification datasets, ensuring a broad and diverse evaluation. For each dataset, we report the condensation rate, representing the fraction of the original data preserved after compression. Given identical condensation rates, we present the test accuracies obtained by six different graph condensation methods. For reference, we provide the test accuracy on the original, uncompressed datasets, which serves as an upper bound for performance comparison.

As presented in Table 2, our proposed method consistently surpasses all competing approaches in most experimental settings. On the NCI1 dataset, it yields substantial improvements over the strongest baseline (i.e., KiDD), with performance gains ranging from 3.34% to 5.46% across various compression ratios. On the Molecular Property Prediction datasets, our approach achieves the highest ROC-AUC scores across most compression ratios, with especially pronounced gains at GPC=50, where it clearly outperforms K-Center and other baselines. In contrast to methods whose performance deteriorates at certain compression levels, our technique exhibits robust, stable behavior across the full range from 1 to 50 graphs per class. Moreover, although a performance gap relative to training on the full dataset persists, our method substantially reduces this gap compared to prior approaches, achieving 85-95% of full-dataset performance at different compression ratios. For the overhead, our FGW matching is strictly constrained to the interaction between the heavily pruned subset (size K) and the condensed graph set (size Mc), bounding the time complexity to O(K·Mc ·V 2 c ·tFGW). Peak GPU memory usage is similarly capped by processing matching pairs in mini-batches. Because our similarity mechanism ensures that K ≪ N (original total graphs) and Mc are very small, the optimal transport problem remains highly tractable.

4.3 Test with Different GNNs (RQ2)

To evaluate the effectiveness of the proposed graph condensation method, we conducted experiments with diverse GNN architectures. These experiments aimed to verify whether the condensed graphs remain compatible with various GNN models and maintain high performance across different network architectures. We further investigated the transferability of task-specific information by assessing the performance of condensed graphs on previously unseen GNN architectures. The corresponding results are summarized in Table 4, which reports the test accuracy of synthetic repositories trained with a single GNN model and evaluated on different networks. Each section of the table corresponds to a specific GNN (e.g., GCN, GAT, or GraphSAGE) used for training, followed by the accuracy achieved by other GNN architectures on the same condensed data for the same task. The results demonstrate that the condensed repositories maintain consistently high accuracy across a range of test architectures, highlighting the broad effectiveness and transferability of our method with diverse GNN models.

From Table 4, we can find that the graphs condensed by DGCNN can be used to train the remaining networks well and achieve at least 65.05% in test accuracy. And graphs condensed by other networks can achieve 64.39% accuracy in training neural networks. Furthermore, the results reveal that regardless of the GNN used for condensation, the test accuracy of a given network differs by up to 1.16%. This highlights the robustness and effectiveness of condensed graphs, which facilitate training and testing across a diverse set of GNN models, making them a valuable tool for reducing repository size without sacrificing performance.

4.4 Ablation Study (RQ3)

To validate the importance of each core component in SSGDC, we performed extensive ablation experiments on multiple architectural variants. The results are summarized in Table 5, which systematically analyzes the contributions of two key modules in our method. For the similarity-based pruning module, we designed two different variants: one removed the similarity mechanism entirely and instead used random sampling to obtain a high-quality subset from the original graph collection. The other adopted a simplified similarity mechanism based solely on graph-level features, ignoring structural information. These experiments show that even a rudimentary similarity mechanism yields better performance than random pruning but still falls far short of our full similarity module, which integrates structural features. The evidence is clear: on both datasets, the Feature-level Similarity variant consistently surpasses the Random Sampling variant, yet its performance plateaus below that of our complete model, indicating that feature-only similarity is insufficient.

For the Fused Gromov-Wasserstein structural matching, we explored two alternative setups. In the first, we substituted the FGW distance with the standard Wasserstein distance, thereby matching only the feature distributions and disregarding structural preservation. In the second, we relied solely on the Gromov-Wasserstein term, emphasizing structural consistency while neglecting explicit feature alignment. These configurations enabled us to isolate and quantify the individual and joint contributions of feature and structure preservation during the condensation process. The results clearly demonstrate that the Wasserstein Distance variant (featureonly matching) generally outperforms the feature-similarity pruning baseline (w/o FGW), highlighting the value of distributional alignment, and the Gromov-Wasserstein variant (structure-only matching) consistently surpasses the Wasserstein variant, particularly on the NC11 dataset. This underscores that structural consistency is often more critical than feature alignment alone for graph data. However, neither isolated component reaches the performance of their fusion. Our full SSGDC method, using the full FGW distance, achieves the best results across all configurations. This definitive superiority validates the necessity and synergy of jointly preserving both feature and structural information through FGW.

5 Conclusion

In this paper, we propose a novel graph condensation framework that effectively addresses the critical limitation of structural information loss inherent in existing methods. Our approach integrates a similarity-based graph selector with a dual-objective loss function that combines gradient matching and Fused Gromov-Wasserstein (FGW) divergence. This integration enables the simultaneous preservation of taskrelevant informational content and the essential relational topology of the original graph repository. Extensive experiments demonstrate that our method consistently outperforms state-of-the-art baselines, achieving superior accuracy across a range of compression ratios and GNN architectures.

Acknowledgments

This work was supported by the Natural Science Foundation of China (No. 62272170). Mingsong Chen is the corresponding author (mschen@sei.ecnu.edu.cn).