Powerful Graph Convolutioal Networks with Adaptive Propagation Mechanism for Homophily and Heterophily

• URL: http://arxiv.org/abs/2112.13562v1
• Date: Mon, 27 Dec 2021 08:19:23 GMT
• Title: Powerful Graph Convolutioal Networks with Adaptive Propagation Mechanism for Homophily and Heterophily
• Authors: Tao Wang and Rui Wang and Di Jin and Dongxiao He and Yuxiao Huang
• Abstract summary: Graph Convolutional Networks (GCNs) have been widely applied in various fields due to their significant power on processing graph-structured data. Existing methods deal with heterophily by mainly aggregating higher-order neighborhoods or combing the immediate representations. This paper proposes a novel propagation mechanism, which can automatically change the propagation and aggregation process according to homophily or heterophily.
• Score: 38.50800951799888
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Convolutional Networks (GCNs) have been widely applied in various fields due to their significant power on processing graph-structured data. Typical GCN and its variants work under a homophily assumption (i.e., nodes with same class are prone to connect to each other), while ignoring the heterophily which exists in many real-world networks (i.e., nodes with different classes tend to form edges). Existing methods deal with heterophily by mainly aggregating higher-order neighborhoods or combing the immediate representations, which leads to noise and irrelevant information in the result. But these methods did not change the propagation mechanism which works under homophily assumption (that is a fundamental part of GCNs). This makes it difficult to distinguish the representation of nodes from different classes. To address this problem, in this paper we design a novel propagation mechanism, which can automatically change the propagation and aggregation process according to homophily or heterophily between node pairs. To adaptively learn the propagation process, we introduce two measurements of homophily degree between node pairs, which is learned based on topological and attribute information, respectively. Then we incorporate the learnable homophily degree into the graph convolution framework, which is trained in an end-to-end schema, enabling it to go beyond the assumption of homophily. More importantly, we theoretically prove that our model can constrain the similarity of representations between nodes according to their homophily degree. Experiments on seven real-world datasets demonstrate that this new approach outperforms the state-of-the-art methods under heterophily or low homophily, and gains competitive performance under homophily.

Related papers

• Leveraging Invariant Principle for Heterophilic Graph Structure Distribution Shifts [42.77503881972965]
  Heterophilic Graph Neural Networks (HGNNs) have shown promising results for semi-supervised learning tasks on graphs. How to learn invariant node representations on heterophilic graphs to handle this structure difference or distribution shifts remains unexplored. We propose textbfHEI, a framework capable of generating invariant node representations through incorporating heterophily information.
  arXiv  Detail & Related papers  (2024-08-18T14:10:34Z)
• 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)
• Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All? [61.35457647107439]
  Most real-world homophilic and heterophilic graphs are comprised of a mixture of nodes in both homophilic and heterophilic structural patterns. We provide evidence that Graph Neural Networks(GNNs) on node classification typically perform admirably on homophilic nodes. We then propose a rigorous, non-i.i.d PAC-Bayesian generalization bound for GNNs, revealing reasons for the performance disparity.
  arXiv  Detail & Related papers  (2023-06-02T07:46:20Z)
• RAW-GNN: RAndom Walk Aggregation based Graph Neural Network [48.139599737263445]
  We introduce a novel aggregation mechanism and develop a RAndom Walk Aggregation-based Graph Neural Network (called RAW-GNN) method. The new method utilizes breadth-first random walk search to capture homophily information and depth-first search to collect heterophily information. It replaces the conventional neighborhoods with path-based neighborhoods and introduces a new path-based aggregator based on Recurrent Neural Networks.
  arXiv  Detail & Related papers  (2022-06-28T12:19:01Z)
• Heterogeneous Graph Neural Networks using Self-supervised Reciprocally Contrastive Learning [102.9138736545956]
  Heterogeneous graph neural network (HGNN) is a very popular technique for the modeling and analysis of heterogeneous graphs. We develop for the first time a novel and robust heterogeneous graph contrastive learning approach, namely HGCL, which introduces two views on respective guidance of node attributes and graph topologies. In this new approach, we adopt distinct but most suitable attribute and topology fusion mechanisms in the two views, which are conducive to mining relevant information in attributes and topologies separately.
  arXiv  Detail & Related papers  (2022-04-30T12:57:02Z)
• Block Modeling-Guided Graph Convolutional Neural Networks [17.39859951491802]
  Graph Convolutional Network (GCN) has shown remarkable potential of exploring graph representation. We introduce block modeling into the framework of GCN so that it can realize "block-guided classified aggregation" GCN is able to aggregate information from homophilic and heterophilic neighbors discriminately according to their homophily degree.
  arXiv  Detail & Related papers  (2021-12-27T04:52:11Z)
• 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)
• Graph Neural Networks with Heterophily [40.23690407583509]
  We propose a novel framework called CPGNN that generalizes GNNs for graphs with either homophily or heterophily. We show that replacing the compatibility matrix in our framework with the identity (which represents pure homophily) reduces to GCN.
  arXiv  Detail & Related papers  (2020-09-28T18:29: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.