Topology-Imbalance Learning for Semi-Supervised Node Classification

1 Introduction

• TINL is introduced as a graph-specific imbalance problem arising from the positions of labeled nodes, unlike quantity imbalance arising from class counts.Source: §1 · pp. 1–2
• Topology imbalance is ubiquitous, pernicious, and orthogonal to quantity imbalance: asymmetric labeled-node positions can cause influence conflict or insufficiency and shift decision boundaries.Unlike quantity-imbalance approaches focused on class totals, TINL considers each labeled node’s position.Source: §1 · p. 2
• Totoro measures topology imbalance through influence conflict, while ReNode adaptively reweights labeled nodes according to their positions relative to class boundaries.Nodes with less conflict receive higher training weights; nodes with more conflict receive lower weights.Source: §1 · p. 2
• Experiments across topology-imbalance, quantity-imbalance, and large-scale graph scenarios, using multiple GNNs, demonstrate ReNode’s effectiveness and generalizability.The paper also proposes sensitivity to topology imbalance as a perspective for evaluating GNN architectures.Source: §1 · p. 2

2.1 Notations and Preliminary

• The semi-supervised setting uses an undirected, unweighted graph with far fewer labeled than unlabeled nodes and focuses on homogeneously connected graphs.The classifier is trained on labeled nodes to predict labels for the unlabeled set.Source: §2.1 · pp. 2–3

2.2 Understanding Topology Imbalance via Label Propagation

• Label Propagation’s predictions approximate GNN predictions, allowing node influence boundaries to reflect GNN decision boundaries and reveal shifts from both label counts and positions.Even quantity-balanced sampling can shift the influence boundary toward the large class when small-class labels lie near the class boundary.Source: §2.2 · p. 3, Figure 2 · p. 3

2.3 Measuring Topology Imbalance by Influence Conflict

• Across 50 training sets, overall conflict had a −0.618 Pearson correlation with GCN performance (p < 0.01), supporting Totoro’s dataset-level measurement of topology imbalance.The section also uses node-level conflict to locate labeled nodes relative to class boundaries.Source: Figure 3 · p. 4, §2.3 · p. 5
• Totoro estimates a labeled node’s proximity to class boundaries from its expected influence conflict with labeled nodes of other classes across the graph.Higher Totoro values indicate greater boundary proximity; the dataset-level score sums labeled-node conflict.Source: §2.3 · pp. 4–5

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

• ReNode uses a Totoro-based cosine schedule to increase training weights for labeled nodes near class centers and reduce weights for nodes near boundaries.It can be combined with class-frequency reweighting for quantity and topology imbalance; the section also describes a large-scale implementation using estimated Personalized PageRank.Source: §2.4 · p. 5

3.1 Datasets

• Experiments cover CORA, CiteSeer, Pubmed, Photo, Computers, Reddit, and MAG-Scholar, with five dataset splits and three runs per split.The first five datasets are used in the transductive setting, while Reddit and MAG-Scholar are used inductively.Source: §3.1 · p. 6

3.3 ReNode for the Compound Scene of TINL and QINL

• ReNode significantly outperforms general and graph-specific quantity-imbalance methods in most compound-imbalance situations, including when ρ=10.The compound experiments use step imbalance with ρ=5 or 10, µ=0.5, a 5% labeling ratio, and GCN as the backbone.Source: Table 3 · p. 7, §3.3 · p. 7

3.2 ReNode for the Pure Topology-imbalance Issue

• ReNode improves Weighted-F1 and Macro-F1 for all six tested GNNs in most cases, with its largest GCN gains on highly topology-imbalanced data.CiteSeer shows less improvement, which the authors attribute to poor connectivity weakening conflict-based position detection.Source: §3.2 · p. 7

3.4 ReNode for Large-scale Graphs

• ReNode improves Weighted-F1 over PPRGo on Reddit and MAG-Scholar across labeling sizes and imbalance settings.The reported improvement is greater with larger labeling sets; when labeling is extremely sparse and influence conflict is negligible, ReNode can exhibit a cold-start problem.Source: Figure 4 · p. 8, §3.4 · p. 8

3.3 ReNode for the Compound Scene of TINL and QINL

• The reported topology-imbalance sensitivity ranking is GCN > PPNP > GAT.The comparison uses Weighted-F1.Source: Figure 5 · p. 8

4.1 Evaluating GNNs from the Aspect of Topology-Imbalance Sensitivity

