Spectral Invariant Learning for Dynamic Graphs under Distribution Shifts

• URL: http://arxiv.org/abs/2403.05026v1
• Date: Fri, 8 Mar 2024 04:07:23 GMT
• Title: Spectral Invariant Learning for Dynamic Graphs under Distribution Shifts
• Authors: Zeyang Zhang, Xin Wang, Ziwei Zhang, Zhou Qin, Weigao Wen, Hui Xue, Haoyang Li, Wenwu Zhu
• Abstract summary: Dynamic graph neural networks (DyGNNs) currently struggle with handling distribution shifts that are inherent in dynamic graphs. We propose to study distribution shifts on dynamic graphs in the spectral domain for the first time.
• Score: 57.19908334882441
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Dynamic graph neural networks (DyGNNs) currently struggle with handling distribution shifts that are inherent in dynamic graphs. Existing work on DyGNNs with out-of-distribution settings only focuses on the time domain, failing to handle cases involving distribution shifts in the spectral domain. In this paper, we discover that there exist cases with distribution shifts unobservable in the time domain while observable in the spectral domain, and propose to study distribution shifts on dynamic graphs in the spectral domain for the first time. However, this investigation poses two key challenges: i) it is non-trivial to capture different graph patterns that are driven by various frequency components entangled in the spectral domain; and ii) it remains unclear how to handle distribution shifts with the discovered spectral patterns. To address these challenges, we propose Spectral Invariant Learning for Dynamic Graphs under Distribution Shifts (SILD), which can handle distribution shifts on dynamic graphs by capturing and utilizing invariant and variant spectral patterns. Specifically, we first design a DyGNN with Fourier transform to obtain the ego-graph trajectory spectrums, allowing the mixed dynamic graph patterns to be transformed into separate frequency components. We then develop a disentangled spectrum mask to filter graph dynamics from various frequency components and discover the invariant and variant spectral patterns. Finally, we propose invariant spectral filtering, which encourages the model to rely on invariant patterns for generalization under distribution shifts. Experimental results on synthetic and real-world dynamic graph datasets demonstrate the superiority of our method for both node classification and link prediction tasks under distribution shifts.

Related papers

• Rank and Align: Towards Effective Source-free Graph Domain Adaptation [16.941755478093153]
  Graph neural networks (GNNs) have achieved impressive performance in graph domain adaptation. However, extensive source graphs could be unavailable in real-world scenarios due to privacy and storage concerns. We introduce a novel GNN-based approach called Rank and Align (RNA), which ranks graph similarities with spectral seriation for robust semantics learning.
  arXiv  Detail & Related papers  (2024-08-22T08:00:50Z)
• Equivariant Machine Learning on Graphs with Nonlinear Spectral Filters [12.709930975472698]
  We consider the graph functional shifts as the symmetry group: the unitary operators that commute with the graph shift operator. We propose nonlinear spectral filters (NLSFs) that are fully equivariant to graph functional shifts. We demonstrate the superior performance of NLSFs over existing spectral GNNs in node and graph classification benchmarks.
  arXiv  Detail & Related papers  (2024-06-03T12:07:01Z)
• Graph Generation via Spectral Diffusion [51.60814773299899]
  We present GRASP, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process. Specifically, we propose to use a denoising model to sample eigenvectors and eigenvalues from which we can reconstruct the graph Laplacian and adjacency matrix. Our permutation invariant model can also handle node features by concatenating them to the eigenvectors of each node.
  arXiv  Detail & Related papers  (2024-02-29T09:26:46Z)
• Out-of-Distribution Generalized Dynamic Graph Neural Network with Disentangled Intervention and Invariance Promotion [61.751257172868186]
  Dynamic graph neural networks (DyGNNs) have demonstrated powerful predictive abilities by exploiting graph and temporal dynamics. Existing DyGNNs fail to handle distribution shifts, which naturally exist in dynamic graphs.
  arXiv  Detail & Related papers  (2023-11-24T02:42:42Z)
• HoloNets: Spectral Convolutions do extend to Directed Graphs [59.851175771106625]
  Conventional wisdom dictates that spectral convolutional networks may only be deployed on undirected graphs. Here we show this traditional reliance on the graph Fourier transform to be superfluous. We provide a frequency-response interpretation of newly developed filters, investigate the influence of the basis used to express filters and discuss the interplay with characteristic operators on which networks are based.
  arXiv  Detail & Related papers  (2023-10-03T17:42:09Z)
• Specformer: Spectral Graph Neural Networks Meet Transformers [51.644312964537356]
  Spectral graph neural networks (GNNs) learn graph representations via spectral-domain graph convolutions. We introduce Specformer, which effectively encodes the set of all eigenvalues and performs self-attention in the spectral domain. By stacking multiple Specformer layers, one can build a powerful spectral GNN.
  arXiv  Detail & Related papers  (2023-03-02T07:36:23Z)
• Spectral-Spatial Global Graph Reasoning for Hyperspectral Image Classification [50.899576891296235]
  Convolutional neural networks have been widely applied to hyperspectral image classification. Recent methods attempt to address this issue by performing graph convolutions on spatial topologies.
  arXiv  Detail & Related papers  (2021-06-26T06:24:51Z)
• Bridging the Gap Between Spectral and Spatial Domains in Graph Neural Networks [8.563354084119062]
  We show some equivalence of the graph convolution process regardless it is designed in the spatial or the spectral domain. The proposed framework is used to design new convolutions in spectral domain with a custom frequency profile while applying them in the spatial domain.
  arXiv  Detail & Related papers  (2020-03-26T01:49:24Z)

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.