PC-Conv: Unifying Homophily and Heterophily with Two-fold Filtering

• URL: http://arxiv.org/abs/2312.14438v1
• Date: Fri, 22 Dec 2023 05:04:28 GMT
• Title: PC-Conv: Unifying Homophily and Heterophily with Two-fold Filtering
• Authors: Bingheng Li, Erlin Pan, Zhao Kang
• Abstract summary: We propose a two-fold filtering mechanism to extract homophily in heterophilic graphs and vice versa. In particular, we extend the graph heat equation to perform heterophilic aggregation of global information from a long distance. To further exploit information at multiple orders, we introduce a powerful graph PC-Conv and its instantiation PCNet.
• Score: 7.444454681645474
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, many carefully crafted graph representation learning methods have achieved impressive performance on either strong heterophilic or homophilic graphs, but not both. Therefore, they are incapable of generalizing well across real-world graphs with different levels of homophily. This is attributed to their neglect of homophily in heterophilic graphs, and vice versa. In this paper, we propose a two-fold filtering mechanism to extract homophily in heterophilic graphs and vice versa. In particular, we extend the graph heat equation to perform heterophilic aggregation of global information from a long distance. The resultant filter can be exactly approximated by the Possion-Charlier (PC) polynomials. To further exploit information at multiple orders, we introduce a powerful graph convolution PC-Conv and its instantiation PCNet for the node classification task. Compared with state-of-the-art GNNs, PCNet shows competitive performance on well-known homophilic and heterophilic graphs. Our implementation is available at https://github.com/uestclbh/PC-Conv.

Related papers

• When Heterophily Meets Heterogeneity: New Graph Benchmarks and Effective Methods [20.754843684170034]
  H2GB is a novel graph benchmark that brings together the complexities of both the heterophily and heterogeneous properties of graphs. Our benchmark encompasses 9 diverse real-world datasets across 5 domains, 28 baseline model implementations, and 26 benchmark results. We present a modular graph transformer framework UnifiedGT and a new model variant, H2G-former, that excels at this challenging benchmark.
  arXiv  Detail & Related papers  (2024-07-15T17:18:42Z)
• The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs [59.03660013787925]
  We introduce the Heterophily Snowflake Hypothesis and provide an effective solution to guide and facilitate research on heterophilic graphs. Our observations show that our framework acts as a versatile operator for diverse tasks. It can be integrated into various GNN frameworks, boosting performance in-depth and offering an explainable approach to choosing the optimal network depth.
  arXiv  Detail & Related papers  (2024-06-18T12:16:00Z)
• Simplified PCNet with Robustness [5.127360270463981]
  Possion-Charlier Network (PCNet) citeli2024pc, the previous work, allows graph representation to be learned from heterophily to homophily. We simplify PCNet and enhance its robustness.
  arXiv  Detail & Related papers  (2024-03-06T12:57:48Z)
• Provable Filter for Real-world Graph Clustering [11.7278692671308]
  A principled way to handle practical graphs is urgently needed. We construct two graphs that are highly homophilic and heterophilic, respectively. We validate our approach through extensive experiments on both homophilic and heterophilic graphs.
  arXiv  Detail & Related papers  (2024-03-06T12:37:49Z)
• Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
  Graphs with homophily-prone edges tend to connect nodes with the same class. Heterophily-prone edges tend to build relationships between nodes with different classes. Existing GNNs only take the original graph during training.
  arXiv  Detail & Related papers  (2023-06-13T08:06:10Z)
• Beyond Homophily: Reconstructing Structure for Graph-agnostic Clustering [15.764819403555512]
  It is impossible to first identify a graph as homophilic or heterophilic before a suitable GNN model can be found. We propose a novel graph clustering method, which contains three key components: graph reconstruction, a mixed filter, and dual graph clustering network. Our method dominates others on heterophilic graphs.
  arXiv  Detail & Related papers  (2023-05-03T01:49:01Z)
• Graph Contrastive Learning under Heterophily via Graph Filters [51.46061703680498]
  Graph contrastive learning (CL) methods learn node representations in a self-supervised manner by maximizing the similarity between the augmented node representations obtained via a GNN-based encoder. In this work, we propose an effective graph CL method, namely HLCL, for learning graph representations under heterophily. Our extensive experiments show that HLCL outperforms state-of-the-art graph CL methods on benchmark datasets with heterophily, as well as large-scale real-world graphs, by up to 7%, and outperforms graph supervised learning methods on datasets with heterophily by up to 10%.
  arXiv  Detail & Related papers  (2023-03-11T08:32:39Z)
• Single-Pass Contrastive Learning Can Work for Both Homophilic and Heterophilic Graph [60.28340453547902]
  Graph contrastive learning (GCL) techniques typically require two forward passes for a single instance to construct the contrastive loss. Existing GCL approaches fail to provide strong performance guarantees. We implement the Single-Pass Graph Contrastive Learning method (SP-GCL) Empirically, the features learned by the SP-GCL can match or outperform existing strong baselines with significantly less computational overhead.
  arXiv  Detail & Related papers  (2022-11-20T07:18:56Z)
• HL-Net: Heterophily Learning Network for Scene Graph Generation [90.2766568914452]
  We propose a novel Heterophily Learning Network (HL-Net) to explore the homophily and heterophily between objects/relationships in scene graphs. HL-Net comprises the following 1) an adaptive reweighting transformer module, which adaptively integrates the information from different layers to exploit both the heterophily and homophily in objects. We conducted extensive experiments on two public datasets: Visual Genome (VG) and Open Images (OI)
  arXiv  Detail & Related papers  (2022-05-03T06:00:29Z)
• Is Homophily a Necessity for Graph Neural Networks? [50.959340355849896]
  Graph neural networks (GNNs) have shown great prowess in learning representations suitable for numerous graph-based machine learning tasks. GNNs are widely believed to work well due to the homophily assumption ("like attracts like"), and fail to generalize to heterophilous graphs where dissimilar nodes connect. Recent works design new architectures to overcome such heterophily-related limitations, citing poor baseline performance and new architecture improvements on a few heterophilous graph benchmark datasets as evidence for this notion. In our experiments, we empirically find that standard graph convolutional networks (GCNs) can actually achieve better performance than
  arXiv  Detail & Related papers  (2021-06-11T02:44:00Z)
• 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)

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.