Does Graph Distillation See Like Vision Dataset Counterpart?

Summary

This paper mainly focuses on the Laplacian Energy Distribution (LED) shift problem of graph dataset condensation.

Strengths

The pipeline figure is clear and straightforward. The studied problem, how to condense a graph dataset, is relatively important.

Weaknesses

Compared to existing studies that widely investigated the gradient matching, it seems that the major contribution of this paper is considering the LED shift. Why LED and how can LED benefit? The authors need to provide more analyses and explanation about their motivation. In the Introduction, the authors mention “We empirically find a positive correlation between LED shift and the performance in cross-architecture settings”. This can only be considered as a finding. The motivation for introducing LED is ambiguous, especially given the correlation does not mean causality. The authors simply compare their method with Gcond and consider it as the SOTA. However, there are many works that have been proposed since Gcond. The authors should consider compare with them as well for a comprehensive evaluation of their method. For example, [1, 2, 3, 4, 5] [1] Jin, Wei, et al. "Condensing graphs via one-step gradient matching." Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022. [2] Yu, Ruonan, Songhua Liu, and Xinchao Wang. "Dataset distillation: A comprehensive review." arXiv preprint arXiv:2301.07014 (2023). [3] Liu, Chuang, et al. "Comprehensive graph gradual pruning for sparse training in graph neural networks." IEEE Transactions on Neural Networks and Learning Systems (2023). [4] Zheng, Xin, et al. "Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data." arXiv preprint arXiv:2306.02664 (2023). [5] Yang, Shuo, et al. "Dataset pruning: Reducing training data by examining generalization influence." arXiv preprint arXiv:2205.09329 (2022).

Questions

see above.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

see above.

Summary

This paper proposes a novel method called SGDD for condensing large-scale graph datasets while preserving the original structure information. The proposed method uses a graphon approximation method to broadcast the original structure as supervision for generating the condensed graph structure and optimizes it using an optimal transport method. The proposed SGDD achieves state-of-the-art results on various datasets and tasks.

Strengths

(1) This paper uncovers the issue of Laplacian energy distribution shift during the condensation of graph datasets and shows that previous graph condensation methods that overlook the original structure information can lead to poor performance in cross-architecture generalization and specific tasks. This paper introduces a metric SC to quantify the Laplacian energy distribution issue. (2) A new condensing paradigm in graph condensation. This paper leverages the graphon theory to guarantee the structure information consistency between the original and generated graph, which firstly involves the generated learning fashion in graph condensation. Consequently, the generated structure may capture the native properties of the original structure in comparison to current methods, which benefits the downstream tasks. (3) Extensive experimental results demonstrate the effectiveness of the proposed method. This work includes extensive experiments on three node-level tasks as well as multiple ablation studies. All of the experiments demonstrate superior results. The most appealing result is that this method performs well in a cross-architecture setting, significantly improving the effectiveness of graph condensation. (4) Potential Impact. When the data and model go bigger and bigger, graph condensation may have more applications and research meanings. As the applications and challenges related to graph condensation remain unidentified, this paper may set the stage for future exploration of this problem and inspire the communities to further investigate and may benefit the areas like pruning, LLM with graphs, and NAS.

Weaknesses

(1) The motivation for using JS divergence in the calculation of SC is unclear. There are serval ways of calculating the distance of two distributions. (2) In Figure.2, the author uses the BWGNN without specifying the difference between BWGNN and other backbones. (3) There is another related method called DosCond[1] which is mentioned in the introduction but not involved in the baselines. The reason why not choosing this method for comparison should be specified. [1] Jin, Wei, et al. “Condensing Graphs via One-Step Gradient Matching.” Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022.

Questions

(1) Please detailed the motivation in weakness.1 and weakness.2. (2) Consider adding the baseline mentioned in weakness (3) or specify the reason why do not compare with this method. (3) There is a high variance in the results of SGDD in Table 1. Would changing the backbone potentially improve the overall performance as shown in Table 1?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

