Discovering Invariant Neighborhood Patterns for Heterophilic Graphs

• URL: http://arxiv.org/abs/2403.10572v1
• Date: Fri, 15 Mar 2024 02:25:45 GMT
• Title: Discovering Invariant Neighborhood Patterns for Heterophilic Graphs
• Authors: Ruihao Zhang, Zhengyu Chen, Teng Xiao, Yueyang Wang, Kun Kuang,
• Abstract summary: We propose a novel Invariant Neighborhood Pattern Learning (INPL) to alleviate the distribution shifts problem on non-homophilous graphs. We show that INPL could achieve state-of-the-art performance for learning on large non-homophilous graphs.
• Score: 32.315495035666636
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the problem of distribution shifts on non-homophilous graphs Mosting existing graph neural network methods rely on the homophilous assumption that nodes from the same class are more likely to be linked. However, such assumptions of homophily do not always hold in real-world graphs, which leads to more complex distribution shifts unaccounted for in previous methods. The distribution shifts of neighborhood patterns are much more diverse on non-homophilous graphs. We propose a novel Invariant Neighborhood Pattern Learning (INPL) to alleviate the distribution shifts problem on non-homophilous graphs. Specifically, we propose the Adaptive Neighborhood Propagation (ANP) module to capture the adaptive neighborhood information, which could alleviate the neighborhood pattern distribution shifts problem on non-homophilous graphs. We propose Invariant Non-Homophilous Graph Learning (INHGL) module to constrain the ANP and learn invariant graph representation on non-homophilous graphs. Extensive experimental results on real-world non-homophilous graphs show that INPL could achieve state-of-the-art performance for learning on large non-homophilous graphs.

Related papers

• Non-Homophilic Graph Pre-Training and Prompt Learning [11.996173149569627]
  We propose ProNoG, a novel pre-training and prompt learning framework for non-homophilic graphs. First, we analyze existing graph pre-training methods, providing theoretical insights into the choice of pre-training tasks. Second, recognizing that each node exhibits unique non-homophilic characteristics, we propose a conditional network to characterize the node-specific patterns in downstream tasks.
  arXiv  Detail & Related papers  (2024-08-22T17:57:31Z)
• The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges [101.83124435649358]
  Homophily principle, ie nodes with the same labels or similar attributes are more likely to be connected. Recent work has identified a non-trivial set of datasets where GNN's performance compared to the NN's is not satisfactory.
  arXiv  Detail & Related papers  (2024-07-12T18:04:32Z)
• Advancing Graph Generation through Beta Diffusion [49.49740940068255]
  Graph Beta Diffusion (GBD) is a generative model specifically designed to handle the diverse nature of graph data. We propose a modulation technique that enhances the realism of generated graphs by stabilizing critical graph topology.
  arXiv  Detail & Related papers  (2024-06-13T17:42:57Z)
• Heterophilous Distribution Propagation for Graph Neural Networks [23.897535976924722]
  We propose heterophilous distribution propagation (HDP) for graph neural networks. Instead of aggregating information from all neighborhoods, HDP adaptively separates the neighbors into homophilous and heterphilous parts. We conduct extensive experiments on 9 benchmark datasets with different levels of homophily.
  arXiv  Detail & Related papers  (2024-05-31T06:40:56Z)
• Generation is better than Modification: Combating High Class Homophily Variance in Graph Anomaly Detection [51.11833609431406]
  Homophily distribution differences between different classes are significantly greater than those in homophilic and heterophilic graphs. We introduce a new metric called Class Homophily Variance, which quantitatively describes this phenomenon. To mitigate its impact, we propose a novel GNN model named Homophily Edge Generation Graph Neural Network (HedGe)
  arXiv  Detail & Related papers  (2024-03-15T14:26:53Z)
• Does Invariant Graph Learning via Environment Augmentation Learn Invariance? [39.08988313527199]
  Invariant graph representation learning aims to learn the invariance among data from different environments for out-of-distribution generalization on graphs. We develop a set of minimal assumptions, including variation sufficiency and variation consistency, for feasible invariant graph learning. We show that extracting the maximally invariant subgraph to the proxy predictions provably identifies the underlying invariant subgraph for successful OOD generalization.
  arXiv  Detail & Related papers  (2023-10-29T14:57:37Z)
• Advective Diffusion Transformers for Topological Generalization in Graph Learning [69.2894350228753]
  We show how graph diffusion equations extrapolate and generalize in the presence of varying graph topologies. We propose a novel graph encoder backbone, Advective Diffusion Transformer (ADiT), inspired by advective graph diffusion equations.
  arXiv  Detail & Related papers  (2023-10-10T08:40:47Z)
• GraphGDP: Generative Diffusion Processes for Permutation Invariant Graph Generation [43.196067037856515]
  Graph generative models have broad applications in biology, chemistry and social science. Current leading autoregressive models fail to capture the permutation invariance nature of graphs. We propose a continuous-time generative diffusion process for permutation invariant graph generation.
  arXiv  Detail & Related papers  (2022-12-04T15:12:44Z)
• DiGress: Discrete Denoising diffusion for graph generation [79.13904438217592]
  DiGress is a discrete denoising diffusion model for generating graphs with categorical node and edge attributes. It achieves state-of-the-art performance on molecular and non-molecular datasets, with up to 3x validity improvement. It is also the first model to scale to the large GuacaMol dataset containing 1.3M drug-like molecules.
  arXiv  Detail & Related papers  (2022-09-29T12:55:03Z)
• Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs [6.018995094882323]
  Graph neural networks (GNNs) have been extensively studied for prediction tasks on graphs. Most GNNs assume local homophily, i.e., strong similarities in localneighborhoods. We propose a flexible GNN model, which is capable of handling any graphs without beingrestricted by their underlying homophily.
  arXiv  Detail & Related papers  (2021-03-26T00:35:36Z)
• Permutation Invariant Graph Generation via Score-Based Generative Modeling [114.12935776726606]
  We propose a permutation invariant approach to modeling graphs, using the recent framework of score-based generative modeling. In particular, we design a permutation equivariant, multi-channel graph neural network to model the gradient of the data distribution at the input graph. For graph generation, we find that our learning approach achieves better or comparable results to existing models on benchmark datasets.
  arXiv  Detail & Related papers  (2020-03-02T03:06:14Z)

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.