Improving Signed Propagation for Graph Neural Networks in Multi-Class
  Environments
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.
Yoonhyuk Choi, Jiho Choi, Taewook Ko, Chong-Kwon Kim
# Is Signed Message Essential for Graph Neural Networks?

###### Abstract

Message-passing Graph Neural Networks (GNNs), which collect information from adjacent nodes, achieve satisfying results on homophilic graphs. However, their performances are dismal in heterophilous graphs, and many researchers have proposed a plethora of schemes to solve this problem. Especially, flipping the sign of edges is rooted in a strong theoretical foundation, and attains significant performance enhancements. Nonetheless, previous analyses assume a binary class scenario and they may suffer from confined applicability. This paper extends the prior understandings to multi-class scenarios and points out two drawbacks: (1) the sign of multi-hop neighbors depends on the message propagation paths and may incur inconsistency, (2) it also increases the prediction uncertainty (e.g., conflict evidence) which can impede the stability of the algorithm. Based on the theoretical understanding, we introduce a novel strategy that is applicable to multi-class graphs. The proposed scheme combines confidence calibration to secure robustness while reducing uncertainty. We show the efficacy of our theorem through extensive experiments on six benchmark graph datasets.

## 1 Introduction

The increase in graph-structured datasets has led to rapid advancements in graph mining techniques including random walk-based node embedding and graph neural networks (GNNs). Especially, GNNs provide satisfactory performances in various applications including node classification and link prediction. The main component of GNNs is message-passing [1], where the information is propagated between nodes and then aggregated. Also, the integration of a structural property with the node features enhances the representation and the discrimination powers of GNNs substantially [1, 13, 14].

Early GNN schemes assume the network homophily where nodes of similar attributes make connections with each other based on the selection [12] or social influence theory [14]. Plain GNN algorithms [15, 16] simply perform Laplacian smoothing (a.k.a low-pass filtering) to receive low-frequency signals from neighbor nodes. Consequently, these methods fail to adequately deal with heterophilous graphs [13, 15, 14] such that even a simple MLP outperforms GNN in some cases. To relieve this problem, a plethora of clever algorithms have been proposed including the adjustment of edge coefficients [13, 12, 1, 1], aggregation of remote nodes with high similarity [18, 15], and diversified message propagation [16]. However, the majority of prior schemes [12] stipulate certain conditions of advantageous heterophily and these constraints undermine their generality and applicability.

Recently, some bodies of work allow the edge coefficients to be negative [15, 1] to preserve high-frequency signal exchanges between neighbors. Further, from the perspective of gradient flow, [1], Di Giovanni _et al._2022] shows that negative eigenvalue preserves the high-frequency signals to dominate during propagation. [1] introduces sheaf to enhance the linear separability of neural networks. Instead of changing the signs of edges, others [11, 13] assign zero-weights to disassortative connections precluding message diffusion on such edges. Here, there arises a question: _does signed messaging always yield better results than assigning zero-weights on heterophilic edges?_

To answer the above question, we conduct an empirical study and illustrate its results in Figure 1. Along with this, we aim to establish theoretical properties to compare their discrimination power. For this, recent studies [12, 13] scrutinize the changes in node features before and after message reception. Here, they provide some useful insights into using signed messages based on the node's relative degree and its homophily ratio. Nonetheless, prior analyses were confined to binary class graphs, which may detriment their applicability to generic graphs. In this paper, we extend the theorem to a multi-class scenario positing that the blind application of signed messages to multi-class graphs may increase the uncertainty of predictions. Throughout this analysis, we suggest employing confidence calibration [1, 16] which is simple yet effective to enhance the quality of predictions. To summarize,
our contributions can be described as follows:

* Contrary to prior work confined to a binary class, we tackle the signed messaging mechanism in a multi-class scenario. Our work provides fundamental insight into using signed messages and establishing the theoretical background for the development of powerful GNNs.
* We conjecture and prove that signed messages escalate the inconsistency between neighbors and increase the uncertainty in predictions. Based on this understanding, we propose a novel uncertainty reduction method using confidence calibration.
* We conduct extensive experiments on six benchmark datasets to validate our theorems and show the effectiveness of confidence calibration.

## 2 Related Work

**Graph Neural Networks (GNNs).** Under semi-supervised settings, GNNs have shown great potential by utilizing the information of adjacent nodes. Early GNN studies [1, 1] focused on the spectral graph analysis (e.g., Laplacian decomposition) in a Fourier domain. However, they suffer from large computational costs as the scale of the graph increases. GCN [13] reduced the overhead by harnessing the localized spectral convolution through the first-order approximation of a Chebyshev polynomial. Another notable approach is spatial-based GNNs [2, 1] which aggregate information in a Euclidean domain. Early spatial techniques became a stepping stone to many useful schemes that encompass relevant remote nodes as neighbors.

**GNNs on heterophilous graphs.** Traditional message-passing GNNs fail to perform well in heterophilic graphs [14]. To redeem this problem, recent studies have paid attention to the processing of disassortative edges [1, 15]. They either capture the difference between nodes or incorporate distant but similar nodes as neighbors. For example, H\({}_{2}\)GCN [13] separates ego and neighbors during aggregation. SimP-GCN [12] suggests a long-range adjacency matrix and EvenNet [11] receives messages from even-hop away nodes only. Similarly, [11] selects neighbors from the nodes without direct connections. Configuring path-level pattern [20] for finding a compatibility matrix [13] has also been proposed. Another school of methodologies either changes the sign of disassortative edges from positive to negative [1, 1, 14, 15] or assigns zero-weights to disassortative edges [1]. Even though these schemes show their effectiveness [1] on binary classes, it may require further investigations before extending their applications to a multi-class scenario.

## 3 Preliminaries

In this section, let us first define the notations and then explain the basics of the problem.

**Notations.** Let \(\mathcal{G}=(\mathcal{V},\mathcal{E},X)\) be a graph with \(|\mathcal{V}|=n\) nodes and \(|\mathcal{E}|=m\) edges. The node attribute matrix is \(X\in\mathbb{R}^{n\times F}\), where \(F\) is the dimension of an input vector. Given \(X\), the hidden representation of node features \(H^{(l)}\) (_l-th_ layer) is derived through message passing. Here, node \(i^{\prime}s\) feature is the row of \(h_{i}^{(l)}\). The structural property of \(\mathcal{G}\) can be represented by its adjacency matrix \(A\in\{0,1\}^{n\times n}\). Also, \(D\) is a diagonal matrix with node degrees \(d_{ii}=\sum_{j=1}^{n}A_{ij}\). Each node has its label \(Y\in\mathbb{R}^{n\times C}\), where \(C\) represents the number of classes. The goal of semi-supervised node classification is to predict the class of unlabeled nodes \(\mathcal{V}_{U}=\{\mathcal{V}-\mathcal{V}_{L}\}\subset\mathcal{V}\) given the partially labeled training set \(\mathcal{V}_{L}\). The global edge homophily ratio (\(B\)) is defined as:

\[B\equiv\frac{\sum_{(i,j)\in\mathcal{E}}\mathbb{1}\left(Y_{i}=Y_{j}\right)}{| \mathcal{E}|}. \tag{1}\]

Likewise, the local homophily (\(b_{i}\)) of node \(i\) is given as:

\[b_{i}\equiv\frac{\sum_{j=1}^{n}A_{ij}\cdot\mathbb{1}\left(Y_{i}=Y_{j}\right)}{ d_{ii}}. \tag{2}\]

**Empirical Analysis.** Vanilla GNNs provide dismal performances in heterophilic datasets, where most edges connect two nodes with different labels. Consequently, finding proper coefficients of entire edges became essential to enhance the overall quality of GNNs. In Fig. 1, we evaluate the node classification accuracy of GCN [13] using six benchmark graphs (the statistical details are shown in Table 1). From the original graph (vanilla GCN), we fabricate two graph variants; one that replaces disassortative edges with -1 (signed GCN), and the other that assigns zero-weights on heterophilous connections (zero-weight GCN). As illustrated in Fig. 1, the zero-weight GCN achieves the best performance, followed by the signed GCN. The detailed explanations regarding this phenomenon will be explained in Section 4.2 and 4.3.

## 4 Theoretical Analysis

We first discuss the mechanism of Message-Passing Neural Networks (MPNN) and the impact of using signed messages (SS 4.1). Then, we introduce the previous analysis of employing signed propagation on binary class graphs (SS 4.2).

Figure 1: Node classification accuracy on six benchmark datasets. Firstly, vanilla GCN utilizes the original graph. The coefficient of heterophilous edges is changed to -1 in signed GCN and to 0 in zero-weight GCN, respectively
Through this, we extend them to a multi-class scenario and point out some drawbacks under this condition (SS 4.3). Finally, we suggest a simple yet effective solution to improve the quality of signed GNNs through the integration of calibration (SS 4.4).

### Message-Passing Neural Networks

**Mechanism of Graph Neural Networks (GNNs).** Generally, most of the GNNs employ the strategy of propagation and then aggregation, where the node features are updated iteratively. This can be represented as follows:

\[H^{(l+1)}=\phi(\bar{H}^{(l+1)}),\ \ \bar{H}^{(l+1)}=AH^{(l)}W^{(l)}. \tag{3}\]

\(H^{(0)}=X\) is the initial vector and \(H^{(l)}\) is nodes' hidden representations at the _l-th_ layer. \(\bar{H}^{(l+1)}\) is retrieved through message-passing (\(A\)) and we obtain \(H^{(l+1)}\) after an activation function \(\phi\) (e.g. ReLU). \(W^{(l)}\) is the trainable weight matrices that are shared across all nodes. The final prediction is produced by applying cross-entropy \(\sigma(\cdot)\) (e.g., log-softmax) to \(\bar{H}^{(L)}\) and the loss function is defined as:

\[\mathcal{L}_{GNN}=\mathcal{L}_{nll}(Y,\widehat{Y}),\ \widehat{Y}=\sigma(\bar{H}^{(L )}). \tag{4}\]

The parameters are updated by computing negative log-likelihood loss \(\mathcal{L}_{nll}\) between the predictions (\(\widehat{Y}\)) and true labels (\(Y\)). Most GNN schemes assume that graphs are assortative and they construct the message-passing matrix (\(A\)) with positive values to preserve the low-frequency information (local smoothing) [14]. Consequently, they fail to capture the difference between node features and achieve lower performance on the heterophilous networks [13, 15].

