Faster Hyperparameter Search for GNNs via Calibrated Dataset Condensation
Authors: Mucong Ding
Xiaoyu Liu
Tahseen Rabbani
Teresa Ranadive
Tai-Ching Tuan
Furong Huang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Condensation
Dataset Condensation
Hyperparameter Optimization
Graph Neural Networks
Graph Compression

Abstract: Dataset condensation aims to reduce the computational cost of training multiple models on a large dataset by condensing the training dataset into a small synthetic set. State-of-the-art approaches rely on matching the model gradients for the real and synthetic data and have recently been applied to condense large-scale graphs for node classification tasks. Although dataset condensation may be efficient when training multiple models for hyperparameter optimization, there is no theoretical guarantee on the generalizability of the condensed data: data condensation often generalizes poorly across hyperparameters/architectures in practice, while we find and prove this overfitting is much more severe on graphs. In this paper, we consider a different condensation objective specifically geared towards hyperparameter search. We aim to generate the synthetic dataset so that the validation-performance rankings of the models, with different hyperparameters, on the condensed and original datasets are comparable. We propose a novel hyperparameter-calibrated dataset condensation algorithm, which obtains the synthetic validation data by matching the hyperparameter gradients computed via implicit differentiation and efficient inverse Hessian approximation. HCDC employs a supernet with differentiable hyperparameters, making it suitable for modeling GNNs with widely different convolution filters. Experiments demonstrate that the proposed framework effectively maintains the validation-performance rankings of GNNs and speeds up hyperparameter/architecture search on graphs.

Under review as a conference paper at ICLR 2023
FASTER HYPERPARAMETER SEARCH FOR GNNs VIA CALIBRATED DATASET CONDENSATION
Anonymous authors Paper under double-blind review
ABSTRACT
Dataset condensation aims to reduce the computational cost of training multiple models on a large dataset by condensing the training dataset into a small synthetic set. State-of-the-ard approaches rely on matching the model gradients for the real and synthetic data and have recently been applied to condense large-scale graphs for node classification tasks. Although dataset condensation may be efficient when training multiple models for hyperparameter optimization, there is no theoretical guarantee on the generalizability of the condensed data: data condensation often in practice, while we find
generalizes poorly across hyperparameters/archiie and prove this overfitting is much more severe on graphs. In this paper, we consider a different condensation objective specifically geared towards hyperparameler search. We aim to generate the synthetic dataset so that the validation validationn-peformaann performance rankings of the models, with different hyperparameters, original datasets are comparable. We propose a novel hyperparameter-caliinnnn callbbrated dataset condensation (HCDC) algorithm, which obtains the synthetic validation data by matching the hyperparameter gradients computed via implicit differen- tiation and efficient inverse Hessian approximation. HCDC employs supernet with differentiable hyperparameters, making it suitable for modeling GNNs with widely different convolution filters. Experiments demonstrate that the proposed framework effectively maintains the validation iiidatioo-perffrmannee performance rankings of GNNs and speeds up syperpurametee//acchtteeurr search on graphs
the condensed and
INTRODUCTION
Graph neural networks (GNNs) have found remarkable success in tackling a variety of graph-related tasks (Hamilton, 2020). However, the prevalence of large-scale graphs in real-world contexts, such as social, information, and biological networks (Hu et al., 2020), which frequently scale up to millions/billions of nodes and edges, poses significant computational issues for training GNNs. While training single model can be expensive, designing deep learning models for new tasks requires substantially more computation, as this involves training multiple models on the same dataset many times to verify the design choice (e.g., the architecture and hyperparameter choice (Elsken al., 2019)). Towards this end, we consider the following question: how can we reduce the computational cost for training multiple models on the same dataset, for hyperparameter search/aptimization?
Natural approaches to reduce the training set size include methods such as graph coreset selec- tion (Baker et al., 2020), graph sparsification (Batson al., 2013), graph coarsening (Loukas, 2019) and graph sampling (Zeng et al., 2019). However, all of these methods involve selecting samples from the given training set, which limits the performance. A more effective alternative synthesize informative samples rather than select from the given samples. Datasel condensation (Zhao et al., 2020) has emerged as a competent data mechanism to synthesize data, with promising results. It aims to produce small synthetic training set such that model trained on the synthetic set obtains testing accuracy comparable to that trained on the original training set.
Although dataset condensation achieves the state-of-the-art performance for neural networks trained on condensed samples, this technique inadequate for accelerating hyperparameter search/optimization,
(1) theoretically, dataset condensation obtains synthetic samples that mini- mize the performance drop of a specific model; however, there is no performance guarantee when using this condensed data to train other models, and (2) in practice, it is unclear how condensation

---

Under review as a conference paper at ICLR 2023
methods compare with strong baselines such various coreset methods, in terms of their ability to preserve the outcome of auchicetturchyyerppaaeeerr optimization.
In this paper, we identify the poor generalizability of existing condensed data approaches as this topic has been overlooked in the existing literature, which focuses more image condensation. We prove that graph condensation fails to preserve validation performance rankings of GNN architectures, and identify two dominant reasons for this failure: (1) most GNNs differ from each other in terms of their convolution filter design. Thus, when performing condensation with a single GNN, the condensed data is overfitted to the corresponding GNN filter, a single biased point in the set of GNN filters; and (2) the learned adjacency matrix of the synthetic graph considerably overfits the condensed data, and thus fails to maintain the characteristics of the original adjacency matrix.
graphs (Jin et al., 2021) across architecuures/hpppppraeeeee
To solve the poor generalizability issue, we develop new dataset condensation framework that preserves the outcome of hyperparameter searchloptimizationn on the condensed data. We propose to learn synthetic data as well as its validation split such that the validation performance ranking of architectures on the synthetic and original datasets are comparable.
Under the assumption of a continuous hyperparameter space or a generic supernet which interpolates all architectures, we find and prove that the goal of preserving validation performance rankings can be realized by matching the hyperparameter gradients on the synthetic and original validation data. The hyperparameter gradients (or hypergradients for short) can be efficiently computed with constant memory overhead by the implicit function theorem (IFT) and the Neumann series approximation of an inverse Hessian (Lorraine et al., 2020). Consequently, we propose a hyperparameter calibrated datasel condensation (HCDC) framework assuming continuous hyperparameters, which suitable to modeling GNNs with different convolution matrices. Experiments demonstrate the effectiveness of the proposed framework in preserving the performance rankings of GNNs.
Although beyond the scope of this paper, HCDC also has the potential to be combined with the supernets in differentiable neural architecture search (differentiable NAS) methods (Liu al., 2018) to tackle the general neural architecture space for image and text data.
Our contributions can be summarized as follows: (1) We formulate new dataset condensation objective for hyperparameter optimization and propose the hyperparameter calibrated dataset con- densation (HCDC) framework that learns synthetic validation data by matching the hypergradients. (2) We prove the hardness of generalizing the condensed graph across GNN architectures, and the validity of HCDC in preserving the validation performance rankings of GNNs. (3) Experiments demonstrate the effectiveness of HCDC in further reducing the search time of off-the-shelf graph NAS algorithms, from several hours to minutes on graphs with millions of nodes.
SETTINGS, BACKGROUND, AND CHALLENGES
2.1 SETTINGS: NODE CLASSIRICATION AND GNNs
This paper adopts graph learning notations, but HCDC is generally applicable to other data, tasks, and models; see Appendix B for discussions.
Node classification on a graph considers a graph T = X, with adjacency matrix A E {0, 11nx,, node features
[g= node class labels y. and mutually disjoint node-splits Verain Uvmi UVrest = [n.. Using a graph neural network (GNN) ʃo,x : Rax" x B - R where 0 θ denotes the parameters and À E A denotes the hyper- param-earseesers (if they exist). we aim to find 8T = arg ming Cifain (0, A), where Cirain (f,, A) == Eiev.... E(Joo. X)) y1) and ((), y) is the cross-entropy loss. The node classification loss Cirain (0, >) is under the transductive setting, which can be easily generalized to the inductive setting by assuming only {Aij i, E Virain) and (X4 i Virain) are used during training.
2.2 BACKGROUND: STANDARD DATASET CONDENSATION METHODS
Now, we review the standard dataset condensation (SDC) and its natural bilevel optimization (BL) formulation (Wang et al., 2018).
2

---

Under review as a conference paper at ICLR 2023
SDC's objective. Standard dataset condensation aims to find synthetic graph S = (A', X', y') of size < with (weighted) adjacency matrix A' E 20 node features X' E Rexd node labels y' [K]s, and (possibly) train/validation' / splits Virain UV val [c]. The goal of SDC is to obtain comparable generalization performance on the real graph by training on the condensed graph, i..., Cl (0", A) R Ci (0$, X) where 0 = arg ming L'S (0. A) the model parameters (of the same GNN fo,x) optimized on the synthetic graph. By posing 0 as a function of the condensed graph S. SDC can be formulated as a bilevel optimization problem,
S = =arg ming Caain (S), A) s.t. (S(S) = arg ming C (0, X).
(1)
However, the above problem involves a nested-loop optimization and solving the inner loop for gs (S) at each iteration requires a computationally expensive procedure: unrolling the neural network's computational graph for S over multiple optimization steps of B.
SDC in a gradient matching formulation. Zhao et al. (2020) alleviate this computational issue by introducing a gradient matching (GM) formulation.
Parameter manthhhng formulation. To start, we assume neural network fo,x is a locally smooth function, and thus similar weights 0 x O" imply similar mappings. Then one can formulate the condensation objective as matching the optimized parameters (which depends on initialization By), i.e., finding S arg ming Eoo [D(8S (S, fo), 8* (Bo))]s.t.05 (S, 0o) == arg ming L'S (5min((((0)) X). where 0T (0n) == arg ming Cipain (0(O)), A) and D( is a distance function.
Reduction to gradient matching via approximations. The parameter-matching problem is still bilevel optimization but can be simplified via several approximations.
(1) Firstly, 05 0o) is optimization, @ (S,60) = 0841 + -V o Egrain (AS A). However, the target parameter BT (fg) may be far away from 6 Zhao et al. (2020) propose to match 0++1 with incompletely optimized 0/41 + 0g - -/Volyyain (O) A) at each
approximated by the output of an incomplete gradient-
iteration t. Consequently, the SDC's objective is now S = arg ming Eag-Peo ECT D(OS, of ]]- (2) Secondly, if we assume o can always track 07 (i.e., 05. 07) from the initialization 6g up to iteration i, then we can replace D(0S (+1- OT. by o (0. A), V Vo (07 A)) and then by this approximation D(V D(VoL Cirain X), VoCirain (0S, A)). Repeating this inductive argument, the standard condensation objective is finally approximated by matching the gradients at each iteration I,
S arg ming Ego
E D (0$, A). Ve (OS,, AA)]
(2)
With this gradient matching objective, we obtain a single deep network with parameters trained on the condensed graph S. 'Tee condensed graph S is optimized such that the distance between the gradient vectors of Clysin and of Cirain w.r.t. the parameters minimized. Cosine distance :(.)) = cos(:;)) works well in practice (Zhao et al., 2020).
2.3 CHALLENGES: STANDARD DATASET CONDENSATION IS PROBLEMATIC ACROSS GNNs
For ease of theoretical discussions, in this subsection, we consider single-layer message passing GNNs. Message passing GNNs can be interpreted as iterative convolution over nodes (i.e., message passing) (Ding et al., 2021) where (0) = X, x(++1) = oCC2e x)x(w)())) for / E [L]. and X) = X(L,, where Cam (A) is the convolution matrix parametrized by a0)), W is the learnable linear weights, and (-) denotes the non- -on-iincarity. dinedimmnsional convolution neural networks (ID-CNNs) can be expressed by a similar formula, f(X) = (Ek= (h) XXW, parameterized by 0 = [a, W] where a = (-K) (K)) P is the eyclic permutation matrix (of a unit shift). The kernel size is (2K- + 1), K 2 0; see Appendix B.2 for details.
Despite the success of the gradient matching algorithm in preserving the model performance when trained on the condensed dataset (Wang et al., 2022), it naturally overfits the model ʃe.x used during condensation and generalizes poorly to others. There no guarantee that the condensed synthetic data S* which minimizes the objective (Eq. (2)) for a specific model fo,x (marked by its hyperparameter A) can generalize well to other models fo. where X F X. We aim to demonstrate that this overfitting issue can be much more severe on graphs than on images, where our main theoretical results can be informally summarized as follows.
The train/validation split of synthetic data is only required by HCDC; see Eq. (1) vs. Eq. (3).
3

