A Survey on Graph Condensation

For any matrix, the symbol $\top,-,+$ represents the operations of transpose, inverse, and pseudoinverse, respectively. Consider $\mathcal{S}=\{\mathcal{G}_{1},\cdots,\mathcal{G}_{\eta}\}$ denote a dataset of $\eta$ graph(s), where $\eta\in\mathbb{N}$, $\mathcal{G}=\{\mathcal{V},\mathcal{E},{\bf A},{\bf X}\}$, $\mathcal{V}$ and $\mathcal{E}$ denotes the set of vertices (nodes) and edges, ${\bf A}\in\mathbb{R}^{N\times N}$ is the adjacency matrix, and ${\bf X}\in\mathbb{R}^{N\times d}$ represents the feature matrix. ${\bf L}_{\mathcal{G}}$ is the corresponding Laplacian matrix of $\mathcal{G}$. $\mathcal{Y}\in\{1,\cdots,C\}^{M}$ denotes the set of labels of the nodes or edges if $\eta=1$, or the label of graphs if $\eta>1$, $[\mathcal{Y}]\in\mathbb{N}^{M\times 1}$ be its vector form. The downstream tasks are specifically defined by $M=N$ for node classification, $M=N^{2}$ for link prediction, and $M=\eta$ for graph classification. $\operatorname{GNN}(;{\theta}_{\mathcal{S}}):\mathcal{S}\rightarrow\mathcal{Y}$ denotes the GNN parameterized with ${\theta}_{\mathcal{S}}$ was trained on dataset $\{\mathcal{S},\mathcal{Y}\}$.

Denote $\mathcal{S}_{c}=\{{\mathcal{G}_{c}}_{1},\cdots,{\mathcal{G}_{c}}_{\mu}\}$ a smaller dataset of $\mu$ graph(s), $\mu\leq\eta$, and $\mathcal{G}_{c}=\{\mathcal{V}^{\prime},\mathcal{E}^{\prime},{\bf A}^{\prime},{\bf X}^{\prime}\}$ where the first dimension of $\mathcal{V}^{\prime},{\bf A}^{\prime}$, and ${\bf X}^{\prime}$ are $N^{\prime}\left(N^{\prime}\ll N\right)$, $\mathcal{Y}^{\prime}\in\{1,\cdots,C\}^{M^{\prime}}$ be the labels of $\mathcal{G}_{c}$. The conventional definition of GC Gao et al. (2024) is to directly borrow the definition of the dataset distillation problem, considering graphs as input and output:

where $\mathcal{L}_{\text{cond }}$ is the optimization objective of condensation.

In contrast, we define Graph Condensation ($GC():\mathcal{S}\rightarrow\mathcal{S}_{c}$), a class of methods aimed to scaling large-scale graphs to smaller yet informative NEW ones. We call:

In this paper, we will focus on condensing a single graph, while methods for multiple will be briefly introduced. To ensure the condensed graphs are informative, their formulations are parameterized through an optimization process:

• •

  Condensation Objective $\mathcal{O}$ describes the loss of graph information, which is quantified by function $\phi$;

• •

  ${\bf W}$ is optimized by minimizing the objective $\mathcal{O}$.

• •

  The Formulation function $f()$ describes how we formulate the condense graphs, which is parameterized by ${\bf{W}}$;

The three steps for formulating condensed graphs correspond to the three steps in the GC workflow as illustrated in fig. 1. Under our definition, specifying what information to preserve, denoted as $\phi$, is crucial as the primary motivation is to reduce the scale of graph data while preserving sufficient information. The details of the optimization objectives be seen in section 3, and the formulations will be presented in section 4. We categorize current methods by the taxonomy of objectives and present the formulations of each in table 1.

