Two Trades are not Baffled: Condensing Graph via Crafting Rational Gradient Matching

Two Trades are not Baffled: Condensing Graph via Crafting Rational Gradient Matching

27 Sep 2024 | Tianle Zhang, Yuchen Zhang, Kun Wang, Kai Wang, Beining Yang, Kaipeng Zhang, Wenqi Shao, Ping Liu, Joey Tianyi Zhou, Yang You
This paper introduces a novel graph condensation method called CrafTing RationalL gradient matching (CTRL), which aims to reduce the impact of accumulated errors in graph condensation by optimizing gradient matching and initialization. Traditional graph condensation methods often rely on gradient matching to generate a synthetic graph that mimics the original graph, but they face challenges such as deviations in training trajectories and accumulated errors due to differences between condensation and evaluation phases. CTRL addresses these issues by considering both the direction and magnitude of gradients during matching, leading to a more accurate synthetic graph. The method also employs a clustering-based initialization strategy to ensure the synthetic graph's feature distribution closely matches the original graph. Theoretical analysis shows that CTRL can effectively neutralize the impact of accumulated errors on the performance of condensed graphs. Extensive experiments on various graph datasets and downstream tasks demonstrate that CTRL achieves state-of-the-art results, particularly in node classification and graph classification tasks. For instance, CTRL achieves lossless condensation on several datasets, including Cora, Citeseer, and Flickr, and outperforms existing methods in terms of accuracy and efficiency. The method also shows strong cross-architecture generalization capabilities, performing well across different graph neural network architectures. The paper also highlights the importance of considering both gradient magnitude and direction in gradient matching, as focusing solely on one can lead to suboptimal results. By combining cosine similarity and Euclidean distance, CTRL provides a more refined matching criterion that reduces matching errors and accumulated errors. The proposed method is generalizable and can be integrated into various data condensation approaches. However, the method is limited to gradient matching frameworks and future work may explore its application in other matching approaches. Overall, CTRL offers a promising solution for graph condensation, achieving high-quality synthetic graphs with minimal loss in performance.This paper introduces a novel graph condensation method called CrafTing RationalL gradient matching (CTRL), which aims to reduce the impact of accumulated errors in graph condensation by optimizing gradient matching and initialization. Traditional graph condensation methods often rely on gradient matching to generate a synthetic graph that mimics the original graph, but they face challenges such as deviations in training trajectories and accumulated errors due to differences between condensation and evaluation phases. CTRL addresses these issues by considering both the direction and magnitude of gradients during matching, leading to a more accurate synthetic graph. The method also employs a clustering-based initialization strategy to ensure the synthetic graph's feature distribution closely matches the original graph. Theoretical analysis shows that CTRL can effectively neutralize the impact of accumulated errors on the performance of condensed graphs. Extensive experiments on various graph datasets and downstream tasks demonstrate that CTRL achieves state-of-the-art results, particularly in node classification and graph classification tasks. For instance, CTRL achieves lossless condensation on several datasets, including Cora, Citeseer, and Flickr, and outperforms existing methods in terms of accuracy and efficiency. The method also shows strong cross-architecture generalization capabilities, performing well across different graph neural network architectures. The paper also highlights the importance of considering both gradient magnitude and direction in gradient matching, as focusing solely on one can lead to suboptimal results. By combining cosine similarity and Euclidean distance, CTRL provides a more refined matching criterion that reduces matching errors and accumulated errors. The proposed method is generalizable and can be integrated into various data condensation approaches. However, the method is limited to gradient matching frameworks and future work may explore its application in other matching approaches. Overall, CTRL offers a promising solution for graph condensation, achieving high-quality synthetic graphs with minimal loss in performance.
Reach us at info@study.space
Understanding Two Trades is not Baffled%3A Condensing Graph via Crafting Rational Gradient Matching