(1) In the real world, graphs may contain multiple types of edges, resulting in heterogeneity. However, the current learning methods may fail to capture this heterogeneity, leading to information loss. (2) Lack of discussion on different backbones.

Summary

The paper proposes a novel approach for graph dataset distillation called Structure-broadcasting Graph Dataset Distillation (SGDD). The authors explicitly consider the impact of the original structure information on graph condensation and demonstrate that their approach achieves state-of-the-art results on 9 datasets, showing superior performance in cross-architecture settings and specific tasks. Overall, the paper presents a significant contribution to the field of graph dataset distillation.

Strengths

- The paper proposes a novel approach for graph dataset distillation that explicitly considers the impact of the original structure information on graph condensation. This is a significant departure from existing methods that primarily focus on optimizing the feature matrices of condensed graphs while overlooking the structure information. - The authors introduce the concept of Substantial Laplacian Energy Distribution (LED) shifts and demonstrate that previous works suffer from such shifts, leading to poor performance in cross-architecture generalization and specific tasks. The authors propose SGDD as a solution to this problem, which is a novel and original contribution. - The authors provide a thorough analysis of the proposed approach, including theoretical analysis and empirical evaluation on 9 datasets. The results demonstrate that SGDD consistently outperforms existing state-of-the-art methods, indicating the high quality of the proposed approach.

Weaknesses

- [Actual Computation Savings] The authors distill the graph dataset. However, the authors only provide the distilled dataset's size ratio to original dataset size. It would be helpful to provide the actual computation savings in terms of time and memory usage. - [The Cost during Graph Distillation] The cost of graph distillation for condensed small graph dataset is recommended to be provided. Since the used benchmark graph datasets are less computationally expensive than datasets in computer vision and natural language processing, the cost of graph distillation period will reflect whether the dataset is necessary for practical use. - [Comparison with Other Methods] The paper provides a comparison of the proposed method with other methods in terms of performance and size ratio (e.g., Table 1). However, it would be beneficial to also compare the cost of graph distillation for the proposed method with other methods. This information would provide a more comprehensive understanding of the practicality of the proposed approach compared to other methods.

Questions

Questions: Please see weaknesses. I would like to update my evaluation after the discussion.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N.A.

Summary

The paper investigates the effects of structural information in graph condensation methods. The authors claim that by maintaining the original structure during condensation using a newly formulated method called Structure-broadcasting Graph Dataset Distillation (SGDD), they are able to achieve more refined results on 9 data sets thereby significantly reducing Laplacian Energy Distribution (LED) shift.

Strengths

This paper addresses an important question regarding the impact of structural information. The authors conduct a comprehensive analysis from the spectral domain and empirically identify significant shifts in Laplacian Energy Distribution (LED), which ultimately result in poor performance in cross-architecture generalization and specific tasks. The proposed method demonstrates effectiveness in the experiments, and empirical analysis confirms the efficacy and necessity of the proposed designs. Overall, the presentation of the paper is also commendable

Weaknesses

large datasets in the Open Graph Benchmark (OGB) is more effective in demonstrating the efficacy of these methods.

Questions

I don't have question regarding this paper.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

Need experiment for large datasets

Summary

This paper proposes a new graph condensation framework called SGDD. The authors argue that existing methods overlook the structure information of the original graph during the condensation. And thus they propose to 1) use the Laplacian Energy Distribution (LED) shift to indicate the generalization performance of the condensed graph, and 2) minimize the LED shift (they claim it’s equivalent to the OT distance between the original and the condensed graphs) to preserve the structure information. Experiments on different datasets over node classification, anomaly detection and link prediction tasks show the effectiveness of the proposed method.

Strengths

- The motivation of preserving the structure information is clear and reasonable. - The experiments seem relatively sufficient and the results are good.

Weaknesses