These kinds of objectives can be formulated as: Get similar & smaller graph $\mathcal{G}_{c}$ from original graph $\mathcal{G}$, and the key is defining what are graph properties and how to evaluate the similarity between two graphs based on these properties. In this case, $\phi$ be graph property extractor, and $\mathcal{O}$ be the corresponding similarity/distance function. We further categorize these objectives into two categories: Spectral and Spacial, by the domain of extracted information. Specifically:

Since the ultimate objective is to achieve comparable performance via training models (include but not limited to GNNs) on smaller graphs $\mathcal{S}_{c}$, the models trained on the original graphs $\mathcal{S}$ can be useful. By expecting GNNs to achieve comparable results as those trained on the original dataset $\mathcal{S}$ through training on the condensed ones $\mathcal{S}_{c}$, we write:

where $\mathcal{L}$ is the task-specific loss (performance) function.

In this case, $\phi(\{\mathcal{G},\mathcal{Y}\})=\phi(\mathrm{Model}(;{\boldsymbol{\theta}_{\mathcal{G}}}))$, and $\mathcal{O}=D(\phi(\mathrm{Model}(;{\boldsymbol{\theta}_{\mathcal{G}_{c}}})),\phi(\mathrm{Model}(;{\boldsymbol{\theta}_{\mathcal{G}}})))$, $D$ is a distance function. We categorize all objectives that utilize such trained model as input as model-guided objectives. Specifically:

It is worth mentioning that the aforementioned two types of objectives are not mutually conflicting. Therefore, the third category named hybrid methods combines both the graph properties and model capabilities as guidance during condensation simultaneously. There are methods such as Yang et al. (2023); Gao et al. (2023); Liu et al. (2023a); Xu et al. (2023a) that optimize the condensed graph from both graph-guided and model-guided objectives. Specifically, Yang et al. (2023) simultaneously match the train trajectory between two models and the Laplacian Energy Distribution between two graphs, Gao et al. (2023) optimize the training trajectory loss and reconstruction loss together, Liu et al. (2022b) perform eigenbasis and training trajectory matching in the same time and Xu et al. (2023a) take the model predicted uncertainty and empirically verified useful graph properties to rank graph training instances for selection.

Three types of objectives, namely graph-guided, model-guided, and hybrid, each with its advantages and drawbacks: To produce ’similar’ condensed graphs, graph-guided objectives focus on preserving the properties of the original graph. This is suitable for applications that require retaining the patterns from original graphs. However, they are not guided by downstream tasks and hence may not be the optimal solution. On the other hand, the model-guided objectives aim to maintain the performance of the model by optimizing the condensed graph. These methods are driven by motivation-oriented optimization and thus perform exceptionally well in predefined scenarios. However, it may result in overfitting, reducing the adaptability of condensed graphs to other models or tasks. Hybrid methods combine the advantages of both graph-guided and model-guided approaches, intending to retain model performance while preserving graph properties for scenarios that value both graph property and model performance. However, balancing between the two objectives as well as optimizing them can be challenging.

In conclusion, the choice of the appropriate objective depends on the specific requirements of the application. Graph-guided is more suitable for tasks emphasizing graph structure, model-guided applies to scenarios emphasizing model performance, and the hybrid method seeks a balance between the two. Considering the goals of the task and the characteristics of the graph, selecting the most suitable method requires careful consideration in practical applications.

Modification approaches encompass actions such as node aggregation and deletion, etc., where the condensed graph is the product of modifying the original graph. This category of formulations can be uniformly formalized as aggregating nodes from $\mathcal{G}$ to $\mathcal{G}_{c}$. Assuming each node $v^{\prime}_{i}\in V^{\prime}$ is aggregated from $k$ nodes in $\mathcal{G}$, $k\in\mathbb{N}$, then the most common scheme, e.g., Loukas (2019); Deng et al. (2020); Jin et al. (2020); Huang et al. (2021); Ma and Chen (2021); Kumar et al. (2023); Dickens et al. (2023); Gao et al. (2023) did, was:

$P\in\mathbb{R}^{N\times N^{\prime}}$ is defined as a projection matrix, indicating that nodes $\mathcal{V}_{(i)}$ in $\mathcal{G}$ were aggregated to a new node $v^{\prime}_{i}$ in $\mathcal{G}_{c}$:

In a general definition, each row of ${\bf P}$ may contain an uncertain number of nonzero entries, ranging from none (the node is considered dropped, e.g., Luo et al. (2021)) to one (the node is aggregated once) and even multiple (communities have overlapping issues). No paper has yet delved into the discussion of community overlapping in this field, however, this scenario can also be included within our formulation.

Synthetic approaches, on the other hand, take the condensed graphs as parameters and directly optimize them by minimizing specific objective functions. We further divide this formulation into three strategies: Predefined, Joint Optimization, and Sequential Optimization. Specifically:

Each of the formulations mentioned has its distinct method (or not being invented yet but can be done) for generating ${\bf A}^{\prime}$, ${\bf X}^{\prime}$, $\mathcal{Y}^{\prime}$ separately, despite that the Sequential Optimization Formulation must rely on the intermediate results of the other formulations. As we conclude, the Modification formulations exhibit the strongest computational efficiency and interpretability, but their applicability is limited, as each graph awaiting condensation requires the recalibration of the projection matrix. The Synthetic by joint optimization formulation is the simplest, defining the objective and optimizing directly, yet it is also the most challenging, the parameter search space may be so big that convergence is difficult. To address this issue, the Synthetic by Sequential Optimization is a 2-step scheme, incorporating the advantages of both easy-to-implement and objective-oriented. The Synthetic by Predefined formulation yields intuitive results and can be effective in carefully designed scenarios. The table 1 presents the objective-based category of methods included in this survey, and strategies on how to formulate the condensed graphs.

After introducing the condensation of a single graph, we will now explore the strategies for condensing multiple graphs. Currently, there are only a few methods addressing this application, so we will only provide a concise overview:

One-by-One strategy: If the number of graphs remains unchanged, i.e., every single graph is condensed independently, e.g., Jin et al. (2020), we categorize this scheme as the one-by-one strategy. Any method that can condense a single graph can be modified to condense multiple graphs by adopting this strategy. Joint Optimization strategy: Similar to the single-graph joint optimization, this strategy combines multiple condensed graphs as parameters of the optimization objective, e.g., Jin et al. (2022). By naming the number of graphs in a graph dataset to be $1$, this category of methods would essentially degenerate into a single-graph optimization strategy. Selecting strategy: The core of this strategy is to rank each single graph by score functions, and select the top-ranked ones, e.g., Wang et al. (2021); Xu et al. (2023a). Given that these methods have limited relevance to our survey, we will not delve further.

We systematically organize and summarize the datasets employed in the discussed methods, categorizing them into two primary types: datasets featuring a single large graph and those comprising multiple graphs. The former is typically utilized for tasks such as node classification and edge prediction, while the latter is employed in graph classification. We present key attributes of the datasets, encompassing details such as the number of nodes, number of edges, features and classes, and the graph type (e.g., social network or molecular network) for datasets with a single large graph. Additionally, for datasets containing multiple subgraphs, we provide organization based on the number of subgraphs, average number of nodes, average number of edges, number of labels, and the type of graph. The detailed statistic of the the datasets can be found in our online resources ¹¹1 https://github.com/liangliang6v6/GraphCondensation.

GC aims to create a significantly smaller graph dataset while preserving sufficient information, thus it is crucial to evaluate how much this information is retained. The evaluation of GC methods is challenging compared to the straightforward performance evaluation of traditional GNNs, mainly due to their involvement in multiple aspects. From a holistic perspective, we summarize the evaluation of the entire GC process into two aspects: effectiveness and efficiency. Effectiveness evaluates how well the GC retains the original information, while efficiency includes both the condensation process and downstream task efficiency. Details can be found below: