# Topology-Imbalance Learning
for Semi-Supervised Node Classification

Deli Chen1,2, Yankai Lin1, Guangxiang Zhao2, Xuancheng Ren2,
Peng Li1, Jie Zhou1, Xu Sun2
1Pattern Recognition Center, WeChat AI, Tencent Inc., China
2MOE Key Lab of Computational Linguistics, School of EECS, Peking University
{delichen, yankailin<EMAIL_ADDRESS>
<EMAIL_ADDRESS>

###### Abstract

The class imbalance problem, as an important issue in learning node
representations, has drawn increasing attention from the community. Although
the imbalance considered by existing studies roots from the unequal quantity
of labeled examples in different classes (quantity imbalance), we argue that
graph data expose a unique source of imbalance from the asymmetric topological
properties of the labeled nodes, i.e., labeled nodes are not equal in terms of
their structural role in the graph (topology imbalance). In this work, we
first probe the previously unknown topology-imbalance issue, including its
characteristics, causes, and threats to semi-supervised node classification
learning. We then provide a unified view to jointly analyzing the quantity-
and topology- imbalance issues by considering the node influence shift
phenomenon with the Label Propagation algorithm. In light of our analysis, we
devise an influence conflict detection–based metric Totoro to measure the
degree of graph topology imbalance and propose a model-agnostic method ReNode
to address the topology-imbalance issue by re-weighting the influence of
labeled nodes adaptively based on their relative positions to class
boundaries. Systematic experiments demonstrate the effectiveness and
generalizability of our method in relieving topology-imbalance issue and
promoting semi-supervised node classification. The further analysis unveils
varied sensitivity of different graph neural networks (GNNs) to topology
imbalance, which may serve as a new perspective in evaluating GNN
architectures.111The code is available at
https://github.com/victorchen96/ReNode.

##  1 Introduction

Graph is a widely-used data structure [61], where the nodes are connected to
each other through natural or handcrafted edges. Similar to other data
structures, the representation learning for node classification faces the
challenge of quantity-imbalance issue, where the labeling size varies among
classes and the decision boundaries of trained classifiers are mainly decided
by the majority classes [55]. There have been a series of studies [44, 14, 58]
handling the Quantity-Imbalance Node Representation Learning (short as QINL).
However, different with other data structures, graph-structured data suffers
from another aspect of the imbalance problem: the imbalance caused by the
asymmetric and uneven topology of labeled nodes, where the decision boundaries
are driven by the labeled nodes close to the topological class boundaries
(left of Figure 1) thus interfering with the model learning.

Present Work. For the first time, we recognize the Topology-Imbalance Node
Representation Learning (short as TINL) as a graph-specific imbalance learning
topic, which mainly focus on the decision boundaries shift phenomena driven by
the topology imbalance in graph and is an essential component for node
imbalance learning. Comparing with the well-explored QINL that studies the
imbalance caused by the numbers of labeled nodes, TINL explores the imbalance
caused by the positions of labeled nodes and owns the following
characteristics:

  * •

Ubiquity: Due to the complex connections of the graph nodes, the topology
structure of nodes in different categories is naturally asymmetric, which
makes TINL an essential characteristic in node representation learning. Hence,
it is difficult to construct a completely symmetric labeling set even with an
abundant annotation budget.

  * •

Perniciousness: The influence from labeled nodes decays with the topology
distance [3]. The asymmetric topology of labeled nodes in different classes
and the uneven distribution of labeled nodes in the same class will cause the
influence conflict and influence insufficient problems (left of Figure 1)
respectively, resulting in a shift of decision boundaries.

  * •

Orthogonality: Quantity-imbalance studies [58, 9, 5] usually treat the labeled
nodes of the same class as a whole and devise solutions based on the total
numbers of each class, while TINL explores the influence of the unique
position of each labeled node on decision boundaries. Thus, TINL is
independent of QINL in terms of the object of study.

Figure 1: Schematic diagram of the topology-imbalance issue in node
representation learning. The color and the hue denote the type and the
intensity of each node’s received influence from the labeled nodes,
respectively. The left shows that nodes close to the boundary have the risk of
information conflict and nodes far away from labeled nodes have the risk of
information insufficient. The right shows that our method can decrease the
training weights of labeled nodes (R1) close to the class boundary and
increase the weights of labeled nodes (B and R2) close to the class centers,
thus relieving the topology-imbalance issue.

Exploring TINL is of great importance for node representation learning due to
its ubiquity and perniciousness. However, the methods [20, 28] for quantity
imbalance can be hardly applied to TINL because of the orthogonality. To
remedy the topology-imbalance issue, thus promoting the node classification,
we propose a model-agnostic training framework ReNode to re-weight the labeled
nodes according to their positions. We devise the conflict detection-based
Topology Relative Location (Totoro) metric to leverage the interaction among
labeled nodes across the whole graph to locate their structural positions.
Based on the Totoro metric, we further increase the training weights of nodes
with small conflict that are highly likely to be close to topological class
centers to make them play a more pivotal role during training, and vice versa
(right of Figure 1). Empirical results of various imbalance scenarios (TINL,
QINL, large-scale graph) and multiple graph neural networks (GNNs) demonstrate
the effectiveness and generalizability of our method. Besides, we provide the
sensitivity to topology imbalance as a new evaluation perspective for
different GNN architectures.

##  2 Topology-Imbalance Node Representation Learning

###  2.1 Notations and Preliminary

In this work, we follow the well-established semi-supervised node
classification setting [56, 23] to conduct analyses and experiments. Given an
undirected and unweighted graph
$\mathcal{G}=(\bm{\mathcal{V}},\bm{\mathcal{E}},\bm{\mathcal{L}})$, where
$\bm{\mathcal{V}}$ is the node set represented by the feature matrix
$\bm{X}\in\mathbb{R}^{n*d}$ ($n=|\bm{\mathcal{V}}|$ is the node size and $d$
is the node embedding dimension), $\bm{\mathcal{E}}$ is the edge set which is
represented by an adjacency matrix $\bm{A}\in\mathbb{R}^{n*n}$,
$\bm{\mathcal{L}}\subset\bm{\mathcal{V}}$ is the labeled node set and usually
we have $|\bm{\mathcal{L}}|\ll|\bm{\mathcal{V}}|$, the node classification
task is to train a classifier $\mathcal{F}$ (usually a GNN) to predict the
class label $\mathbf{y}$ for the unlabeled node set
$\bm{\mathcal{U}}=\bm{\mathcal{V}}-\bm{\mathcal{L}}$. The training sets for
different classes are represented by
$(\bm{\mathcal{C}}_{1},\bm{\mathcal{C}}_{2},\cdots,\bm{\mathcal{C}}_{k})$ and
$k$ is the number of classes. The labeling ratio
$\delta=\bm{\mathcal{L}}/\bm{\mathcal{V}}$ is the proportion of labeled nodes
in all nodes. In this work, we focus on TINL in homogeneously-connected graphs
and hope to inspire future studies on the critical topology-imbalance issue.

(a) Predictions of GCN and LP

(b) Uniform Sampling

(c) Quantity-balanced Sampling

Figure 2: Node influence and boundary shift caused by quantity- and topology-
imbalance. (a): The prediction results of GCN and LP are highly consistent
(t-SNE [48] visualization of the CORA dataset). (b): The node influence
boundary (the yellow dotted line) is shifted towards the small class from the
true class boundary (the black dotted line) under the quantity- and topology-
imbalance scene. (c): The node influence boundary is shifted towards the large
class under the quantity-balanced, topology-imbalanced scene. We regard the
large class as positive class to indicate the results.

###  2.2 Understanding Topology Imbalance via Label Propagation

From Figure 1, we can intuitively perceive the imbalance brought by the
positions of labeled nodes; in this part, we further explore the nature of
topology imbalance with the well-known Label Propagation [60] algorithm (short
as LP) and provide a uniform analysis framework for the comprehensive node
imbalance issue. In LP, labels are propagated from the labeled nodes and
aggregated along edges, which can also be viewed as a random walk process from
labeled nodes. The convergence result $\bm{Y}$ after repeated propagation is
regarded as the nodes soft-labels:

$\bm{Y}=\alpha(\bm{I}-(1-\alpha)\bm{A}^{\prime})^{-1}\bm{Y}^{0},$ (1)

where $\bm{I}$ is the identity matrix, $\alpha\in(0,1]$ is the random walk
restart probability,
$\bm{A}^{\prime}=\bm{D}^{-\frac{1}{2}}\bm{A}\bm{D}^{-\frac{1}{2}}$ is the
adjacency matrix normalized by the diagonal degree matrix $\bm{D}$,
$\bm{Y}^{0}$ is the initial label distribution where labeled nodes are
represented by the one-hot vectors. The prediction label for the $i$-th node
is $\bm{q}_{i}=\arg\max_{j}\bm{Y}_{ij}$. LP is a simple yet successful model
[46] and can be unified with GNN models owning the message-passing mechanism
[50]. From Figure 2(a), we can empirically find that there is a significant
correlation between the results of LP and GCN (T/F indicates prediction is
True/False).

The LP prediction $\bm{q}$ can be viewed as the distribution of the (labeled)
node influence [50] (i.e. each node is mostly influenced by which class’s
information); hence the boundaries of the node influence can act as an
effective reflection for the GNN model decision boundaries considering the
high consistency between LP and GNN. Moreover, node influence offers a unified
view of TINL and QINL: ideally, the node influence boundaries should be
consistent with the true class boundaries, but both the labeled nodes’ numbers
(QINL) and positions (TINL) can cause a shift of the node influence boundaries
from the true one, resulting in deviation of the model decision boundaries.

Node imbalance issue is composed of topology- and quantity-imbalance. Figure 2
illustrates two examples of node influence boundary shift. In Figure 2(b),
when the uniform selection is adopted to generate training set, both the
quantity and the topology are imbalanced for model training; then the large
class with more total nodes (denotes by blue color) will own stronger
influence than the small class with fewer total nodes (denotes by red color)
due to the quantity advantage and the node influence boundary is shifted
towards the small class. In Figure 2(c), when the quantity-balanced strategy
is adopted for sampling training nodes, it will be easier for the small class
to has more labeled nodes close to the class boundary and the boundary of the
node influence is shifted into the large class. We can find that even when the
training set is quantity-balanced, the topology-imbalance issue still exists
and hinders the node classification learning. Hence, we can conclude that node
imbalance learning is caused by the joint effect of TINL and QINL. Separately
considering TINL or QINL will lead to a one-sided solution to node imbalance
learning.

Figure 3: Effectiveness of Totoro at (a) Node Level: labeled nodes (t-SNE
visualization of the CORA dataset) with less influence conflict (lighter
color) are farther-away from class boundaries than those with high conflict
(darker color), and (b) Dataset Level: There is a significant negative
correlation between the GNN (GCN) performance and overall conflict of the
training set (the Pearson correlation coefficient is $-0.618$ over 50 randomly
selected training sets with the $p$ value smaller than 0.01).

###  2.3 Measuring Topology Imbalance by Influence Conflict

Although we have realized that the imbalance of node topology interferes with
model learning, how to measure the labeled node’s relative topological
position to its class (being far away from or close to the class center)
remains the key challenge in handling the topology-imbalance issue due to the
complex graph connections and the unknown class labels for most nodes in the
graph. As the nodes are homogeneously connected when constructing the graph,
even nodes close to the class boundaries own similar characteristics to their
neighbors. Thus it is unreliable to leverage the difference between the
characteristics of one labeled node and its surrounding subgraphs to locate
its topological position. Instead, we propose to utilize the node topology
information by considering the node influence conflict across the whole graph
and devise the Conflict Detection-based Topology Relative Location metric
(Totoro).

Similar to Eq (1), we calculate the Personalized PageRank [34] matrix $\bm{P}$
to measure node influence distribution from each labeled node:

$\bm{P}=\alpha(\bm{I}-(1-\alpha)\bm{A^{\prime}})^{-1}.$ (2)

Node influence conflict denotes topological position. According to related
studies [50, 24, 2], $\bm{P}$ can be viewed as the distribution of influence
exerted outward from each node. We assume that if a labeled node
$v\in\bm{\mathcal{V}}$ encounters strong heterogeneous influence from the
other classes’ labeled nodes in the subgraph around node $v$ where node $v$
itself owns great influence, we have the conclusion that node $v$ meets large
influence conflict in message passing and it is close to topological class
boundaries, and vice versa. Based on this hypothesis, we take the expectation
of the influence conflict between the node $v$ and the labeled nodes from
other classes when node $v$ randomly walks across the entire graph as a
measurement of how topologically close node $v$ is to the center of the class
it belongs to. The Totoro value of node $v$ is computed as:

$\displaystyle\bm{T}_{v}$
$\displaystyle=\mathbb{E}_{x\sim\bm{P}_{v,:}}[\sum_{j\in[1,k],j\neq\bm{y}_{v}}\frac{1}{|\bm{\mathcal{C}}_{j}|}\sum_{i\in\bm{\mathcal{C}}_{j}}\bm{P}_{i,x}],$
(3)

where $\bm{y}_{v}$ is the ground-truth label of node $v$, $\bm{P}_{v}$
indicates the personalized PageRank probability vector for the node $v$. A
larger Totoro value $\bm{T}_{v}$ indicates that node $v$ is topologically
closer to class boundaries, and vice versa. The normalization item
$\nicefrac{{1}}{{|\bm{\mathcal{C}}_{j}|}}$ is added to make the influence from
the different classes comparable when computing conflict.

We visualize the node labels and the Totoro values (scaled to $[0,1]$) of
labeled nodes in Figure 3(a). We can find that the labeled nodes with smaller
Totoro values are farther away from the class boundaries, demonstrating the
effectiveness of Totoro in locating the positions of labeled nodes. Besides,
we sum the conflict of all the labeled nodes
$\sum_{b\in\bm{\mathcal{L}}}\bm{T}_{v}$ to measure the overall conflict of the
dataset, which can be viewed as the metric for the overall topology imbalance
given the graph $\bm{\mathcal{G}}$ and the training set $\bm{\mathcal{L}}$.
Figure 3(b) shows that there is a significant negative correlation between the
overall conflict and the model performance, which further demonstrates the
effectiveness of Totoro in measuring the intensity of topology imbalance at
the dataset level.

###  2.4 Alleviate Topology Imbalance by Instance-wise Node Re-weighting

In this section, we introduce ReNode, a model-agnostic training weight
schedule mechanism to address TINL for general GNN encoder in a plug-and-play
manner. Inspired by the analysis in Section 2.2, the ReNode method is devised
to promote the training weights of the labeled nodes that are close to the
topological class centers, so as to make these nodes play a more active role
in model learning, and vice versa. Specifically, we devise a cosine annealing
mechanise 222We also try other schedules and the cosine method works best.
More details can be found in Appendix B. for the training node weights based
on their Totoro values:

$\displaystyle\bm{w}_{v}=w_{\text{min}}+\frac{1}{2}(w_{\text{max}}-w_{\text{min}})(1+\mathrm{cos}(\frac{\mathrm{Rank}(\bm{T}_{v})}{|\bm{\mathcal{L}}|}\pi)),\quad
v\in\bm{\mathcal{L}}$ (4)

where $\bm{w}_{v}$ is the modified training weight for the labeled node $v$,
$w_{\text{min}},w_{\text{max}}$ are the hyper-parameters indicating the lower
bound and upper bound of the weight correction factor,
${\mathrm{Rank}}(\bm{T}_{v})$ is the ranking order of $\bm{T}_{v}$ from the
smallest to the largest. The training loss $L_{T}$ for the quantity-balanced,
topology-imbalanced node classification task is computed by the following
equations:

$L_{T}=-\frac{1}{|\bm{\mathcal{L}}|}\sum_{v\in\bm{\mathcal{L}}}\bm{w}_{v}\sum_{c=1}^{k}\bm{y}^{\ast
c}_{v}\,\log\,\,{\bm{g}}^{c}_{v},\quad\bm{g}=\mathrm{softmax}(\mathcal{F}(\bm{X},\bm{A},\bm{\theta})),$
(5)

where $\mathcal{F}$ denotes any GNN encoder, $\bm{\theta}$ is the parameter of
$\mathcal{F}$, $\bm{g}_{i}$ is the GNN output for node $i$,
$\bm{y}^{\ast}_{i}$ is the gold label for node $i$ in one-hot embedding. By
encouraging the positive effects of the labeled nodes near the class
topological centers, and reducing the negative effects of those near the
topological class boundaries, our ReNode method is expected to minimize the
deviation between the node influence boundaries and the true class boundaries,
so as to correct the class imbalance caused by the positions of labeled nodes.

#### ReNode to Jointly Handle TINL and QINL

In this part, we introduce the application of the ReNode method in a more
general graph imbalance scenario where both the topology- and quantity-
imbalance issues exist. As analyzed in previous sections, the TINL and QINL
are orthogonal problems. Therefore, we propose that our ReNode method based on
(labeled) node topology can be seamlessly combined with the existing methods
designed for the quantity-imbalance learning. Without loss of generality, we
present how our ReNode method can be combined with the vanilla class
frequency-based re-weight method [20]. The training loss $L_{Q}$ for the
quantity-imbalanced, topology-imbalanced node classification task is
formalized in the following equation:

$\displaystyle L_{Q}$
$\displaystyle=-\frac{1}{|\bm{\mathcal{L}}|}\sum_{v\in\bm{\mathcal{L}}}\bm{w}_{v}\frac{\bar{|\bm{\mathcal{C}}|}}{|\bm{\mathcal{C}}_{j}|}\sum_{c=1}^{k}\bm{y}^{\ast
c}_{v}\,\log\,\,{\bm{g}}^{c}_{v},$ (6)

where $\bar{|\bm{\mathcal{C}}|}$ is the average number of the class training
sizes. With this method, the final weight of the labeled node is affected by
two perspectives: training examples of the minority classes will have higher
weights than that of the majority classes; training examples close to the
topological class centers will have higher weights than those are close to the
topological class boundaries.

#### ReNode for Large-scale Graph

There are mainly two challenges when applying ReNode to large-scale graphs:
(1) how to calculate the PageRank matrix, and (2) how to train the GNN model
in an inductive setting [16]. In this work, we follow the PPRGo method [2] to
implement our method on the large-scale graph, which can decouple the feature
learning process from the information transmission process to resolve the
dependence on the global graph topology structure and can be carried out much
efficiently. Following PPRGo, the Personalized PageRank matrix $\hat{\bm{P}}$
and the corresponding training ReNode factor $\hat{\bm{w}}$ are generated by
the estimation method from Andersen et al. [1] and then $\hat{\bm{P}}$ is
directly employed as the aggregation weights from all the other nodes
regardless of their topology distance from the current node:

$\displaystyle\bm{g}^{\prime}$
$\displaystyle=\mathrm{softmax}(\hat{\bm{P}}\mathcal{F}^{\prime}(\bm{X},\theta^{\prime})),$
(7)

where $\mathcal{F}^{\prime}$ can be a linear layer or a multi-layer perceptron
with parameter $\theta^{\prime}$. The final training loss for large-scale
graph $L_{L}$ follows Eq (5) and (6), and replaces ${\bm{w}}$ and ${\bm{g}}$
with $\hat{\bm{w}}$ and ${\bm{g}^{\prime}}$.

Table 1: ReNode (short as RN) for the pure topology-imbalance issue. We report
Weighted-F1 (W-F, %), Macro-F1 (M-F, %) and the corresponding standard
deviation for each group of experiments. $*$ and $**$ represent the result is
significant in student t-test with $p<0.05$ and $p<0.01$, respectively.

Model | Training | CORA | CiteSeer | PubMed | Photo | Computers
---|---|---|---|---|---|---
W-F | M-F | W-F | M-F | W-F | M-F | W-F | M-F | W-F | M-F
GCN | w/o RN | 79.1$\pm$1.1 | 77.8$\pm$1.5 | 66.2$\pm$1.0 | 62.0$\pm$1.3 | 74.6$\pm$2.1 | 74.7$\pm$1.9 | 86.8$\pm$2.0 | 84.7$\pm$1.7 | 74.2$\pm$2.6 | 73.6$\pm$2.9
w/ RN |  79.8∗∗$\pm$0.9 |  78.6∗∗$\pm$1.2 |  66.9∗$\pm$1.1 |  62.8∗$\pm$1.4 |  76.1∗∗$\pm$1.5 |  76.1∗∗$\pm$1.8 |  87.7∗∗$\pm$2.2 |  85.4∗∗$\pm$1.9 |  74.7∗$\pm$2.2 |  74.5∗∗$\pm$2.3
GAT | w/o RN | 76.0$\pm$1.7 | 74.9$\pm$1.9 | 66.3$\pm$2.8 | 62.4$\pm$2.6 | 73.9$\pm$2.2 | 73.9$\pm$2.1 | 88.3$\pm$2.0 | 86.2$\pm$2.2 |  79.0$\pm$2.1 |  78.8$\pm$2.3
w/ RN |  77.7∗∗$\pm$2.0 |  76.2∗∗$\pm$1.8 |  67.1∗$\pm$1.9 |  63.2∗$\pm$1.6 |  75.2∗∗$\pm$2.0 |  75.1∗∗$\pm$2.5 |  89.1∗∗$\pm$2.0 |  87.1∗∗$\pm$2.0 | 78.8$\pm$1.9 | 78.7$\pm$2.0
PPNP | w/o RN | 80.5$\pm$1.6 | 79.1$\pm$1.4 | 67.5$\pm$1.8 | 63.2$\pm$1.6 | 74.6$\pm$1.9 | 74.7$\pm$1.7 | 89.3$\pm$1.3 | 86.8$\pm$1.4 | 78.7$\pm$1.5 | 77.7$\pm$1.7
w/ RN |  81.9∗∗$\pm$0.6 |  80.5∗∗$\pm$0.8 |  68.1∗$\pm$1.4 |  63.7∗$\pm$2.0 |  76.0∗∗$\pm$2.0 |  76.1∗∗$\pm$2.2 |  89.7∗$\pm$1.0 |  87.2∗$\pm$1.3 |  79.0∗$\pm$1.1 |  78.3∗$\pm$1.1
SAGE | w/o RN | 75.1$\pm$1.7 | 74.6$\pm$1.4 | 67.0$\pm$1.4 | 63.0$\pm$1.4 | 74.2$\pm$2.2 | 74.2$\pm$2.1 | 86.2$\pm$2.6 | 83.9$\pm$2.4 | 73.5$\pm$3.4 | 71.6$\pm$2.5
w/ RN |  75.7∗∗$\pm$1.7 |  75.1∗∗$\pm$1.4 |  67.3$\pm$1.4 |  63.5∗$\pm$1.2 |  74.9∗∗$\pm$1.9 |  78.2∗∗$\pm$2.3 |  86.5$\pm$1.7 |  84.1$\pm$1.7 |  74.9∗∗$\pm$3.0 |  72.3∗∗$\pm$2.5
CHEB | w/o RN | 74.5$\pm$1.1 | 73.4$\pm$1.1 | 66.8$\pm$1.8 | 63.2$\pm$1.6 | 75.1$\pm$1.8 | 75.2$\pm$1.1 | 82.1$\pm$2.2 | 79.4$\pm$3.5 | 70.3$\pm$4.0 | 68.4$\pm$3.4
w/ RN |  75.3∗∗$\pm$1.1 |  74.0∗∗$\pm$1.1 |  67.5∗∗$\pm$1.6 |  63.8∗∗$\pm$1.5 |  76.2∗∗$\pm$1.4 |  76.3∗∗$\pm$1.2 |  84.8∗∗$\pm$2.4 |  82.1∗∗$\pm$2.8 |  70.5$\pm$4.0 |  68.6$\pm$3.4
SGC | w/o RN | 74.9$\pm$2.1 | 73.8$\pm$2.1 | 65.7$\pm$1.6 | 61.8$\pm$1.6 | 72.9$\pm$2.3 | 73.1$\pm$2.6 | 87.1$\pm$1.3 | 84.9$\pm$1.1 | 77.4$\pm$1.7 | 76.8$\pm$1.8
w/ RN |  77.0∗∗$\pm$1.1 |  76.0∗∗$\pm$1.1 |  67.2∗∗$\pm$1.3 |  62.9∗∗$\pm$1.8 |  73.7∗∗$\pm$2.8 |  73.8∗∗$\pm$2.1 |  87.4$\pm$1.5 |  85.2$\pm$1.5 |  78.2∗∗$\pm$1.8 |  77.8∗∗$\pm$1.2

Table 2: Result of different dataset conflict levels (High/Middle/Low). Our
ReNode method improve the GNN (GCN) performance most when the conflict level
of graph is high.

W-F(%) | CORA-H | CORA-M | CORA-L | CiteSeer-H | CiteSeer-M | CiteSeer-L | PubMed-H | PubMed-M | PubMed-L
---|---|---|---|---|---|---|---|---|---
w/o RN | 76.5$\pm$1.3 | 78.4$\pm$0.7 | 79.7$\pm$0.8 | 62.6$\pm$1.5 | 65.3$\pm$0.6 | 67.3$\pm$1.1 | 72.1$\pm$2.4 | 74.7$\pm$1.8 | 78.3$\pm$1.8
w/ RN |  78.7∗∗$\pm$0.8 |  79.3∗∗$\pm$0.6 |  80.4∗∗$\pm$0.6 |  63.8∗∗$\pm$1.3 |  66.0∗∗$\pm$0.8 |  67.5$\pm$1.4 |  74.3∗∗$\pm$2.1 |  75.6∗∗$\pm$1.9 |  78.8∗$\pm$1.5

##  3 Experiments

In this section, we will first introduce the experimental datasets for both
transductive and inductive semi-supervised node classification. Then we
introduce the experiments to verify the effectiveness of the proposed ReNode
method in three different imbalance situations: (1) TINL only, (2) TINL and
QINL, (3) Large-scale Graph.

###  3.1 Datasets

We adopt two sets of graph datasets to conduct experiments. For the
transductive setting [16], we take the widely-used Plantoid paper citation
graphs [42] (CORA,CiteSeer, Pubmed) and the Amazon co-purchase graphs [30]
(Photo,Computers) to verify the effectiveness of our method. For the inductive
setting, we conduct experiments on the popular Reddit dataset [16] and the
enormous MAG-Scholar dataset (coarse-grain version) [2] which owns millions of
nodes and features. For each of these datasets, we repeat experiments on $5$
different datasets splittings [43] and we run $3$ times for each splitting to
reduce the random variance. More details about the datasets and experiment
settings are presented in Appendix A.

###  3.2 ReNode for the Pure Topology-imbalance Issue

#### Settings

When considering topology-imbalance only, the labeling set takes a balanced
setting and the annotation size for each class is all equal to
${|\bm{\mathcal{L}}|}/{k}$. Following the most widely-used semi-supervised
setting in node classification studies [56, 23], we randomly select 20 nodes
in each class for training and 30 nodes per class for validation; all the
remaining nodes form the test set. We display the experiment results for the
$5$ transductive datasets on $6$ widely-used GNN models: GCN [23], GAT [49],
PPNP [24], GraphSAGE [16] (short as SAGE), ChebGCN [10] (short as CHEB) and
SGC [52]. We strictly align the hyperparameters in each group of experiments
to show the pure improvement brought by our ReNode method (similarly
hereinafter). The training loss $L_{T}$ from section 2.4 is adopted.

#### Results

From Table 1, we can find that our ReNode method can effectively improve the
overall performance (Weighted-F1) and the class-balance performance (Macro-F1)
for all the 6 experiment GNNs in most cases, which proves the effectiveness
and generalizability of our method. Our method considers the graph-specific
topology imbalance issue which has been usually neglected in existing methods
and conducts a fine-grained and self-adaptive adjustment to the training node
weights based on their topological positions. We notice that the improvement
for the CiteSeer dataset is less than the other datasets. We analyze the
reason lies in that the connectivity of CiteSeer is poor, which makes the
conflict detection–based method fail to reflect the node topological position
well. To verify the motivation of relieving topology-imbalance, we set
training sets with different levels of topology-imbalance to test our
method333The settings of the dataset topology-imbalance levels is shown in
Appendix C.. Table 2 displays that our ReNode method improves the performance
of GNN (GCN) most when the dataset is highly topologically imbalanced, which
demonstrates that our method can effectively alleviate topology-imbalance and
improve GNN performance.

###  3.3 ReNode for the Compound Scene of TINL and QINL

#### Settings

When jointly considering both topology- and quantity-imbalance issues,
following existing studies [5, 4], we take the step imbalance setting, in
which all the minority classes have the same labeling size $n_{i}$ and all the
majority classes have the same labeling size $n_{a}=\rho*n_{i}$. The imbalance
ratio $\rho$ denotes the intensity of quantity imbalance which is equal to the
ratio of the node size of the most frequent to least frequent class. In this
work, the imbalance ratio $\rho$ is set to $[5,10]$ for each dataset. The
fraction of the majority classes is $\mu$, and for all experiments, we set
$\mu=0.5$ and round down the result $\mu*k$. The training loss $L_{Q}$ from
section 2.4 is adopted. We implement two groups of baselines for comparison:
(1) Popular quantity-imbalance methods for general scenarios: Re-weight [20]
(RW), Focal Loss [28] (Focal) and Class Balanced Loss [9] (CB); (2) Graph-
specific quantity-imbalance methods: DR-GCN [44], RA-GCN [14] and GraphSMOTE
[58]. To jointly handle the topology- and quantity-imbalance issues and
demonstrate the orthogonality of them, we combine our ReNode method with these
three general quantity-imbalance methods (RW, Focal, CB)444The three graph-
specific methods have special operations for the training loss, which can be
hardly combined with our method.. The backbone model is GCN [23], and the
labeling ratio $\delta$ is set to $5\%$.

#### Results

From Table 3 (Macro-F1 is reported here for a fair comparison with these
methods designed for class-balance performance), we can find that our ReNode
method significantly outperforms both the general and the graph-specific
quantity-imbalance methods in most situations by simultaneously alleviating
the topology- and quantity-imbalance issues. Even when the training set is
severely quantity-imbalanced ($\rho$=10), our method still effectively
alleviates the imbalance issue and promotes model performance well. The
performance of the quantity-imbalance methods from the general field (RW,
Focal, CB) is on par with or less effective than the graph-specific quantity-
imbalance methods (DR-GCN, RA-GCN, G-SMOTE), while the combination of our
ReNode method and these general quantity-imbalance methods can surpass the
graph-specific quantity-imbalance methods, which demonstrates that the node
imbalance learning can be further solved by jointly handling the topology- and
quantity-imbalance issues instead of considering the quantity-imbalance issue
only.

Table 3: ReNode method for the compound scene of TINL and QINL. The imbalance
ratio $\rho$ is set to different levels ($[5,10]$) to test the effect of our
method under different imbalance intensities.

Macro-F1(%) | CORA | CiteSeer | PubMed | Photo | Computers
---|---|---|---|---|---
Imbalance Ratio | 5 | 10 | 5 | 10 | 5 | 10 | 5 | 10 | 5 | 10
CE | 60.9$\pm$1.5 | 41.0$\pm$3.5 | 53.6$\pm$2.1 | 47.6$\pm$2.8 | 61.0$\pm$1.9 | 49.7$\pm$2.6 | 62.0$\pm$2.7 | 40.7$\pm$3.4 | 50.4$\pm$2.6 | 35.5$\pm$3.2
DR-GCN | 67.7$\pm$1.1 | 51.3$\pm$1.4 | 54.7$\pm$1.7 | 52.5$\pm$2.6 | 79.4$\pm$1.2 | 78.0$\pm$1.6 | 80.8$\pm$2.3 | 79.5$\pm$2.8 | 66.9$\pm$3.5 | 67.4$\pm$3.6
RA-GCN | 69.0$\pm$1.5 | 51.7$\pm$1.7 |  55.6$\pm$1.3 | 52.7$\pm$2.1 | 80.6$\pm$1.8 | 78.1$\pm$2.1 | 81.4$\pm$2.6 | 79.4$\pm$3.2 | 71.2$\pm$2.8 | 68.7$\pm$3.0
G-SMOTE | 68.1$\pm$0.9 | 49.6$\pm$1.1 | 54.0$\pm$1.6 | 51.8$\pm$1.3 | 79.7$\pm$1.2 | 76.4$\pm$1.5 | 82.2$\pm$1.8 | 77.5$\pm$2.1 | 71.9$\pm$2.5 | 61.3$\pm$3.2
RW (w/o RN) | 69.1$\pm$1.4 | 49.7$\pm$1.6 | 53.6$\pm$2.3 | 52.9$\pm$2.6 | 80.5$\pm$1.5 | 78.0$\pm$2.0 | 80.5$\pm$2.7 | 80.4$\pm$3.3 | 70.5$\pm$3.2 | 67.8$\pm$4.2
RW (w/ RN) | 70.0∗$\pm$1.3 | 50.1$\pm$1.7 | 55.2∗∗$\pm$1.8 | 54.0∗∗$\pm$2.5 |  81.2∗$\pm$1.0 | 78.5∗$\pm$2.2 |  83.9∗∗$\pm$2.1 |  81.3∗∗$\pm$3.2 | 72.4∗∗$\pm$2.6 |  70.2∗∗$\pm$2.4
FOCAL (w/o RN) | 66.4$\pm$1.6 | 51.9$\pm$1.8 | 54.3$\pm$1.3 | 54.0$\pm$1.9 | 80.5$\pm$0.7 | 78.0$\pm$1.6 | 79.3$\pm$1.9 | 79.2$\pm$2.2 | 65.8$\pm$2.7 | 63.9$\pm$2.6
FOCAL (w/ RN) | 68.7∗∗$\pm$0.7 |  52.6∗∗$\pm$1.9 | 54.6$\pm$1.2 |  54.7∗$\pm$1.5 | 80.9∗$\pm$0.8 |  78.7∗∗$\pm$1.4 | 80.0∗∗$\pm$2.3 | 80.7∗∗$\pm$2.9 | 68.6∗∗$\pm$3.1 | 65.5∗∗$\pm$3.5
CB (w/o RN) | 69.8$\pm$1.5 | 51.5$\pm$1.5 | 54.1$\pm$1.3 | 53.5$\pm$0.8 | 80.6$\pm$0.8 | 77.6$\pm$1.6 | 77.9$\pm$2.6 | 78.8$\pm$3.1 | 69.6$\pm$2.2 | 64.8$\pm$2.9
CB (w/ RN) |  71.1∗∗$\pm$0.6 | 51.9∗$\pm$1.2 | 54.7∗$\pm$1.6 | 54.3∗∗$\pm$2.3 | 81.2∗$\pm$1.8 | 78.3∗∗$\pm$2.6 | 79.6∗∗$\pm$2.7 | 80.4∗∗$\pm$3.3 |  73.1∗∗$\pm$3.1 | 66.5∗∗$\pm$3.6

###  3.4 ReNode for Large-scale Graphs

#### Settings

We conduct experiments on the two large-scale datasets: Reddit and MAG-
Scholar, to verify the effectiveness of our ReNode method in the inductive
setting. We conduct experiments with different labeling sizes (20/50/100
training nodes per class) and imbalance settings (TINL-only, TINL and QINL).
The backbone GNN model is PPRGo [2] 555We do not implement other inductive
backbone GNN models like Cluster-GCN [8] or APPNP [24] due to the low
efficiency [2] of them when handling the enormous MAG-Scholar dataset.. For
QINL, we take the uniform selection to sample training nodes to be consistent
with PPRGo. The training loss $L_{L}$ from section 2.4 is adopted. Both
baseline and our methods are not combined with any quantity-imbalance method.

#### Results

In Figure 4, we present the experiment results with different labeling sizes
and imbalance settings, we can find that our method can effectively promote
the performance on the large-scale graphs comparing to the popular PPRGo model
across different settings, which demonstrates the applicability of our method
for extremely-large graphs. We also notice that our method can bring greater
improvement when the labeling size is large. We explain the reason lies in
that when the labeling size is large, the positions located by the conflicts
among nodes will be more accurate, thus bringing more reasonable weight
adjustments. On the other hand, when the labeling ratio is extremely small
(especially for the enormous MAG-Scholar graph) and the influence conflict
between the labeled nodes is negligible, our method exhibits the cold start
problem.

Figure 4: Experimental results (Weighted-F1,%) on the large-scale Reddit and
MAG-Scholar graphs. Our ReNode method can effectively improve the model
performance under different labeling sizes.

Figure 5: Evaluating GNNs from the aspect of topology-imbalance sensitivity
(Metric: Weighted-F1 (%)). We can summarize the ranking of topology-imbalance
sensitivity: GCN > PPNP > GAT.

##  4 Discussions

###  4.1 Evaluating GNNs from the Aspect of Topology-Imbalance Sensitivity

In Figure 5, we evaluate the GNN’s capability for handling topology-imbalance
and find that different GNNs present significant difference in the topology-
imbalance sensitivity across multiple datasets. The GCN model is susceptible
to the topology-imbalance level of the graph and its performance decays
greatly when the topology-imbalance increases. On the opposite, the GAT model
is less sensitive to the topology-imbalance level and can achieve the best
results when the topology-imbalance level is high. The PPNP model can achieve
ideal performance when the topology-imbalance level is low, and its
performance does not drop as sharply as GCN when the topology-imbalance level
is high. We analyze the reason lies in that: (1) the aggregation operation of
GCN is equivalent to directly averaging neighbor features [54] that lacks the
noise filtering mechanism, so it is more sensitive to the topology-imbalance
level of the graph; (2) the GAT model can dynamically adjust the aggregation
weight from different neighbors, which increases its robustness to the high
topology-imbalance situation but hinders the model performance when the graph
topology-imbalance level is low and there is less need to filter neighbor
information; (3) the infinite convolution mechanism of the PPNP model makes it
possible to aggregate the information from distant nodes to enhance its
robustness to the graph topology imbalance.

Shchur et al. [43] notice that the performance ranking of GNNs varies with the
training set selection. Hence, existing node classification studies [41, 17]
usually repeat experiments multiple times with different training sets to
reduce this randomness. The results from Figure 5 inspire us that the topology
imbalance can partly explain the randomness of GNN performance caused by the
training set selection and we can adopt the topology-imbalance sensitivity as
a new aspect in evaluating the performance of different GNN architectures.

###  4.2 Limitations of Method

Although our ReNode method has proven effective in multiple scenarios, we also
notice some limitations of it because of the complexity of node imbalance
learning. First, the ReNode method is devised for homogeneously-connected
graphs (linked nodes are expected to be similar, such as the various datasets
in experiments), and it needs a further update for heterogeneously-connected
graphs (such as protein networks). Besides, the ReNode method improves less
when the graph connectivity is poor (Section 3.2) or the labeling ratio is
extremely low (Section 3.3) because in these cases, the conflict level among
nodes is low thus the nodes topological positions are insufficiently
reflected.

##  5 Related Work

Imbalanced classification problems are widespread in real scenarios and have
attracted extensive attention from both academia and industry. Most existing
studies on this topic focus on the class-imbalanced quantity distribution
[18], where the model’s inference ability for the majority classes will be
significantly better than that of minority classes [15]. The existing methods
for solving the quantity-imbalance issue can be roughly divided into methods
for the data selection phase and the model training phase. Active learning
[39, 12, 51] and Re-sampling [6, 19, 32] are two classical examples designed
to construct a quantity-balanced training set . On the other hand, Re-
weighting is a simple but effective solution for the model training phase,
which adjusts the weights of training samples in different classes based on
the labeling sizes [20, 38, 9, 5]. However, directly applying these methods
into the graph scene lacks the consideration for the graph-specific topology-
imbalance issue. Unlike the re-weight methods which conduct class-lever re-
weighting, our ReNode method is a more fine-grained one and assign weights to
each node individually.

There have been quantity-imbalance studies (Tomek links [47], NearMiss [29],
One-Sided Selection [25]) trying to exclude the negative influence of labeling
samples close to class boundaries by measuring the similarity of sample
features. However, in the graph scene, the prior knowledge contained in node
connections is more reliable than directly calculating the feature similarity.
Besides, the number of labeled nodes is quite small in the semi-supervised
setting. Thus it is not robust to locate their positions by computing
similarity among a small number of nodes and we propose to leverage the
influence conflict across the whole graph to locate node position to
boundaries.

Graph data structure owns a wide range of applications, such as social media
[16], stock exchange [27], shopping [43], medicine [53], transportation [36]
and so on. Similar to other data structures, graph node representation
learning also suffer from the quantity-imbalance issue [44]. Apart from the
universal quantity-balance approaches introduced in Section 5 which can be
transferred to the graph scene, there are some graph-specific quantity-
imbalance methods recently proposed. DR-GCN [44] propose two types of
regularization to tackle quantity imbalance: class-conditioned adversarial
training and unlabeled nodes latent distribution constraint. RA-GCN [14]
propose to automatically learn to weight the training samples in different
classes in an adversarial training manner. AdaGCN Shi et al. [45] propose to
leverage the boosting algorithm to handle the quantity-imbalance issue for the
node classification task. GraphSMOTE [58] combines the synthetic node
generation and the edge generation to up-sample nodes for the minority
classes. However, these studies only pay attention to the quantity imbalance
and overlook the topology imbalance.

Different from these studies [57, 37, 33] that try to locate the absolute
positions for all the nodes by measuring their distance from the selected
anchor nodes, our Totoro metric is devised to locate the relative positions to
the class boundary for the labeling nodes by considering the influence
conflict and can get rid of the dependence on the anchor nodes. Besides, our
relative positions can more accurately reflect node class information because
we distinguish the information from different classes while existing studies
[57, 37] treat all the anchor nodes the same and ignore the class difference.

##  6 Conclusion and Future Work

In this work, we recognize the topology-imbalance node representation learning
(TINL) as a graph-specific imbalance learning problem that has not been
studied so far. We find that the topology-imbalance issue widely exists in
graphs and severely hinders the learning of node classification. We unify TINL
with the quantity-imbalance node representation learning (QINL) by considering
the shift of the node influence boundaries from true class boundaries. To
measure the degree of topology imbalance, we devise a conflict detection–based
metric Totoro to locate node position, and further propose the ReNode method
to adaptively adjust the training weights of labeled nodes based on their
topological positions. Extensive empirical results have verified the
effectiveness of our method in various settings: TINL-only, both TINL and
QINL, and large-scale graph. Besides, we also propose the topology-imbalance
sensitivity as a new metric to evaluate GNNs.

Considering the importance of the topology-imbalance issue and the limitations
of our approach, advanced methods with stronger theoretical or experimental
support are expected in future work. Moreover, since topology imbalance is
widespread in graph-related tasks other than node classification, how to
measure and solve the topology-imbalance issues in broader graph scopes
remains a meaningful challenge for future study.

##  7 Acknowledgement

We appreciate all the thoughtful and insightful suggestions from reviews. This
work was supported in part by a Tencent Research Grant and National Natural
Science Foundation of China (No. 61673028). Xu Sun is the corresponding author
of this paper.

## References

  * Andersen et al. [2006] Reid Andersen, Fan R. K. Chung, and Kevin J. Lang.  Local Graph Partitioning using PageRank Vectors.  In _47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings_ , pages 475–486. IEEE Computer Society, 2006.
  * Bojchevski et al. [2020] Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann.  Scaling Graph Neural Networks with Approximate PageRank.  In _the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2020_ , pages 2464–2473. ACM, 2020.
  * Buchnik and Cohen [2018] Eliav Buchnik and Edith Cohen.  Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity.  _Proc. ACM Meas. Anal. Comput. Syst._ , 2(1):10:1–10:19, 2018.
  * Buda et al. [2018] Mateusz Buda, Atsuto Maki, and Maciej A. Mazurowski.  A Systematic Study of the Class Imbalance Problem in Convolutional Neural Networks.  _Neural Networks_ , 106:249–259, 2018.
  * Cao et al. [2019] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Aréchiga, and Tengyu Ma.  Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss.  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , pages 1565–1576, 2019.
  * Chawla et al. [2002] Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall, and W Philip Kegelmeyer.  SMOTE: Synthetic Minority Over-sampling Technique.  _Journal of artificial intelligence research_ , 16:321–357, 2002.
  * Chen et al. [2020] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun.  Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View.  In _the 34th AAAI Conference on Artificial Intelligence, AAAI 2020_ , pages 3438–3445. AAAI Press, 2020.
  * Chiang et al. [2019] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh.  Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks.  In _the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019_, pages 257–266. ACM, 2019.
  * Cui et al. [2019] Yin Cui, Menglin Jia, Tsung-Yi Lin, Yang Song, and Serge J. Belongie.  Class-Balanced Loss Based on Effective Number of Samples.  In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019_ , pages 9268–9277. Computer Vision Foundation / IEEE, 2019.
  * Defferrard et al. [2016] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.  Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering.  In _Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain_ , pages 3837–3845, 2016.
  * Duan et al. [2018] Yueqi Duan, Wenzhao Zheng, Xudong Lin, Jiwen Lu, and Jie Zhou.  Deep Adversarial Metric Learning.  In _2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018_ , pages 2780–2789. Computer Vision Foundation / IEEE Computer Society, 2018.
  * Ertekin et al. [2007] Seyda Ertekin, Jian Huang, and C Lee Giles.  Active Learning for Class Imbalance Problem.  In _the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2007_ , pages 823–824, 2007.
  * Fey and Lenssen [2019] Matthias Fey and Jan E. Lenssen.  Fast Graph Representation Learning with PyTorch Geometric.  In _ICLR Workshop on Representation Learning on Graphs and Manifolds_ , 2019.
  * Ghorbani et al. [2021] Mahsa Ghorbani, Anees Kazi, Mahdieh Soleymani Baghshah, Hamid R. Rabiee, and Nassir Navab.  RA-GCN: Graph Convolutional Network for Disease Prediction Problems with Imbalanced Data.  _arXiv preprint: 2103.00221_ , 2021.
  * Guo et al. [2017] Haixiang Guo, Yijing Li, Jennifer Shang, Gu Mingyun, Huang Yuanyue, and Gong Bing.  Learning from Class-Imbalanced Data: Review of Methods and Applications.  _Expert Syst. Appl._ , 73:220–239, 2017.
  * Hamilton et al. [2017] William L. Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive Representation Learning on Large Graphs.  In _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pages 1024–1034, 2017.
  * Hassani and Khasahmadi [2020] Kaveh Hassani and Amir Hosein Khasahmadi.  Contrastive Multi-View Representation Learning on Graphs.  In _the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 4116–4126. PMLR, 2020.
  * He and Garcia [2009] Haibo He and Edwardo A. Garcia.  Learning from imbalanced data.  _IEEE Trans. Knowl. Data Eng._ , 21(9):1263–1284, 2009.
  * He et al. [2008] Haibo He, Yang Bai, Edwardo A. Garcia, and Shutao Li.  ADASYN: Adaptive synthetic sampling approach for imbalanced learning.  In _the International Joint Conference on Neural Networks, IJCNN 2008, part of the IEEE World Congress on Computational Intelligence, WCCI 2008, Hong Kong, China, June 1-6, 2008_ , pages 1322–1328. IEEE, 2008.
  * Huang et al. [2016] Chen Huang, Yining Li, Chen Change Loy, and Xiaoou Tang.  Learning Deep Representation for Imbalanced Classification.  In _the 29th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016_ , pages 5375–5384, 2016.
  * Kalantidis et al. [2020] Yannis Kalantidis, Mert Bülent Sariyildiz, Noé Pion, Philippe Weinzaepfel, and Diane Larlus.  Hard Negative Mixing for Contrastive Learning.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.
  * Kingma and Ba [2015] Diederik P. Kingma and Jimmy Ba.  Adam: A Method for Stochastic Optimization.  In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , 2015.
  * Kipf and Welling [2017] Thomas N Kipf and Max Welling.  Semi-supervised Classification with Graph Convolutional Networks.  In _the 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings_. OpenReview.net, 2017.
  * Klicpera et al. [2019] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann.  Predict then Propagate: Graph Neural Networks meet Personalized PageRank.  In _the 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net, 2019.
  * Kubat et al. [1997] Miroslav Kubat, Stan Matwin, et al.  Addressing the Curse of Imbalanced Training Sets: One-sided Selection.  In _the 14th International Conference on Machine Learning (ICML 1997), Nashville, Tennessee, USA, July 8-12, 1997_ , volume 97, pages 179–186. Morgan Kaufmann, 1997.
  * Li et al. [2018] Qimai Li, Zhichao Han, and Xiao-Ming Wu.  Deeper Insights into Graph Convolutional Networks for Semi-supervised Learning.  In _the 32nd AAAI Conference on Artificial Intelligence, New Orleans, Louisiana, USA, February 2-7, 2018_ , pages 3538–3545. AAAI Press, 2018\.
  * Li et al. [2020] Wei Li, Ruihan Bao, Keiko Harimoto, Deli Chen, Jingjing Xu, and Qi Su.  Modeling the Stock Relation with Graph Network for Overnight Stock Movement Prediction.  In _the 29th International Joint Conference on Artificial Intelligence, IJCAI 2020_ , pages 4541–4547. ijcai.org, 2020.
  * Lin et al. [2017] Tsung-Yi Lin, Priya Goyal, Ross B. Girshick, Kaiming He, and Piotr Dollár.  Focal Loss for Dense Object Detection.  In _IEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017_ , pages 2999–3007. IEEE Computer Society, 2017.
  * Mani and Zhang [2003] Inderjeet Mani and I Zhang.  kNN Approach to Unbalanced Data Distributions: A Case Study Involving Information Extraction.  In _Workshop on Learning from Imbalanced Datasets_ , volume 126, 2003\.
  * McAuley et al. [2015] Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel.  Image-based Recommendations on Styles and Substitutes.  In _the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, Santiago, Chile, August 9-13, 2015_ , pages 43–52. ACM, 2015.
  * Nair and Hinton [2010] Vinod Nair and Geoffrey E Hinton.  Rectified Linear Units Improve Restricted Boltzmann Machines.  In _the 27th International Conference on Machine Learning (ICML-10), June 21-24, 2010, Haifa, Israel_ , pages 807–814. Omnipress, 2010.
  * Nekooeimehr and Lai-Yuen [2016] Iman Nekooeimehr and Susana K Lai-Yuen.  Adaptive Semi-unsupervised Weighted Oversampling (A-SUWO) for Imbalanced Datasets.  _Expert Systems with Applications_ , 46:405–416, 2016.
  * Nishad et al. [2020] Sunil Nishad, Shubhangi Agarwal, Arnab Bhattacharya, and Sayan Ranu.  GraphReach: Position-Aware Graph Neural Networks using Reachability Estimations.  In _the 30th International Joint Conference on Artificial Intelligence IJCAI_ , 2020.
  * Page et al. [1999] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd.  The PageRank Citation Ranking: Bringing Order to the Web.  Technical report, Stanford InfoLab, 1999.
  * Paszke et al. [2017] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer.  Automatic Differentiation in PyTorch.  In _NeuriIPS 2017 Workshop on Autodiff_ , 2017.
  * Prokoptsev et al. [2018] Nikolay G Prokoptsev, AE Alekseenko, and Yaroslav Aleksandrovich Kholodov.  Traffic Flow Speed Prediction on Transportation Graph with Convolutional Neural Networks.  _Computer research and modeling_ , 10(3):359–367, 2018.
  * Qin et al. [2021] Zhenyue Qin, Saeed Anwar, Dongwoo Kim, Yang Liu, Pan Ji, and Tom Gedeon.  Position-Sensing Graph Neural Networks: Proactively Learning Nodes Relative Positions.  _arXiv preprint: 2105.11346_ , 2021.
  * Ren et al. [2018] Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun.  Learning to Reweight Examples for Robust Deep Learning.  In _International Conference on Machine Learning_ , pages 4334–4343. PMLR, 2018.
  * Ren et al. [2020] Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Yao Huang, Zhihui Li, Xiaojiang Chen, and Xin Wang.  A Survey of Deep Active Learning.  _arXiv preprint: 2009.00236_ , 2020.
  * Robinson et al. [2021] Joshua David Robinson, Ching-Yao Chuang, Suvrit Sra, and Stefanie Jegelka.  Contrastive Learning with Hard Negative Samples.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021.
  * Rong et al. [2019] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang.  The Truly Deep Graph Convolutional Networks for Node Classification.  _arXiv preprint: 1907.10903_ , 2019.
  * Sen et al. [2008] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.  Collective Classification in Network Data.  _AI magazine_ , 29(3):93–93, 2008.
  * Shchur et al. [2018] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann.  Pitfalls of Graph Neural Network Evaluation.  _arXiv preprint: 1811.05868_ , 2018.
  * Shi et al. [2020] Min Shi, Yufei Tang, Xingquan Zhu, David A. Wilson, and Jianxun Liu.  Multi-Class Imbalanced Graph Convolutional Network Learning.  In _the 29th International Joint Conference on Artificial Intelligence, IJCAI 2020_ , pages 2879–2885. ijcai.org, 2020.
  * Shi et al. [2021] Shuhao Shi, Kai Qiao, Shuai Yang, L Wang, J Chen, and Bin Yan.  AdaGCN: Adaptive Boosting Algorithm for Graph Convolutional Networks on Imbalanced Node Classification.  _arXiv preprint: 2105.11625_ , 2021.
  * Sokol et al. [2012] Marina Sokol, Konstantin Avrachenkov, Paulo Gonçalves, and Alexey Mishenin.  Generalized Optimization Framework for Graph-based Semi-supervised Learning.  In _the 12th SIAM International Conference on Data Mining, Anaheim, California, USA, April 26-28, 2012_ , pages 966–974. SIAM / Omnipress, 2012.
  * Tomek et al. [1976] Ivan Tomek et al.  Two Modifications of CNN.  _IEEE Transactions on Systems, Man, and Cybernetics_ , 1976.
  * Van der Maaten and Hinton [2008] Laurens Van der Maaten and Geoffrey Hinton.  Visualizing Data using t-SNE.  _Journal of machine learning research_ , 9(11), 2008.
  * Veličković et al. [2018] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph Attention Networks.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_. OpenReview.net, 2018.
  * Wang and Leskovec [2020] Hongwei Wang and Jure Leskovec.  Unifying Graph Convolutional Neural Networks and Label Propagation.  _arXiv preprint: 2002.06755_ , 2020.
  * Wang et al. [2020] Xinyue Wang, Bo Liu, Siyu Cao, Liping Jing, and Jian Yu.  Important Sampling based Active Learning for Imbalance Classification.  _Science China Information Sciences_ , 63(8):1–14, 2020.
  * Wu et al. [2019] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger.  Simplifying Graph Convolutional Networks.  In _International Conference on Machine Learning_ , pages 6861–6871. PMLR, 2019.
  * Wu et al. [2018] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande.  MoleculeNet: a Benchmark for Molecular Machine Learning.  _Chemical science_ , 2018.
  * Xu et al. [2019] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How Powerful are Graph Neural Networks?  In _the 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net, 2019.
  * Yang and Xu [2020] Yuzhe Yang and Zhi Xu.  Rethinking the Value of Labels for Improving Class-Imbalanced Learning.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.
  * Yang et al. [2016] Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov.  Revisiting Semi-supervised Learning with Graph Embeddings.  In _the 33nd International Conference on Machine Learning, ICML 2016_ , volume 48 of _JMLR Workshop and Conference Proceedings_ , pages 40–48. JMLR.org, 2016.
  * You et al. [2019] Jiaxuan You, Rex Ying, and Jure Leskovec.  Position-aware Graph Neural Networks.  In _the 36th International Conference on Machine Learning, ICML 2019_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 7134–7143. PMLR, 2019.
  * Zhao et al. [2021] Tianxiang Zhao, Xiang Zhang, and Suhang Wang.  GraphSMOTE: Imbalanced Node Classification on Graphs with Graph Neural Networks.  In _WSDM ’21, The Fourteenth ACM International Conference on Web Search and Data Mining, Virtual Event, Israel, March 8-12, 2021_ , pages 833–841. ACM, 2021.
  * Zheng et al. [2019] Wenzhao Zheng, Zhaodong Chen, Jiwen Lu, and Jie Zhou.  Hardness-Aware Deep Metric Learning.  In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019_ , pages 72–81. Computer Vision Foundation / IEEE, 2019.
  * Zhou and Burges [2007] Dengyong Zhou and Christopher J. C. Burges.  Spectral Clustering and Transductive Learning with Multiple Views.  In _the 24th Annual International Conference on Machine Learning, ICML 2007_ , volume 227, pages 1159–1166. ACM, 2007.
  * Zhou et al. [2020] Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun.  Graph Neural Networks: A Review of Methods and Applications.  _AI Open_ , 1, 2020.

##  Appendix A More Details of Dataset and Experiments

#### Linux Server

We run all the experiments on a Linux server, some important information is
listed:

  * •

CPU: Intel(R) Xeon(R) Silver 4210 CPU @ 2.20GHz $\times$ 40

  * •

GPU: NVIDIA GeForce RTX2080TI-11GB $\times$ 8

  * •

RAM: 125GB

  * •

cuda: 11.1

#### Python Package

We implement all deep learning methods based on Python3.7. The experiment code
is included in the supplementary materials. The versions of some important
packages are listed:

  * •

torch [35]: 1.9.1+cu111

  * •

torch-geometric [13]: 2.0.1

  * •

torch-cluster:1.5.9

  * •

torch-sparse: 0.6.12

  * •

scikit-learn: 1,0

  * •

numpy:1.20.3

  * •

scipy:1.7.1

#### Datasets

The statistical information of our experimental datasets are shown in Table 4.
All these data are publicly available and the URLs listed as follows:

  * •

Planetoid Citation Datasets [42] (CORA/CiteSeer/PubMed):
https://github.com/rusty1s/pytorch_geometric/blob/master/torch_geometric/datasets/planetoid.py

  * •

Amazon Co-purchasing Datasets [30] (Photo/Computers):
https://github.com/rusty1s/pytorch_geometric/blob/master/torch_geometric/datasets/amazon.py

  * •

Reddit Comment Dataset [16]:https://github.com/TUM-
DAML/pprgo_pytorch/blob/master/data/get_reddit.md

  * •

MAG-Scholar Dataset [2] (coarse grained version):
https://figshare.com/articles/dataset/mag_scholar/12696653/2

Table 4: Statistical information about datasets. M indicates million. Dataset | #Node | #Edge | #Feature | #Class | Training
---|---|---|---|---|---
CORA | 2,708 | 5,429 | 1,433 | 7 | Transductive
CiteSeer | 3,327 | 4,732 | 3,703 | 6 | Transductive
PubMed | 19,717 | 44,338 | 5,00 | 3 | Transductive
Photo | 7,487 | 119,043 | 745 | 8 | Transductive
Computers | 13,381 | 245,778 | 767 | 10 | Transductive
Reddit | 232,965 | 11,606,919 | 602 | 41 | Inductive
MAG-Scholar | 10.5145M | 132.8176M | 2.7842M | 8 | Inductive
Table 5: Dataset Topology-Imbalance Level

$\sum_{v\in{\bm{\mathcal{L}}}}\bm{T}_{v}$ | LOW | MIDDLE | HIGH
---|---|---|---
CORA | 4.26$\pm$0.27 | 6.03$\pm$0.21 | 7.39$\pm$0.43
CiteSeer | 1.19$\pm$0.11 | 2.26$\pm$0.01 | 4.37$\pm$0.23
Pubmed | 0.14$\pm$0.02 | 0.25$\pm$0.01 | 0.42$\pm$0.05

#### Dataset Splitting

In training, we run 5 different random splittings for each dataset to relieve
the randomness introduce by the training set selection following Shchur et al.
[43]. We repeat experiments 3 times for each splitting to relieve the training
splitting. The final performance (weighted F1, macro F1, and the standard
deviation) is calculated based on the 15 repeated experiments. The dataset
splitting seed list is $[0,1,2,3,4]$; the model training random seed list is:
$[0,1,2]$.

#### Method Hyperparameters

For all encoders ($\mathcal{F}$ and $\mathcal{F^{\prime}}$), we stacked two
GNN or linear layers with the ReLU [31] activation function666Except the SGC
model, which increases the power iteration times of the normalized adjacency
matrix to replace stacking GNN layers.. All the hyper-parameters are tuned on
the validation set. The tuning range of dataset-specific hyperparameters is as
follows:

  * •

PageRank teleport probability $\alpha$: $[0.05,0.1,0.15,0.2]$;

  * •

Dimension of hidden layer: $[16,32,64,128,256]$;

  * •

Lower bound of the cosine annealing $w_{min}$: $[0.25,0.5,0.75]$;

  * •

Upper bound of the cosine annealing $w_{max}$: $[1.25,1.5,1.75]$;

#### Training Setting

We take the Adam [22] as the model optimizer. The learning ratio begins to
decay after 20 epochs with a ratio of 0.95. We early stop the training process
if there is no improvement in 20 epochs. The tuning range of dataset-specific
hyperparameters is as follows:

  * •

Learning Rate:$[0.005,{0.0075},0.01,0.015]$,

  * •

Dropout Probability: $[0.2,0.3,0.4,{0.5},0.6]$.

##  Appendix B Supplement to the ReNode Method

Apart from the relative ranking re-weight method in ReNode, we also tried to
adjust the training weight based on the following scheduling methods:

  * •

Linear decay based on the original node Totoro values;

  * •

Linear decay based on the rank of node Totoro values;

  * •

Discrete values for different nodes with a piece-wise function;

Among all these methods, the presented cosine annealing method works best. We
analyze the reason lies in that, PageRank is proposed for node ranking; hence
adjusting weights based on the original values is not robust and can be
largely affected by outliers. Comparing to the linear decay schedule, the
cosine schedule methods pay more attention to nodes with middle-level
conflict, distinguishing which is of great importance for the model training.

The ReNode method assigns more weights to nodes far away from the graph class
boundaries, which it is different from methods used in metric learning [59,
11] or contrastive learning [21, 40] that pay more attention to the ’hard’
samples closing to class boundaries. In semi-supervised node classification,
most message-passing based GNN model (e.g. GCN) relies on smoothing the
adjacent nodes to transfer the category information from the labeled nodes to
the unlabeled nodes [26, 7]. Thus, the ’easy’ labeled nodes far away from the
class boundaries are expected to better represent class prototypes. Enlarging
the training weights of those ’hard’ nodes that are close to the class
boundaries makes it easier to confuse the class prototype with others.
Besides, the labeling size in semi-supervised learning is much smaller than
supervised learning (usually 20 nodes per class) and usually, the training
nodes are sampled randomly. Hence, a very likely scenario is that the ’hard’
samples for some categories are very close to the true class boundaries, while
the ’hard’ samples for other categories are far away from the true class
boundaries. Relying on these ’hard’ nodes to decide decision boundaries will
cause a large shift of decision boundaries from the true ones.

##  Appendix C Settings of Dataset Topology-Imbalance Levels

In Section 3, we evaluate the model performance under different levels of
topology imbalance. We introduce the settings for the topology-imbalance
levels. For each experiment dataset, we randomly sampled 100 training sets,
and calculate the dataset overall conflict as introduced in Section 2.3. Then
we choose the 3 training sets with the highest/middle/lowest overall conflict
as the high/middle/low-level topology-imbalance setting and report the average
results on the 3 training sets for each dataset. The specific conflict values
of different levels are displayed in Table 5.

##  Appendix D Submission Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes] The main claims stated in the
abstract and introduction accurately reflect the paper’s contributions and
scope.

    2. (b)

Did you describe the limitations of your work? [Yes] We discuss the limitation
in Section 4.2.

    3. (c)

Did you discuss any potential negative societal impacts of your work? [N/A] We
think that our proposal has no obvious potential negative societal effect.

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes] We have read ethics review guidelines and ensure that
our paper conforms to them.

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [N/A]

    2. (b)