My major concern is the soundness of this paper: - Some claims seem to be problematic. For example, in line 176-179, the authors claim that ‘minimizing the LED shift is equivalent to minimizing the distance of Laplacian pseudo-inverse matrices [65]’ and ‘Following the previous work [78], minimizing such distance can be further approximated to optimizing a free parameter $P$ in Eq(6)’. However, the equivalence in [65] only applies to the objective using a specific GW distance and the approximation in [78] only applies to another OT distance based objective. So the two claims cannot hold simultaneously. What’s worse, the authors do not describe which OT distance is used in their original objective function. Then how could we conclude that ‘minimizing the upper bound of Eq. (7) is equal to optimizing the $L_{structure}$ on Eq. (5)’ in line 189? - The writing is not very easy to follow. The mixed use of ‘LED shift’, ‘LED shift coefficient’, ‘SC’ is very confusing (e.g., in Def2 and the caption of Fig2). And it’s not clear what’s the role of the proposed LED shift coefficient. This coefficient is neither used to derive the objective function, nor adopted as a performance metric in the tables for comparison. ============================= Post-rebuttal: The author responses have basically solved my concerns about the soundness.

Questions

Please see the above part.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

None.

Further Discussions with Reviewer 5ivm

Dear reviewer 5ivm: Thanks again for pointing out our key benefits of preserving the structure information. According to your constructive comments, we made the necessary adjustments on introducing the optimal transport and conducted time-consuming experiments on $SC$. Additionally, we have revised our writing of relevant concepts to enhance the accessibility for readers. As the rebuttal period is about to close, may I know if our rebuttal addresses your concerns? Thank you for taking the time to review our work and provide your insightful comments.

Further Discussions with Reviewer FmUF

Dear reviewer FmUF: Thanks for taking the time to review our paper. We detailed our motivation in the response and provide a more comprehensive study with additional 5 works. Hope our rebuttal has addressed your concerns. As the discussion period is nearing its end, please feel free to let us know if you have any other concerns. Thanks!

Looking forward to the updated evaluation

Dear Reviewer 9hTZ, Thanks for the response. Based on your reviews, we are looking forward to your updated evaluations of our work.

Further experiments on Ogbn-products

Dear reviewer ZZ8V: Thanks for your patience, we finished our experiments on Ogbn-products, and show the table as follows. We will add these results in the revision. **Results on Ogbn-products:** Note: we report the results of SGDD and the other 3 baselines on 7 different condensation ratios($r$). We use the $\Delta$ to denote the improvements for our proposed SGDD to K-Center. | Condensation Ratio ($r$) | Random | K-Center | GCond [B] | SGDD | $\Delta$ (%) | | --- | --- | --- | --- | --- | --- | | 0.0001% | 18.8 | 32.6 | 36.5 | 36.8 | $\uparrow$4.1 | | 0.0002% | 18.4 | 34.7 | 36.4 | 36.8 | $\uparrow$2.0 | | 0.0003% | 21.5 | 35.8 | 36.4 | 38.8 | $\uparrow$3.0 | | 0.0004% | 23.8 | 35.6 | 36.9 | 38.6 | $\uparrow$3.0 | | 0.0005% | 25.4 | 35.7 | 37.6 | 38.8 | $\uparrow$3.1 | | 0.001% | 34.8 | 35.4 | 38.2 | 40.1 | $\uparrow$4.7 | | 0.002% | 35.2 | 36.2 | 38.8 | 40.3 | $\uparrow$4.0 | Conclusion(s): - **Our proposed SGDD consistently outperforms other baselines across all condensation ratios with no meticulous tuning. Notably, it improves accuracy by 4.7% over K-Center at the 0.001% ratio, and by 1.8% and 5.3% over GCond [B] and Random, respectively.** We eagerly await your feedback to know if our experiments have adequately addressed your concerns. Please feel free if you have other questions. Thanks for your constructive suggestion again! [B] Wei Jin, et.al. Graph condensation for graph neural networks. ICLR 2022.