Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the graph condensation problem for GNN training, in which a large graph is condensed into a small synthetic graph, and the GNN trained on the small graph is expected to perform similar to the GNN trained on the large graph.

Technically, the overall framework follows the gradient matching method, but specific parameterization is proposed for optimizing the small synthetic graph.

main_review: Strength:
- The paper is easy to follow and overall well-organized.
- The method is sound.
- Various experiments are conducted, including the generalization experiments 

Weaknesses:
- The overall method is similar to the existing gradient matching method. The innovation is limited, but the setting is new for applying this method.
- Compared to the existing gradient matching method for data condensation, the major difference in graph problem is the new parameterization for the adjacency matrix A' and X'. The authors claim that it is important to parameterize A' as a function of X'. However, experiments are not conducted to support this very important claim.

Questions:
- What if A' and X' are treated as free parameters? What if A' is independent of X'? For example, we can set $A_{ij}'= relu( W_{ij} - \delta )$ where $W_{ij}$ is a free parameter to replace equation (7). What's the performance of this approach, in terms of both the optimization efficiency and the test performance?
- Experiments use GNNs with 2 layers. What if more layers are used? Intuitively, using fewer layers (e.g., 0 layer in the extreme case) will reduce this problem to the normal data condensation problems on non-graph data. What if a deeper GNN is used so that the graph structure plays a more important role?
- Some statements are not clear enough. For example, for the $\theta_t$ in equation (5), it only mentions this replaces the $\theta_t^S$ and $\theta_t^T$ (I believe there is a typo under equation (5), too). However, how $\theta_t$ is computed is not mentioned. Taking the average of $\theta_t^S$ and $\theta_t^T$? 

summary_of_the_review: - Pro: The method is sound.
- Con: The method is similar to the existing gradient matching method, but the graph setting is new.
- Con: Experiments can be improved:
-- Ablation study is needed to verify the effectiveness of the proposed parameterization.
-- Experiments on deeper GNNs can better demonstrate the method.

My score is actually between weak rejection and weak acceptance. I will consider increasing my score to weak acceptance if experiments can be improved.

---post rebuttal

The new experimental results in the revised paper have addressed my concerns so I choose to raise the score to 6.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: To alleviate the storage and time consumption for training GNN models on large graphs, the paper studies graph condensation, which draws inspirations from data distillation/condensation. It first constructs a much smaller synthetic graph, and then train GNN models on this small graph. Empirical results show that, graph condensation can reduce the size of the graph by 99% but still achieves comparable accuracy.
main_review: Strengths:
1. The idea of using data condensation/distillation on GNNs is new and interesting. 
2. The empirical results looks quite promising. It is impressive that the compression ratio can be more than 100, and the testing accuracies remain competitive in many cases.
3. Empirical results show that the synthetic graph constructed based on SGC work well across different models. This generalizability is a useful property of this technique.
4. The paper is well-written.

Weaknesses:
1. Although applying condensation techniques on GNNs is new and some technical details need to be taken care of, the main ideas still follow previous work, e.g. the gradient matching loss.
2. The aim of graph condensation is to alleviate the storage and time consumption. However, to construct the smaller graph, one still needs to train a GNN model on the original graph, which still requires sampling methods for large graphs. I think the authors should provide more discussions on the computation costs of the condensation process. 
3. On more complicated datasets such as OGB-arxiv, the accuracy gap is still quite noticeable. And it seems difficult to improve the accuracy by using larger condensed graph size, since it would become more difficult to train the parameters in the synthetic graph.
summary_of_the_review: Overall, I think graph condensation is a new and interesting direction, and the empirical results presented in the submission are generally encouraging. On the other hand, given previous work on data condensation, the novelty of the current method is not significant.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper introduces GCond, a graph condensation framework designed to compress graph datasets and reduce storage and time requirements while training GNNs on large-scale graphs. GCond makes use of gradient matching and graph sampling to reduce the graph size. Experiments demonstrate that GCond can maintain a high degree of accuracy while significantly lowering the size of the graph.
main_review: Strength:
1. This paper is generally well-written and easy to follow.

2. The paper's motivation is clear.

3. Extensive experiments are conducted to demonstrate the model's effectiveness.

Weakness:
1. This paper attempts to extend the Dataset Condensation model and Gradient Matching technique presented in [1] to the domain of GNNs. Although some differences exist, they are so minor that the main equations (1) - (5) in this work are nearly identical to equations (4), (5), and (7) - (9) in [1]. As a result, I believe this work lacks innovation in terms of technical contribution.