Did you include complete proofs of all theoretical results? [N/A]

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]
We include them in the supplemental material.

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes] We describe them in detail in the paper main body
and the appendix.

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [Yes] We report error bars and the random seed
for all experiments in the paper main body and the appendix.

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We include
them in the appendix.

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes] We cite
all the existing assets used in this work.

    2. (b)

Did you mention the license of the assets? [Yes] We mention the license in
appendix.

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [N/A] We have no new assets.

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [Yes] All the datasets we use is open-source and can be
obtained from their public release.

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [Yes]  the datasets we use has
no personally identifiable information or offensive content.

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]


# A Note on the Complexity of One-Sided Crossing Minimization of Trees

Alexander Dobler  [regular]envelope Algorithms and Complexity Group, TU Wien,
Austria

###### Abstract

In 2011, Harrigan and Healy published a polynomial-time algorithm for one-
sided crossing minimization for trees [2]. We point out a counterexample to
that algorithm, and show that one-sided crossing minimization is -hard for
trees.

##  1 Introduction

One-sided crossing minimization deals with the minimization of crossings in
drawings of bipartite graphs. Given a bipartite graph $G=(V_{1}\cupdot
V_{2},E)$ with the vertex set $V_{1}$ ordered vertically on the left side by a
permutation $\pi_{1}$, the task is to find a vertical order $\pi_{2}$ of
$V_{2}$ on the right side to minimize the number of pairwise crossings between
the edges in $E$ if they are drawn as straight lines (see Figure 1(b)). Here,
$A\cupdot B$ is the disjoint union of two sets $A$ and $B$. In this paper, we
call such a drawing _two-layer drawing_ of $G$ respecting $\pi_{1}$ and
$\pi_{2}$. The problem is known as One-Sided Crossing Minimization (OSCM), or
as One-Layer Crossing Minimization (OLCM). It is well-known that this problem
is -hard for general bipartite graphs [1]. A 2011 WALCOM paper [2] presented a
polynomial-time algorithm for the case when $G$ is a tree. In Section 2 we
discuss their proof and give a counterexample to the statements leading to the
presented algorithm. In Section 3 a proof for -hardness of One-Sided Crossing
Minimization in trees is given.

