PathMLP: Smooth path towards high-order homophily.

Area of Science:

• Graph Neural Networks
• Machine Learning
• Network Science

Background:

• Real-world graphs increasingly exhibit heterophily, where nodes connect to dissimilar nodes, challenging traditional Graph Neural Network (GNN) homophily assumptions.
• Classical GNNs struggle with heterophily, leading to performance degradation due to reliance on node similarity for learning.
• Existing methods to capture high-order information in GNNs often suffer from over-smoothing, inefficient computation, and underutilization of relevant data.

Purpose of the Study:

• To address the limitations of classical GNNs in heterophilous graph settings.
• To develop a novel approach that effectively utilizes high-order graph information for improved node representation learning.
• To propose a computationally efficient and over-smoothing-immune model for heterophilous graphs.

Main Methods:

• A similarity-based path sampling strategy was designed to identify and capture smooth paths exhibiting high-order homophily.
• A lightweight model, PathMLP, was developed using multi-layer perceptrons (MLPs) for encoding path-based messages.
• Adaptive path aggregation was employed to learn robust node representations in heterophilous graph environments.

Main Results:

• PathMLP demonstrated superior performance, outperforming baseline methods on 16 out of 20 benchmark datasets.
• The proposed method effectively alleviates the performance degradation caused by graph heterophily.
• PathMLP proved immune to the over-smoothing problem common in deep GNN architectures and exhibited high computational efficiency.

Conclusions:

• PathMLP offers an effective and efficient solution for node representation learning in heterophilous graphs by exploiting high-order homophilous information.
• The model's ability to handle graph heterophily and avoid over-smoothing makes it a valuable advancement in GNN research.
• The proposed path sampling and MLP-based aggregation strategy provides a promising direction for future GNN development.