---

Under review as a conference paper at ICLR 2023
Proposition. Standard dataset condensation using gradient matching algorithm (Eq. (2)) is prob- lematic across GNNs. The condensed graph using a single-laye message passing GNN may fail to generalize to the other GNNs with a different convolution matrix.
We first show the successful generalization of SDC across one mne-dimensional convolution neural networks (ID-CNN). Then, we show a contrary result on GNNs: failed generalization of SDC across GNNs. These theoretical analyses demonstrate the hardnesss of data condensation on graphs. Our analysis is based on the achievability condition of a gradient matching objective; see Assumption 1 in Appendix A.
In Lemma I of Appendix C.I, under least square regression with linear GNN/CNN (see Appendix B.4 for formal definitions), if the standard dataset condensation GM objective is achievable, then the optimizer on the condensed dataset S is also optimal on the original dataset T. Now, we study the generalizability of the condensed dataset across different models. We first show a successful generalization of SDC across different ID-CNN networks; see Proposition in Appendix A. As long as we use 1D-CNN with sufficiently large kernel size during condensation, we can generalize the condensed dataset to wide range of models, i.e., ID-CNNs with a kernel size K' S K.
However, we obtain a contrary result for GNNs terms of the generalizability of condensed datasets across models. Two dominant effects, which cause the failure of the condensed graph's 's ability to generalize across GNNs, are discovered.
Firstly, the learned adjacency A' of the synthetic graph S can easily overfit the condensation objective (see Proposition 2), and thus can fail to maintain the characteristics of the original structure and distinguish between different architectures; see Proposition 2 in Appendix A for the theoretical result and Table for relevant experiments.
Ratio (e/fn)
learned
A' I
0.05%
59.2 1.1
0.5
642
won www.
1.0
(a) Test accuracy of graph condensation with learned identity adjacency.
40
1.0
Condemettes
GCN
NGC
GIN
GCN
ML.3 0.8
39.2 0 07
42.22443 60.5 0.6
SGC
39.2 1.1
7.
GIN
36
$3.5 5.8
89.1 1.1
(b) Generalization accuracy of graphs con- densed with different GNNs (row) across GNNs (column) under e/n- 0.25%.
Widatier Acoulacy Conderaed Graphi
Welterten Acouliry Condeneed Gtuphi"
(a) Condense ratio c/n 0.2
(b) Condense ratio c/n 0.8
Table 1: Test accuracy of GNNs trained on condensed Ogbn-arxiv (Hu et al., 2020) graph verifying the two effects (Proposi- tions and 3) that hinders the generaliza- tion of the condensed graph across GNNs. (a) Condensed adjacency is overfitted to the SDC Objective, (b) Convolution filters and inductive bias mismatch across GNNs.
Figure 1: The manifold of GNNs with convolution filters C3 = [+x (+) Amaa L-I) (linear combination first two orders of ChebNet (Defferrard et al., 2016), X's are hyperparamcters; see Appendices B.2 and E) projected to the plane of validation accuracy on condensed (x-axis) and original (y-axis) graphs under two ratios c/n on Cora (Yang et al., 2016). The GNN with C = Armux - L) x L (red dot) is a biased point in this model space.
Secondly, GNNs differ from each other mostly on the design of convolution filter C(A), i.e., how the convolution weights C' depend on the adjacency information A. The convolution filter C(A) used during condensation is a single biased point in "the space of convolutions": see Fig. for visualization, thus there is mismatch of inductive bias when transferring to a different GNN. These two effects lead to the obstacle when transferring the condensed graph across GNNs, which is formally characterized by Proposition 3 in Appendix A.
Proposition 3 provides an effective lower- on the relative estimation error of optimal model parameters when different convolution filter C'(-) o C(-) is used,2 According to the spectral char- acterization of convolution filters of GNNs (Table of (Balcilar et al., 2021)), we can approximately compute the maximum eigenvalue of Q for some GNNs. For example, if we condense with f graph
"If (+)+ C(-) Lemma guarantees W WT. and the lower bound in Proposition 3 is 0.
4

---

Under review as a conference paper at ICLR 2023
isomorphism network (GIN-O) (Xu et al., 2018) but train fc GCN on the condensed graph, we have [ // W & deg + where deg is the average node degree of the original graph. This large lower bound hints the catastrophic failure when transferring across GIN and GCN; see Table 1.
3 HYPERPARAMETER CALIBRATED DATASET CONDENSATION
Our goal to develop an optimal and reliable condensation method for auchitccuurehhypppaammeeee search. Standard dataset condensation objective (Eq. (1)/E.. (2)) does not accomplish this goal since does not generalize across GNNs, as proven in Section 2.3. In this section, we propose new condensation objective specifically for preserving the outcome of hyperparameter optimization opttiiitoneeeeroootniaattiooonn (HPO) on the condensed dataset.
HPO's objective. HPO finds the optimal hyperparameter X7 such that the corresponding model fU,A minimizes the validation loss after training, i.e.,
A minAiA (A) where (7()) = CP (07 (A), and 0J (A) == arg ming Cirin (0, A). (HPO)
We see HPO itself is bilevel optimization, where the optimal parameter 87 (A) posed function of the hyperparameter X, and so is the optimized validation loss (A()): see Fig. 3 for illustration.
Dataset condensation for HPO. If both the train and validation sets are defined on the condensed dataset S, the optimal hyperparameter X is well-defined. Our goal is to find the synthetic dataset S such that we can obtain comparable validation performance if the hyperparameters are optimized on Clearly, this goal looks very similar to the goal of standard dataset condensation, preserving generalization performance Cleat (0") R Lleat (0S), which inspires us to formulate the new objective as a bilevel optimization problem too,
the condensed dataset, i.e., (X²) ~ L
S arg ming (1*(
s.t. ( arg minxeA (A),
where optimized validation losses LJ (.) and (-)( are defined following Eq. (HPO).
However, two challenges exist: (1) This formulation (Eq. (3)) is nested optimization (for dataset condensation) over another nested optimization (for HPO) which is challenging to solve high order gradients are required. (2) In addition, another challenge lies in the search space/feasible set of the hyperparameters A. In contrast to parameter optimization, where the search space is usually assumed to be the continuous and unbounded Euclidean space, the search space of hyperparameters A can be either a discrete set continuous one. Examples of discrete hyperparameters include neural network type, width, depth, batch size, etc. Often we face compositions of these discrete- and hyperparameters, and we can either model them all as discrete ones and search by grid search, Bayesian optimization, and reinforcement learning; or relax the discrete search space to a continuous one.
continuous-nauue
Hyperparameter calibration: a sufficient alternative to HPO's objective. To solve the afore- mentioned two challenges, we propose an sufficient alternative to Eq. (HPO). Specifically, we propose to identify the condensed dataset that preserves the outcome of HPO on A without solving the HPO objective. We call this hyperparameter calibration, which is formally defined in Definition
Definition (Hyperparameter Calibration). Given original dataset T. generic model fa. and hyperparameter search space A, we say condensed dataset S is hyperparameter calibrated, for any \ # X2 E A, holds that,
(ci( 27 (F3(()) (3s0))))))33))))) 0,
(HC)
In other words, changes of the optimized validation loss on T and S always have the same sign between hyperparameters A # X2
It is clear that if hyperparameter calibration (HC) is satisfied, HPO the original and condensed datasets yields the same result. Therefore, our mission changes to ensuring hyperparameter calibra- tion for single pair of hyperpaaaameeess A2)-
HCDC: hypergradient alignment objective for dataset condensation. To proceed, we assumes the existence of continuous extension of the search space: the (possibly discrete) search space can be extended to compact and connected set À 3 A, where define continuation of the
5

---