(a) A tree $T$ (which forms a bipartite graph).

(b) A two-layer drawing of $T$ with $9$ crossings.

(c) The directed graph $CP_{T}$.

Figure 1: A counterexample to $CP_{T}$ being acyclic.

##  2 The Proof in [2] and a Counterexample

The proof applies a well-known characterization of optimal solutions of OSCM
in terms of feedback arc set. Namely, let us consider an instance
$G=(V_{1}\cupdot V_{2},E)$ of OSCM with a fixed permutation $\pi_{1}$ of
$V_{1}$. For $u,v\in V_{2}$, let $c(u,v)$ be the number of crossings between
edge pairs in $N_{G}(u)\times N_{G}(v)$ if $u$ is placed before $v$ in
permutation $\pi_{2}$, where $N_{G}(u)$ (resp. $N_{G}(v)$) are the edges
incident to $u$ (resp. $v$) in $G$. Let $CP_{G}$ be the directed multi-graph
defined on the vertex set $V_{2}$ such that, for $u,v\in V_{2}$, there exist
$cr(u,v)-cr(v,u)$ edges from $u$ to $v$ if $cr(u,v)>cr(v,u)$. The number of
crossings in an optimal solution can then be obtained by the cardinality of a
minimum feedback arc set $A$ in $CP_{G}$, and the ordering $\pi_{2}$ achieving
this amount of crossings can be obtained by removing $A$ from $CP_{G}$ and
defining $\pi_{2}$ as some topological ordering of the obtained directed
acyclic graph [4].

