EPO: An Efficient Edge Proximity Operator for Edge Representation Learning

Graph representation learning aims to encode high-dimensional and sparse graph data into low-dimensional dense representations. Despite substantial progress in node representation learning, edge-wise representation learning remains relatively underexplored, and directly adapting node-wise methods often fails to adequately capture edge-specific topology and attributes. To address this limitation, we propose EPO, an efficient and effective framework that jointly models structural proximity and edge features. We first establish a connection between edge-based Personalized PageRank and node-based Personalized PageRank on the corresponding subdivision graph, providing a spanning-forest interpretation of high-order edge proximity. Based on this connection, EPO employs a parallel extension of Wilson's algorithm to efficiently approximate a sparse edge proximity operator with theoretical guarantees. Using this operator, we further develop two models: EPO-F learns edge representations from a matrix-factorization perspective, whereas EPO-P directly propagates edge features to capture high-order structural information. Extensive experiments on six real-world datasets show that our models achieve the best or second-best performance in edge classification while maintaining competitive computational efficiency. Moreover, EPO scales effectively to graphs containing more than 15 million edges, demonstrating its applicability to large-scale edge-wise graph learning.