**Meaning of using signed messages.** Recent studies [13, 16, 15] emphasize the importance of high-frequency signals and suggest flipping the sign of disassortative edges from positive to negative to preserve such signals. We first show that they can also contribute to the separation of ego and neighbors. Let us assume an ego node \(i\) and its neighbor node \(j\) is connected with a signed edge. Let us ignore other neighbor nodes to concentrate on the mechanism of signed messaging. Applying GCN [10], we obtain the output of node \(i\) as:

\[\widehat{Y}_{i}=\sigma(\bar{H}_{i}^{L})=\sigma(\frac{\bar{H}_{i}^{(L)}}{d_{i} +1}-\frac{\bar{H}_{j}^{(L)}}{\sqrt{(d_{i}+1)(d_{j}+1)}}). \tag{5}\]

Assuming that the label of the ego (\(Y_{i}\)) is \(k\), we can calculate the loss (\(\mathcal{L}_{nll}\)) between a true label \(Y_{i}\in\mathcal{R}^{C}\) and a prediction \(\widehat{Y}_{i}\in\mathcal{R}^{C}\) as below:

\[\mathcal{L}_{nll}(Y_{i},\widehat{Y}_{i})=-\log(\widehat{y}_{i,k}) \tag{6}\]

Since the column-wise components of the last weight matrix \(W^{(L)}\) act as an independent classifier, we prove that the probability of node \(j\) being a class \(k\) (\(\widehat{y}_{j,k}\)), transitions in the opposite to the node \(i\)'s probability (\(\widehat{y}_{i,k}\)) as the training epoch (\(t\)) proceeds:

\[\widehat{y}_{j,k}^{(t+1)}<\widehat{y}_{j,k}^{t},\ \widehat{y}_{i,k}^{(t+1)}> \widehat{y}_{i,k}^{t}, \tag{7}\]

where \(\widehat{y}_{i,k}^{(t+1)}=\widehat{y}_{i,k}^{t}-\eta\bigtriangledown_{i} \mathcal{L}_{nll}(Y_{i},\widehat{Y}_{i})\) and \(\widehat{y}_{j,k}^{(t+1)}=\widehat{y}_{j,k}^{t}-\eta\bigtriangledown_{j} \mathcal{L}_{nll}(Y_{i},\widehat{Y}_{i})\). Notation \(\eta\) is the learning ratio and a symbol \(\bigtriangledown\) represents a partial derivative of the loss function.

_Proof of Eq. 7 is in App. A.1._

**Motivation.** We prove that signed messages contribute to separate disassortative neighbor nodes. Nonetheless, in Fig. 1, signed GCN achieves inferior performance than zero-weighted GCN. In the following section, we analyze this phenomenon by developing our theorems from binary to multi-class scenarios.

### Using signed messages on binary classes

In this section, we aim to analyze the movements of node features given three types of graphs (original, signed, and zero-weights). We again employ GCN [10] as a baseline. Here, we assume a binary classification task (\(y_{i}\in\{0,1\}\)) similar to previous work [1, 15] and inherit several useful notations for simplifications: (1) For all nodes \(i=\{1,...,n\}\), their degrees \(\{d_{i}\}\) and features \(\{h_{i}\}\) are i.i.d. random variables. (2) We assume that every class has the same population. (3) With a slight abuse of notation, assume \(h^{(0)}=XW^{(0)}\) is the first layer projection of initial node features. (4) Given the label \(y_{i}\), the node feature follows the distribution (\(\mu\) or \(-\mu\)) as:

\[\mathbb{E}(h_{i}^{(0)}|y_{i})=\begin{cases}\mu,&\text{if }y_{i}=0\\ -\mu,&\text{if }y_{i}=1.\end{cases} \tag{8}\]

Prior work [15] introduces Theorems 4.1, 4.2 using the local homophily (Eq. 2), message passing (Eq. 3), and expectation of node features (Eq. 8). Each theorem below utilizes the original and signed graph, respectively.

**Theorem 4.1** (Binary class, vanilla GCN).: _Let us assume \(y_{i}=0\). Then, the expectation after a single-hop propagation \(\mathbb{E}(h_{i}^{(1)})\) is defined as:_

\[\mathbb{E}(h_{i}^{(1)}|y_{i},d_{i})=\frac{(2b_{i}-1)d_{i}^{\prime}+1}{d_{i}+1} \mathbb{E}(h_{i}^{(0)}|y_{i}), \tag{9}\]

_where \(d_{i}^{\prime}=\sum_{j\in\mathcal{N}_{i}}\sqrt{\frac{d_{i}+1}{d_{j}+1}}\)._

_Proof is provided in App. A.2._

The generalized version of the above theorem is described in [15], which takes two distributions \(\mu_{0},\mu_{1}\) as:

\[h_{i}\sim N(b_{i}\mu_{0}+(1-b_{i})\mu_{1},\frac{1}{\sqrt{d_{i}+1}}). \tag{10}\]

Eq. 10 reduces to Eq. 9 when \(\mu_{1}=-\mu_{0}\).

