acceptodds
Under review as a conference paper at ICLR 2027

EPO: An Efficient Edge Proximity Operator for Edge Representation Learning

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Edge representation learning, subdivision graph expansion, spanning forest sampling

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_9UyqOpenReview ↗
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
  1. 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.

  2. The research motivation is unclear, and the specific problem the paper aims to address is not clearly articulated. The introduction needs substantial improvement.

  3. 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.

1 comment

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-KK 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.

MethodYelpChiMAG
EB-GNN0.78510.9647

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.

Reviewer_VSfUOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes EPO, which is an efficient edge representation learning that approximates Personalized PageRank using weighted spanning-forest sampling. The author introduces two variants (EPO-F and EPO-P), which achieves strong edge classification performance and scalability on large graphs.

Critical strengths

The paper addresses an important (and interesting) problem in graph representation learning.

The author establishes a theoretical contribution between edge-based PPR and node-based PPR

The empirical results demonstrate the effectiveness of the proposed method

Critical weaknesses

Although the paper establishes a theoretical connection between Edge-PPR and Node-PPR, its overall framework builds upon existing mechanisms (PPR, spanning-forest sampling, and MF). The paper needs to clarify its novelty beyond adapting these methods

The proposed scaling (lines 319 ~ ) can produce values of 1 (logarithm is zero), potentially discarding weak proximity signals

The theoretical analysis guarantees entry-wise approximation of Edge-PPR. However, it does not establish how approximation errors affect the learned representations

No feature-only MLP or straightforward edge-PPR propagation baseline is included

Questions for authors

Please see above

3 comments

Response to Reviewer VSfU

Thank you for your time and help. Below is our response to your comments.


[W1] Novelty

Our contribution lies in enabling explicit and scalable approximation of the global edge-proximity operator, rather than introducing PPR or matrix factorization themselves. Specifically, we establish an exact Edge-PPR-to-Node-PPR reduction on a subdivision graph with n+mn+m nodes and 2m2m edges, avoiding potentially quadratic line-graph expansion. We then derive a rooted-forest interpretation and develop parallel sampling to jointly estimate proximities for all edges. The explicit sparse operator contains at most mlml nonzero entries for ll samples, with unbiased entry estimates and concentration guarantees. Forest generation takes expected linear time for fixed sampling parameters. This addresses a key limitation: dense Edge-PPR requires quadratic storage, while matrix-free methods such as TER cannot directly apply entry-wise nonlinear transformations. EPO supports these transformations through scalable sparse computation. Ablations demonstrate their benefit, and efficiency experiments establish scalability to graphs with over 15 million edges.


[W2] Logarithm

After scaling, the smallest nonzero entries equal 1 and become zero after taking the logarithm. This performs threshold-based sparsification by removing the weakest observed proximities. Similarly, STRAP (Yin and Wei, 2019) retains approximate proximity reserves of at least ϵ/2\epsilon/2 before scaling and logarithmic transformation. Removing the resulting zeros further reduces storage and factorization costs. We have corrected the statement to specify that the scaling ensures nonnegative logarithms.

Empirically, logarithm improves AUC over the untransformed operator on all six datasets. We also evaluate square root, which preserves singleton observations. Its improvements are inconsistent, whereas logarithm achieves the highest AUC throughout. These results support our choice, although they do not isolate the effect of thresholding alone. We have added these results to the revised manuscript.

AblationMOOCYelpChiMAGRedditMINDDBLP
Without transformation0.83880.83010.98630.92840.97760.9052
Square root0.83910.82150.98860.93800.97170.8841
Logarithm (EPO-F)0.86330.84260.99890.94660.98470.9176

[W3] Error Analysis

Following Wang et al. (2023), we analyze propagation and reconstruction errors separately. Let E=Π~−ΠE=\tilde{\Pi}-\Pi. Applying Theorem 4.3 with failure probability δ/m2\delta/m^2 per entry and a union bound gives max⁡i,j∣Eij∣≤ϵ\max_{i,j}|E_{ij}|\leq\epsilon and ∥E∥F≤mϵ\|E\|_F\leq m\epsilon with probability at least 1−δ1-\delta, under the correspondingly increased sampling budget.

EPO-P: For fixed encoded features HH, let ZP=ΠHZ_P=\Pi H and Z~P=Π~H\tilde Z_P=\tilde{\Pi}H. Since their difference is EHEH, we obtain ∥Z~P−ZP∥F≤∥E∥2∥H∥F≤mϵ∥H∥F\|\tilde Z_P-Z_P\|_F\leq\|E\|_2\|H\|_F\leq m\epsilon\|H\|_F, directly connecting operator error to propagation error.

EPO-F: Let A=gs(Π)A=g_s(\Pi) and A~=gs(Π~)\tilde A=g_s(\tilde{\Pi}), where gs(x)=log⁡(max⁡{1,sx})g_s(x)=\log(\max\{1,sx\}) acts entry-wise and s=α∗l/αs=\alpha^*l/\alpha. This agrees with our sampled-matrix transformation and is ss-Lipschitz, giving ∥A~−A∥F≤s∥E∥F\|\tilde A-A\|_F\leq s\|E\|_F. Let AkA_k be the best rank-kk approximation of AA. If the reconstruction A^k\widehat A_k computed from A~\tilde A satisfies a (1+η)(1+\eta) relative SVD-error guarantee, then ∥A−A^k∥F≤(1+η)∥A−Ak∥F+(2+η)∥A−A~∥F\|A-\widehat A_k\|_F\leq(1+\eta)\|A-A_k\|_F+(2+\eta)\|A-\tilde A\|_F. This separates intrinsic low-rank error from operator-estimation error; exact truncated SVD gives η=0\eta=0.


[W4] Baselines

We add two baselines to distinguish the contributions of edge attributes, structural propagation, and feature encoding. MLP directly classifies raw edge features XEX_E without using graph structure. EPO-P (w/o FE) removes the feature encoder before propagation, computing Π~XE\tilde{\Pi}X_E and feeding the propagated features into an MLP classifier. In contrast, EPO-P propagates encoded features as Π~fθ(XE)\tilde{\Pi}f_\theta(X_E). The AUC results are reported below.

BaselineMOOCYelpChiMAGRedditMINDDBLP
MLP0.59230.72460.52100.64910.69250.4990
EPO-P (w/o FE)0.79040.75520.96360.90110.90720.7703

Direct propagation consistently outperforms MLP across all six datasets, demonstrating the benefit of incorporating graph structure. EPO-P further improves over direct propagation on every dataset, supporting the effectiveness of feature encoding before propagation.


We have incorporated these revisions into the manuscript. Thank you again for your helpful suggestions and valuable insights.

Thank you for the detailed rebuttal and additional experiments. However, some of my main concerns remain:

  • While the advantages of forest sampling are better explained, the paper still lacks a direct comparison with existing efficient PPR approximation methods.
  • The additional experiments show its empirical benefits, but they do not clarify whether removing weak proximity signals through logarithmic scaling causes information loss.
  • The new error bounds are helpful, but they can be loose for large graphs. In addition, tehy do not directly guarantee the stability or performance of the learned representations.

Overall, the rebuttal addresses some of my concerns, but some of them are still remaining (novelty and theoretical justification). Therefore, I am inclined to maintain my original rating

AuthorsOpenReview ↗

Response to Reviewer VSfU

Thank you for your response and further comments. Below, we provide additional analysis and experiments.


[W1] Comparison with PPR approximation methods

Our original experiments focused on evaluating EPO as an edge representation learning framework rather than benchmarking PPR approximation algorithms. TER, a prior method that also exploits EdgePPR, uses matrix factorization to compute representation vectors directly. Our work establishes an exact correspondence between EdgePPR and NodePPR on a subdivision graph. This correspondence allows PPR algorithms to explicitly construct an approximate edge proximity matrix and apply nonlinear transformations before factorization, which is a central advantage of EPO.

The PPR computation module is therefore replaceable: compatible PPR approximation algorithms can be integrated into EPO through this correspondence. Building on this general connection, we further derive a weighted rooted-spanning-forest interpretation of EdgePPR and develop an efficient parallel sampling algorithm that jointly estimates proximities for all edges. The raw estimator is unbiased and admits pointwise concentration guarantees, while ll forest samples yield at most mlml nonzero entries.

We additionally compare EPO with SpeedPPR [1] and PPFV [2] on YelpChi and a synthetic Barabási–Albert (BA) graph with 10,000 nodes and 50,000 edges. We adjust each method’s approximation parameters to obtain comparable full-operator construction times and measure the corresponding relative Frobenius error.

DatasetMetricSpeedPPRPPFVEPO
YelpChiTime (s)11.9212.3511.67
Error8.2×10−48.2\times 10^{-4}1.1×10−31.1\times 10^{-3}9.6×10−49.6\times 10^{-4}
BATime (s)19.6118.0519.24
Error9.3×10−49.3\times 10^{-4}9.7×10−49.7\times 10^{-4}1.1×10−31.1\times 10^{-3}

