Cheng, Xueqi; Wang, Yu; Liu, Yunchao; Zhao, Yuying; Aggarwal, Charu C.; Derr, Tyler. “Edge Classification on Graphs: New Directions in Topological Imbalance.” WSDM 2025 – Proceedings of the 18th ACM International Conference on Web Search and Data Mining (2025): 392-400. https://doi.org/10.1145/3701551.3703518.
Recent years have seen great success in using Graph Machine Learning (GML) for tasks like node and graph classification, and predicting links between nodes. However, edge classification—which has many real-world uses, such as analyzing social networks and improving cybersecurity—has not progressed as much, even with the rise of GML methods.
To address this gap, our study presents a comprehensive approach to edge classification. We identify a novel problem called the Topological Imbalance Issue, which happens when edges are unevenly distributed across classes. This imbalance affects the structure around each edge and reduces classification performance.
Inspired by recent work showing how node classification accuracy can vary with local graph patterns, we explore whether similar local structure differences affect edge classification. To do this, we introduce Topological Entropy (TE)—a new metric that measures how imbalanced the local edge class distribution is. Our results show that TE accurately reflects this local imbalance and that focusing on edges with high TE can improve edge classification.
Based on this insight, we propose two strategies:
- Topological Reweighting, which adjusts training weights based on TE, and
- TE Wedge-based Mixup, which creates synthetic edges between highly imbalanced areas to improve training.
We combine these into a new edge classification strategy called TopoEdge, designed specifically to address topological imbalance. Experiments on real-world datasets show that our methods significantly improve performance. Our code and data are available at https://github.com/XueqiC/TopoEdge, and we also provide curated datasets and testing setups to serve as a new benchmark for future edge classification research.