**Theorem 4.2** (Binary class, signed GCN).: _If the sign of heterophilous edges is flipped correctly under the error ratio (\(e\)), the expectation is given by:_

\[\mathbb{E}(h_{i}^{(1)}|y_{i},d_{i})=\frac{(1-2e)d_{i}^{\prime}+1}{(d_{i}+1)} \mathbb{E}(h_{i}^{(0)}|y_{i}). \tag{11}\]

_Proof can be seen in App. A.3._

Referring to this analysis, we can induce the expectation of zero-weight GCN as below:
**Theorem 4.3** (Binary class, zero-weight GCN).: _Similar to the Theorem 4.2, assigning zero weights to the heterophilous edges leads to the following feature distribution:_

\[\mathbb{E}(h_{i}^{(1)}|y_{i},d_{i})=\frac{(b_{i}-e)d_{i}^{\prime}+1}{(d_{i}+1)} \mathbb{E}(h_{i}^{(0)}|y_{i}). \tag{12}\]

_Proof can be found in App. A.4._

For all theorems, if the coefficient of \(\mathbb{E}(h_{i}^{(0)}|y_{i})\) is smaller than 1, the node feature moves towards the decision boundary and message passing loses its discrimination power [20]. Based on this observation, we can compare the discrimination powers of signed and zero-weight GCNs.

**Corollary 4.4** (Binary class, discrimination power).: _Omitting the overlapping part of Theorems 4.2 and 4.3, their difference, Z, can be induced by the error ratio (e) and homophily (\(b_{i}\)):_

\[Z=(1-2e)-(b_{i}-e)=1-e-b_{i}, \tag{13}\]

_where \(0\leq e,b_{i}\leq 1\)._

We visualize \(Z\) in Fig. 2a. Note that the space is half-divided by the plane \(Z=0\) since \(\int_{0}^{1}\int_{0}^{1}(1-e-b)\,de\,db=0\). When \(b_{i}\) and \(e\) are small, \(Z\) becomes positive which indicates that signed GCN outperforms zero-weight GCN and vice versa.

Now, let us assume that the error ratio is zero (\(e=0\)) identical to the settings of our previous analysis (Fig. 1). Under this condition, \(Z\)\((=1-b_{i})\) should be non-negative regardless of the homophily ratio (\(0\leq b_{i}\leq 1\)). However, Fig. 1 shows that zero-weight GCN generally outperforms signed GCN (\(Z\leq 0\)) contradicting the Corollary 4.4. Thus, we extend the above theorems to cover a multi-class scenario and point out the limitations in the previous analyses.

### Using signed messages on multiple classes

Without loss of generality, one can extend the expectation of node features from a binary (Eq. 8) to multiple classes through polar coordinates as below:

\[\mathbb{E}(h_{i}^{(0)}|y_{i})=(\mu,\frac{2\pi j}{C}),\ j=0,...,C-1. \tag{14}\]

Here, \(\mu\) represents the scale of a vector. The direction of the vector is determined by its label \(j\). The above equation also satisfies the origin symmetry under the binary class (\(C=2\)) since \((\mu,0)=-(\mu,\pi)\). Through this equation, we can redefine Thm. 4.1 and 4.2 for multiple class GCNs.

**Theorem 4.5** (Multi-class, signed GCN).: _Let us assume the label \(y_{i}=0\). For simplicity, we denote the coordinates of the ego \((\mu,\theta)\) as \(k\), and its neighbors \((\mu,\theta^{\prime})\) as \(k^{\prime}\), where \(\theta=0\) and \(\theta^{\prime}=\frac{2\pi j}{c}\neq 0\). Then, the expectation of \(h_{i}\) is defined as:_

\[\mathbb{E}(h_{i}^{(1)}|y_{i},d_{i})=\frac{(1-2e)\{b_{i}k+(b_{i}-1)k^{\prime}\} d_{i}^{\prime}+k}{d_{i}+1}. \tag{15}\]

_Proof is provided in App. B.1._

**Theorem 4.6** (Multi-class, zero-weight GCN).: _Likewise, the \(h_{i}^{(1)}\) driven by zero-weight GCN is:_

\[\mathbb{E}(h_{i}^{(1)}|y_{i},d_{i})=\frac{\{(1-e)b_{i}k+e(1-b_{i})k^{\prime}\} d_{i}^{\prime}+k}{d_{i}+1}. \tag{16}\]

_Proof is provided in App. B.2._

Similar to Corollary 4.4, we can compare the separability of the two methods based on their coefficients.

**Corollary 4.7** (Multi-class).: _The difference of discrimination power (\(Z\)) between signed and zero-weight GCN in the multi-class case is:_

\[Z=-eb_{i}k+(1-e)(b_{i}-1)k^{\prime} \tag{17}\]

_Then, we can induce the conditional statement as below based on the distribution of aggregated neighbors (\(k^{\prime}\)):_

\[Z\in\begin{cases}1-e-b_{i},&\text{if }k^{\prime}=-k\\ -2eb-(1-e-b_{i}),&\text{if }k^{\prime}=k.\end{cases} \tag{18}\]

_More details can be found in App. B.3._