[1] Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. https://openreview.net/pdf?id=mSAKhLYLSsl.


2. In Section 3.2, the authors claim that GCond-X, which only learns the condensed node features X' and not the condensed graph structure A', also performs well. This observation leads me to wonder if the proposed method is better suited for *dataset* condensation rather than *graph* condensation.

3. The paper makes no attempt to analyze the algorithm's complexity or to report its runtime.

Minor comments:
1. In equation (3), the letter 'D' should be in the mathematical font. 

2. On page 4, line 1, it appears that the phrases '[...] and unrolling the entire training trajectory of the inner problem' have been omitted or repeated. 

3. Page 6, Evaluation section, line 3: 'With r percent of N nodes'. Here r should be a number between 0 and 100, and yet it is a percentage in Table 2. 

4. All 'r=...' in the supporting materials appear to be in a non-math typeface.
summary_of_the_review: The paper's idea is interesting, as evidenced by the experimental results. However, the theoretical depth and novelty may not be enough to meet ICLR's standards.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes and addresses the problem of graph condensation. In a nutshell, provided a large graph G, the scope of the paper is to propose a solution able to generate a smaller synthetic graph G’, which effectively allows to train Graph Neural Networks (GNNs) able to achieve similar performance as if they were trained on G. In order to do that, the authors propose to match the gradients produced by a specific GNN on mini-batches extracted from G and G’. This avoids the need of constructing a minimization problem based on an outer and inner training loop which would be computationally heavy to handle. The node-wise features X’ of the smaller graph G’ are considered as free parameters in the optimization process and the adjacency matrix A’ is instead inferred from X’ via a learnable MLP which is trained alongside X’ with an alternating optimization schema. The authors evaluate the quality of their approach on the Cora, Citeseer, OGBN-Arxiv and Reddit datasets, condensing and evaluating the new graphs with a variety of different architectures. 
main_review: Overall, I personally found the idea of the problem presented in the paper intriguing. Being able to shrink large datasets to smaller ones in order to allow an easy training and tuning of a variety of approaches is something that would for sure help both in academic and industrial settings. 

This said, I’m not sure the solution proposed in the paper fully addresses the problem. In order to make the new condensed graphs actually useful for training and tuning, we would need a variety of different GNNs to actually approach their original performance when actually trained on the smaller synthetic graphs or at least to show the same order of performance (i.e. if performance of GNN1 are better than GNN2 when trained on the original graph, they should also be better when trained on the synthetic graph), so that we could for instance tune a variety of different architectures on the smaller condensed graphs G’ and then re-train only the best performing one on the original datasets. However, these conditions don’t seem to be satisfied for a variety of approaches. Besides for GCN, which achieves in 4 out of 5 datasets performance which are reasonably close to the ones it would have if trained on the original graphs, the generalizability of condensed graphs to different architectures doesn’t seem particularly strong as outlined in Table 3. For instance, Graph Attention Network which achieves 83% on the original CORA, it achieves only 66.2% on the condensed one with SGC and, in addition to this, it is actually outperformed by GCN which instead achieves lower performance than GAT if trained on the original dataset (a similar, although less marked, comparison could be made for APPNP as well, which is outperformed by GCN both on Citeseer and Cora, while outperforming it if trained on the original datasets as per https://arxiv.org/pdf/1903.02428v3.pdf). This is most likely due to the way in which the condensed graphs are constructed (i.e. via SGC), which intrinsically pushes the condensed graph to perform well for the model used at condensation time (or models which are reasonably similar to this one, e.g. GCN) but it doesn’t offer any guarantee for reasonably different models. 

For this reason, while I personally think that the problem outlined in paper is of interest to the community, I’m not sure the solution proposed in the manuscript is mature enough for pushing for an acceptance to ICLR.

In addition to this, there are a variety of other points that I would like to highlight in my review and which I would like the authors to address in their rebuttal:

1) Equation 6, the distance measure boils down to the sum of one minus the cosine similarity between the columns of the two different gradients. Why did the authors choose that specific distance and not for instance an L2 distance? What is the effect of that distance on performance of the approach?

2) In the graph sampling paragraph of subsection 3.1, the authors state “To further reduce memory usage and ease optimization, we calculate the gradient matching loss for nodes from different classes separately, as matching the gradients w.r.t. the data from a single class is easier than that from all classes.”, however there is not really an explanation in the paper why this would be easier. Do the authors match gradients on each class separately as they want nodes of the same class to provide the same information? why? I believe the approach should work even if we aggregate the gradients on all samples from different classes.