The authors in [2] claim that $CP_{T}$ is acyclic for trees $T$. This would
imply a simple algorithm for One-Sided Crossing Minimization by computing a
topological ordering of $CP_{T}$. In Figure 1 we give a counterexample to that
claim. Namely, let $T$ be as in Figure 1(a), such that
$V_{1}=\\{a,b,c,d,e,f\\},V_{2}=\\{g,h,i\\}$ and let $\pi_{1}=(d,f,b,a,c,e)$.
This implies that

$\displaystyle\text{cr}(g,h)=2,$ $\displaystyle\text{cr}(h,g)=3,$
$\displaystyle\text{cr}(g,i)=3,$ $\displaystyle\text{cr}(i,g)=2,$
$\displaystyle\text{cr}(h,i)=4,$ $\displaystyle\text{cr}(i,h)=5,$

which results in the graph $CP_{T}$ in Figure 1(c) that is not acyclic. In
fact, this is one of the counterexamples s.t. $T$ has the fewest number of
vertices.

##  3 NP-hardness

OSCM is -hard for trees by a reduction from another restricted variant of OSCM
discussed in [3]: it was shown that OSCM is -hard for bipartite graphs
$G=(V_{1}\cupdot V_{2},E)$ such that $G$ is the disjoint union of 4-stars,
that is, the connected components of $G$ are 5-vertex graphs with one vertex
having degree 4 and the remaining vertices having degree 1. Furthermore,
$V_{1}$ consists of all the degree-1 vertices, while $V_{2}$ consists of all
the degree-4 vertices. Given such a graph $G$ and a permutation $\pi_{1}$ of
$V_{1}$, it is -hard to find a permutation $\pi_{2}$ of $V_{2}$ that minimizes
the number of edge crossings.