Fig. 2b plots \(Z\) for the multi-class case. The above corollary implies that if the distribution of aggregated neighbor is origin symmetry (\(k^{\prime}=-k\)), \(Z\) (\(=1-e-b\)) becomes identical to the Eq. 13. Under this condition, signed propagation might perform well. However, as \(k^{\prime}\) gets closer to \(k\), its discrimination power degrades (\(Z\) gets smaller) as shown in the blue areas in Fig. 2b, where \(\int_{0}^{1}\int_{0}^{1}(-2eb+e+b-1)\,dedb=-1\). Intuitively, the probability of being \(k^{\prime}=-k\) may decrease as the number of classes increases, which means that the zero-weight GCN generally outperforms the signed GCN in multi-class graphs. Based on this observation, we point out some limitations below.

**Limitation of signed messages in multi-class graphs.** Now, we introduce two types of limitations (P1 and P2) that may degrade the overall quality of GNNs.

**(P1) The sign of a message from multi-hop away nodes depend on the paths through which information is transmitted.** GNNs stack multiple layers to utilize the information of multi-hop away neighbors. Here, we assume three nodes \(i,j,k\) that are connected serially and the signs of their edges are \(s_{ij}\) and \(s_{jk}\), respectively. If \(y_{i}=y_{j}\), then \(s_{ij}=1\), otherwise \(s_{ij}=-1\). To begin, let us define a message from node \(k\) to \(i\) as below:

\[h_{i}^{(2)}=h_{i}^{(1)}W^{(1)}+s_{ij}(h_{j}^{(0)}W^{(0)}+s_{jk}h_{k}^{(0)}W^{( 0)})W^{(1)}, \tag{19}\]

Figure 2: We plot the Z to compare the discrimination power of signed and zero-weight GCNs. The red and blue colored parts indicate the regions where signed GCN and zero-weight GCN have better performance, respectively
where we omit the degree scaling factor for simplicity. In the above equation, we can infer that the sign of \(h_{k}^{(0)}\) depends on the multiplication of \(s_{ij}\) and \(s_{jk}\). If the label is binary (e.g., 0 or 1), signed propagation does not degrade the overall quality since \(s_{ij}\cdot s_{jk}=1\) if \(i\) and \(k\) belong to the same class, and \(s_{ij}\cdot s_{jk}=-1\) otherwise. However, the problem occurs when employing multi-class datasets. For example, let us assume the labels of three nodes are \(y_{i}=0,y_{j}=1\), and \(y_{k}=2\). Even though \(i\) and \(k\) are in different classes, \(k\) is trained to be similar to \(i\) since \(s_{ij}\cdot s_{jk}=(-1)\times(-1)=1\). To solve this problem, one has to configure the classes of nodes on entire paths between two nodes and manually assign their signs. But this incurs high computational costs of \(O(\sum_{l=2}^{L}\sum_{i=1}^{N}\sum_{j=i}^{N}A_{ij}^{l})\). Thus, we propose to solve the second type of limitation (P2) as below.

**(P2) Signed propagation increases the uncertainty of the prediction.** Adequate management of uncertainty is vital in machine learning to generate highly confident predictions [11, 12, 13]. This is closely related to the entropy (e.g., information gain [10]) and recent work [10] formulates two types of uncertainties: the _aleatoric_ and _epistemic_ caused by the data and the model, respectively. But here, we rather focus on the conflict evidence (_dissonance_) [13, 14], which ramps up the entropy of outputs. One can easily measure the uncertainty of a prediction (\(\widehat{y}_{i}\)) using Shannon's entropy [13] as:

\[E(\widehat{y}_{i})=-\sum_{j=1}^{C}\widehat{y}_{i,j}log_{c}\widehat{y}_{i,j}. \tag{20}\]

Furthermore, measuring dissonance (_diss_) is also important [14] as it is powerful in distinguishing Out-of-Distribution (OOD) data from conflict predictions [15] and improving classification accuracy:

\[diss(\widehat{y}_{i})=\sum_{j=1}^{C}\left(\frac{\widehat{y}_{i}\sum_{k\neq j} \widehat{y}_{ik}(1-\frac{\|\widehat{y}_{ik}-\widehat{y}_{ij}\|}{\widehat{y}_{ ij}+\widehat{y}_{ik}})}{\sum_{k\neq j}\widehat{y}_{ik}}\right), \tag{21}\]

which can be defined only for non-zero elements. We show that signed messages are helpful for ego and neighbor separation from Eq. 5 to 7. Now, we posit that neighbors connected with signed edges provoke higher entropy (e.g., \(E(\widehat{y}_{i})\) or \(diss(\widehat{y}_{i})\)) than the one with a plane or zero-weighted one.

**Theorem 4.8**.: _Under multiple classes, the entropy gap between the signed neighbor \(E(\widehat{y}_{s})\) and plane (or zero) one \(E(\widehat{y}_{p})\) increases in proportion to the training epoch (\(t\))._

\[E(\widehat{y}_{s}^{(t+1)})-E(\widehat{y}_{p}^{(t+1)})>E(\widehat{y}_{s}^{t})- E(\widehat{y}_{p}^{t}). \tag{22}\]

_Proof with an example can be seen in the App. C._

To summarize, signed messages contribute to the separation of two nodes (Fig 2(a)), while they also increase the uncertainty of neighboring nodes \(j,k\) that propagate signed information to an ego \(i\) (Fig. 2(b)). To deal with this, we employ confidence calibration which will be explained below.

