Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data

Summary

This work proposes a structure-free graph condensation paradigm to distill a large-scale graph into a small-scale graph node set without explicit graph structures. The node attributes of the obtained small-scale condensed graph-free data could encode topology structure information. And the condensed node set could serve as a substitution to replace the large-scale graph for training GNNs and achieves comparable performance on the test set. The method contains two techniques, (1) the parameter matching schema under imitation learning, and (2) a dynamic evaluation schema with a GNTK score. The experimental results could verify its claims and show performance effectiveness.

Strengths

S1-[originality]: This work's most remarkable part is its structure-free condensation paradigm, which removes the graph structure by encoding it into node attributes, so that the obtained condensed graph-free data only contains a set of informative nodes. I think this paper would inspire many interesting questions for future researches and topics, when only use a set of nodes to represent the whole large-scale graph for training but obtain comparable test results. S2-[clarity]: Overall, the question descriptions, contributions, techniques, and experimental results of this paper are described clearly and soundly. first, the concept of structure-free graph condensation and its relevant scenarios have been clearly defined and exemplified. second, the contributions and techniques including the training trajectory matching with online GNN parameters and the GNTK-based dynamic score are clear and sound. This paper could ease three-level optimization to a bi-level optimization without condensed graph structures, which is a novel and interesting structure-free graph condensation pattern. The GNTK-based dynamic evaluation score enables the closed-form solution of GNN evaluation and sounds novel to me. third, the experimental results compared with the whole graph dataset training results could support this paper's arguments. An ablation study verifies the effectiveness of the structure-free paradigm. There is another interesting part that the results across different GNN architectures show surprisingly good generalization ability in terms of the condensed node set. This is an inspirable result and deserves future explorations. S3-[significance]: this work on graph condensation is an interesting problem to reduce the effects brought by large-graph data scale and quantity, and it might be helpful for reducing calculations in real-world applications.

Weaknesses

There are only some technical details that are not well presented here. W1: how to choose the condensation ratios like Cora with 0.9% and Citeseer with 1.3%? More details and explanations should be involved. W2: how to deal with the condensed graph labels Y? Is it generated according to the original large-scale graph's classes and each class examples? W3: are the student steps and teacher steps empirical hyperparameters or learnable parameters that need to be optimized in the condensation process? More details should be given. Besides, this work provides some interesting results, and more discussions of experimental findings should be given, for instance, why the synthesized graph-free data has good generalization ability.

Questions

Please provide more details corresponding to the weakness.

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

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

Yes, the authors have mentioned limitations, no negative social impact.

Summary

This paper studies an interesting problem. The authors proposes a new paradigm for reducing the size of large-scale graphs without explicit graph structures. The proposed SFGC, encodes topology structure information into node attributes in synthesized graph-free data. Extensive experiments demonstrate the effectiveness of the proposed method compred with existing graph condensation methods.

Strengths

- The paper proposes a novel SFGC approach. - This paper studies the effectiveness and generalization ability issues in graph condensation. - This paper provides theoretical illustrations of the proposed structure-free graph condensation paradigm from the views of statistical learning and information flow, respectively.

Weaknesses

- The work fails to provide a clear motivation for why it is important or required to reduce the size of big graphs lacking explicit graph structures. - The paper could benefit from a more thorough discussion of the limitations and potential future directions of the proposed approach. - Without having access to the source code, it is challenging to reproduce the results. The experimental setting is described, however it would be beneficial to have access to the source code to guarantee that the findings can be reproducible. If the main concern about the reproducibility is solved, I am willing to increase the score.

Questions

- How computationally efficient is the SFGC strategy compared to the current graph condensation techniques? - How effective and robust is the SFGC method on real-world graphs with noisy or insufficient data?

Rating

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

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

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

The authors could benefit from a more thorough discussion of the limitations and potential negative societal impacts of their work, as well as potential ways to mitigate these issues.

Summary