Figure 2: Sketch of the construction of $G^{\prime}$.

Let us consider the graph $G^{\prime}$ that is constructed from $G$ by adding
a new vertex $v$ to $V_{1}$ and connecting $v$ to all vertices in $V_{2}$ (see
Figure 2). Note that $G^{\prime}$ is a tree and consider the ordering
$\pi_{1}^{\prime}$ of $V_{1}(G^{\prime})$ that is constructed from $\pi_{1}$
by appending $v$ to the end. Let $\pi_{2}$ be a permutation of $V_{2}$. The
following is easy to see.

######  Lemma 3.1.

A two-layer drawing of $G$ respecting $\pi_{1}$ and $\pi_{2}$ has $k$
crossings if and only if a two-layer drawing of $G^{\prime}$ respecting
$\pi_{1}^{\prime}$ and $\pi_{2}$ has $k+|V_{2}|(|V_{2}|-1)$ crossings.

###### Proof.

We calculate the number of crossings involving edges incident to $v$ (the
purple edges in Figure 2) in the drawing of $G^{\prime}$ as follows.

$\displaystyle 4+2\cdot 4+3\cdot 4+\dots+(|V_{2}|-1)\cdot
4=2|V_{2}|(|V_{2}|-1).$

The remaining crossings in $G^{\prime}$ correspond one-to-one to crossings in
$G$. ∎