Under review as a conference paper at ICLR 2023
brof codiing puraradess e10
Prpectozina Pxateoos
Ag 2h
bq eeN
bs P..
Perumero
Pacomaton
(a) Discrete A = (A:} (b) Continuous A e X
(a) Train loss Cirain
(b) Validation loss CT
Illustration of the constructed tended search space Å illustrated as the or- ange trajectory for both a) discrete A and (b) continuous A. The trajectory starts from A = A; A for discrete (or random points for continuous A), and updates through Xr,41 + X.. x
Figure 2:
Figure 3: Loss landscape w.E.L and X. A hyperparameter À has an optimal parameter 0" (A) (blue curve in (0. X)-plane in (a)) that minimizes the train loss. In (b), injecting optimal parameters 0" (A) into the validation loss, we obtain function of validation loss w.r.t. À (denoted
C7-(A) in (C, A)-plane, shown the orange curve. The purple dash line illustrates the hypergradients, i.e., gradient of (A) w.r.t.
generic model Sa,A on À so that Sa,S is differentiable anywhere in Å. In Section 4, will elaborate on how to construct such an extended search space Å.
Now, with the existence of such continual extension of the search space, if we limit our step size to be small, we only need to ensure hyperparameter calibration in Eq. (HC) under the special case that A is within the neighborhood of 22, i.e., Xı E (A2) for some > O. The change in validation loss approximated up to first-order by the hypergradients, i.e., ()1) - LJ (A2) RS xVxC7 (A), AX), where Å À + AA, A2 with > A - 0+ The hyperparameter calibration condition within this tiny neighborhood B, is then simplified to (AC || (A) ie., the two hypergradient vectors are aligned and pointing the same direction.
Assuming the extended search space Å can be covered by the union of many small neighborhoods, we derive the following notion and equivalence relation of hypergradient alignment.
Definition (Hypergradient Alignment). We say hypergradients are aligned in an extended search space A, for any X E Å, holds that xxC7(A) II (A) i.e., cos cos(V (A), VxC3s (A)) O. Theorem (Equivalence between Hypergradient Alignment and Hyperparameter Calibration). Hy- pergradient alignment (Definition 2) is equivalent to hyperparameter calibration (Definition 1) on the connected and compact set, e.g., the extended search space A.
We summarize the relations between the notions (Definitions 1 and 2) as follows, Hypergrad. Alignment in Å <>> Hyperpara. Calibration in Á - Hyperpara. Calibration in A. Therefore, hypergradient alignment on Á is sufficient to ensure hyperparameter calibration on A, and hence the outcome of HPO over A is preserved. Consequently, as the core of our hyperparameter calibrated dataset condensation (HCDC), we propose the hypergradient alignment objective below
S arg mins ΣxE D(VxCal (OT(A)) A), VxLga (0S (0S(O)) A)),
(HCDC)
where cosine distance D(,,)) = cos(:.) .) is used.
IMPLEMENTATIONS OF HCDC AND APPLICATIONS TO GNNS
Finally, work implementing and simplifying the hyperparameter calibrated dataset condensation (HCDC) objective and apply it to the graph wechiteturrehypeppaaaneeee search problem.
Constructing the extended search space Å. The HCDC objective requires hypergradient alignment over all X's in an extended space that is a compact and connected superset of A. Under the discrete search space A, which consists of p candidate hyperparameters, construct Á as (pp²) continuous paths connecting pairs of candidate hyperparameters (shown as blue lines in Fig. 2a). This is apparently undesirable due to its quadratic complexity in p. We propose a construction of Á with a linear complexity in p, which works as follows. For any i E [p]. we construct "representative" path, named i-th HPO trajectory, which starts from X X, A and
can naively

---

