Beyond Binary: Improving Signed Message Passing in Graph Neural Networks for Multi-Class Graphs.

Area of Science:

• Computer Science
• Machine Learning
• Graph Neural Networks

Background:

• Graph Neural Networks (GNNs) excel on homophilic graphs but falter on heterophilic ones.
• Signed propagation, using negative weights for heterophilic edges, shows promise but lacks multi-class theoretical backing.

Purpose of the Study:

• To provide new theoretical insights into GNNs for multi-class heterophilic graphs.
• To identify and address the limitations of signed propagation in these complex scenarios.

Main Methods:

• Developed new theoretical frameworks for GNNs in multi-class settings.
• Introduced two novel calibration strategies to enhance discrimination and reduce prediction entropy.
• Conducted extensive theoretical and experimental analyses.

Main Results:

• Signed propagation can degrade neighbor separability and increase prediction uncertainty in multi-class graphs.
• The proposed calibration strategies effectively improve discrimination power and reduce prediction entropy.
• Enhanced performance for both signed and general message-passing neural networks was demonstrated.

Conclusions:

• The novel calibration strategies offer significant improvements for GNNs on multi-class heterophilic graphs.
• These methods mitigate the identified drawbacks of signed propagation, leading to more stable and accurate predictions.