Understanding and Enhancing Message Passing on Heterophilic Graphs via Compatibility Matrix

Graph Neural Networks (GNNs) excel in graph mining tasks thanks to their message-passing mechanism, which aligns with the homophily assumption. However, connected nodes can also exhibit inconsistent behaviors, termed heterophilic patterns, sparking interest in heterophilic GNNs (HTGNNs). Although the message-passing mechanism seems unsuitable for heterophilic graphs owing to the propagation of dissimilar messages, it is still popular in HTGNNs and consistently achieves notable success. Some efforts have investigated such an interesting phenomenon, but are limited in the data perspective. The model-perspective understanding remains largely unexplored, which is conducive to guiding the designs of HTGNNs. To fill this gap, we build the connection between node discriminability and the compatibility matrix (CM). We reveal that the effectiveness of the message passing in HTGNNs may be credited to increasing the proposed Compatibility Matrix Discriminability (CMD). However, the issues of sparsity and noise pose great challenges to leveraging CM. Thus, we propose CMGNN, a novel approach to alleviate these issues while enhancing the CM and node embeddings explicitly. A thorough evaluation involving 13 datasets and comparison against 20 well-established baselines highlights the superiority of CMGNN.

Authors

• Zhuonan Zheng
• Yuanchen Bei
• Zhiyao Zhou
• Sheng Zhou College of Computer Science, Zhejiang University, China
• Yao Ma
• Ming Gu Beijing National Research Center for Information Science and Technology (BNRist), Tsinghua University, Beijing, China School of Software, Tsinghua University, Beijing, China
• HONGJIA XU
• Jiawei Chen State Key Laboratory of Blockchain and Data Security, Zhejiang University College of Computer Science, Zhejiang University, China Hangzhou High-Tech Zone (Binjiang) Institute of Blockchain and Data Security
• Jiajun Bu Zhejiang University

Keywords

No keywords are indexed for this paper.