Under review as a conference paper at ICLR 2023
updates through X < X (V shown as the orange dashed lines in Fig. 2a. All of the p trajectories will approach the optima X forming "connected" paths between any pair of hyperparameters X # A E A. This construction is also used in continuous search space to save computation (except that we randomly select the starting points X; ~ AA) To extend general discrete neural architecture space A into a continuously differentiable A, differentiable NAS approaches surveyed in Appendix D.3 can be used, and we leave exploration in this direction to future work.
Computing hypergradients and optimizing hypergradient alignment loss in Eq. (HCDC). The hypergradients are the gradients of the optimized validation loss (A) C7' 2)) w.r.t the hyperparameters \; see Fig. for the illustration. The efficient computation of hypergradients (A) and VxL5(A) uses the implicit function theorem (IFT),
VxC+(A) =
O8 (Pccpiin (0.2)
o (0 0000
V Voly
CoCaall0000 (0, (0
(IFT)
8200
where V2 is the direct gradient, which is 0 when À only affects the loss through the model
(0.)) inverse training fa,x- The first term is the product of the training mixed partials [ ex0e
Hessian 8 (l ( and the validation gradients Vo (0, A). While the other parts can be 2630?
computed by Back-propagate conjugate gradient method, Lorraine al. (2020) propose stable, tractable and efficient Neumann 8 _C
the inverse Hessian needs to be approximated. Instead of using the
with constant memory constraint. To optimize the synthetic validation set Svaal w.r.t. the cosine hypergradient matching loss in Eq. (HCDC), we only need to take gradients of VoLg (6,, A) and VxL3 (0, A) w.r.t. S which can be handled by the same back-propagation technique in SDC, where we take gradients of V Vo (0, A) w.r.t Strain
series approximation, 8 (l))))
lim;-xoo Σj=n [T
080e"
Connecting HCDC to SDC (Eq. (2)). Theoretically speaking, the objective of HCDC, preserving the outcome of hyperparameter optimization (HPO), is orthogonal the objective of SDC, which pre- serves the generalization performance. Therefore, we use SDC to learn the synthetic training dataset Strain in Eq. (2) and HCDC to learn the synthetic validation dataset Sval in Eq. (HCDC). Learning the synthetic training and validation dataset may result in disconnected training and validation set, which is allowed in graph learning.
search problems can HCDC solve? We illus- trate how to tackle the two types of search spaces: (1) discrete and finite A and (2) continuous and bounded A with two typical examples originated from the problem of searching for the best convolution matrix C(A) on a large graph T (A, y). (1) Discrete and finite search space A: often the most important question of architecture search on large graphs is what design of convolution filter performs best on the given graph? One may simply train the set of p prior-defined GNNs (209. .] i 1 .P) whose convolution matrices are C = (c (A),..., ",,,).,,(()) (A)} and compare their validation performance. We can formulate this problem HPO, by defining an "inter- polated" model ff_, whose convolution matrix is (A) = (()) (4) +..+++++++ ( cela (A), a0))
Which graph wwchitecture/hyprpprrr
c(P)
where hyperparameters x = (A()..... X E A and parameters a = ( The search space A = (A1 = of ....... . A = e is the set of unit vectors in R (2) Continuous and bounded search space A: one may also use a continuous generic formula, e.g., truncated series, to model a wide range of convolution filters, i.e., Cx(A) Ei ( (() (A), for example in ChebNet (Defferrard et al., 2016) or SIGN (Frasca et al., 2020) (see Appendix B.2). The formula of Cx (A) is special case of the (A,)(A) in (1), despite the search space now continuous.
(.)).
The complete pseudo-code of HCDC. We conclude this section by summarizing the implementa- tion of HCDC in Algorithm 1. We assume discrete and finite search space A.
In Line 8, to compute S.n. DV V (2)), we note that only V (A) depends on
Sval. By Eq. (IFT), (3) = - 8² (0.2) 8 cstain (0.A) -1 VeL A) (there is direct 0oans
8x0us gradients since À only affects the loss through the model fe. Since only the validation loss term VoLgal (0, A) depends on Syal, we only need to compute S VoLgal (0, A) by back-propagation.
7

---

Under review as a conference paper at ICLR 2023
Algorithm HCDC: hyperparameter calibrated dataset condensation, which aims preserve the
validation performance ranking of archicctturs/hhppeppaaaeeen
Require: Original dataset T. A set of NN architectures fo.A where À E A (Aa...., Ap).
Require: Condensed training data Strain Icarned by standard gradicnt-mathing algorithm (Eq. (2)). Randomly initialized synthetic graph Sval C classes.
for repeat k
0, ......K
do
for À == .1,..... Ap do
Initialize 0 t 0o Pbo
for epoch 0, ..... .....
do train (0, A).
5
Update 0 + - 17 V S
6
i mod Tx = then
Update À + À nA (A).
Hypergradients calculated using Eq. (IFT).
8
Update Sval <- Sval nss V sua (A)
return Condensed validation data SYal-
5
RELATED WORK
Graph condensation (Jin et al., 2021) achieved the state-of-the-art preserving GNNs' performance on the simplified graph. Jin et al. (2021) adapted the gradient matching algorithm (Zhao et al., 2020) (Eq. (2)) to graph data, together with MLP-based graph generative model (Anand & Huang, 2018), leaving out several major issues on its efficiency, performance, and generalizability. While the efficiency the performance degradation on medium- and large-sized graphs still renders graph condensation impractical. Our HCDC designed for syperparametee//cchiiteeuuu search, where train multiple models on the same dataset and the efficiency gain is much more significant.
improved by reducing the number of gradient matching steps (Jin et al., 2022),
Implicit differentiation methods apply the implicit function theorem (IFT) (Eq. (IFT)) nested- optimization problems (Wang et al., 2019). Lorraine et al. (2020) approximated the inverse Hessian by Neumann series, which stable alternative conjugate gradients (Shaban et al., 2019) and scales IFT to large networks with constant memory. Lorraine et al. (2020) also showed that unrolling differentiation around locally optimal parameters for steps is equivalent to approximating the inverse Hessian by Neumann series up to the first terms.
In addition. we summarize graph reduction methods (including graph coreset selection, graph sampling, graph sparsification, and graph coarsening), as well as more dataset condensation and coreset selection methods beyond graphs and differentiable NAS methods Appendix D.
EXPERIMENTS
In this section validate the effectiveness of hyperparameter calibrated dataset condensation (HCDC) when applied to speed up graph pahiitetturehhyypparrmaaa correlation coefficient r, between
search. Spearman's 's rank rankings of the ordered list of hyperparameters the original
and condensed datasets, which concisely referred to as correlation, used as an important evaluation metric, addition the percentage accuracy metrie (referred as performance).
Synthetic experiments on CIFAR-10. We first consider a synthetically created set of hyperparam- on image dataset, CIFAR-10. Consider the M-fold cross validation, where fraction of 1 L/M samples are used as the validation dataset each time. The M-fold cross-validation process can be modeled by a set of M hyperparameters {y;, E {0, 1} | 1, ... M.. where y. 1 if and only the i-th fold is used for validation. The problem of finding the best validation performance among the M results can be modeled as hyperparameter optimization problem with a discrete search space |A| M. We compare HCDC with the gradient matching (Zhao et al., 2020) and distribution matching (Zhao & Bilen, 2021b) baselines. We also consider uniform random sampling baseline and an early-stopping baseline where we train the same number of iterations' (with the same batchsize) as the other methods but on the original dataset. The results of M = 20 and c/n = 2% and 4% are reported in Table 2. where shows that HCDC can be applied to general types of data and tasks as long as the extended search space be effectively and efficiently constructed.
see HCDC achieves the highest rank correlation. This experiment
8

---

Under review as a conference paper at ICLR 2023
Ratio (Casain (n)
Method
2%
4%
-0.03
0.07
SDC GM
0.64
0.78
SDC DDC-DM
0.77
0.86
SSoopigg
0.11
0.24
HCDC
0.91
0.94
Table 2: The rank correlation and validation performance on the original dataset of the M-fold cross validation ranked/selected on the condensed dataset on CIFAR-I0.
Speed-up of the search process of graph NAS when combined with HCDC Ogbn-arxiv, best test performance so far vs. time spent.
Figure 4:
Finding the best convolution filter on (large) graphs. One application of HCDC we analyzed in Section 4 is to speed up the selection of the best-suited convolution filter design on large graphs. Following the method discussed in Section 4, we test HCDC against (1) Random: the random uniform sampling of nodes and find their induced subgraph, (2) GCond-X: graph condensation (Jin et al., 2021) but fix the synthetic adjacency to identity, (3) GCond: graph condensation algorithm in (Jin et al., 2021), and (4) Whole Graph: when the model selection is performed on the original dataset. We use random uniform sampling to find the training synthetic subgraph before we apply HCDC. For the other coreset/condeenstionn methods, which do not define the validation split, we randomly split the train and validation nodes according to the original split ratio. We report not only the Spearman's 's rank correlation, but also the test performance (on the original dataset) of the model selected by the condensed dataset. In Table 3, we see HCDC consistently outperforms the other approaches, and the test performance of selected architecture is close to the ground-truth best performance.
Method Dutset
Ratio (Gaeec/))
Random
OCond
GUond
Graph Perf
Com
Perf.
Cour.
Per. (8))
Con:
Perí:
Perf. (9))
20.5 0.7
0.01 28
8L.
Com
1.8%
0.40
81.0
0.5
0.21 07
80-3
0033-004 0.4
0.76
83.2
0.85
831
0
81.8 a 0.0
3,6%
0.51 .94
82.2 0.6
0.21 .04
50.9 0.6
0.81
= 04
83.22:11
0.90 : .01
83.4 0.3
1.3%
0.38
71.9 0.8
0.16
.07
70.7
0.9
0.68 00
11
0.79 2 01
0
Chiceer
1,84
0.56 1:68+.00 100
72.2 0.0
0.29
05
70.8
0.5
0.70
76
71.5++07
0.63 + 02
13.3
0.5
13.7 + 0.0
5.28
0.71 4
73.022:0.3
0.25
2: 08
7012 0.4
0.8 00
T1.1 0:
0.89 :
T3.4 0.4
0.18
0.29 2:00 .88
0.20 70.1
00
00.8 1.4
0.00
0.77 1.
04
0.0
Oghassnsiv
0.25%
0.8
10.5 1:3
0:54::00
70.1 0.7
0.4 20 26
10:50:10
0.83 :
72.45:10
13.2 08
0.42
12.1
0.20 2:
0.53 0.8
Reali
0.25%
9:2
0.
D4.1
Table 3: Spearman's 's rank correlation and test performance of convolution filter selected on the condensed graph.
Speeding up off-the-shelf graph architecture search algorithms. Finally, we test HCDC on how much speed-up up it can provide to the off- the-shelf graph architecture search methods. We use graph NAS (Gao al., 2019) on Ogbn-ard arxiv with a condensation ratio of c/n 0.5%. The search space of architectures is the same as the set used in Table 3 with a focus on graphs with different convolution filters. We plot the best test performance of searched architecture (so far) versus the time spent during searching (in seconds) in Fig. 4. We see HCDC, as dataset condensation approach, can further speed up the search process of graph NAS and is orthogonal to the efficient search algorithms like Bayesian optimization or reinforcement learning used by NAS methods.
7 CONCLUSION
This paper considers novel objective for dataset condensation: preserving the outcome of hyperpa- rameter search/optimization. We propose the hyperparameter calibration formulation for this goal, which is then realized by aligning the hyperparameter gradients. We demonstrate both theoretically and experimentally that HCDC can effectively preserve the validation performance rankings of GNNs and accelerate the hyperparameteraacchteennr search on graphs. However, the overall performance of HCDC can be affected by (1) how the supernet generalize to unseen architectures; (2) where we align hypergradients in the search space; (3) how we learn the synthetic training set; (4) how we parameterize the synthetic graph/dataset; and leave the heuristic exploration of all possible techniques for these design choices for future work. Beyond graph datasets, HCDC has the potential to be integrated with differentiable neural architecture search (NAS) methods (Liu et al., 2018; Wang et al., 2020) to address general neural architecture space. We hope our work opens up a promising new avenue for speeding up hyperparantterarchhtttuuue search by compressing the underlying dataset.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Rahaf Aljundi, Min Lin, Baptiste Goujaud, and Yoshua Bengio. Gradient based sample selection for online continual learning. Advances neural information processing systems, 32, 2019.
Namrata Anand and Possu Huang. Generative modeling for protein structures. Advances in neural information processing systems, 31, 2018.
Daniel Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H-C Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering in graphs of bounded treewidth. In International Conference Machine Learning, pp. 569-579. PMLR, 2020.
Muhammet Balcilar, Renton Guillaume, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks spectral perspective. In Proceedings of the International Conference Learning Representations (ICLR), 2021.
Joshua Batson, Daniel A Spiclman, Nikhil Srivastava, and Shang-Huu Hua Teng. Spectral sparsification of graphs: theory and algorithms. Communications of the ACM, 56(8):87-94, 2013.
Yoshua Bengio. Gradient-based optimization of hyperparameters. Neural computation, 12(8): 1889-1900, 2000.
Ondrej Bohdal, Yongxin Yang, and Timothy Hospedales. Flexible dataset distillation: Learn labels instead of images. arXiv preprint arXiv:2006.085572 2020.
Zalán Borsos, Mojmir Mutny, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming. Advances in Neural Information Processing Systems, 0.:14877-14899) 2020.
Vladimir Braverman, Shaofeng H-C Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering in excluded-mine graphs and beyond. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2679-2696. SIAM, 2021.
Chen Cai, Dingkang Wang, and Yusu Wang- Graph coarsening with neural networks. In International Conference on Learning Representations, 2020.
Yutian Chen, Max Welling, and Alex Smola. Super- Super-samples from kernel herding. In Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, pp. 109-116, 2010.
Wei-Lin Chiang. Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 257-266. 2019.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in neural information processing systems, volume 29, 2016.
Mucong Ding, Kezhi Kong, Jingling Li, Chen Zhu, John Dickerson, Furong Huang, and Tom Goldstein. Vq-gnn: A universal framework to scale up graph neural networks using vector quantization. Advances in Neural Information Processing Systems, 34:6733-6746. 2021.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. The Journal of Machine Learning Research, 20(1); 19(1):1997-2017, 2019.
Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004.11 2020.
Yang Gao, Hong Yang, Peng Zhang, Chuan Zhou, and Yue Hu. Graphnas: Graph neural architecture search with reinforcement learning. arXiv preprint arXiv:1904.09998 2019.
Chengeheng Guo, Bo Zhao, and Yanbing Bai. Deepcore: A comprehensive library for coreset selection in deep learning. arXiv preprint arXiv:2204.08499 2022.
10

---

Under review as a conference paper at ICLR 2023
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. Advances in neural information processing systems, 30, 2017.
William L Hamilton. Graph Representation Learning. Morgan & Claypool Publishers, 2020.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 10111188221,,--11 2020.
ZHAO Huan, YAO Quanming, and TU Weiwei. Search to aggregate neighborhood for graph neural network. In 202/ IEEE 37th International Conference on Data Engineering (ICDE), pp. 552-563.
IEEE, 2021.
Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. Scaling up graph neural networks via graph coarsening. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 675-684, 2021.
Rishabh Iyer, Ninad Khargoankar, Jeff Bilmes, and Himanshu Asanani. Submodular combinatorial information measures with applications in machine learning. In Algorithmic Learning Theory, pp. 722-754. PMLR, 2021.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. In International Conference on Learning Representations, 2017.
Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensation for graph neural networks. In International Conference Learning Representations, 2021.
Wei Jin, Xianfeng Tang, Haoming Jiang, Zheng Li, Danqing Zhang, Jiliang Tang, and Bing Yin. Condensing graphs via one-step gradient matching. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 720-730, 2022.
Jang-Hy Kim, Jinuk Kim, Seong Joon Oh, Sangdoo Yun, Hwanjun Song, Joonhyun Jeong, Jung- Woo Ha, and Hyun Oh Song. Dataset condensation via efficient synthetic-data parameterization. In International Conference on Machine Learning, pp. 11102 11118. PMLR, 2022.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2016.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph
learning. In Advances in neural information processing systems. PMLR, 2019.
Suraj Kothawade, Vishal Kaushal, Ganesh Ramakrishnan, Jeff Bilmes, and Rishabh Iyer. Prism: A rich class of parameterized submodular information measures for guided data subset selection. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 10238-10246, 2022.
Jan Larsen, Lars Kai Hansen, Claus Svarer, and M Ohlsson. Design and regularization of neural networks: the optimal use of a validation set. In Neural Networks for Signal Processing VI. Proceedings of the 1996 IEEE Signal Processing Society Workshop, pp. 62-71. IEEE, 1996.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Uncertainty in artificial intelligence, pp. 367-377. PMLR, 2020.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. In International Conference on Learning Representations, 2018.
Mengyang Liu, Shanchuan Li, Xinshi Chen, and Le Song. Graph condensation via receptive field distribution matching. arXiv preprint arXiv:2206. 13697, 2022.
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International Conference Artificial Intelligence and Statistics, pp. 1540-1552. PMLR, 2020.
Andreas Loukas. Graph reduction with spectral and cut guarantees. J. Mach. Learn. Res., 20(116): 1-42, 2019.
11

---

Under review as a conference paper at ICLR 2023
Andreas Loukas and Pierre Vandergheynst. Spectrally approximating large graphs with smaller graphs. In International Conference on Machine Learning, pp. 3237-3246. PMLR, 2018
Jelena Luketina, Mathias Berglund, Klaus Greff, and Tapani Raiko. Scalable gradient-based tuning of continuous regularization hyperparameters, In International conference machine learning, pp. 2952-2960. PMLR, 2016.
Chris Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: continuous relaxation of discrete random variables. In International Conference on Learning Representations, 2017.
James Martens and Roger Grosse. Optimizing neural networks with frottcder-factored approximate curvature. In International conference machine learning, pp. 2408-2417. PMLR, 2015.
Timothy Nguyen, Zhourong Chen, and Jachoon Lee. Dataset meta-learning from kernel ridge- regression. In International Conference on Learning Representations, 2020.
Timothy Nguyen, Roman Novak, Lechao Xiao, and Jaehoon Lee. Dataset distillation with infinitely wide convolutional networks. Advances in Neural Information Processing Systems, 34:5186-5198 2021.
Peter Ochs, René Ranftl, Thomas Brox, and Thomas Pock. Bilevel optimization with nonsmooth lower level problems. In International Conference on Scale Space and Variational Methods in Computer Vision, pp. 654-665. Springer, 2015.
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning data diet: Finding important examples early in training. Advances in Neural Information Processing Systems, 34: 20596-20607, 2021.
Fabian Pedregosa.
Hyperparameter optimization with approximate gradient. In International conference on machine learning, pp. 737-746. PMLR, 2016.
Omri Puny, Heli Ben-Hamu, and Yaron Lipman. From graph low-rank global attention to 2-fwl approximation. In International Conference on Machine Learning. PMLR, 2020.
Sylvestre-Alvis Alvise Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H Lampert. icarl: Incremental classifier and representation learning. In Proceedings of the IEEE conference on Computer Vision and Puttern Recognition, pp. 2001-2010, 2017.
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer on large-scale molecular data. In Advances in neural information processing systems, volume 33, 2020.
Venu Satuluri, Srinivasan Parthasarathy, and Yiye Ruan. Local graph sparsification for scalable clustering. Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, pp. 721-732. 2011.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference on Learning Representations, 2018.
Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated baok-propag for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1723-1732 PMLR, 2019.
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In International conference on artificial neural networks, pp. 412-422. Springer, 2018
Felipe Petroski Such, Aditya Rawal, Joel Lehman, Kenneth Stanley, and Jeffrey Clune. Generative teaching networks: Accelerating neural architecture search by learning to generate synthetic training data. In International Conference on Machine Learning, pp. 9206-9216. PMLR, 2020.
Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey Gordon. An empirical study of example forgetting during deep neural network learning. In International Conference on Learning Representations, 2018.
12

---

Under review as a conference paper at ICLR 2023
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations. 2018.
Kai Wang, Bo Zhao, Xiangyu Peng. Zheng Zhu, Shuo Yang, Shuo Wang, Guan Huang, Hakan Bilen, Xinchao Wang, and Yang You. Cafe: Learning to condense dataset by aligning features. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 12196-12205, 2022.
Ruochen Wang, Minhao Cheng, Xiangning Chen, Xiaocheng Tang, and Cho-Jui Hsieh, Rethinking ar- chitecture selection in differentiable nas. In International Conference on Learning Representations, 2020.
Tongzhou Wang, Jun- Yan Zhu, Antonio Torralba, and Alexei A Efros. Dataset distillation. arXiv preprint arXiv:1811.10955 2018
Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A
follow-the-ridge approach. International Conference on Learning Representations, 2019.
Zhili Wang, Shimin Di, and Lei Chen. Autogel: An automated graph neural network with explicit link information. Advances in Neural Information Processing Systems, 14:24509-245222 2021.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. Snas: stochastie neural architecture search. In International Conference on Learning Representations, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2018.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learming, pp. 40-48. PMLR, 2016.
Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. In International Conference on Learning Representations, 2019.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2019.
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations. arXiv preprint arXiv:2001.05140, 2020.
Bo Zhao and Hakan Bilen. Dataset condensation with differentiable siamese augmentation. In International Conference on Machine Learning, pp. 12674-12685. PMLR, 2021a.
Bo Zhao and Hakan Bilen. Dataset condensation with distribution matching. arXiv preprint 10..4221 2021b.
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. In International Conference Learning Representations, 2020.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V Le. Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 8697-8710, 2018
13

---

Under review as a conference paper at ICLR 2023
Supplementary Material
A STANDARD DATASET CONDENSATION IS PROBLEMATIC ACROSS GNNS
In this section, we complete the theoretical details behind Scction 2.3, which shows standard dataset condensation is problematic across GNNs.
Assumption (Achievability of a gradient matching Objective), A gradient matching objective is defined to be achievable if there exists a non-degenerate trajectory (0) ( (i.e., a trajectory that spans the entire parameter space θ i.e. span(0)) :..., 1)- 2 θ) such that the gradient matching loss (the objective of Eq. (2) without expectation) this trajectory is O.
Proposition 1 (Successful Generalization of SDC across ID-CNNs), Consider least- least-squares regres- sion with one-dimensional linear convolution fX)+1(X)o k= (x } XW parameterized by 0 [a,, W] where a (a(-k), K) ..... ..
the cyclic permutation matrix (of a unit shift). The kernel size is (2K + 1), 2 O. the gradient matching objective of f2k*1 is achievable, then the condensed dataset S achieves the gradient matching objective any trajectory (0,5) IT for
any linear convolution fgr 22k'+ with kernel size (2K' + K) K' K'20. O.
The intuition behind Proposition 1 is that the ID-CNN of kernel size (2K + 11 is a "supernet" of the ID-CNN of kernel size (2K" + 1) if K' S K, and the condensed dataset via a bigger model can generalize well to smaller ones. This result suggests us to use a sufficiently large model during condensation, to enable the generalization of the condensed dataset to a wider range of models.
Proposition 2 (Condensed Adjacency Overfits SDC Objective). Consider least-squares regression with a linear GNN, [(A, = XW parameterized by W and C(A) which depends on graph adjacency A. For any (full-ranked) synthetic node features X' E Rexd, there exists a synthetic adjacency matrix A' E cxc such that the gradient matching objective is achievable.
Proposition 3 (Failed Generalization of SDC across GNNs). Consider least-square. regression with linear GNN, fW (A, X) = C(A)XW parametrized by W, there always exists condensed graph S*, such that the gradient matching objective for f is achievable. However, if we train new linear GNN CC (A, X) with convolution matrix C' (AA' on S*, the relative error between the optimized model pa- rameters of fW on the real and condensed graphs is ( -W..1//WWW. || 2 max (Tmax(() (Q)- -1,1111- Twin (Q)}, where WT. arg minw ll for (), W arg minw I|y' - f X'
and Q = (XTIC(A)] (FXC)
B MORE PRELIMINARIES
In this section, describe in greater details the types of data, downstream tasks, and neural network models that our hyperparramete--calirride also religiously define the simplified linear convolution regression problem with least-square loss and linear convolution models, which is the assumed setup for Lemma and Propositions 1 to 3.
dataset condensation (HCDC) applies to. Moreover, we
B. DOWNSTREAM TASKS
In Section 2 we have defined the downstream task that this paper mainly focus on, node clas- sification on graphs. Where we are given graph T (A, X, with adjacency matrix A {0, 1 1 node features X E gnxdd node class labels y E [K]", and mutually disjoint node-splits Viain Uva Vist V [m], and the goal is to predict the node labels.
Here, to give a background on the convolution neural networks (CNNs) applications discussed in Section 2.3, show follows the settings above can be also used to describe per-pixel classification on images (e.g., for semantic segmentation) where CNNs are usually used.
For per-pixel classification, we are given set of images of size x h, the pixel values of the j-th image can be formatted as a tensor X, E Rxxxxx there are e channels. We are also given the pixel labels 2) E [K]* for each image j E [n] and the mutually disjoint image- splits Trrain U Toal U Trast [n]. Clearly, can reshape the pixel values and pixel labels of
14

---

Under review as a conference paper at ICLR 2023
the j-th image to wh x and wh respectively, and concatenate those matrices from all images. Following this, denoting n = nwh, we obtain the concatenated pixel value matrix X E Raxe and the concatenated pixel label vector y [K]". The image-splits are translated into pixel-level splits where Virain = {i [j - 1)wh I i S juh,,j E [tria (similar for Veat and Viest) and Virain Veal Vaest [n]. We can also define the auxiliary adjacency matrix A E {0, 1] jaxa on
the n nwh pixels, where A is block diagonal A = diag(AI,.... An) and A, E {0, 1]
10,113xxuo wh J.wkwwwwh wh is
the assumed adjacency (e.g. a (wo-dimensional grid) of the j-th image.
B.2 NEURAL NETWORK MODELS
This paper mainly focus graph neural networks (GNNs) Sa, R8"" x Raxd - R where 0 E e denotes the parameters and À E A denotes the hyperparameters. In Section 2 we have seen that most GNNs can interpreted as iterative convolution / message passing over nodes (Ding et al., 2021: Balcilar et al., 2021) where x()) X and f(A, x(),, and for I [L], the update-rule is,
x o (A)
where Ca (A) is the convolution matrix parametrized by ( w() is the learnable linear weights, and a (-) denotes the non -ineaiita Thus the parameters consists of all a's (if they exist) and W's, i..., 0 [a
(L-1), W ..... W(L-1)).
More specifically, it is possible for GNNs to have more than one convolution filters per layer (Ding al., 2021; Balcilar al., 2021) and we may generalize Eq. (4) to,
x a
((ú all (A)x
Within this common framework, GNNs differ from each other by the choice of convolution filters {C which can be either fixed or learnable. If Cti) is fixed, there is no parameters (1.i) for any I e [L]. If C is learnable, the convolution matrix relies on the learnable parameters (1.3) and can be different in each layers (thus should be denoted as C(.0). Usually for GNNs, the convolution matrix depends on the parameters in two possible ways: (1) the convolution matrix Ct..)) is scaled by the scalar parameter a (1.i) E IR, i.e., C( a (t.5) (()) (e.g. GIN (Xu al., 2018), ChebNet (Defferrard et al., 2016), and SIGN (Frasca et al., 2020)); or (2) the convolution matrix is constructed by 2,
nove-level self-attentions [C(,,)) by hame (x(²) X [ (e.g., GAT (Veličković et al., 2018), Graph Transformers (Rong et al., 2020; Puny et al., 1: Zhang et al., 2020)). Based on (Ding et al., 2021; Balcilar al., 2021), we summarize the popular GNNs reformulated into the convolution over nodes / message-passing formula (Eq. (5)) in Table 4.
Convolutional neural networks can also be reformulated into the form of Eq. (5). For simplicity we only consider one-dimensional convolution neural network (ID-CNN) and the generalization to 2D/3D-CNNV is trivial. If we denote the constant cyclic permutation matrix (which corresponds to a unit shift) as P R"x*, the update rule of a ID-CNN with kernel size (2K + 1), K 2 0 can be written as,
k=K Σ
x(++1)
(6)
A
K
We will use this common convolution formula of GNNs (Eq. (5)) and ID-CNNs (Eq, (6)) in Ap- pendix B.4 and Proposition 1.
B.3 OTHER TYPES OF DATA, TASKS, AND MODELS
In Appendices B. and B.2 we have discussed the formal definition of two possible tasks (I) node classification on graphs and (2) per-pixel classification on images, and reformulated many popular GNNs and CNNs into a general convolution form (Eqs. (5) and (6)). However, we want to note that the application of dataset condensation methods (including the standard dataset condensation (Wang et al., 2018; Zhao et al., 2020; Zhao & Bilen, 2021b) and our HCDC) is not limited by the specific types of data, tasks, and models.
15

---

Under review as a conference paper at ICLR 2023
Model Name
Design
Conv.
Type
Conv.
Convolution Marrix
GCN' (Kipf & Welling, 2016)
Sputial Comy.
Fixed
C= D U2ĀD 1/2
(11))
SAGE-Menn" (Hamilton et a 2017)
Message Passing
Fixed
(et2) Dー
(0 A and
GAT (Velickovié et al, 2018)
Self-Atiattinn
Learnabe
heads
(x.2 . - mep [LoskyRoLL
(x( | wite) all
Fixed
1 =
GIN (Xu et al,, 2018)
WL-Tess
Learaale
- In and 1 +
6 I., eth 21/ In-
SGC*(Delf 2016)
Spettal Conv.
Learablec
order poly.
2g ((--))
and Nil B16
T., (() Araa In.
ChebNet (Defeerrt et al., 2016)
Spectral Conv.
Learnable
order of poly.
< 20(21 g(>22)
and Mod
GDC (Klicpraa al, 2019)
Diflusion
Fixed
C=5
< and 109
(ugg wil (X xg))
Graph Transformer' (Kong 2020)
Self-Atiention
Learnalec
heads
Vae (X we M )))
Where À = A + I,. D In. 2(00 represents mean aggregator. Weight matrix (Hamilton et al., 2017) is W/O W((.) [| W 'Need row-wise normalization. C is non-zero if and only if A.g - 1, thus GAT follows direct-neighbor aggregation. *The weight matrices of two convolution supports are the same, W W( largest eigenvalue, which for a large graph. Where is the diffusion matrix = D 0,7", example, decaying weights 0g e * and transition matrix T D-1-2 ? Need row-wise normalization. Only describes the global self-attention layer, where Wrlla), w3 E Rhoda are weight matrices which compute the queries and keys vectors. contrast to GAT, all entries (l are non-zero. Different design Graph Transformers (Puny et al., 2020; Rong et al,, 2020; Zhang al., 2020) use graph adjacency information different ways, and is not characterized here, see the original pupers for details.
5 "Whre normalized aplacian I= D 1/2 AT) 1/2 and Ames
be approximated as
Table Summary of GNNs formulated as generalized graph convolution.
For HCDC, we can follow the conventions in (Zhao et al., 2020) to define the train/validation losses on iid samples and define the notion of dataset condensation as learning a smaller synthetic dataset with less number of samples. Here we leave the readers to (Zhao et al., 2020) for formal definitions of condensation on datasets with iid samples.
More generally speaking, our HCDC can be applied as long (1) the train and validation losses, i.e., Ctrain (0, A) and Cy (0, A) can be defined (as functions of the parameters and hyperparameterss; and (2) we have an well-defined notion of the learnable synthetic dataset S, (c.g., which includes prior-knowled like what is the format of the synthetic data in S and how the same model fo,x is applied).
B.4 THE LINEAR CONVOLUTION REGRESSION PROBLEM
For the ease of theoretical analysis, in Lemma I and Propositions to we consider simplified linear convolution regression problem follows,
8T arg min [[Ca(A) XW y 0=(a,W]
where we are given continuous labels y and use sum-of-squares loss E(g.v) = y11 instead of the cross entropy loss used for node/pixel classification. We also assume linear GNN/CNN se= (i) X) C. (A) is used, where C., (A) the convolution matrix which depends on the adjacency matrix A and the parameters E RP, and W is the learnable linear weights with d elements (hence, the complete parameters consists two parts, i.e., [a, W]).
As explained in Appendix B.2, this linear convolution model fo=ja, w1 C, (A)XW already generalizes a wide variety of GNNs and CNNs. For example, it can represents the (single-layer) graph convolution network (GCN) (Kipf & Welling, 2016) whose convolution matrix is defined as C(A) カー AĀ- where À and D are the "self-loop-added" adjacency and degree matrix (for
16

---

Under review as a conference paper at ICLR 2023
GCNN there is no learnable parameters in C,4) omit a:). It also generalizes the oie-dimeali convolution neural network (ID-CNN), where the convolution matrix is (A( - > k== and P is the cyclic permutation matrix correspond a unit shift.
[0] P
is important to note that although we considered this simplified linear convolution regression problem in some of our theoretical results, which is both convex and linear. We argue that most of the theoretical phenomena reflected by Lemma and Propositions to 3 can be generalized to the general non-convex losses and non-linear models; see Appendix C.4 for the corresponding discussions.
C PROOFS AND EXTENDED THEORETICAL RESULTS
In this section, we provide the proofs to the theoretical results Lemma 1 and Propositions to 3 and Theorem 1, together with some extended theoretical discussions, including generalizing the linear convolution regression problem to non-convex losses and non-linear models (see Appendix C.4).
To proceed, please recall the linear convolution regression problem defined in Appendix B.4, the achievability of gradient-matching objective (Eq. (2)) defined as Assumption I in Section 2.3.
C.I VALIDITY OF STANDARD DATASET CONDENSATION
As the first step, we verify the validity of the standard dataset condensation (SDC) using the gradient- matching objective Eq. (2) for the linear convolution regression problem.
Lemma 1. (Validity of SDC) Consider least square regression with linear convolution model [w X) C(A)XW parameterized by W. If gradient-matchinn objective of fw is achievable, then the optimizer on the condensed dataset S, Le.. W = arg minw Ls(W)) ) is also optimal for the original dataset, i.e., (TWS)) minw (TW)).
Proof. In the linear convolution regression problem, sum-of-squares loss is used, and (T(W) = |ICWW-yi -yll (similarly (W) | CC'''Wy''l3 where C' C(A'). We assume X C' Rdxd invertible and we can apply the optimizer formula for ordinary least square (OLS) regression find the optimizer W of CT (W) as,
CX
W C
Also, we can compute the gradients of (T(W) w.r. W as,
V 2X CTT (CXW-
and similarly for VwLs(WW..
Given the achievability of the gradient-matching objective of fw, know there ists non-degenerate trajectory (W; which spans the entire parameter space, i.e., span(W"5 ... W = R2d, such that the gradient-matching loss (the objective of Eq. (2) without expectation) on this trajectory is O. Assuming ((,,)) is the L2 norm (Zhao et al., 2020), this means, WW LWW,) for E E
Substitute in the formula for the gradients V CT (W) and Cs"), we then have,
T CT (CXWS y) = X'T TT (C'X'W, -y) for [T]
Since the set of (WS)) Jt=o spans the complete parameter space IR,, we can transform the set of Jiz0 ( E Ra by linear transformation. Meanwhile, set of 7' equations above can transformed to,
vectors (wx, W:S 1==0 W to the set of unit vectors {ef
y) x (C - y') for E [d]. This directly leads to XTCTTX C' and X CTy= x" y'.
X TTCT(CXed
Using the formula for the optimizers T and W above, we readily get, T = C CX) 'X TTOT
C*T -
W.S
And hence,
CT(W)) (
= min L LTW).
which concludes the proof.
17

---

Under review as a conference paper at ICLR 2023
Despite its simplicity, Lemma directly verifies the validity of the standard dataset condensation on some specific learning problems. Although the formulation of formulation (Eq. (2)) is an efficient but weaker formulation than the bilevel formulation of SDC (Eq. (1)), we see is strong enough for some the linear convolution regression problem.
C.2 GENERALIZATION ISSUES OF SDC
Now, we move forward and focus on the generalization issues (the gradient-matching formulation of) the standard dataset condensation (SDC) across GNNs.
To start with, we prove the successful generalization of SDC across ID-CNNs as follows, which is very similar to the proof of Lemma 1.
Proof of Proposition In Proposition 1, we consider one-dimensional linear convolution models f2k+1(x) = (Ei=k- a (k) ph) JWW parameterized by a E IP and W E IR (where p = 2K 1).
If we denote,
k= K Σ
C=
pk
and 0 =
la, W] E RD-d Ia,
k=-K K
then from the proof of Lemma we know the gradients of (T(W) w.r. W is again,
Vw 2x E (CXW-
We know the achievability of the gradient- matehinn objective means there exists a non-degenerate trajectory (0S) )E=0 which spans the entire parameter space, i.e., span(O), o = IRtd By
decomposing o5 into [of,, WF). we know that there exists (af) T-1 which spans R2' and there exists (WS))=) which spans IRd.
Since the gradient-matching objective is minimized 0 (WS))=) which spans gd following the same procedure as the proof of Lemma I, we again obtain,
x xCcTy=
Mean while, since the same gradient-matching matching objective is also minimized to 0 on (a which spans R2, we have,
k= K
(4) T y' for te [T]. k=-k
k=k Σ
T
Σ
(a (4))
y X
K
Again by linear combining the above T equations and because (af)T= be transformed the unit vectors in R", we have,
X (Ph) y
( X T for == -K,..... K.
Hence, for any new trajectory (a (a which spans Re' where p' = 2K' + 1, by linear combining the above equations, have,
K TT
Σ (0(5)(() y= X"T y= K
k=k (at5)(t)pu))
T y for LE (T).
Σ
With similar procedure for the X CT part, we conclude that on the new trajectory (T:))T=)
T-1
Vw Ww W).
remains to prove that on any new trajectory V VaCy(a, W) VaCs(a, W). Only need to note that,
Va Cy (a, W) = 2W P -y)
Hence, by the p equations above we can readily show,
xT pkp X plky' for k = - = K,...,K
18

---

Under review as a conference paper at ICLR 2023
Again with similar procedure for the X XT CX part, we finally show that the new trajectory (
T-1
VaCT(a, W) = VaLs(a,
This concludes the proof.
Then we focus on the linear GNNs, we want to verify the insight that the learned adjacency A' of the condensed graph has "too many degrees of freedom" so that can easily overfit the gradient-matching objectíve, no matter what learned synthetic features X' are. Again, the proof of Proposition 2 uses some results in the proof of Lemma
Proof of Proposition 2: Now, we consider a linear GNN defined as f(A,X = C(A)XW. From the proof of Lemma we know that for the gradient-matchngg objective of be achievable, is equivalent to require that,
X'TCX=""CCCC and xTc y=cy= y
where C and C' refer C(A) and C(A') respectively.
Firstly we note that once we find C" and X' such that satisfy the first condition XTC X CT X',', can always find y' Re such that X X C'T y since yEyis a scalar.
Now, we focus finding the convolution matrix C' and the node feature matrix X' of the condensed synthetic graph to satisfy X C = = C' X'X". We assume n > c > and consider the diagonalization of X T CX gdxd, Since XTC CX is positive semi-definite, it can be diagonalized as X C' CX VS where V E Rd is an orthogonal matrix and S E IR is diagonal matrix that
diag(s1,.....
For any (real) semi-unitary matrix U E Rexd such that U = Id, we can construct C'X' = USV E Reed and we can easily verify they satisfy the condition,
C' VSSUUSV
= = cx
Then since X' is full ranked, for any X', by considering the dingular-valus decomposition of X', we that we can always find a convolution matrix C' such that C" X' USV and this concludes the proof.
Finally, we use some results of Proposition 2 to prove Proposition the failure of SDC when generalizating across GNNs.
Proof of Proposition 3: We prove by steps.
For the first step, we aim to show that there always exist a condensed synthetic dataset S such that achieves the gradient-matching objective but the learned adjacency matrix A' Le is the identity matrix. Clearly this directly follows form the proof of Proposition 2, where we only require C'X' = USV (see the proof of Proposition 2 for details). If the learned adjacency matrix A' Ic- the for any GNNs, the corresponding convolution matrix C' is also (or proportional to) identity, thus we only need to set the learned node feature matrix X' USV satisfy the condition. The first step is proved.
For the second step, we evaluate the relative estimation error of the optimal parameter when transfer to new GNN f with convolution filter C(.), i.e., ! - - [I/I[W/ [|- Using the formula for the optimal parameter in the proof of Lemma again, we have,
W exx
and
W (X"T e ex y',
where e C(A') E(L.) C(I.) (the last equation the fact that the convolution matrix of GNNs are the same the underlying graph is identity).
Moreover, by the validity of SDC on fC. know, (see the proof of Lemma 1 for details),
xT = xTx and = x
19

---

Under review as a conference paper at ICLR 2023
Thus, altogether derive that X" X XTcTx and X X. And therefore,
=x -X
Now, note that,
[ W 1
[e(A)]
oma (Q) 1, min (imm((1)) (Q))
where Q (CTTCCC
This concludes the proof.
C.3 VALIDITY OF HCDC
Finally, we complete the proof of Theorem with more detials.
Proof of Theorem 1: Firstly, we prove the necessity by contradiction.
If there exists Ao E s.t. the two gradient vectors are not aligned at Ao then there exists small perturbation AAg such that L (Ao + AAo) Li (Ao) and L + AAo) (As()) have different signs.
Secondly, we prove the sufficiency by path-integration.
For any pair X * A Å, have path 7 A2) Å from Ag and X then integrating hypergra- dients (A) along the path recovers the hyperparameeter-calibraaiii condition. More specifically, along the path have (71) ()2) ((nn)))) (A)A (similar for (x) Thus we have,
(CT( - (3(0))))))))) - (3)(2))
( Micinoo VALT( (
(2(A))))) V2L3(A)d1)
(V (AL3(A))
20
the second last inequality by Cauchy-Schward inquality and the last inequality by cos( (A), (A);(A) 0 for any À A2) E A.
This concludes the proof.
C.4 GENERALIZE TO NON- NON-CONVEX AND NON-LINEAR CASE
Although the results above are obtained for least squares loss and linear convolution model, it still reflects the nature of general non-comvex losses and non-linear models. Since dataset condensation is effectively matching the local minima {07] the original loss Ctrain (0, v²) with the local minima (0S} of the condensed loss Ltrain (8, }²), within the small neighborhoods surrounding the pair of local minima (ØT, 8²), one respectively. Hence the generalizability issues with convex loss and liner model may hold.
approximate the non-convex loss and non- con-linear model with convex/linear
D EXTENDED RELATED WORK
This section contains the extensive discussions of many related work/areas which cannot be fitted into the main paper due to the page limit.
D.1 DATASET CONDENSATION AND CORESET SELECTION
Firstly, we review the two main approaches to reducing the training set size while preserving model performance.
20

---

Under review as a conference paper at ICLR 2023
Dataset condensation (or distillation) is first proposed in (Wang et al., 2018) a Bearningtto-lem problem by formulating the network parameters as a function of synthetic data and learning them through the network parameters to minimize the training loss over the original data. However, the nested-loop optimization precludes it scaling up to large-scale in-the-wild datasets. Zhao et al. (2020) alleviate this issue by enforcing the gradients of the synthetic samples w.r.t. the network weights to approach those of the original data, which successfully alleviates the expensive unrolling of the computational graph. Based on the meta-learning formulation in (Wang al., 2018), Bohdal et al. (2020) and Nguyen et al. (2020; 2021) propose to simplify the inner-loop optimization of a classification model by training with ridge regression which has a closed- form solution, while Such et al. (2020) model the synthetic data using generative network. To improve the data efficiency of synthetic samples in gradient-matching algorithm, Zhao & Bilen (2021a) apply differentiable Siamese augmentation, and Kim et al. (2022) introduce efficient synthetic-data parametrization. Recently, a new catributtionmmacchin framework (Zhao & Bilen, 2021b) proposes to match the hidden features rather than the gradients for fast optimization, but may suffer from performance degradation compared to gradient-matching (Zhao & Bilen, 2021b), where Kim et al. (2022) provide some interpretation.
Graph condensation (Jin et al., 2021) achieves the state-of-the-- art performance for preserving GNNs' performance the simplified graph. However, Jin al. (2021) only adapt the gradient-matching algorithm of dataset condensation Zhao et al. (2020) to graph data, together with a MLP-based generative model for edges (Anand & Huang, 2018; Simonovsky & Komodakis, 2018), leaving out several major issues on efficiency, performance, and generalizability. Subsequent work aims to apply algorithm (Zhao & Bilen, 2021b; Wang et al., 2022) of
the more efficient Iotribution-matchhin dataset condensation to graph (Liu et al., 2022) or speed up steps (Jin et al., 2022). While the efficiency issue of graph condensation is mitigated (Jin et al., 2022), the performance degradation on medium- and large-sized graphs still renders graph condensation practically meaningless. Our HCDC is specifically designed for repeated training in architecture search, which is, in contrast, well-motivated.
graph condensation by
reducing the number of
Coreset selection methods choose samples that are important for training based on heuristic criteria, for example, minimizing the distance between coreset and whole-dataset centers (Chen et al., 2010; Rebuffi et al., 2017), maximizing the diversity of selected samples in the gradient space (Aljundi et al., 2019), discovering cluster centers (Sener & Savarese, 2018), and choosing samples with the largest negative implicit gradient (Borsos et al., 2020). Forgetting (Toneva et al., 2018) measures the forgetfulness of trained samples and drops those that are not easy forget. GraNd (Paul et al., 2021) selects the training samples that contribute most to the training loss in the first few epochs. Prism (Kothawade et al., 2022) select samples maximize submodular set-functions which are combinatorial generalizations of entropy measures (lyer et al., 2021). Recent benchmark (Guo et al., 2022) of a variety of coreset selection methods for image classification indicates Forgetting, GraNd, and Prism are among the best performing corset methods but still evidently underperform the dataset condensation baselines. Although coreset selection can be very efficient, most of the methods above suffer from three major limitations:
(I) their performance is upper-bounded by the information in the selected samples; (2) most of them do not directly optimize the synthetic samples to preserve the model performance; and (3) most of them select samples incrementally and greedily, which are short-sighted.
D.2 GRAPH REDUCTION
Secondly, we summarize the traditional graph reduction method for graph neural network training.
Graph coreset selection is non-trivial generalization of the above method coreset methods given the non-iid nature of graph nodes and the non-linearity nature of GNNs. The very few off-the-shelff graph coresct algorithms are designed for graph clustering (Baker et al., 2020; Braverman et al., 2021) and are not optimal for the training of GNNs.
Graph sampling methods (Chiang et al., 2019; Zeng et al., 2019) can be as simple as uniformly sampling a set of nodes and finding their induced subgraph, which is understood as graph-counterpart of uniform sampling of tid samples. However, most of the present graph sampling algorithms (e.g.. ClusterGCN (Chiang et al., 2019) and GraphSAINT (Zeng et al., 2019)) are designed for sampling multiple subgraphs (mini-batches), which forms a cover of the original graph for training GNNs
21

---

Under review as a conference paper at ICLR 2023
with memory constraint. Therefore those graph mini bati-bbtch sampling algorithms are effectively graph partitioning algorithms and not optimized to find just one representative subgraph.
Graph sparsification (Batson et al., 2013; Satuluri et al., 2011) and graph coarsening (Loukas & Vandergheynst, 2018; Loukas, 2019; Huang ct al., 2021; Cai et al., 2020) algorithms are usually designed preserve specific graph properties like graph spectrum and graph clustering. Such objectives are often not aligned with the optimization of downstream GNNs and are shown to be sub-optimal in preserving the information train GNNs well (Jin et al., 2021).
D.3 OTHER RELATED AREAS
Lastly, we list two important relevant areas to this work, implicit differentiation methods based on the implicit function theorem (IFT), and the differentiable neural architecture search (NAS) algorithms.
Implicit differentiation methods apply the implicit function theorem (IFT) to the rested-optimization problems (Ochs et al., 2015; Wang et al., 2019). The IFT requires inverting the training Hessian with respect to the network weights, where early work either computes the inverse explicitly (Bengio, 2000; Larsen et al., 1996) or approximates it as the identity matrix (Luketina et al., 2016). Conjugate gradient (CG) is applied to invert the Hessian approximately (Pedregosa, 2016), but is difficult to scale deep networks. Several methods have been proposed to efficiently approximate Hessian inverse, for example, 1-step unrolled differentiation (Luketina et al., 2016), Fisher information matrix (Larsen et al., 1996). NN-structure aided Kronecker-factordd inversion (Martens & Grosse, 2015). Lorraine et al. (2020) use the Neumann inverse approximation, which is a stable alternative to CG (Shaban et al., 2019) and successfully scale gradient-based ootiiiziott to large networks with constant memory constraint. It is shown that unrolling differentiation around locally optimal weights for steps is equivalent to approximating the Neumann series inverse approximation up to the first terms.
Differentiable NAS methods, e.g., DARTS (Liu et al., 2018) 8) explore the possibility of transforming the discrete neural architecture space into a continuously differentiable form and further uses gradient optimization to search the neural architecture. DARTS follows a cell-based search space (Zoph et al., 2018) and continuously relaxes the original discrete search strategy. Despite its simplicity, several work cast double on the effectiveness of DARTS (Li & Talwalkar, 2020; Zela et al., 20.9). SÑAS (Xie al., 2018) points out that DARTS suffers from the unbounded bias issue towards its objective, and it remodels the NAS and leverages the Gumbel-softmax trick (Jang et al., 2017; Maddison et al., 2017) to learn the exact architecture parameter. Differentiable NAS techniques have also been applied to graphs to automatically design data-specific GNN architectures (Wang et al., 2021; Huan et al., 2021).
E IMPLEMENTATION DETAILS
In this section we list more implementation details on the experiments in Section 6.
For the synthetic experiments on CIFAR-10, we randomly split the CIFAR-10 images into M = 20 splits and perform cross validation. For the baseline methods (Random, SDC-GM, SDC-DM), the dataset condensation is performed independently for each split. For HCDC, we first condense the training set of the synthetic dataset by SDC-GM. Then, we learn a separate validation set of with 1/M-size of the training set and train with the HCDC objective on the M-HPO trajectories as described in Section 4. We report the correlation between the ranking of splits (in terms of their validation performance on this split). For the Farly-Stopping method, we only train the same number iterations as the other methods (with the same batchsize), which means there are only e/n * 500 epochs.
For the experiments about finding the best convolution filter on (large) graphs, we create the set of ten candidate convolution filters (see Table 4 for definitions and references) GCN, SAGE- Mean, LAGE-Max. GAT, GIN-c, GIN-O, SGC(K=2), SGC(K=3), ChebNet(K=2),, ChebNet(K-3). The implementations are provided by PyTorch Geometric https: /ttp/pyyoccct www.orreeheeeeeeeeeeeeeeeoeoeeee arii. readt hedocs. 1 en/ eatest/ /modules milles/nn /n. html. We also select the GNN width from (128, 256} and the GNN depth from {2, 4) so there are 10 x 2 2 40 models in total.
22

---

Under review as a conference paper at ICLR 2023
For the experiments about speeding up off- sffftf graph architecture search algorithms, adopt GraphNAS (Gao et al., 2019) togher with their proposed search space from their official repository https://githut. Nom/GraphNAS, GrapaaasS..a....Saaa We apply to Ogbn-arxit with condensation ratio Ctrain/ n = 0.5%.
23


Reviews:
[{"review_id": "xlATmJ0wBT7", "reviewer": "Reviewer_C3Kq", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a new graph condensation method (HCDC) for fast hyperparameter/architecture search by aligning the hyperparameter gradients. As in the paper, the proposed method is theoretically and experimentally proven to be effective on preserving the validation performance rankings of GNNs.", "summary_of_the_review": "I think the task is interesting, and due to the readability of the paper, it is hard to justify the contribution.", "strength_and_weaknesses": "Strength:\n\nThe task is novel and there are many potential applications for the use cases of the proposed method.\n\nWeakness:\n\nThe paper is hard to read and have many confusing parts:\n\n1) The paper is about hyperparameter search on GNN, but the experiment is on Cifar10. \n\n2) The proposed method seems be used for constructing validation data only. According to the paper, the training data condensation is using other graph condensation methods. This brings the question of why not using the proposed method for training graph condensation? and what if performing NAS on the distilled graph generated by other graph condensation methods to search for hyperparameters?\n\n3) The experiment result also seems confusing. For example, in Table 3, are the results on the distilled training graph as the ratio is on the n_train? to my understanding, the training graph is generated by other graph condensation method. Then how to choose the graph condensation method for training?\n\n\n\n\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bsgo6ROG2Vp", "reviewer": "Reviewer_ny5k", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper solves a problem of hyperparameter search for a graph neural network using calibrated dataset condensation. The authors propose a novel hyperparameter-calibrated dataset condensation framework by matching hyperparameter gradients in synthetic validation data generation. Unlike the standard dataset condensation, the proposed method is more robust for an overfitting issue, in particular for graph structures. Finally, the experimental results are demonstrated to show the validity of the proposed method.", "summary_of_the_review": "Please check the above text boxes.", "strength_and_weaknesses": "Here the strengths and weaknesses of this work are described.\n\n## Strengths\n\nIt solves an interesting problem regarding graph neural networks in the perspective of hyperparameter optimization.\n\nThe arguments of this work is well-supported by thorough analyses and diverse evidences.\n\n## Weaknesses\n\nI think that presentation and writing can be improved more. The current version is okay, but some expressions need to be polished. In particular, there are too many terms with a dash \"-\", which makes sentences complicated. Also, a calligraphic \"C\", which stands for another convolution filter, is somewhat confusing with \"C\". I know that you can prefer your own expressions to write your paper, but these can be improved regardless of my suggestions. Moreover, I think \"test\", \"cos\", or any similar terms should be a regular font; please check them out carefully.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "R4gepBbRIw", "reviewer": "Reviewer_RKbd", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes the graph condensation method for hyperparameter search. The proposed HCDC algorithm optimizes synthetic validation data as well as training data so that the obtained optimal hyperparameter on synthetic data shows good performance on the original validation set. They theoretically analyze previous approaches and verify existing methods can overfit to specific models and fail to generalize over other models. To overcome this issue, the paper proposes a new objective that matches hyperparameter gradients. The paper shows the effectiveness of their method on GNN convolutional filter search.  ", "summary_of_the_review": "The paper proposes a novel approach on dataset condensation by matching hypergradient. There are some promising experimental results. However, the paper requires consistent and more concise notations for readability. Also, the final algorithm is not described in detail and the paper lacks some important experimental analysis, e.g., time complexity, optimization results of other hyperparameters, comparison to hyperparameter optimization by hypergradient. Due to these reasons, it is hard to understand their method fully. \n\n-------\n\n**Post rebuttal**   \n   \nAfter reading the authors rebuttals, I still have some major concerns. \n- In response 4, authors said their main contribution is to find a condensed dataset that preserves the validation performance ranking of architectures, and thus it is not directly comparable to hypergradient optimization methods. However, I still believe the paper should compare with the hypergradient optimization methods to demonstrate the effectiveness of the proposed approach. (the proposed method requires to compute the hypergradient with the original training set, so if the direct use of the hypergradient is more effective, then why should we use the proposed approach for NAS?\n- In response 3.2, authors said it takes about 531 seconds for condensation before NAS. However, this is much larger than the time spent for search in Figure 4 (140 seconds) and it is unclear whether the proposed method is effective. Authors should reflect this on Figure 4. \n- In response 1.2, authors mention that the focus of this paper is on the architecture hyperparameters, not general hyperparameters (learning rate). Then, the terms like HPO in the paper seems not appropriate, and I think the writing should be revised by only considering NAS, not HPO. \n\nFrom the reasons above, I maintain my score.\n", "strength_and_weaknesses": "**Strength**\n- The proposed idea matching the hyperparameter gradient is novel.\n- The paper presents the problems of the existing methods theoretically and experimentally.\n- The experimental results on GNN convolutional filter (Table 3) are promising. \n\n**Weakness**\n- **It is hard to follow the paper.** There are too many notations that are often not consistent. For example, (page 3) $\\theta^S(S,\\theta_0)$ and $\\theta^T(\\theta_0)$, (page 5) $\\lambda^S$ and $\\lambda^S(S)$. Why do the same notations have a different number of arguments? This makes me confused.   \nAlso, the paper considers various hyperparameters (network type, width, learning rate; on page 5), but their mathematical notations of the paper only cover a very limited class of hyperparameters: $f_{\\theta, \\lambda}:R^{n\\times n}\\times R^{n\\times d} \\rightarrow R^{n\\times K}$, where $\\lambda$ is a hyperparameter. Based on this, they define the loss function as $L(\\theta, \\lambda)$, but general hyperparameters cannot be the argument of the loss function. For example, the learning rate is the argument of the learning algorithm, not the loss function. This inconsistency between the claims and explanations reduces the readability of the paper.   \n- **Algorithm is not described in detail.**  The paper uses the existing hypergradient method but differentiating the hypergradient is not trivial (see eq. (IFT) on page 7). However, the authors do not elaborate on the process. It would be informative if the authors provide the complexity analysis of the algorithm and error analysis by hypergradient approximation.   \nAlso, the authors should summarize and present the final algorithm, which is currently absent. It is unclear how the synthetic training set and validation set are optimized. (Do they optimized sequentially?)\n- **Experimental analyses are insufficient.** They conduct a synthetic experiment, finding the best cross-validation fold, but it is hard to understand the meaning of this experiment. (HCDC optimizes the validation set, and it is unclear what is the evaluation metric). Rather than synthetic experiments, the experiments in realistic settings (e.g., other types of hyperparameters and other domains or tasks) will be much more informative.   \nAlso, there is no computational cost analysis of the condensation algorithm. Figure 4 compares the search process speed on synthetic and original data, but it is unfair because it does not consider the time for optimizing the synthetic set. \n\nFurther questions.\n- The proposed method requires calculating hypergradient on the original training set. What is the benefit of the proposed method over the method directly using the hypergradient to optimize the hyperparameter? \n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CkcbNifYDu", "reviewer": "Reviewer_K3vn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper addresses the problem of node classification in graphs,\nesp. via graph condensation, i.e., finding a smaller graph on which\nmodels can be learnt and perform well on the whole graph\nnevertheless. The authors show that previous approaches (Jin et al.\n2021) that match loss gradients do not work well across different\ngraph neural network (GNN) architectures. Therefore they\npropose to match validation loss hyperparameter gradients\ninstead. They apply a method from the literature (Lorrainne et al. 2020)\nto compute those gradients efficiently. In experiments they\nshow that their method better ranks hyperparameters w.r.t.\ntheir performance on the whole graph and outperforms\nexisting baselines on four different datasets by up to 1.9\n(absolute) %.\n", "summary_of_the_review": "I see three issues:\n\nw1. differences in the experiments w.r.t. published work.\n  In the experiments, esp. tab. 3, performances are compared\n  against the baseline model GCond (Jin et al. 2021), but there are\n  major differences to the published numbers in the baseline paper, e.g.\n  a. the dataset Flickr is dropped. Often different reduction ratios\n      are used. \n  b. the whole graph performance is different, e.g., for\n      ogbn-arxiv you have 73.2, they have 71.4.\n  c. the performance for the random baseline and for the baseline\n      GCond differ, e.g., for ogbn-arix 0.25% and 0.5% you report\n      70.5 and 71.1, they report 63.2 and 64.0.\n\n  Is there an experimental condition changed that explains these\n  differences? And if so, could you reproduce their results and\n  compare head-to-head also?\n\nw2. claim of training speedup not substantiated.\n\n  The authors argue that by dataset condensation they could speed\n  up training.\n  While no one doubts that training on smaller graphs will take less time\n  than training on larger graphs, to substantiate the claim that dataset\n  condensation speeds up the training process one would have to compare\n  the sum of the training time on the smaller graph and the time needed\n  for its condensation to the training time on the larger graph. Is there\n  really a speedup? And if so, how large is it?\n\nw3. The extended hyperparameter search space \\tilde\\Lambda is not clear\n  to me.\n\n  What exactly is it, as a space, \\R^p ? And how do you map\n  between its elements and the p many hyperparameters in a\n  differentiable manner? \n\n", "strength_and_weaknesses": "s1. interesting problem setting: graph condensation.\ns2. clearly identified limitation in current work (overfitting hyperparameters)\n  and plausible approach to overcome it. \ns3. good experimental results.\n\nw1. differences in the experiments w.r.t. published work.\nw2. claim of training speedup not substantiated.\nw3. the extended hyperparameter search space \\tilde\\Lambda is not clear\n  to me.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject