# BuffGraph: Enhancing Class-Imbalanced Node Classification via Buffer Nodes

Qian Wang  National University of Singapore<EMAIL_ADDRESS>,  Zemin Liu
National University of Singapore<EMAIL_ADDRESS>,  Zhen Zhang  National
University of Singapore<EMAIL_ADDRESS>and  Bingsheng He  National University
of Singapore<EMAIL_ADDRESS>
(2018; 20 February 2007; 12 March 2009; 5 June 2009)

###### Abstract.

Class imbalance in graph-structured data, where minor classes are
significantly underrepresented, poses a critical challenge for Graph Neural
Networks (GNNs). To address this challenge, existing studies generally
generate new minority nodes and edges connecting new nodes to the original
graph to make classes balanced. However, they do not solve the problem that
majority classes still propagate information to minority nodes by edges in the
original graph which introduces bias towards majority classes. To address
this, we introduce BuffGraph, which inserts buffer nodes into the graph,
modulating the impact of majority classes to improve minor class
representation. Our extensive experiments across diverse real-world datasets
empirically demonstrate that BuffGraph outperforms existing baseline methods
in class-imbalanced node classification in both natural settings and
imbalanced settings. Code is available at
https://anonymous.4open.science/r/BuffGraph-730A.

node classification; class imbalance; heterophily; graph neural network

††copyright: acmlicensed††journalyear: 2018††doi: XXXXXXX.XXXXXXX††conference:
Make sure to enter the correct conference title from your rights confirmation
emai; June 03–05, 2018; Woodstock, NY††isbn: 978-1-4503-XXXX-X/18/06††ccs:
Computing methodologies Learning latent representations††ccs: Mathematics of
computing Graph algorithms

##  1\. Introduction

Graphs are powerful tools for representing complex data and relationships, as
they can effectively encapsulate vast amounts of information (Cao et al.,
2016). Among various methods for graph analytics, graph representation
learning stands out for its ability to convert high-dimensional graph data
into a lower-dimensional space while retaining essential information (Cai et
al., 2018). Recent years have witnesses the rapid development of graph
representations, especially the Graph Neural Networks (GNN) (Kipf and Welling,
2016; Veličković et al., 2017; Hamilton et al., 2017). Among tasks on graphs,
node classification has been important in real-world graphs such as
classifying influencers in the social network (Bhadra et al., 2023) and
detecting fraudsters in financial activities (Lin et al., 2022; Shamsi et al.,
2022).

Typically, GNN models are designed to operate under the assumption of class
label balance, learning node features through neighborhood aggregation and
presuming node similarity within these neighborhoods (Kipf and Welling, 2016;
Veličković et al., 2017; Hamilton et al., 2017). However, this assumption does
not hold across many real-world graphs, which often exhibit significant class
imbalances. For example, the number of frauster accounts in the Ethereum
network is much smaller than normal accounts (Wang et al., 2023). Such class
imbalances lead to a skewed performance between majority and minority classes,
inherently biasing the the model towards majority classes (Zhou and Gong,
2023). Consequently, directly applying GNNs to class-imbalanced graphs risks
underrepresenting the minority classes, highlighting the need for approaches
that can effectively address this imbalance.

To address this problem, multiple imbalanced node classification methods have
been proposed (Zhao et al., 2021; Park et al., 2022; Song et al., 2022; Zhou
and Gong, 2023; Li et al., 2023). These methods can be categorized into two
perspectives: data-level and algorithm-level. The data-level methods focus on
balancing data distributions. For example, GraphSMOTE utilizes SMOTE to
interpolate synthesize new minority nodes between two minority nodes in the
embedding space (Zhao et al., 2021). GraphENS (Park et al., 2022) resolves
this problem by synthesizing new nodes by mixing minority and majority nodes.
GraphSR augments minority classes from unlabelled nodes in the graph (Zhou and
Gong, 2023). GraphSHA synthesizes harder minority samples to enlarge the minor
decision boundaries (Li et al., 2023). In contrast, algorithm-level method TAM
(Song et al., 2022) optimizes GraphENS by adjusting the margin of each
minority node based on its neighborhood.

Despite their effectiveness, these methods predominantly address imbalance
from a node generation perspective, without directly tackling the critical
issue of heterophily — the tendency for nodes to connect across different
classes, which significantly influences performance. As depicted in Figure 1,
those minority classes with higher heterophily present a worse node
classification accuracy. The primary limitation of prior approaches is their
inability to effectively manage heterophily within their frameworks, thereby
constraining their overall performance in real-world applications where
heterophily is prevalent.

In this study, we address the challenge of class-imbalanced node
classification by focusing on mitigating heterophily, a critical factor that
significantly impacts the predictive performance for minority classes.
Heterophily, the phenomenon where edges predominantly link nodes of different
classes, presents a unique challenge in the realm of GNN particularly due to
the failure of message passing mechanisms when adjacent nodes belong to
distinct classes. This issue is compounded in scenarios characterized by a
stark imbalance between major and minor classes, raising the question: how can
we effectively address heterophily in such contexts to enhance classification
outcomes? To answer this question, we hypothesize that instead of sampling
nodes and edges subjectively, inserting buffer nodes into each edge can
improve the performance of class-imbalanced node classification. And we show
the performance change after inserting buffer nodes of two datasets:
CoauthorCS and WikiCS in the Figure 1. Heterophily is determined by analyzing
the proportion of a node’s one-hop neighbors that share the different labels
as the node itself. Here we introduce the heterophily score of each class’s
definition: the average of heterophily of each node in this class. As
illustrated in Figure 1, the insertion of buffer nodes results in a noticeable
improvement in accuracy across most classes especially those classes have a
higher heterophily score.

Figure 1. Comparative analysis of class-wise accuracy improvements before and
after node insertion for the Coauthor-CS (left) and WikiCS (right) datasets.
Classes are organized in descending order according to the number of samples
per class. The heterophily score depicted corresponds to the average
heterophily score across samples within each class, offering insights into the
impact of node insertion on class-wise performance considering the underlying
heterophily dynamics.

Informed by our preceding experiments and the critical need to navigate the
challenges posed by heterophily in graph structures, especially within the
realm of class-imbalanced node classification, we have developed BuffGraph, an
innovative model tailored to counteract heterophily’s adverse effects.
BuffGraph aims to improve prediction accuracy across both majority and
minority classes comprehensively. Central to the BuffGraph methodology is the
nuanced tailoring of message passing, which is delicately fine-tuned to match
the heterophily level of each edge. BuffGraph distinguishes itself by
employing buffer nodes to intelligently modulate the graph’s heterophily.
Buffer nodes are defined as artificial nodes inserted between existing nodes
connected by an edge, serving as intermediaries that adjust the flow of
information across the network. Buffer nodes are designed without labels,
positioning them as neutral elements within the graph. This absence of labels
allows buffer nodes to act purely as modulators of the information flow,
without directly influencing the class-specific dynamics of message passing.
Specifically, for edges characterized by high heterophily, BuffGraph
predominantly routes message passing through these buffer nodes, effectively
tempering the heterophily’s impact. Conversely, for connections exhibiting low
heterophily, it minimizes the intermediary role of buffer nodes, allowing for
more direct message passing. Such adaptability ensures that BuffGraph adeptly
addresses the distinct heterophily challenges presented by different classes,
facilitating more precise and fair predictions within class-imbalanced graphs.

To rigorously evaluate the efficacy of our BuffGraph, we conduct experiments
on a variety of real-world datasets, including co-purchase networks
(AmazonPhotos and AmazonComputers (Shchur et al., 2018)), co-authorship
networks (CoauthorCS and CoauthorPhysics (Sen et al., 2008)), and a Wikipedia-
based dataset (WikiCS (Mernyei and Cangea, 2020)). These datasets are well-
acknowledged for their relevance and complexity, offering a robust framework
for testing. Our experiment settings are designed to be comprehensive and
rigorous, comparing BuffGraph’s performance against several baseline models
across natural splitting and imbalanced splitting settings. The results
demonstrate that BuffGraph consistently outperforms the baseline models (Zhao
et al., 2021; Park et al., 2022; Song et al., 2022; Li et al., 2023) in most
configurations and datasets. For instance, under the naturally splitting
scenario, BuffGraph exhibits its superiority by achieving a 3% increase in
accuracy, a 2% enhancement in balanced accuracy, and a significant 4% boost in
F1-score on the Amazon-Computers dataset compared to the second-best outcomes.
Conversely, within the imbalanced splitting framework, BuffGraph continues to
excel, marking a 2% improvement in accuracy, a 1% gain in balanced accuracy,
and a 1.5% uplift in F1-score on the Amazon-Computers dataset relative to the
runner-up results. These findings underscore BuffGraph’s adaptability and
efficacy in addressing class imbalances across diverse real-world graph
scenarios.

In summary, our work introduces several key contributions:

  * •

We propose the BuffGraph model, a novel approach ingeniously crafted to refine
message passing for each edge in a graph. This model is specifically
engineered to address the significant challenge of heterophily in scenarios of
class imbalance during node classification, ensuring precise and effective
communication between nodes.

  * •

Through extensive experimental evaluations, BuffGraph is shown to outperform
an array of baseline models in terms of performance and adaptability. This
clearly establishes its superiority and benchmark setting capability in
handling diverse graph data complexities.

  * •

The insights derived from our study not only highlight the practical efficacy
of the BuffGraph model but also pave new avenues for future explorations into
the nuanced interplay of heterophily in class-imbalanced graph data analysis.

##  2\. Preliminary

In this section, we introduce the notations and definitions appearing in our
BuffGraph model.

###  2.1. Graph Notations

In this study, we address the challenge of class-imbalanced node
classification on an unweighted, undirected graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}=\\{v_{1},\cdots,v_{N}\\}$ represents the set of $N$ nodes, and
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ denotes the edges. The
graph structure is captured by an adjacency matrix
$\boldsymbol{A}\in\\{0,1\\}^{N\times N}$, with $\boldsymbol{A}_{ij}=1$
indicating an edge between nodes $v_{i}$ and $v_{j}$. Node features are
represented by a matrix $\boldsymbol{X}\in\mathbb{R}^{N\times d}$, where each
row $\boldsymbol{X}_{i}\in\mathbb{R}^{d}$ corresponds to the $d$-dimensional
features of node $v_{i}$. Each node $v$ is labeled with one of $C$ classes,
$\boldsymbol{Y}(v)\in\\{1,\cdots,C\\}$, with $\boldsymbol{Y}_{c}$ encompassing
all nodes in class $c$.

The training subset $\mathcal{V}^{L}\subset\mathcal{V}$, particularly in
imbalanced settings, is characterized by class size disparities, quantified by
the imbalance ratio
$\rho=\max\\{|\boldsymbol{Y}_{i}|\\}^{C}_{i=1}/\min\\{|\boldsymbol{Y}_{j}|\\}^{C}_{j=1}$,
reflecting the size proportion between the largest and smallest classes. This
setup underscores the complexities of achieving fair and accurate
classification across diverse class distributions in graph-based learning
scenarios.

###  2.2. Node Classification via GNN

GNN serve as a cornerstone for node classification within graph-structured
data. The functionality of the $l$-th layer in GNNs is calculated through a
set of operations: the message function $m_{l}$, the aggregation function
$\psi_{l}$, and the update function $\gamma_{l}$ (Park et al., 2022). The
update process for a node $v$’s feature $x_{v}^{(l+1)}$ from its $l$-th layer
feature $x_{v}^{(l)}$ is given by:

(1)
$x_{v}^{(l+1)}=\gamma_{l}\left(x_{v}^{(l)},\psi_{l}\left(\left\\{m_{l}\left(x_{u}^{(l)},x_{v}^{(l)},w_{u,v}\right)\mid
u\in\mathcal{N}(v)\right\\}\right)\right),$

where $w_{u,v}$ represents the weight of the edge between nodes $u$ and $v$.
For instance, GCN (Kipf and Welling, 2016) computes the node feature update
as:

(2)
$x_{v}^{(l+1)}=\sum_{u\in\mathcal{N}(v)\cup\\{v\\}}\frac{1}{\sqrt{\hat{d}_{v}\hat{d}_{u}}}\Theta_{l}x_{u}^{(l)},$

where $\hat{d}_{v}$ denotes the normalized degree of node $v$, incorporating
the self-loop, and $\Theta_{l}$ is the layer-specific trainable parameter
matrix.

###  2.3. Heterophily Score

In this work, we address the challenge of class-imbalanced node classification
through the lens of heterophily. We propose the heterophily score as a pivotal
metric in our analysis, designed to quantify the diversity of connections
within the network. Specifically, it measures the degree to which nodes or
edges deviate from the principle of homophily – the tendency of similar nodes
to be connected. This metric is computed for each node, edge, and class within
the graph, facilitating a comprehensive understanding of the network’s
structure and its implications for node classification.

For nodes, we adopt the definition in (Pei et al., 2020) to define the
heterophily score of a node $v$ as:

(3)
$\beta_{v}=1-\frac{|\\{\boldsymbol{Y}(u)=\boldsymbol{Y}(v)\\}_{u\in\mathcal{N}(v)}|}{|\mathcal{N}(v)|},$

where $\mathcal{N}(v)$ is the set of one-hop neighbors of node $v$. This
equation calculates the proportion of a node’s neighbors that do not share its
label, thus quantifying the node’s heterophily.

To address the limitations inherent in training data, where labels may not
fully capture the diversity of connections, we also compute a heterophily
score for each edge. This score aids in refining our predictive models by
emphasizing the dynamics of relationships within the graph. The edge
heterophily score, based on the Manhattan distance between the embeddings of
two connected nodes $u$ and $v$, reflects the intuition that more similar
embeddings indicate lower heterophily. The formula is as follows:

(4) $h_{uv}=\frac{1}{D}\sum_{i=1}^{D}|z_{u}^{i}-z_{v}^{i}|,$

where $z_{u}$ and $z_{v}$ are the embeddings of nodes $u$ and $v$
respectively, and $D$ is the dimensionality of the embeddings.

Lastly, we calculate the class-level heterophily score as the average
heterophily score of all nodes belonging to a class $c$, offering a measure of
the class’s overall connectivity diversity:

(5) $h_{c}=\frac{1}{|C|}\sum_{v\in C}\beta_{v},$

where $C$ represents the set of nodes in class $c$, and $\beta_{v}$ is the
heterophily score of node $v$. Through this multi-faceted approach to
computing heterophily scores at different structural levels of the graph, we
gain a nuanced insight into how heterophily impacts imbalanced node
classification.

##  3\. Related Work

In this section, we review the prior work related to class-imbalanced node
classification, and heterophily in graphs.

###  3.1. Class-imbalanced Node Classification

Class imbalance is a common phenomenon in machine learning tasks such as image
classification (Peng et al., 2017) and fake account detection (He and Garcia,
2009). For class-imbalanced graphs, majority classes have more samples than
minority classes, leading to a bias towards the majority. Existing methods to
tackle class imbalance in graphs primarily involve generating new nodes and
edges (Shi et al., 2020; Qu et al., 2021; Zhou and Gong, 2023; Zhao et al.,
2021; Park et al., 2022; Li et al., 2023). Among these methods, DRGCN (Shi et
al., 2020) employs GANs for synthetic node generation. GraphSMOTE (Zhao et
al., 2021) and ImGAGN (Qu et al., 2021) generate nodes belonging to minority
classes to balance the classes. However, ImGAGN (Qu et al., 2021) focuses on
binary classification, making it less suitable for multi-class graphs.
GraphENS (Park et al., 2022) generates minority nodes by considering the
node’s neighborhood and employing saliency-based mixing. TAM (Song et al.,
2022) addresses class imbalance by introducing connectivity- and distribution-
aware margins to guide the model, emphasizing class-wise connectivity and the
distribution of neighbor labels. GraphSR (Zhou and Gong, 2023) augments
minority classes from unlabelled nodes of the graph automatically. GraphSHA
(Li et al., 2023) focuses on generating ’hard’ minority classes to enlarge the
margin between majority and minority classes. However, these methods do not
address the heterophily phenomenon in class-imbalanced graphs, where majority
classes disproportionately influence minority classes, further inducing bias
towards the majority.

###  3.2. Heterophily in Graphs

Although numerous GNNs have been proposed, most operate under the assumption
that nodes with similar features or those belonging to the same class are
connected to each other (Zheng et al., 2022). For instance, a paper is likely
to cite other papers from the same field (Sen et al., 2008). However, this
assumption does not hold for many real-world graphs. For instance, fraudulent
accounts may connect to numerous legitimate accounts in financial datasets.
Heterophily refers to the connection between two nodes with dissimilar
features or from different classes (Zheng et al., 2022). GNNs designed for
heterophilic graphs primarily fall into two categories: non-neighbor message
aggregation and GNN architecture refinement. MixHop (Abu-El-Haija et al.,
2019) considers two-hop neighbors instead of one-hop. H2GCN (Zhu et al., 2020)
theoretically demonstrates that two-hop neighbors contain more nodes from the
same class as the central node than one-hop neighbors do. In contrast, GNN
architecture refinement focuses on distinguishing similar neighbors from
dissimilar ones (Yan et al., 2022; Zhu et al., 2021). Inspired by these
methods, we propose adjusting the influence of minority nodes’ neighbors based
on the degree of heterophily between them and their one-hop neighbors in the
context of class-imbalanced node classification tasks.

##  4\. Proposed Method

In this section, we present a comprehensive description of our BuffGraph
model. The framework of BuffGraph is depicted in the Figure 2. First, we
insert buffer nodes into every edge in the graph. Then, we refine message
passing and optimize neighbor aggregation under this setup, all guided by edge
heterophily. And Algorithm 1 outlines the steps of BuffGraph’s implementation.
Additionally, we delve into both the complexity and theoretical analysis of
BuffGraph, thereby substantiating its effectiveness from a theoretical
standpoint.

Figure 2.  BuffGraph overview where $v_{1}$, $v_{2}$, $v_{4}$, $v_{5}$ are of
the major class and $v_{3}$, $v_{6}$ are of the minor class. The input graph
is shown in (a). Subsequently, we introduce a buffer node into every edge
within the graph, as depicted in (b). The feature of the buffer node is a
blend of the features from the two nodes connected by the edge, weighted by
$\alpha$ and $1-\alpha$ respectively. We zoom in $v_{4}$ to show the neighbor
aggregation of BuffGraph in (c). Each neighbor node passes message both across
the buffer node and directly to $v_{4}$ at the same time based on the edge’s
heterophily extent. The loss function is calculated when doing the neighbor
aggregation in BuffGraph shown in (d).

###  4.1. Buffer Node Generation

In response to the challenge posed by class imbalance in node classification
tasks, we propose a pioneering buffer node generation approach, inspired by
the mixup concept (Azabou et al., 2023). Buffer nodes introduce new nodes
along each edge, thereby extending the path messages traverse, which
effectively slows the message passing. This extension transforms direct one-
hop neighbors into two-hop neighbors, broadening the interaction range and
subtly modulating communication speed within the network.

A buffer node does not have a label but have a feature vector. Specifically,
the feature vector $\boldsymbol{X}_{\text{buf}}$ for a buffer node
$v_{\text{buf}}$ is generated by interpolating the features of the two
connected nodes: a source node $v_{\text{src}}$ and a target node
$v_{\text{tar}}$. The interpolation is governed by the following equation:

(6)
$\boldsymbol{X}_{\text{buf}}=\alpha\boldsymbol{X}_{\text{src}}+(1-\alpha)\boldsymbol{X}_{\text{tar}},\quad\alpha\in[0,1].$

Here, $\alpha$ serves as the mixup coefficient, influencing the degree to
which the features of the source and target nodes impact the buffer node’s
features. A lower value of $\alpha$ biases the feature vector
$\boldsymbol{X}_{\text{buf}}$ towards the target node $v_{\text{tar}}$ while a
higher value of $\alpha$ biases the feature vector
$\boldsymbol{X}_{\text{buf}}$ towards the source node $v_{\text{src}}$.

The integration of a buffer node into each edge is designed primarily to
modulate the message passing across edges, especially in contexts marked by
heterophily, rather than expanding the feature set. Consequently, the role of
$\alpha$ becomes secondary in this context, and we opt for a uniform value of
$\alpha=1/2$ for all edges to simplify the initial phase of our research and
ensure methodological consistency. To rigorously assess the impact of
$\alpha$, we undertake a series of experiments exploring variations of
$\alpha$, which are detailed in Section 5.7. And to validate the efficacy of
decelerating message passing speed through the insertion of buffer nodes, we
present a theoretical analysis in Section 4.4.

###  4.2. BuffGraph Framework

To address the challenges of message passing across heterophilic edges within
class-imbalanced graphs, we introduce the BuffGraph model. This model
incorporates a dynamic message passing mechanism that precisely modulates the
flow of information through each edge, optimizing the efficacy of buffer nodes
in managing heterophily. A detailed illustration of the BuffGraph framework
and its operational intricacies is provided in Figure 2.

Initially, we introduce an innovative approach to integrate buffer nodes into
every edge of the graph, a strategy that diverges from the rigid node
insertion method utilized in (Azabou et al., 2023) to address heterophily in
class-imbalanced graphs. Our method simultaneously employs both the original
edge, acting as a residual link, and the newly established links through
buffer node insertion. This dual-link utilization allows for dynamic
modulation of the message passing process. Following this, we pre-train a
conventional GCN model to derive a heterophily score for each edge. This score
then guides the allocation of information flow, enabling a differential
treatment of messages: they are passed directly via residual links or the
links generated by buffer nodes, with weights assigned based on the
heterophily score. For instance, as depicted in Figure 2, node $v_{4}$ shares
similarity with $v_{2}$ but differs from $v_{6}$. As a result, the message
from $v_{6}$ predominantly traverses via buffer node $v_{12}$, whereas the
message from $v_{2}$ has a lesser reliance on buffer node $v_{10}$. Two
special cases are: one where only residual links are used for direct message
passing, which is the vanilla GNN; another where only links generated by
buffer nodes are employed for indirect message passing. The GNN neighbor
aggregation mechanism we utilize is (Li et al., 2023):

(7)
$\boldsymbol{H}_{t}^{(l)}\leftarrow\boldsymbol{\operatorname{Transform}}\left(\underset{\forall
v_{s}\in\mathcal{N}_{t}}{\boldsymbol{\operatorname{Propagate}}}\left(\boldsymbol{H}_{s}^{(l-1)};\boldsymbol{H}_{t}^{(l-1)}\right)\right),$

where $\boldsymbol{H}_{t}^{(l)}$ represents node embedding of node $v_{t}$ in
the $l$-th layer.

Then, during the training phase, we leverage the message passing speed fine-
tuned in the pre-training stage to further train the model. Notably, we
reassess the heterophily score for each edge based on current model outputs
and adjust the message passing speed accordingly by taking into account both
heterophily loss and node classification loss every 50 epochs. The loss
function is:

(8)
$\boldsymbol{\mathcal{L}_{\text{total}}}=\boldsymbol{\mathcal{L}_{\text{pred}}}+\lambda\cdot\boldsymbol{\mathcal{L}_{\text{hetero}}}$

This adjustment is grounded in the understanding that edges linking nodes of
differing classes (indicative of high heterophily) should minimize direct
message passing in favor of routing messages through buffer nodes, and vice
versa. By judiciously modulating the information flow in this manner, we
enhances our model’s flexibility and effectiveness across various graph
structures and class imbalance situations. The detailed algorithm of our
comprehensive framework is outlined in Algorithm 1.

Algorithm 1 Buffer Node Synthesis and Adaptive Message Passing Algorithm

###  4.3. Complexity Analysis

Given $N$ as the total number of nodes and $E$ as the total number of edges
within the graph, the creation of buffer nodes correlates with the entirety of
the node and edge sets, leading to a computational complexity of $O(N+E)$.
This process efficiently reuses mixup coefficients from previous epochs, thus
avoiding additional computational demands. Pairing nodes for the mixup
procedure exhibits a complexity of $O(N^{2})$, given the potential for any
node to be paired with another. Generating augmented features for buffer nodes
requires $O(N\cdot d)$ time, with $d$ representing the dimensionality of the
node features. Additionally, forming augmented edges for the buffer nodes
incurs a time complexity of $O(E)$, engaging the whole graph’s edge set.
Hence, the total additional complexity introduced by our model is
$O(N^{2}+N\cdot d+E)$. As demonstrated by successful experiments on extensive
datasets such as Coauthor-Physics and WikiCS, BuffGraph can work well on the
large datasets.

###  4.4. Theoretical Analysis

In this section, we explore the BuffGraph model, with a special emphasis on
understanding how the integration of buffer nodes alters the graph’s structure
through changes in eigenvalues (Azabou et al., 2023). We examine the pivotal
role these modifications play in addressing the challenges associated with
heterophily.

Graph Laplacian and Eigenvalues in BuffGraph. For a graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ with nodes $\mathcal{V}$ and edges
$\mathcal{E}$, the graph Laplacian $\mathbf{L}$ is defined as
$\mathbf{L}=\mathbf{D}-\mathbf{A}$, where $\mathbf{A}$ is the adjacency matrix
and $\mathbf{D}$ is the degree matrix. The eigenvalues of $\mathbf{L}$,
represented by $\lambda_{i}$ for $i=1,\ldots,|\mathcal{V}|$, play a crucial
role in the graph’s diffusion processes. Specifically, a smaller eigenvalue
for a node suggests that it is more easily influenced by its neighbors’
diffusion patterns.

Impact of Buffer Nodes on Spectral Properties. Buffer nodes alter the
adjacency matrix to $\mathbf{A}^{\prime}$ and degree matrix to
$\mathbf{D}^{\prime}$. This results in a new graph Laplacian
$\mathbf{L}^{\prime}=\mathbf{D}^{\prime}-\mathbf{A}^{\prime}$. The eigenvalues
$\lambda^{\prime}_{i}$ of $\mathbf{L}^{\prime}$ now encapsulate the modified
spectral characteristics, affecting the graph’s information propagation
behavior. Then, the eigenvalue shift as follows:

(9) $\Delta\lambda_{i}=\lambda^{\prime}_{i}-\lambda_{i},$

where $\Delta\lambda_{i}$ quantifies the change in spectral properties
attributable to the addition of buffer nodes. With the increase of
eigenvalues, a minority node preserves more of its magnitude without being
affected by its majority neighbors (Keriven, 2022).

Modified Message Passing in BuffGraph. The incorporation of buffer nodes
necessitates a revision of the message passing mechanism, which in the
spectral domain, is reflected by:

(10)
$\mathbf{H}^{(l+1)}=\sigma\left(\mathbf{D}^{\prime-1/2}\mathbf{A}^{\prime}\mathbf{D}^{\prime-1/2}\mathbf{H}^{(l)}\mathbf{W}^{(l)}\right),$

where $\mathbf{H}^{(l)}$ denotes node embeddings at layer $l$, and
$\mathbf{W}^{(l)}$ is the weight matrix at layer $l$. This formula underscores
the nuanced adaptation of the BuffGraph model to heterophily by modulating the
eigenvalues through buffer nodes.

Conclusion. Buffer nodes adjust the eigenvalues $\lambda^{\prime}_{i}$ of the
original graph to facilitate a more balanced diffusion of information,
ensuring both minority and majority class features are adequately represented.

##  5\. Experiments

In this section, we conduct extensive experiments to evaluate the
effectiveness of BuffGraph for class-imbalanced node classification compared
with existing baselines. We would like to answer the following three research
questions:

Q1: How does BuffGraph’s performance in node classification on naturally
class-imbalanced graphs compare to that of existing baseline models?

Q2: How effectively does BuffGraph outperform other baseline models in node
classification across graphs with varying class-imbalance ratios?

Q3: Do all of BuffGraph’s components contribute to its performance?

Table 1. Statistics of datasets used in the paper.

Dataset | #Nodes | #Edges | #Features | #Classes | #Max / Min
---|---|---|---|---|---
Amazon-Photos | 7,650 | 119,081 | 745 | 8 | 5.86
Amazon-Computers | 13,752 | 245,861 | 767 | 10 | 17.72
Coauthor-CS | 18,333 | 163,778 | 6,805 | 15 | 35.05
Coauthor-Physics | 34,493 | 247,962 | 8,415 | 5 | 6.33
WikiCS | 11,701 | 216,123 | 300 | 10 | 9.08

Table 2. Random splitting experiment results of BuffGraph and other baselines
on five class-imbalanced node classification benchmark datasets. We report all
metrics with the standard deviation errors for five repetitions. The best
result is highlighted by bold text. The runner-up result is highlighted by the
underline.

| Dataset | Amazon-Photos | Amazon-Computers | Coauthor-CS | Coauthor-Physics | WikiCS
---|---|---|---|---|---|---
Random Splitting | Acc. | BAcc. | F1 | Acc. | BAcc. | F1 | Acc. | BAcc. | F1 | Acc. | BAcc. | F1 | Acc. | BAcc. | F1
Methods | Vanilla | 92.44$\pm$0.16 | 90.41$\pm$0.62 | 91.20$\pm$0.27 |  87.71$\pm$0.36 | 82.34$\pm$1.36 | 83.03$\pm$1.86 | 92.89$\pm$0.41 | 89.97$\pm$0.45 | 90.70$\pm$0.63 | 96.22$\pm$0.24 | 94.60$\pm$0.42 | 93.49$\pm$0.03 | 83.20$\pm$0.23 | 80.34$\pm$0.41 | 80.63$\pm$0.07
Reweight | 92.91$\pm$0.36 | 92.51$\pm$0.41 | 91.72$\pm$0.25 | 86.21$\pm$0.71 |  89.23$\pm$0.19 | 85.09$\pm$0.68 | 92.86$\pm$0.03 | 90.86$\pm$0.13 | 91.09$\pm$0.04 | 95.70$\pm$0.02 | 95.06$\pm$0.05 | 94.52$\pm$0.01 | 82.66$\pm$0.17 |  82.82$\pm$0.09 | 80.92$\pm$0.20
PC Softmax | 91.83$\pm$0.33 | 91.83$\pm$0.34 | 90.31$\pm$0.48 | 87.13$\pm$1.49 | 87.60$\pm$0.67 | 85.09$\pm$1.71 | 92.95$\pm$0.12 |  91.87$\pm$0.11 | 91.21$\pm$0.11 | 96.14$\pm$0.07 | 95.36$\pm$0.11 | 95.07$\pm$0.11 | 82.76$\pm$0.32 | 81.94$\pm$0.50 | 80.46$\pm$0.45
Balanced Softmax | 93.46$\pm$0.05 | 91.19$\pm$0.01 | 92.05$\pm$0.05 | 86.28$\pm$0.02 | 87.42$\pm$0.29 | 83.91$\pm$0.02 |  93.46$\pm$0.05 | 91.19$\pm$0.01 |  92.05$\pm$0.05 | 96.16$\pm$0.03 |  95.52$\pm$0.06 | 95.05$\pm$0.02 |  83.83$\pm$0.49 | 82.15$\pm$0.51 |  81.74$\pm$0.72
Cross Entropy | 93.40$\pm$0.20 | 92.13$\pm$0.21 | 92.30$\pm$0.23 | 86.99$\pm$0.22 | 82.26$\pm$0.75 | 84.21$\pm$0.50 | 93.05$\pm$0.14 | 90.85$\pm$0.37 | 91.49$\pm$0.32 |  96.50$\pm$0.14 | 95.30$\pm$0.13 |  95.25$\pm$0.18 | 83.15$\pm$0.23 | 82.63$\pm$0.74 | 81.57$\pm$0.30
GraphSmote | 89.72$\pm$0.45 | 90.69$\pm$0.57 | 88.90$\pm$0.48 | 85.36$\pm$0.72 | 84.79$\pm$1.22 | 85.22$\pm$0.98 | 87.44$\pm$0.24 | 85.08$\pm$0.63 | 84.26$\pm$0.52 | 95.09$\pm$0.53 | 93.01$\pm$0.66 | 93.42$\pm$0.76 | 82.94$\pm$0.70 | 80.42$\pm$1.14 | 80.65$\pm$0.75
GraphENS | 93.37$\pm$0.42 | 92.18$\pm$0.36 | 91.63$\pm$0.46 | 86.35$\pm$0.71 | 87.66$\pm$0.54 |  85.81$\pm$0.47 | 91.65$\pm$0.23 | 90.72$\pm$0.39 | 89.53$\pm$0.36 | 95.46$\pm$0.09 | 95.32$\pm$0.04 | 94.27$\pm$0.06 | 81.78$\pm$0.06 | 80.87$\pm$0.12 | 79.80$\pm$0.08
TAM | 90.13$\pm$0.33 | 90.98$\pm$0.36 | 89.15$\pm$0.49 | 85.46$\pm$0.11 | 88.51$\pm$0.67 | 84.52$\pm$0.26 | 92.41$\pm$0.04 | 90.84$\pm$0.01 | 91.35$\pm$0.02 | 95.35$\pm$0.19 | 95.04$\pm$0.08 | 94.04$\pm$0.20 | 80.73$\pm$0.34 | 79.02$\pm$0.21 | 79.02$\pm$0.16
GraphSHA |  93.63$\pm$0.23 |  92.61$\pm$0.66 |  92.60$\pm$0.38 | 82.98$\pm$0.17 | 77.73$\pm$1.90 | 79.10$\pm$2.22 | 92.68$\pm$0.59 | 91.00$\pm$0.37 | 90.94$\pm$0.51 | 96.27$\pm$0.14 | 95.51$\pm$0.17 | 95.05$\pm$0.11 | 81.83$\pm$1.22 | 80.76$\pm$0.54 | 78.95$\pm$1.53
BuffGraph |  93.90$\pm$0.13 |  93.10$\pm$0.09 |  93.20$\pm$0.27 |  90.22$\pm$0.48 |  91.85$\pm$0.34 |  89.30$\pm$0.69 |  94.90$\pm$0.28 |  93.88$\pm$0.39 |  93.70$\pm$0.41 |  96.78$\pm$0.07 |  96.02$\pm$0.16 |  95.79$\pm$0.07 |  84.47$\pm$0.22 |  83.62$\pm$0.15 |  82.10$\pm$0.12

Table 3. Imbalanced splitting experiment results of our model BuffGraph and
other baselines on five class-imbalanced node classification benchmark
datasets.

| Dataset | Amazon-Photos | Amazon-Computers | Coauthor-CS | Coauthor-Physics | WikiCS
---|---|---|---|---|---|---
$\rho$=10 | Acc. | BAcc. | F1 | Acc. | BAcc. | F1 | Acc. | BAcc. | F1 | Acc. | BAcc. | F1 | Acc. | BAcc. | F1
Methods | Vanilla | 92.20$\pm$0.54 | 89.60$\pm$0.05 | 90.41$\pm$0.14 | 83.40$\pm$0.29 | 69.71$\pm$0.28 | 70.79$\pm$0.43 | 92.54$\pm$0.55 | 89.86$\pm$0.68 | 90.53$\pm$0.63 | 95.65$\pm$0.04 | 93.76$\pm$0.12 | 94.19$\pm$0.17 | 81.30$\pm$1.00 | 75.16$\pm$1.53 | 77.42$\pm$1.55
Reweight | 92.65$\pm$0.36 | 92.34$\pm$0.17 | 90.79$\pm$0.36 | 86.46$\pm$0.20 | 89.26$\pm$0.08 | 85.33$\pm$0.14 | 93.23$\pm$0.12 | 91.74$\pm$0.07 | 91.86$\pm$0.03 | 96.35$\pm$0.04 | 95.12$\pm$0.20 | 95.16$\pm$0.09 | 81.16$\pm$0.13 | 81.48$\pm$0.28 | 79.54$\pm$0.34
PC Softmax | 84.51$\pm$0.86 | 88.69$\pm$1.27 | 84.01$\pm$2.57 | 70.48$\pm$1.09 | 84.92$\pm$1.21 | 70.50$\pm$0.46 | 92.78$\pm$0.02 | 93.16$\pm$0.06 | 91.23$\pm$0.14 | 95.18$\pm$0.09 |  95.47$\pm$0.08 | 93.87$\pm$0.13 | 76.01$\pm$2.24 | 80.30$\pm$1.42 | 73.85$\pm$2.13
Balanced Softmax | 92.81$\pm$0.20 |  93.33$\pm$0.04 | 91.44$\pm$0.19 |  87.55$\pm$0.24 |  89.31$\pm$0.16 |  86.95$\pm$0.02 | 93.99$\pm$0.01 |  93.24$\pm$0.03 | 92.35$\pm$0.02 |  96.46$\pm$0.05 |  95.46$\pm$0.03 |  95.32$\pm$0.04 | 82.14$\pm$0.04 |  82.45$\pm$0.21 |  80.10$\pm$0.08
Cross Entropy | 91.67$\pm$0.16 | 87.85$\pm$0.40 | 89.93$\pm$0.35 | 87.46$\pm$0.18 | 83.49$\pm$0.53 | 85.19$\pm$0.53 |  94.04$\pm$0.07 | 92.03$\pm$0.03 |  92.38$\pm$0.04 | 96.12$\pm$0.01 | 94.53$\pm$0.11 | 94.93$\pm$0.03 | 82.44$\pm$0.23 | 78.07$\pm$0.51 | 80.06$\pm$0.10
GraphSmote | 88.31$\pm$0.63 | 88.15$\pm$1.53 | 87.27$\pm$0.28 | 85.30$\pm$0.66 | 84.66$\pm$0.27 | 84.35$\pm$0.23 | 88.95$\pm$0.19 | 83.96$\pm$0.99 | 85.56$\pm$0.78 | 92.64$\pm$0.36 | 92.79$\pm$0.11 | 94.42$\pm$0.53 | 74.96$\pm$1.07 | 69.43$\pm$2.17 | 70.82$\pm$1.93
GraphENS | 92.55$\pm$0.07 | 91.66$\pm$0.37 | 91.07$\pm$0.02 | 85.50$\pm$0.58 | 89.21$\pm$0.14 | 85.05$\pm$0.69 | 92.12$\pm$0.03 | 90.49$\pm$0.01 | 89.21$\pm$0.16 | 95.35$\pm$0.19 | 95.04$\pm$0.08 | 94.04$\pm$0.20 | 80.73$\pm$0.30 | 79.94$\pm$0.27 | 77.83$\pm$0.45
TAM | 91.08$\pm$0.03 | 91.70$\pm$0.07 | 90.15$\pm$0.07 | 85.79$\pm$0.18 | 88.21$\pm$0.69 | 85.21$\pm$0.42 | 92.53$\pm$0.04 | 90.45$\pm$0.13 | 90.67$\pm$0.13 | 95.25$\pm$0.06 | 94.11$\pm$0.19 | 93.66$\pm$0.16 | 81.12$\pm$0.04 | 80.29$\pm$0.03 | 79.32$\pm$0.12
GraphSHA |  93.56$\pm$0.04 | 92.46$\pm$0.30 |  92.59$\pm$0.02 | 85.24$\pm$0.52 | 83.77$\pm$0.55 | 83.31$\pm$0.59 | 92.42$\pm$0.16 | 90.43$\pm$0.46 | 90.21$\pm$0.22 | 96.27$\pm$0.14 | 95.14$\pm$0.04 | 94.94$\pm$0.14 |  82.60$\pm$0.30 | 80.34$\pm$0.31 | 80.00$\pm$0.52
BuffGraph |  93.74$\pm$0.30 |  92.90$\pm$0.42 |  92.65$\pm$0.60 |  89.51$\pm$0.35 |  90.54$\pm$0.57 |  88.14$\pm$0.40 |  94.06$\pm$0.02 |  93.78$\pm$0.03 |  92.72$\pm$0.35 |  96.43$\pm$0.17 | 95.32$\pm$0.04 |  95.33$\pm$0.12 |  83.71$\pm$0.55 |  83.00$\pm$0.52 |  81.93$\pm$0.62

###  5.1. Experiments Setup

Environments. We conduct all experiments using PyTorch on an NVIDIA GeForce
RTX 3090 GPU. More details are in A.

Datasets. To comprehensively evaluate BuffGraph, we conduct experiments across
five naturally class-imbalanced datasets: Amazon-Photos, Amazon-Computers,
Coauthor-CS, Coauthor-Physics, and WikiCS. A statistical summary of these
datasets, including their key characteristics, is detailed in Table 1. The
Max/Min ratio in this summary represents the number of samples in the largest
majority class to that in the smallest minority class, offering insights into
the extent of imbalance within each dataset.

Baselines. In this study, we present our results using a GCN backbone and
compare them against a comprehensive set of baselines that encompass both loss
management strategies and class-imbalanced node classification approaches.
These include Reweight, PC SoftMax, Cross Entropy, and Balanced Softmax for
loss management, alongside GraphSMOTE, GraphENS, TAM, and GraphSHA for
tackling class imbalance. A detailed description of each baseline is provided
in the Appendix B.

Evaluation Metrics.  We evaluate model performance using Accuracy (Acc.),
Balanced Accuracy (BAcc.), and Macro F1 Score (F1). Balanced Accuracy is
defined as the average of accuracy of all classes (Li et al., 2023). Macro F1
is defined as the average of F1 scores of all classes. These metrics are
selected for their widespread acceptance in class-imbalanced node
classification task (Zhao et al., 2021; Park et al., 2022; Song et al., 2022;
Zhou and Gong, 2023).

###  5.2. Implementation Details

Random Splitting Experiment Settings. For the random splitting experiment, we
divide the datasets into training, validation, and testing sets with a 6:2:2
ratio. This random partitioning is carefully chosen to preserve the inherent
distributional characteristics of each dataset, thereby mitigating potential
biases. It ensures that our evaluations accurately reflect the true learning
capabilities of the models and not artifacts of the data distribution. We
standardize our models on the three hidden layers and explore hidden
dimensions of 64, 128, and 256. Among these, we select the dimension that
provides the best performance. For the learning rate, we explore the optimal
settings by evaluating the performance at values of 0.001, 0.005, and 0.01.
For the dropout rate, we explore the optimal settings for evaluating the
performance of 0.1, 0.2, 0.3, 0.4, 0.5. Based on these experiments, we have
chosen to set the hidden dimensions to 256, the dropout rate to 0.4, and the
learning rate to 0.01 to achieve the best performance. Regarding the training
duration, we configure the model to run for up to 2000 epochs, with an early
stopping parameter set at 500 epochs to ensure stability in the model’s
predictions during the training phase.

Imbalanced Experiment Settings. For the imbalanced experiment, we initially
perform a random split of the dataset into training, validation, and testing
sets following a 6:2:2 ratio. Subsequently, within the training set, we impose
an imbalance by downsampling the last half of the classes to achieve an
imbalance ratio of 10, meaning that the number of samples in these minority
classes is reduced to one-tenth of the most samples in the majority classes.
This two-step process, which adheres to the guidelines in (Park et al., 2022),
allows us to simulate a realistic imbalanced learning scenario and rigorously
assess model performance under the imbalanced condition.

Baseline Settings: In our experiments, we meticulously adhere to the
hyperparameter settings outlined in the papers for baseline models GraphSMOTE
(Zhao et al., 2021), GraphENS (Park et al., 2022), TAM (Song et al., 2022),
and GraphSHA (Li et al., 2023). This approach is critical to ensure the
reproducibility and comparability of our study. More details are in Appendix
B.

###  5.3. Experimental Results

Random Splitting Experiment Results. The results presented in Table 2
highlight BuffGraph’s outstanding performance against competing methods across
all metrics and datasets with a notable advantage in BAcc. For example,
BuffGraph exhibits a 2% increase in BAcc over the next best performing model
on Amazon-Computers and Coauthor-CS. This enhancement underscores BuffGraph’s
proficiency in accurately classifying minority classes. Additionally,
BuffGraph excels in overall accuracy, affirming its adeptness at boosting
performance uniformly across both majority and minority classes without
compromising the integrity of either.

The exceptional performance of BuffGraph can be attributed to its innovative
incorporation of buffer nodes, which strategically modulate the impact of
majority class nodes. This prevents the excessive influence of majority class
on minority class nodes. This approach ensures a more balanced information
dissemination within the graph, allowing minority class nodes to retain their
distinctive features during the learning process. In contrast, while some
baselines, such as Reweight, achieve impressive BAcc. on specific datasets,
their inability to maintain high overall accuracy suggests a disproportionate
focus on minority classes at the expense of majority class representation.
This imbalance highlights the challenges inherent in designing models that can
navigate the complex dynamics of class-imbalanced datasets without favoring
one class group over another. Therefore, BuffGraph represents a significant
step forward in achieving a balance between accurate minority class prediction
and overall classification performance.

Imbalanced Splitting Experiment Results. Different to the random splitting
setting in the above experiment, we specifically focused on cases where the
imbalance ratio between majority classes and minority classes equals 10 to
test BuffGraph’s performance against other baselines in more extreme class-
imbalanced graphs. From the result shown in Table 3, BuffGraph has superior
performance across most metrics and most datasets, particularly in terms of
F1. For example, BuffGraph achieves a 2% increase in F1 on Amazon-Computers
and WikiCS than runner-up results. These findings highlight BuffGraph’s
adeptness at sustaining elevated performance levels amidst substantial class
imbalances. Consequently, BuffGraph is affirmed as a robust model, adept not
just in randomly class-imbalanced graphs but also in those with significant
class imbalances as defined in our study.

Figure 3. Trend of BAcc. with the increase of imbalance ratio on Amazon-
Computers.

###  5.4. Imbalance Ratio Study

To further investigate BuffGraph’s effectiveness on class-imbalanced graphs,
we adjust the imbalance ratio to 15, 20, and 25 within the Amazon-Computers
dataset. Subsequently, we evaluate the BAcc. against competitive baselines,
including Balanced Softmax, GraphENS, TAM, GraphSHA, as depicted in Figure 3.
BuffGraph demonstrates stable performance across varying imbalance ratios,
significantly surpassing other baselines by at least a 3% margin in comparison
to the second-best results. This underscores BuffGraph’s robustness in
managing class imbalance across different levels of imbalance ratios for node
classification tasks in class-imbalanced graphs.

Figure 4. Scalability study on Coauthor-Physics.

###  5.5. Scalability Study

To evaluate the scalability of BuffGraph, we conduct a scalability study on
the biggest dataset: Coauthor-Physics. We sample four graphs of Coauthor-
Physics with the number of nodes: 5000, 10000, 15000, and 20000. Then, we run
BuffGraph on these graphs and report the training and test time of each epoch.
We report the result in the Figure 4. We can see from the Figure 4 that the
time of each epoch increases linearly with the sample of the graph’s node size
which shows that BuffGraph can scale to large graphs in the real-world
scenarios.

Figure 5. Ablation study on Amazon-Computers and WikiCS.

###  5.6. Ablation Study

To assess the efficacy of each element within our proposed BuffGraph model, we
conduct an ablation study on the Amazon-Computers and WikiCS datasets,
applying the GCN architecture and a random splitting setting, which is of the
same setting as the experiment in Table 2. This study deconstructs the
BuffGraph model by removing its key components once at a time to understand
their individual contributions. The variations considered in this analysis
include: (1) BuffGraph, representing the full BuffGraph model as the baseline
for comparison; (2) BuffGraph - Heterophily Loss (HL), examining the effect of
removing the heterophily loss component on overall performance; (3) BuffGraph
- Concrete Message Passing (CMP), assessing the role of concrete message
passing and its dependency on the buffer node path; and (4) BuffGraph - Update
Message Passing (UMP), investigating the implications of excluding the update
of message passing during the training based on total loss. This structured
approach allows for a nuanced understanding of how each component contributes
to the efficacy of the BuffGraph model.

The results shown in Figure 5 underscore the critical nature of the updating
message passing mechanism in training, as its removal (- UMP) precipitates the
most substantial decline in performance across most metrics on the both
datasets, especially of F1. In addition, the exclusion of other components
also notably diminishes all metrics across both datasets. This analysis
underscores the integral role each component plays within the BuffGraph model,
highlighting their collective importance in achieving optimal performance.

Figure 6. Parameter sensitivity analysis on Amazon-Computers and WikiCS.

###  5.7. Parameter Sensitivity Study

To assess the sensitivity of BuffGraph’s parameters, we focus on two critical
hyperparameters: $\alpha$, utilized in feature mixup, and $\lambda$, applied
in heterophily loss management. This investigation employs Amazon-Computers
and WikiCS. The outcomes are detailed in Figure 6. Notably, a $\alpha$ value
of 0.5 yields the most favorable results across both datasets. Regarding
$\lambda$, performance on Amazon-Computers remains relatively stable for
values up from 0.1 to 1, whereas on WikiCS, performance improves as $\lambda$
increases from 0.1 to 1. However, elevating $\lambda$ to 2 and 5 lead to a
marked decline in performance for both datasets. This parameter sensitivity
study highlights the nuanced impact of these parameters on model efficacy as
well as the wise choice of these parameters in our BuffGraph.

##  6\. Conclusion

In this study, we introduce BuffGraph, a groundbreaking model designed to
address the challenges of class imbalance in graph-structured data, with a
particular emphasis on heterophily. Leveraging a novel buffer node
interpolation technique and an adaptive message-passing mechanism, BuffGraph
significantly surpasses existing baselines in the realm of class-imbalanced
node classification. Our comprehensive experimental evaluation underscores
BuffGraph’s exceptional proficiency in accurately classifying minority classes
while preserving the integrity of majority class identification across both
naturally and artificially imbalanced graphs. This capability is vital for a
broad spectrum of practical applications. The insights gained from our study
not only affirm the practical utility of BuffGraph but also open new avenues
for further research into the complex dynamics of heterophily in class-
imbalanced graph analysis.