### Methodology

Previously, we single out two types of limitations. The optimal solution for (P1) is to configure the entire paths between two nodes and assign a proper sign. However, this might be intractable as the size of the graph increases. Instead, we propose a simple yet effective solution that can reduce the uncertainty (P2) through confidence calibration. The proposed method, free from entire path configuration, is cost-efficient and fairly powerful. Calibration is one type of self-training method [12, 13] that acts as a regularization term. Even though it has shown to be effective for generic GNNs [13], we notice that the performance gain is much greater when integrated with signed methods. Many algorithms can be used for calibration (e.g., temperature and vector scaling [12]). In this paper, our loss function is defined as,

\[\mathcal{L}_{calib}=\frac{1}{n}\sum_{i=1}^{n}(-max(\widehat{y}_{i})+submax( \widehat{y}_{i})), \tag{23}\]

where \(n=|\mathcal{V}_{valid}\cup\mathcal{V}_{test}|\) is the set of validation and test nodes. Our method is quite similar to prior work [13], but we do not utilize the label of validation sets for a fair comparison. As defined above, it penalizes the maximal and sub-maximal values to be similar in order to suppress the generation of conflict evidence. Since the calibration only utilizes the outputs \(\widehat{y}\), it has high scalability and is applicable to any type of GNNs. Integrating Eq. 23, the overall loss (\(\mathcal{L}_{total}\)) can be defined as below:

\[\mathcal{L}_{total}=\mathcal{L}_{GNN}+\lambda\mathcal{L}_{calib}. \tag{24}\]

To validate our analysis (SS 5.1), we employ several state-of-the-art methods to obtain \(\mathcal{L}_{GNN}\). The \(\lambda\) is a hyper-parameter that balances the influence of calibration. In Section 5.4, we conduct an experiment to select the \(\lambda\) that achieves the best validation score for each dataset. We describe the pseudo-code and time complexity of our algorithm in _App. D_.

\begin{table}
\begin{tabular}{c c c c c c c} \hline Datasets & Cora & Citeseer & Pubmed & Actor & Cham. & Squirrel \\ \hline \# Nodes & 2,708 & 3,327 & 19,717 & 7,600 & 2,277 & 5,201 \\ \# Edges & 10,558 & 9,104 & 88,648 & 25,944 & 33,824 & 211,872 \\ \# Features & 1,433 & 3,703 & 500 & 931 & 2,325 & 2,089 \\ \# Labels & 7 & 6 & 3 & 5 & 5 & 5 \\ \hline \end{tabular}
\end{table}
Table 1: Statistical details of six benchmark datasets

Figure 3: (a) In binary class graphs, signed propagation contributes to the separation of nodes (\(i\), \(j\)) and reduces the entropy. (b) In multi-class graphs, the uncertainty of neighboring nodes that are connected with signed edges (\(j\), \(k\)) increases
## 5 Experiments

We conducted extensive experiments to validate our theorems and to compare the performances of our method and baselines. We aim to answer the following research questions:

* **Q1** Is the calibration alleviate the uncertainty issue when integrated with the signed GNNs?
* **Q2** Do the signed messages increase the uncertainty of the final prediction?
* **Q3** Is the number of classes correlated with the prediction uncertainty?
* **Q4** How does the hyper-parameter \(\lambda\) in Eq. 24 affect on the performance?

**Datasets.** The statistical details of datasets are in Table 1. (1) _Cora, Citeseer, Pubmed_(Kipf and Welling, 2016) are citation graphs, where a node corresponds to a paper and edges are citations between them. The labels are the research topic of the papers. (2) _Actor_(Tang _et al._, 2009) is a co-occurrence graph where actors and co-occurrences in the same movie are represented as nodes and edges, respectively. The labels are five types of actors. (3) _Chameleon, Squirrel_(Rozemberczki _et al._, 2019) are Wikipedia hyperlink networks. Each node is a web page and the edges are hyperlinks. Nodes are categorized into five classes based on monthly traffic.

**Baselines.** We employ several state-of-the-art methods for validation: (1) Plane GNNs: GCN (Kipf and Welling, 2016), and APPNP (Klicpera _et al._, 2018). (2) GNNs for heterophilous graphs: GAT (Velickovic _et al._, 2017), GCNII (Chen _et al._, 2020), H\({}_{2}\)GCN (Zhu _et al._, 2020), and PTDNet (Luo _et al._, 2021). (3) GNNs with signed propagation: GPRGNN (Chien _et al._, 2020), FAGCN (Bo _et al._, 2021), and GGCN (Yan _et al._, 2021).

_Details of implementation and baselines are in App. E._

### Experimental Results (Q1)

In Table 2, we describe the node classification accuracy of each method. A symbol (\(\ddagger\)) means that calibration is supplemented to the basic method. Now, let us analyze the results from two perspectives.

**Homophily ratio plays an important role in GNNs.** Three citation networks have higher homophily compared to others. We can see that all methods perform well under homophilic datasets. As homophily decreases, methods that adjust weights depending on associativity outperform plain GNNs. Similarly, using signed messages (GPRGNN, FAGCN, and GGCN) has shown to be effective here. They achieve notable performance for both homophilic and heterophilic datasets, which means the separation of ego and neighbors (H\({}_{2}\)GCN) is quite important.

