  Message-passing Graph Neural Networks (GNNs), which collect information from
adjacent nodes achieve dismal performance on heterophilic graphs. Various
schemes have been proposed to solve this problem, and propagating signed
information on heterophilic edges has gained great attention. Recently, some
works provided theoretical analysis that signed propagation always leads to
performance improvement under a binary class scenario. However, we notice that
prior analyses do not align well with multi-class benchmark datasets. This
paper provides a new understanding of signed propagation for multi-class
scenarios and points out two drawbacks in terms of message-passing and
parameter update: (1) Message-passing: if two nodes belong to different classes
but have a high similarity, signed propagation can decrease the separability.
(2) Parameter update: the prediction uncertainty (e.g., conflict evidence) of
signed neighbors increases during training, which can impede the stability of
the algorithm. Based on the observation, we introduce two novel strategies for
improving signed propagation under multi-class graphs. The proposed scheme
combines calibration to secure robustness while reducing uncertainty. We show
the efficacy of our theorem through extensive experiments on six benchmark
graph datasets.