## References

  * (1)
  * Abu-El-Haija et al. (2019) Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. 2019.  Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In _international conference on machine learning_. PMLR, 21–29.
  * Azabou et al. (2023) Mehdi Azabou, Venkataramana Ganesh, Shantanu Thakoor, Chi-Heng Lin, Lakshmi Sathidevi, Ran Liu, Michal Valko, Petar Veličković, and Eva L Dyer. 2023.  Half-Hop: A graph upsampling approach for slowing down message passing. In _International Conference on Machine Learning_. PMLR, 1341–1360.
  * Bhadra et al. (2023) Jayati Bhadra, Amandeep Singh Khanna, and Alexei Beuno. 2023.  A Graph Neural Network Approach for Identification of Influencers and Micro-Influencers in a Social Network:* Classifying influencers from non-influencers using GNN and GCN. In _2023 International Conference on Advances in Electronics, Communication, Computing and Intelligent Information Systems (ICAECIS)_. IEEE, 66–71.
  * Cai et al. (2018) Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. 2018.  A comprehensive survey of graph embedding: Problems, techniques, and applications.  _IEEE transactions on knowledge and data engineering_ 30, 9 (2018), 1616–1637.
  * Cao et al. (2016) Shaosheng Cao, Wei Lu, and Qiongkai Xu. 2016.  Deep neural networks for learning graph representations. In _Proceedings of the AAAI conference on artificial intelligence_ , Vol. 30.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ 30 (2017).
  * He and Garcia (2009) Haibo He and Edwardo A Garcia. 2009.  Learning from imbalanced data.  _IEEE Transactions on knowledge and data engineering_ 21, 9 (2009), 1263–1284.
  * Hong et al. (2021) Youngkyu Hong, Seungju Han, Kwanghee Choi, Seokjun Seo, Beomsu Kim, and Buru Chang. 2021.  Disentangling label distribution for long-tailed visual recognition. In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_. 6626–6636.
  * Keriven (2022) Nicolas Keriven. 2022.  Not too little, not too much: a theoretical analysis of graph (over) smoothing.  _Advances in Neural Information Processing Systems_ 35 (2022), 2268–2281.
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling. 2016.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ (2016).
  * Li et al. (2023) Wen-Zhi Li, Chang-Dong Wang, Hui Xiong, and Jian-Huang Lai. 2023.  GraphSHA: Synthesizing Harder Samples for Class-Imbalanced Node Classification.  _arXiv preprint arXiv:2306.09612_ (2023).
  * Lin et al. (2022) Dan Lin, Jiajing Wu, Qi Xuan, and K Tse Chi. 2022.  Ethereum transaction tracking: Inferring evolution of transaction networks via link prediction.  _Physica A: Statistical Mechanics and its Applications_ 600 (2022), 127504.
  * Mernyei and Cangea (2020) Péter Mernyei and Cătălina Cangea. 2020.  Wiki-cs: A wikipedia-based benchmark for graph neural networks.  _arXiv preprint arXiv:2007.02901_ (2020).
  * Park et al. (2022) Joonhyung Park, Jaeyun Song, and Eunho Yang. 2022.  Graphens: Neighbor-aware ego network synthesis for class-imbalanced node classification. In _The Tenth International Conference on Learning Representations, ICLR 2022_. International Conference on Learning Representations (ICLR).
  * Pei et al. (2020) Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. 2020.  Geom-gcn: Geometric graph convolutional networks.  _arXiv preprint arXiv:2002.05287_ (2020).
  * Peng et al. (2017) Yuxin Peng, Xiangteng He, and Junjie Zhao. 2017.  Object-part attention model for fine-grained image classification.  _IEEE Transactions on Image Processing_ 27, 3 (2017), 1487–1500.
  * Qu et al. (2021) Liang Qu, Huaisheng Zhu, Ruiqi Zheng, Yuhui Shi, and Hongzhi Yin. 2021.  Imgagn: Imbalanced network embedding via generative adversarial graph networks. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_. 1390–1398.
  * Ren et al. (2020) Jiawei Ren, Cunjun Yu, Xiao Ma, Haiyu Zhao, Shuai Yi, et al. 2020\.  Balanced meta-softmax for long-tailed visual recognition.  _Advances in neural information processing systems_ 33 (2020), 4175–4186.
  * Sen et al. (2008) Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008.  Collective classification in network data.  _AI magazine_ 29, 3 (2008), 93–93.
  * Shamsi et al. (2022) Kiarash Shamsi, Friedhelm Victor, Murat Kantarcioglu, Yulia Gel, and Cuneyt G Akcora. 2022.  Chartalist: Labeled Graph Datasets for UTXO and Account-based Blockchains.  _Advances in Neural Information Processing Systems_ 35 (2022), 34926–34939.
  * Shchur et al. (2018) Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. 2018.  Pitfalls of graph neural network evaluation.  _arXiv preprint arXiv:1811.05868_ (2018).
  * Shi et al. (2020) Min Shi, Yufei Tang, Xingquan Zhu, David Wilson, and Jianxun Liu. 2020.  Multi-class imbalanced graph convolutional network learning. In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20)_.
  * Song et al. (2022) Jaeyun Song, Joonhyung Park, and Eunho Yang. 2022.  TAM: topology-aware margin loss for class-imbalanced node classification. In _International Conference on Machine Learning_. PMLR, 20369–20383.
  * Veličković et al. (2017) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ (2017).
  * Wang et al. (2023) Qian Wang, Zhen Zhang, Zemin Liu, Shengliang Lu, Bingqiao Luo, and Bingsheng He. 2023.  ETGraph: A Pioneering Dataset Bridging Ethereum and Twitter.  _arXiv preprint arXiv:2310.01015_ (2023).
  * Yan et al. (2022) Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. 2022.  Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In _2022 IEEE International Conference on Data Mining (ICDM)_. IEEE, 1287–1292.
  * Zhao et al. (2021) Tianxiang Zhao, Xiang Zhang, and Suhang Wang. 2021.  Graphsmote: Imbalanced node classification on graphs with graph neural networks. In _Proceedings of the 14th ACM international conference on web search and data mining_. 833–841.
  * Zheng et al. (2022) Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. 2022.  Graph neural networks for graphs with heterophily: A survey.  _arXiv preprint arXiv:2202.07082_ (2022).
  * Zhou and Gong (2023) Mengting Zhou and Zhiguo Gong. 2023.  GraphSR: A Data Augmentation Algorithm for Imbalanced Node Classification.  _arXiv preprint arXiv:2302.12814_ (2023).
  * Zhu et al. (2021) Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. 2021.  Graph neural networks with heterophily. In _Proceedings of the AAAI conference on artificial intelligence_ , Vol. 35. 11168–11176.
  * Zhu et al. (2020) Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. 2020.  Beyond homophily in graph neural networks: Current limitations and effective designs.  _Advances in neural information processing systems_ 33 (2020), 7793–7804.

## APPENDIX

##  Appendix A EXPERIMENTAL ENVIRONMENTS

All models in our experiments were implemented using Pytorch 2.0.0 in Python
3.9.16, and run on a robust Linux workstation. This system is equipped with
two Intel(R) Xeon(R) Gold 6226R CPUs, each operating at a base frequency of
2.90 GHz and a max turbo frequency of 3.90 GHz. With 16 cores each, capable of
supporting 32 threads, these CPUs offer a total of 64 logical CPUs for
efficient multitasking and parallel computing. The workstation is further
complemented by a potent GPU setup, comprising eight NVIDIA GeForce RTX 3090
GPUs, each providing 24.576 GB of memory. The operation of these GPUs is
managed by the NVIDIA-SMI 525.60.13 driver and CUDA 12.0, ensuring optimal
computational performance for our tasks.

##  Appendix B DETAILED EXPERIMENT SETTINGS

For the class-imbalanced node classification experiments, we selected a
diverse set of competitive baselines, categorized into loss management
strategies and specific approaches to addressing class imbalance in node
classification:

Loss Management Strategies:

  * •

Reweight: Modifies class weights inversely proportional to their frequency in
the dataset, aiming to mitigate class imbalance.

  * •

PC SoftMax (Hong et al., 2021): Enhances model probability calibration for
multi-class scenarios, improving minority class predictions.

  * •

Cross Entropy: Employed as the primary loss function, it quantifies the
difference between the predicted probabilities and the actual distribution.

  * •

Balanced Softmax (Ren et al., 2020): Adjusts softmax regression to lower the
generalization error, particularly effective in multi-class imbalance.

Class-Imbalanced Node Classification Approaches:

  * •

GraphSMOTE (Zhao et al., 2021): Generates synthetic instances for minority
classes, directly addressing the imbalance issue.

  * •

GraphENS (Park et al., 2022): Employs ensemble techniques to augment minority
class representation through synthetic instance generation.

  * •

TAM (Song et al., 2022): Introduces a tailored margin that considers
connectivity and distribution, enhancing minority class classification.

  * •

GraphSHA (Li et al., 2023): Focuses on creating challenging minority samples
to improve classification margins between classes.

We employ the same GCN backbone (Kipf and Welling, 2016), for all class-
imbalanced node classification baselines. Typically, the selection of the
number of hidden layers is confined to the set {2, 3}, and the dimensions of
these layers are chosen from {64, 128, 256}. We report the best prediction
results obtained from all configurations.

For GraphSmote, we opt for the GraphSmoteO variant, which is tailored to
predict discrete values without necessitating pretraining, showcasing superior
performance among its various versions (Zhao et al., 2021).

In the implementation of GraphENS, we adhere to the configurations suggested
in the original codebase, setting the feature masking rate $k$ to 0.01 and the
temperature $\tau$ to 1 (Park et al., 2022).

For TAM, we select the GraphENS-based iteration, which is identified as the
most performant according to the findings reported in the corresponding paper.
The default settings from the released code are utilized, with the
coefficients for ACM $\alpha$, ADM $\beta$, and classwise temperature $\phi$
set to 2.5, 0.5, and 1.2, respectively (Song et al., 2022).

Specifically for GraphSHA, we follow the parameter configurations detailed in
the original study, employing the PPR version with a setting of $\alpha=0.05$
and $K=128$ (Li et al., 2023).