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

• URL: http://arxiv.org/abs/2306.02664v2
• Date: Mon, 23 Oct 2023 05:28:43 GMT
• Title: Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data
• Authors: Xin Zheng, Miao Zhang, Chunyang Chen, Quoc Viet Hung Nguyen, Xingquan Zhu, Shirui Pan
• Abstract summary: Existing graph condensation methods rely on the joint optimization of nodes and structures in the condensed graph. We advocate a new Structure-Free Graph Condensation paradigm, named SFGC, to distill a large-scale graph into a small-scale graph node set.
• Score: 91.27527985415007
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph condensation, which reduces the size of a large-scale graph by synthesizing a small-scale condensed graph as its substitution, has immediate benefits for various graph learning tasks. However, existing graph condensation methods rely on the joint optimization of nodes and structures in the condensed graph, and overlook critical issues in effectiveness and generalization ability. In this paper, we advocate a new Structure-Free Graph Condensation paradigm, named SFGC, to distill a large-scale graph into a small-scale graph node set without explicit graph structures, i.e., graph-free data. Our idea is to implicitly encode topology structure information into the node attributes in the synthesized graph-free data, whose topology is reduced to an identity matrix. Specifically, SFGC contains two collaborative components: (1) a training trajectory meta-matching scheme for effectively synthesizing small-scale graph-free data; (2) a graph neural feature score metric for dynamically evaluating the quality of the condensed data. Through training trajectory meta-matching, SFGC aligns the long-term GNN learning behaviors between the large-scale graph and the condensed small-scale graph-free data, ensuring comprehensive and compact transfer of informative knowledge to the graph-free data. Afterward, the underlying condensed graph-free data would be dynamically evaluated with the graph neural feature score, which is a closed-form metric for ensuring the excellent expressiveness of the condensed graph-free data. Extensive experiments verify the superiority of SFGC across different condensation ratios.

Related papers

• GC-Bench: An Open and Unified Benchmark for Graph Condensation [54.70801435138878]
  We develop a comprehensive Graph Condensation Benchmark (GC-Bench) to analyze the performance of graph condensation. GC-Bench systematically investigates the characteristics of graph condensation in terms of the following dimensions: effectiveness, transferability, and complexity. We have developed an easy-to-use library for training and evaluating different GC methods to facilitate reproducible research.
  arXiv  Detail & Related papers  (2024-06-30T07:47:34Z)
• Simple Graph Condensation [30.85754566420301]
  Graph condensation involves tuning Graph Neural Networks (GNNs) on a small condensed graph for use on a large-scale original graph. We introduce the Simple Graph Condensation (SimGC) framework, which aligns the condensed graph with the original graph from the input layer to the prediction layer. SimGC achieves a significant speedup of up to 10 times compared to existing graph condensation methods.
  arXiv  Detail & Related papers  (2024-03-22T05:04:48Z)
• Graph Data Condensation via Self-expressive Graph Structure Reconstruction [7.4525875528900665]
  We introduce a novel framework named textbfGraph Data textbfCondensation via textbfSelf-expressive Graph Structure textbfReconstruction. Our method explicitly incorporates the original graph structure into the condensing process and captures the nuanced interdependencies between the condensed nodes.
  arXiv  Detail & Related papers  (2024-03-12T03:54:25Z)
• GDM: Dual Mixup for Graph Classification with Limited Supervision [27.8982897698616]
  Graph Neural Networks (GNNs) require a large number of labeled graph samples to obtain good performance on the graph classification task. The performance of GNNs degrades significantly as the number of labeled graph samples decreases. We propose a novel mixup-based graph augmentation method to generate new labeled graph samples.
  arXiv  Detail & Related papers  (2023-09-18T20:17:10Z)
• Demystifying Graph Convolution with a Simple Concatenation [6.542119695695405]
  We quantify the information overlap between graph topology, node features, and labels. We show that graph concatenation is a simple but more flexible alternative to graph convolution.
  arXiv  Detail & Related papers  (2022-07-18T16:39:33Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  We propose a graph convolutional relationship between the observed and latent graphs, and formulate the graph learning task as a network inverse (deconvolution) problem. In lieu of eigendecomposition-based spectral methods, we unroll and truncate proximal gradient iterations to arrive at a parameterized neural network architecture that we call a Graph Deconvolution Network (GDN) GDNs can learn a distribution of graphs in a supervised fashion, perform link prediction or edge-weight regression tasks by adapting the loss function, and they are inherently inductive.
  arXiv  Detail & Related papers  (2022-05-19T14:08:15Z)
• Scaling R-GCN Training with Graph Summarization [71.06855946732296]
  Training of Relation Graph Convolutional Networks (R-GCN) does not scale well with the size of the graph. In this work, we experiment with the use of graph summarization techniques to compress the graph. We obtain reasonable results on the AIFB, MUTAG and AM datasets.
  arXiv  Detail & Related papers  (2022-03-05T00:28:43Z)
• Multilevel Graph Matching Networks for Deep Graph Similarity Learning [79.3213351477689]
  We propose a multi-level graph matching network (MGMN) framework for computing the graph similarity between any pair of graph-structured objects. To compensate for the lack of standard benchmark datasets, we have created and collected a set of datasets for both the graph-graph classification and graph-graph regression tasks. Comprehensive experiments demonstrate that MGMN consistently outperforms state-of-the-art baseline models on both the graph-graph classification and graph-graph regression tasks.
  arXiv  Detail & Related papers  (2020-07-08T19:48:19Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.