S-Mixup: Structural Mixup for Graph Neural Networks
Existing studies for applying the mixup technique on graphs mainly focus on
graph classification tasks, while the research in node classification is still
under-explored. In this paper, we propose a novel mixup augmentation for node
classification called Structural Mixup (S-Mixup). The core idea is to take into
account the structural information while mixing nodes. Specifically, S-Mixup
obtains pseudo-labels for unlabeled nodes in a graph along with their
prediction confidence via a Graph Neural Network (GNN) classifier. These serve
as the criteria for the composition of the mixup pool for both inter and
intra-class mixups. Furthermore, we utilize the edge gradient obtained from the
GNN training and propose a gradient-based edge selection strategy for selecting
edges to be attached to the nodes generated by the mixup. Through extensive
experiments on real-world benchmark datasets, we demonstrate the effectiveness
of S-Mixup evaluated on the node classification task. We observe that S-Mixup
enhances the robustness and generalization performance of GNNs, especially in
heterophilous situations. The source code of S-Mixup can be found at
\url{https://github.com/SukwonYun/S-Mixup}
Junghurn Kim, Sukwon Yun, Chanyoung Park
# S-Mixup: Structural Mixup for Graph Neural Networks

###### Abstract.

Existing studies for applying the mixup technique on graphs mainly focus on graph classification tasks, while the research in node classification is still under-explored. In this paper, we propose a novel mixup augmentation for node classification called Structural Mixup (S-Mixup). The core idea is to take into account the structural information while mixing nodes. Specifically, S-Mixup obtains pseudolabels for unlabeled nodes in a graph along with their prediction confidence via a Graph Neural Network (GNN) classifier. These serve as the criteria for the composition of the mixup pool for both inter and intra-class mixups. Furthermore, we utilize the edge gradient obtained from the GNN training and propose a gradient-based edge selection strategy for selecting edges to be attached to the nodes generated by the mixup. Through extensive experiments on real-world benchmark datasets, we demonstrate the effectiveness of S-Mixup evaluated on the node classification task. We observe that S-Mixup enhances the robustness and generalization performance of GNNs, especially in heterophilous situations. The source code of S-Mixup can be found at [https://github.com/SukwonYun/S-Mixup](https://github.com/SukwonYun/S-Mixup).

Graph Neural Networks, Mixup, Node Classification +
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

[

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

[

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

[

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

[

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: [
performance gain stems from accurately classifying high homophily nodes. However, we observe a performance drop for nodes with a relatively low homophily ratio compared to the vanilla GCN baseline. This suggests that newly generated nodes through mixup do not significantly contribute to smoothing decision boundaries and achieving generalizability. Moreover, given nodes with low homophily ratio comprise around 1/3 of all nodes (33.3% in Cora and 35.7% in Citeseer), their relatively low performance should not be ignored. This becomes critical in real-world scenarios, where disassortative nodes inevitably emerge within assortative graphs, especially when such nodes are linked to malicious activities like fraud or bots (Han et al., 2017; Li et al., 2018) negatively affecting neighbors. Hence, a balanced approach that prevents bias towards high homophily nodes, considering structural information, is vital for optimal performance.

Furthermore, existing methods such as GraphMix and Manifold Mixup lack _the ability to manage newly generated nodes_ in terms of their structural information. These methods primarily focus on obtaining representations of mixed nodes without considering their local neighborhood context. As a result, they resort to replacing existing nodes with newly generated ones instead of adding them to the graph and connecting them to existing nodes. This approach loses the opportunity to utilize the original features of the given nodes and leverage message-passing through the newly generated edges.

In this regard, with the goal of properly utilizing structural information, we propose a novel mixup method for node classification, called Structural Mixup (S-Mixup), which equips the ability to connect the relevant edges to the newly generated nodes that seamlessly align with the current graph. More precisely, we first pass the original graph through the GNN classifier to obtain two key components that enable the mixup process while incorporating structural information: pseudo-labels with prediction confidence and edge gradients. We utilize pseudo-labels with prediction confidence to expand the candidate pool for node mixup. Specifically, nodes with high and low prediction confidence are selected for the intra-class mixup, while nodes with medium confidence are used for the inter-class mixup. We then utilize the edge gradients to identify edges with high gradient values. The newly generated nodes are connected to the existing nodes and are passed through the GNN classifier. Extensive experiments illustrate that S-Mixup outperforms existing mixup-based GNNs in node classification task.

## 2. Methodology

**Notations.** Given a graph \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})\), let \(\mathcal{V}=\{v_{1},...,v_{N}\}\) denote the set of nodes, \(\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}\) denote the set of edges, and \(\mathbf{X}\in\mathbb{R}^{N\times F}\) denote the node feature matrix. We use \(\mathcal{C}\) to denote the set of classes of nodes in \(\mathcal{G}\). We define \(\mathbf{A}\in\mathbb{R}^{N\times N}\) as the adjacency matrix where \(\mathbf{A}_{ij}=1\) iff \((v_{i},v_{j})\in\mathcal{E}\) and \(\mathbf{A}_{ij}=0\) otherwise. Our main goal is to enhance performance in a node classification task.

**Our approach.** We propose a novel mixup method, Structural Mixup (S-Mixup), that incorporates structural information within newly generated nodes. We first revisit vanilla GNN to obtain two key outputs, pseudo-labels with prediction confidence and edge gradient, in Section 3.1. Then, we describe how we expand the mixup pool through the prediction confidence and conduct inter-class and intra-class mixups in Section 3.2. With edge gradients obtained via a vanilla GNN, we then demonstrate how we select edges of the newly generated nodes in Section 3.3. Finally, we propose an overall training process of S-Mixup in Section 3.4. The overall architecture of S-Mixup is illustrated in Figure 2.

### Revisiting Graph Neural Networks

Before we perform node mixup and edge selection, we first revisit the vanilla GNN to obtain key outputs that will play a significant role in the following sections. Specifically, we pass a graph through a conventional two-layer Graph Convolutional Network (Gan et al., 2017) as: \(\hat{\mathbf{Y}}=\text{softmax}(\hat{\mathbf{A}}\sigma(\hat{\mathbf{A}} \mathbf{X}\mathbf{W}^{1})\mathbf{W}^{2})\), where \(\hat{\mathbf{Y}}\in\mathbb{R}^{N\times|\mathcal{C}|}\) denotes prediction probability, \(\hat{\mathbf{A}}=\hat{\mathbf{D}}^{-1/2}\hat{\mathbf{A}}\hat{\mathbf{D}}^{-1/2}\) denotes a transition matrix where \(\hat{\mathbf{D}}\) and \(\hat{\mathbf{A}}\) indicates the self-loop included diagonal degree matrix and adjacency matrix, respectively. \(\sigma\) is the ReLU activation function, and \(\mathbf{W}^{1}\in\mathbb{R}^{F\times D}\) and \(\mathbf{W}^{2}\in\mathbb{R}^{D\times|\mathcal{C}|}\) denote trainable weight matrices that encode features into hidden embedding space, \(D\) and hidden embedding space to class space \(|\mathcal{C}|\), respectively. Here, we define one-hot transformed _pseudo-labels_ of each node as \(\hat{\mathbf{Y}}=\text{one-hot}(\text{argmax}(\hat{\mathbf{Y}}))\in\mathbb{R} ^{N\times|\mathcal{C}|}\), and _prediction confidence_ of each node as \(\mathbf{y}_{\text{conf}}=\text{max}(\hat{\mathbf{Y}})\in\mathbb{R}^{N}\), where \(0\leq\mathbf{y}_{\text{conf}}\leq 1\) due to the softmax operation. This will later serve as a criterion for node mixup. Then the node classification loss is calculated as: \(\mathcal{L}_{\text{ce}}=-\sum_{\mathbf{x}\in\mathcal{V}_{\mathcal{H}}}\sum_{ \mathbf{x}\in\mathcal{C}}\mathbf{y}_{\mathbf{y}}[c]\log(\hat{\mathbf{y}}_{ \mathbf{y}}[c])\), where \(\mathcal{V}_{\mathcal{H}}\) denotes the set of training nodes and \(\mathbf{y}_{\mathbf{y}}[c]\) is either 1 or 0 depending on the value in the \(c\)-th index of class one-hot vector of training node \(v\). During backpropagation using gradient descent within this loss, we can naturally obtain gradients with respect to an adjacency matrix, \(\hat{\mathbf{A}}\) by applying the chain rule as follows:

\[\frac{\partial\mathcal{L}_{\text{ce}}}{\partial\hat{\mathbf{A}}}=\frac{\partial \mathcal{L}_{\text{ce}}}{\partial\hat{\mathbf{Y}}}\frac{\partial\hat{\mathbf{Y }}}{\partial\hat{\mathbf{A}}}\frac{\partial\hat{\mathbf{A}}}{\partial\hat{ \mathbf{A}}}=-(\hat{\mathbf{Y}}^{-1})\cdot\{(\hat{\mathbf{A}}\mathbf{X}\mathbf{W }^{1}\mathbf{W}^{2})^{\top}\mathbf{I}+(\mathbf{X}\mathbf{W}^{1}\mathbf{W}^{2})^ {\top}\hat{\mathbf{A}}\}\cdot(\hat{\mathbf{D}}^{-1}) \tag{1}\]

It is important to note that while the adjacency matrix does not possess trainable edge weights and thus maintains a static state, its gradient does change with each epoch due to the modifications in the trainable weight parameters \(\mathbf{W}^{1}\) and \(\mathbf{W}^{2}\). Here, we define the _edge gradient_ for each edge as \(e_{ij}=\left|\frac{d\hat{\mathbf{x}}}{d\hat{\mathbf{x}}}\right|_{2},\forall i,j\leq N\), which will later serve as a criterion for edge selection.

### Confidence-based Node Mixup

Given the _pseudo-labels_\(\hat{\mathbf{Y}}\) with _prediction confidence_\(\mathbf{y}_{\text{conf}}\), we now perform mixup while considering the class information as well as its uncertainty, i.e., confidence in terms of Inter-class Mixup and Intra-class Mixup. In essence, during the Inter-class Mixup, we aim to use nodes from different classes that have medium-level confidence. This approach helps to smooth the decision boundary between classes. On the other hand, during the Intra-class Mixup, we aim to

Figure 2. Overall architecture of S-Mixup.
use nodes from the same class with high and low confidence levels. This approach enhances generalizability within a class.

**Inter-class Mixup.** The key success of mixup lies in its ability to create smoother decision boundaries, which are well-established factors contributing to a model's generalizability (Bang et al., 2017; Chen et al., 2018). Thus, to achieve such smooth decision boundaries among different classes, we utilize nodes with medium-level confidence. The intuition behind using medium-level confidence nodes is that nodes with high confidence tend to be far from the decision boundary and too discriminative (i.e., easy to classify), whereas nodes with low confidence may be too close to the decision boundary (i.e., hard to classify). Hence, we choose nodes with medium-level confidence for obtaining smooth boundaries between classes. Formally, we consider the middle \(2\)\(\pi\)% among \(\mathbf{y}_{\text{conf}}\) in each class as the inter-class mixup pool, where \(r\) is a hyperparameter. The generation of new nodes can then be achieved by randomly sampling from the inter-class mixup pool in each class, as follows:

\[\mathbf{x}_{\text{new}}^{\text{Inter}}=\lambda\mathbf{x}_{j}+(1-\lambda) \mathbf{x}_{j},\mathbf{y}_{\text{new}}^{\text{Inter}}=\lambda\tilde{\mathbf{y} }_{j}+(1-\lambda)\tilde{\mathbf{y}}_{j},\ \forall i,j\leq N\ s.t\ \tilde{\mathbf{y}}_{j}\neq \tilde{\mathbf{y}}_{j} \tag{2}\]

where \(\mathbf{x}_{\text{new}}^{\text{Inter}}\in\mathbb{R}^{F}\), \(\mathbf{y}_{\text{new}}^{\text{Inter}}\in\mathbb{R}^{|\mathcal{C}|}\) denote the feature, label of the newly generated node, respectively, and \(\lambda\in[0,1]\) is the mixing ratio, drawn from a Beta distribution with parameter \(\alpha\) fixed as 1.0.

**Intra-class Mixup.** At the same time, considering nodes within the same class is also crucial, as it can significantly influence the decision boundaries of the classes. Thanks to the pseudo-labels we previously obtained, we can now conduct intra-class mixup to achieve robust characteristics for each class. Specifically, we aim to obtain robust features for each class by interpolating between nodes with high confidence and those with low confidence. Formally, we consider the upper \(r\)\(\neq\) among \(\mathbf{y}_{\text{conf}}\) as the mixup pool for high-confidence nodes and the lower \(r\)\(\neq\) among \(\mathbf{y}_{\text{conf}}\) as the mixup pool for low-confidence nodes. Then, through random sampling from the intra-class mixup pool, i.e., high-confidence and low-confidence mixup pools, we generate new nodes in each class as follows:

\[\mathbf{x}_{\text{new}}^{\text{Intra}}=\lambda\mathbf{x}_{i}+(1-\lambda) \mathbf{x}_{j},\mathbf{y}_{\text{new}}^{\text{Intra}}=\tilde{\mathbf{y}}_{j}, \ \forall i,j\leq N\ s.t\ \hat{\mathbf{y}}_{i}=\tilde{\mathbf{y}}_{j} \tag{3}\]

where \(\mathbf{x}_{\text{new}}^{\text{Intra}}\in\mathbb{R}^{F}\) denotes the feature of the newly generated node, and \(\mathbf{y}_{\text{new}}^{\text{Intra}}\) shares the same one-hot class vector as nodes \(i\) and \(j\).

### Gradient-based Edge Selection

Recall that we are dealing with the graph-structured data where both nodes and edges play significant roles. In this regard, the subsequent challenge that naturally emerges is: _how do we create connections between the newly generated nodes and the existing ones?_ To address this question, we propose to leverage the edge gradient, \(\epsilon_{ij}\), which we acquired during the vanilla GNN in Section 3.1. The rationale behind utilizing the edge gradient is twofold: **(1)** The newly generated nodes would be in favor of being connected to nodes that can convey supervisory signals to them. Intuitively, as the training loss is derived from labeled training samples, the gradient value within an edge that is either directly connected to or located within a 1-hop distance from the original training nodes would be larger than that of an edge that is neither connected nor in vicinity of the training nodes. This tendency is corroborated by Figure 3 (a), where we report the edge gradient with respect to labeled nodes as the training epoch increases. In short, an edge with high gradient implies that it is close to the labeled nodes, and thus such an edge would be preferred for newly generated nodes in order to transmit supervised signals. **(2)** The existing nodes would prefer to be connected to newly generated nodes if these new connections can help alleviate their local and structural difficulties, particularly in heterophilous scenarios. More precisely, nodes that are surrounded by disassortative neighbors would encounter difficulties in being correctly classified, thus necessitating mitigation. This phenomenon is substantiated by Figure 3 (b), which illustrates the edge gradient dynamics for both homophilous and heterophilous situations. We observe that with increasing epochs, the edge gradient value intensifies for difficult samples, i.e., those on heterophilous edges. Consequently, for existing nodes, selecting high-gradient edges emerges as a preferable strategy for existing nodes, as it provides opportunities to better manage such heterophilous situations. To sum up, both newly generated nodes and existing nodes would benefit from being connected to edges with high gradient values.

Now, to create edges for the newly generated nodes \(\mathbf{x}_{\text{new}}^{\text{Inter}}\), \(\mathbf{x}_{\text{new}}^{\text{Intra}}\), we leverage the edge gradient obtained during the training of the vanilla GNN. In each epoch, we initially connect a generated node with the two nodes from which the node is generated. Subsequently, we expand the connections to encompass high-gradient edges that fall within the top \(m\)% of the total edge gradients with hyperparameter \(m\) and are connected to either of the two nodes involved in the node mixup. Formally, the adjacency for a newly generated node stemming from the source node \(i\) and \(j\) can be expressed as follows:

\[\mathbf{A}_{\text{new,}k}=\begin{cases}1,&\text{if }m\text{-th Percentile}(e_{..})\leq \epsilon_{kq},\ \forall k\leq N\ \text{s.t.}\ q\in\{i,j\}\\ 0,&\text{otherwise}\end{cases} \tag{4}\]

where \(e_{..}\) denote the list of all edge gradient values and \(e_{kq}\) denote edge gradient value within node \(k\) and node \(q\).

### Model Training

To sum up, the overall training process of S-Mixup is expressed as: \(\mathcal{L}_{\text{final}}=\mathcal{L}_{\text{ce}}+\eta\mathcal{L}_{\text{ mixup}}^{\text{Intra}}+(1-\eta)\mathcal{L}_{\text{mixup}}^{\text{Inter}}\), where \(\mathcal{L}_{\text{ce}}\) denotes the cross entropy loss computed from the GNN classifier with the labeled training nodes, and \(\mathcal{L}_{\text{mixup}}^{\text{Intra}}\), \(\mathcal{L}_{\text{mixup}}^{\text{Inter}}\) represent the cross entropy loss computed from GNN classifier with the newly added nodes with their corresponding pseudo-labels in intra-class mixup and inter-class, respectively, with a loss balancing hyperparameter \(\eta\). During training, since node mixup and edge connection are implemented based on the pseudo-labels and prediction confidence derived from the initial GNN, we prioritize the optimization of \(\mathcal{L}_{\text{ce}}\) loss followed by optimizing \(\eta\mathcal{L}_{\text{mixup}}^{\text{Intra}}+(1-\eta)\mathcal{L}_{\text{ mixup}}^{\text{Inter}}\) loss in our implementation.

Figure 3. Edge gradient of vanilla GCN in Cora dataset. **(a) ‘Direct & O’, ‘1-Hop & X’ represent a correctly predicted edge directly linked to labeled nodes and an incorrectly predicted edge linked to labeled nodes within 1-hop, respectively. **(b) ‘Homophilous’ denote edges connecting same labeled nodes**.
## 3. Experiments

**Datasets.** We evaluate S-Mixup on five benchmark citation datasets, namely Cora, CiteSeer, PubMed, Coauthor-CS, and Coauthor-Physics. For the split, we follow the data split setting of GraphMix (Gan et al., 2017). The detailed statistics can be found in Table 1.

**Compared Methods.** We compare S-Mixup with GCN (Golovolov et al., 2015), node-perspective mixup models such as GraphMix (Gan et al., 2017) and Manifold Mixup (Gan et al., 2017), as well as an oversampling-based model, GraphSMOTE (Gan et al., 2018), and a feature saliency-based mixup model, GraphENS (Gan et al., 2018).

**Evaluation Protocol.** All experiments are repeated ten times with randomly initialized parameters, and we present the mean accuracy and standard deviation conducted on RTX 3090 (24GB). Common hyperparameters include a learning rate chosen from \(\{0.01,0.05,0.1\}\), hidden dimensions from \(\{16,64\}\), and a fixed dropout rate of 0.5. For each model, individual hyperparameters are tuned within a range as recommended by the respective authors.

**Overall Performance.** In Table 2, S-Mixup outperforms other mixup-based models such as GraphMix and Manifold Mixup, as well as oversampling-based models like GraphSMOTE and GraphENS. The vanilla GCN model serves as the lower performance bound. Specifically, in CiteSeer dataset, our method achieves the highest performance, showing a significant improvement of 4.69% over the vanilla GCN, which is a substantial improvements considering that the performance gain of GraphMix over the vanilla GCN is 2.35%.

**Ablation Studies.** As S-Mixup employs a confidence-based node mixup for both inter-class and intra-class nodes with a gradient-based edge selection strategy, we observe several key outcomes from Table 2. **(1)** Incorporation of both inter-class and intra-class mixup is crucial to the efficacy of the node mixup technique. This integration aids not only in generating smoother decision boundaries but also in establishing a more generalized representation for each class. Figure 4 provides a detailed view of the progression of node representations as epochs grow. We observe that generated nodes in both the inter-class and intra-class mixup are placed near the decision boundaries, which aligns with the objectives of smoothing decision boundaries and creating generalized representations. **(2)** It is essential to connect the newly generated nodes with the pre-existing nodes. Our findings show that even when the proposed method is used with a low edge gradient (S-Mixup w/ low Edge), it surpasses the performance of the same method without any edge connection (S-Mixup w/o Edge). **(3)** Our proposed method is superior when using high-gradient edges rather than low-gradient ones. High-gradient edges encapsulate a greater degree of supervised information, providing an opportunity to mitigate heterophilous situations, as mentioned in Section 3.3.

**Sensitivity Analysis.** Figure 5 (a) demonstrates the hyperparameter sensitivity with respect to the sampling hyperparameter \(r\in\{0.1,0.2,0.3,0.4,0.5\}\), which is responsible for the inter- and intra-class mixup, and \(m\in\{0.1,0.2,0.3,0.4,0.5\}\) that dictates high edge gradient selection. Interestingly, our proposed method exhibits robustness against significant variations in both hyperparameters. However, favoring a joint small range for \(m\) and \(r\) appears to be beneficial. This is likely because node generation via high-confidence values (i.e., small \(r\)) and node connections via high edge gradient values (i.e., small \(m\)) introduce less uncertainty compared to their low-confidence and low-gradient counterparts. In Figure 5 (b), we also investigate the impact of the loss controlling parameter \(\eta\in\{0.1,0.2,...,0.9\}\), keeping \(m\) and \(r\) fixed. We find that a balanced consideration of both inter- and intra-class mixup, represented by \(\eta=0.5\), is advantageous for training S-Mixup.

## 4. Conclusion

In this paper, we present a novel mixup augmentation technique that thoroughly accounts for the structural information inherent in the graph domain. We identified that existing works, which do not fully incorporate structural information, fail to generalize well in heterophilous scenarios. In response to this, S-Mixup initially processes the vanilla GNN to acquire pseudo-labels along with their prediction confidence. Subsequently, we constitute the mixup pool for both inter-class and intra-class cases using nodes with medium levels of prediction confidence, and a combination of high and low confidence levels, respectively. Furthermore, to establish connections between newly generated nodes and existing ones, we employ the edge gradient-based edge selection. Through comprehensive experiments, we showed the superiority of S-Mixup in enhancing the robustness and generalization of node classification task.

**Acknowledgement: No.2021R1C1C1009081 and No.2022-0-00157.**