**Calibration improves the overall quality and alleviates uncertainty.** We apply calibration (\(\ddagger\)) to signed GNNs (GPRGNN, FAGCN, and GGCN). We also apply calibration to GCN and GAT. The average improvements of three signed GNNs by calibration are 4.37%, 3.1%, and 3.13%, respectively. The improvements are greater than those of GCN(r) (2.65%) and GAT(r) (1.97%). Additionally, we describe the dissonance (Eq. 21) of each method in a bracket, where the calibrated methods show lower values than the corresponding

\begin{table}
\begin{tabular}{l c c c c c c c c} \hline \hline Datasets & Cora & Citeseer & Pubmed & Actor & Chameleon & Squirrel \\ Hom. (Eq. 1) & 0.81 & 0.74 & 0.8 & 0.22 & 0.23 & 0.22 & \\ \hline GCN & 79.0 \(\pm\)0.6\% (0.17) & 67.5 \(\pm\)0.8\% (0.29) & 77.6 \(\pm\)0.2\% (0.53) & 20.2 \(\pm\)0.4\% (0.29) & 49.3 \(\pm\)0.5\% (0.19) & 31.7 \(\pm\)0.7\% (0.31) \\
**GCN\({}^{\ddagger}\)** & 81.0 \(\pm\)0.9\% (0.12) & 71.3 \(\pm\)1.2\% (0.14) & 77.8 \(\pm\)0.4\% (0.38) & 21.7 \(\pm\)0.6\% (0.62) & 49.4 \(\pm\)0.6\% (0.25) & 31.5 \(\pm\)0.6\% (0.58) \\ APPNP & 81.3 \(\pm\)0.5\% (0.15) & 68.9 \(\pm\)0.3\% (0.21) & 79.0 \(\pm\)0.3\% (0.42) & 23.8 \(\pm\)0.3\% (0.49) & 48.0 \(\pm\)0.7\% (0.34) & 30.4 \(\pm\)0.6\% (0.69) \\ \hline GAT & 80.1 \(\pm\)0.6\% (0.22) & 68.0 \(\pm\)0.7\% (0.25) & 78.0 \(\pm\)0.4\% (0.45) & 22.5 \(\pm\)0.3\% (0.28) & 47.9 \(\pm\)0.8\% (0.17) & 30.8 \(\pm\)0.9\% (0.27) \\
**GAT\({}^{\ddagger}\)** & 81.4 \(\pm\)0.4\% (0.12) & 72.2 \(\pm\)0.6\% (0.08) & 78.3 \(\pm\)0.3\% (0.39) & 23.2 \(\pm\)1.8\% (0.43) & 49.2 \(\pm\)0.4\% (0.16) & 30.3 \(\pm\)0.8\% (0.40) \\ GCNII & 81.1 \(\pm\)0.7\% (0.08) & 68.5 \(\pm\)1.4\% (0.13) & 78.5 \(\pm\)0.4\% (0.20) & 25.9 \(\pm\)1.2\% (0.43) & 48.1 \(\pm\)0.7\% (0.16) & 29.1 \(\pm\)0.9\% (0.24) \\ H\({}_{2}\)GCN & 80.6 \(\pm\)0.6\% (0.16) & 68.2 \(\pm\)0.7\% (0.22) & 78.5 \(\pm\)0.3\% (0.29) & 25.6 \(\pm\)1.0\% (0.34) & 47.3 \(\pm\)0.8\% (0.19) & 31.3 \(\pm\)0.7\% (0.62) \\ PTDNet & 81.2 \(\pm\)0.6\% (0.24) & 69.5 \(\pm\)0.8\% (0.42) & 78.8 \(\pm\)0.5\% (0.44) & 21.5 \(\pm\)0.6\% (0.33) & 50.8 \(\pm\)0.9\% (0.17) & 32.1 \(\pm\)0.7\% (0.34) \\ \hline GPRGNN\({}^{\ddagger}\) & 82.2 \(\pm\)0.4\% (0.25) & 70.4 \(\pm\)0.8\% (0.43) & 79.1 \(\pm\)0.1\% (0.26) & 25.4 \(\pm\)0.2\% (0.55) & 49.8 \(\pm\)0.7\% (0.25) & 30.5 \(\pm\)0.6\% (0.36) \\
**GPRGNN\({}^{\ddagger}\)** & 84.8 \(\pm\)0.2\% (0.05) & 73.3 \(\pm\)0.5\% (0.06) & 79.9 \(\pm\)0.2\% (0.14) & 27.7 \(\pm\)1.3\% (0.041) & 50.3 \(\pm\)0.3\% (0.20) & 31.0 \(\pm\)0.4\% (0.17) \\ FAGCN & 80.9 \(\pm\)0.5\% (0.15) & 68.8 \(\pm\)0.6\% (0.17) & 79.0 \(\pm\)0.5\% (0.31) & 25.2 \(\pm\)0.8\% (0.66) & 46.5 \(\pm\)1.1\% (0.25) & 30.4 \(\pm\)0.4\% (0.64) \\
**FAGCN\({}^{\ddagger}\)** & 83.5 \(\pm\)0.4\% (0.10) & 73.4 \(\pm\)0.5\% (0.08) & 79.7 \(\pm\)0.2\% (0.20) & 27.6 \(\pm\)0.5\% (0.51) & 48.6 \(\pm\)0.7\% (0.20) & 31.3 \(\pm\)0.5\% (0.52) \\ GGCN & 80.0 \(\pm\)1.2\% (0.38) & 68.7 \(\pm\)1.6\% (0.30) & 78.2 \(\pm\)0.4\% (0.47) & 23.0 \(\pm\)0.5\% (0.47) & 48.5 \(\pm\)0.7\% (0.15) & 30.2 \(\pm\)0.7\% (0.40) \\
**GGCN\({}^{\ddagger}\)** & 82.7 \(\pm\)0.8\% (0.07) & 72.2 \(\pm\)0.4\% (0.05) & 78.7 \(\pm\)0.3\% (0.35) & 24.1 \(\pm\)0.4\% (0.31) & 50.3 \(\pm\)0.4\% (0.08) & 30.8 \(\pm\)0.6\% (0.17) \\ \hline \hline \end{tabular}
\end{table}
Table 2: Mean node classification accuracy (%) with standard deviation on six datasets. A shadowed grid indicates the best performance. Values in bracket stand for the dissonance defined in Eq. 21 and symbol \(\ddagger\) means that calibration is applied to baseline method