We find that EPO achieves comparable PPR approximation accuracy to both baselines under similar running times.

[1] Wu et al. Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push. SIGMOD, 2021.

[2] Liao et al. Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches. SIGMOD, 2023.


[W2] Logarithm

We acknowledge that the logarithmic transformation removes singleton observations. To isolate the effect of this removal, we add two ablation variants. Let C=(α∗l/α)Π~C=(\alpha^*l/\alpha)\tilde{\Pi} denote the scaled proximity matrix, whose entries are sampling counts. Log1p applies log⁡(1+Cij)\log(1+C_{ij}), preserving every nonzero entry. Log1p w/o singletons applies I[Cij≥2]log⁡(1+Cij)\mathbb{I}\left[C_{ij}\geq2\right]\log(1+C_{ij}), removing only singleton observations. The two variants assign identical values to entries with Cij≥2C_{ij}\geq2, differing solely in whether singletons are retained. The additional AUC results are reported below.

TransformationMOOCYelpChiMAG
Log1p0.86330.84290.9988
Log1p w/o singletons0.86300.84270.9988
Log (EPO-F)0.86330.84260.9989

Retaining singleton observations yields only small AUC gains: 0.0003 on MOOC and 0.0002 on YelpChi, with no change on MAG. These results suggest that singleton removal has a limited empirical effect under the evaluated settings. Meanwhile, removing the resulting zero entries increases matrix sparsity and can reduce storage and factorization costs. This serves a purpose similar to top-k filtering in representation learning, although our procedure uses a count threshold rather than retaining a fixed number of entries.


[W3] Further error analysis

We supplement the previous worst-case bounds with a mean-square analysis that directly exploits the forest estimator. For a fixed feature matrix HH independent of the sampled forests, let c=α/α∗c=\alpha/\alpha^*. Independence across forest samples and the doubly stochastic property of Π\Pi yield E∥(Π~−Π)H∥F2=(c∥H∥F2−∥ΠH∥F2)/l≤c∥H∥F2/l\mathbb{E}\|(\tilde{\Pi}-\Pi)H\|_F^2=(c\|H\|_F^2-\|\Pi H\|_F^2)/l\leq c\|H\|_F^2/l. Thus, the mean-square propagation error normalized by the input feature energy decreases as 1/l1/l, without the explicit graph-size factor introduced by the previous mϵm\epsilon bound.

Our theoretical objective is to quantify how operator approximation affects representation computation: propagation error in EPO-P and low-rank reconstruction error in EPO-F. Classification performance after retraining cannot be guaranteed from operator accuracy alone; such a result requires additional assumptions on the data distribution, optimization procedure, and classifier. We therefore assess downstream performance and its variability empirically. Appendix E.4 and Table 4 already report standard deviations over five independent runs, with forests independently resampled in every run.


We hope these revisions address your remaining concerns. Thank you again for your valuable suggestions. If you have any further questions or suggestions, we would be happy to provide additional clarification.

Reviewer_BH6AOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper addresses the challenge of edge-wise graph representation learning (GRL). Existing methods either aggregate node embeddings, expand line graphs, or rely on implicit proximity approximations like randomized SVD (e.g., TER) which cannot accommodate element-wise non-linear transformations. To overcome these limitations, the authors introduce EPO. EPO has two model variants, including EPO-F that applies entry-wise log transformation followed by truncated SVD for structural edge embeddings, and EPO-P that treats the operator as a feature propagation matrix over edge features. Evaluation results on six real-world benchmarks on edge classification show that EPO achieves competitive or SOTA performance with higher efficiency.

Critical strengths

S1: The reduction from Edge-PPR to Node-PPR on the subdivision graph (i.e., Theorem 4.1) and its rooted spanning forest interpretation (i.e., Theorem 4.2) are elegant and mathematically solid

S2: Unlike previous methods (e.g., TER), EPO constructs an explicitly sparse Edge-PPR matrix, which allows element-wise non-linear transformations.

S3: The evaluation results across six benchmarks against thirteen baselines are comprehensive.

Critical weaknesses

W1: The evaluation is solely restricted to edge classification. As a general edge representation learning framework, the paper lacks evaluations on other edge-centric tasks.

W2: Although forest sampling yields a sparse proximity matrix, computing a truncated SVD of 256 dimension on an m x m matrix for large-scale graphs can still encounter severe memory and time bottlenecks compared to EPO-P.

Questions for authors

Q1: Could the authors provide evaluation results or discussion on other edge-centric tasks, such as link prediction or edge regression?