This paper presents a new method to condense a training graph into a smaller number of disconnected nodes, such that a GNN trained on these nodes performs similar to one trained on the original graph at test time.

Strengths

**Originality.** Structure-free condensation has been reported before (GCOND-X), but the proposed method to do so is novel. **Quality.** The overall quality of the work is good, including the presented techniques, results, tables and plots. **Clarity.** The paper is mostly clear. **Significance.** Graph condensation can be very useful under the right application scenarios. I don't see any special significance of aiming for structure-free condensation, except that the method ends up giving better results (e.g. due to easier optimization, as discussed in the paper).

Weaknesses

The paper is not particularly easy to follow. GCOND-X is not discussed explicitly in the related works, even though it is a structure-free graph condensation method. Hyper-parameter details have not been provided.

Questions

What does the condensed structure-free data look like in relation to the original training data? Some intuitive visualization would be nice to have. What are the GNN depths used? It seems that the fidelity of structure-free condensation should go down as more neighbor aggregation steps are involved at test time, as they were not encountered when training on the condensed data.

Rating

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

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

A discussion of limitations is missing. An obvious limitation is that structure-free condensation won't work under ego- and neighbor-embedding separation [1] which is an effective recommendation for heterophilic datasets. [1] Zhu et. al. "Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs." NeurIPS 2020

Summary

This paper studies the problem of reducing the size of a large graph dataset while preserving task-relevant information. It introduces a new methodology to distill large-scale real-world graphs into smaller synthetic graph node sets by disregarding graph structures to create condensed graph-free data. The approach involves two key components: a training trajectory meta-matching scheme for effectively synthesizing small-scale graph-free data, and a graph neural feature score metric for evaluating the quality of condensed graph-free data dynamically. Extensive experiments have demonstrated the efficiency and effectiveness of the proposed method.

Strengths

1. The paper addresses an interesting problem in the field of graph condensation, which has significant practical implications. 2. The proposed SFGC methodology exhibits commendable performance and generalization across various graph neural network (GNN) architectures. 3. The utilization of the Graph Neural Tangent Kernel (GNTK) to avoid iterative training of GNNs adds an interesting aspect to the paper.

Weaknesses

Suggestions for Improvement: 1. To further strengthen the paper, it is recommended to demonstrate the benefits of SFGC in practical applications such as neural architecture search, privacy protection, adversarial robustness, or continual learning. Including at least one of these applications would greatly enhance the paper's significance. 2. It would be of interest to clarify how SFGC can benefit neural architecture search for GNNs since it does not generate graph structures, which are essential for GNNs, and different GNNs may require distinct operations over the graph structure. 3. While Figure A2 provides a comparison of the running time between GCN and GNTK, it would be valuable to include a detailed complexity analysis of both methods concerning the number of nodes. * Specifically, elaborate on the quadratic complexity of GNTK due to the pairwise kernel matrix calculations and the matrix inversion operation. * I guess that is also why on Reddit (r=0.05%) GCN and GNTK exhibit similar running times. What if we further increase r to 0.1%? 4. It would be beneficial to include an empirical comparison with DosCond, as it also aims to accelerate the graph condensation process, to provide a comprehensive evaluation of SFGC.

Questions

1. Complexity comparison of GCN and GNTK 2. What is the exact formulation for $\mathcal{K}$ in Eq. 7? Specifically, what are the values for $\beta$ and $K$.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

4 excellent

Contribution

3 good

Limitations

Yes

Summary

This paper introduces a structure-free graph condensation method designed to distill large-scale graphs into small-scale graph-free data while preserving comparable expressiveness. The proposed method, named SFGC, achieves this by condensing the graph topology into an identity matrix, effectively embedding the structure information into the node attributes. To effectively imitate the GNN training process, SFGC employs a training trajectory meta-matching scheme. Additionally, a graph neural feature scoring technique is used, which dynamically evaluates the quality and relevance of the synthetic graph-free data.

Strengths