• GCN is highly sensitive to topology imbalance, GAT performs best at high imbalance, and PPNP performs well at low imbalance without GCN’s sharp decline.The authors relate these patterns to GCN’s neighbor averaging, GAT’s adaptive neighbor weights, and PPNP’s ability to aggregate distant-node information.Source: §4.1 · pp. 8–9
• The authors did not implement Cluster-GCN [8] or APPNP, citing their low efficiency [2] when handling the enormous MAG-Scholar dataset.Source: §4.1 · p. 8
• Topology-imbalance sensitivity may partly explain training-set-dependent GNN rankings and offers an additional perspective for evaluating architectures.The paper connects this perspective to earlier observations that GNN performance rankings vary with training-set selection [43].Source: §4.1 · p. 9

4.2 Limitations of Method

• ReNode is designed for homogeneously connected graphs, and improves less with poor connectivity or extremely low labeling ratios, where conflicts provide insufficient topological-position information.Source: §4.2 · p. 9

• Most existing imbalance methods address unequal class quantities through selection, resampling, or class-level reweighting, but do not account for graph topology imbalance.Source: §5 · p. 9
• ReNode differs from class-level reweighting by assigning weights to individual nodes.Source: §5 · p. 9
• Totoro locates labeled nodes relative to class boundaries using influence conflicts across the graph, rather than feature similarity among the few labeled nodes.The paper argues that graph connections provide more reliable prior knowledge than feature similarity for this purpose.Source: §5 · p. 9
• Unlike anchor-based methods that locate absolute node positions, Totoro estimates relative positions to class boundaries, distinguishes class-specific influence, and does not depend on anchor nodes.Source: §5 · p. 10

• The paper identifies topology-imbalance node representation learning as a previously unstudied graph-specific problem and links it with quantity imbalance through shifted node-influence boundaries.Source: §6 · p. 10
• Across TINL-only, combined TINL and QINL, and large-scale settings, empirical results support ReNode’s effectiveness; Totoro measures topology imbalance and ReNode adaptively adjusts labeled-node weights.Source: §6 · p. 10
• The authors call for stronger theoretical or experimental support and identify measuring and addressing topology imbalance beyond node classification as an open challenge.Source: §6 · p. 10

• The implementation uses Python 3.7, torch 1.9.1+cu111, and torch-geometric 2.0.1.Source: A More Details of Dataset and… · p. 14
• The appendix identifies dataset-statistics tables and lists sources for Planetoid citation, Amazon co-purchasing, Reddit, and MAG-Scholar datasets.Source: Table 4 · p. 15, A More Details of Dataset and… · p. 15
• Experiments use five dataset splits and three training runs per split, with final performance calculated over 15 repetitions.Source: A More Details of Dataset and… · p. 15
• Hyperparameters are tuned on validation data, with listed search ranges for hidden dimension, cosine-annealing bounds, learning rate, and dropout.The appendix also states that training uses Adam, learning-rate decay, and early stopping.Source: A More Details of Dataset and… · p. 15

B Supplement to the ReNode Method

• The tested alternatives include linear decay based on original Totoro values, linear decay based on Totoro rank, and piece-wise discrete weights.These are compared with the relative-ranking re-weighting method in ReNode.Source: B Supplement to the ReNode Method · p. 16
• Cosine annealing works best among the tested weight schedules, with greater attention to nodes with middle-level conflict than linear decay.The supplement says weighting by original Totoro values is not robust and can be strongly affected by outliers.Source: B Supplement to the ReNode Method · p. 16
• With small, randomly sampled training sets, hard nodes may lie near true class boundaries for some categories but far from them for others, shifting learned boundaries.The passage explains why relying on hard nodes can confuse class prototypes; ReNode instead gives more weight to nodes farther from graph class boundaries.Source: B Supplement to the ReNode Method · p. 16

C Settings of Dataset Topology-Imbalance Levels

• For each dataset, 100 training sets are randomly sampled and their overall conflict is calculated.Source: C Settings of Dataset… · p. 16
• The sets with the highest, middle, and lowest overall conflict define the high-, middle-, and low-level topology-imbalance settings.Source: C Settings of Dataset… · p. 16
• Reported results for each dataset and level are averages over the three selected training sets; their conflict values are shown in Table 5.Source: C Settings of Dataset… · p. 16

D Submission Checklist

• The authors say the abstract and introduction reflect the paper’s contributions and scope, and that limitations are discussed in Section 4.2.Source: D Submission Checklist · p. 16
• The checklist marks theoretical assumptions and proofs as not applicable and states that the authors reviewed ethics guidelines and consider there to be no obvious negative societal effect.Source: D Submission Checklist · p. 16
• The checklist says code, data, and instructions are included in the supplement, training details are in the paper and appendix, and error bars and random seeds are reported.Compute resources are included in the appendix.Source: D Submission Checklist · p. 17
• The authors report citing existing assets and documenting their licenses, while stating that they release no new assets.Source: D Submission Checklist · p. 17
• The checklist says the datasets are publicly available and contain no personally identifiable information or offensive content.Source: D Submission Checklist · p. 17