- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper propose an efficient edge proximity operator for edge representation learning. It establishes a connection between edge-based and node-based PPR and employs weighted spanning-forest sampling to efficiently approximate edge proximity matrices. Based on this operator, the authors develop two variants, EPO-F and EPO-P, for structural embedding and edge feature propagation, respectively.
Critical strengths
The authors have released the source code.
Critical weaknesses
-
The paper establishes a connection between Edge-PPR and Node-PPR on the subdivision graph. However, mature Node-PPR algorithms can already efficiently approximate PPR on large-scale graphs and could be directly applied to the subdivision graph. Therefore, the necessity of introducing the subsequent forest-sampling framework is not sufficiently justified.
-
The research motivation is unclear, and the specific problem the paper aims to address is not clearly articulated. The introduction needs substantial improvement.
-
The baselines are outdated. The paper identifies TER, published in 2023, as the state-of-the-art method for edge representation learning. However, three years have passed since its publication. The authors should discuss subsequent advances in this area and clarify whether edge representation learning remains an active research topic.
Questions for authors
See above Cons.
Response to Reviewer 9Uyq
Thank you for your time and help. Below is our response to your comments.
[W1] Forest Sampling for EdgePPR
Many established PPR approximation methods employ push operations to accumulate probability mass for a given source or target. While these methods can be applied to the subdivision graph, our goal is to explicitly construct a sparse proximity operator covering all edges, which motivates the forest-sampling approach.
Specifically, each sampled forest provides root assignments for all nodes, allowing proximity estimates for all edges to be updated jointly. During Wilson sampling, walks terminate upon reaching the existing forest and inherit its root assignments, sharing computation across sources. Our algorithm constructs an approximation of the global Edge-PPR operator in near-linear time for fixed sampling parameters, with entry-wise error guarantees. The estimator is unbiased, in contrast to standard truncated push estimates. Furthermore, the sampling procedure directly bounds the number of nonzero entries by nnz$(\tilde{\Pi})\leq ml$, without requiring explicit thresholding or top-K truncation to enforce sparsity. Finally, independent forest samples can be generated in parallel, with the resulting acceleration demonstrated in Table 5. Together, these properties make forest sampling suitable for constructing the explicit Edge-PPR operator at scale.
[W2] Motivation
Our motivation is to enable explicit access to high-order edge proximities while maintaining scalability. Explicitly materializing the dense Edge-PPR matrix requires quadratic storage, making it impractical for large graphs. Matrix-free approaches such as TER avoid this cost but cannot directly apply entry-wise nonlinear transformations to the proximity matrix before factorization. EPO addresses this trade-off through a subdivision-graph reduction and forest sampling, which construct an explicitly accessible sparse approximation of Edge-PPR with theoretical guarantees. The resulting operator supports both nonlinear matrix factorization and high-order feature propagation. We have revised the Introduction to articulate this computational bottleneck, distinguish our objective from existing approaches, and explain how the proposed framework addresses it.
[W3] Recent Baseline
Our experimental baselines are not limited to methods published in 2023: Tables 1 and 2 already include TopoEdge (Cheng et al., WSDM 2025), a recent method addressing topological imbalance in edge classification. TER serves as a directly relevant comparator for our proximity-based matrix factorization approach, while TopoEdge represents more recent advances in edge classification.
We additionally evaluate EB-GNN (Barceló et al., ICML 2026), which learns edge representations through edge-based message passing. We adapt it to edge classification by applying an MLP classification head to its learned edge representations, using the same data splits and evaluation protocol. The AUC results on YelpChi and MAG are reported below; runs on the remaining datasets exceeded the time limit or encountered out-of-memory errors.
EB-GNN was originally evaluated on molecular edge-level regression and graph-level prediction tasks, rather than specifically optimized for edge classification. Although it does not achieve the best AUC in our evaluation, it advances edge-based graph learning by combining expressive message passing with efficient computation. Together with TopoEdge, this work demonstrates continued activity in the field.
We have incorporated these revisions into the manuscript. Thank you again for your helpful suggestions and valuable insights.