Q2: How does the sampling efficiency and convergence behave on power-law graphs with isolated/low-degree nodes or extreme super nodes?

Q3: The ablation study clearly demonstrates the benefit of the log-transform. Did the authors explore other non-linear functions?

2 comments

Response to Reviewer BH6A

Thank you for your time and help. Below is our response to your comments.


[W1 & Q1] Edge-Centric Tasks

Following TER and AER (Wang et al., 2023), our evaluation focuses on edge classification. We acknowledge that additional tasks would strengthen the evidence for broader applicability.

  • Edge regression. Our six benchmarks provide categorical edge labels rather than continuous regression targets in the current setup. Regression would require another dataset or a separately defined task. EPO could be adapted by replacing the classification head and loss, with the target excluded from input features to prevent leakage. We have not yet evaluated this extension.

  • Link prediction. EPO represents edges present in the input graph, whereas link prediction requires scoring missing candidate edges. This requires additional candidate-edge representation and scoring mechanisms, with held-out links excluded from operator construction.


[W2] SVD Costs

As discussed in Section 4.4, EPO-F performs truncated SVD on a sparse proximity matrix. With ll sampled forests, each row contains at most ll nonzero entries, giving nnz(Π~)≤ml\mathrm{nnz}(\widetilde{\Pi})\leq ml. Sparse storage and computation avoid materializing a dense m×mm\times m matrix.

With k=256k=256, the complete EPO-F pipeline takes 6,447 seconds on DBLP, compared with approximately 8,400 seconds for TER+AER(G) (Table 2). We additionally measure the runtime and peak memory of the SVD stage:

DatasetTime (s)Peak Memory (GB)
Reddit661.85
MIND1024.23
DBLP85131.68

SVD completes in approximately 14 minutes with 31.68 GB peak memory on DBLP, demonstrating feasibility at the evaluated scale of over 15 million edges.


[Q2] Power-Law Graphs

Our analysis assumes a connected input graph and excludes isolated nodes. Appendix D establishes an expected sampling-time bound without requiring a particular degree distribution. Sampling one forest takes O(wmax⁡(n+m))O(w_{\max}(n+m)) expected time, where wmax⁡=(1−α∗)/(α∗dmin⁡)w_{\max}=(1-\alpha^*)/(\alpha^*d_{\min}) and dmin⁡d_{\min} is the minimum degree in the subdivision graph. Since dmin⁡≥1d_{\min}\geq1, the bound is linear in graph size for fixed α\alpha, including for connected power-law inputs with low-degree nodes and high-degree hubs.

Empirically, we compare connected Barabási–Albert (BA) graphs, exhibiting approximately power-law degree distributions, with connected regular graphs. Each pair has identical node and edge counts and average degree 10. Each new BA node attaches to five existing nodes; the counterpart is a 10-regular graph. We measure forest sampling and proximity-matrix construction time.

NodesEdgesBA graph time (s)Regular graph time (s)
10,00050,0001912
100,000500,000186119
1,000,0005,000,0001,9751,207

Although BA graphs take longer, runtime grows approximately linearly for both graph families, supporting scalability under heterogeneous degree distributions.

For convergence, Theorem 4.3 provides a pointwise concentration guarantee whose sample requirement depends on α\alpha, ϵ\epsilon, and δ\delta, rather than the degree distribution. It therefore applies to connected power-law graphs. This does not imply identical empirical runtimes or errors across structures, but shows that degree heterogeneity does not invalidate the guarantee.


[Q3] Nonlinear Transformations

Our logarithmic transformation follows proximity-based matrix factorization methods including NetMF, STRAP, and LEMANE. It compresses the dynamic range of proximity values, reducing the dominance of large entries while increasing the relative contribution of smaller retained entries.

We additionally evaluate the element-wise square-root transformation, inspired by Hellinger PCA (Lebret and Collobert, 2014), keeping the sampled matrix, embedding dimension, data splits, and training settings unchanged. The AUC results are:

TransformationMOOCYelpChiMAGRedditMINDDBLP
Without transformation0.83880.83010.98630.92840.97760.9052
Square root0.83910.82150.98860.93800.97170.8841
Logarithm (EPO-F)0.86330.84260.99890.94660.98470.9176

Square root yields inconsistent improvements, whereas logarithm achieves the highest AUC across all six datasets, supporting our choice.


We have incorporated these revisions and additional results into the manuscript. Thank you again for your helpful suggestions.

Thank you for your detailed response. Most of my concerns have been addressed. I will keep my score at 3.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.