Graph Distillation with Eigenbasis Matching

• URL: http://arxiv.org/abs/2310.09202v2
• Date: Tue, 14 May 2024 17:12:15 GMT
• Title: Graph Distillation with Eigenbasis Matching
• Authors: Yang Liu, Deyu Bo, Chuan Shi,
• Abstract summary: We propose Graph Distillation with Eigenbasis Matching (GDEM) to replace the real large graph. GDEM aligns the eigenbasis and node features of real and synthetic graphs. It directly replicates the spectrum of the real graph and thus prevents the influence of GNNs.
• Score: 43.59076214528843
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The increasing amount of graph data places requirements on the efficient training of graph neural networks (GNNs). The emerging graph distillation (GD) tackles this challenge by distilling a small synthetic graph to replace the real large graph, ensuring GNNs trained on real and synthetic graphs exhibit comparable performance. However, existing methods rely on GNN-related information as supervision, including gradients, representations, and trajectories, which have two limitations. First, GNNs can affect the spectrum (i.e., eigenvalues) of the real graph, causing spectrum bias in the synthetic graph. Second, the variety of GNN architectures leads to the creation of different synthetic graphs, requiring traversal to obtain optimal performance. To tackle these issues, we propose Graph Distillation with Eigenbasis Matching (GDEM), which aligns the eigenbasis and node features of real and synthetic graphs. Meanwhile, it directly replicates the spectrum of the real graph and thus prevents the influence of GNNs. Moreover, we design a discrimination constraint to balance the effectiveness and generalization of GDEM. Theoretically, the synthetic graphs distilled by GDEM are restricted spectral approximations of the real graphs. Extensive experiments demonstrate that GDEM outperforms state-of-the-art GD methods with powerful cross-architecture generalization ability and significant distillation efficiency. Our code is available at https://github.com/liuyang-tian/GDEM.

Related papers

• Scalable Implicit Graphon Learning [25.015678499211404]
  We propose a scalable method that combines implicit neural representations (INRs) and graph neural networks (GNNs) to estimate a graphon from observed graphs. We evaluate SIGL in synthetic and real-world graphs, showing that it outperforms existing methods and scales effectively to larger graphs.
  arXiv  Detail & Related papers  (2024-10-22T22:44:24Z)
• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  The ubiquity of large-scale graphs in node-classification tasks hinders the real-world applications of Graph Neural Networks (GNNs) This paper studies graph coresets for GNNs and avoids the interdependence issue by selecting ego-graphs based on their spectral embeddings. Our spectral greedy graph coreset (SGGC) scales to graphs with millions of nodes, obviates the need for model pre-training, and applies to low-homophily graphs.
  arXiv  Detail & Related papers  (2024-05-27T17:52:12Z)
• A Spectral Analysis of Graph Neural Networks on Dense and Sparse Graphs [13.954735096637298]
  We analyze how sparsity affects the graph spectra, and thus the performance of graph neural networks (GNNs) in node classification on dense and sparse graphs. We show that GNNs can outperform spectral methods on sparse graphs, and illustrate these results with numerical examples on both synthetic and real graphs.
  arXiv  Detail & Related papers  (2022-11-06T22:38:13Z)
• MentorGNN: Deriving Curriculum for Pre-Training GNNs [61.97574489259085]
  We propose an end-to-end model named MentorGNN that aims to supervise the pre-training process of GNNs across graphs. We shed new light on the problem of domain adaption on relational data (i.e., graphs) by deriving a natural and interpretable upper bound on the generalization error of the pre-trained GNNs.
  arXiv  Detail & Related papers  (2022-08-21T15:12:08Z)
• Evaluating Explainability for Graph Neural Networks [21.339111121529815]
  We introduce a synthetic graph data generator, ShapeGGen, which can generate a variety of benchmark datasets. We include ShapeGGen and several real-world graph datasets into an open-source graph explainability library, GraphXAI.
  arXiv  Detail & Related papers  (2022-08-19T13:43:52Z)
• Graph Generative Model for Benchmarking Graph Neural Networks [73.11514658000547]
  We introduce a novel graph generative model that learns and reproduces the distribution of real-world graphs in a privacy-controlled way. Our model can successfully generate privacy-controlled, synthetic substitutes of large-scale real-world graphs that can be effectively used to benchmark GNN models.
  arXiv  Detail & Related papers  (2022-07-10T06:42:02Z)
• Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
  This paper focuses on creating a small graph to represent the original graph, so that GNNs trained on the size-reduced graph can make accurate predictions. We view the original graph as a distribution of receptive fields and aim to synthesize a small graph whose receptive fields share a similar distribution.
  arXiv  Detail & Related papers  (2022-06-28T02:10:05Z)
• 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)
• Adaptive Kernel Graph Neural Network [21.863238974404474]
  Graph neural networks (GNNs) have demonstrated great success in representation learning for graph-structured data. In this paper, we propose a novel framework - i.e., namely Adaptive Kernel Graph Neural Network (AKGNN) AKGNN learns to adapt to the optimal graph kernel in a unified manner at the first attempt. Experiments are conducted on acknowledged benchmark datasets and promising results demonstrate the outstanding performance of our proposed AKGNN.
  arXiv  Detail & Related papers  (2021-12-08T20:23:58Z)

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.