3) In the same subsection as for points 2, the authors also state “For the condensed graph A’, we sample a batch of synthetic nodes of class c but do not sample their neighbors as we need to learn the connections with other nodes.”. Does this imply that their model will learn connections only across the sampled nodes at each step instead of out of the entire pool of available nodes?

4) The authors evaluate their approach on Cora and Citeseer (among the other datasets) but they didn’t consider PubMed which is typically used in experimental evaluations alongside these two. Is there a specific reason why the authors decided to skip PubMed in their experimental evaluation?

5) In Section 4.1 the authors state “As vanilla DC cannot leverage any structure information, we develop a variant named DC-Graph, which additionally leverages graph structure during test stage, to replace DC for the following experiments.”. However, as for DC-Graph the authors use only the identity matrix on the condensed graph at training time, while they use the whole original graph at test time, it is unclear how DC and DC-Graph differ at test time. Did the authors discard the connectivity of the original graph during testing when evaluating a model trained on graph condensed with DC? If that is correct, why?

6) Section 4.3, paragraph “Different Architectures” is quite unclear. I believe the authors are showing the performance that different architectures tested with graphs condensed with SGC allow to achieve, however these numbers don't match the ones reported in table 4 for ChebNet. I believe this is just a typo and I would ask the authors to please confirm this and if I'm correct to fix the error in the table. Additionally, I would kindly ask the authors to please report the performance that the considered models were able to achieve on the original graphs. It would greatly help at highlighting the variation in performance of the approaches wrt the ideal scenario (i.e. where we train and test them on the same graph)

7) Section 4.3, paragraph “Versatility of GCOND”, the authors omit GAT out of the comparison showing the performance of a graph condensed with a GNN but then used for training with a different one because of its “deterioration in performance with large neighborhood sizes”. However, this doesn’t appear to me as a sufficient justification for omitting GAT altogether and if this fails at performing well in those specific conditions it should probably be shown in the table with the other methods.  Additionally, couldn't we restrict the neighborhood sizes in the condensed graph (e.g. by considering only the K most similar neighbors) before training GAT if this fails to perform well with large neighborhoods?

8) In Table 4, surprisingly a graph condensed with GCN is not the best one for training GCN (the graph condensed with SGC allows to achieve 10% more in terms of accuracy with GCN). This is quite surprising and I wonder if the authors have a justification for this. 

9) Table 5, the graph condensed with SGC for OGBN-Arxiv loses its original homophily. This is probably the reason for the drop in performance, however I was not able to identify in the paper a reason for this. Do the authors have a justification for this behavior?

----

Updated score to 6 after author's rebuttal.
summary_of_the_review: The paper proposes and addresses the problem of graph condensation. While the formulation of the problem is interesting, I didn’t find the approach proposed by the authors to be mature enough for ICLR due to the limitations and issues highlighted in the main review. I thus consider the paper a weak reject for the conference and I kindly ask the authors to reply to the points highlighted in my review in their rebuttal.
review_title: null

Meta-review: This paper addresses the scale issue in Graph Neural Networks by proposing a “condensation” approach that produces a small synthetic graph from a large original graph such that GNNs trained on both graphs have comparable performance. 

Reviewer cTj2 had concerns with novelty: they claimed the proposed method was close to gradient matching. However, they admitted that the graph setting was new. They suggested some clarity and experimental improvements. 

Reviewer R5cV made a similar comment w.r.t. the similarity to gradient matching. Though overall they were more positive than R5cV and thought the idea was interesting and results were compelling.

Reviewer XqrK like the others, argued that the paper “lacked technical innovation in terms of technical contribution”. They pressed for a complexity or runtime analysis. 

Reviewer peGb found the idea and problem “intriguing” though felt the solution fell short. They offered many suggestions for improving the quality of the experiments and the analysis. 

In the discussion period, reviewer peGb raised their score, thanking the authors for answering their questions. They felt that the additional experiment for NAS was relevant and cleared up a key doubt. Reviewer cTj2 updated their score as well but stated it was critical that the author release the code for reproducing the new experimental results. I think that with most reviewers now on the “accept” side of the fence, I am more inclined to recommend acceptance because I do not see any critical flaws. I think that cTj2’s request for code is reasonable and strongly suggest that the authors do so.
Decision: Accept (Poster)