# GCARe: Mitigating Subgroup Unfairness in Graph Condensation through Adversarial Regularization
## 3 Background  
In this section, we first introduce the notations to be used throughout this paper. Then, we brief the readers on the idea and algorithm of graph condensation.  
In this paper, we consider the task of transductive node classification. A graph consisting of \(N\) nodes can be denoted as a triple \((A,X,Y)\), where \(A\in\mathbb{R}^{N\times N}\) is the adjacency matrix, \(X\in\mathbb{R}^{N\times D}\) is the feature matrix of the nodes, and \(Y\in\{0,\ldots,C-1\}^{N}\) is the node labels over the \(C\) classes. Given a GNN model, we use \(\theta\) to denote its model parameters, \(\text{GNN}_{\theta}(A,X)\) denotes the message-passing procedure, and \(L(\text{GNN}_{\theta}(A,X),Y)\) represents the cross-entropy classification loss.  
Graph Condensation via Gradient MatchingGiven a target graph dataset \(\mathcal{T}=(A_{\mathcal{T}},X_{\mathcal{T}},Y_{\mathcal{T}})\) with \(N_{\mathcal{T}}\) nodes, graph condensation aims at learning on such a synthetic graph dataset \(\mathcal{S}=(A_{\mathcal{S}},X_{\mathcal{S}},Y_{\mathcal{S}})\) with \(N_{\mathcal{S}}\) nodes (\(N_{\mathcal{S}}\ll N_{\mathcal{T}}\)), whereby a GNN trained on \(\mathcal{S}\) performs comparably to one trained on \(\mathcal{T}\). To achieve this goal, [PERSON] et al. [14] proposed to feed a model with batches from both the original and condensed datasets, and match the model gradients at each iteration. The intuition behind this is that, by forcing the gradients to be similar at any step, the model is expected to converge to the same point when trained on either dataset. The gradient matching loss is used to update the condensed data.  
[PERSON] [11] extends this idea to the graph field. Specifically, the node features of the synthetic graph, i.e., \(X_{\mathcal{S}}\), are treated as learnable parameters, and are initialized first. The adjacency matrix is modeled as a function of the node features via the parameters \(\Phi\): \(A_{\mathcal{S}}=\Phi(X_{\mathcal{S}})\). A GNN model is then employed as the agent for compressing the graph, which we refer to as the upstream GNN. Then, at the t-th iteration, both the original graph and condensed graph are fed to the GNN, and the corresponding gradients are computed through backpropagation:  
\[g_{t}^{\mathcal{S}} =\
abla_{\theta}L\Big{(}\text{GNN}_{\theta_{t}}\big{(}\Phi(X_{ \mathcal{S}}),X_{\mathcal{S}}\big{)},Y_{\mathcal{S}}\Big{)} \tag{1}\] \[g_{t}^{\mathcal{T}} =\
abla_{\theta}L\Big{(}\text{GNN}_{\theta_{t}}\big{(}A_{\mathcal{ T}},X_{\mathcal{T}}\big{)},Y_{\mathcal{T}}\Big{)} \tag{2}\]The distance between the two gradients are computed layer by layer via cosine similarity to obtain the gradient matching loss \(D(g_{t}^{S},g_{t}^{T})\), which is then backward to update both \(\Phi\) and \(X_{S}\). Note that this involves computing the second-order derivatives \(\frac{\partial^{2}L}{\partial\theta\,\partial X_{S}}\), which is time-consuming. Then, the upstream GNN is trained for several steps on the updated synthetic graph. This is achieved by aligning the gradients at each iteration, whereby the synthetic graph imitates the whole trajectory of the model updates on the original graph. GCond gained remarkable success on graph condensation. For instance, it was able to approximate the accuracy by up to 95.3% on reddit, and 99.0% on Citeseer while reducing the graph sizes by 99.9%.  
While GCond suffers from the time complexity that occurs when interchangeably updating the synthetic graph and the upstream GNN, DosCond [10], on the other hand, skips the latter and only updates the synthetic graph. This significantly accelerates the condensation process without sacrificing the performance.  
Our method is highly flexible and can be easily integrated with either condensation method. In this paper, we utilize both methods as the backbone.