Figure 4: Comparison of the dissonance on three graph variants; vanilla GCN, signed GCN, and zero-weight GCN (Q2)
vanilla model. To summarize, the results indicate that calibration not only contributes to reducing uncertainty but also improves the accuracy of signed GNNs significantly.

### Correlation of using signed messages and the uncertainty (Q2)

To show that signed messages increase uncertainty, we assume three types of graphs for GCN [13] using four datasets. Specifically, we fabricate two graph variants, signed GCN and zero-weight GCN. Here, we remove the randomness for a fair comparison. The results are illustrated in Fig. 4, where the x-axis is the number of layers and the y-axis represents dissonance. Referring to Thm. 4.8, the uncertainty is higher on signed GCN for all shallow layers. As we stack more layers, the entropy of vanilla GCN increases dramatically on heterophilous datasets, the Chameleon and Squirrel. In other words, plain GCN fails to discriminate the ego and neighbors (over-smoothing) and yields low classification accuracy.

### Case Study (Q3)

Theoretical analyses confirm that signed messages increase the uncertainty in multi-class graphs (SS 4.3). They have shown to be effective when \(k^{\prime}\) gets closer to \(-k\) (Eq. 18), but this probability is inversely proportional to the number of classes \(c\). To further analyze this phenomenon, we compare the dissonance of two variants of GCN (signed GCN and zero-weight GCN) by decrement of the number of classes (\(c\)). Specifically, if the original data contains seven classes (e.g., Cora), we remove all the nodes that belong to the rightmost class to generate a graph with six labels. The results are illustrated in Fig. 5. As can be seen, zero-weight GCN (red) tends to have lower dissonance under multiple classes. However, under binary classes (\(c\)=2), signed GCN (blue) shows lower uncertainty with the aid of ego-neighbor separation. In the binary case, zero-weight GCN only utilizes homophilous neighbors and fails to generalize under this condition.

### Hyper-parameter Analysis (Q4)

We conduct an experiment to investigate the effect of hyper-parameter \(\lambda\) (Eq. 24) that controls the impact of calibration. We tune the \(\lambda\) from 0 to 1 and choose the one with the best validation score. In Figure 6, we describe the node classification accuracy on four benchmark datasets. The blue line represents calibrated GCN, while others are signed GNNs with calibration. Firstly, we notice that GPRCNN\({}^{\ddagger}\) achieves the best performance on Cora, Citeseer, and Chameleon datasets. The performance gain in signed GNNs is restricted by the original node classification accuracy. For example, in the Squirrel dataset, GCN outperforms all baselines. Proper calibration helps to improve the performances but is limited by the inherent low capability of base models in heterophilous graphs. Further, assigning the same weights to \(\mathcal{L}_{GNN}\) and \(\mathcal{L}_{calib}\) generally downgrades the overall performance, which necessitates careful assignment of \(\lambda\) to achieve the optimal results for each dataset.

## 6 Conclusion

In this work, we provide a new theoretical perspective on using signed messages for node embedding under multi-class benchmark datasets. Firstly, we show that signed messages contribute to the separation of heterophilous neighbors in a binary class, which is consistent with conventional studies. Then, we extend previous theorems to a multi-class scenario and point out two critical limitations of using signed propagation: (1) it may incur inconsistency between nodes, and (2) increases the probability of generating conflict evidence. Based on the observations, we employ calibration for signed GNNs to reduce uncertainty and enhance the quality. Through experimental analysis, we show that our method is beneficial for both homophilic and heterophilic graphs. We claim that our theorems can provide insights to develop a better aggregation scheme for future GNN studies.

Figure 5: By differentiating the number of classes, we compare the dissonance of GCN using two graph variants (Q3)

Figure 6: The effect of hyper-parameter \(\lambda\) in Eq. 24 on the classification accuracy of four calibrated methods (Q4)