# Edge Classification on Graphs: New Directions in Topological Imbalance

arXiv: https://arxiv.org/abs/2406.11685 · HTML: https://mlsanity.com/paper/2406.11685/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 55 references that are in the map.
- First posted on arXiv 17 Jun 2024.

## Builds on (most cited first, 30 of 30)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [mixup: Beyond Empirical Risk Minimization](https://mlsanity.com/paper/1710.09412/) (2017)
- [WILDS: A Benchmark of in-the-Wild Distribution Shifts](https://mlsanity.com/paper/2012.07421/) (2020)
- [Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization](https://mlsanity.com/paper/1911.08731/) (2019)
- [In Search of Lost Domain Generalization](https://mlsanity.com/paper/2007.01434/) (2020)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [What is the Effect of Importance Weighting in Deep Learning?](https://mlsanity.com/paper/1812.03372/) (2018)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [A Fine-Grained Analysis on Distribution Shift](https://mlsanity.com/paper/2110.11328/) (2021)
- [GraphSMOTE: Imbalanced Node Classification on Graphs with Graph Neural Networks](https://mlsanity.com/paper/2103.08826/) (2021)
- [G-Mixup: Graph Data Augmentation for Graph Classification](https://mlsanity.com/paper/2202.07179/) (2022)
- [Edge-labeling Graph Neural Network for Few-shot Learning](https://mlsanity.com/paper/1905.01436/) (2019)
- [Extending the WILDS Benchmark for Unsupervised Adaptation](https://mlsanity.com/paper/2112.05090/) (2021)
- [Community Interaction and Conflict on the Web](https://mlsanity.com/paper/1803.03697/) (2018)
- [Topology-Imbalance Learning for Semi-Supervised Node Classification](https://mlsanity.com/paper/2110.04099/) (2021)
- [Adapting Membership Inference Attacks to GNN for Graph Classification: Approaches and Implications](https://mlsanity.com/paper/2110.08760/) (2021)
- [SDGNN: Learning Node Representation for Signed Directed Networks](https://mlsanity.com/paper/2101.02390/) (2021)
- [TAM: Topology-Aware Margin Loss for Class-Imbalanced Node Classification](https://mlsanity.com/paper/2206.12917/) (2022)
- [Position-aware Structure Learning for Graph Topology-imbalance by Relieving Under-reaching and Over-squashing](https://mlsanity.com/paper/2208.08302/) (2022)
- [Understanding Why Generalized Reweighting Does Not Improve Over ERM](https://mlsanity.com/paper/2201.12293/) (2022)
- [Imbalanced Graph Classification via Graph-of-Graph Neural Networks](https://mlsanity.com/paper/2112.00238/) (2021)
- [Class-Imbalanced Learning on Graphs: A Survey](https://mlsanity.com/paper/2304.04300/) (2023)
- [Is Importance Weighting Incompatible with Interpolating Classifiers?](https://mlsanity.com/paper/2112.12986/) (2021)
- [Distance-wise Prototypical Graph Neural Network in Node Imbalance Classification](https://mlsanity.com/paper/2110.12035/) (2021)
- [Fused Gromov-Wasserstein Graph Mixup for Graph-level Classifications](https://mlsanity.com/paper/2306.15963/) (2023)
- [A Topological Perspective on Demystifying GNN-Based Link Prediction Performance](https://mlsanity.com/paper/2310.04612/) (2023)
- [Structure Enhanced Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2201.05293/) (2022)
- [AttrE2vec: Unsupervised Attributed Edge Representation Learning](https://mlsanity.com/paper/2012.14727/) (2020)
- [Signed Node Relevance Measurements](https://mlsanity.com/paper/1710.07236/) (2017)

## Built on by (most cited first, 4 of 4)

- [Bridging Theory and Practice in Link Representation with Graph Neural Networks](https://mlsanity.com/paper/2506.24018/) (2025)
- [GNNs Meet Sequence Models Along the Shortest-Path: an Expressive Method for Link Prediction](https://mlsanity.com/paper/2507.07138/) (2025)
- [Advancing Edge Classification through High-Dimensional Causal Modeling of Node-Edge Interplay](https://mlsanity.com/paper/2605.00374/) (2026)
- [Towards Faithful Graph Explanations with Synergistic Edge Effects via Granular Balls](https://mlsanity.com/paper/2607.21381/) (2026)

## Abstract (arXiv)

Recent years have witnessed the remarkable success of applying Graph machine learning (GML) to node/graph classification and link prediction. However, edge classification task that enjoys numerous real-world applications such as social network analysis and cybersecurity, has not seen significant advancement. To address this gap, our study pioneers a comprehensive approach to edge classification. We identify a novel `Topological Imbalance Issue', which arises from the skewed distribution of edges across different classes, affecting the local subgraph of each edge and harming the performance of edge classifications. Inspired by the recent studies in node classification that the performance discrepancy exists with varying local structural patterns, we aim to investigate if the performance discrepancy in topological imbalanced edge classification can also be mitigated by characterizing the local class distribution variance. To overcome this challenge, we introduce Topological Entropy (TE), a novel topological-based metric that measures the topological imbalance for each edge. Our empirical studies confirm that TE effectively measures local class distribution variance, and indicate that prioritizing edges with high TE values can help address the issue of topological imbalance. Based on this, we develop two strategies - Topological Reweighting and TE Wedge-based Mixup - to focus training on (synthetic) edges based on their TEs. While topological reweighting directly manipulates training edge weights according to TE, our wedge-based mixup interpolates synthetic edges between high TE wedges. Ultimately, we integrate these strategies into a novel topological imbalance strategy for edge classification: TopoEdge. Through extensive experiments, we demonstrate the efficacy of our proposed strategies on newly curated datasets and thus establish a new benchmark for (imbalanced) edge classification.