######  Theorem 3.2.

One-Sided Crossing Minimization is -hard for trees.

## References

  * [1] Peter Eades and Nicholas C. Wormald  “Edge Crossings in Drawings of Bipartite Graphs”  In _Algorithmica_ 11.4, 1994, pp. 379–403  DOI: 10.1007/BF01187020
  * [2] Martin Harrigan and Patrick Healy  “ _k_ -Level Crossing Minimization Is NP-Hard for Trees”  In _Proc. International Workshop on Algorithms and Computation (WALCOM 2011)_ 6552, LNCS  Springer, 2011, pp. 70–76  DOI: 10.1007/978-3-642-19094-0˙9
  * [3] Xavier Muñoz, Walter Unger and Imrich Vrto  “One Sided Crossing Minimization Is NP-Hard for Sparse Graphs”  In _Proc. International Symposium on Graph Drawing (GD 2001)_ 2265, Lecture Notes in Computer Science  Springer, 2001, pp. 115–123  DOI: 10.1007/3-540-45848-4˙10
  * [4] Kozo Sugiyama, Shojiro Tagawa and Mitsuhiko Toda  “Methods for Visual Understanding of Hierarchical System Structures”  In _IEEE Trans. Syst. Man Cybern._ 11.2, 1981, pp. 109–125  DOI: 10.1109/TSMC.1981.4308636