- Graph condensation is a crucial research area with many real-world applications. The authors propose a new “structure-free” graph condensation method. - They provide convincing experimental results and comprehensive discussions overall. - The idea of using GNTK-based graph neural feature score metric is interesting and effective. - The paper is clearly written and easy to follow. Supplementary materials also offer valuable additional information regarding the model and its performance behaviors.

Weaknesses

- The authors claim that this is the first work that distills large-scale graphs to small-scale synthetic graph-free data, but the previous work GCOND-X also appears to perform a similar task of distilling large graphs to small-scale graph-free data. Further clarification on this would be needed. - It appears that the experiments do not precisely determine the extent to which different aspects of the model contribute to performance improvement. - The effectiveness of the “structure-free paradigm” in SFCG should also be convincingly demonstrated. In Section 3.2, a graph structure is generated from condensed node features and compared with SFCG. However, since the graph structure is already included in the node features, inputting the graph structure and condensed node features into the GNN model again could cause over-smoothing. Therefore, it is unclear whether the performance improvement over existing models is due to the structure-free paradigm or appears to be due to over-smoothing.

Questions

- Could you provide more details on how the three condensation ratios for each dataset used in the experiments were determined? - I am curious why the performances of the five variants of SFGC in Figure 3 (Citeseer), used for synthesizing graph structures, drop significantly at a condensation ratio (r) of 3.6%, which is even much worse than the case of smaller condensation ratios. - I would like to know if the number of expert trajectories affects the performance and how the number of expert trajectories were set. - Claiming that the long-term parameter distribution matching method is superior because the SFGC method outperforms GCOND and GCOND-X in Table 1 might be somewhat hasty. While the superior performance could be due to the consideration of long-range, it seems that finding the optimal condensed graph-free data, as seen in Table A4, also plays a significant role.

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

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The authors do not include a discussion on the potential limitations of this study or offer insights into possible future research directions. - An important consideration is that if SFGC necessitates the pre-training of a GNN on a large-scale graph to obtain a pre-trained training trajectory, it implies that real-world large-scale data must be initially trained. While this process is distinct from the graph condensation pipeline, it nonetheless introduces challenges associated with intensive computational demands. Addressing and suggesting solutions for this could provide valuable directions for future studies. - I find the potential of employing different GNN models as the condensation network intriguing. As the method of incorporating graph structural information into node features heavily relies on the characteristics of the condensation model, using a different GNN model could potentially alter the properties of the condensed graph and impact the final performance. Therefore, additional experiments with various condensation networks and test networks would offer valuable insights.

Summary

This paper proposes a graph dataset condensing algorithm with a main idea of creating a new format of graph representation that does not explicitly include edge information. The authors suggest a new graph kernel and training algorithm with trajectory for online gradient to achieve graph condensation. Experiments demonstrate that the suggested algorithm (named SFGC) outperforms other baselines that condense the graph with explicit edge information in terms of node classification. The authors also showcase the performance of SFGC in terms of generalization ability and empirical learning time efficiency.

Strengths

One of the main strengths of this paper is introducing an interesting method for compressing graph datasets. The idea of removing edge information explicitly seems strong, but it appears plausible and well-founded, akin to non-negative matrix factorization with constraints of non-negativity. The simplicity of the idea allows other researchers to easily adapt it to their own graph-related research. Furthermore, the authors present numerous experimental results demonstrating that the suggested framework outperforms the baseline models.

Weaknesses

I have some questions, so I hope to listen to the answers from the authors. It is hard to see Figure 3.

Questions

- Can SFGC be used for edge classification tasks, such as edge prediction? - I am curious why using SFGC is better than using the whole dataset in Cora data (Table 1). In lines 303 to 304, the authors mentioned this phenomenon, but it would be beneficial to see the reason backed with examples.

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

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

It is challenging to find the limitation section. Could you please indicate the part where the limitations of the proposed method are discussed?

Thanks for the rebuttal

Thank you for the detailed response and some of my concerns have been addressed. I tend to accept this paper and I think my current score is reasonable.